在线学习算法分享.

在线学习算法分享XX2016.××.××Outline•传统方法•批量（Batch）算法•在线算法•稀疏性的考量•非光滑凸优化算法：FOBOS、AOGD、RDA、FTRL介绍传统方法•最小化的目标函数（无约束优化），softregularizationformulation：•另一种等价约束优化描述，convexconstraintformulation：Outline•传统方法•批量（Batch）算法•在线算法•稀疏性的考量•非光滑凸优化算法：FOBOS、AOGD、RDA、FTRL介绍•无约束优化表示•全局梯度下降：•牛顿法、LBFGS等方法•不等式约束凸优化问题•投影梯度下降（约束优化表示下），gt是subgradient批量算法批量算法•传统不等式约束的凸优化方法：内点法（转化为规则化的无约束优•批量算法的优缺点优点•精度高局限性•受限于被训练数据的规模•无法有效处理数据流，做在线训练Outline•传统方法•批量（Batch）算法•在线算法•稀疏性的考量•非光滑凸优化算法：FOBOS、AOGD、RDA、FTRL介绍在线算法•在线梯度下降（OGD）•随机梯度下降（SGD），在凸集上做投影混合正则化项：在线算法•梯度下降方法•精度比较好•局限性•很难产生真正稀疏的解，即便加入L1正则化项•对于不可微点的迭代会存在一些问题（theiteratesofthesubgradientmethodareveryrarelyatthepointsofnon-differentiability）Outline•传统方法•批量（Batch）算法•在线算法•稀疏性的考量•非光滑凸优化算法：FOBOS、AOGD、RDA、FTRL介绍稀疏性的考量1.简单加入L1范数•a+b两个float数很难绝对等于零，无法产生真正稀疏的特征权重2.那就设定一个阈值，做截断来保证稀疏，可以结合L1范数•简单截断方法，每online训练K个数据截断一次稀疏性的考量•Truncatedgradient（09年的工作）3.Black-boxwrapperapproaches：•黑盒的方法去除一些特征，然后重新训练的看被消去的特征是否有效。•需要在数据集上对算法跑多次，不太实用Outline•传统方法•批量（Batch）算法•在线算法•稀疏性的考量•非光滑凸优化算法：FOBOS、AOGD、RDA、FTRL介绍非光滑全局优化算法•迭代公式非光滑全局优化算法•.•迭代方程•第一项：梯度或累积梯度；•第二项：L1正则化项；•第三项：限定x不要离已迭代过的解太远（proximal），或者离0太远（central），也是lowregret的需求•regret定义𝑄𝑡是对角矩阵，𝑄1:𝑡=𝑑𝑖𝑎𝑔(𝜎𝑡,1, 𝜎𝑡,2,⋯ 𝜎𝑡,𝑛),𝜎𝑡,𝑖=1𝛾𝑔𝑠,𝑖𝑡𝑠=1FOBOSForward-BackwardSplittingmethod(google和伯克利09年的工作）•可以看作truncatedgradient的一种特殊形式•基本思想：跟projectedsubgradient方法类似，不过将每一个数据的迭代过程，分解成一个经验损失梯度下降迭代和一个优化问题AOGD•迭代公式•再看一下OGD•OGD迭代公式的等价优化问题的含义：•每次新的结果不要太远离之前的结果•每一步还是要向正确的方向前进（梯度or子梯度方向）AOGDRDA•Regularizeddualaveraging（微软10年的工作）•非梯度下降的范畴，属于更加通用的一个primal-dualalgorithmicschema的一个应用•克服了SGD类方法所欠缺的exploitingproblemstructure，especiallyforproblemswithexplicitregularization。•能够更好地在精度和稀疏性之间做trade-offFTRL(Follow-the-regularized-Leader)•基本思想OGD不够稀疏FOBOS能产生更加好的稀疏特征梯度下降类方法，精度比较好RDA可以在精度与稀疏性之间做更好的平衡稀疏性更加出色FTRL综合OGD的精度和RDA的稀疏性最关键的不同点是累积L1惩罚项的处理方式FTRL(Follow-the-regularized-Leader)•迭代公式•再看一下OGD•OGD迭代公式的等价优化问题的含义：•每次新的结果不要太远离之前的结果•每一步还是要向正确的方向前进（梯度or子梯度方向）•这种迭代方式够简单，但不够好，解不稀疏。FTRL(Follow-the-regularized-Leader)•Mirrordecent•利用了上面的直观特性，但是用arbitraryBregmandivergence代替二范数项，并更进一步，对历史点的bregman项叠加起来：•Composite-objectivemirrordescent（COMID）•每一轮将正则化项加入到目标函数中（例如1范数）FTRL(Follow-the-regularized-Leader)•FTRL-Proximal算法把OGD的迭代方式变成一个优化问题。第一项：梯度或累积梯度；第二项：L1正则化项；第三项：限定x不要离已迭代过的解太远（proximal），或者离0太远（central），也是lowregret的需求FTRL(Follow-the-regularized-Leader)•FTRL（改进与实际应用H.BrendanMcMahan,google）•10年理论性paper，但未显式地支持正则化项迭代；论文证明regretbound以及引入通用的正则化项；揭示OGD、FOBOS、RDA等算法与FTRL关系；•FTRL，可以看作RDA和FOBOS的混合，但在L1范数或者其他非光滑的正则项下，FTRL比前两者更加有效FTRL(Follow-the-regularized-Leader)FTRL(Follow-the-regularized-Leader)数值算例ThanksQ&A