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

在線學(xué)習(xí)算法分享XX2016.××.××Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹傳統(tǒng)方法最小化的目標(biāo)函數(shù)（無約束優(yōu)化），softregularizationformulation：另一種等價(jià)約束優(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)點(diǎn)法（轉(zhuǎn)化為規(guī)則化的無約束優(yōu)批量算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)精度高局限性受限于被訓(xùn)練數(shù)據(jù)的規(guī)模無法有效處理數(shù)據(jù)流，做在線訓(xùn)練Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹在線算法在線梯度下降（OGD）隨機(jī)梯度下降（SGD），在凸集上做投影混合正則化項(xiàng)：在線算法梯度下降方法精度比較好局限性很難產(chǎn)生真正稀疏的解，即便加入L1正則化項(xiàng)對于不可微點(diǎn)的迭代會(huì)存在一些問題（theiteratesofthesubgradientmethodareveryrarelyatthepointsofnon-differentiability）Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹稀疏性的考量簡單加入L1范數(shù)a+b兩個(gè)float數(shù)很難絕對等于零，無法產(chǎn)生真正稀疏的特征權(quán)重2.那就設(shè)定一個(gè)閾值，做截?cái)鄟肀ＷC稀疏，可以結(jié)合L1范數(shù)簡單截?cái)喾椒?，每online訓(xùn)練K個(gè)數(shù)據(jù)截?cái)嘁淮蜗∈栊缘目剂縏runcatedgradient（09年的工作）Black-boxwrapperapproaches：黑盒的方法去除一些特征，然后重新訓(xùn)練的看被消去的特征是否有效。需要在數(shù)據(jù)集上對算法跑多次，不太實(shí)用Outline傳統(tǒng)方法批量（Batch）算法在線算法稀疏性的考量非光滑凸優(yōu)化算法：FOBOS、AOGD、RDA、FTRL介紹非光滑全局優(yōu)化算法迭代公式非光滑全局優(yōu)化算法.迭代方程第一項(xiàng)：梯度或累積梯度；第二項(xiàng)：L1正則化項(xiàng)；第三項(xiàng)：限定x不要離已迭代過的解太遠(yuǎn)（proximal），或者離0太遠(yuǎn)（central），也是lowregret的需求regret定義

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

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

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