作者：韩信子@ShowMeAI
教程地址：http://www.showmeai.tech/tutorials/83
本文地址：http://www.showmeai.tech/article-detail/165
申明：版权所有，转载请分割平台与作者并注明出处

1.最优化实践（Optimality Theory）

咱们在做事过程中，会心愿以最小的代价获得最大的收益。在解决一些工程问题时，人们常会遇到多种因素交错在一起与决策指标相互影响的状况；咱们会应用最优化数学实践来应答这一挑战，而大家理解的线性规划也是最早的最优化办法之一。

李航博士的《统计学习办法》将机器学习总结为：机器学习 = 模型 + 策略 + 算法。而公式中的算法指的就是优化算法。大家在算法求职面试过程中，在我的项目模型成果调优过程中，都常常会遇到优化算法，它是学习AI必备的数学知识。

2.最优化问题的数学形容

最优化的根本数学模型如下公式所示：

$$\begin{array}{ll}\min & f(\mathbf{x}) \\\text { s.t. } & h_{i}(\mathbf{x})=0 \\& g_{j}(\mathbf{x}) \leqslant 0\end{array}$$

它有三个基本要素，即：

设计变量：$ \bold{x} $是一个实数域范畴内的$ n $维向量，被称为决策变量或问题的解；
指标函数：$ f(x) $为指标函数；
约束条件：$ h_{i} \left( x \right) =0 $称为等式束缚，$ g_{j} \left( x \right) \leq 0 $为不等式束缚，$ i,j=0,1,2,\dots $

3.凸集与凸集拆散定理

1）凸集（Convex Set）

实数域$ R $上（或复数$ C $上）的向量空间中，如果汇合$ S $中任两点的连线上的点都在$ S $内，则称汇合$ S $为凸集。

设汇合$ S\subset R^{n} $，若对于任意两点$ x, y \in S $，及实数$ \lambda(0 \leq \lambda \leq 1) $都有：$ \lambda x+(1-\lambda) y \in S $则称汇合$ \mathrm{S} $为凸集。

2）超平面和半空间

实际上，二维空间的超平面就是一条线（能够使曲线），三维空间的超平面就是一个面（能够是曲面）。其数学表达式如下：

超平面：

$$H=\left\{x \in R^{n} \mid a_{1}+a_{2}+\ldots+a_{n}=b\right\}$$

半空间：

$$H^{+}=\left\{x \in R^{n} \mid a_{1}+a_{2}+\ldots+a_{n} \geq b\right\}$$

3）凸集拆散定理（Hyperplane Separation Theorem）

所谓两个凸集拆散，直观地看是指两个凸汇合没有穿插和重合的局部，因而能够用一张超平面将两者隔在两边，如图所示。

4）凸函数（Convex Function）

凸函数就是一个定义域在某个向量空间的凸子集$ C $上的实值函数。

数学定义为：对于函数$ f(x) $，如果其定义域$ C $是凸的，且对于

$$∀x_{1},x_{2}∈C,0\leq t \leq 1$$

有：$ f\left( t x_{1}+\left( 1- t \right) x_{2} \right) \leq t f\left( x_{1} \right) +\left( 1- t \right) f\left( x_{2} \right) $，则$ f(x) $是凸函数。

注：如果一个函数是凸函数，则其部分最长处就是它的全局最长处。这个性质在机器学习算法优化中有很重要的利用，因为机器学习模型最初就是在求某个函数的全局最长处，一旦证实该函数（机器学习外面叫“损失函数”）是凸函数，那相当于咱们只用求它的部分最长处了。

4.梯度降落算法（Gradient Descent Algorithm）

1）背景

计算机在使用迭代法做数值计算（比方求解某个方程组的解）时，只有误差可能收敛，计算机最初通过肯定次数的迭代后是能够给出一个跟实在解很靠近的后果的。

其中有一个十分外围的问题，如果咱们失去的指标函数是非线性的状况下，依照哪个方向迭代求解误差的收敛速度会最快呢？答案就是沿梯度方向。

这就引入了咱们的梯度降落法。

2）梯度降落法

在多元微分学中，梯度就是函数的导数方向。梯度法是求解无约束多元函数极值最早的数值办法，很多机器学习的罕用算法都是以它作为算法框架，进行改良而导出更为简单的优化办法。

在求解指标函数$ f(x) $的最小值时，为求得指标函数的一个凸函数，在最优化办法中被示意为:

$$\min f(x)$$

依据导数的定义，函数$ f(x) $的导函数就是指标函数在$ x $上的变化率。在多元的状况下，指标函数$ f(x, y, z) $在某点的梯度$ \operatorname{grad}f(x, y, z)=\left(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z}\right) $是一个由各个重量的偏导数形成的向量，负梯度方向是$ f(x, y, z) $减小最快的方向。

