IT相关就是杨宗的学习记录人工智能/模式识别/机器学习精华专题

机器学习之最优化

2017-08-05  本文已影响83人  就是杨宗

这篇关于最优化的文章是最近学习的一个总结,放在简书上,方便以后查阅,如果帮助了其他读者,也算一件好事。

一、前言

现实生活中,当我们面临抉择(有几个备选方案可选),我们总是会希望可以做出最优选择,所以可以对所面临的问题进行建模,也就是根据需要考虑的因素,得到一个代价函数(损失函数)或者收益函数,然后求解该优化问题,寻找函数的最值点,得到最优选择。

例如种地问题,问:种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

上一篇下一篇

猜你喜欢

热点阅读