SIGAI机器学习第三集 数学知识-2

讲授机器学习相关的高等数学、线性代数、概率论知识

大纲：

最优化中的基本概念
梯度下降法
牛顿法
坐标下降法
数值优化算法面临的问题
拉格朗日乘数法
凸优化问题
凸集
凸函数
凸优化
拉格朗日对偶
KKT条件

最优化中的基本概念：

最优化问题就是求一个函数的极大值或极大值问题，一般f(x)是一个多元函数，x∈Rⁿ，一般把最优化问题表述为求极小值问题。

x称为优化变量，f(x)称为目标函数。

可能对x还有约束条件，一个或多个，等式约束或不等式约束，可能有的既有等式约束又有不等式约束，这样就比较复杂了。

满足约束条件且在f(x)定义域内的x组成的集合叫做可行域D。

局部极小值，全局最小值，极值点的导数或梯度等于零，机器学习中的函数一般都是可导的。

直接求一阶导数为零不就可以解出极值点了吗？但实际上不太可行，方程不好求解，会出现超越方程。如下：

 这时要用到迭代法，不断迭代更新未知量的值去找导数为零的点。

 梯度下降法：

第一种数值优化（求近似解而非理论上的精确解）算法，叫梯度下降法。

推导梯度下降法的迭代公式：

如果x在x₀的δ邻域的话，泰勒展开式中的高阶无穷小项就可以舍去，等式近似成立。

f(x)=f(x₀)+▽^Tf(x₀)(x-x₀)+O(x-x₀)，当x在x₀的δ邻域时f(x)≈f(x₀)+▽^Tf(x₀)(x-x₀)，即f(x)-f(x₀)≈▽^Tf(x₀)(x-x₀)，于是，怎么让f(x)比f(x₀)小逐渐靠近极小值点呢？就让▽^Tf(x₀)(x-x₀)小于零就可以了。怎么做到让它小于零呢？要让▽^Tf(x₀)(x-x₀)小于零，那么▽^Tf(x₀)、(x-x₀)向量的夹角要大于90度，当取(x-x₀)为负梯度方向时，f(x)下降速度最快，即x_k+1=x_k-r▽f(x_k)，这里▽f(x_k)前加一个系数步长r，为了保持x_k+1和x_k离的充分近即x_k+1在x_k的邻域内，才能忽略泰勒展开中一次以上的项，即r要足够小。

实现细节问题：

初始值的设定，x从哪一点开始，尽量选一个开始就接近极值点的点。

步长的选择，r选多少合适，一般是经验值，充分接近于0的正数就可以，有时随着迭代过程动态调整。

迭代终止的判定规则，||▽f(x_k)||≤ε，梯度足够小接近于零的时候退出循环；或者设定迭代次数。

牛顿法：

也是一种数值优化算法，牛顿是物理学家和数学家，牛顿和莱布尼兹一起发明了微积分，是数学历史上的一次飞跃。

目标：找梯度为零的点，即▽f(x)=0，直接解很麻烦，采用某种迭代法向着极值点靠近。

泰勒展开到二次项，f(x)=f(x₀)+▽^Tf(x₀)(x-x₀)+1/2*(x-x₀)^TH(x-x₀)+O((x-x₀)²)，其中H是Hession矩阵，理解为当x在x₀的邻域内时，可以忽略后边的高阶无穷小，在x₀附近可以用一个二次函数来近似代替f(x)函数，离x₀越远函数值误差会越大越近误差越小。

对上式对x求梯度：

▽f(x)≈▽f(x)+H(x-x₀)，令▽f(x)为g，则g+H(x-x₀)=0，就可以把极值点求出来了，x=x₀ - H^-1g（前提是H可逆，H和g都是在x₀这一点取得的），于是得到迭代公式：x_k+1=x_k-H^-1_kg_k，同样的以上等式是在x₀的邻域内才能成立的，所以加上一个系数保证x在x₀的δ邻域内，即x_k+1=x_k - rH^-1_kg_k。

实现细节问题：

初始值的设定，x₀的选择。

