如何素描學習演算法：data deletion、stability 與算術電路局部逼近
- 17小时前
- 讀畢需時 3 分鐘
訓練數據如何影響模型行為，係 interpretability、privacy 同基礎科學嘅核心問題；其技術核心之一係 data deletion（文中亦與 datamodeling、influence functions、machine unlearning 等課題相連）：在合理預計算之後，能否快速預測。若某子集訓練樣本從未參與學習，模型喺指定「量度（measurement）」下會變成點？
Gunn（2026）喺 arXiv:2604.07328v1 提出一套可證明嘅 data deletion scheme：喺深度學習設定下，預測誤差可壓至任意小 ε；precomputation 同 prediction 分別僅比常規訓練與推論慢 poly(1/ε) 倍級，儲存則相當於 poly(1/ε) 個模型嘅空間。技術上，工作建基於以隨機複方向之高階導數對算術電路（arithmetic circuit）作局部 sketch，並利用 forward-mode automatic differentiation 高效計算。
一、Data deletion 係乜嘢？
方案包含兩個演算法：
Precomputation：輸入學習演算法描述同訓練集，輸出已訓練模型連同輔助資訊。
Prediction：輸入量度函數 ϕ（將參數映到某實數結果，例如固定查詢上嘅輸出概率）同欲刪除嘅小子集 D，利用輔助資訊近似 ϕ(A(T\\D))——即「若 D 從未用於訓練」時該量度之值。
文中以藝術家作品被納入訓練、事後想判斷某生成內容與其作品之關係是否具因果性為例：若訓練流程支援上述預計算，即可快速查詢「剔除該批作品後，模型產生 x 嘅概率」。
二、點解過往方案難做到任意小誤差？
既有可證保證多依賴代理模型（surrogate）或啟發式，與真實重訓練結果相關性有限。常見如可加性（additivity）假設：將數據權重對預測嘅影響視為線性疊加（datamodeling、influence functions 路線）。現實模型並非可加；為控制誤差有時須改動訓練演算法本身，且對大量或結構相關嘅刪除，誤差與可擴展性仍受限——亦無法單靠加計算任意壓低誤差界。
三、Stability 假設（直觀）
將學習過程抽象為由權重向量 w（例如各樣本之 downweight）映到參數再經 ϕ 量度，合成 f = ϕ ∘ A。若 f 喺 w = 0 附近之 Taylor 展開中，r 階導數項之規模隨 r 快速衰減（文中以 Frobenius 范數形式表述），則稱 f 具 stability。直觀上，量度結果對訓練數據微擾唔可過敏；越穩定，越可用有限階導數資訊可靠地外推至「刪除子集」對應之權重模式。
作者指出此假設唔等同代理模型，並聲稱與學習強模型相容；於 microgpt 上作最小實驗以檢視式（1）類條件（詳見論文 §5.2）。
四、技術路線（節略）
將訓練與量度表述為算術電路（Baur–Strassen 意味合成電路仍屬算術電路類）。
Local sketching：在隨機複方向上計算多階導數以逼近局部行為；預測端需將導數經 ϕ「推過去」，涉及 Faà di Bruno 式組合與 fast subset convolution 等，以避免先近似 A 再喂 ϕ 所引致之不穩定誤差放大。
為控制失敗概率，實際演算法採 median-of-means 等穩健聚合（引言已說明與直覺版方案之差異）。
五、含意與限制
正面係：喺 stability 成立前提下，首次喺深度學習語境同時做到（作者宣稱）預計算階段毋須先知所有未來量度 ϕ，並對反事實預測給出可證誤差界。讀者仍須注意：data deletion 本身唔等同完整 unlearning 方案；不當應用甚至可能損害隱私（文中引用相關警示文獻）。
六、小結
arXiv:2604.07328v1 以「sketch 算術電路 + stability」重新框定訓練數據對模型輸出嘅反事實查詢，並給出與 ε 相關之複雜度與誤差敘述；對關注可證數據歸因同刪除權實作邊界嘅讀者，係近年少見嘅理論—系統交匯之作。
Reference
S. Gunn. How to sketch a learning algorithm. arXiv:2604.07328v1 [cs.LG], 8 Apr 2026. https://arxiv.org/abs/2604.07328
A. Karpathy. microgpt（文中實驗相關代碼倉庫，見論文所述 microgpt-sketch 連結）。
關於 datamodeling／predictive data attribution 之導論與近期工作——見原文 §1.2 引用（如 IGEP24、IE25 等）。
W. Baur & V. Strassen. The complexity of partial derivatives. Theoretical Computer Science（Baur–Strassen 經典結果背景）。
