南京大學周志華等提出DFOP演算法：無分佈一次通過學習

選自arXiv

機器之心編譯

作者：趙鵬、周志華

參與：吳攀、黃小天

線上機器學習應用中， 資料總是會隨時間增多， 怎麼開發能有效應對這種動態情況的演算法是一個值得關注的熱門研究主題。 近日， 南京大學研究者趙鵬和周志華在 arXiv 發佈了一篇題為《Distribution-Free One-Pass Learning》的論文， 提出了一種有望解決這一問題的演算法 DFOP。 機器之心對該論文進行了摘要介紹， 更多詳情請參閱原論文。

論文：無分佈一次通過學習（Distribution-Free One-Pass Learning）

論文位址：https://arxiv.org/abs/1706.02471

在許多大規模機器學習應用中， 資料會隨著時間而累積， 因此， 一個合適的模型應當能以一種線上的範式而進行更新。

此外， 因為在構建模型時， 總的資料量是未知的， 因此我們希望使用獨立於資料量的存儲來對每個資料項目進行僅一次的掃描。 另外值得注意的是在資料累積過程中， 其基礎分佈可能會發生改變。 為了應對這樣的任務， 在這篇論文中， 我們提出了 DFOP——無分佈一次通過學習方法（distribution-free one-pass learning approach）。 這種方法在資料累積過程中分佈發生變化時效果良好， 且無需有關該變化的先驗知識。 每個資料項目一旦被掃描後就可以被拋棄了。 此外， 理論保證（theoretical guarantee）也表明在一個輕微假設下的估計誤差（estimate error）會下降， 直到高概率地收斂。 我們通過實驗驗證了 DFOP 在回歸和分類上的表現。

3 預備工作

這一部分簡要介紹了靜態場景中的流回歸模型（streaming regression model）。

在一個流場景（streaming scenario）中，

我們用 {x(t), y(t)} 表示一個有標籤的資料集， 其中 x(t) 是第 t 個實例的特徵， y(t) 是一個實值輸出。 此外， 我們假設了一個如下的線性模型：

其中 {ε(t)} 是雜訊序列， {w(t)} 是我們要估計的。

當在一個靜態場景中時， 序列 {w(t)} 是一個常數向量， 用 w0 表示。 然後， 可以採用最小二乘法來最小化其殘差平方和， 其有一個閉式解（closed-form solution）。 但是， 當添加一個線上的/一次通過的約束（其要求原始項在被處理之後就被拋棄）時， 它就無法工作。 遞迴最小二乘法（RLS/recursive least square）和隨機梯度下降（SGD）是以線上的範式解決這一問題的兩種經典方法。

當在一個非靜態環境中時， 尤其是基礎分佈改變時， 傳統的方法是不合適的， 因為我們永遠不期望經典的 i.i.d 假設還能繼續發揮效用。 在下一節， 我們提出了基於指數遺忘機制（exponential forgetting mechanism）來處理這種場景，

而無需對資料流程的演化進行明確的建模；我們也給出了理論支持和實證論證。

在下面， ||·|| 表示在

空間中的 L2 範數。 同時， 對於有界實值序列 {x(t)}， x* 表示該序列的上界， 即

4 無分佈一次通過學習

因為序列 {w(t)} 在動態環境中會隨時間改變， 所以使用前面介紹的方法來估計當前（即時間 t 時）概念。 相反， 我們引入了一個貼現因數（discounted factors）{λ(t)} 序列來對舊資料的損失降權， 如下：

其中 λ(i) ∈ (0, 1) 是一個貼現因數， 可以平滑地給更舊的資料加上更少的權重。 如果我們將所有 λ(i) 都簡化成一個常量 λ ∈ (0, 1)， 那麼就可以更直觀地理解， 則此時該函數就為：

數量

被稱為遺忘因數（forgetting factor）[Hay08]。 遺忘因數的值實際上是過去條件的穩定性（stability of past condition）和未來演化敏感度（sensitivity of future evolution）之間的權衡。

需要指出， 這個基於指數遺忘因數的遺忘機制也可以被看作是滑動視窗方法（sliding window approach）的某種程度的連續類比。 帶有足夠小權重的舊資料或多或少可被看作是從視窗中排除的。 更多關於視窗大小和遺忘因數的關係的討論可見於第 5.4 節。

4.1 演算法

對於 (3) 中提出的優化問題， 顯然， 通過取該函數的導數， 我們可以直接得到其最優的閉式解：

但是， 上述運算式是一個離線的估計（off-line estimat）， 亦即 t 之前的所有資料項目都需要。 我們沒有重複求解 (4)， 而是基於新進入資料項目的資訊為之前的估計增加了一個校正項， 從而對其基礎概念（underlying concept）進行估計。 使用遺忘因數遞迴最小二乘法 [Hay08]， 我們可以以一次通過的範式（one-pass paradigm）求解目標 (3)。 而就我們所知， 這是第一次採用傳統的遺忘因數 RLS 來在一次通過的約束條件下解決這樣的帶有分佈改變的任務。

我們將其命名為 DFOP（Distribution-Free One-Pass 的縮寫）， 並總結為如下演算法 1：

另外， 應該指明， {λ(t)} 被選作常量無論如何都是必要的， 我們為動態貼現因數序列 {λ(t)} 提供了一個泛化的 DFOP（縮寫為 G-DFOP）， 對應於 (11) 式，其也被證明是一個一次通過（one-pass）演算法。第 1 節的詳細證明參閱補充材料。

對於分類場景，y(t) 不再是一個實值輸出，而是一個離散值，出於方便我們假設 y(t) ∈ {−1, +1}。在分類時，會在原來的輸出步驟上進行一點細微的調整，其效果在下一節中通過實驗獲得了驗證。

假設特徵是 d 維的，在演算法處理步驟中我們只需要記住：

易言之，存儲總是 O(d^2)，其與訓練實例的數量無關。此外，在第 t 時間戳記（time stamp）時，wˆ (t) 的更新也與先前的資料項目不相關，即每一個資料項目一旦被掃描，即被捨棄。

4.2. 理論保證

這一節中，我們在一個非平穩回歸場景中開發了一個估計的誤差界（error bound）。

5. 實驗

圖 1: 在合成資料集上，7 種方法在 holdout 精確度方面的表現對比。左邊是全部的 7 種方法；為了清晰，右邊只繪製了 RLS、DWM 和 DFOP。

圖 2 ：在帶有分佈變化的 4 個資料集上使用不同的遺忘因數的累積精確度

對應於 (11) 式，其也被證明是一個一次通過（one-pass）演算法。第 1 節的詳細證明參閱補充材料。

對於分類場景，y(t) 不再是一個實值輸出，而是一個離散值，出於方便我們假設 y(t) ∈ {−1, +1}。在分類時，會在原來的輸出步驟上進行一點細微的調整，其效果在下一節中通過實驗獲得了驗證。

假設特徵是 d 維的，在演算法處理步驟中我們只需要記住：

易言之，存儲總是 O(d^2)，其與訓練實例的數量無關。此外，在第 t 時間戳記（time stamp）時，wˆ (t) 的更新也與先前的資料項目不相關，即每一個資料項目一旦被掃描，即被捨棄。

4.2. 理論保證

這一節中，我們在一個非平穩回歸場景中開發了一個估計的誤差界（error bound）。

5. 實驗

圖 1: 在合成資料集上，7 種方法在 holdout 精確度方面的表現對比。左邊是全部的 7 種方法；為了清晰，右邊只繪製了 RLS、DWM 和 DFOP。

圖 2 ：在帶有分佈變化的 4 個資料集上使用不同的遺忘因數的累積精確度