引用

Ginart A, Guan M Y, Valiant G, et al. Making ai forget you: Data deletion in machine learning[J].

摘要

最近激烈的讨論集中在如何讓個人控制他們的數據何時可以使用和不能使用。在本文中，我們提出了一個框架，研究當不再允許部署從特定用戶數據派生的模型時該怎麼辦。特别是，我們提出了從訓練的機器學習模型中有效删除單個數據點的問題。對于許多标準 ML 模型，完全删除個人數據的唯一方法是在剩餘數據上重新訓練整個模型，這在計算上通常不切實際。我們研究了在 ML 中實現高效數據删除的算法原理。對于 k 均值聚類的特定設置，我們提出了兩種可證明的高效删除算法，它們在 6 個數據集的删除效率平均提高了 100× 以上，同時生成了與規範 k-means 基線具有可比統計質量的聚類。

1. 介紹

個人可以随時決定他們不希望其個人數據被特定實體用于特定目的，繼續使用直接訓練已删除數據的人工智能系統可能被視為非法。此外，所謂的模型反轉攻擊已經證明了對手從訓練的 ML 模型中提取用戶信息的能力。

删除一個樣本點後，滿足請求删除的一種樸素方法是根據剩餘 n-1 樣本重新訓練模型，然而成本可能相當高，因此，我們認為高效的數據删除是機器學習模型和 AI 系統的基本數據管理操作，就像關系數據庫或其他經典數據結構一樣。

本文的關鍵組成部分包括引入删除高效學習，我們将數據删除作為一個在線問題，從中産生了最佳删除效率的概念。我們使用 k 均值聚類問題對删除有效學習進行了案例研究。我們提出了兩種删除效率算法，它們(在某些制度下)實現了最佳删除效率。根據經驗，在六個數據集上，我們的方法相對于規範 Lloyd 算法，在攤銷運行時中平均實現了超過 100× 加速。同時，提出的删除效率算法在聚類質量的三個不同統計指标上的表現與規範算法相當。最後，我們綜合了一個算法工具箱，用于設計删除高效的學習系統。我們将我們的工作總結為三個貢獻：(1)我們在機器學習的背景下正式化了有效數據删除的問題和概念。(2)提出兩種不同的 k 均值聚類删除效率解，具有理論保證和較強的實證結果。(3)從我們的理論和實驗中，我們綜合了設計删除高效學習系統的四個一般工程原理。

2.相關工作

确定性删除更新：如簡介中所述，已知某些規範學習算法存在有效的删除操作，包括線性模型和某些類型的懶惰學習技術。

數據删除和數據隐私：在機器學習中保護數據的相關想法不會導緻有效的數據删除，而是試圖使數據私有或不可識别。支持高效删除的算法不必是私有的，私有的算法不必支持高效删除。數據删除的挑戰隻有在存在計算限制的情況下才會出現，另一方面，隐私也帶來了統計挑戰。

3.問題闡述

本節描述設置，并在機器學習算法和模型的上下文中定義數據删除和删除效率的概念，最後總結了了用于設計删除高效學習算法的高級原則。

我們用 D={x1,...，xn}表示數據集，由 n 個數據點組成的集合，每個數據點 xi∈Rd;為簡單起見，我們通常将 D 表示為 n×d 實值矩陣。設 A 表示将數據集映射到假設空間 H 中的模型的算法。算法 A 可以對任何大小的數據集進行操作。

定義 3.1.數據删除操作：我們為學習算法 A，RA(D，A(D)，i)定義了一個數據删除操作，它将數據集 D，模型 A(D)和索引 i∈{1,...,n}映射到 H 中的某個模型。如果對于所有 D 和 i，随機變量 A(D−i)和 RA(D，A(D)，i)在分布上相等，則這樣的運算是數據删除運算，A(D−i)=dRA(D，A(D)，i)。在這裡，我們專注于确切的數據删除：從模型中删除訓練點後，模型應該就像從一開始就沒有看到過這個訓練點一樣。

計算挑戰 每個學習算法 A 都支持簡單的數據删除操作，對應于在删除指定的數據點後簡單地對新數據集進行重新訓練，即在數據集 D−i 上運行算法 A。正因此，數據删除的挑戰是計算性的：1)我們能否設計一個學習算法 A，并支持數據結構，以便實現計算高效的數據删除操作？2)對于什麼算法 A，是否存在數據删除操作，該操作在數據集大小中的時間亞線性運行，或者至少在計算原始模型 A(D)所需的時間内以亞線性運行？3)對 A(D)中包含的元數據的内存占用的限制如何影響數據删除算法的效率？

