Question

为了探索比上面的向量空间模型更加有效的计算广告方案，必然会碰到大量的与数据挖掘和机器学习相关的算法问题。在这些与数据相关的问题中，最重要的基础技能是最优化理论和方法。最优化讨论的是在给定一个数学上明确表达的优化目标后，如何用系统性的方法和思路找到该目标的最优解。这方面的书籍和文章很多，我们从工程的角度出发，简要整理一下在面临各类目标函数时的一般性思路，并希望大家能够认清“模型”和“优化”这两个概念的联系与区别。

最优化问题讨论的是，给定某个确定的目标函数以及该函数自变量的一些约束条件，求解该函数的最大或最小值的问题。这样的问题可以表示为下面的一般形式：

这里 f（x）是一个关于自变量 x的目标函数，而 g（x）和 h（x）为 x的矢量函数，对应着一组不等式和等式约束条件，其中g（x）≺0表示矢量g（x）的每一个元素都小于或等于0。根据约束条件以及目标函数的性质不同，最优化问题求解的思路也有很大的不同。其中无约束优化问题的方法是基础，而带约束优化问题则在一定条件下可以转化为无约束优化问题来求解，这涉及下面将要谈到的拉格朗日法和凸优化问题。

10.2.1 拉格朗日法与凸优化

我们先来看看解带约束优化问题的一般框架思路。在实际工程中，带约束优化非常常见，如后面将提到的广告合约量约束下的优化问题。有关带约束优化最重要的方法就是拉格朗日法。具体来说，对公式 10.4 那样的带约束优化问题，可以引入一个拉格朗日对偶函数（Lagrange dual function）^[13]或简称对偶函数：

这里引入的矢量变量λ和ν称为拉格朗日乘子，对偶函数是一个关于拉格朗日乘子的函数，对应地，有下面的拉格朗日对偶问题（Lagrange dual problem）：

可以证明，对偶问题的最优值是原问题最优值的下界，而当这两者完全一致时，称为强对偶（strong duality）得到满足。可以证明，当原问题是凸优化问题，即目标函数为凸函数，并且由各项约束得到的可行解域（feasible region）也是凸的话，强对偶总是被满足的。但需要特别说明，并不是只有凸优化问题才是强对偶的^[3]，如后面将要提到的Trust-Region法中的子问题，虽然其目标函数不能保证为凸，但是强对偶也是可以保证的。由于凸优化的这一性质，它在带约束优化中具有非常重要的核心地位——因为我们可以通过转而优化对偶问题求得同样的解，这为优化过程提供了极大的方便性。另外有趣的是，不论原问题是否为凸优化，这一对偶问题都是一个凸优化问题，因此往往在求解上有一定的便利性。

进一步，当原目标函数和所有的约束函数都可导时，强对偶问题最重要的性质是使得KKT（Karush-Kuhn-Tucker）^[13]条件成立的点可以同时满足原问题和对偶问题最优化的要求。KKT条件是一组关于x，λ，ν的等式和不等式方程，它为很多带约束优化问题提供了求得解析解的思路，这里我们略去其具体形式，有兴趣的读者请进一步参考参考文献[13]中详细的

说明。

拉格朗日乘子法和KKT条件为带约束优化问题提供了标准思路。而当我们遇到的带约束优化问题为凸优化时，完全可以沿着这一标准思路来解决；当问题不是凸优化时，需要具体分析强对偶是否成立，再决定求解的思路。

通过拉格朗日方法，我们可以将一个带约束优化问题转化为不带约束的基本优化问题来解决。在下面的讨论中，我们将根据优化问题的特点介绍无约束优化的一些基本算法。

10.2.2 下降单纯形法

在有些问题中，f 不可导或者工程上求导代价极大^[4]这种情形下，假设函数值是连续的，我们有一种自然的思路，那就是采用不断试探的方法：在自变量为一维的情况下，给定一个初始区间，假设区间内有唯一的最小值，可以按照黄金分割的方法不断缩小区间以得到最小值。

上面的方法也可以推广到自变量是高维的情形，对应的算法称为下降单纯形法（downhill simplex method）。这一方法有一个更直观的称呼，即阿米巴变形虫法。简单地讲，将一维空间上用两个点限制的区间不断变形的思路加以推广，在D维空间中可以选择一个D+1个点张成的超多面体或称为单纯形（simplex），然后对这一单纯形不断变形以收敛到函数值的最小点。

