『机器学习笔记』最优化方法

百川AI

发布于 2021-10-19 16:00:45

5140

发布于 2021-10-19 16:00:45

文章被收录于专栏：我还不懂对话

最优化方法是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。机器学习的问题大多可以建模成一种最优化模型求解，常见最优化方法有梯度下降法，牛顿法和拟牛顿法，启发式优化算法（PSO, ABC等）。

梯度下降法

梯度下降法是一种迭代算法，选取适当的初值

x^{(0)}

，不断以负梯度方向更新x的值，达到减少函数

f(x)

值的目的。

假设

f(x)

具有一阶连续偏导数，求解最优化问题为：

\min\limits_{x \in R^n} f(x)

设第k次迭代值为

x^{(k)}

，则

f(x)

在

x^{(k)}

处的一阶泰勒展开为：

f(x) = f(x^{(k)}) + g_k^T(x-x^{(k)})

其中，

g_k^T = \nabla f(x^{(k)})

，表示

f(x)

在

x^{(k)}

的梯度。

求出第k+1次的迭代值

x^{(k+1)}

x^{(k+1)} = x^{(k)} + \lambda_k *p_k

其中，

p_k

是搜索方向，取负梯度方向：

p_k = -\nabla f(x^{(k)}), \lambda_k

是步长。由以为搜索决定，即

\lambda_k

使得

f(x^{(k)} + \lambda_k p_k) = \min\limits_{\lambda > 0} f(x^{(k)} + \lambda p_k)

在具体的机器学习优化中，函数变为损失函数，通过不断更新迭代参数

w_i

，达到使得损失函数最小的目的。

批量梯度下降-Batch Gradient Descent, BGD

设定损失函数

l(y, f(x))

，y表示真实值，

f(x)

表示预测值，一般的损失函数有平方损失，如

l(y, f(x)) = (y - f(x))^2

对于样本量为m，维度为n的样本空间，整体的损失函数为：

f(w) = \sum\limits_{j=0}^n w_j x_j

L(w) = \frac{1}{2m} \sum\limits_{i=1}^m l(y_i , f_w(x^i))

算法思路：

将f(x)对

w_j

求偏导，得到每个

w_j

对应的梯度：

\frac{\partial L(w)}{\partial w_j} = -\frac{1}{m} \sum\limits_{i=1}^m \frac{\partial l(w)}{\partial w_j} ,\ \ j \ from \ 1 \ to \ n

按照每个参数

w_j

的负梯度方向更新

w_j

，使得风险函数最小化。

w_j^{'} = w_j + -\frac{\partial L(w)}{\partial w_j} = w_j + \frac{1}{m} \sum\limits_{i=1}^m \frac{\partial l(w)}{\partial w_j}

它得到的是一个全局的梯度，每一步迭代都会用到训练集所有数据，对于样本量n很大的数据集，其迭代速度就会很慢，而且容易陷入局部最优。

随机梯度下降-Stochastic Gradient Descent, BGD

随机梯度下降通过每个样本来迭代更新一次，如果样本量很大的话，可能用少量样本量就讲w迭代到最优解，减小了计算量。但是样本中可能存在噪声点，所以SGD并不是每次都是整体最优的方向。

算法思路：

损失函数：

L(w) = \frac{1}{2m} \sum\limits_{i=1}^m l(y_i , f_w(x^i))

对于每个样本的损失函数，求第i个样本对应的

w_j

偏导，来更新

w_j

：

w_j^{'} = w_j + \frac{\partial l_w(x^i, y^i)}{\partial w_j}, j \ from \ 1 \ to \ n

一般迭代小于m次，每次计算量为

n^2

，其实就可以满足停止条件，获得最优解。

机器学习算法随机梯度下降求解模型

批量梯度下降—最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。

随机梯度下降—最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

牛顿法和拟牛顿法

牛顿法和拟牛顿法都是求解无约束问题的方法，优点损失收敛速度快。

牛顿法

对于无约束最优化问题：

\min\limits_{x \in R^n} f(x)

假设

f(x)

具有二阶连续偏导数，若第K次迭代值为

x^{(k)}

，则将其在

x^{(k)}

附近进行二阶泰勒展开：

f(x) = f(x^{(k)}) + g_k^T(x - x^{(k)}) + \frac{1}{2}(x - x^{(k)})^T H(x^{(k)})(x - x^{(k)})

其中，

g_k = g(x^{(k)}) = \nabla f(x^{(k)})

是

f(x)

的梯度向量在点

x^{(k)}

的值，而：

H(x) = [\frac{\partial^2f}{\partial x_i \partial x_j}]_{n*n}

牛顿法算法

输入：目标函数

f(x)

，梯度

g(x) = \nabla f(x)

，海赛矩阵

H(x)

，精度要求

\varepsilon

;

输出：

f(x)

的极小值点;

取初始点

x^{(0)}

，置k=0;

计算

g_k = g(x^{(k)})

;

g_k < \varepsilon

，则停止计算，得到近似解

x^* = x^{(k)}

;

计算

H_k = H(x^{(k)})

，并求

p_k

H_k p_k = -g_k

x^{(k+1)} = x^{(k)} + p_k,\ k= k+1

，转到步骤2;

牛顿法其实是找目标函数倒数的零点，然后通过导数零点获得目标函数的极值点。

拟牛顿法

牛顿法的每次迭代中会计算海赛矩阵的逆矩阵，计算复杂。所以考虑使用一个n阶矩阵

G_k = G(x^{(k)})

来近似。

牛顿法中海赛矩阵瞒住条件：

g_{k+1} - g_k =H_k(x^{(k+1)} - x^{(k)})

在

H_k

是正定(

H^{-1}_k

也是正定的)的情况下，可以保证牛顿法的搜索方向

p_k

是下降方向，而

p_k = -\lambda g_k

，所以

x = x^{(k)} +\lambda p_k = x^{(k)} - \lambda H_k^{-1} g_k

此处

f(x)

在

x^{(k)}

处的一阶泰勒展开为：

f(x) = f(x^{(k)}) -\lambda g_k^T H^{-1}_k g_k

拟牛顿法讲

G_k

作为

H^{-1}_k

的近似，首先

G_k

也要是正定的，同事满足条件：

G_{k+1} y_k= x^{(k+1)} - x^{(k)}

每次迭代的时候，选择更新：

G_{k+1} = G_k + \Delta G_k

区别

梯度下降法是用来求函数值最小处的参数值，而牛顿法是用来求函数值为0处的参数值，不过是导数的0值点。
梯度法中需要选择学习速率，而牛顿法不需要选择任何参数。
梯度法需要大量的迭代次数才能找到最小值，而牛顿法只需要少量的次数便可完成。
梯度法中的每一次迭代的代价要小，其复杂度为O(n),而牛顿法的每一次迭代的代价要大，为O(n^3)。因此当特征的数量n比较小时适合选择牛顿法，当特征数n比较大时，最好选梯度法。这里的大小以n等于1000为界来计算。

参考资料

《统计学习方法》《The Elements of Statistical Learning 》《Machine Learning A Probabilistic Perspective》 Top 10 algorithms in data mining

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017/03/31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

serverless

编程算法

登录后参与评论

0 条评论

热度