數據删除作為在線問題 給定 n 個數據點的數據集、特定的訓練算法 A 及其相應的删除操作 RA，可以考慮 m≤n 不同索引的流，i1，i2,...,im∈{1,...,n}，對應于要删除的數據點序列。然後，在線任務是設計一個數據删除操作，該操作一次給定一個索引ij，并且必須在給定索引 ij 時輸出 A(D−{i1,...,ij})。目标是最大限度地減少攤銷計算時間。

在線數據删除中，會出現攤銷運行時的簡單下限。所有(順序)學習算法 A 在自然假設（A 必須至少處理一次每個數據點）的情況下，要在 Ω(n)時間内運行。此外，在最好的情況下，A 帶有常量時間删除操作(或删除預言機)。

我們将實現此下限的算法稱為删除效率。對于許多基本學習範式來說，獲得嚴格的上限和下限是一個懸而未決的問題。在本文中，我們對 k 均值聚類進行了一個案例研究，表明我們可以在不犧牲統計性能的情況下實現删除效率。

3.1 删除高效機器學習系統的一般原則

線性 使用線性計算允許進行簡單的後處理，以撤消單個數據點對一組參數的影響。一般來說，Sherman-Morrison-Woodbury 矩陣恒等式和矩陣因式分解技術可用于導出用于更新線性模型的快速而明确的公式。

懶惰 懶惰學習方法将計算延遲到推理時間，導緻瑣碎的删除。惰性學習最簡單的例子之一是 k-最近鄰，在删除時從數據集中删除一個點會直接轉換為推理時的更新模型。從某種意義上說，懶惰可以被解釋為将計算從訓練轉移到推理。作為副作用，删除可以大大簡化。

模塊化 在删除高效學習的上下文中，模塊化是計算狀态或模型參數對數據集特定劃分的依賴性的限制。在這種模塊化下，我們可以隔離需要重新計算的特定數據處理模塊，以便考慮數據集的删除。模塊化在數據的維度與數據集大小相比較小的制度中應該是最有效的，允許數據集的分區來捕獲重要的結構和特征。

量化 許多模型都具有從數據集空間到模型空間的連續性-對數據集的微小更改應導緻對模型(分布在)模型的微小更改。在統計和計算學習理論中，這個想法被稱為不穩定。我們可以通過量化從數據集到模型的映射來利用穩定性。量化在參數數量與數據集大小相比較少的制度中最為有效。

4.删除高效集群

數據删除是機器學習的普遍挑戰。由于其簡單性，本文專注于 k-means 聚類作為案例研究。我們提出了兩種算法用于删除高效 k 均值聚類。在 k 均值的上下文中，我們将輸出質心視為我們有興趣從中删除數據點的模型。我們總結了我們提出的算法和狀态理論運行時複雜性以及統計性能保證。

4.1 量化 k 均值

我們提出了 Lloyd 算法的量化變體，作為 k 均值聚類的删除有效解，稱為 Q-k 均值。通過量化每次疊代時的質心，算法的質心相對于高概率的删除是恒定的。在這種量化穩定性的概念下，可以支持有效的删除，因為大多數删除都可以解決，而無需從頭開始重新計算質心。這裡介紹該算法的精簡版本(算法 1)。

Q-k-means 也遵循疊代協議，但與 Lloyd 算法有四個關鍵區别。首先，在更新分區之前，質心在每次疊代中都會被量化。量子化将每個點映射到均勻晶格的最近頂點。為了去偏置量化，我們對晶格應用随機相移。其次，在整個計算過程中的各個步驟中，我們将優化狀态記憶到模型的元數據中，以便在删除時使用。第三，引入了一個平衡校正步驟，該步驟通過基于先前質心的動量項對當前質心進行平均來補償 γ-不平衡的聚類。顯式地，對于某些 γ∈(0，1)，如果|πκ|≤γn/k，則認為任何分區 πκ 都是 γ-不平衡的，我們可能認為 γ 是最小簇大小與平均簇大小的比率。第四，由于量化，疊代不再保證降低損失，因此，如果損失在任何疊代中增加，都會提前終止。

Q-k-means 中的删除很簡單。通過從訓練時保存的元數據，我們可以驗證删除特定數據點是否會導緻與訓練期間實際計算的量化質心不同。如果是這種情況，我們必須從頭開始重新訓練以滿足删除請求。否則，我們可以通過更新元數據以反映指定數據點的删除，但不必重新計算質心。Q-k-means 直接依賴于量化原理來實現預期的快速删除。Q-k-means 還利用線性原理來回收計算。由于質心計算在數據點中是線性的，因此很容易确定由于在删除時删除而導緻的質心更新。

