监督学习&梯度下降法

监督学习

符号定义：

符号	意义
\(m\)	训练集包含的数据个数
\(x\)	输入变量/特征（feature）
\(y\)	输出变量/目标（target）
\((x, y)\)	一个训连样本
\((x^{(i)}, y^{(i)})\)	第i个训练样本

监督学习的主要流程：

线性回归

以预测房价为例，我们的目标是导出一个函数（即假设），根据房子的特征（比如大小、卧室数量等等）来预测房价，那么： - 输入（特征）：\(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=\theta^Tx​\)

此时，学习函数（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)} \]

直到收敛

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