监督式学习(Supervised Learning)，是一个机器学习中的方法，可以由数据(data)中学到或建立一个模式，并依此模式推测新的实例。
通过学习数据的输入(x : Input variables)和输出(y : Output Variables)，建立一个函数h：x->y，通常函数h被称作hypothesis。若函数h的输出是一段连续的值，这种学习问题被称为回归分析(Regression Analysis)；若函数h的输出是推测某种性质，这种学习问题被称为分类问题(Classification Problem)。 <!-- more -->
假设现有向量 $\vec x=x_1,x_2,x_3…$作为输入，那么$h_\theta(x)=\theta_0+\theta_1\times x_1+\theta_2\times x_2…$
令$x_0=1$，则有$h_\theta(x)=\theta^Tx$
定义 $J(\theta)=\frac{1}{2}\sum_{i=1}^{m}(h_\theta(x^{(i)})-(y^{(i)}))^2$ 为训练模型和实际输出的差异，要使得训练模型尽可能合理，其实就是要选择合适的 $\theta$ ，最终使得 $J(\theta)$ 尽可能小。
梯度下降算法是一种能找到一个 $J(\theta)$ 最小值的方法。
先随机指定一组系数 $\theta$，然后进行迭代，通过改变θ的值来减小 $J(\theta)$，直到 $J(\theta)$ 不再变小（收敛）。
有以下迭代式 $\theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)$
对$\theta_j$求偏导，其实是求得 函数在$\theta$处的梯度，由方向导数概念可知，沿负梯度方向，函数的下降最快。 其中$\alpha$ 是学习速率，这个值设置太大会导致算法在最小值附近大幅度跳动，导致不能正常收敛。
对该式进行化简
$\theta_j:=\theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$
具体的梯度下降算法分为：批量梯度下降(batch gradient descent)和随机梯度下降（stochastic gradient descent）。
批量梯度下降在一轮迭代过程中，需要遍历完所有数据，计算出每个 $\theta$ 的更新值，再对 $\theta$ 进行更新：
$Repeat\ until\ convergence${
$\theta_j:=\theta_j+\alpha\sum_{i=1}^m(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)} $
(for every j)
}
令T为总的迭代次数，则该算法的时间复杂度是$O(T\times m\times n)$
其中n为feature的数量，m为输入的数量。
随机梯度下降在一轮迭代过程中，每遍历一条训练数据，就更新一次 $\theta$。在数据量大的时候通常随机梯度下降会比批量梯度下降的收敛速度更快，即T的值会小很多：
$Repeat\ until\ convergence${
$for\ i=1\ to\ m:$
$\theta_j:=\theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)} $
(for every j)
}
[批量梯度下降算法c++实现代码][1] [1]:https://github.com/plusplus7/MachineLearning/blob/master/src/gradient_descent/batch_gradient_descent.cc
[随机梯度下降算法c++实现代码][2] [2]:https://github.com/plusplus7/MachineLearning/blob/master/src/gradient_descent/stochastic_gradient_descent.cc