第三章 优化方法简介 Optimization Methods

梯度下降及不同形式

拉格朗日乘子法与KKT条件

对偶

3.1 为什么要优化？

机器学习问题最后都归结为优化问题。

优化问题的一般形式：

3.2 预备知识

泰勒展开 Taylor series

$$\begin{array}{rl}f(\mathbf{x})& =f({\mathbf{x}}_0)+\nabla f({\mathbf{x}}_0{)}^{\top }(\mathbf{x}-{\mathbf{x}}_0)+o(\Vert \mathbf{x}-{\mathbf{x}}_0{\Vert }_2)\\ f(\mathbf{x})& =f({\mathbf{x}}_0)+\nabla f({\mathbf{x}}_0{)}^{\top }(\mathbf{x}-{\mathbf{x}}_0)+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}_0{)}^{\top }{\nabla }^{2}f({\mathbf{x}}_0)(\mathbf{x}-{\mathbf{x}}_0)+o(\Vert \mathbf{x}-{\mathbf{x}}_0{\Vert }_2^2)\end{array}$$

梯度 Gradient

$$\nabla f(\mathbf{x})=\left[\begin{array}{c}\frac{\partial f(\mathbf{x})}{\partial x_1}\\ \frac{\partial f(\mathbf{x})}{\partial x_2}\\ ⋮\\ \frac{\partial f(\mathbf{x})}{\partial x_d}\end{array}\right]$$

海森矩阵 Hessian

$${\nabla }^{2}f(\mathbf{x})=\left[\begin{array}{ccc}\frac{{\partial }^{2}f(\mathbf{x})}{\partial x_1^2}& \cdots & \frac{{\partial }^{2}f(\mathbf{x})}{\partial x_1\partial x_d}\\ ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f(\mathbf{x})}{\partial x_d\partial x_1}& \cdots & \frac{{\partial }^{2}f(\mathbf{x})}{\partial x_d^2}\end{array}\right]$$

半正定矩阵 Positive semi-definiteness

局部最优解的充要条件

优化问题的困难

Go for convex problems!
寻求凸问题

3.3 凸集与凸函数

凸集 Convex Sets

定义

凸集举例

n维实数空间

n维实数非负象限

范式球

仿射子空间

凸函数 Convex Function

定义

凸函数成立的一阶条件

凸函数成立的更一般的条件

凸函数的充要条件：在每处都存在非空的次梯度或次微分集合。

凸函数成立的二阶条件

二阶可微 海森矩阵半正定

凸函数举例

线性函数

二次函数

范数

与仿射函数的组合

Log-sum 形式

机器学习中的例子

保凸运算

为什么关心函数的凸性？

任何局部极值都是全局极值。

这意味着我们找到的解就是最优解。

这使得优化变得容易，因为不必担心陷入局部极值。

凸优化 Convex Optimization

定义

仿射函数
凸集
凸函数

凸优化问题的好处

凸优化的更多性质

3.4 无约束优化

无约束优化

如果没有解析解的话，可以使用梯度下降或牛顿方法等迭代的手段来使x沿负梯度方向逐步逼近极小值点。

★梯度下降 Gradient Descent

梯度的更新公式：

$$x_{t+1}=x_t-{\eta }_t\nabla f(x_t)$$

${\eta }_t$ 是学习率

梯度下降算法

梯度下降的学习率

学习率过大，收敛时产生振荡，难以收敛到最优值；

学习率过小，则收敛极其缓慢，可能也难以收敛到最优值。

★梯度下降的不同形式

根据每一步所用的数据量：

• 批量梯度下降法（Batch Gradient Descent, BGD）
  是梯度下降法最常用的形式 ，就是在更新参数时使用所有的样本来进行更新。
• 随机梯度下降法（Stochastic Gradient Descent, SGD）
  每一步仅仅选取一个样本来求梯度。
• 小批量梯度下降法（Mini batch Gradient Descent, MBGD）
  是批量梯度下降法和随机梯度下降法的折衷，每一步采用一部分固定数量的样本来计算。

