首页 > 代码库 > 优化之法

优化之法

 

背景

我要说的优化不是软件开发中的优化(降低空间和时间复杂度),而是一种意义更普遍的优化算法,是已知问题模型,如何寻找最优解的方法,已知能量函数(也叫代价函数)求全局最小值,恰如图中所示。优化算法是如此的普遍,机器学习中的线性回归,计算机视觉中的特征匹配,立体视觉和三维重建。又是如此的种类繁多,局部的和全局的,连续的和离散的,一阶的和二阶的。实现复杂的优化算法是会让人抓狂的,像什么L-BFGS即便是Andrew Ng这样的风云人物也是过了若干年以后才有所领悟。梯度下降虽然简单,但实现它也有很多技巧。

 

选择

    基于梯度的算法还有最速下降,牛顿法,高斯牛顿,阻尼牛顿,共轭梯度,随机梯度下降,大名鼎鼎的LM(列文伯格马奎尔特)。如果你不了解这些算法的原理和特点,很容易会迷失在这些稀奇古怪的名字中。我了解到的原则是,当能量函数的梯度可求时用基于梯度的方法,这时LM往往是最好的选择。因为LM实际上是梯度下降和牛顿下降的完美合体。当能量函数不平滑时,这些算法很容易收敛于局部最小,如图中卡在半山腰的小球。需要应用一些全局搜索策略,比如线性搜索。或者在代价函数中加入扰动,像随机梯度下降法所做的那样。除此外,还应兼顾时间,精度和鲁棒性。

 

实现

    如果有人问我:对于自己实现一种优化算法,你有何建议?我的回答是:你最好别这样做,用现成的库,因为这里面诡计多端,是一个苦活累活。如果非得自己写,掌握那些基本的技巧和调试方法是必不可少的。我在课题中使用随机梯度下降法,因此以它为例子介绍。题目是:基于统计学模型的3D人脸重建。它有两个输入:一是输入照片(2D),二是统计学模型(3D)。借助于计算机图形学把统计学模型投影成2D照片,输入照片和模型照片的像素平法差作为能量函数,应用随机梯度下降法优化之。能量函数的形式千差万别,本例中形式如下。


 

正如其名,这个算法的核心是随机的计算梯度。具体说就是随机的选择40个像素点,基于这些点计算能量函数的梯度,也就是求解每个变量的偏导,或许用到链条法则视情况而定。求导是最基本的也是最重要的一步,出错一切都是白费,除了细心求解反复验证以外没有更好的办法了。真正重要的是调试技巧:怎样选择一个合适的学习曲率(下图中的lambda)?怎样验证算法是否有效?

取不同的学习曲率lambda,典型的取值[0.001,0.003,0.01,0.03,0.1,0.3,1,3,10]。绘制能量函数随迭代次数变化之曲线。假如像下面左图的形状,说明算法收敛,lambda选择合适。如果能量函数曲线一路飙升,或者上下起伏不定,像下面中右图的形状,说明lambda大了。选择更小的lambda,竭尽全力的左倾。

 

有时候纵使选择了合适的lambda,最终结果也不见得好。很可能是因为模型不准导致过拟合和欠拟合,或者叫做高方差和高偏差的问题。同样的还是通过绘制曲线来解决,这条曲线叫做学习曲线(learning cure)。这时候在能量函数中引入正则项,下面公式后三项。

 

特别的把数据分成3类:训练集,验证集,测试集。具体做法是:1)用没有正则项的代价函数在训练集上优化模型参数。2)使用优化的模型参数在验证集上求函数值。3)使用优化的模型参数在测试集上函数值。4)绘制学习曲线。学习曲线揭示了模型的本质特征,对于高偏差的情况增加训练数据徒劳无益,对高方差的情况却有所成效。更多细节参考Andrew ng的机器学习https://www.coursera.org/course/ml,它是我的想法之源。