最优化理论

发表于 更新于 分类于 ， 阅读次数： 本文字数： 8.5k 阅读时长 ≈ 8 分钟

本文讲解了常用的优化算法，对应深度学习的优化函数，实际学习路径可以是最小二乘法->座标下降->梯度下降->牛顿法

什么是最优化算法？

  • 最优化方法是机器学习的灵魂，用于更新模型参数使策略（损失函数）最小化的方法
  • 即给定一个函数 f:A→R{\displaystyle f:A\to \mathbb {R} }，寻找一个元素 x0∈A{\displaystyle \mathbf {x} ^{0}\in A} 使得对于所有 A{\displaystyle A} 中的 x{\displaystyle \mathbf {x} } ，f(x0)≤f(x){\displaystyle f(\mathbf {x} ^{0})\leq f(\mathbf {x} )}（最小化）；或者 f(x0)≥f(x){\displaystyle f(\mathbf {x} ^{0})\geq f(\mathbf {x} )}（最大化）

如何解决最优化问题？

  • 对于无约束的优化问题，如果函数是二次可微的话，可以通过找到目标函数梯度为0（也就是拐点）的那些点来解决此优化问题，要找到那些拐点，我们可以通过猜测一个初始点，然后用比如以下的迭代的方法来找到：1）梯度下降法 (Gradient descent, GD) ；2）牛顿法 (Newton’s method)；3）共轭梯度法
  • 有约束条件的约束问题常常可以通过拉格朗日乘数转化为非约束问题
  • 其他一些流行的方法有 ：1遗传算法；2）模拟退火法 ；3粒子群算法

概率模型如何求解？

  • 概率模型学习策略：极大似然估计 (MLE)贝叶斯估计极大后验概率估计（MAP）。这时学习的策略是极小化对数似然损失或极小正则化(regularization)的对数似然损失
  • 决策树学习的策略：正则化的极大似然估计，损失函数是对数似然损失正则化 (regularization)项是决策树的复杂度
  • 逻辑斯谛回归模型与最大熵模型条件随机场学习策略：既可以看成是极大似然估计，又可以看成是极小逻辑斯谛损失（正则化 (regularization)的逻辑斯谛损失）
  • 朴素贝叶斯（NBC）模型隐马尔可夫模型模型的非监督学习：极大似然估计或极大后验概率估计，但这时模型含有隐变量

常见算法学习策略？

  • 朴素贝叶斯法与隐马尔可夫模型：极大似然估计值，可以由概率计算公式直接计算
  • 逻辑斯谛回归模型与最大熵模型条件随机场：利梯度下降法 (Gradient descent, GD)、拟牛顿法等，这些都是一般的无约束最优化问题的解法
  • 支持向量机（SVM）：可以解凸二次规划的对偶问题。有序列最小最优化算法等方法
  • 决策树 (ID3, ID4.5, C4.5)：基于启发式算法的典型例子，可以认为是特征选择、生成、剪枝是启发式地进正则化的极大似然估计
  • 提升方法：利用学习的模型是加法模型、损失函数是指数损失函数的特点，启发式地从前向后逐步学习模型，以达到逼近优化目标函数的目的
  • EM：一种迭代的求解含隐变量概率模型参数的方法，它的收敛性可以保证，但是不能保证收敛到全局最优

什么是收敛?

  • 通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化
  • 也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象

什么是最小二乘法？

  • 通过最小化误差的平方和，使得拟合对象无限接近目标对象，是一种优化算法

  • 上图假设是温度和买冰淇淋数量的关系图，这里假设这种关系是线性关系，即 f(x)=ax+b，可以通过最小二乘法求解这个式子的参数 a、b

  • 1）计算总平方误差：利用平方误差求出式子与样本的距离，也即求样本点到直线 y 方向的距离

    S=∑(f(xi)−yi)2=∑(axi+b−yi)2S=\sum(f(x_i)-y_i)^2=\sum(ax_i+b-y_i)^2

  • 2）最小化误差：即求得误差的极小值，这可以通过对求导公式=0 求出，得到方程组后求解参数 a=7.2，b=-73，最终结果是绿色线的结果，也可以假设关系二次关系，求得红色线的式子

    ∂S∂a=2∑(axi+b−yi)xi=0∂S∂b=2∑(axi+b−yi)=0\begin{aligned}\frac{\partial S}{\partial a}&=2\sum(ax_i+b-y_i)x_i=0\\\\\frac{\partial S}{\partial b}&=2\sum(ax_i+b-y_i)=0\end{aligned}

