梯度下降法

梯度下降法，又称“最速下降法”，是机器学习领域最常用的优化算法之一，适用于各种无约束的优化问题。

下面我们简单叙述梯度下降法的原理。假设无约束优化函数是：

$\min_{\theta\in R^n} f(\theta)$

我们需要求解上式的极小值，当然我们可以直接求解偏导数，令偏导数等于0，但是有时这种方法并不现实，因为偏导数可能非常复杂，难以求解零点。梯度下降法尝试从任意点出发，采用迭代的方式，每次都使函数的值下降一点点。

$\theta_{k+1} = \theta_{k} - \eta \Delta \theta$

其中 $\eta$ 是一个很小的正数，一般为一个常数（当然也可以随着梯度下降法的进行动态调整大小），我们的目标是让 $f(\theta_{k+1})<f(\theta_k)$
为了达到目标，我们尝试让 $f(\theta)$ 在 $\theta_k$ 处做泰勒展开：

$f(\theta) = f(\theta_k) + \nabla f(\theta_k)\cdot (\theta-\theta_k)$

通过让右边第二项恒小于等于0，左边就会小于 $f(\theta_k)$ ，令 $\theta-\theta_k = -\eta \nabla f(\theta_k)$ 即可满足条件，所以很容易得到 $\theta_{k+1}$ 的更新方法：
$\theta_{k+1} = \theta_k - \eta \nabla f(\theta_k)$

从函数图像上看，某点的梯度方向是该点处函数上升最快的方向，因此我们每次向梯度的反方向取值，企图寻找到函数值下降较快的方向。梯度下降法用于凸函数时能寻找到全局最优，但是对于非凸函数可能找到的是局部最优点，此时需要用其他方法保证解是可接受的（全局最优或者一个可接受范围内的局部最优），如选取多个初始点，或者模拟退火等。

对于机器学习问题来说，优化函数 $f(\theta)$ 一般是关乎训练集中所有数据（点）的一个函数，比如最小二乘的目标函数（假设训练集的数据格式为： $(\mathbf{x_i}, y_i)$ , 函数 $g$ 为训练模型）：
$f(\theta) = \sum_{i=1}^N ||y_i - \hat{y_i}||_2^2 = \sum_{i=1}^N ||y_i - g(\mathbf{x_i}, \theta)||_2^2$