如上图所示，当需要求$ f(x) $的最小值时（机器学习中的$ f(x) $个别就是损失函数，而咱们的指标就是心愿损失函数最小化），咱们就能够先任意选取一个函数的初始点$ x_{0} $（三维状况就是$ \left(x_{0}, y_{0}, z_{0}\right) $），让其沿着图中红色箭头（负梯度方向）走，顺次到$ x_{1}, x_{2}, \ldots, x_{n} $（迭代n次）这样可最快达到极小值点。

3）梯度降落法的过程

输出：指标函数$ f(x) $，梯度函数$ g(x)=\operatorname{grad} f(x) $，计算精度$ \varepsilon $。

输入：$ f(x) $的极小值点$ x^{*} $

1、任取取初始值$ x_{0} $，置$ k=0 $；
2、计算$ f\left(x_{k}\right) $；
3、计算梯度$ g_{k}=\operatorname{grad} f\left(x_{k}\right) $，当$ \left|g_{k}\right|<\varepsilon $时进行迭代，令$ x^{*}=x_{k} $；
4、否则令$ P_{k}=-g_{k} $，求$ \lambda_{k} $使$ f\left(x_{k+1}\right)=\min f\left(x_{k}+\lambda_{k} P_{k}\right) $；
5、置$ x_{k+1}=x_{k}+\lambda_{k} P_{k} $，计算$ f\left(x_{k+1}\right) $，当$ \left|f\left(x_{k+1}\right)-f\left(x_{k}\right)\right|<\varepsilon $或$ \left|x_{k+1}-x_{k}\right|<\varepsilon $时，进行迭代，令$ x^{*}=x_{k+1} $；
6、否则，置$ k=k+1 $，转3。

5.随机梯度降落算法（Stochastic Gradient Descent, SGD）

在梯度降落法的迭代中，除了梯度值自身的影响外，另外一个很重要的参数是每一次取的步长，而且这个参数的抉择十分重要：

步长值获得越大，收敛速度就会越快，然而带来的可能结果就是容易越过函数的最长处，导致发散；
步长取太小，算法的收敛速度又会明显降低。

咱们心愿找到一种比拟好的办法可能均衡步长。

随机梯度降落法引进了随机样本抽取形式，并提供了一种动静步长取值策略。目标就是又要优化精度，又要满足收敛速度。

也就是说，下面的批量梯度降落法每次迭代时都会计算训练集中所有的数据，而随机梯度降落法每次迭代只是随机取了训练集中的一部分样本数据进行梯度计算，这样做最大的益处是能够防止有时候陷入部分极小值的状况（因为批量梯度降落法每次都应用全副数据，一旦到了某个部分极小值点可能就进行更新了；而随机梯度法因为每次都是随机取局部数据，所以就算部分极小值点，在下一步也还是能够跳出）。

两者的关系能够这样了解：随机梯度降落办法以损失很小的一部分精确度和减少肯定数量的迭代次数为代价，换取了总体的优化效率的晋升。减少的迭代次数远远小于样本的数量。

6.牛顿法（Newton’s Method）

1）牛顿法介绍

牛顿法也是求解无约束最优化问题罕用的办法，最大的长处是收敛速度快。从实质下来看，牛顿法是二阶收敛，梯度降落是一阶收敛，所以牛顿法就更快。

艰深地说，比方你想找一条最短的门路走到一个盆地的最底部。梯度降落法每次只从你以后所处地位选一个坡度最大的方向走一步；牛顿法在抉择方向时，不仅会思考坡度是否够大，还会思考你走了一步之后，坡度是否会变得更大。所以，能够说牛顿法比梯度降落法看得更远一点，能更快地走到最底部。

或者从几何上说，牛顿法就是用一个二次曲面去拟合你以后所处地位的部分曲面，而梯度降落法是用一个立体去拟合以后的部分曲面，通常状况下，二次曲面的拟合会比立体更好，所以牛顿法抉择的降落门路会更合乎实在的最优降落门路。

2）牛顿法的推导

将指标函数$ f(x) $在$ x_{k} $处进行二阶泰勒开展，可得：

$ f(x)=f\left(x_{k}\right)+f^{\prime}\left(x_{k}\right)\left(x-x_{k}\right)+\frac{1}{2} f^{\prime \prime}\left(x_{k}\right)\left(x-x_{k}\right)^{2} $

指标函数$ f(x) $有极值的必要条件，是在极值点处一阶导数为0，即：$ f^{\prime}(x)=0 $
所以，对下面的展开式两边同时求导（留神$ x $才是变量，$ x_{k} $是常量$ \Rightarrow $ $ f^{\prime}\left(x_{k}\right) $，$ f^{\prime \prime}\left(x_{k}\right) $都是常量)，并令$ f^{\prime}(x)=0 $可得:$ f^{\prime}\left(x_{k}\right)+f^{\prime \prime}\left(x_{k}\right)\left(x-x_{k}\right)=0 $
即:$ x=x_{k}-\frac{f^{\prime}\left(x_{k}\right)}{f^{\prime \prime}\left(x_{k}\right)} $
于是能够结构如下的迭代公式:$ x_{k+1}=x_{k}-\frac{f^{\prime}\left(x_{k}\right)}{f^{\prime \prime}\left(x_{k}\right)} $
这样，就能够利用该迭代式顺次产生的序列
$$ \left\{x_{1}, x_{2}, \ldots, x_{k}\right\} $$
才逐步迫近$ f(x) $的极小值点了。