什么是梯度下降法(Gradient descent, GD) ?

  • 是一类一阶最优化算法，通常也称为最陡下降法，要使用梯度下降法找到一个函数的 局部极小值，必须向函数上当前点对梯度(gradient)（或者是近似梯度）的 反方向 的规定步长距离点进行迭代搜索
  • 梯度下降方法基于以下的观察：如果实值函数F(x){\displaystyle F(\mathbf {x} )}在点a{\displaystyle \mathbf {a} } 处可微且有定义，那么函数F(x){\displaystyle F(\mathbf {x} )}在a{\displaystyle \mathbf {a} }点沿着梯度相反的方向−∇F(a){\displaystyle -\nabla F(\mathbf {a} )}下降最多。即如果b=a−γ∇F(a){\mathbf {b}}={\mathbf {a}}-\gamma \nabla F({\mathbf {a}}) ，对于γ>0{\displaystyle \gamma >0}为一个够小数值时成立，那么F(a)≥F(b){\displaystyle F(\mathbf {a} )\geq F(\mathbf {b} )}
  • 例子： 现有函数 y=x2y=x^2，初始条件为 x0=2,y0=4x_0=2,y_0=4，如何通过梯度下降，找到最小值？
    • 目标函数对变量求导dydx=2x\frac{d y}{d x}=2 x ，在x0=2,y0=4x_0=2,y_0=4 的梯度为2∗x0=42*x_0=4 ，按照1%的梯度向下走，x更新为x1=x0−0.01∗4=1.96x_1=x_0-0.01*4=1.96，此时y的值为y1=3.8416<4y_1=3.8416<4
    • 按照这个方式更新x，可以将y的值按下图方式滚到坡低

为什么使用梯度下降时，学习率r必须足够小？

  • 已知梯度下降的迭代公式为

    xn+1=xn−γn∇F(xn), n≥0\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0

  • 根据函数的一阶泰勒展开，在负梯度方向，函数值是下降的。只要学习率rnr_n设置的足够小，并且没有到达梯度为0的点处，每次迭代时函数值一定会下降
  • 足够小的学习率rnr_n 可以保证迭代之后的xn+1x_{n+1}位于迭代之前的值xnx_{n}的邻域内，从而可以忽略泰勒展开中的高次项，保证迭代时函数值下降

梯度下降法找到的一定是下降最快的方向么？

  • 梯度下降法并不是下降最快的方向，它只是目标函数在当前的点的切平面（当然高维问题不能叫平面）上下降最快的方向，可以认为是局部下降最快的方向
  • 牛顿方向（考Hessian矩阵(黑塞矩阵) ）才一般被认为是下降最快的方向，可以达到Superlinear的收敛速度。梯度下降类的算法的收敛速度一般是Linear甚至Sublinear的（在某些带复杂约束的问题）

梯度下降法和牛顿法的异同？

  • 梯度下降法(Gradient descent, GD) 牛顿法(Newton’s method)拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解
  • 相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长

座标下降法与梯度下降法比较？

  • 坐标下降的顺序是任意的
  • 坐标下降的关键在于一次一个地更新，所有的一起更新有可能会导致不收敛
  • 坐标上升法和坐标下降法的本质一样，只不过目标函数成为求极大值了
  • 如果目标函数不平滑的话，坐标下降法可能会陷入非驻点。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系

