分类目录归档:迭代优化算法

最速下降法

首先,理解梯度向量是指向函数值增长最快的方向的:MIT18.02笔记-梯度的定义与理解

定义函数f(x),其在点x处沿着方向d的变化率可用方向导数表示,即梯度与方向的乘积: Df(x;d)=f(x)Tdd=f(x)||f(x)||时,函数f在点x处的下降速率最大,即负梯度方向为最速下降方向

最速下降算法:在迭代过程,每次都选择负梯度方向搜索(对于寻找最小值的最优化问题)

最速下降算法步骤:

  1. 初始化x1,设定允许的最小误差ϵ,迭代次数k=1
  2. 对于第k次迭

Read more

共轭梯度法

共轭梯度法(Conjugate Gradient)是介于最速下降法牛顿法之间的一个方法

  • 仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,
  • 避免了牛顿法需要存储和计算Hessian矩阵(占用空间大)并求逆的缺点
  • 求解大型线性方程组或非线性最优化问题时常用且高效的方法

1 共轭方向法

G为对称正定矩阵,若dmTGdn=0, mn ,则称dmdn为“G共轭”,共轭方向是“互不相关”的方向

共轭是正交的推广,n个共轭向量可以作为n维空间的非正交基,共轭向量间是线性无关的

共轭方向法

Read more

贝叶斯优化

贝叶斯优化是一种通用的黑盒优化算法,不需要计算梯度便可快速解决最优化问题,贝叶斯优化适合处理目标函数计算成本高或求导困难的情况。贝叶斯优化最常用的场景是超参搜索(尤其是神经网络类算法,计算成本高,超参数还多)

1 贝叶斯优化与代理模型

贝叶斯优化(Bayesian Optimization,BO)

  • 目的是要找到一组最优的超参组合x,能使评价/目标函数f(x)达到全局最优

  • 由于评价/目标函数f(x)计算成

Read more

拟牛顿类算法

在最优化问题的求解过程中常利用到函数梯度及其高阶信息

  • 这类算法最常见的就是梯度下降法和牛顿迭代法
  • 梯度下降考虑了函数的一阶导数, 是一种一阶优化方法
  • 牛顿算法考虑了函数的二阶偏导, 是一种二阶优化方法

1 牛顿迭代法

牛顿法(Newton's method)又称为牛顿-拉弗森方法(Newton-Raphson method)

牛顿法借助泰勒级数的低阶展开,寻找方程f(x)=0的根(因此也被称为切线法)

牛顿法计算步骤:

  • 随机初始化$x=x

Read more

期望最大化EM算法

期望最大化(Expectation-Maximum,简称EM)算法是一种机器学习常见基础算法

EM算法常用于处理存在隐变量的最大似然估计模型,训练过程简单描述如下:

  1. E步,固定模型参数,优化潜在变量分布
  2. M步,固定潜在变量分布,优化模型参数
  3. 重复EM步骤,直至收敛或达到最大迭代次数

K-means聚类为例进行直观理解:

  1. 聚类簇的质心就是潜在变量
  2. E步,随机化/更新簇的质心
  3. M步,根据质心重新分配样本
  4. 重复EM步骤,直至簇的质心不再变化或达到最大迭代次数

EM算法作为一种基础算法,广泛应用于多种算法模型的学习过程,比如:隐马尔可夫模型 HMM

这类算法思想在其他模型中也经常遇见,比

Read more

梯度下降法族

1 梯度下降法-简单版

大部分机器学习模型的构建都是寻找最小损失函数的过程,而梯度下降法(Gradient Descent)便是一种常见迭代优化算法,用于寻找损失最小的参数解。

以简单二次函数为例进行算法的简单说明,模型形式

Read more

坐标轴下降法

坐标下降法(英语:coordinate descent)是一种非梯度优化算法。算法在每次迭代中,在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言,算法可能无法在较小的迭代步数中求得最优解。

附件/Pasted image 20210819215357.png

为了加速收敛,可以采用一个适当的坐标系,例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系,即自适应坐标下降法。

#坐标下降法 #非梯度 #CoordinateDescent

Read more