小螞蟻說：
摘要
由於在線學習(online learning)的高效性和可擴展性使其成為解決超大規模數據的實時學習問題的熱門選擇。
現階段大多數在線學習方法都是基於全局模型的方法，即使用一個全局模型來處理所有數據，而且大多都假設流入的數據都是線性可分的。然而這種假設在實踐中並非總是如此，因此基於局部在線學習框架被提出來解決非線性可分的問題。並且這種方法無需引入kernel, 從而降低了模型的複雜度。之前一些局部在線學習框架中的模型的參數大多數僅僅利用了特徵的一階信息，因此將嚴重限制分類器的性能。為了提高提高分類器的性能，許多二階信息的模型被提出，比如典型的二階在線學習算法SCW(Soft Confidence Weighted)。
受到以上信息的啟發，我們提出了一個基於SCW算法的局部(Local)在線學習(Onlinelearning)算法（SCW-LOL)。該算法將單個SCW分類器擴展到多個SCW分類器，組成一個多分類器模型。我們還研究了各個分類器之間的更新和預測關係以及算法的理論預測誤差上界。廣泛的實驗結果表明，我們提出所提出的SCW-LOL算法是收斂的，並且相對目前主流的在線學習方法，幾乎在所有數據集都能達到最佳效果。
引言
近年來，在線學習算法在數據挖掘和機器學習中扮演越來越重要的角色。與通過學習整個訓練數據產生最佳預測的傳統機器學習技術相反，在線學習模型通過流式數據，每次只處理一個實例，根據預測結果實時更新當前模型，一直重複循環。由於在線學習不需要跟蹤任何歷史示例，因此避免了昂貴的訓練成本並減少了大量的內存消耗。同時在線學習能實時將最新的數據反饋至模型中，減少了模型的延時性。這些優勢使其在工業界有較多應用，例如搜索排序、協作過濾和異常檢測等。
很早就有一些在線學習算法被提出和應用，如Perceptron Algorithm和Passive Aggressive（PA）算法。由於一階在線學習算法僅僅使用一階信息，往往稱這些算法為一階在線學習算法。後來又出現了大量的二階在線學習算法來進一步提高分類器的性能。最具代表性有Confidence Weight（CW），Adaptive Regularization of Weights(AROW)和Soft Confidence Weight（SCW-I，SCW-II）算法等。二階在線學習使用了二階信息，其效果往往要優於一階在線學習模型效果。一階和二階在線學習算法都假設傳入的實例幾乎是線性可分的，然而在實踐中有些實例是線性不可分的，甚至是非線性的。
為了解決在線學習中的非線性可分問題，一些基於核的在線學習算法被廣泛應用，但是這些基於核在線學習方法需要消耗更多的計算和內存資源。同時另一方面，為了解決線性不可分的任務，一些局部分類器已經在離線學習中提出。比如：局部線性支持向量機和局部深度核學習。這些局部分類器避免了內核建模，並且比內核方法快得多，但它們並不合適應用於在線學習任務中。為了解決在線學習的非線性數據的問題，一種基於多個局部分類器的聯合在線學習框架被提出，並顯示了良好的效果。為了提高模型的效果，我們進一步擴展地提出了基於SCW算法的局部在線學習算法(SCW-LOL)。稍後我們將詳細描述該算法的細節以及實驗結果。
問題分析
在線學習過程可表示為：時刻t時，模型遇到實時樣本
當前模型將對樣本給出一個預測值
之後，模型將收到一個樣本標籤
這樣模型就能計算出上次預測的損失值
並通過loss值去更新模型參數。在線學習的目標是模型的所有歷史上誤差的累加和最小。
方法介紹
在這裡我們將詳細介紹我們的方法細節。SCW-LOL算法主要包括兩部分：主分類器模型，其參數為均值
和協方差矩陣
；各個子分類器模型，每個子分類器參數為均值
和協方差矩陣
我們將SCW算法中優化函數擴展為多個分類器的優化函數，如下：
在實際中，每個樣本都對應一個主分類器和一個特定的子分類器，公式（6）表示當前樣本
對應於第j個子分類器，其中
為超參數，表示主分類器的權重。這樣我們將樣本可以定義如下形式：
與其他傳統的在線學習不同，在樣本與子分類器的選擇上，我們採用一種onlineKMeans算法，將樣本分配到離樣本距離最近的子分類器。每個子分類器維護自己的一個質心
，通過質心來計算與樣本的距離。同時，當樣本分配到該子分類器時，更新質心如下公式：
其中
表示t時刻分配到i個子分類器的總樣本數。
同理，主分類器和子分類器模型的參數可表示如下形式：
那麼公式（5）可以寫成如下公式：
公式（9）和SCW算法的目標函數類似，模型參數的更新公式如下：
其中相關係數的計算如下：
其中SCW-LOL算法訓練和更新的流程如下圖：
實驗結果
我們採用兩個主要指標來衡量在線學習的性能，一個是累積錯誤率
, 該指標反映了模型從開始到現在的整體準確率。另一個指標是測試錯誤率，這個指標表示模型訓練結束後，在未知的測試集上的錯誤率，該指標反映了模型的泛化能力。
我們在10個不同數據集（5個2分類數據集，5個多分類數據集）上測試了我們的SCW-LOL算法，並同時與其他主要的在線學習算法比較，其結果如下：
從實驗結果來看，SCW-LOL算法在大部分數據集上都取得了最好的性能。尤其在多分類預測中，在所有算法中的錯誤率最小。
總結
為解決在線學習中非線性數據的問題，我們提出了一種基於SCW算法的局部在線學習（SCW-LOL）算法。該算法從流數據中學習並更新全局模型和局部模型。傳入的樣本將被分配到相應的局部模型，通過多個局部線性模型來逼近非線性模型，從而解決數據非線性可分問題。此外，我們的方法模型參數維護了二階信息，比一階在線學習方法的準確度更高。通過損失界限的理論分析，SCW-LOL算法的損失界限不會高於SCW算法的損失界限，也就意味著該在線學習算法是收斂的。實驗結果顯示，SCW-LOL算法在流式數據預測中性能十分突出，尤其在多類分類預測任務上。
閱讀更多 螞蟻金服科技 的文章