删除時間複雜度 Q-k-means 通過量化質心來支持删除，因此它們可以穩定地抵抗小的擾動。

定理 4.1. 設 D 是大小為 n 的[0，1]d 上的數據集。修複 Q-k-means 的參數 T、k、ε 和 γ。Q-k-means 預期在時間 O(m2d5/2/ε)内完成 m 次删除，其概率超過在量化階段的随機性和 k-means 初始化。

理論統計性能 設L∗ 為特定問題實例的最佳損失。一般來說，實現最優解決方案是 NP-Hard。但我們可以用 k-means 近似它，從而實現 EL ≤(8logk 16)L∗。

推論 4.1.1. 設L是一個随機變量，表示 Q-k-means 在大小為 n 的特定問題實例上的損失。則 EL≤(8logk 16)L∗ ε[(8logk 16)L∗]1/2 ndε2/4。

4.2分而治之k-Means

"分而治之"k-means (DC-k-means) 在高層次上，DCk-means 的工作原理是将數據集劃分為小的子問題，将每個子問題作為獨立的 k-means 實例求解，然後遞歸地合并結果。我們在這裡提供了 DC-k-means 的僞代碼。

DC-k-means 在高度為 h 的完美 w-ary 樹上運行。原始數據集作為統一的多項式随機變量劃分到樹中的每個葉子中，其中數據點作為試驗，留下作為結果。在每片葉子上，通過 k-means 求解一定數量的質心。将葉子合并到它們的父節點中時，構造一個新的數據集，該數據集由每個葉子的所有質心組成。然後，通過另一個 k-means 實例計算父級的新質心，為簡單起見，我們在樹中的所有子問題中固定 k。利用樹層次結構來模塊化計算對數據的依賴。在删除時，我們隻需要從一個葉子到根重新計算子問題。此觀察結果使我們能夠支持快速删除操作。我們的方法與預先存在的分布式 k-means 算法是不同的(不僅因為它被修改為删除，而且還因為它在一般的根樹上運行)。

類似于在 Q-k-means 中如何作為删除效率和統計性能之間進行權衡的旋鈕，對于 DC-k-means，我們想象 w 也可以用作類似的旋鈕。統計性能對樹寬 w 的依賴性在理論上不如 Q-k-means 對的依賴性那麼容易處理，但統計性能往往會随着 w 的增加而下降。

正如我們在實驗中所展示的那樣，深度-1 DC-k-means 證明了删除時間和統計性能之間在經驗上令人信服的權衡。此算法還有其他各種潛在的擴展，例如在聚類質量沿樹上傳播時對質心進行加權，或探索更深樹的統計性能。

删除時間複雜度 為了進行後續的漸近分析，對于 ρ∈(0，1)，可以考慮将樹寬度 w 參數化為 w=Θ(nρ)，将 k 和 T 視為小常量。

命題 4.2 設 D 是大小為 n 的 Rd 上的數據集。修複 DC-k-means 的參數 T 和 k。設 w=Θ(nρ)和 ρ∈(0，1)然後，使用深度 1、w-ary 分而治之樹，DC-k-means 在預期支持在時間 O(mmax{nρ，n1−ρ}d)内完成 m 次删除，其概率超過數據集分區中的随機性。

4.3 在線删除設置中的攤銷運行時複雜性

推論4.2.1. 對于 ε=Θ(n −β ), 0<β<1，如果 α≤(1-β)/2,那麼 Q-k-means 算法是 α-删除高效的。

推論4.2.2. 對于 w = Θ(n ρ ), 0 < ρ < 1, 深度 1 的 w-ary 分而治之樹, 如果 α<1−max{1−ρ,ρ}，則 DC-k-means 在期望上是 α-删除高效的。

5 實驗

本節将通過對算法的攤銷運行時和在線删除請求模拟流的聚類質量進行基準測試，為算法提供概念驗證。規範 Lloyd 算法作為基線，将這個基線簡單地稱為 k-means，并将我們提出的兩種方法稱為 Q-k-means 和 DC-k-means。

數據集 五個真實的公開數據集：Celltype，Covtype，MNIST，Postures，Botnet，以及由高斯混合模型制成的合成數據集。所有數據集都附帶了真實值标簽用來評估聚類方法的統計質量。

