南京大學周志華等提出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 個數據集上使用不同的遺忘因子的累積精確度

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！