优化算法

Posted by MaggicQ on April 13, 2019

本文目录

常见优化算法

常见损失函数

机器学习算法的关键一环是模型评估,而损失函数定义了模型的评估指标。可以说,没有损失函数就无法求解模型参数。不同的损失函数优化难度不同,最终得到的模型参数也不同,针对具体的问题需要选取合适的损失函数。

下面介绍一下几种常见的监督学习中的损失函数:

0-1损失函数

其中$y$表示样本点的标签,$x$表示样本点的特征,$f$是我们训练的模型。

该损失函数能够直观地刻画分类的错误率,但是由于其非凸、非光滑的特点,使得算法很难直接对该函数进行优化。

Hinge损失函数

Hinge损失在$fy\geq 1$处不可导,因此不能用梯度下降法进行优化,而是用次梯度下降法(Subgradient Descent Method)。

Logistic损失函数

该函数处处光滑,因此可以用梯度下降法进行优化。但是,该损失函数对所有的样本点都有所惩罚,因此对异常值相对更敏感一些。

交叉熵损失函数

当预测值$f \in [-1, 1]$时,另一个常用的代理损失函数是交叉熵(Cross Entropy)损失函数:

这四种损失函数的曲线如图所示:

平方损失函数与绝对损失函数

对于回归问题,最常用的损失函数是平方损失函数:

平方损失函数是光滑函数,能够用梯度下降法进行优化。然而,当预测值距离真实值越远时,平方损失函数的惩罚力度越大,因此它对异常点比较敏感。为了解决该问题,可以采用绝对损失函数:

绝对损失函数相当于是在做中值回归,相比做均值回归的平方损失函数,绝对损失函数对异常点更鲁棒一些。

梯度下降法

梯度下降法(gradient descent)是求解无约束最优化问题的一种最常用的方法。

梯度下降法是一种迭代算法。选取适当的初值$x(0)$,不断迭代,更新x的值,进行目标函数的极小化,直到收敛。由于负梯度方向是使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新x的值,从 而达到减少函数值的目的。

梯度下降法的流程如下:

输入:目标函数 $f \left( x \right)$ ,梯度函数 $g\left( x^{\left(k\right)} \right)=\nabla f \left( x^{\left(k\right)}\right)$ ,计算精度 $\varepsilon$

输出: $f \left( x \right) $ 的极小点 $x^{*}$

  1. 取初值 $x^{\left(0\right)} \in R^{n}$ ,置 $k=0$
  2. 计算 $f \left( x^{\left(k\right)}\right)$
  3. 计算梯度 $g_{k}=g\left( x^{\left(k\right)} \right)$ ,当 $\| g_{k} \| < \varepsilon $ 时,停止迭代,令 ;否则,令 ,求 ,使:

  4. 置 $x^{\left(k+1\right)}= x^{\left(k\right)}+\lambda_{k}p_{k}$ ,计算 $f \left( x^{\left(k+1\right)} \right)$ 当 $\| f \left( x^{\left(k+1\right)} \right) - f \left( x^{\left(k\right)} \right) \| < \varepsilon $ 或 $\| x^{\left(k+1\right)} - x^{\left(k\right)} \| < \varepsilon $ 时,停止迭代,令 $x^{*}=x^{k+1}$
  5. 否则,置 $k=k+1$ ,转3.

当目标函数是凸函数时,梯度下降法的解是全局最优解。一般情况下,其解不保证是全局最优解。梯度下降法的收敛速度也未必是很快的。

