在線學習算法分享

在線學習算法分享XX2016.××.××Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹傳統(tǒng)方法最小化的目標函數(shù)（無約束優(yōu)化），softregularizationformulation：另一種等價約束優(yōu)化描述，convexconstraintformulation：Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹無約束優(yōu)化表示全局梯度下降：牛頓法、LBFGS等方法不等式約束凸優(yōu)化問題投影梯度下降（約束優(yōu)化表示下），gt是subgradient批量算法批量算法傳統(tǒng)不等式約束的凸優(yōu)化方法：內(nèi)點法（轉(zhuǎn)化為規(guī)則化的無約束優(yōu)批量算法的優(yōu)缺點優(yōu)點精度高局限性受限于被訓練數(shù)據(jù)的規(guī)模無法有效處理數(shù)據(jù)流，做在線訓練Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹在線算法在線梯度下降（OGD）隨機梯度下降（SGD），在凸集上做投影混合正則化項：在線算法梯度下降方法精度比較好局限性很難產(chǎn)生真正稀疏的解，即便加入L1正則化項對于不可微點的迭代會存在一些問題（theiteratesofthesubgradientmethodareveryrarelyatthepointsofnon-differentiability）Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹稀疏性的考量簡單加入L1范數(shù)a+b兩個float數(shù)很難絕對等于零，無法產(chǎn)生真正稀疏的特征權重2.那就設定一個閾值，做截斷來保證稀疏，可以結合L1范數(shù)簡單截斷方法，每online訓練K個數(shù)據(jù)截斷一次稀疏性的考量Truncatedgradient（09年的工作）Black-boxwrapperapproaches：黑盒的方法去除一些特征，然后重新訓練的看被消去的特征是否有效。需要在數(shù)據(jù)集上對算法跑多次，不太實用Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹非光滑全局優(yōu)化算法迭代公式非光滑全局優(yōu)化算法.迭代方程第一項：梯度或累積梯度；第二項：L1正則化項；第三項：限定x不要離已迭代過的解太遠（proximal），或者離0太遠（central），也是lowregret的需求regret定義

FOBOSForward-BackwardSplittingmethod(google和伯克利09年的工作）可以看作truncatedgradient的一種特殊形式基本思想：跟projectedsubgradient方法類似，不過將每一個數(shù)據(jù)的迭代過程，分解成一個經(jīng)驗損失梯度下降迭代和一個優(yōu)化問題AOGD迭代公式再看一下OGDOGD迭代公式的等價優(yōu)化問題的含義：每次新的結果不要太遠離之前的結果每一步還是要向正確的方向前進（梯度or子梯度方向）AOGDRDARegularizeddualaveraging（微軟10年的工作）非梯度下降的范疇，屬于更加通用的一個primal-dualalgorithmicschema的一個應用克服了SGD類方法所欠缺的exploitingproblemstructure，especiallyforproblemswithexplicitregularization。能夠更好地在精度和稀疏性之間做trade-offFTRL(Follow-the-regularized-Leader)基本思想OGD不夠稀疏FOBOS能產(chǎn)生更加好的稀疏特征梯度下降類方法，精度比較好RDA可以在精度與稀疏性之間做更好的平衡稀疏性更加出色FTRL綜合OGD的精度和RDA的稀疏性最關鍵的不同點是累積L1懲罰項的處理方式FTRL(Follow-the-regularized-Leader)迭代公式再看一下OGDOGD迭代公式的等價優(yōu)化問題的含義：每次新的結果不要太遠離之前的結果每一步還是要向正確的方向前進（梯度or子梯度方向）這種迭代方式夠簡單，但不夠好，解不稀疏。

FTRL(Follow-the-regularized-Leader)Mirrordecent利用了上面的直觀特性，但是用arbitraryBregmandivergence代替二范數(shù)項，并更進一步，對歷史點的bregman項疊加起來：Composite-objectivemirrordescent（COMID）每一輪將正則化項加入到目標函數(shù)中（例如1范數(shù)）FTRL(Follow-the-regularized-Leader)FTRL-Proximal算法把OGD的迭代方式變成一個優(yōu)化問題。

第一項：梯度或累積梯度；第二項：L1正則化項；第三項：限定x不要離已迭代過的解太遠（proximal），或者離0太遠（central），也是lowregret的需求FTRL(Follow-the-regularized-Leader)FTRL（改進與實際應用H.BrendanMcMahan,google）10年理論性paper，但未顯式地支持正則化項迭代；論文證明regretbound以及引入通用的正則化項；揭示OGD、FOBOS、RDA等算法與FTRL關系；FTRL，可以看作RDA