刪除機器學習模型中的認證數(shù)據(jù)

引用：

Chuan Guo,Tom Goldstein,Awni Hannun,et al. Certified Data Removal from Machine Learning Models[J],2020

摘要

良好的數(shù)據(jù)管理需要根據(jù)數(shù)據(jù)所有者的請求刪除數(shù)據(jù)。這就提出了一個問題，即一個隱含存儲訓練數(shù)據(jù)信息的受過訓練的機器學習模型，是否以及如何會受到這種移除請求的影響。是否有可能從機器學習模型中“移除”數(shù)據(jù) ?。我們?yōu)榫€性分類器開發(fā)了一個認證刪除機制，并以經(jīng)驗研究學習設(shè)置，在其中該機制是實際的。

1. 介紹

機器學習模型通常在第三方數(shù)據(jù)上進行訓練，當一方要求將其數(shù)據(jù)從此類在線平臺上移除時，就會產(chǎn)生這樣一個問題，即此類請求將如何影響在移除之前受訓的模型。當模型受到數(shù)據(jù)中毒攻擊的負面影響時，也會出現(xiàn)類似的問題。因此在不從頭開始重新訓練模型的情況下，是否可能從模型中“刪除”數(shù)據(jù) ?

我們在一個稱為認證移除的框架中研究這個問題，理論上保證對手不能提取從模型中移除的訓練數(shù)據(jù)的信息。受差異隱私(Dwork,2011)的啟發(fā)，認證刪除邊界模型之間的最大分歧訓練的數(shù)據(jù)集與一些實例刪除和模型訓練的數(shù)據(jù)集，從不包含那些實例。這保證了成員資格推理攻擊對從模型中移除的數(shù)據(jù)不成功。強調(diào)認證移除是一個非常強的移除概念;在實際應用中，較少約束的概念同樣可以滿足數(shù)據(jù)所有者移除的期望

2. 除認證

D 是一個固定的訓練數(shù)據(jù)集，A 是一個(隨機)學習算法，它訓練一個模型輸出 h∈H，即 A:D→H。我們想從 A 的輸出中移除一個訓練樣本 x∈D。

為此，我們定義了一個數(shù)據(jù)刪除機制 M 應用于 A (D)，目的是消除 x 的影響。如果移除成功，m 的輸出應該很難與應用的 Dx 的輸出區(qū)分開來。對于>0，使用刪除機制執(zhí)行-認證的 removal(-CR)來學習算法 A，如果 ?T 三角形數(shù)據(jù)集 H,D 三角形 X, X∈D

還定義了一個更寬松的概念(?, δ)-如果 ?T ? H,D ? X,x ∈ D 的刪除:

概念上，δ 上界方程 1 中最大散度界失敗的概率。

具有 ? = 0 的瑣碎的認證刪除機制 M 完全忽略了 A(D)，直接評估 A(Dx)，也就是說，它設(shè)置 M(A(D),D,x) =A(Dx)。這種刪除機制對許多模型來說是不切實際的，因為它可能需要在每次刪除訓練樣本時重新訓練模型。需要尋找去除成本為 O(n)或更少的機制 M，它具有較小的常數(shù)，其中 n = |D|是訓練集大小。

參數(shù)不可分辨性的不足。完全刪除另一個替換選擇是通過斷言的輸出，M (A (D), D, x)是足夠接近的(D x)?？紤]線性回歸量訓練數(shù)據(jù)集 D = {(e_1, 1), (e_2, 2),…,(e_d, d)}，其中 e_i 是 R_d 的標準基向量。用 0 初始化的回歸向量，或者具有權(quán)重衰減懲罰的回歸向量，將在 w_i (e_i, i)上設(shè)置一個非零權(quán)重，在 d 中包含，在 w_i 上設(shè)置一個零權(quán)重。在這種情況下，留下 w_i 非零仍然顯示(e_i, i)出現(xiàn)在訓練中。

不同隱私的關(guān)系。我們的認證移除方法與不同的隱私有關(guān)，但有重要的區(qū)別。差異隱私聲明：

其中 D 和 D’僅在一個樣本中不同。由于 D 和 D x 僅在一個樣本中不同，因此可以直觀地看出 A 的差異隱私是認證移除的充分條件。

雖然差別隱私是一個充分條件，但它不是認證移除的必要條件。因此，我們將認證刪除的研究視為分析效用和刪除效率之間的權(quán)衡，從零開始的再培訓和不同的隱私在光譜的兩端，而刪除中間。

3. 刪除機制

3.1 線性分類器