步长的选择，比梯度下降法要复杂，因为梯度下降法会保证每次迭代函数值都在降，而牛顿法不能保证每次函数值都下降，所以r的选择比较讲究，选择不好的话可能会不收敛，一般用直线搜索技术确定r（x_k+1=x_k - rH^-1_kg_k，如10^-3、10^-4、...，每次迭代的时候比较r取哪个值时函数值下降的最快就给r取哪个值）。

迭代终止的判定规则，||▽f(x_k)||≤ε。

牛顿法和梯度下降法相比，x迭代式中多了一个H^-1（实际求解时一般不直接求解H^-1，而是求解Ax=b，可以用共轭梯度法），梯度下降法只是依赖于一阶导数信息，而牛顿法它既用了一阶导数信息也用了二阶导数信息，梯度下降法用线性函数近似的代替目标函数，牛顿法用二次函数代替目标函数，所以说牛顿法的收敛速度是更快的，但是牛顿法也有他的局限，H矩阵不一定可逆，不可逆时该方法无效，当变量很多的时候解H矩阵（解Ax=b）是非常耗时间的，由此就产生了一种改进的算法：拟牛顿法。

坐标下降法：

一种数值优化算法，是一种分治法的思想。

假设要优化一个多元的目标函数，自变量x是一个向量，有n个分量。

min f(x)，x=(x₁,x₂,...,x_n)，原理：先固定住很多分量不动，只优化一个分量min_xi f(x)，就把多元函数的极值问题转化为一元函数的极值问题，这样问题求解的难度就小非常多，优化完一个分量之后，再同理优化别的分量，走完一轮后下次迭代同理。一元函数的极值问题可以用牛顿法也可以用公式解，看问题具体的形式了。

数值优化算法面临的问题：

前边的梯度下降法（也有改进型，如adam、anadata）和牛顿法它们求解极值问题的依据都是▽f(x₀)=0，而函数在某点导数等于零，它只是函数取得极值的必要非充分条件，所以他们会面临局部极值问题和鞍点问题，对于极值问题，梯度下降法和牛顿法要把所有的局部极值点都要找出来是非常麻烦的（要设置不同的初始迭代点然后让它收敛到不同的局部极小值点处再比较，这是一个NPC问题），鞍点问题是驻点但非极值点（H矩阵在此点是不定的，既不正定也不负定）。
拉格朗日乘数法：

拉格朗日乘数法是求极值的不是求最值，如果要求最值，要把极值点的函数值和不可导点的函数值还有端点函数值进行比较，求出来的是可能的极值点，因为可能是驻点非极值点。

用于求解带有一组等式约束的极值问题：

min f(x)，h_i(x)=0,i=1,...,p，其中x是优化变量，f(x)是目标函数。构造一个拉格朗日乘子函数，把这样一个带等式约束的问题转化为对x不带约束的优化问题。

拉格朗日乘子函数：，λ_i叫乘子变量，L(x，λ)对x和λ求偏导：

凸优化问题：

数值优化会面临局部最小值问题和鞍点问题，能不能避免这两个问题呢？答案是OK的，只要对优化问题进行限定，就可以避免这两种情况的发生。怎么限定呢？凸优化问题。

凸优化是一种很特殊的优化，有两个约束：

1.问题的可行域D是一个凸集

2.目标函数是一个凸函数

同时满足以上两条的优化问题叫凸优化问题。

凸集：

凸集的定义，对于点的集合C，有点x、y∈C，那么它们连线上的任何一点也是属于集合C的，即θx+(1-θ)y∈C。

典型的凸集：

Rⁿ

仿射子空间{x∈Rⁿ:Ax=b}，就是一组等式组成的约束，他是凸集，一般是线性约束

多面体{x∈Rⁿ:Ax≤b}，即一组线性不等式构成的约束是凸集

凸集的交集还是凸集，多个凸集的并集不是凸集

凸函数：

凸函数的定义：f(θx+(1-θ)y)<θf(x)+(1-θ)f(y)

 凸函数的判定：

①可根据定义判定