梯度下降算法所面临的挑战？

  • 数据挑战：只能解决那些意义非常明确的凸优化问题；没有特定的方法来规避鞍点的出现
  • 梯度挑战：梯度下降算法时出现错误，可能会导梯度消失(gradient vanishing) 或梯度爆炸(gradient exploding) 。当梯度太小或者太大时，就会出现这样的问题，进而导致算法无法收敛
  • 执行挑战：观察网络资源利用率是非常重要的。比如，在执行梯度下降算法时，了解需要多少资源是非常重要的。如果应用程序的储存器太小，那么网络就会失败

最小二乘法与梯度下降法比较？

  • 梯度下降法 (Gradient descent, GD)与最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。
  • 梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解
  • 最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势

什么是牛顿法 (Newton’s method)？

  • 又称为牛顿-拉弗森方法（Newton-Raphson method），是二阶优化技术，利用了函数的一阶和二阶导数信息，直接寻找梯度为0的点
  • 上图是 f(x)=(x−2)2f(x)=(x-2)^2 的牛顿法求解过程，假设初始化位置为 A 点，求 A 点的斜率与 x 轴的交点 B，可知 f(xB)<f(xA)f(x_B)<f(x_A)，只要不断迭代这个过程，就可求出 f (x)的极小值。
  • 以上过程可简化为：参数 x 的更新过程，即

    xn+1=xn−f(xn)f′(xn)x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}

  • 牛顿法本身是一阶算法，本质是求根算法 (上式)。但如果用来求最优解（极值点），这时就要求导数为 0 的跟，就需要求二阶导数，就变成了二阶算法

    xn+1=xn−f′(xn)f′′(xn)x_{n+1}=x_{n}-\frac{f^\prime(x_{n})}{f^\prime\prime(x_{n})}

  • 从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

什么是拟牛顿法？

  • 一种牛顿法(Newton’s method)为基础设计的，求解非线性方程组或连续的最优化问题函数的零点或极大、极小值的算法。当牛顿法中所要求计算雅可比矩阵Hessian矩阵(黑塞矩阵) 难以甚至无法计算时，拟牛顿法便可派上用场
  • 拟牛顿法的思路是不计算目标函数的Hessian矩阵然后求逆矩阵，而是通过其他手段得到一个近似Hessian矩阵逆的矩阵。具体做法是构造一个近似Hessian矩阵或其逆矩阵的正定对称矩阵，用该矩阵进行牛顿法的迭代 ，不需要二阶导数的信息，简化了运算的复杂度

什么是共轭梯度法(Conjugate gradient method)？

  • 共轭梯度法是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法
  • 共轭梯度法是一种通过迭代下降的共轭方向来避免Hessian矩阵求逆计算的方法，介于最速下降法与牛顿法之间

什么是坐标下降法 (coordinate descent)？

  • 坐标下降法（coordinate descent）是一种非梯度优化算法。算法在每次迭代中，在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值，在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系（参考自适应坐标下降法）
  • 与通过梯度获取最速下降的方向不同，在坐标下降法中，优化方向从算法一开始就予以固定。例如，可以选择线性空间的一组基 e1,e2,…,en{\displaystyle \mathbf {e} _{1},\mathbf {e} _{2},\dots ,\mathbf {e} _{n}} 作为搜索方向。在算法中，循环最小化各个坐标方向上的目标函数值。亦即，如果 xk{\displaystyle \mathbf {x} ^{k}} 已给定，那么，xk+1{\displaystyle \mathbf {x} ^{k+1}} 的第 i{\displaystyle i} 个维度为

    xik+1=arg min⁡y∈R  f(x1k+1,…,xi−1k+1,y,xi+1k,…,xnk){\displaystyle \mathbf {x} _{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},…,x_{i-1}^{k+1},y,x_{i+1}^{k},…,x_{n}^{k})}

  • 因而，从一个初始的猜测值x0{\displaystyle \mathbf {x} _{0}}以求得函数F{\displaystyle F}的局部最优值，可以迭代获得x0,x1,x2,…{\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots }的序列

什么是模拟退火法？

  • 模拟退火（Simulated annealing,SA）是一种通用概率算法，常用来在一定时间内寻找在一个很大搜寻空间中的近似最优解
  • 模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置
  • 模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率