批量梯度下降法

梯度更新比较耗时，尤其是数据集非常大的情况下 。但是由于每次的下降方向为总体样本的平均梯度，更准确
地朝向极值所在的方向迭代次数少。

批量梯度下降法的速度会比较慢，尤其是数据集非常大的情况下，收敛速度就会非常慢，但是由于每次的下降方向为总体样本的平均梯度，它得到的会是一个全局最优解。

随机梯度下降法

梯度更新快，由于每次迭代并不是都向着全体样本的最优化方向，导致梯度下降的波动非常大，更容易从一个局部最优跳到另一个局部最优，准确度下降。迭代次数多，可能不收敛，或陷入局部极值或鞍点。

训练速度很快，即使在样本量很大的情况下，可能只需要其中一部分样本就能迭代到最优解，由于每次迭代并不是都向着全体样本的最优化方向，导致梯度下降的波动非常大，更容易从一个局部最优跳到另一个局部最优，准确度下降。

小批量梯度下降法

小批量梯度下降法既保证了训练的速度，又能保证最后收敛的准确率。

小批量梯度下降法介于前两者之间，梯度更新比 BGD 快，迭代次数比 SGD 少。学习过程仍会有振荡，为更
接近最小值，需要增加学习率衰减项，避免过度振荡。

机器学习中使用建议

简单的说就是：
批量梯度下降在每次更新参数时，利用全部样本来计算梯度；
随机梯度下降在每次更新参数时，随机选择一个样本来计算梯度；
小批量梯度下降在每次更新参数时，随选择一个样本子集来计算梯度；

• 当训练集比较小时
  批学习，采用拟牛顿或者共轭梯度下降
• 当训练集大时
  随机梯度下降
• 当训练集介于二者之间时
  小批量学习

牛顿法 Newton's method

牛顿法

拟牛顿法

牛顿法与梯度下降的对比

略

共轭梯度法

略

梯度下降的改进

基于学习率

• 学习率衰减
• Adagrad
• Adadelta
• RMSprop

基于梯度

• Momentum 基于动量的方法
• Nesterov accelerated gradient
• 梯度截断
• Adam
• Nadam

AdaGrad 自适应学习率 (2011)

Adadelta 自适应增量算法 (2012)

RMSprop 均方根传递算法 (2012)

动量 Momentum 优化法

ADAM 适应性矩估计算法 (2014)

略

3.5 约束优化

等式约束

等式约束 Equality constraints 问题

约束条件会将解的范围限定在一个可行域，此时不一定能找到使得 ∇xf(x)为 0 的点，只需找到在可行域内使得 f(x)最小的值即可。

可行域

示例:

局部极值的条件

在区域内部，极值点必为驻点，但驻点不一定是极值点

二维情况下的目标函数是 f(x,y) ，在平面中画出 f(x,y)的等高线，如下图的虚线所示，只给出一个约束等式 h(x,y)=0 ，如下图的绿线所示，

目标函数 f(x,y)与约束 h(x,y) 只有三种情况：相交、相切或者没有交集。

• 没交集肯定不是解。
• 相交得到的一定不是最优值。因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小。
• 只有等高线与目标函数的曲线相切的时候，才可能得到可行解。
  ${\nabla }_{x}f(x)-\alpha {\nabla }_{x}h(x)=0$
  两者的法向量是平行的

★等式约束的拉格朗日乘子法

一个等式约束的情况

有等式约束最优化问题的表现形式：

定义拉格朗日函数：

则当 $x^{\ast }$ 是一个局部最小 <=> 存在一个 ${\mu }^{\ast }$ 满足约束

其中 ${\nabla }_{\mathrm{x}\mathrm{x}}^2\mathcal{L}(x^{\ast },{\mu }^{\ast })$ 是正定矩阵。

多个等式约束的情况

不等式约束

示例 1

如何确定 $x_F$ 是局部极值点?

当约束区域包含目标函数原有的可行解时，此时加上约束可行解仍落在约束区域内部，对应g(x)<0的情况，这时约束条件不起作用.

