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

《在线最优化求解(Online Optimization)-冯扬.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在线最优化求解(OnlineOptimization)冯扬(@fengyoung)新浪微博-商业平台及产品部-推荐引擎2014-12-09摘要：最优化求解问题可能是我们在工作中遇到的最多的一类问题了：从已有的数据中提炼出最适合的模型参数，从而对未知的数据进行预测。当我们面对高维高数据量的场景时，常见的批量处理的方式已经显得力不从心，需要有在线处理的方法来解决此类问题。本文以模型的稀疏性作为主线，逐一介绍几个在线最优化求解算法，并进行推导，力求讲清楚算法的来龙去脉，以及不同算法之间的区别和联系，达到融会贯通。在各个算法原理介绍之后，都会给出该算法的工程实现伪代码，可

2、以用于实际工作的参考。1动机与目的在实际工作中，无论是工程师、项目经理、产品同学都会经常讨论一类话题：“从线上对比的效果来看，某某特征或因素对xx产品的最终效果有很大的影响”。这类话题本质上说的是通过已有的数据反映出某些特定的因素对结果有很强的正（或负）相关性。而如何定量计算这种相关性？如何得到一套模型参数能够使得效果达到最优？这就是最优化计算要做的事情。举一类典型点的例子：在推荐和广告计算中，我们经常会需要对某些值进行预测，例如在一条推荐或广告在曝光之前先预测用户是否会产生点击（CTR预估），或者是否会由此产生某些转换（RPM预估）。这类问题可以表示为：针对一个

3、输入?=[?,?…?]∈ℝ?，通12?过某个函数?(?)计算（预测）输出?∈ℝ。根据?值为连续的还是离散的，预测问题被划分成回归问题（Regression）和分类问题（Classification）。而利用已有的样本数据{(??,??)

4、?=1,2,…,?}训练?(?)的过程往往转换成一个最优化求解的过程。无论是线性回归（LinearRegression）、逻辑回归（LogisticRegression）、支持向量机（SVM）、深度学习（DeepLearning）中，最优化求解都是基本的步骤。常见的梯度下降、牛顿法、拟牛顿法等属于批量处理的方法（Batch），每次

5、更新都需要对已经训练过的样本重新训练一遍。而当我们面对高维高数据量的时候，批量处理的方式就显得笨重和不够高效，因此需要有在线处理的方法（Online）来解决相同的问题。关于在线最优化问题（OnlineOptimization）的论文比较多，逐一查找阅读费时费力，那么本文就以高维高数据量的应用场景中比较看重的稀疏性作为主线，来介绍一些在线最优化的方法。本文的预期读者大概有如下几类：1.具有很深机器学习经验和背景的高阶人员：就拿这篇文章当作一个关于在线最优化算法的回顾材料好了，如有错误和不足欢迎指正。2.具有一定机器学习经验的中级读者：可以将本文作为一个理论资料进行阅

6、读，略过“预备知识”部分，直接进入主题，将之前对于在线最优化算法的理解串联起来，希望能对将来的工作提供帮助。3.对机器学习有认识但是实践经验较少的初级读者：从预备知识看起，逐一理解相关概念和方法，从而达到融会贯通的目的。4.仅仅对算法的工程实现感兴趣的读者：大致浏览一下预备知识中的2.3节，了解我1/17们要讨论什么，然后直奔各算法的算法逻辑（伪代码），照着实现就ok鸟。5.高富帅和白富美：只需要知道本文讨论的是一堆好用的求最优解的方法，可以用于分类预测、回归预测等一系列问题。然后吩咐攻城狮去实践就好了。还可以拿这篇文章嘲笑机器学习的屌丝：看你们都弄些啥，累死累活

7、的，挣那么几个钢镚2预备知识2.1凸函数如果?(?)是定义在N维向量空间上的实值函数，对于在?(?)的定义域?上的任意两个点?1和?2，以及任意[0,1]之间的值?都有：???1+1−??2≤???1+1−???2∀?1,?2∈?,0≤?≤1[1]那么称?(?)是凸函数（Convex）。一个函数是凸函数是它存在最优解的充分必要条件。此外，如果?(?)满足：???1+1−??2

8、条件通常我们需要求解的最优化问题有如下三类：(1)无约束优化问题：。?=???????(?)?含义是求解?，令目标函数?(?)最小；(2)有等式约束的优化问题：?=???????(?)??.?.???=0;?=1,2…,?含义是在n个等式约束???的条件下，求解?，令目标函数?(?)最小。(3)有不等式约束的优化问题：2/17?=???????(?)????=0;?=1,2…,??.?.???≤0;?=1,2…,?含义是在n个等式约束???以及m个不等式约束???的条件下，求解?，令目标函数?(?)最小。?针对无约束最优化问题，通常做法就是对?(?)求导，并令??

9、=0，求解