在線學(xué)習(xí)算法分享

在線學(xué)習(xí)算法分享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)點精度高局限性受限于被訓(xùn)練數(shù)據(jù)的規(guī)模無法有效處理數(shù)據(jù)流，做在線訓(xùn)練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)生真正稀疏的特征權(quán)重2.那就設(shè)定一個閾值，做截斷來保證稀疏，可以結(jié)合L1范數(shù)簡單截斷方法，每online訓(xùn)練K個數(shù)據(jù)截斷一次稀疏性的考量Truncatedgradient（09年的工作）Black-boxwrapperapproaches：黑盒的方法去除一些特征，然后重新訓(xùn)練的看被消去的特征是否有效。需要在數(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)化問題的含義：每次新的結(jié)果不要太遠離之前的結(jié)果每一步還是要向正確的方向前進（梯度or子梯度方向）AOGDRDARegularizeddualaveraging（微軟10年的工作）非梯度下降的范疇，屬于更加通用的一個primal-dualalgorithmicschema的一個應(yīng)用克服了SGD類方法所欠缺的exploitingproblemstructure，especiallyforproblemswithexplicitregularization。能夠更好地在精度和稀疏性之間做trade-offFTRL(Follow-the-regularized-Leader)基本思想OGD不夠稀疏FOBOS能產(chǎn)生更加好的稀疏特征梯度下降類方法，精度比較好RDA可以在精度與稀疏性之間做更好的平衡稀疏性更加出色FTRL綜合OGD的精度和RDA的稀疏性最關(guān)鍵的不同點是累積L1懲罰項的處理方式FTRL(Follow-the-regularized-Leader)迭代公式再看一下OGDOGD迭代公式的等價優(yōu)化問題的含義：每次新的結(jié)果不要太遠離之前的結(jié)果每一步還是要向正確的方向前進（梯度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（改進與實際應(yīng)用H.BrendanMcMahan,google）10年理論性paper，但未顯式地支持正則化項迭代；論文證明regretbound以及引入通用的正則化項；揭示OGD、FOBOS、RDA等算法與FTRL關(guān)系；FTRL，可以看作RDA