《在线最优化求解onlineoptimization冯扬资料》由会员分享，可在线阅读，更多相关《在线最优化求解onlineoptimization冯扬资料（17页珍藏版）》请在金锄头文库上搜索。
1、 1 / 17 在线最优化求解在线最优化求解 (Online Optimization) 冯扬 (fengyoung) 新浪微博-商业平台及产品部-推荐引擎 2014-12-09 摘要：摘要： 最优化求解问题可能是我们在工作中遇到的最多的一类问题了： 从已有的数据中提炼 出最适合的模型参数，从而对未知的数据进行预测。当我们面对高维高数据量的场景时，常 见的批量处理的方式已经显得力不从心， 需要有在线处理的方法来解决此类问题。 本文以模 型的稀疏性作为主线，逐一介绍几个在线最优化求解算法，并进行推导，力求讲清楚算法的 来龙去脉，以及不同算法之间的区别和联系，达到融会贯通。在各个算法原理介绍之后，
2、都 会给出该算法的工程实现伪代码，可以用于实际工作的参考。 1 动机与目的动机与目的 在实际工作中，无论是工程师、项目经理、产品同学都会经常讨论一类话题： “从线上 对比的效果来看，某某特征或因素对 xx 产品的最终效果有很大的影响” 。这类话题本质上说 的是通过已有的数据反映出某些特定的因素对结果有很强的正（或负）相关性。而如何定量 计算这种相关性？如何得到一套模型参数能够使得效果达到最优？这就是最优化计算要做 的事情。 举一类典型点的例子：在推荐和广告计算中，我们经常会需要对某些值进行预测，例如 在一条推荐或广告在曝光之前先预测用户是否会产生点击（CTR 预估） ，或者是否会由此产 生某些
3、转换（RPM 预估） 。这类问题可以表示为：针对一个输入 = 1,2 ，通 过某个函数()计算（预测）输出 。根据值为连续的还是离散的，预测问题被划分 成回归问题（Regression）和分类问题（Classification） 。而利用已有的样本数据(,)| = 1,2,训练()的过程往往转换成一个最优化求解的过程。 无论是线性回归 （Linear Regression） 、 逻辑回归 （Logistic Regression） 、 支持向量机 （SVM） 、 深度学习（Deep Learning）中，最优化求解都是基本的步骤。常见的梯度下降、牛顿法、拟 牛顿法等属于批量处理的方法 （Bat
4、ch） ， 每次更新都需要对已经训练过的样本重新训练一遍。 而当我们面对高维高数据量的时候， 批量处理的方式就显得笨重和不够高效， 因此需要有在 线处理的方法（Online）来解决相同的问题。关于在线最优化问题（Online Optimization）的 论文比较多， 逐一查找阅读费时费力， 那么本文就以高维高数据量的应用场景中比较看重的 稀疏性作为主线，来介绍一些在线最优化的方法。 本文的预期读者大概有如下几类： 1. 具有很深机器学习经验具有很深机器学习经验和背景的高阶和背景的高阶人员：人员： 就拿这篇文章当作一个关于在线最优化 算法的回顾材料好了，如有错误和不足欢迎指正。 2. 具有一定
5、机器学习经验的中级读者：具有一定机器学习经验的中级读者：可以将本文作为一个理论资料进行阅读，略过 “预备知识”部分，直接进入主题，将之前对于在线最优化算法的理解串联起来， 希望能对将来的工作提供帮助。 3. 对机器学习有认识但是实践经验较少的初级读者：对机器学习有认识但是实践经验较少的初级读者：从预备知识看起，逐一理解相关 概念和方法，从而达到融会贯通的目的。 4. 仅仅对算法的工程实现感兴趣的读者：仅仅对算法的工程实现感兴趣的读者：大致浏览一下预备知识中的 2.3 节，了解我 2 / 17 们要讨论什么，然后直奔各算法的算法逻辑（伪代码） ，照着实现就 ok 鸟。 5. 高富帅高富帅和和白富
6、美：白富美：只需要知道本文讨论的是一堆好用的求最优解的方法，可以用于 分类预测、回归预测等一系列问题。然后吩咐攻城狮去实践就好了。还可以拿这篇 文章嘲笑机器学习的屌丝：看你们都弄些啥，累死累活的，挣那么几个钢镚 2 预备知识预备知识 2.1 凸函数凸函数 如果()是定义在 N 维向量空间上的实值函数， 对于在()的定义域上的任意两个点 1和2，以及任意0,1之间的值都有： 1+ 1 2 1 + 1 2 1,2 , 0 1 那么称()是凸函数（Convex）1。一个函数是凸函数是它存在最优解的充分必要条件。 此外，如果()满足： 1+ 1 2 0，所以 0 = 0 ： 这时候有： + = 0 又
7、由于 0，所以 0 所以，在 0时，= max (0, ) (2) 当当 0； () = 1 =1 ；公式(3-3-3)就是一个无约束的非平滑最优化问题。 其中第 2 项 在= 0处不可导。假设是其最优解，并且定义 为 在的 次导数，那么有： = 1 () + 0， 不满足 (3-3-5) 如果 0，由(3-3-4)得 = 1，则 () + () 0，不满足 (3-3-5) 所以，当 () 时：时： 采用相同分析方法得到 0，有 = 1满足条件，即：= () (3) 当当 () 0，有 = 1满足条件，即：= () + 次梯度最优化条件 13 / 17 Algorithm 5. Regular
8、ized Dual Averaging with L1 Regularization 1 input , 2 initialize , = 0 3 for t = 1,2,3 do 4 = 1 + 1 ,(),() 5 refresh according to +1 = 0if ( ) 6 end 7 return W 3.3.3 L1-RDA 与与 L1-FOBOS 的比较的比较 在 3.2.3 中我们看到了 L1-FOBOS 实际上是 TG 的一种特殊形式，在 L1-FOBOS 中，进行 “截断”的判定条件是 () () () = (+ 1 2)。通常会定义为与 1 正相关的函数 （ =
9、1 ） ，因此 L1-FOBOS 的“截断阈值”为 1 ，随着的增加，这个阈值会逐渐 降低。 相比较而言， 从(3-3-6)可以看出， L1-RDA 的 “截断阈值” 为， 是一个常数， 并不随着而变 化， 因此可以认为L1-RDA比L1-FOBOS在截断判定上更加aggressive， 这种性质使得L1-RDA 更容易产生稀疏性；此外，RDA 中判定对象是梯度的累加平均值 ()，不同于 TG 或 L1-FOBOS 中针对单次梯度计算的结果进行判定， 避免了由于某些维度由于训练不足导致截 断的问题。并且通过调节一个参数，很容易在精度和稀疏性上进行权衡。 3.4 FTRL 在 3.3.3 中我们
10、从原理上定性比较了 L1-FOBOS 和 L1-RDA 在稀疏性上的表现。有实验证 明，L1-FOBOS 这一类基于梯度下降的方法有比较高的精度，但是 L1-RDA 却能在损失一定精 度的情况下产生更好的稀疏性。那么这两者的优点能不能在一个算法上体现出来？这就是 FTRL 要解决的问题。 FTRL（Follow the Regularized Leader）是由 Google 的 H. Brendan McMahan 在 2010 年提 出的14，后来在 2011 年发表了一篇关于 FTRL 和 AOGD、FOBOS、RDA 比较的论文15，2013 年又和 Gary Holt, D. Scu
11、lley, Michael Young 等人发表了一篇关于 FTRL 工程化实现的论文16。 本节我们首先从形式上将 L1-FOBOS 和 L1-RDA 进行统一， 然后介绍从这种统一形式产生 FTRL 算法，以及介绍 FTRL 算法工程化实现的算法逻辑。 3.4.1 L1-FOBOS 和和 L1-RDA 在形式上的统一在形式上的统一 L1-FOBOS 在形式上，每次迭代都可以表示为（这里我们令 + 1 2 = = ( 1 )是一个 随 t 变化的非增正序列） ： (+ 1 2)= () () 14 / 17 (+1)= 1 2 (+ 1 2) 2 2 + () 1 把这两个公式合并到一起，有
12、： (+1)= 1 2 ()+ () 2 2 + () 1 通过这个公式很难直接求出(+1)的解析解，但是我们可以按维度将其分解为 N 个独立的 最优化步骤： 1 2 + () 2 + () = 1 2 2 + 1 2 () 2 + () + () + () = + + 1 2() 2 + () 2 2 + 由于 () 2 2 + 与变量 无关，因此上式可以等价于： + + 1 2() 2 再将这 N 个独立最优化子步骤合并，那么 L1-FOBOS 可以写作： (+1)= () + 1+ 1 2() () 2 2 而对于 L1-RDA 的公式(3-3-2)，我们可以写作： +1 = 1:t + 1+ 1 2() 0 2 2 这里 1: = () =1 ；如果令()= 1 () 1 (1)， (1:) = 1 ()，上面两个式子可以写作： (+1)= () + 1+ 1 2 (1:) () 2 2 (3-4-1) +1 =