用 D = {(x_1, y_1)，…，(x_n, y_n)}分為 n 個樣本的訓練集，?i: x_i∈R^d，對應的目標為 y_i。我們假設(shè)學習算法 A 試圖最小化線性模型的正則化經(jīng)驗風險

認證移除的方法如下。首先定義一個移除機制，給定要移除的訓練數(shù)據(jù)點(x, y)，生成一個近似等于 L(w;D (x, y))的唯一極小值的模型 w?。由這種機制產(chǎn)生的模型可能仍然包含關(guān)于(x, y)的信息，特別是如果梯度 ?L(w?;D (x, y))非零，它將揭示關(guān)于刪除的數(shù)據(jù)點的信息。為了隱藏這一信息，我們在訓練時對模型參數(shù)施加足夠大的隨機擾動。

去除機制。在不喪失一般性的前提下，我們假設(shè)我們的目標是移除最后一個訓練樣本(x_n, y_n)。具體地說，定義了一種有效的去除機制，該機制可以在 D’= D x_n, y_n)的情況下近似地最小化 L(w;D’)。首先，表示樣本(xn, yn)處的損失梯度 ?= λw? ?' ((w?)>x_n, y_n)和 Hw?=?2L(w?;D’)處的 Hessian。我們考慮 Newton 更新刪除機制 M:

這是應用于被移除點(x_n, y_n)的梯度影響的一步牛頓更新。更新

也被稱為訓練點(x_n, y_n)對參數(shù)向量 w? 的影響函數(shù)。

這個牛頓更新的計算成本是由形成和反 Hessian 矩陣的成本決定的。隨后的 Hessian 反轉(zhuǎn)使得移除時的移除機制為 O(d3);反演可以利用高效的線性代數(shù)庫和 gpu。

為了限制這種去除機制的近似誤差，我們觀察到:?L(w?;D’)只有當 w? 是 L(·;D’)的唯一極小值時才為零。我們還觀察到，梯度殘差范數(shù)||?L(w?;D’)||反映了 L(·;D’)最小值在 w? 近似下的誤差。我們推導了去除機制的梯度剩余范數(shù)的上界(參見方程 3)

定理 1。假設(shè) ?(x_i, y_i)∈D,w∈R^d: ||?' (w>x_i, y_i)||≤C.同時假設(shè) y’’是 γ-Lipschitz, ||x_i||≤1 對于所有(x_i, y_i)∈D，則:

損失擾動。通過定理 1 獲得小的梯度范數(shù)||?L(w?;D’)||不能保證經(jīng)過認證的去除。特別地，梯度殘差的方向可能泄露關(guān)于被“移除”的訓練樣本的信息。為了隱藏這一信息，我們在訓練時使用了的損失擾動技術(shù)。它通過一個隨機的線性項來擾亂經(jīng)驗風險:

讓 A(D’)是 Lb(·;D’)的一個精確的最小值 1，并且讓~ A(D’)是 Lb(·;D’)的一個近似的最小值。具體地說，讓~ w 是由 a 產(chǎn)生的一個近似解決方案。這意味著梯度剩余是:

定理 2。假設(shè) b 來自一個具有密度函數(shù) p(·)的分布，對于任意 b1,b2∈R^d 滿足||b1?b2||≤?’，我們有:

實現(xiàn)認證的去除。將定理 2 與定理 1 中的梯度剩余范數(shù)界 ?’結(jié)合，可以用定理 2 證明去除。安全參數(shù) ? 和 δ 取決于 b 采樣時的分布。我們保證(?，δ)認證去除以下兩個合適的分布 p(b)

定理 3。假設(shè) A 是返回損失 L_b(w;D)的唯一最優(yōu)值的學習算法，M 是牛頓更新刪除機制(參見公式 3)。假設(shè) k?L(w?;D’)k2≤? ‘，對于某個可計算界 ?’> 0。我們對 M 有以下保證:

1.如果 b 來自密度為

那么對于 A M 等于 ?-CR;

2.如果

那么 M 等于(?，δ)-CR 為 A，

3.2 實際考慮

最小二乘和邏輯回歸。上述經(jīng)過認證的移除機制可用于最小二乘和邏輯回歸，這在機器學習的現(xiàn)實應用中是普遍存在的。

邏輯回歸假設(shè) ?i: y_i∈{?1， 1}，并使用損失函數(shù)

其中 σ(·)表示 sigmoid 函數(shù)，

損失梯度和 Hessian 由:

