机器学习之最优化
这篇关于最优化的文章是最近学习的一个总结,放在简书上,方便以后查阅,如果帮助了其他读者,也算一件好事。
一、前言
现实生活中,当我们面临抉择(有几个备选方案可选),我们总是会希望可以做出最优选择,所以可以对所面临的问题进行建模,也就是根据需要考虑的因素,得到一个代价函数(损失函数)或者收益函数,然后求解该优化问题,寻找函数的最值点,得到最优选择。
例如种地问题,问:种x亩的玉米和y亩的小麦可以获得最大收益,x和y均未知,且满足一定约束条件,调整x和y,使得目标函数达到最大,也就得到了最优选择。
大部分的机器学习算法都可以归结为最优化问题,例如logistic回归和神经网络,都是调整模型参数,使得损失函数最小,得到参数的最优值;SVM中,调整模型参数,使得划分超平面距离两个类边缘的间隔最大,即得到模型的最优解。
二、从最优化到凸优化
一般情况下求解一个函数的最值并不容易,因为容易陷入局部极值,所以一般的最优化问题直接穷举遍历(解空间比较小)或者使用启发式搜索(解空间很大,NP问题)。而凸优化问题(convex optimization)则可以高效地求解最值,基于目标函数的“凸”性,它的局部最优解即为全局最优解。
一旦一个问题转化为凸优化问题,那么这个问题就得到了解决,因为凸优化已经被研究透了。
三、凸优化的定义:
(1)凸集(convex sets):集合中任意两点的连线都在这个集合中。
(2)凸函数(convex functions):函数曲线任意两点的连线都在函数上方。
(3)凸优化:调整优化变量使得目标函数(是一个凸函数)最小,优化变量属于凸集,或者说优化变量需要满足一定的不等式约束和等式约束。
四、凸优化问题分类:
(1)线性规划(LP, linear programming):目标函数和不等式约束都是线性函数。
(2)二次规划(QP, quadratic programming):目标函数是凸二次函数,不等式约束是线性函数。
(3)二次约束二次规划(QCQP, quadratically constrained quadratic programming):目标函数和不等式约束都是凸二次函数。
五、凸优化问题求解的一般方法:
根据凸函数的性质,只要一直沿着可以使目标函数变小的方向搜索,就可以找到最小值,所以可以使用梯度下降的方法。
要更新某一个优化变量,只需对这个优化变量求偏导,然后计算它处于当前值的导数,即梯度,也就是目标函数在此处的变化率,然后乘上步长,即得到修正量,然后根据负梯度方向更新这个优化变量即可。
六、求解线性规划:
先画出可行域,然后将顶点代入目标函数,求得最大值或最小值即可。
这是因为,目标函数是线性函数,所以只要x或y增大,目标函数都会增大,所以可能的最优解一定在可行域的边界上。沿着边界,x或y会增大,直到遇到拐点(也就是可行域的顶点),遇到拐点之后,x或y可能会减小,所以最优解只可能是几个交点之一。
转载请注明如下内容:
文章来自简书,作者:就是杨宗
原文链接:http://www.jianshu.com/p/b47daa391e2d