在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。这里就对梯度下降法做一个完整的总结。
在微积分里面，对多元函数的参数求?偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数f(x,y), 分别对x,y求偏导数，求得的梯度向量就是(?f/?x,&?f/?y)T,简称grad f(x,y)或者▽f(x,y)。对于在点(x0,y0)的具体梯度向量就是(?f/?x0,&?f/?y0)T.或者▽f(x0,y0)，如果是3个参数的向量梯度，就是(?f/?x,&?f/?y，?f/?z)T,以此类推。
那么这个梯度向量求出来有什么意义呢？他的意义从几何意义上讲，就是函数变化增加最快的地方。具体来说，对于函数f(x,y),在点(x0,y0)，沿着梯度向量的方向就是(?f/?x0,&?f/?y0)T的方向是f(x,y)增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是 -(?f/?x0,&?f/?y0)T的方向，梯度减少最快，也就是更加容易找到函数的最小值。
2. 梯度下降与梯度上升
在机器学习算法中，在最小化损失函数时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数，和模型参数值。反过来，如果我们需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。
梯度下降法和梯度上升法是可以互相转化的。比如我们需要求解损失函数f(θ)的最小值，这时我们需要用梯度下降法来迭代求解。但是实际上，我们可以反过来求解损失函数 -f(θ)的最大值，这时梯度上升法就派上用场了。
下面来详细总结下梯度下降法。&&&&&&&&
3. 梯度下降法算法详解
3.1 梯度下降的直观解释
首先来看看梯度下降的一个直观的解释。比如我们在一座大山上的某处位置，由于我们不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山峰低处。
从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。
3.2&梯度下降的相关概念
在详细了解梯度下降的算法之前，我们先看看相关的一些概念。
1. 步长（Learning rate）：步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。用上面下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度。
2.特征（feature）：指的是样本中输入部分，比如样本（x0,y0）,（x1,y1）,则样本特征为x，样本输出为y。
3. 假设函数（hypothesis function）：在监督学习中，为了拟合输入样本，而使用的假设函数，记为hθ(x)。比如对于样本（xi,yi）(i=1,2,...n),可以采用拟合函数如下：&hθ(x) =&θ0+θ1x。
4. 损失函数（loss function）：为了评估模型拟合的好坏，通常用损失函数来度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于样本（xi,yi）(i=1,2,...n),采用线性回归，损失函数为：
& & & & & & &\(J(\theta_0, \theta_1) = \sum\limits_{i=1}^{m}(h_\theta(x_i) - y_i)^2\)
& 其中\(x_i\)表示样本特征x的第i个元素，\(y_i\)表示样本输出y的第i个元素，\(h_\theta(x_i)\)为假设函数。&&&
3.3&梯度下降的详细算法
梯度下降法的算法可以有代数法和矩阵法（也称向量法）两种表示，如果对矩阵分析不熟悉，则代数法更加容易理解。不过矩阵法更加的简洁，且由于使用了矩阵，实现逻辑更加的一目了然。这里先介绍代数法，后介绍矩阵法。
3.3.1&梯度下降法的代数方式描述
1. 先决条件： 确认优化模型的假设函数和损失函数。
比如对于线性回归，假设函数表示为&\(h_\theta(x_1, x_2, ...x_n) = \theta_0 +&\theta_{1}x_1 + ... +&\theta_{n}x_{n}\), 其中\(\theta_i \) (i = 0,1,2... n)为模型参数，\(x_i \) (i = 0,1,2... n)为每个样本的n个特征值。这个表示可以简化，我们增加一个特征\(x_0 = 1 \) ，这样\(h_\theta(x_0, x_1, ...x_n) = \sum\limits_{i=0}^{n}\theta_{i}x_{i}\)。
同样是线性回归，对应于上面的假设函数，损失函数为：
& & & & & &\(J(\theta_0, \theta_1..., \theta_n) = \frac{1}{2m}\sum\limits_{i=0}^{m}(h_\theta(x_0, x_1, ...x_n) - y_i)^2\)
2. 算法相关参数初始化：主要是初始化\(\theta_0, \theta_1..., \theta_n\),算法终止距离\(\varepsilon\)以及步长\(\alpha\)。在没有任何先验知识的时候，我喜欢将所有的\(\theta\)初始化为0， 将步长初始化为1。在调优的时候再 优化。
3. 算法过程：
1）确定当前位置的损失函数的梯度，对于\(\theta_i\),其梯度表达式如下：
\(\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)\)
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即\(\alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)\)对应于前面登山例子中的某一步。
3）确定是否所有的\(\theta_i\),梯度下降的距离都小于\(\varepsilon\)，如果小于\(\varepsilon\)则算法终止，当前所有的\(\theta_i\)(i=0,1,...n)即为最终结果。否则进入步骤4.
4）更新所有的\(\theta\)，对于\(\theta_i\)，其更新表达式如下。更新完毕后继续转入步骤1.
\(\theta_i =&\theta_i -&\alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)\)
下面用线性回归的例子来具体描述梯度下降。假设我们的样本是\((x_1^{(0)}, x_2^{(0)}, ...x_n^{(0)}, y_0),&(x_1^{(1)}, x_2^{(1)}, ...x_n^{(1)},y_1), ...&(x_1^{(m)}, x_2^{(m)}, ...x_n^{(m)}, y_n)\),损失函数如前面先决条件所述：
\(J(\theta_0, \theta_1..., \theta_n) = \frac{1}{2m}\sum\limits_{i=0}^{m}(h_\theta(x_0, x_1, ...x_n) - y_i)^2\)。
则在算法过程步骤1中对于\(\theta_i\) 的偏导数计算如下：&
& \(\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)= \frac{1}{m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{j}, x_1^{j}, ...x_n^{j}) - y_j)x_i^{j}\)
由于样本中没有\(x_0\)上式中令所有的\(x_0^{j}\)为1.
步骤4中\(\theta_i\)的更新表达式如下：
& & & & & &\(\theta_i =&\theta_i -&\alpha\frac{1}{m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{j}, x_1^{j}, ...x_n^{j}) - y_j)x_i^{j}\)
从这个例子可以看出当前点的梯度方向是由所有的样本决定的，加\(\frac{1}{m}\) 是为了好理解。由于步长也为常数，他们的乘机也为常数，所以这里\(\alpha\frac{1}{m}\)可以用一个常数表示。
在下面第4节会详细讲到的梯度下降法的变种，他们主要的区别就是对样本的采用方法不同。这里我们采用的是用所有样本。
3.3.2 梯度下降法的矩阵方式描述
这一部分主要讲解梯度下降法的矩阵方式表述，相对于3.3.1的代数法，要求有一定的矩阵分析的基础知识，尤其是矩阵求导的知识。
1. 先决条件： 和3.3.1类似， 需要确认优化模型的假设函数和损失函数。对于线性回归，假设函数\(h_\theta(x_1, x_2, ...x_n) = \theta_0 +&\theta_{1}x_1 + ... +&\theta_{n}x_{n}\)的矩阵表达方式为：
\(h_\mathbf{\theta}(\mathbf{x}) =&\mathbf{X\theta}\) ，其中， 假设函数\(h_\mathbf{\theta}(\mathbf{X})\)为mx1的向量,\(\mathbf{\theta}\)为nx1的向量，里面有n个代数法的模型参数。\(\mathbf{X}\)为mxn维的矩阵。m代表样本的个数，n代表样本的特征数。
& & & & & & &损失函数的表达式为：\(J(\mathbf\theta) = \frac{1}{2}(\mathbf{X\theta} -&\mathbf{Y})^T(\mathbf{X\theta} -&\mathbf{Y})\), 其中\(\mathbf{Y}\)是样本的输出向量，维度为mx1.
2.&算法相关参数初始化: \(\theta\)向量可以初始化为默认值，或者调优后的值。算法终止距离\(\varepsilon\)，步长\(\alpha\)和3.3.1比没有变化。
3.&算法过程：
1）确定当前位置的损失函数的梯度，对于\(\theta\)向量,其梯度表达式如下：
\(\frac{\partial}{\partial\mathbf\theta}J(\mathbf\theta)\)
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即\(\alpha\frac{\partial}{\partial\theta}J(\theta)\)对应于前面登山例子中的某一步。
3）确定\(\mathbf\theta\)向量里面的每个值,梯度下降的距离都小于\(\varepsilon\)，如果小于\(\varepsilon\)则算法终止，当前\(\mathbf\theta\)向量即为最终结果。否则进入步骤4.
4）更新\(\theta\)向量，其更新表达式如下。更新完毕后继续转入步骤1.
\(\mathbf\theta=&\mathbf\theta -&\alpha\frac{\partial}{\partial\theta}J(\mathbf\theta)\)
还是用线性回归的例子来描述具体的算法过程。
损失函数对于\(\theta\)向量的偏导数计算如下：
\(\frac{\partial}{\partial\mathbf\theta}J(\mathbf\theta) = \mathbf{X}^T(\mathbf{X\theta} -&\mathbf{Y})\)
步骤4中\(\theta\)向量的更新表达式如下：\(\mathbf\theta=&\mathbf\theta -&\alpha\mathbf{X}^T(\mathbf{X\theta} -&\mathbf{Y})\)
对于3.3.1的代数法，可以看到矩阵法要简洁很多。这里面用到了矩阵求导链式法则，和两个矩阵求导的公式。
公式1：\(\frac{\partial}{\partial\mathbf{X}}(\mathbf{XX^T}) =2\mathbf{X}\)
公式2：\(\frac{\partial}{\partial\mathbf\theta}(\mathbf{X\theta}) =\mathbf{X^T}\)
如果需要熟悉矩阵求导建议参考张贤达的《矩阵分析与应用》一书。
3.4&梯度下降的算法调优
在使用梯度下降时，需要进行调优。哪些地方需要调优呢？
1. 算法的步长选择。在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。前面说了。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。
2. 算法参数的初始值选择。&初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。
3.归一化。由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征x，求出它的期望\(\overline{x}\)和标准差std(x)，然后转化为：
\(\frac{x - \overline{x}}{std(x)}\)
这样特征的新期望为0，新方差为1，迭代次数可以大大加快。
4. 梯度下降法大家族（BGD，SGD，MBGD）
4.1 批量梯度下降法（Batch Gradient Descent）
批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新，这个方法对应于前面3.3.1的线性回归的梯度下降算法，也就是说3.3.1的梯度下降算法就是批量梯度下降法。
\(\theta_i =&\theta_i -&\alpha\sum\limits_{j=0}^{m}(h_\theta(x_0^{j}, x_1^{j}, ...x_n^{j}) - y_j)x_i^{j}\)
由于我们有m个样本，这里求梯度的时候就用了所有m个样本的梯度数据。
4.2&随机梯度下降法（Stochastic Gradient Descent）
随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的m个样本的数据，而是仅仅选取一个样本j来求梯度。对应的更新公式是：
\(\theta_i =&\theta_i -&\alpha (h_\theta(x_0^{j}, x_1^{j}, ...x_n^{j}) - y_j)x_i^{j}\)
随机梯度下降法，和4.1的批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
那么，有没有一个中庸的办法能够结合两种方法的优点呢？有！这就是4.3的小批量梯度下降法。
4.3&小批量梯度下降法（Mini-batch Gradient Descent）
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样子来迭代，1&x&m。一般可以取x=10，当然根据样本的数据，可以调整这个x的值。对应的更新公式是：
\(\theta_i =&\theta_i - \alpha&\sum\limits_{j=t}^{t+x-1}(h_\theta(x_0^{j}, x_1^{j}, ...x_n^{j}) - y_j)x_i^{j}\)
5. 梯度下降法和其他无约束优化算法的比较
在机器学习中的无约束优化算法，除了梯度下降以外，还有前面提到的最小二乘法，此外还有牛顿法和拟牛顿法。
梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。
梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。
（欢迎转载，转载请注明出处。欢迎沟通交流： pinard.）&
阅读(...) 评论()后使用快捷导航没有帐号？
查看: 2431|回复: 0
java实现梯度下降法
注册会员, 积分 90, 距离下一级还需 110 积分
论坛徽章:1
梯度下降法
基本思想是找出对应的一系列系数theta(i)使得错误估计函数J(theta)=∑(f(xi)-yi)^2/2最小,这是一个关于theta(i)的函数,
要得到其最小值需要求关于theta(i)的各个偏导数J'(theta)=(h(x)-y)xi, 这个J'(theta)是一个描述函数上升变化的向量, 如
果沿着其反方向则函数值会递减, 所以思想是:
随机取一组theta_old, 对于一个训练数据集, 遍历数据集计算下一组theta_new(i)=theta_old(i)-t*(J'(theta_old),使theta
优化直到收敛, 也就是theta或者是J(theta)变化开始很小.
theta的初始值和步长t的选择不当的话, 很可能找到局部最优解, 很可能在迭代过程中来回摆动
代码如下，为什么论坛的代码功能这么弱，格式全乱了。。。
import .math.BigD
import java.util.ArrayL
import java.util.A
import java.util.L
import kmeans.Kmeans.DataN
public class GradientDescent {
& & & & private List&DataNode& samples = new ArrayList&DataNode&();
& & & & private double learningRate = 0.00001;
& & & & private double tolerance = 0.001;
& & & & private double[]
& & & & private int sampleN
& & & & public GradientDescent(double[][] samples) {
& & & & & & & & for(double[] data:samples) {
& & & & & & & & & & & & this.samples.add(new DataNode(data));
& & & & & & & & }
& & & & & & & & sampleNum = samples.
& & & & & & & & dimension = samples[0].
& & & & & & & & theta = new double[dimension-1];
& & & & public void train() {
& & & & & & & & int iNum = 0;
& & & & & & & & double lossChange = Double.MAX_VALUE;
& & & & & & & & double pLossFuncValue = Double.MAX_VALUE;
& & & & & & & & while(iNum++&1000&&lossChange&tolerance) {
& & & & & & & & & & & & for(int i=0;i&sampleNum&&lossChange&i++) {
& & & & & & & & & & & & & & & & double hi = 0.0;
& & & & & & & & & & & & & & & & DataNode dataNode = samples.get(i);
& & & & & & & & & & & & & & & & double[] data = Arrays.copyOfRange(dataNode.getData(), 1, dimension);
& & & & & & & & & & & & & & & & for(int j = 0;j&dimension-1;j++)
& & & & & & & & & & & & & & & & {
& & & & & & & & & & & & & & & & & & & & hi += data[j]*theta[j];
& & & & & & & & & & & & & & & & }
& & & & & & & & & & & & & & & & double ei = hi - dataNode.getDataByDimension(0);
& & & & & & & & & & & & & & & & for(int k = 0;k&dimension-1;k++) {
& & & & & & & & & & & & & & & & & & & & theta[k] = theta[k]-learningRate*ei*data[k];
& & & & & & & & & & & & & & & & }
& & & & & & & & & & & & & & & & double lossFuncValue = 0.0;
& & & & & & & & & & & & & & & & for(int m=0;m&sampleNm++) {
& & & & & & & & & & & & & & & & & & & & hi = 0.0;
& & & & & & & & & & & & & & & & & & & & dataNode = samples.get(m);
& & & & & & & & & & & & & & & & & & & & data = Arrays.copyOfRange(dataNode.getData(), 1, dimension);
& & & & & & & & & & & & & & & & & & & & for(int n = 0;n&dimension-1;n++) {
& & & & & & & & & & & & & & & & & & & & & & & & hi += data[n]*theta[n];
& & & & & & & & & & & & & & & & & & & & }
& & & & & & & & & & & & & & & & & & & & lossFuncValue += Math.pow(hi-dataNode.getDataByDimension(0), 2);
& & & & & & & & & & & & & & & & }
& & & & & & & & & & & & & & & & System.out.println(i+& Theta is &+Arrays.toString(theta)+&,error is &+new BigDecimal(lossFuncValue).toPlainString());
& & & & & & & & & & & & & & & & lossChange = Math.abs(lossFuncValue-pLossFuncValue);
& & & & & & & & & & & & & & & & pLossFuncValue = lossFuncV
& & & & & & & & & & & & }
& & & & & & & & }
& & & & }
& & & &
& & & & public static void main(String[] args) {
& & & & & & & & double[][] trainData = { {-1,1,&&71, 3}, {-1,1, 158,14}, {1, 1,128, 5},
& & & & & & & & & & & & & & & & {-1,1,& &2, 1},
& & & & & & & & & & & & & & & & {-1,1,& &1,15},
& & & & & & & & & & & & & & & & {-1,1,& &1,16},
& & & & & & & & & & & & & & & & {-1,1,&&61,17},
& & & & & & & & & & & & & & & & {-1,1,&&37,16},
& & & & & & & & & & & & & & & & {-1,1, 113,16},
& & & & & & & & & & & & & & & & {1, 1, 59,12},
& & & & & & & & & & & & & & & & {1, 1, 82,14},
& & & & & & & & & & & & & & & & {-1,1, 148,16},
& & & & & & & & & & & & & & & & {-1,1,&&18, 2},
& & & & & & & & & & & & & & & & {-1,1,& &1,12},
& & & & & & & & & & & & & & & & {-1,1, 168,18},
& & & & & & & & & & & & & & & & {-1,1,& &1,16},
& & & & & & & & & & & & & & & & {-1,1,&&78,15},
& & & & & & & & & & & & & & & & {-1,1, 175,13},
& & & & & & & & & & & & & & & & {-1,1,&&80,16},
& & & & & & & & & & & & & & & & {-1,1,&&27, 9},
& & & & & & & & & & & & & & & & {-1,1,&&22,16},
& & & & & & & & & & & & & & & & {1, 1,105, 5},
& & & & & & & & & & & & & & & & {1, 1, 96,12},
& & & & & & & & & & & & & & & & {-1,1, 131, 3},
& & & & & & & & & & & & & & & & {1, 1, 15, 2},
& & & & & & & & & & & & & & & & {-1,1,& &9,13},
& & & & & & & & & & & & & & & & {-1,1,& &8, 6},
& & & & & & & & & & & & & & & & {-1,1, 100,14},
& & & & & & & & & & & & & & & & {-1,1,& &4,16},
& & & & & & & & & & & & & & & & {-1,1, 151,16},
& & & & & & & & & & & & & & & & {-1,1,&&31,16},
& & & & & & & & & & & & & & & & {-1,1, 125,11},
& & & & & & & & & & & & & & & & {-1,1, 130,13},
& & & & & & & & & & & & & & & & {-1,1, 112,16},
& & & & & & & & & & & & & & & & {-1,1, 140,11},
& & & & & & & & & & & & & & & & {-1,1,&&93,16},
& & & & & & & & & & & & & & & & {-1,1,& &1, 9},
& & & & & & & & & & & & & & & & {1, 1, 52, 6},
& & & & & & & & & & & & & & & & {-1,1,&&20, 9},
& & & & & & & & & & & & & & & & {1, 1, 91,12},
& & & & & & & & & & & & & & & & {1, 1, 73, 1},
& & & & & & & & & & & & & & & & {-1,1,&&35,13},
& & & & & & & & & & & & & & & & {-1,1, 143, 3},
& & & & & & & & & & & & & & & & {-1,1,&&61, 1},
& & & & & & & & & & & & & & & & {-1,1,&&97,16},
& & & & & & & & & & & & & & & & {1, 1,139,10},
& & & & & & & & & & & & & & & & {-1,1, 136,15},
& & & & & & & & & & & & & & & & {-1,1, 131,13},
& & & & & & & & & & & & & & & & {1, 1,121, 3},
& & & & & & & & & & & & & & & & {-1,1, 177,14},
& & & & & & & & & & & & & & & & {-1,1,&&68,10},
& & & & & & & & & & & & & & & & {-1,1,& &9,17},
& & & & & & & & & & & & & & & & {1, 1,139, 6},
& & & & & & & & & & & & & & & & {-1,1,& &2,17},
& & & & & & & & & & & & & & & & {-1,1, 140,15},
& & & & & & & & & & & & & & & & {-1,1,&&72,15},
& & & & & & & & & & & & & & & & {-1,1,& &2,13},
& & & & & & & & & & & & & & & & {1, 1,120, 8},
& & & & & & & & & & & & & & & & {-1,1,&&51, 9},
& & & & & & & & & & & & & & & & {-1,1, 102,13},
& & & & & & & & & & & & & & & & {1, 1,130, 1},
& & & & & & & & & & & & & & & & {1, 1,114, 8},
& & & & & & & & & & & & & & & & {-1,1,&&81, 1},
& & & & & & & & & & & & & & & & {-1,1, 118,16},
& & & & & & & & & & & & & & & & {-1,1, 118,16},
& & & & & & & & & & & & & & & & {-1,1,&&17,10},
& & & & & & & & & & & & & & & & {-1,1, 195,17},
& & & & & & & & & & & & & & & & {-1,1, 159,13},
& & & & & & & & & & & & & & & & {-1,1,&&18,11},
& & & & & & & & & & & & & & & & {-1,1,&&15,16},
& & & & & & & & & & & & & & & & };
& & & & & & & & GradientDescent model = new GradientDescent(trainData); model.train();
}
复制代码
扫一扫加入本版微信群随机梯度下降（Stochastic gradient descent）和 批量梯度下降（Batch gradient descent ）的公式对比、实现对比
我的图书馆
随机梯度下降（Stochastic gradient descent）和 批量梯度下降（Batch gradient descent ）的公式对比、实现对比
梯度下降（GD）是最小化风险函数、损失函数的一种常用方法，随机梯度下降和批量梯度下降是两种迭代求解思路，下面从公式和实现的角度对两者进行分析，如有哪个方面写的不对，希望网友纠正。
下面的h(x)是要拟合的函数，J(theta)损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的记录条数，j是参数的个数。
1、批量梯度下降的求解思路如下：
（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度
（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta
（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度！！所以，这就引入了另外一种方法，随机梯度下降。
2、随机梯度下降的求解思路如下：
（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta
（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
3、对于上面的linear regression问题，与批量梯度下降对比，随机梯度下降求解的会是最优解吗？
（1）批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小。
（2）随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近。
4、梯度下降用来求最优解，哪些问题可以求得全局最优？哪些问题可能局部最优解？
对于上面的linear regression问题，最优化问题对theta的分布是unimodal，即从图形上面看只有一个peak，所以梯度下降最终求得的是全局最优解。然而对于multimodal的问题，因为存在多个peak值，很有可能梯度下降的最终结果是局部最优。
5、随机梯度和批量梯度的实现差别
以前一篇博文中NMF实现为例，列出两者的实现差别（注：其实对应python的代码要直观的多，以后要练习多写python！）
[java] //&随机梯度下降，更新参数&&public&void&updatePQ_stochastic(double&alpha,&double&beta)&{&&&&&&for&(int&i&=&0;&i&&&M;&i++)&{&&&&&&&&&&ArrayList&Feature&&Ri&=&this.dataset.getDataAt(i).getAllFeature();&&&&&&&&&&for&(Feature&Rij&:&Ri)&{&&&&&&&&&&&&&&//&eij=Rij.weight-PQ&for&updating&P&and&Q&&&&&&&&&&&&&&double&PQ&=&0;&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&K;&k++)&{&&&&&&&&&&&&&&&&&&PQ&+=&P[i][k]&*&Q[k][Rij.dim];&&&&&&&&&&&&&&}&&&&&&&&&&&&&&double&eij&=&Rij.weight&-&PQ;&&&&&&&&&&&&&&&&//&update&Pik&and&Qkj&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&K;&k++)&{&&&&&&&&&&&&&&&&&&double&oldPik&=&P[i][k];&&&&&&&&&&&&&&&&&&P[i][k]&+=&alpha&&&&&&&&&&&&&&&&&&&&&&&&&&*&(2&*&eij&*&Q[k][Rij.dim]&-&beta&*&P[i][k]);&&&&&&&&&&&&&&&&&&Q[k][Rij.dim]&+=&alpha&&&&&&&&&&&&&&&&&&&&&&&&&&*&(2&*&eij&*&oldPik&-&beta&*&Q[k][Rij.dim]);&&&&&&&&&&&&&&}&&&&&&&&&&}&&&&&&}&&}&&&&//&批量梯度下降，更新参数&&public&void&updatePQ_batch(double&alpha,&double&beta)&{&&&&&&&&for&(int&i&=&0;&i&&&M;&i++)&{&&&&&&&&&&ArrayList&Feature&&Ri&=&this.dataset.getDataAt(i).getAllFeature();&&&&&&&&&&&&for&(Feature&Rij&:&Ri)&{&&&&&&&&&&&&&&//&Rij.error=Rij.weight-PQ&for&updating&P&and&Q&&&&&&&&&&&&&&double&PQ&=&0;&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&K;&k++)&{&&&&&&&&&&&&&&&&&&PQ&+=&P[i][k]&*&Q[k][Rij.dim];&&&&&&&&&&&&&&}&&&&&&&&&&&&&&Rij.error&=&Rij.weight&-&PQ;&&&&&&&&&&}&&&&&&}&&&&&&&&for&(int&i&=&0;&i&&&M;&i++)&{&&&&&&&&&&ArrayList&Feature&&Ri&=&this.dataset.getDataAt(i).getAllFeature();&&&&&&&&&&for&(Feature&Rij&:&Ri)&{&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&K;&k++)&{&&&&&&&&&&&&&&&&&&//&对参数更新的累积项&&&&&&&&&&&&&&&&&&double&eq_sum&=&0;&&&&&&&&&&&&&&&&&&double&ep_sum&=&0;&&&&&&&&&&&&&&&&&&&&for&(int&ki&=&0;&ki&&&M;&ki++)&{//&固定k和j之后,对所有i项加和&&&&&&&&&&&&&&&&&&&&&&ArrayList&Feature&&tmp&=&this.dataset.getDataAt(i).getAllFeature();&&&&&&&&&&&&&&&&&&&&&&for&(Feature&Rj&:&tmp)&{&&&&&&&&&&&&&&&&&&&&&&&&&&if&(Rj.dim&==&Rij.dim)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ep_sum&+=&P[ki][k]&*&Rj.&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&for&(Feature&Rj&:&Ri)&{//&固定k和i之后,对多有j项加和&&&&&&&&&&&&&&&&&&&&&&eq_sum&+=&Rj.error&*&Q[k][Rj.dim];&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&//&对参数更新&&&&&&&&&&&&&&&&&&P[i][k]&+=&alpha&*&(2&*&eq_sum&-&beta&*&P[i][k]);&&&&&&&&&&&&&&&&&&Q[k][Rij.dim]&+=&alpha&*&(2&*&ep_sum&-&beta&*&Q[k][Rij.dim]);&&&&&&&&&&&&&&}&&&&&&&&&&}&&&&&&}&&}&&
TA的最新馆藏
喜欢该文的人也喜欢