这个例子中的约束是无效（inactive）约束

示例 2

当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界 g(x)=0上。

如何确定 $x_F$ 是局部极值点?

由图可见可行解 x 只能在 g(x)<0 或者 g(x)=0 的区域里取得：

• 当可行解 x 落在 g(x)<0 的区域内，此时直接极小化 f(x) 即可；
• 当可行解 x 落在 g(x)=0 即边界上，此时等价于等式约束优化问题.

约束的局部极值点

在不等式约束中，若 λ≠0，说明可行解 x 是落在约束区域的边界上的，
这时可行解应尽量靠近无约束时的解，
在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解，
此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同

★一个不等式约束情况下优化问题的总结

★不等式约束的拉格朗日乘子法 KKT条件

一个不等式约束的KKT条件

定义拉格朗日函数：

则当­ $x^{\ast }$ 是一个局部最小 <=> 存在一个­ ${\lambda }^{\ast }$ 满足约束：(KKT条件)

• ${\nabla }_{\mathrm{x}}\mathcal{L}({\mathbf{x}}^{\ast },{\lambda }^{\ast })=0$
• ${\lambda }^{\ast }\ge 0$
• ${\lambda }^{\ast }g({\mathbf{x}}^{\ast })=0$
• $g(x^{\ast })\le 0$
• Plus positive definite constraints on ${\nabla }_{\mathbf{x}\mathbf{x}}\mathcal{L}({\mathbf{x}}^{\ast },{\lambda }^{\ast })$ （在 ${\nabla }_{\mathbf{x}\mathbf{x}}\mathcal{L}({\mathbf{x}}^{\ast },{\lambda }^{\ast })$ 加上正定的约束）

特别注意：

• 优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件。
• 不是凸优化的话，KKT条件只是极小值点的必要条件，不是充分条件。

KKT条件概括了这两种情况：

多个不等式约束的KKT条件

多个等式、不等式约束的KKT条件

KKT条件例题

可行域

一种解法

另一种解法

★对偶函数与对偶问题

在机器学习中，对偶（duality）是指将一个优化问题转化为其对偶形式，从而更容易地解决原始问题。具体来说，对于一个原始优化问题，通过构建一个拉格朗日函数，并对其进行最大化或最小化，可以得到对偶问题。通过解决对偶问题，我们可以获得原始问题的解。这种方法在解决某些优化问题时非常有用，因为对偶问题可能比原始问题更容易求解。

对偶问题

一般描述

对偶问题

不等约束下的最优化一阶必要条件： KKT 条件

为什么要研究对偶问题？

虽然对偶方法并不能保证成功，但是

• 它对于某些类别的函数有效。
• 在这些情况下，它总能带来更简单的优化问题。
• 特别是当原问题中自变量的维度比约束的数量大得多的情况下。
• 最优解由拉格朗日乘子构成的表达式可以帮助我们理解最优解，例如在SVM中那样。
• 对偶函数总是凹函数，无论原问题如何。
• 所以对偶函数的优化是个凸优化问题。

弱对偶&强对偶

令 $f^{\ast }$ 表示原问题最优解，$q^{\ast }$ 表示对应的拉格朗日对偶问题的最优解，则

弱对偶，$q^{\ast }\le f^{\ast }$，拉格朗日对偶问题的最优解是原问题最优解的最好下界，且原问题不论是否为凸，弱对偶总是成立；

强对偶，$q^{\ast }=f^{\ast }$，若原问题是凸优化问题、满足KKT条件，则强对偶条件成立，此时可以通过求解对偶问题来得到原始问题的解。

3.6 坐标下降优化

坐标下降法

坐标下降法每次沿着单个维度方向进行搜索，当得到一个当前维度下的最小值之后再循环使用不同的维度方向，最终收敛得到最优解。

块坐标下降法

块坐标下降是坐标下降的更一般化，它通过对变量的子集进行同时优化 ，在下降的过程中更新的次序可以是确定的或随机的。