在機器學習中有哪些典型的Online演算法？

01-02

在機器學習中有哪些典型的Online演算法？或者說，在機器學習中的常用模型中，哪些支持Online演算法，請具體介紹下

online演算法挺多的。

比如基於gradient descent的online演算法，舉例如下（不止這麼多）

1. Online gradient descent: Logarithmic Regret Algorithms for Online Convex Optimization

2. Dual averaging: Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization

2. FTRL: A Unified View of Regularized Dual Averaging

3. Adagrad: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

這方面有很多論文，還有一本挺不錯的綜述：Online Learning and Online Convex Optimization http://www.cs.huji.ac.il/~shais/papers/OLsurvey.pdf

比如基於multi-armed bandit問題的online演算法

1. Finite-time Analysis of the Multiarmed Bandit Problem

multi-armed bandit的相關paper實在太多了，這裡就列出早期經典的。也有一本對應的綜述：Regret Analysis of Stochastic and
Nonstochastic Multi-armed
Bandit Problems http://homes.di.unimi.it/~cesabian/Pubblicazioni/banditSurvey.pdf

以上兩類是追求regret bound的演算法。也有一些稱作的online的演算法只是取義於『隨時間變化而更新』，而不證明regret bound。

經典的online演算法就是SGD啦。

概率模型（生成模型）都可以做online。無論是用採樣還是變分。

基於kernel(非線性)的方法則不能online，雖然可以每來一個樣本就更新一次，但是必須把之前看所有的數據都保存下來來構建kernel matrix，這樣空間需求會越來越大。

另外，可以了解下這個，

JohnLangford/vowpal_wabbit · GitHub

http://www.jmlr.org/papers/volume7/crammer06a/crammer06a.pdf

最高引和最成功的online learning演算法是passive aggressive.有時間到實驗室再慢慢寫。

在線學習實際上就是沒來一個/批樣本增量更新一次，主要有兩類：

1、基於貝葉斯公式，這種更新方式非常自然。有名的應用包括微軟的MatchBox，以及其在廣告點擊率上的應用，具體的paper名字大概是web-scale ctr prediction

2、基於sgd的方法，基於梯度優化的演算法大都可以應用。這一類方法有很多變種，大多數是加速sgd的收斂速度，以及減少調參對收斂的影響，神經網路的訓練基本都是此類方法。另外google有一篇文章Ad Predictor，算是把ctr預估的方向指向實時更新了

其他還有一些online的方法，不過往往需要各種trick,比如近鄰法，因為這類方法是非參數模型

logistic regression, linear svm, 神經網路

我自己實現和搬運的一些在線演算法:

yejiming/ML_Algorithms · GitHub

概率，神經網路，DeepLearning都是online的

ee類的就是bayes+ucb,ts系列

增量訓練類的比較典型的就是sgd，還有共軛先驗類的bayes