在使用梯度下降时,需要进行调优。哪些地方需要调优呢?

  1. 算法的步长选择。为了加快收敛速率,同时提高求解精度,通常会采用衰减学习速率的方案:一开始算法采用较大的学习速率,当误差曲线进入平台期后,减小学习速率做更精细的调整。最优的学习速率方案也通常需要调参才能得到。
  2. 算法参数的初始值选择。初始值不同,获得的最小值也有可能不同,因此梯度下降求得的只是局部最小值;当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险,需要多次用不同初始值运行算法,关键损失函数的最小值,选择损失函数最小化的初值。
  3. 归一化。由于样本不同特征的取值范围不一样,可能导致迭代很慢,为了减少特征取值的影响,可以对特征数据归一化。
  4. ​算法的batch size大小的选择,在不同的应用中,最优的batch size通常会不一样,需要通过调参选取。一般$m$取2的幂次时能充分利用矩阵运算操作,所以可以在2的幂次中挑选最优的取值,例如32、64、128、256等。

梯度下降法的几种分类(BGD,SGD,MBGD)

  • 批量梯度下降法(Batch Gradient Descent)是梯度下降法最常用的形式,具体做法也就是在更新参数时使用所有的样本来进行更新。当样本数量很大的时候,这需要很大的计算量,耗费很长的计算时间,在实际应用中基本不可行。
  • 随机梯度下降法(Stochastic Gradient Descent),其实和批量梯度下降法原理类似,区别在与求梯度时没有用所有的样本的数据,而是仅仅选取一个样本来求梯度。随机梯度下降法,和批量梯度下降法是两个极端,一个采用所有数据来梯度下降,一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说,随机梯度下降法由于每次仅仅采用一个样本来迭代,训练速度很快,而批量梯度下降法在样本量很大的时候,训练速度不能让人满意。对于准确度来说,随机梯度下降法用于仅仅用一个样本决定梯度方向,导致解很有可能不是最优。对于收敛速度来说,由于随机梯度下降法一次迭代一个样本,导致迭代方向变化很大,不能很快的收敛到局部最优解。

  • 小批量梯度下降法(Mini-batch Gradient Descent)小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷,也就是对于 $m$ 个样本,我们采用 $x$ 个样子来迭代, $1<x<m$ 。一般可以取 $x=16,32,64…$ ,当然根据样本的数据,可以调整这个 $x$ 的值。

牛顿法和拟牛顿法

牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法,有收敛速度快的优点。牛顿法是迭代算法,每一步都需求解目标函数的海塞矩阵(Hessian Matrix),计算比较复杂。拟牛顿法通过正定矩阵近似海塞矩阵的逆矩阵或海塞矩阵,简化了这一计算过程。

牛顿法的最初提出是用来求解方程的根问题。我们假设点 $x^\star$ 为函数 $f(x)$ 的根,那么有 $f(x^\star)=0$ 。现在我们把函数 $f(x)$ 在点 $x_k$ 处一阶泰勒展开有:

$\frac{f(x)-f(x_k)}{x-x_k} = f^{‘}(x_k) \Rightarrow f(x)=f(x_k) + f^{‘}(x_k) \cdot (x-x_k)$

那么假设点 $x_{k+1}$ 为该方程的根,则有: $f(x_{k+1})=f(x_k) + f^{‘}(x_k) \cdot (x_{k+1}-x_k) = 0$

得到: $x_{k+1} = x_k - \frac{f(x_k)}{f^{‘}(x_k)}$

此时得到一个递归方程,可以通过迭代的方式不断的让 $x$ 趋近于 $x^\star$ 从而求得方程 $f(x)$ 的解。

牛顿法求解方程的根的过程如下图所示:

下面讲述的是,如何将牛顿法应用到无约束最优化问题中。

考虑无约束最优化问题:

其中: $x^\star$ 为目标函数的极小点。

对于最优化问题, $f(x)$ 有极值的必要条件是:极值点处一阶导数等于0,即梯度向量为 0。特别是当 Hessian 矩阵为正定矩阵时,函数 $f(x) $有极小值。因此我们可以在一阶导数处利用牛顿法通过迭代的方式求得最优解,即:求一阶导数对应函数的根。

牛顿法的直观解释:每一次迭代,目标函数在局部可以近似表示成二次函数,然后以该二次函数的极值点来代替目标函数的极值点,不断重复直到收敛。