牛顿法的迭代如图：

下面探讨的是2维状况，高维状况的牛顿迭代公式是：

$$\mathbf{x}_{n+1}=\mathbf{x}_{n}-\left[H f\left(\mathbf{x}_{n}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{n}\right), n \geq 0$$

$ \nabla f $是的梯度，即：
$$\nabla f=\left[\begin{array}{c}\frac{\partial f}{\partial x_{1}} \\\frac{\partial f}{\partial x_{2}} \\\vdots \\\frac{\partial f}{\partial x_{N}}\end{array}\right]$$
$ H $是Hessen矩阵，即：
$$H(f)=\left[\begin{array}{cccc}\frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\\frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\\vdots & \vdots & \ddots & \vdots \\\frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{n}^{2}}\end{array}\right]$$

3）牛顿法的过程

1、给定初值$ x_{0} $和精度间值$ \varepsilon $，并令$ k=0 $；
2、计算$ x_{k} $和$ H_{k} $；
3、若$ \left|g_{k}\right|<\varepsilon $则进行迭代；否则确定搜寻方向:$ d_{k}=-H_{k}^{-1} \cdot g_{k} $；
4、计算新的迭代点:$ x_{k+1}=x_{k}+d_{k} $}；
5、令$ k=k+1 $，转至2。

7.阻尼牛顿法（ Damped Newton’s Method ）

1）背景

牛顿法的迭代公式中没有步长因子，是定步长迭代。对于非二次型指标函数，有时候会呈现的状况，这表明，原始牛顿法不能保障函数值稳固的降落。在重大的状况下甚至会造成序列发散而导致计算失败。

为打消这一弊病，人们又提出阻尼牛顿法。阻尼牛顿法每次迭代的方向依然是$ x_{k} $，但每次迭代会沿此方向做一维搜寻，寻求最优的步长因子$ \lambda_{k} $，即：

$$\lambda_{k}=\operatorname{minf}\left(x_{k}+\lambda d_{k}\right)$$

2）阻尼牛顿法算法过程

1、给定初值$ x_{0} $和精度阈值$ \varepsilon $，并令$ k=0 $；
2、计算$ g_{k} $（$ f(x) $在$ x_{k} $处的梯度值）和$ H_{k} $；
3、若$ \left|g_{k}\right|<\varepsilon $则进行迭代；否则确定搜寻方向:$ d_{k}=-H_{k}^{-1} \cdot g_{k} $；
4、利用$ d_{k}=-H_{k}^{-1} \cdot g_{k} $失去步长$ \lambda_{k} $，并令$ x_{k+1}=x_{k}+\lambda_{k} d_{k} $；
5、令$ k=k+1 $，转至2。

8.拟牛顿法（Quasi-Newton Method）

1）概述

因为牛顿法每一步都要求解指标函数的Hessen矩阵的逆矩阵，计算量比拟大（求矩阵的逆运算量比拟大），因而提出一种改良办法，即通过正定矩阵近似代替Hessen矩阵的逆矩阵，简化这一计算过程，改良后的办法称为拟牛顿法。

2）拟牛顿法的推导

先将指标函数在$ x_{k+1} $处开展：$ f(x)=f\left(x_{k+1}\right)+f^{\prime}\left(x_{k+1}\right)\left(x-x_{k+1}\right)+\frac{1}{2} f^{\prime \prime}\left(x_{k+1}\right)\left(x-x_{k+1}\right)^{2} $

两边同时取梯度，得:$ f^{\prime}(x)=f^{\prime}\left(x_{k+1}\right)+f^{\prime \prime}\left(x_{k+1}\right)\left(x-x_{k+1}\right) $
取上式中的$ x=x_{k} $，得:$ f^{\prime}\left(x_{k}\right)=f^{\prime}\left(x_{k+1}\right)+f^{\prime \prime}\left(x_{k+1}\right)\left(x-x_{k+1}\right) $
即：$ g_{k+1}-g_{k}=H_{k+1} \cdot\left(x_{k+1}-x_{k}\right) $
可得：$ H_{k}^{-1} \cdot\left(g_{k+1}-g_{k}\right)=x_{k+1}-x_{k} $

下面这个式子称为“拟牛顿条件"，由它来对Hessen矩阵做束缚。

ShowMeAI相干文章举荐

图解线性代数与矩阵论
图解概率与统计
图解信息论
图解微积分与最优化

ShowMeAI系列教程举荐

图解Python编程：从入门到精通系列教程
图解数据分析：从入门到精通系列教程
图解AI数学根底：从入门到精通系列教程
图解大数据技术：从入门到精通系列教程