梯度范數(shù)的數(shù)據(jù)依賴界。定理 1 中的界包含一個常數(shù)因子 1/λ^2，對于小數(shù)據(jù)集的實際應用可能太過松散。幸運的是，我們可以在梯度殘差上推導出一個數(shù)據(jù)相關(guān)的邊界，該邊界可以有效地計算，并且在實踐中更加嚴格?；叵胍幌?，L(·;D’)的 Hessian 的形式是:

由方程 4 得到

已知二階導數(shù) y’’的 Lipschitz 常數(shù) l’’，我們可以這樣約束它

多個刪除。去除 T 后的最壞情況梯度殘差范數(shù)可以在 T 中線性縮放。我們可以用 T 的歸納法來證明這一點。假設(shè)去除 T≥1 次后的梯度殘差為 uT ||uT||≤t0，其中 ?’為一次去除的梯度殘差范數(shù)界。設(shè) D^(T)為去掉 T 個數(shù)據(jù)點的訓練數(shù)據(jù)集。考慮修正的損失函數(shù) L^(T) b(w;D^(T)) = Lb(w;D^(T))?u> Tw，并設(shè) wt 為 T 去除后的近似解。那么 wT 是 L^(T) b(w;D^(T))的一個精確解，因此，上述定理可以應用于 L(T) b(w;D^(T))，證明牛頓更新近似 wT 1 有梯度殘差 u’，范數(shù)最大為 ?’。然后:

因此，去除 T 1 后 Lb(w;D(T))的梯度殘差為 u_T 1:= uT u’，其范數(shù)最多為(T 1) ?’乘以三角形不等式。

批量刪除。在某些場景中，數(shù)據(jù)刪除可能不需要在數(shù)據(jù)所有者請求刪除之后立即進行。這可能允許批量移除多個訓練樣本一次移除，以提高效率。Newton 更新刪除機制自然支持這個擴展。在不喪失一般性的前提下，假設(shè)要移除的訓練數(shù)據(jù)批次為 Dm= {(x*(n?m 1), y*(n?m 1))，…(x_n,y_n)}。定義:

批量移除更新為:

我們得到了與定理 1 和推論 1 相似的分批移除梯度殘差范數(shù)的邊界。

定理 4。在定理 1 相同的正則性條件下，我們得到:

定理 4 中的梯度剩余界是隨著移除的次數(shù)進行二次縮放的，而不是在逐個移除示例時進行線性縮放。誤差的增加是由于對 Hessian 的更粗略的近似，也就是說，在當前的解決方案中只計算一次 Hessian，而不是對每個刪除的數(shù)據(jù)計算一次。

減少在線計算。牛頓更新要求形成和反轉(zhuǎn)黑森。雖然對于較小的 d，反演的 O(d3)成本相對有限，并且可以在 gpu 上高效地進行反演，但形成 Hessian 的成本是 O(d2n)，這對于大數(shù)據(jù)集可能是有問題的。

當計算數(shù)據(jù)依賴界時，可以使用類似的技術(shù)來計算術(shù)語

它涉及(n?1)× d 數(shù)據(jù)矩陣 X 與 d 維向量的乘積。通過離線形成 X 的奇異值分解，并通過求解 d × d 矩陣上的特征分解問題，應用在線降日期來形成 X? 的奇異值分解，我們可以將該計算的在線分量減少到 O(d3)。結(jié)果表明，該方法減少了

的計算量，僅涉及 d × d 矩陣和 d 維向量，這使得在線計算成本與 n 無關(guān)。

偽代碼。我們提供了用于訓練啟用刪除的模型和用于(?，δ)-CR 牛頓更新機制。在訓練過程中(算法 1)，我們通過抽樣一個高斯噪聲向量 b，在訓練損失中加入一個隨機線性項。根據(jù)定理 3，σ 的選擇決定了“去除預算”:可以產(chǎn)生的最大梯度剩余范數(shù)為 σ?/c。在優(yōu)化訓練損耗時，任何對強凸損耗函數(shù)具有收斂保證的優(yōu)化器都可以在算法 1 中找到最小值。我們在實驗中使用了 L-BFGS，因為它是我們嘗試過的最有效的優(yōu)化器。

在移除過程中(算法 2 中的第 19 行)，我們應用批量 Newton 更新(等式 6)，并使用推論 2(算法 2 中的第 15 行)計算梯度殘差范數(shù)邊界。變量 β 在所有移除過程中累積梯度殘差范數(shù)。如果預先確定的預算 σ?/c，我們使用算法 1 在剩余的數(shù)據(jù)點上從頭開始訓練一個新的刪除啟用模型。

