title: 1. 监督学习&梯度下降法 date: 2018-06-03 14:29:00 categories: 梯度下降 tags: [梯度下降, 线性回归] mathjax: true

监督学习

符号定义：

监督学习的主要流程：

线性回归

以预测房价为例，我们的目标是导出一个函数（即假设），根据房子的特征（比如大小、卧室数量等等）来预测房价，那么：

• 输入（特征）：$x_1, x_2, …$（比如大小、卧室数量等等）

• 输出（目标）：$y$（房价）

• 假设：$h(x)=h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n$，用于预测房价，其中$\theta_i$是参数，$n$是特征数量

  为了方便，可以将假设写成：$h(x)=\sum_{i=0}n\theta_ix_i=\thetaTx​$

此时，学习函数（Learning Algorithm）的目标就是找到合适的参数$\theta$，使之能够导出『合理』的假设$h(x)$，这里我们将『合理』理解为：$h_\theta(x)$（假设）和$y$（目标）之间的差距最小，也即：

$$ \displaystyle \min_{\theta}\frac{1}{2}\sum_{i=1}m(h_\theta(x){(i)}-y_{(i)})^2 $$ 这里的$\frac{1}{2}$是为了简化之后的计算。

我们定义$$\displaystyle J(\theta)=\frac{1}{2}\sum_{i=1}m(h_\theta(x){(i)}-y_{(i)})^2$$，那么我们的目标就是去选取合适的$\theta$，以最小化$J(\theta)$。

梯度下降法

搜索算法（梯度下降）

目的：不断改变$\theta$，从而来减少$J(\theta)$。

原理：每次都往下降最快的地方走，从而找到一个局部最优解。

一般会初始化$\vec{\theta}=\vec{0}$，然后每次都沿着梯度方向走，以保证每次都往下降最快的地方走： $$ \displaystyle \theta_i:=\theta_i - \alpha\frac{\partial}{\partial \theta_i}J(\theta) $$ 其中，$:=$表示赋值操作，$\alpha$为步长。

对于某个训练样本$(x, y)$ $$\displaystyle \frac{\partial}{\partial \theta_i}J(\theta) = \frac{\partial}{\partial \theta_i}(\frac{1}{2}(h_\theta(x)-y)^2)$$ $$\displaystyle = 2 \times \frac{1}{2}(h_\theta(x)-y)\frac{\partial}{\partial \theta_i}(h_\theta(x)-y)$$ $$\displaystyle = (h_\theta(x)-y)\frac{\partial}{\partial \theta_i}(\theta_0x_0+…+\theta_nx_n-y)$$ $$\displaystyle =(h_\theta(x)-y) \times x_i$$

那么，$\theta_i:=\theta_i - \alpha (h_\theta(x)-y) \times x_i$

批量梯度下降法（Batch Gradient Descent）

批量梯度下降法，使用的是所有训练样本的平均梯度：

$$ \displaystyle \theta_i:=\theta_i - \alpha \frac{1}{m} \sum_{j=1}m(h_\theta(x{(j)})-y{(j)}) \times x_i{(j)} $$

但每次下降都需要遍历所有样本，效率较低，具体过程可能如下：

随机梯度下降法（Stochastic Gradient Descent）

又称为『增量梯度下降法』

对每个样本$(x_{(j)}, y_{(j)})$进行： $$ \displaystyle \theta_i:=\theta_i - \alpha (h_\theta(x{(j)})-y{(j)}) \times x_i^{(j)} $$

直到收敛

这时，每次梯度下降只遍历一个样本，具体过程可能如下：