在線删除基準測試 我們模拟了 1000 個删除請求的流，這些請求是随機統一選擇的，無需替換。算法在完整數據集上訓練一次，然後運行其删除操作以滿足流中的每個請求，從而在每個請求中生成一個中間模型。對于規範 k-means 基線，通過從頭開始重新訓練來滿足删除。

協議 為了衡量統計績效，我們使用三個衡量集群質量的指标進行評估。為了衡量删除效率，我們測量挂鐘時間以完成我們的在線删除基準測試。我們對每個數據集上的每個方法運行五個重複，并在所有結果中包括标準偏差。

5.1 統計性能指标

為了評估我們算法的聚類性能，最明顯的指标是 k-means 目标的優化損失。為了徹底驗證提出的算法的統計性能，我們還包括兩個規範聚類分析性能指标。輪廓系數：此系數測量一種相關性(介于-1 和 1 之間)，用于捕獲每個聚類的密度以及不同聚類的分離程度。分數越高，表示聚類密度越大，分離程度越高。歸一化互信息(NMI)：此數量測量分配的聚類與實況标簽的一緻性，分數越高，表示一緻性越好。

5.2 結果

在表 1-表 3 中展示了 3 種算法在 6 個數據集中每個數據集上的統計聚類性能。表 1 展示了所提出的方法在 k-means 基線上的優化損失率。表 2 展示了 clusters 的輪廓系數。表 3 展示了 NMI。表 4 展示了每種方法的訓練和删除的攤銷總運行時間。總體而言，我們看到三種方法的統計聚類性能良好。

此外，我們發現兩種提出的算法都産生了數量級的加速。正如理論分析所預期的那樣，當維度相對于樣本數量較低時，Q-k-means 提供更多的加速，而 DC-k-means 在維度上更一緻。

特别要注意的是，MNIST 具有我們嘗試的數據集中最高的 d/n 比率，其次是 Covtype，這兩個數據集分别是 Q-k-means 提供最小加速的數據集。另一方面，對于固定 d ，DC-k-means 在 n 增加時提供持續增加的加速提升。此外，我們看到 Q-k-means 在其删除效率方面往往具有更高的方差，因為質心穩定性的随機性比數據集分區中的随機性具有更大的影響。我們注意到，1000 次删除量不到測試的每個數據集的 10%，并且在整個基準測試中統計性能幾乎保持不變。圖 1 将在線删除基準上的攤銷運行時繪制為流中删除次數的函數。

6 讨論

目前，删除高效監督方法的主要選擇是線性模型、支持向量機和非參數回歸。雖然在這裡的分析側重于聚類的具體問題，但提出的四個設計原則，将作為删除高效學習算法的支柱。這些方法在其他監督學習技術中的具有潛在應用。

分段回歸 分段(或分段)線性回歸是規範回歸模型的常見松弛。通過将 Q-k-means 與線性最小二乘回歸相結合，應該可以支持分段回歸的變體。

核回歸 随機傅裡葉特征風格的核回歸可以很容易地修改，以支持大規模監督學習的高效删除。随機要素不依賴于數據，因此隻有要素空間上的線性圖層需要更新以進行删除。

決策樹和随機森林 量化也是決策樹的一種有前途的方法。通過量化或随機化決策樹拆分标準，似乎可以支持有效的删除。此外，随機森林與裝袋具有天然的親和力，這自然可以用來強加模塊化。

深度神經網絡和随機梯度下降 一系列研究已經觀察到神經網絡訓練對量化和修剪的魯棒性。可以利用這些技術在 SGD 樣式優化期間量化梯度更新，從而實現與 Q-k-means 中相關的參數穩定性概念。這将需要更大的批量大小和更少的梯度步驟才能很好地擴展。近似删除方法也有可能克服大型神經模型精确删除方法的缺點。

7 結論

在這項工作中，我們提出了大規模學習系統的删除效率概念，提出了可證明的删除效率無監督聚類算法，并确定了可能使其他學習算法和範式的删除效率成為可能的潛在算法原理。我們隻是觸及了理解學習系統中删除效率的表面。在整個過程中，我們做了一些簡化的假設，使得我們的系統中隻有一個模型和一個數據庫。我們還假設基于用戶的删除請求僅對應于單個數據點。了解具有許多模型和許多數據庫的系統以及複雜的用戶到數據關系中的删除效率是未來工作的重要方向。

緻謝

本文由南京大學軟件學院 2021 級碩士于亞東翻譯轉述，劉子夕審核。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!