有关下降单纯形法的细节和代码实现可以参考参考文献[66]。

10.2.3 梯度下降法

当 f 可以比较容易地求导时，基于梯度的方法是首要选择。我们先来看一下梯度的定义。假设有D维空间中的自变量x=（x₁，x₂，...x_D）^>∈R^D，那么函数f（x）在x点的梯度可以写成：

梯度的几何意义是 f 在 x点函数值上升最快的方向，因此它是一个与 x维数相等的矢量。利用梯度的优化方法概念上就是每次都沿着梯度的相反方向按某步长前进一小步，这样的方法称为梯度下降法（gradient descent），其更新公式为：

其中†控制着沿梯度负方向下降的速度，称为学习率（learning rate）。

很多工程中的目标函数都具有可分解的特性，即整个训练集上的梯度可以表示为各个训练样本梯度的和。在这种情况下，一个可行但效率并不高的并行实现就是将计算梯度的过程分解到各个数据划分上分别完成，然后将各部分的梯度相加并更新参数。显然这样的计算过程非常容易在MapReduce框架下实现，然而每迭代一步，都要用到训练集所有的数据，可想而知，在数据规模较大时，这种方法的迭计算效率是比较低的。

在在线学习中，梯度下降的方法还有另外一种变形，也就是随机梯度下降（Stochastic Gradient Descent，SGD）^[12]的方法。在普通梯度方法中，计算一次下降方向需要很大的计算量，而SGD的每一次迭代并不是精确地计算梯度，而是基于随机选取的一个样例来计算梯度。这是一个重要的简化，在实际大数据的情况下，这比普通的梯度法效果更好。从计算角度来看，SGD并不容易并行实现，为了实现其并行计算，产生了一系列并行SGD算法和相应的机器学习框架，如Parallelized SGD^[82]等，有兴趣的读者可以深入了解。

10.2.4 拟牛顿法

在实际的工程问题中，简单地采用批处理模式的梯度下降法有时会遇到一个麻烦：当函数值对各个自变量归一化不够好时，优化过程会陷入Zig-Zag折线更新的困境，这一现象可以用图10-1 中的例子来形象地说明。在自变量维数很高时，这一问题尤为严重，因为我们无法一一检查各个自变量的意义，因此在某些维度上缩放尺度不一样是无法避免的。如何避免这一问题呢？我们假设函数值呈现像图10-1中那样呈近似的二次曲面状，那么很自然的思路就是引入二阶导数信息，以迅速探索到函数值的谷底。

图10-1 梯度下降法优化过程陷入Zig-Zag折线示意

f（x）的二阶导数是一个D×D的矩阵，其定义为：

这是一个 D×D 的矩阵，我们称之为赫斯矩阵（Hessian matrix）。同时利用梯度和二阶导数做优化，相当于在当前点处进行二阶的泰勒展开，并找到此二次曲面的极小值点，这样的方法称为牛顿法，其更新公式为：

当†=1时，牛顿法的每一步都是在求一个二次曲面的极小值。显然，只有当赫斯矩阵正定时，极小值才存在。不过在实际的优化问题中，即使目标函数存在唯一的极小值，也不能保证每一点的赫斯矩阵都正定，因此一般来说，牛顿法并不是想象中那样可行。

解决上面的问题其实也不难：我们可以构造一个不太精确，但是可以保证正定的伪赫斯矩阵，用它来代替实际的赫斯矩阵更新参数，这样的方法就是工程上真正使用的拟牛顿法。直观上来看，利用前面几次迭代的函数值和梯度可以近似地拟合出赫斯矩阵，而随着拟合公式的不同，也就产生了不同的拟牛顿方法。拟牛顿的一种常见方法是由 Broy-den、Fletcher、Goldfarb 和 Shanno 四位学者创造的，称为 BFGS 方法^[62]。在 BFGS 方法中，赫斯矩阵的逆是迭代更新的，其更新公式如下：

其中y_k=∇_k+1−∇_k 为前后两次的梯度差，而s_k=x_k+1−x_k 为前后两次的自变量差。这里之所以要直接操作赫斯矩阵的逆是因为在牛顿法的更新中，给定赫斯矩阵的逆和梯度矢量，可以通过简单的矩阵乘法得到更新方向，从而避免了复杂的求逆过程。