3.3 非線性模型

深度學習模型通常將線性模型應用于網(wǎng)絡(luò)在 ImageNet 等公共數(shù)據(jù)集上預訓練后提取的特征的視覺任務(wù)，或從公共文本語料庫的語言模型訓練用于自然語言任務(wù)。在這樣的設(shè)置中，我們只需要擔心從應用到特征提取器輸出的線性模型中刪除數(shù)據(jù)。

當特征提取器也對私有數(shù)據(jù)進行訓練時，我們可以對線性模型使用我們的認證去除機制，該模型應用于差分私有特征提取網(wǎng)絡(luò)的輸出。

定理 5。假設(shè) Φ 是一個隨機學習算法，它是(?DP， δDP)-差異私有，和 Φ 的輸出被用于線性模型通過最小化 Lb 和使用去除機制，保證(?CR,δCR)認證的去除。然后整個程序保證(?DP ?CR,δDP δCR)認證的刪除。

這種方法相對于以一種差異私有的方式訓練整個網(wǎng)絡(luò)的優(yōu)點是，線性模型可以使用更小的擾動來訓練，這可能會大大提高最終模型的準確性。

4. 實驗

4.1 線性邏輯回歸

我們首先在 MNIST 數(shù)字分類數(shù)據(jù)集上進行實驗。為簡單起見，我們限制在區(qū)分數(shù)字 3 和 8 的二進制分類問題上，并使用算法 1 訓練正則化邏輯回歸器。

λ 和 σ 的影響。培訓 removal-enabled 模型使用算法 1 需要選擇兩個 hyperparameters: L2-regularization 參數(shù) λ,和標準差 σ,取樣擾動向量 b。圖 1 顯示的影響 λ 和 σ 之前刪除測試準確性和預期數(shù)量的支持。將支撐移除數(shù)固定在 100(中間地塊)時，σ 值與 ?(參看算法 2 的第 16 行)，因此更高 ? 結(jié)果 σ 較小，精度提高。增加 λ 可以在重新訓練之前進行更多的移除，因為它減少了梯度殘差范數(shù)，但是非常高的 λ 值會對測試精度產(chǎn)生負面影響，因為正則化項占了最大的損失。

圖 1. MNIST 的線性邏輯回歸。梯度殘差范數(shù)(在對數(shù)尺度上)作為移除數(shù)量的函數(shù)

梯度剩余范數(shù)界限的嚴密性。在算法 2 中，我們使用推論 1 和推論 2 中的數(shù)據(jù)依賴界來計算去除誤差的每數(shù)據(jù)或每批估計，而不是定理 1 和定理 4 中的最壞情況界。圖 1 顯示了不同邊界的值作為刪除點數(shù)量的函數(shù)?？紤]兩種移除場景:單點移除和批量移除，批大小為 m = 10。我們觀察到三種現(xiàn)象:(1)最壞情況邊界(淺藍色和淺綠色)比數(shù)據(jù)依賴邊界(深藍和深綠色)高幾個數(shù)量級，這意味著使用數(shù)據(jù)依賴邊界時，支持的移除數(shù)要高幾個數(shù)量級。(2)梯度殘差范數(shù)邊界的累加和在單個和批量移除數(shù)據(jù)相關(guān)邊界上近似為線性。(3)依賴于數(shù)據(jù)的范數(shù)邊界與梯度殘差范數(shù)(虛線)的真值之間存在較大的差距，這表明我們的去除機制的實用性可以通過更嚴格的分析進一步提高。

梯度殘差規(guī)范與移除難度。依賴于數(shù)據(jù)的界由更新

的范數(shù)控制，該范數(shù)測量移走點對參數(shù)的影響，并且根據(jù)被移走的訓練樣本而變化很大。圖 3 顯示了

的 10 個最大和最小值對應的訓練樣本。這些樣本表明，移除異常值更難，因為模型傾向于記住它們的細節(jié)，它們對模型的影響很容易與其他樣本區(qū)分開來。

4.2 非線性 Logistic 回歸使用公共，預先訓練的特征提取器

我們考慮一種常見的場景，即特征提取器根據(jù)公共數(shù)據(jù)進行訓練，而線性分類器使用非公共數(shù)據(jù)對這些特征進行訓練。我們研究了兩個任務(wù):(1)LSUN 數(shù)據(jù)集上的場景分類和(2)斯坦福情感樹庫數(shù)據(jù)集上的情感分類。我們將 LSUN 數(shù)據(jù)集細分為每類 100K 個圖像。