②一阶判别法：一元函数f(y)≥f(x)+f^'(x)(y-x)，多元函数f(y)≥f(x)+▽f(x)(y-x)

③二阶判别法：如果是一元函数，f^''(x)≥0可以判断为是凸函数；对于多元函数，它的Hession矩阵半正定可以判断为是凸函数，如果是正定就是一个严格的凸函数（没有平的地方）。

对于凸函数的非负线性组合也是凸函数：

，w_i≥0，对于求解的目标函数如果可以写成几部分之和，如果每个部分都是凸函数，那么加起来还是凸函数。

凸优化：

凸优化的定义是目标函数是一个凸函数且可行域是一个凸集。

如果是凸函数和凸集，那么局部最优解一定是全局最优解。

凸优化一般写成以下形式：

①，无约束条件

②，有约束条件

机器学习算法凸优化问题：SVM、logistic回归、线性回归。证明的思路是，证明可行域是凸集、目标函数是凸函数即可。

凸优化有效规避局部极小值问题和鞍点问题（因为Hession矩阵是半正定的，也就是非不定的，所以不存在不定的点，规避了鞍点问题），证明了一个问题是凸优化问题，也就说明这个问题基本上就得到解决了，无论是用牛顿法、梯度下降法或其他方法，最终都可以得到它的全局最小值点，只是早晚的问题（迭代多少次收敛的问题），收敛是有保证的，所以说凸优化问题在优化问题中占有非常重要的地位。

拉格朗日对偶：

对偶是最优化问题里边非常重要的一块理论和方法。拉格朗日对偶法把原来难以求解的问题转换成另外一个问题来求解，两个问题是等价的，但是另外一个问题更容易求解，这就是它的核心的想法。

原始优化问题：

首先构造一个广义的拉格朗日函数（和拉格朗日乘数法一样的，只是这里是广义的即多了一组不等式约束，不等式约束乘子变量要大于等于零即λ_i≥0）：

 

原问题：

，即先让x不动，求对于v、λ函数的极大值求出v、λ，再求对于x的极小值。

原问题等价于我们要求解的问题，因为，而让x不动求L极大值时，是等式约束值为0，而f(x)视为常数，此时即求的极大值，因为g_i(x)≤0且λ_i≥0，所以的极大值为0，所以求L对v、λ的极大值为f(x)，然后求L的极小值，此时就是求f(x)的极小值，即等价于原始问题的优化。

对于x不属于可行域C，即破坏了约束条件如至少有一个h_i(x)≠0，就让v_i取正无穷或负无穷，使得通过控制v_i使得趋向于正无穷，使得无论x取什么值，L都是趋向于正无穷。即在可行域之内，原始问题和原问题是等价，有相同的最优解；超出可行域之外L都是正无穷，不管怎么操作x都不可能取到原始问题的极小值。

对偶问题：

就是对操作乘子变量和操作x顺序调换一下，

显然弱对偶成立，，d^*是弱对偶问题的最优解，p^*是原问题的最优解。

对偶间隙：p* - d* ，如果间隙等于0的话，说明原问题和对偶问题是等价的他们有相同的最优解，怎么保证间隙为零？

对偶间隙为0时称为强对偶，Slater条件是强对偶成立的其中一个条件。假设有一个最优化问题是凸优化问题，且至少存在一个可行解（不一定是最优解），使得不等式约束严格满足（取小于号），那么此时原问题和对偶问题是等价的，即强对偶是成立的。Slater是强对偶成立的充分条件而非必要条件。对于所有的优化问题，弱对偶都是成立的，而强对偶成立是有条件的，其中一个条件就是Slater条件。

KKT条件

KKT条件是拉格朗日乘数法的一个推广，拉格朗日乘数法是一个求解带等式约束的极值问题。

这里求解的问题既带有等式约素也带有不等式约束：

 构造拉格朗日乘子函数：

，除了对等式约束构造拉格朗日乘子以外也对不等式约束构造了一组拉格朗日乘子。

KKT条件在极值点处要满足以下条件：

 本集总结：