再来看看如何确定公式 10.10中的步长 †。牛顿法是在当前自变量点进行泰勒展开，因此拟合出来的二次曲面严格来说只在很小的邻域内是有效的，因此我们完全无法保证按公式10.10或得到更好的函数值。但是，当†足够小时，一定可以找到一个比现有函数值更优的点。要找到这样一个合适的†，需要根据Wolfe条件^[62]，即要求†满足如下的不等式：

其中p_k为迭代第k步时找到的下降方向，在拟牛顿法中即为B_k∇f_k（x），而为两个常数^[5]。因此，在实际的拟牛顿法中，在得到下降方向后，需要在下降方向上进行线搜索（line search），以找到满足Wolfe条件的†用以更新参数。

需要强调，拟牛顿法是连续优化问题中最为基础的优化方法，它作为原子操作大量地被用在其他更为复杂的优化方法当中。因此，对拟牛顿方法熟练地掌握和应用是工程中非常重要的基本技能。我们在下面附上BFGS迭代求解的代码片段。

这段代码仍然是示例性的，并且为了表述简洁，其中用到了未预先定义但意义很清楚的简单的运算函数，例如用 dot 函数计算两个适量的点积等。本书后面的一些代码也会有这样的情况，我们就不一一说明了。在上述代码中用到了一维线搜索求解步长，即其中的WolfeSearch函数调用。比较常见的方案是基于Wolfe条件的方法，下面给出其示例性代码。

10.2.5 Trust-Region 法

梯度下降法、牛顿法和拟牛顿法都属于线搜索方法，它们的共同特点是，在当前迭代点x^k处寻找下一个迭代点x^k+1时，首先确定一个下降方向，然后沿着这个下降方向进行一维线搜索。这种搜索策略可以概括为“先方向，后步长”。Trust-Region法采用的是一种不同的搜索策略：每次迭代时，将搜索范围限制在x_k 的一个置信域内，然后同时决定下次迭代的方向和步长；如果当前置信域内找不到可行解，则缩小置信域范围。在每个迭代中，我们要求自变量的差s_k满足。另外为了单次迭代求解的效率，用函数在x_k附近的泰勒展开来近似原来的目标函数f（x_k+s）。具体来说，每一次迭代需要解下面形式的子问题：

通过解得的 s 就可以同时获得本次迭代的方向和步长。由于此过程没有对目标函数的一阶导和二阶导做近似，往往能够更准确地把握下降方向，因此有时能表现出比拟牛顿法更好的收敛性能。

在公式 10.13的基础上，为了实现 Trust-Region优化策略，还需要确定置信半径 δ_k 的选取。一般来说，可以通过比较模型函数和目标函数的下降量来指导置信半径的选择：

如果，说明目标函数值没有改进；若模型函数较真实地逼近了目标函数，我们期望ρ_k的值接近于1；如果ρ_k 的值较小，说明在当前置信域内，模型函数和目标函数差别较大，需要缩小当前的置信域；如果 ρ_k 的值较大，可以在下次迭代时适当伸长收敛半径。在这一思路的基础上，我们附上Trust-Region算法主流程的代码片段。

每个迭代中需要解子问题10.13，即代码中tr cg的函数调用。显然，这是一个带约束优化问题，由于∇²f（x_k ）未必是正定的，因此这并不是一个凸优化问题。不过，在这个特殊的非凸优化中，读者可以自行验证，KKT 条件是可以满足的，因此仍然可以用拉格朗日法来求解。我们略去求解的过程，直接给出下面的解。为问题10.13的全局最优解，当且仅当本身是一个可行解，并且存在满足下面的条件：

最后一个不等式表示矩阵（H_k+λI ）是半正定的。当 ˆs位于置信域内部时，λ=0，有显式解；当位于置信域边界上时，λ>0，问题变为寻找充分大的λ>0，使得H_k+λI半正定，并且为这一方程的根，此时虽然不存在显式解，但由于这是一个单变量的优化问题，可以比较方便地用线搜索的方法得到解。根据公式10.14，读者容易写出tr_cg函数的具体实现。