對于 LSUN，我們使用 ResNeXt-101 模型提取特征，對 1B 張 Instagram 圖片進行訓練，并在 ImageNet 上進行微調(diào)。對于 SST，我們使用預訓練的 RoBERTa 語言模型提取特征。在移除時，我們使用算法 2 與 ?= 1，δ= 1e-4。

結(jié)果 LSUN。我們將 10 路 LSUN 分類任務(wù)縮減為 10 個單對全的任務(wù)，并對反例進行子采樣，以確保在所有二元分類問題中正類和負類是平衡的。由于訓練樣本并不總是需要從所有 10 個分類器中刪除，所以子采樣的好處是刪除。圖 3(左)顯示了測試準確性和 LSUN 上預期移除數(shù)量之間的關(guān)系。(λ， σ)的值顯示在每個點旁邊，最左邊的點對應于訓練一個不支持移除的規(guī)則模型。該模型在需要重新培訓之前支持超過 10,000 次移除，但代價是準確性略有下降(從 88.6%降至 83.3%)。

圖 2. MNIST 訓練數(shù)字按范數(shù)排序

圖 3. 線性模型訓練公共特征提取器

風場。SST 是一種情感分類數(shù)據(jù)集，通常用于基準語言模型。在預測電影評論是否正面的二元分類任務(wù)中，我們使用了 SST。圖 3(右)顯示了準確性和支持的刪除數(shù)量之間的權(quán)衡。常規(guī)模型(最左邊的點)獲得了 89.0%的測試精度，這與競爭性先前工作的性能相匹配。與之前一樣，在測試精度的小損失的情況下支持大量的移除;去除的計算成本比重新訓練模型的計算成本低 870 倍。

4.3 使用差分私有特征提取器的非線性 Logistic 回歸

當公共數(shù)據(jù)無法用于訓練特征提取器時，可以在私有數(shù)據(jù)上訓練差分私有特征提取器，并應用定理 5 從最終(啟用刪除)線性層中移除數(shù)據(jù)。與使用的方法訓練整個模型相比，這種方法一個主要的優(yōu)勢是最終的線性層可以部分糾正私有特征提取器產(chǎn)生的噪聲特征。

我們在街景房號數(shù)字分類數(shù)據(jù)集上對該方法進行了評估。為了公平的比較，我們固定 δ = 1e-4 和訓練(?DP/10，δ)-private 的 CNNs 的范圍內(nèi)的值 ?DP。由聯(lián)盟約束的團體隱私，結(jié)果模型支持到那時(?DP,δ)-CR 刪除。

為了度量定理 5 用于認證數(shù)據(jù)刪除的有效性，我們還培訓了一個(?DP/10,δ/10)-differentially 私有 CNN，并從其倒數(shù)第二線性中提取特征。我們在算法 1 中使用這些特征訓練 10 個單對全分類器，總失效概率最多為 9δ/10。與 LSUN 上的實驗類似，我們在每個二進制分類器中對負面示例進行子采樣，以加快刪除速度。對 ?CR≈?DP/10，從而達到(?， δ)-CR 與 ?= ?DP ?CR≈?DP ?DP/10。

圖 5 顯示了測試準確性和 ? 完全私有和 Newton 更新刪除方法。對于較小的值或 ?，訓練私有特征提取器(藍色)和使用算法 1 訓練線性層比訓練完全差分私有模型(橙色)獲得更高的測試精度。特別是在 ?≈0.1，全差異私有基線的準確率僅為 22.7%，而我們的方法獲得了 71.2%的測試精度。從 private 提取器上訓練的線性模型中移除只需要 0.27 秒，相比之下，當從零開始重新訓練 CNN 時需要超過 1.5 小時。

5. 總結(jié)

我們研究了一種從機器學習模型中快速“移除”數(shù)據(jù)的機制，直到一種不同的私有保證:移除后的模型與從一開始就沒有看到被移除數(shù)據(jù)的模型無法區(qū)分。在未來的工作中至少還有四個挑戰(zhàn)。(1) Newton 更新移除機制需要反求 Hessian 矩陣，這可能是有問題的。(2)不支持去除非凸損失模型。(3)我們的數(shù)據(jù)依賴界與真正的梯度殘差范數(shù)之間存在較大的差距。(4)有些應用可能需要開發(fā)替代的、約束較少的數(shù)據(jù)刪除概念。

致謝

本文由南京大學軟件學院 2021 級碩士馮翔翻譯轉(zhuǎn)述，尹伊寧審核。