什么是粒子群算法？

  • 粒子群算法（Particle Swarm Optimization，PSO），或称粒子群优化，是属于人工智能算法
  • 借由观察鸟类族群觅食的讯息传递所得到的一个启发，粒子群算法的理论基础是以单一粒子来做为鸟类族群之中的单一个体，于算法中赋予该粒子（个体）拥有记忆性，并能够透过与粒子群体中的其他粒子之间的互动而寻求到最适解

什么是遗传算法(Genetic Algorithm, GA)？

  • 一类借鉴生物界的进化规则演化而来的随机搜索算法。主要特点是直接对结构对象进行操作，不存在求导和函数连续性的鉴定，具有内在的隐并行性和更好的全局行动能力
  • 采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自动调整搜索方向不需要确定的规则
  • 例子：求区（0,31]的y=x2y=x^2的最大值
      1. 设定种群规模, 编码染色体，产生初始种群

      S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011)

      1. 定义适应度函数, 取适应度函数：f (x)=x * x
      1. 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作
      • 计算适应度

        f(s1)=f(13)=13∗13=169f(s2)=f(24)=242∗24=576f(s3)=f(8)=8∗8=64f(s4)=f(19)=19∗19=36\begin{array}{l}f (s1) = f(13) = 13*13= 169 \\ f (s2) = f(24) = 242*24= 576 \\ f (s3) = f(8) = 8*8 = 64 \\ f (s4) = f(19) = 19*19 = 36\end{array}

      • 计算选择概率

        P(s1)=P(13)=(13/13+24+8+19)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31\begin{array}{l}P(s1) = P(13) =(13/13+24+8+19)= 0.14 \\ P(s2) = P(24) = 0.49 \\ P(s3) = P(8) = 0.06 \\ P(s4) = P(19) = 0.31\end{array}

      • 赌轮选择法：1） 在［0, 1］区间内产生一个均匀分布的随机数r； 2）若r≤q1,则染色体x1被选中；3） 若qk-1
      1. 选择-复制： 设从区间［0, 1］中产生4个随机数如下
      1. 交叉： 设交叉率 pc=100%，即 S 1 中的全体染色体都参加交叉运算，设 s 1’与 s 2’配对，s 3’与 s 4’配对。分别交换后两位基因，得新染色体

      s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）s1’’=11001（25）, s2’’=01100（12） s3’’=11011（27）, s4’’=10000（16）

      1. 变异： 设变异率pm=0.001， 群体S1中共有 5×4×0.001=0.02 位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异
      1. 新的迭代： 在迭代好多代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出

牛顿法有哪些缺点？

  • 牛顿法需要求目标函数的二阶导数，高维时矩阵非常大，计算及存储都有难度
  • 小批量训练数据时，牛顿法的二阶估计噪声过大
  • 目标函数非凸时，容易收敛到鞍点

采用期望最大化(EM)算法求解的模型有哪些，为什么不用牛顿法或梯度下降法？

  • 期望最大化(Expectation-Maximum,EM) 求解的模型一般有GMM或者协同过滤，K-means其实也属于EM
  • EM算法一定会收敛，但是可能收敛到局部最优。由于求和的项数将随着隐变量的数目指数上升，会给梯度计算带来麻烦

什么是凸集、凸函数？

  • 凸集：若对集合C中任意两点u和v，连接他们的线段仍在集合C中，那么集合C是凸集 αu+(1−α),v∈C,α0,1]αu+(1-α),v∈C,α0, 1]
  • 凸函数：凸集上的函数是凸函数。凸函数的每一个局部极小值也是全局极小值( f(x) = 0.5x^2 ) f(αu+(1−α)v)≤αf(u)+(1−α)f(v)f(αu + (1-α)v) ≤ αf(u)+ (1-α)f(v)

参考：

  1. 牛顿法是一阶还是二阶，为什么很少用 - 简书
  2. 牛顿迭代法 - 知乎