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

2021-10-19 16:00:45 浏览数 (1)

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

梯度下降法

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

x^{(0)}

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

f(x)

值的目的。

假设

f(x)

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

minlimits_{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) = minlimits_{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) = sumlimits_{j=0}^n w_j x_j
L(w) = frac{1}{2m} sumlimits_{i=1}^m l(y_i , f_w(x^i))

算法思路：

  1. 将f(x)对
w_j

求偏导，得到每个

w_j

对应的梯度：

frac{partial L(w)}{partial w_j} = -frac{1}{m} sumlimits_{i=1}^m frac{partial l(w)}{partial w_j} , j from 1 to n
  1. 按照每个参数
w_j

的负梯度方向更新

w_j

，使得风险函数最小化。

w_j^{'} = w_j -frac{partial L(w)}{partial w_j} = w_j frac{1}{m} sumlimits_{i=1}^m frac{partial l(w)}{partial w_j}

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

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

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

算法思路：

  1. 损失函数：
L(w) = frac{1}{2m} sumlimits_{i=1}^m l(y_i , f_w(x^i))
  1. 对于每个样本的损失函数，求第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
  1. 一般迭代小于m次，每次计算量为
n^2

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

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

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

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

牛顿法和拟牛顿法

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

牛顿法

对于无约束最优化问题：

minlimits_{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)

的极小值点;

  1. 取初始点
x^{(0)}

，置k=0;

  1. 计算
g_k = g(x^{(k)})

;

  1. 若
g_k < varepsilon

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

x^* = x^{(k)}

;

  1. 计算
H_k = H(x^{(k)})

，并求

p_k
H_k p_k = -g_k
  1. 置
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

serverless 编程算法

0 人点赞