1.7优化（optimization）
1.7 优化（optimization）
1.7.1 梯度下降（Gradient Descent）
解决回归算法中一些求拟合线性方程最优解问题，即最小化损失函数J(θ) = ( h(x) - y )^2的问题，有两种求解方法：最小二乘法和梯度下降法。而通过矩阵求解最小二乘公式中：θ = ( XTX)-1XTy→要求X是列满秩的，而且求矩阵的逆比较慢，所以一般采用梯度下降法。
算法目标是最小化J(θ)，找到最优解。首先引入梯度概念：
由公式可见，对点x0的导数反映了函数在点x0的瞬时变化速率，或者叫在点x0处的斜度。推广到多维函数中，就有了梯度的概念，梯度是一个向量组合，反映了多维图形中变化速率最快的方向。
求解过程中若导数为正，θ1会减小，并以新的θ1作为基点重新求导，一直迭代就会找到最小的θ1；若导数为负时，θ1就会增大，直到找到使损失函数最小的值。需要注意的是步长α为学习速率，若设置太小则会迭代很多次才找到最优解，若太大则可能跳过最优解而找不到最优解。另外，在不断迭代的过程中，梯度值会不断变小，所以θ1的变化速度也会越来越慢，所以不需要使学习速率α的值越来越小。当梯度下降到一定数值后，每次迭代的变化很小，这时可以设定一个阈值，变化小于该阈值就停止迭代，得到近似于最优解的结果。若损失函数的值不断变大，则有可能是学习速率太大，导致算法不收敛，可适当的调整α值，本身这个过程就是调试选择最佳参数α值的过程。
优缺点总结：优点：容易并行，每次迭代过程中开销较小，随机梯度下降开销更小；缺点：收敛速度较慢，需要在节点之前进行通信。
1.7.2 LBFGS算法（拟牛顿法值L-BFGS算法）(Limited-memory Broyden-Fletcher-Goldfarb-Shanno)
代码实现：
L-BFGS算法中使用到的正则化方法是SquaredL2Updater。算法实现上使用到了由scalanlp的成员项目breeze库中的BreezeLBFGS函数,mllib中自定义了BreezeLBFGS所需要的DiffFunctions。
1.7.3 非负最小二乘法（NNLS(Non-Negative Least Squares)）
Spark中的非负正则化最小二乘法使用改进投影梯度法结合共轭梯度法来求解非负最小二乘。最小二乘法分为线性最小二乘和非线性最小二乘。共轭梯度法的基本思想是把共轭性与最速下降方法（Gradient Descent梯度下降）相结合，利用已知点处的梯度构造一组共轭方法，并沿这组方向进行搜索，求出目标函数的极小点。
Spark中解决最小二乘可以选择两种方式，一种是非负正则化最小二乘（NNLS），一种是乔里斯基分解（Cholesky）。乔里斯基分解是把一个对称正定的矩阵表示成一个上三角矩阵U的转置和其本身的乘积的分解。
NNLS中sort方法用来解最小二乘，它通过迭代求解极小值，求解步骤：
- 确定迭代次数
- 求梯度
- 求梯度的投影矩阵
- 求搜索方向
- 计算步长
- 调整步长并修改迭代值