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