在线最优化求解(Online Optimization)-冯扬

1/17在线最优化求解(OnlineOptimization)冯扬(@fengyoung)新浪微博-商业平台及产品部-推荐引擎2014-12-09摘要：最优化求解问题可能是我们在工作中遇到的最多的一类问题了：从已有的数据中提炼出最适合的模型参数，从而对未知的数据进行预测。当我们面对高维高数据量的场景时，常见的批量处理的方式已经显得力不从心，需要有在线处理的方法来解决此类问题。本文以模型的稀疏性作为主线，逐一介绍几个在线最优化求解算法，并进行推导，力求讲清楚算法的来龙去脉，以及不同算法之间的区别和联系，达到融会贯通。在各个算法原理介绍之后，都会给出该算法的工程实现伪代码，可以用于实际工作的参考。1动机与目的在实际工作中，无论是工程师、项目经理、产品同学都会经常讨论一类话题：“从线上对比的效果来看，某某特征或因素对xx产品的最终效果有很大的影响”。这类话题本质上说的是通过已有的数据反映出某些特定的因素对结果有很强的正（或负）相关性。而如何定量计算这种相关性？如何得到一套模型参数能够使得效果达到最优？这就是最优化计算要做的事情。举一类典型点的例子：在推荐和广告计算中，我们经常会需要对某些值进行预测，例如在一条推荐或广告在曝光之前先预测用户是否会产生点击（CTR预估），或者是否会由此产生某些转换（RPM预估）。这类问题可以表示为：针对一个输入𝑋=[𝑥1,𝑥2…𝑥𝑁]∈ℝ𝑁，通过某个函数𝑕(𝑋)计算（预测）输出𝑦∈ℝ。根据𝑦值为连续的还是离散的，预测问题被划分成回归问题（Regression）和分类问题（Classification）。而利用已有的样本数据{(𝑋𝑗,𝑦𝑗)|𝑗=1,2,…,𝑀}训练𝑕(𝑋)的过程往往转换成一个最优化求解的过程。无论是线性回归（LinearRegression）、逻辑回归（LogisticRegression）、支持向量机（SVM）、深度学习（DeepLearning）中，最优化求解都是基本的步骤。常见的梯度下降、牛顿法、拟牛顿法等属于批量处理的方法（Batch），每次更新都需要对已经训练过的样本重新训练一遍。而当我们面对高维高数据量的时候，批量处理的方式就显得笨重和不够高效，因此需要有在线处理的方法（Online）来解决相同的问题。关于在线最优化问题（OnlineOptimization）的论文比较多，逐一查找阅读费时费力，那么本文就以高维高数据量的应用场景中比较看重的稀疏性作为主线，来介绍一些在线最优化的方法。本文的预期读者大概有如下几类：1.具有很深机器学习经验和背景的高阶人员：就拿这篇文章当作一个关于在线最优化算法的回顾材料好了，如有错误和不足欢迎指正。2.具有一定机器学习经验的中级读者：可以将本文作为一个理论资料进行阅读，略过“预备知识”部分，直接进入主题，将之前对于在线最优化算法的理解串联起来，希望能对将来的工作提供帮助。3.对机器学习有认识但是实践经验较少的初级读者：从预备知识看起，逐一理解相关概念和方法，从而达到融会贯通的目的。4.仅仅对算法的工程实现感兴趣的读者：大致浏览一下预备知识中的2.3节，了解我2/17们要讨论什么，然后直奔各算法的算法逻辑（伪代码），照着实现就ok鸟。5.高富帅和白富美：只需要知道本文讨论的是一堆好用的求最优解的方法，可以用于分类预测、回归预测等一系列问题。然后吩咐攻城狮去实践就好了。还可以拿这篇文章嘲笑机器学习的屌丝：看你们都弄些啥，累死累活的，挣那么几个钢镚2预备知识2.1凸函数如果𝑓(𝑋)是定义在N维向量空间上的实值函数，对于在𝑓(𝑋)的定义域𝐶上的任意两个点𝑋1和𝑋2，以及任意[0,1]之间的值𝑡都有：𝑓𝑡𝑋1+1−𝑡𝑋2≤𝑡𝑓𝑋1+1−𝑡𝑓𝑋2∀𝑋1,𝑋2∈𝐶,0≤𝑡≤1那么称𝑓(𝑋)是凸函数（Convex）[1]。一个函数是凸函数是它存在最优解的充分必要条件。此外，如果𝑓(𝑋)满足：𝑓𝑡𝑋1+1−𝑡𝑋2𝑡𝑓𝑋1+1−𝑡𝑓𝑋2∀𝑋1,𝑋2∈𝐶,0𝑡1则𝑓(𝑋)是严格凸函数（StrictConvex）。如图1所示，(a)为严格凸函数，(b)为凸函数。图1凸函数2.2拉格朗日乘数法及KKT条件通常我们需要求解的最优化问题有如下三类：(1)无约束优化问题：。𝑋=𝑎𝑟𝑔𝑚𝑖𝑛𝑋𝑓(𝑋)含义是求解𝑋，令目标函数𝑓(𝑋)最小；(2)有等式约束的优化问题：𝑋=𝑎𝑟𝑔𝑚𝑖𝑛𝑋𝑓(𝑋)𝒔.𝒕.𝑕𝑘𝑋=0;𝑘=1,2…,𝑛含义是在n个等式约束𝑕𝑘𝑋的条件下，求解𝑋，令目标函数𝑓(𝑋)最小。(3)有不等式约束的优化问题：3/17𝑋=𝑎𝑟𝑔𝑚𝑖𝑛𝑋𝑓(𝑋)𝒔.𝒕.𝑕𝑘𝑋=0;𝑘=1,2…,𝑛𝑔𝑙𝑋≤0;𝑙=1,2…,𝑚含义是在n个等式约束𝑕𝑘𝑋以及m个不等式约束𝑔𝑙𝑋的条件下，求解𝑋，令目标函数𝑓(𝑋)最小。针对无约束最优化问题，通常做法就是对𝑓(𝑋)求导，并令𝜕𝜕𝑋𝑓𝑋=0，求解可以得到最优值。如果𝑓(𝑋)为凸函数，则可以保证结果为全局最优解。针对有等式约束的最优化问题，采用拉格朗日乘数法（LagrangeMultiplier）[2]进行求解：通过拉格朗日系数𝐴=[𝑎1,𝑎2…𝑎𝑛]𝑇∈ℝ𝑛把等式约束和目标函数组合成为一个式子，对该式子进行最优化求解：𝑋=𝑎𝑟𝑔𝑚𝑖𝑛𝑋𝑓𝑋+𝐴𝑇𝐻(𝑋)其中，𝐻𝑋=[𝑕1𝑋,𝑕2𝑋…𝑕𝑛𝑋]𝑇∈ℝ𝑛，相当于将有等式约束的最优化问题转换成了无约束最优化求解问题，解决方法依旧是对𝑓𝑋+𝐴𝑇𝐻(𝑋)的各个参数（𝑋,𝐴）求偏导，并令其等于0，联立等式求解。针对有不等式约束的最优化问题，常用的方法是KKT条件（Karush-Kuhn-TuckerConditions）[3]：同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子：𝐿𝑋,𝐴,𝐵=𝑓𝑋+𝐴𝑇𝐻(𝑋)+𝐵𝑇𝐺(𝑋)KKT条件是说最优值必须满足以下条件：𝜕𝜕𝑋𝐿𝑋,𝐴,𝐵=0𝐻(𝑋)=0𝐵𝑇𝐺(𝑋)=0其中，𝐵=[𝑏1,𝑏2…𝑏𝑚]𝑇∈ℝ𝑚，𝐺𝑋=[𝑔1𝑋,𝑔2𝑋…𝑔𝑚𝑋]𝑇∈ℝ𝑚。KKT条件是求解最优值𝑋∗的必要条件，要使其成为充分必要条件，还需要𝑓𝑋为凸函数才行。在KKT条件中，𝐵𝑇𝐺(𝑋)=0这个条件最有趣，因为𝑔𝑙𝑋≤0，如果要满足这个等式，需要𝑏𝑙=0或者𝑔𝑙𝑋=0。在我们后面的推导中会用到这个性质。2.3从Batch到Online我们面对的最优化问题都是无约束的最优化问题（有约束最优化问题可以利用拉格朗日乘数法或KKT条件转换成无约束最优化问题），因此我们通常可以将它们描述成：𝑊=𝑎𝑟𝑔𝑚𝑖𝑛𝑊ℓ𝑊,𝑍𝑍={(𝑋𝑗,𝑦𝑗)|𝑗=1,2,…𝑀}𝑦𝑗=𝑕(𝑊,𝑋𝑗)(2-3-1)这里𝑍为观测样本集合（训练集）；𝑋𝑗为第j条样本的特征向量；𝑦𝑗=𝑕(𝑊,𝑋𝑗)为预测值；𝑕(𝑊,𝑋𝑗)为特征向量到预测值的映射函数；ℓ𝑊,𝑍为最优化求解的目标函数，也称作损失函数，损失函数通常可以分解为各样本损失函数的累加，即ℓ𝑊,𝑍=ℓ𝑊,𝑍𝑗𝑀𝑗=1；𝑊为特征权重，也就是我们需要求解的参数。以线性回归和逻辑回归为例，它们的映射函数和损失函数分别为：4/17LinearRegression𝑕𝑊,𝑋𝑗=𝑊𝑇𝑋𝑗ℓ𝑊,𝑍=𝑦𝑗−𝑊𝑇𝑋𝑗2𝑀𝑗=1LogisticRegression𝑕𝑊,𝑋𝑗=11+𝑒−𝑊𝑇𝑋𝑗ℓ𝑊,𝑍=𝑙𝑜𝑔⁡(1+𝑒−𝑦𝑗𝑊𝑇𝑋𝑗)𝑀𝑗=1在2.1中我们给出了无约束最优化问题解析解的求法。而在我们实际的数值计算中，通常做法是随机给定一个初始的𝑊(0)，通过迭代，在每次迭代中计算损失函数在当前𝑊(𝑡)的下降方向，并更新𝑊，直到损失函数稳定在最小的点[4]。例如著名的梯度下降法（GD,GradientDescent）就是通过计算损失函数的在当前𝑊(𝑡)处的梯度[5]（Gradient），以梯度𝛻𝑊ℓ𝑊(𝑡),𝑍的反方向作为下降方向更新𝑊，如果损失函数是一个非平滑的凸函数（Non-smoothconvex），在不可导处用次梯度[6]（Subgradient）方向的反方向作为下降方向。算法如下[7]：Algorithm1.BatchGradientDescentRepeatuntilconvergence{𝑊𝑡+1=𝑊𝑡−𝜂(𝑡)𝛻𝑊ℓ𝑊(𝑡),𝑍}GD是一种批量处理的方式（Batch），每次更新𝑊的时候都要扫描所有的样本以计算一个全局的梯度𝛻𝑊ℓ𝑊,𝑍。考虑另一种权重更新策略[7]：Algorithm2.StochasticGradientDescentLoop{forj=1toM{𝑊𝑡+1=𝑊𝑡−𝜂(𝑡)𝛻𝑊ℓ𝑊(𝑡),𝑍𝑗}}在算法2中，每次迭代仅仅根据单个样本更新权重𝑊，这种算法称作随机梯度下降[8]（SGD,StochasticGradientDescent）。与GD相比较，GD每次扫描所有的样本以计算一个全局的梯度，SGD则每次只针对一个观测到的样本进行更新。通常情况下，SGD能够比GD“更快”地令𝑊逼近最优值。当样本数𝑀特别大的时候，SGD的优势更加明显，并且由于SGD针对观测到的“一条”样本更新𝑊，很适合进行增量计算，实现梯度下降的Online模式（OGD,OnlineGradientDescent）。2.4正则化正则化（Regularization）的意义本质上是为了避免训练得到的模型过度拟合（overfitting）训练数据。我们用图2来说明什么是过拟合，该图来自于王科的微博（@王小科科科）。图2是一个局部加权线性回归（Locallyweightedlinearregression）的训练结果，当学习度为1时，相当于进行线性回归，这时候模型与训练样本以及实际曲线拟合得都不够好，模型处于欠拟合（underfitting）状态；当学习度逐渐增加到4的过程中，模型逐渐与实际曲线吻合；随着学习度继续增加，越来越多的样本直接落到模型曲线上（模型拟合训练数据），但是模型却与实际曲线相差越来越大，出现了过拟合。5/17图2欠拟合&过拟合过拟合体现出来的现象就是特征权重𝑊的各个维度的绝对值非常大：一些大正数，一些大负数。这种模型虽然能够很好匹配样本（如图2中Degree=20的情况），但是对新样本做预测的时候会使得预测值与真实值相差很远。为了避免过拟合的情况，我们通常在损失函数的基础上加一个关于特征权重𝑊的限制，限制它的模不要太大，如果用𝜓(𝑊)表示特征权重𝑊的一种求模计算，那么(2-3-1)转换成：𝑊=𝑎𝑟𝑔𝑚𝑖𝑛𝑊ℓ𝑊,𝑍s.t.𝜓𝑊𝛿这个时候我们面对的是一个有约束的最优化问题。根据KKT条件，我们知道当选取合适的系数𝜆，那么这个有约束最优化问题等价于如下无约束最优化问题：𝑊=𝑎𝑟𝑔𝑚𝑖𝑛𝑊ℓ𝑊,𝑍+𝜆𝜓𝑊其中𝜓𝑊称作正则化因子（Regularizer），是一个关于𝑊求模的函数，我们常用正则化因子有L1和L2正则化：L1Regularization𝜓𝑊=𝑊1=𝑤𝑖𝑁𝑖=1L2Regularization𝜓𝑊=𝑊22=𝑤𝑖2=𝑊𝑇𝑊𝑁𝑖=1不管是使用L1还是L2正则化，其基本原理都是一样的，即在最小化损失函数ℓ𝑊,𝑍的同时，还要考虑𝑊的模带来的贡献，从而避免𝑊的维度上取一些绝对值很大的值。L1和L2正则化的区别主要有两个：(