数据科学、数据分析、人工智能必备知识汇总-----最优化-----持续更新

1. 基本概念

机器学习中，我们往往要求损失函数loss，loss当然越小越好。因为这里是数学，$f(x)$其实就是我们编写机器学习算法时的$\theta$或者说$w权重$

最优化问题就是求 $f(x),x\in \mathbb{R}$的极大值或者极小值

---

我们往往求极小值，在这里$x$是优化变量，就是自变量，$f(x)$称为目标函数，可能还带有约束条件，有些优化问题既有等式约束，又有不等式约束

---

$\{\begin{array}{ll}\max f(x)\iff \min f(x)& 求最大和求最小，是可以互相转换的（求最大加负号，变为求最小）\\ & \\ g_i(x)=0& i=\mathrm{1...}m，等式约束条件可能有多个（i个）\\ & \\ h_j(x)\le 0& j=\mathrm{1...}n，不等式约束条件可能有i个\end{array}$

---

满足这种约束条件，并且还在 $f(x)$定义域之内的那些$X$构成的集合叫可行域 $D$

初中我们就学求极值的问题了，比如二次函数抛物线的顶点就是极大值或者极小值,高中我们也会有求极值的题目,算一个非常复杂的函数的极值,借用初等数学一些的技巧来完成的

---

而真正的飞跃是发生在大学里面,微积分这门课为求解极值提供了一个统一的方法，就是找它导数等于0的点，如果是多元函数的话,我们说它的梯度等于0,我们去解方程组就可以了，在机器学习里面我们遇到的几乎所有的函数都是可导的。光滑即可导$f^{{}^{\prime }}(x)=0$

局部极小值(local minimum)，任何在 $x_0$的邻域存在$f(x)\ge f(x_0),\forall x\in \delta (x_0)$（$\forall$表示任意；$\delta 表示邻域$）

---

---

通过大量实践发现在高维度的优化问题中，局部最小值和全局最小值通常没有大大的区别 甚至在有些情况下比局部最小值有更好的归纳能力(泛化能力)。

2. 为什么要迭代求解

前面说了求极值就是导数或梯度等于0，找到疑似的极值，就是驻点

---

$驻点：\{\begin{array}{l}{f}^{{}^{\prime }}(x)=0\\ \nabla f(x)=0\end{array}$

---

有了微积分里面这样的手段，只要函数可导，我们求解不就行了?但是很多时候去求方程等于0或方程组等于0的根并不是那么容易，比如

---

$f(x,y)=x^3-2x^2+e^{xy}-y^3+10y^2+100sin(xy)$

---

分别求对 X和Y的偏导数后，我们求一阶导数为0的点也一样有些复杂

---

$\{\begin{array}{l}3x^2-4x+e^{xy}\cdot y+100cos(xy)\cdot y=0\\ \\ x\cdot e^{xy}-e{y}^2+20y+xcos(xy)=0\end{array}$

---

对于求下面的一些函数的方程叫做超越方程，别说超越方程了，对于5次或以上的代数方程它都没有求根公式了，所以这个思路（找导数为0的点）看上去很美,但是实际上是行不通的,我们得想其它的办法

---

$e^x、\ln x、\sin x、\arcsin x$

近似求解，我们先给个初始的值，看看它是不是极值点，当然得满足等式或者不等式约束.

---

如果不是,我们想办法再前进一步,只要我们的$x_n$ 越来越接近我们的极值点,那这个问题不就解决了嘛

---

$x_0\to x_1\to x_2\to ...\to x_n$

---

我们要构造一个序列，满足这样一个极限，当$k趋近于+\infty$的时候，$f(x_k)$这点的梯度值极限趋近于0的话，那我们就找到了函数的驻点

---

$\underset{k\to +\infty }{\lim }\nabla f(x_k)=0$

---

由此我们要解决的核心问题就变成了,怎么从当前一个点移动到下一个点上面去,也就是怎么从$x_k$到$x_{k+1}$

---

迭代法是我们计算数学中经常采用的一种方法，它不单单可以求极值，还可以用来求方程组的解，包括线性方程，非线性方程，一个矩阵的特征值等等

---

$x_{k+1}=h(x_k)$

---

---

上图我们最终找到了$\nabla f(X)=0$，注意这里是数学解释，对应到机器学习中x就是我们的$\theta$参数

3. 梯度下降法

沿用了我们的迭代求解的思路

数值优化算法，是求近似解，而不是理论上面的精确解

---

$x_{k+1}=x_k-\gamma \nabla f(x_k)$：$k是时刻，\gamma 是步长，f是损失函数$

---

下面我们来推导这个公式，需要用到多元函数的泰勒展开公式$f(x)=f(x_k)+[\nabla f(x_k){]}^T(x-x_k)+\frac{1}{2}[x-x_k{]}^{T}H(x_k)[x-x_k]$最后加上一个高阶无穷小$O^n$

---

$f(x)=f(x_0)+[\nabla f(x_0){]}^T(x-x_0)+o(x-x_0)$

---

如果我们忽略高阶无穷小，也就是说$x$它是属于 $x_0$ 的$\delta$邻域里面的话,那么等号就会变成$约等于$，那么我们把 $f(x_0)$放到等号左边

---

$f(x)-f(x_0)\approx [\nabla f(x_0){]}^T(x-x_0)$

---

$X^{T}Y=\Vert X\Vert \cdot \Vert Y\Vert \cdot cos\theta ，其中\Vert X\Vert \ge 0$

---

这时要想下降的更快，就要让等式右边得到最小值，即当 cos0=-1,下降的幅度最大!

---

单位向量代表的是方向，长度为 1的向量就是模为 1的向量称为单位向量。

---

$\Vert \vec{v}\Vert =\sqrt{v_1^2+v_2^2+\cdots +v_n^2}$

---

向量乘以标量不会改变它的方向，只会改变它的幅值。这就是缩放向量的方法。所以一个向量可以表示为一个标量乘以一个单位向量。为了使得下降幅度最大，那么向量$(x-x_0)$的方向和梯度的方向相反:

---

$v=-\frac{\nabla f({\theta }_0)}{\Vert \nabla f({\theta }_0)\Vert }，\frac{梯度向量}{向量的模}$得到单位向量，就指明了梯度向量的方向，加个负号就获得了反方向，所以$(x-x_0)$最好是梯度向量的反方向

---

$\theta ={\theta }_0-\eta \frac{\nabla f({\theta }_0)}{\Vert \nabla f({\theta }_0)\Vert }$:上面$v=(x-x_0)，把x记为\theta$，化简一下就得到这个式子了，$因为方向不是标量$,给它乘一个$\eta$

---

分母是个标量，可以并入到$\eta$中，简化为:$\theta ={\theta }_0-\eta \nabla ({\theta }_0)$

---

需要注意的是,$x$和 $x_0$ 离的充分近,也就是在它的$\delta$邻域里面,才能忽略掉泰勒展开里面的一次以上的项，否则就不能忽略它了，它就不是高阶无穷小了，约等于的条件就不成立了所以$\eta$步长不能够太大，由此我们就得到了梯度下降法的公式

---

$\{\begin{array}{ll}x=x_0& \\ & \\ for(...)& \\ & \\ & x_{k+1}=x_k-\gamma \nabla f(x_k)\end{array}$

---

实现细节问题

---

初始值的设定，随机或者设定满足约束条件的就 OKAY

---

步长的设定，一个充分接近于0的数就可以了，也可以动态的调整

---

循环终止的判定，max iteration最大迭代，上一次减下一次的 $f(x)$

3. 牛顿法

将梯度下降法中的$\gamma \nabla f(x_k)$更换为$H_k^{-1}{g}_k$，也就是换成了hessian矩阵

数据量不是特别大的情况下，牛顿法确实比梯度下降，下降的更快，因为牛顿法是二元逼近，但是到了BD神经网络数据量特别大时，牛顿法因为需要计算hessian矩阵，计算量也特别大，效率反而不如梯度下降法

$x_{k+1}=x_k-H_k^{-1}{g}_k$

---

它是基于这样一个思想，我们不是要找梯度等于$0$的点嘛，迭代$x$让梯度值尽可能等于 $0$

---

$\nabla f(X)=0$

---

$x_0\to x_1\to x_2\to \cdots \to x_n$

---

推导牛顿法的公式，就是多元函数的泰勒展开公式，这里我们把它展开成二次以上的项$f(x)=f(x_k)+[\nabla f(x_k){]}^T(x-x_k)+\frac{1}{2}[x-x_k{]}^{T}H(x_k)[x-x_k]+o(x-x_0)$

---

同样当$x$在 $x_0$ 的$\delta$邻域里面的话，我们可以把后面的高阶无穷小忽略掉，从而建立一个近似的等式

---

不是要找梯度等于$0$的$x$嘛,我们现在用二次函数来代替原来的函数 $f(x)$在 $x_0$ 处用一个抛物线来近似它,但是离 $x_0$ 越远误差会越大,离 $x_0$ 越近误差会越小

---

1. 左边牛顿法，红色曲线是在x0处展开的二阶泰勒，可见依然需要多次迭代，因为红色曲线是近似的，需要让红色曲线不断逼近真正的最小点
2. 右边梯度下降法，红色切线，是在x0处展开的一阶泰勒

---

如果是二次函数的话，我们找它梯度等于0的点是非常好找的，基于约等于的式子，两边同时求导，取梯度的话，就是下面

---

$f(x)\approx f(x_0)+[\nabla f(x_0){]}^T(x-x_0)+\frac{1}{2}[x-x_0{]}^{T}H(x_0)[x-x_0]$

$\{\begin{array}{l}\because 已知公式(w^{T}x{)}^{{}^{\prime }}=w,(x^{T}Ax{)}^{{}^{\prime }}=(A+A^T)x\\ \\ \therefore \nabla f(x)\approx \nabla f(x_0)+H(x_0)(x-x_0)=0\end{array}$

---

下面就可以解一次方程，如果 hessian 矩阵可逆，就可以两边乘上 H 的逆矩阵

---

$\{\begin{array}{l}g+H(x-x_0)\\ x-x_0=-H^{-1}g\end{array}$

---

前提是可逆的，对比一下和梯度下降法的公式,注意一下 $H$和 $q$ 都是 $x=x_0$ 点处取得的$x_{k+1}=x_k-\eta \cdot g_k$

那我们去求解方程组，那不是一次就可以求得梯度等于0的点x了嘛?

---

但是因为我们忽略了后面的高阶无穷小，所以我们只是近似的找到了梯度等于0的点，但是它并没有真正找到，所以我们下次要继续去用这个公式去迭代。

---

$x_{k+1}=x_k-\eta \cdot H_k^{-1}\cdot g_k$

实现细节问题

---

1. 初始值的设定，随机或者设定满足约束条件的就 OKAY
2. 步长的设定，$\eta$步长的设定和梯度下降法不同，不是迭代就一定使得 $f(x)$下降，所以设置不好就有可能不收敛，求不到最优解的值

牛顿法一般会用 line search 的技术，就是选择些$10^{-4}10^{-6}$等等，看看哪个步长使得$f(x_{k+1})$更小就反过来选择哪个作为步长

3. 循环里面写$x_{k+1}=x_k-\eta \cdot H_k^{-1}\cdot g_k$
4. 循环终止的判定，max iteration，上一次减下一次的 $f(x)$

如果我们的$x$是二次函数的话，牛顿法一步就可以收敛，前提是步长不做设置，等于1的时候就可以了,这是因为如果原函数 $f(x)$是二次函数的话,泰勒展开里面就不是约等于，而是直接等于

---

在工程里面我们不是直接求解 $hessian$ 矩阵的逆矩阵,而是求一个方程组 $AX=b$,可以用共轭梯度法

---

梯度下降法只用到了一阶导数的信息,牛顿法既用到了一阶导数的信息,也用到了二阶导数的信息。

---

梯度下降法是用线性函数来代替目标函数，牛顿法是用二次函数来代替目标函数所以说牛顿法的收敛速度是更快的。

---

但是牛顿法也有它的局限,hessian 矩阵不一定可逆,第二个即使存在,我们去解一个线性方程组时，当 hessian 矩阵规模很大,解线性方程组是非常耗时的,因此出现了一种改进的算法叫拟牛顿法

4. 坐标下降法

分治法的思想

---

$\min f(x),x=(x_1,x_2,...,x_n)$

---

它的思想是按住其它的不动，只优化其中一个比如$x_1$，那就把多元函数求极值问题变成了一元函数求极值问题,这样优化的难度就小了很多

---

紧接着我们把其它的按住不动,再优化$x_2$,一直到$x_n$,完了之后再回来优化$x_1$,至于一个变量怎么解,可以用牛顿法或者公式来求解

---

观察具体问题的形式

---

SVM 中的 SMO 算法就是把其中两个拿出来优化，其它的固定不动

---

liblinear 库也大量的使用坐标下降法来求解的

---

我们把所有的从$x_1$ $x_2$到$x_n$,优化一遍 ,就好比梯度下降迭代一次 ,这种方法它也有很大好处，就是计算的工作量小很多

5. 数值优化算法面临的问题

前面梯度下降法，还有牛顿法求极值的依据都是$\nabla f(x_k)=0$，而前面我们也说了函数在某一点的导数或梯度等于$0$就是驻点，它只是函数取得极值的必要条件，不是充分条件，也就是说无法推导出

---

$\nabla f(x_k)=0\Rightarrow x_k\min$：注意这个不成立，不要当成公式。也就是说梯度下降法这些，虽然找到了导数为0的点，但不能确定这个点就是极值点。我们前面微积分也讲过这个问题

所有我们前面介绍的数值优化算法，都会面临两个问题

---

局部极值问题，理论上我们要求全局最优解的话,我们要把所有极小值找出来,你可能要不断的去设置不同的初始迭代点,反复的求解让它收敛到不同的局部最小值，然后来比较谁最小来找到一个全局最小值。

---

鞍点问题

---

前面我们说过一元函数$x^3$函数，在坐标为$0$处它是驻点，但是它连局部最小值点都不是，对应多元函数来说，我们称之为鞍点

---

严格定义是，在这一点它的 hessian 矩阵是不定的既不正定也不负定，这样它就即不是极小值的点也不是极大值的点。

所以为了解决这些问题，我们不会直接使用梯度下降法，而是用他们的优化形式，例如神经网络中，基于动量的优化方法（优化梯度下降法）

6. 拉格朗日乘数法

用来求解等式约束下的极值问题的$\{\begin{array}{l}\min f(x)\\ h_i(x)=0,i=1,...,k\end{array}$拉格朗日乘子函数，把对x带约束条件的优化问题，转化为不带约束条件的优化问题

---

$L(x,\alpha )=f(x)+\sum _{i=1}^k{\alpha }_i{h}_i(x)$:将约束条件累加到了一起，并为每项乘了一个拉格朗日乘子$\alpha$

---

下面两个式子是分别对$x$和$\alpha$求梯度，然后去解下面方程组就可以了

---

${\nabla }_{x}f+\sum _{i=1}^k{\alpha }_i{\nabla }_x{h}_i=0$

---

$h_i(x)=0$

7. 凸优化问题

前面我们说过数值优化面临两个问题，一个是局部极值问题,和鞍点问题,我们能不能避免这两个问题呢 ?

---

只要我们对优化问题进行限定就可以，这类问题有两个限定条件

1. 优化变量的可行域必须是凸集
2. 优化函数必须是个凸函数

---

同时满足这两个限定条件的问题,叫做凸优化问题,从而才能说局部极小值就是全局极小值

7.1 凸集

凸集的定义:对于一个点的集合$C$,有 $x,y$ 它都是属于$C$里面的两个点，它们两点的连线中任何一点也是属于集合$C$的

---

$\theta x+(1-\theta )y\in C$

---

$0\le \theta \le 1$

---

典型的凸集

---

欧式空间 $R^n$

---

$x,y\in R^n\Rightarrow \theta x+(1-\theta )y\in R^n$

---

它的意义在于，很多时候可行域就是欧式空间，那肯定是凸集仿射子空间 { x ∈ R n : A x = b } \{ x∈R^n:Ax=b \} {x∈Rn:Ax=b}

---

$x$是$n$维欧式空间里的向量，满足 $Ax=b$ 这个方程组的解，它构成的集合就是仿射子空间

---

$\{\begin{array}{ll}x,y\in C& \\ & \\ A(\theta x+(1-\theta )y)& =\theta Ax+(1-\theta )Ay\\ & \\ & =\theta b+(1-\theta )b\\ & \\ & =b\end{array}$

---

它的意义在于,所有的等式约束构成的集合是凸集,很多时候等式约束就是这样的线性方程,所以一般我们不会构建处非线性的等式约束来。

多面体 { x ∈ R n : A x = b } \{ x∈R^n:Ax=b \} {x∈Rn:Ax=b}

---

线性不等式的解

---

$\{\begin{array}{ll}x,y\in C& \\ & \\ A(\theta x+(1-\theta )y)& =\theta Ax+(1-\theta )Ay\\ & \\ & \le \theta b+(1-\theta )b\\ & \\ & \le b\end{array}$

---

这样中间的点它还是不等式的解,所以说这样一个集合它还是凸集,它的现实意义在于,如果有一组线性不等式约束的话，那它构成的可行域也一定是凸集

---

凸集的交集也是凸集$\bigcap _{i=1}^k{C}_i$

---

如果有$k$ 个集合$C_1,C_2,...,C_k$,它们是凸集,那它们的交集也一定是凸集,它们的并集不是凸集,会有凹的地方了

---

7.2 凸函数

$f(\theta x+(1-\theta )y)<\theta f(x)+(1-\theta )f(y)$

---

---

凸函数在函数上任意找两点,它们的连续就是割线上的值比对应的 $f(x)$的值要大

---

证明函数是凸函数,第一种当然是利用上面定义去证明,也可以利用一阶导数信息,和二阶导数信息去证明

先说对于一元函数来说，怎么用一阶导数来判断是凸函数还是不是凸函数呢?

---

$f(y)\ge f(x)+f^{{}^{\prime }}(x)(y-x)$：x是切线和抛物线相交的点，y是变化的

多元函数$f(y)\ge f(x)+\nabla f(x{)}^T(y-x)$

---

二阶判别法

---

如果是一元函数,那么$f^{{}^{\prime \prime }}(x)\ge 0$就是凸函数

---

多元函数 Hessian 矩阵是半正定的,它就是凸函数，>0 就是严格的凸函数，=0 就是有平的地方，就是有线性变化的地方

比如 $ax+b$ 求二阶的时候就是$=0$.

---

如果每个函数$f_i(x)$都是凸函数 ,那么它们的非负线性组合 $f(x)=\sum _{i=1}^k{w}_i{f}_i(x)如果w_i\ge 0$也是凸函数

7.3 凸优化的性质

凸优化的定义是目标函数是凸函数，可行域是个凸集,如果有这两个限定条件的话,局部最优解一定是全局最优解

下面证明对于凸优化问题，它的局部最优解一定是全局最优解。

---

反证法：假设有一点$x$是局部最小值,但不是全局最小值,那样就存在另外一个点$y$是全局最小值位置，这时 $f(y)<f(x)$

---

---

如果可以证明x的邻域有个点$z$是比$x$的值还小的,$f(z)<f(x)$,那么$x$肯定不是最优解了

---

$z=\theta y+(1-\theta )x$

---

$\theta =\frac{\delta }{2\Vert x-y{\Vert }_2}$:$\delta$是邻域半径；$\Vert x-y{\Vert }_2$是 L2 范数，表示x和y两点之间的距离；把θ带进来证明$z$是在$x$邻域的，也就是小于等于$\delta$的

---

---

根据凸函数的性质，同时 $f(y)<f(x)$，$\theta >0$

---

$f(z)=f(\theta y+(1-\theta )x)\le \theta f(y)+(1-\theta )f(x)=\theta (f(y)-f(x))+f(x)<f(x)$

---

所以这和前面的假设是矛盾的，所以说前面的性质是成立的

7.4 凸优化一般的表述形式

$\min f(x)，x\in C（C是凸集）$

---

$\min f(x)；c_i(x)\le 0,i=1,...,m；h_j(x)=0,j=1,...,k；$由不等式等式约束条件构成的可行域也是凸集

往往我们需要去证明的一些机器学习算法它们都是凸优化问题，比如逻辑回归，SVM，线性回归等,证明它的可行域是凸集,目标函数是凸函数就可以了

---

凸优化规避了局部最小值问题，而且也规避了鞍点问题，f(x)是凸函数，它的 hessian 矩阵是半正定的，当是半正定的也就规避了鞍点问题

8. 拉格朗日对偶

凸优化，非线性规划问题,甚至是运筹学里面的线性规划问题都会涉及这个概念

---

它的意义是把原始问题转化为另外一个问题来求解，但是转化之后的问题要容易求解一点

---

拉格朗日乘数法的扩展，用来解决既带等式约束条件，又带不等式约束条件的一种方法；通过把原问题转换为对偶问题来求解，很多时候对偶问题比原问题更容易求解

---

$\min f(x)；g_i(x)\le 0,i=1,...,m；h_j(x)=0,j=1,...,k；$

---

构建一个广义的拉格朗日函数，所谓广义就是还包括不等式约束条件

---

在下面式子中你会发现对$x$的约束没有了，虽然有个对$\alpha$的约束

---

$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^m{\alpha }_i{g}_i(x)+\sum _j^k{\beta }_j{h}_j(x)$

原始问题

---

$p^{\ast }={\min }_x{\max }_{\alpha ,\beta ,{\alpha }_i\ge 0}L(x,\alpha ,\beta )={\min }_x{\theta }_p(x)$

---

原始问题等价于我们要求解的问题

9. KKT 条件

拉格朗日乘数法的扩展,用来解决既带等式约束条件,又带不等式约束条件的一种理论结果:求解的时候用这个就行了

$\{\begin{array}{ll}\min f(x)& {\nabla }_{x}L(x^{\ast })=0\\ & \\ g_i(x)\le 0i=1,...,q& {\mu }_i\ge 0\\ & \\ h_i(x)=0i=1,...,p& {\mu }_i{g}_i(x^{\ast })=0\\ & \\ 上面是原问题，接下来使用拉格朗日乘数法（对偶）& \\ & \\ L(x,\lambda ,\mu )=f(x)+\sum _j^p{\lambda }_j{h}_j(x)+\sum _{i=1}^q{\mu }_i{g}_i(x)& h_j(x^{\ast })=0\\ & \\ & g_i(x^{\ast })\le 0\end{array}$