量化研究数学基础——最优化方法

super1 · 发表于 2021-12-18 13:19

引言

最优化方法，是整个机器学习甚至深度学习的基础，而在组合构建的时候，各标的的权重计算也需要用到最优化，本文将针对常用的最优化方法的数学基础进行介绍，以便于在模型开发的过程中更科学的选择优化器以及超参数配置。
一阶优化算法

目前，神经网络基本使用的都是一阶的优化算法，包括基本的梯度算法以及其他的衍生版本，梯度下降法的基本逻辑为：
设置最小梯度标准 $eps$ ，最大迭代次数 $N$ 以及学习率
初始化 $x_0,k=0$
如果 $||\nabla f(x_k)|| > eps$ 且 $k<N$ :

$x_{k+1}=x_k-\alpha \nabla f(x_k)$

$k =k+1$
梯度下降法在每次迭代的时候会计算函数在该点的梯度，每次根据梯度乘以学习率来调整参数，从而达到降低函数值的效果，从数学上，可以通过泰勒展开进行理解。
对于第k次迭代，其调整前函数值为 $f(x_k)$ ，调整后为 $f(x_k-\alpha \nabla f(x_k))$ ，对于后者做泰勒展开：

$\\ f(x_k-\alpha \nabla f(x))=f(x_k)+(\nabla f(x_k))^T*(-\alpha \nabla f(x))+o||-\alpha \nabla f(x)|| \\ =f(x_k)-\alpha (\nabla f(x))^T(\nabla f(x))+o$
忽略无穷小量，我们有：

$f(x_k-\alpha \nabla f(x_k))-f(x_k)=-\alpha (\nabla f(x_k))^T\nabla f(x_k)$
由于 $(\nabla f(x_k))^T\nabla f(x_k)\geq0$ 恒成立，则只要给定大于0，就可以保证每次迭代之后，损失函数满足 $f(x_{k+1}) < f(x_k)$ ，从而达到最小化损失函数的效果。
通常情况下，仅仅使用梯度下降法，可能会面临收敛速度慢的问题，因此有研究者开始尝试对梯度下降法进行改进，常见的改进算法包括Momentum,AdaGrad,RMSProp,AdaDelta,Adam。
Momentum，在更新参数时会引入上一次更新的值，用公式表达为：

$x_{k+1}=x_k+v_k$

$v_k=-\alpha \nabla f(x_k)+v_{k-1}$
AdaGrad，在更新参数的时候，对于梯度，会除以历史梯度在该方向累计值，从而使得参数在某个方向上更新很多后学习率降低，用公式表达为：

$x_{k+1}^i=(x_k^i)-\alpha \frac{g_k^i}{\sqrt{\sum_{j=1}^{k}{(g_j^i)^2+\varepsilon}}}$
其中i为向量在各个方向上的分量， $g_k$ 为第k次的梯度向量
RMSProp，RMSProp相对于AdaGrad的改进集中在分母部分，将历史梯度的平方值做了衰减之后再进行累加：
给定初始的E=0

$E[g^2]_k=\delta E[g^2]_{k-1}+(1-\delta)g_k^2$

$x_{k+1}^i=(x_k^i)-\alpha \frac{g_k^i}{\sqrt{{E(g_k^2)^i+\varepsilon}}}$
AdaDelta与RMSprop的计算逻辑相似，E的计算公式相同，但是增加了RMS:

$RMS[g]_k=\sqrt{E[g^2]_k+\varepsilon}$
类似的，可以参照计算出 $RMS[\Delta x]_{k-1}$
最终更新公式为：

$x_{k+1}=x_k-\frac{RMS[\Delta x]_{k-1}}{RMS[g]_k}g_k$
Adam引入了两个向量m和v，初始值为0

$m_k^i=\beta _1m_{k-1}^i+(1-\beta_1)g_k^i$

$v_k^i=\beta_2v_{k-1}^i+(1-\beta_2)(g_k^i)^2$
最终更新公式为：

$x_{k+1}^i=(x_k^i)-\alpha \frac{\sqrt{1-\beta_2^k}}{\sqrt{1-\beta_1^k}}\frac{m_k^i}{\sqrt{v_k^i}+\varepsilon}$
二阶优化算法

牛顿法

牛顿法的基本思路是，对于一个函数f(x)，其在x点取得极值的必要条件是： $\nabla f(x)=0$ 。但是实际上，直接解该方程十分麻烦，所以考虑对其做泰勒展开，牛顿法中，会展开到二阶：

$f(x)=f(x_0)+\nabla f(x_0)\Delta x+1/2\nabla ^2f(x_0)\Delta x^2+o||\Delta x||^2$
移项后两边除以 $\Delta x$ ，可以得到：

$\nabla f(x)=\nabla f(x_0)+\nabla^2f(x_0)(x-x_0)$
然后带入最开始的方程组，可以解得：

$x=x_0-(\nabla ^2f(x_0))^{-1}\nabla f(x_0)$
其中，f(x)的二阶记为H，一阶导记为g。
由于我们对函数进行了泰勒展开，因此一次只能计算近似值，为了获得更精确的结果，还需要不断迭代，因此可以得到我们的迭代公式：

$x_{k+1}=x_k-\alpha H^{-1}_kg_k$
拟牛顿法

但是牛顿法存在一个致命的缺陷，就是当黑塞矩阵不可逆的时候，牛顿法就会失效，为了解决这一问题，就提出了拟牛顿法，典型的包括DFP算法、BFGS算法和L-BFGS算法，由于其基本逻辑类似，我们仅选择DFP进行说明。
重新来看 $\nabla f(x)=\nabla f(x_{k+1})+\nabla^2f(x_{k+1})(x-x_{k+1})$ ，我们令 $x=x_{k}$ 带入，可以得到：

$g_{k+1}-g_k=H_{k+1}(x_{k+1}-x_k)$ ，简写为 $s_k=H_{k+1}^{-1}y_k$
因此，只要知道了s和y，就可以近似计算黑塞矩阵的逆矩阵，然后在每次迭代时进行更新，假设我们的迭代的目标是逆矩阵，为了方便表示，我们暂时先吧上标中的(-1)去掉，然后令：

$H_{k+1}=H_k+E_k$
E为矫正矩阵，上述问题可以转化为求解E，给定E的格式为：

$E_k=\alpha_ku_ku_k^T+\beta_kv_kv_k^T$
然后带入到上面的式子中，移项可得：

$\alpha_ku_ku_k^Ty_k+\beta_kv_kv_k^Ty_k=s_k-H_ky_k$
该方程解不唯一，为了方便计算，我们取一组特殊条件：

$\alpha_ku_ku_k^Ty_k=s_k,\beta_kv_kv_k^Ty_k=-H_ky_k$ 且 $u_k=s_k,v_k=H_ky_k$
带入方程解得：

$\alpha_k=\frac{1}{s_k^Ty_k},\beta_k=-\frac{1}{y_k^TH_ky_k}$
将结果导入到H的更新公式，可以得到最终的表达式：

$H_{k+1}=H_k-\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}+\frac{s_ks_k^T}{y_k^Ts_k}$

		自动登录	找回密码
密码			立即注册