既然要将目标函数局部近似为二次函数,自然地就要引入泰勒公式。假设 $f(x)$ 具有二阶连续偏导,若第 $k$ 次迭代值为 $x_k$ ,则可将 $f(x)$ 在 $x_k$ 附近进行二阶泰勒展开:

其中: $∇ f(x_k)$ 是 $f(x)$ 的梯度向量在点 $x_k$ 的值, $H(x_k)$ 是 $f(x)$ 的 Hessian 矩阵。

$f(x)$有极值的必要条件:它的一阶导在极值点处取值为0特别地,若是极小值点则 Hessian 是正定矩阵。 $f(x)$ 的一阶导为: $∇ f(x) = ∇ f(x_k) + H(x_k)(x-x_k)$ 因此,若从 $x_k$ 开始迭代,求 $f(x)$ 的极小点 $x_{k+1}$作为第 $k+1$ 次的迭代值。即:

则有: $x_{k+1} = x_k - H^{-1}(x_k) ∇ f(x_k)$ ,即为牛顿法的迭代公式。

我们可以看到,当 $ H(x_k)$ 为正定( $ H^{-1}(x_k)$ 也为正定)的时候,可以保证牛顿法的搜索方向是向下搜索的。

牛顿法的算法流程:

输入:梯度 $g(x)=∇f(x)$ ,Hessian 矩阵 $H(x)$ ,精度 $ϵ$ ;

输出: $f(x)$ 的极小点。

1) 随机选择初始点 $x_0$ ,迭代次数 $k=0$ ;

2) 计算目标函数 $f(x)$ 在点 $x_k$ 的梯度 $g(x_k)$ 和Hessian 矩阵 $H(x_k)$; 若 $||g(x_k)|| <\epsilon$ ,停止计算,得到近似解: $x^\star=x(k)$

3) 根据迭代公式 $x_{k+1} = x_k - H^{-1}(x_k) ∇ f(x_k)$ 更新 $x$ 值;

步骤(3)要求 $H^{-1}(x_k)$ ,计算比较复杂,所以有其他的改进方案。

在上面所说的牛顿法的迭代中,需要计算 Hessian 矩阵的逆矩阵,计算过程较复杂,考虑采用一个 $n$ 阶矩阵 $G_k = G(x_k)$ 近似替代 $H^{-1}_k = H^{-1}(x_k)$,这就是拟牛顿法的基本想法。常用的求解拟牛顿的算法有DFP算法、BFGS算法、Broyden类算法

具体就不展开了。

EM算法

EM算法也称期望最大化(Expectation-Maximum,简称EM)算法,它是一种迭代算法,用于含有隐变量(hidden variable)的概率模型参数的极大似然估计。

EM算法的引入

如果概率模型的变量都是观测变量,那么给定数据,可以直接使用极大似然估计法,或是贝叶斯估计法估计模型参数。但是当模型含有隐变量时,就不能简单地使用这些方法,EM算法就是含有隐变量的概率模型参数的极大似然估计法。

EM算法的思路是使用启发式的迭代方法,既然我们无法直接求出模型分布参数,那么我们可以先猜想隐含数据(EM算法的E步),接着基于观察数据和猜测的隐含数据一起来极大化对数似然,求解我们的模型参数(EM算法的M步)。由于我们之前的隐藏数据是猜测的,所以此时得到的模型参数一般还不是我们想要的结果。不过没关系,我们基于当前得到的模型参数,继续猜测隐含数据(EM算法的E步),然后继续极大化对数似然,求解我们的模型参数(EM算法的M步)。以此类推,不断的迭代下去,直到模型分布参数基本无变化,算法收敛,找到合适的模型参数。

EM算法的推导

假设我们面对一个含有隐变量的概率模型,目标是极大化观测数据$Y$关于参数$\theta$的对数似然函数,即极大化:

EM算法是通过迭代逐步近似极大化$L(\theta)$的。假设在第$i$次迭代后$\theta$的估计值是$\theta^{(i)}$。我们希望新的估计值$\theta$能使$L(\theta)$增加,即$L(\theta) > L(\theta^{(i)})$,并逐步达到极大值。为此,考虑两者的差:

利用琴生不等式,计算其下界:

即函数$B(\theta, \theta^{(i)})$是$L(\theta)$的一个下界,且易得$L(\theta^{(i)}) = B(\theta^{(i)}, \theta^{(i)})$,因此,任何可以使$B(\theta, \theta^{(i)})$增大的$\theta$,也可以使$L(\theta)$增大。为了使$L(\theta)$尽可能怎增大,选择$\theta^{(i)}$时$B(\theta, \theta^{(i)})$达到极大,即

下面求$\theta^{i+1}$的表达式:

其中,$ Q\left(\theta, \theta^{(i)}\right) =\sum_{Z} \log P(Y, Z | \theta) P\left(Z | Y, \theta^{(i)}\right) $

琴声不等式:

EM算法的流程

由上面的叙述我们可以给出EM算法的流程

输入:观测变量数据Y,隐变量数据Z,联合分布$P(Y, Z | \theta)$,条件分布$P(Z | Y , \theta)$;

输出:模型参数$\theta$

(1)选择参数的初值$\theta^{(0)}$,开始迭代;

(2)E步:记$\theta^{(i)}$为第$i$次迭代参数$\theta$的估计值,在第$i+1$次迭代的E步,计算

​ 这里,$P(Z|Y, \theta^{(i)})$是在给定观测数据Y和当前的参数估计$\theta^{(i)}$下隐变量数据Z的条件概率分布;

​ 这里的Q函数是完全数据的对数似然函数$logP(Y, Z | \theta)$关于在给定预测数据$Y$和当前参数$\theta^{(i)}$下对未观测数据$Z$的条件概率分布$P(Z | Y, \theta^{(i)})$的期望

(3)M步:求使$Q(\theta, \theta^{(i)})$极大化的$\theta$,确定第$i+1$迭代次的参数的估计值$\theta^{(i+1)}$

(4)重复第2步和第3步,直到收敛。

关于EM算法的几点说明:

  • 参数的初值可以任意选择,但需注意EM算法对初值是敏感的。
  • 每次迭代实际在求Q函数及其极大
  • 迭代停止的条件一般是Q函数不再增长或者增长很小
  • EM算法不能保证找到全局最优

可以证明EM算法是收敛的,详细过程可以查看李航-统计学习方法。

对于回归问题,最常用的损失函数是平方损失函数:

平方损失函数是光滑函数,能够用梯度下降法进行优化。然而,当预测值距离真实值越远时,平方损失函数的惩罚力度越大,因此它对异常点比较敏感。为了解决该问题,可以采用绝对损失函数:

绝对损失函数相当于是在做中值回归,相比做均值回归的平方损失函数,绝对损失函数对异常点更鲁棒一些。

FAQ

无约束优化问题的优化方法有哪些?

  • 直接法,就是能够直接给出优化问题最优解的方法。但是需要目标函数满足两个条件:

    1. $L(\cdot)$是凸函数
    2. $\nabla L\left(\theta^{*}\right)=0$ 有闭式解

    这两个条件限制了它的应用范围,因此,在很多实际问题中,我们往往采用迭代法。

  • ​迭代法就是迭代地修正对最优解的估计。迭代法又可以分为一阶法(梯度下降法)和二阶法(牛顿法和拟牛顿法)两类。二阶法的收敛速度一般要远快于一阶法,但是在高维情况下,$Hessian$矩阵求逆的计算复杂度很大,而且当目标函数非凸时,二阶法有可能会收敛到鞍点(Saddle Point)。

随机梯度下降法有什么缺点?

随机梯度下降法则采样单个样本来估计的当前梯度,这样做的好处是计算速度快,内存开销小,但是由于每步接受的信息量有限,随机梯度下降法对梯度的估计常常出现偏差,造成目标函数曲线收敛得很不稳定,伴有剧烈波动,有时甚至出现不收敛的情况。

特别是对于山谷和鞍点两类地形来说,在山谷地形中,准确的梯度方向是沿山道向下,稍有偏离就会撞向山壁,而粗糙的梯度估计使得它在两山壁间来回反弹震荡,不能沿山道方向迅速下降,导致收敛不稳定和收敛速度慢。在鞍点处,随机梯度下降法会走入一片平坦之地$($此时离最低点还很远,故也称plateau)。随机梯度下降法无法准确察觉出梯度的微小变化,结果就停滞下来。

针对随机梯度下降法的缺点,目前有哪些优化的变种方法?

随机梯度下降对参数的更新方式表示为:

其中,当前估计的负梯度$-g_t$表示步子的方向,学习速率$\eta$控制步幅。改造的随机梯度下降法仍然基于这个公式。

动量(Momentum)方法

为了解决随机梯度下降法山谷震荡和鞍点停滞的问题,动量方法修改模型参数的迭代公式为:

具体地说,前进步伐$-v_t$由两部分组成,一是学习速率$\eta$乘以当前估计的梯度$g_t$, 二是带衰减的前一次步伐$v_{t-1}$。 这里,惯性就体现在对前一次步伐信息的重利用上。

与随机梯度下降相比,动量方法的收敛速度更快,收敛曲线也更稳定。如下图所示:

AdaGrad方法

AdaGrad为随机梯度下降法增加了环境感知这个优点。随机梯度下降法对环境的感知是指在参数空间中,根据不同参数的一些经验性判断,自适应地确定参数的学习速率,不同参数的更新步幅是不同的。对不同的参数使用不同的更新步幅能够帮助我们利用好数据的分布信息。例如,在文本处理中训练词嵌入模型的参数时,有的词或词组频繁出现,有的词或词组则极少出现。数据的稀疏性导致相应参数的梯度的稀疏性,不频繁出现的词或词组的参数的梯度在大多数情况下为零,从而这些参数被更新的频率很低。在应用中,我们希望更新频率低的参数可以拥有较大的更新步幅,而更新频率高的参数的步幅可以减小。

AdaGrad方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性,取值越小表明越稀疏,具体的更新公式表示为

其中,$\theta_{t+1, i}$表示$t+1$时刻的参数向量$\theta_{t+1}$的第$i$个参数,$g_{k,i}$表示$k$时刻的梯度向量$g_k$的第$i$个维度。分母中求和的形式实现了退火过程,这是很多优化技术中常见的策略,意味着随着时间推移,学习速率将会越来越小,从而保证了算法的最终收敛。

RMSProp方法

AdaGrad方法采用所有历史梯度平方和的平方根做分母,分母随时间单调递 增,产生的自适应学习速率随时间衰减的速度过于激进。

针对这个问题,AdaDelta 和RMSProp采用指数衰退平均的计算方法,用过往梯度的均值代替它们的求和。

ADam方法

$Adam$方法将惯性保持和环境感知这两个优点集于一身。一方面,$Adam$记录梯度的一阶矩(first moment),即过往梯度与当前梯度的平均,这体现了惯性保持;另一方面,$Adam$还记录梯度的二阶矩(second moment),即过往梯度平方与当前梯度平方的平均,这类似$AdaGrad$方法,体现了环境感知能力,为不同参数产一阶矩和二阶矩采用类似于滑动窗口内求平均的思想进行融合,即当前梯度和近一段时间内梯度的平均值,时间久远的梯度对当前平均值的贡献呈指数衰减(exponential decay average)。具体来说,一阶矩和二阶矩采用指数衰退平均技术,计算公式为:

其中,$\beta_1$, $\beta_2$为衰减系数,$m_t$是一阶矩,$v_t$是二阶矩。

Adam的更新公式为

其中,