Machine Learning Notes 02

Supervised Learning Algorithm

Posted by Wang Zhihao on 2017-03-19

线性回归

线性回归模型

我们用 $x(i)$ 来表示输入变量(input variables),或者叫作输入特征(input features),比如房屋价格预测问题中的居住面积。用 $y(i)$ 来表示我们想要预测的输出变量(output variables),或者叫作目标变量(target variable),在房屋价格预测问题中,房屋的加个就是输出变量。$(x(i),y(i))$ 是一个训练样本(training example),数据集中数据的集合 $(x(i),y(i));i=1,…,m$ 被称为训练集(training set)。我们还用$X$来表示输入样本空间,用 $Y$ 来表示输出样本空间,在房屋价格预测问题中,$X = Y = \mathbb{R}$

下面我们来稍微正式地描述监督学习问题,我们的目标是,给定一个训练集(training set)我们想要去「学习」一个函数/方程 $h: X \rightarrow Y$ 使得 $h(x)$ 是一个对目标变量$y$好的预测。出于一些历史遗留原因,这个方程 $h$ 被称为一个假设(hypothesis)。

img/01.png

$n$元线性回归模型的假设为:
$$y=\theta_0+\theta_1 x_1+\cdots+\theta_n x_n$$

为了方便起见,定义$x_0=1$,则有

$$y=\theta_0+\theta_1 x_1+\cdots+\theta_n x_n = \theta^\mathrm{T}x$$

其中 $x=\left[\begin{matrix}
x_0\\
x_1\\
\vdots\\
x_n
\end{matrix}\right]\in \mathbb{R}^{n+1}$, $\theta=\left[\begin{matrix}
\theta_0\\
\theta_1\\
\vdots\\
\theta_n
\end{matrix}\right]\in \mathbb{R}^{n+1}$

当$n$取1时,假设为$y=\theta_0+\theta_1 x$,这就是一元线性回归的假设。为了方便起见,我们往往从一元线性回归模型出发,最终推广到$n$元。

代价方程(Cost function)

通过代价方程(Cost function)我们可以来度量假设的准确性。代价方程的定义如下:

$$J(\theta_0, \theta_1) = \dfrac {1}{2m} \displaystyle \sum _{i=1}^m \left ( \hat{y}_{i}- y_{i} \right)^2 = \dfrac {1}{2m} \displaystyle \sum _{i=1}^m \left (h_\theta (x_{i}) - y_{i} \right)^2$$

代价方程可以写成 $\dfrac {1}{2} \bar{x}$ 的形式,其中 $\bar{x}$ 是预测值与真实值之差的均方。这个平均值之所以乘以$\dfrac {1}{2}$是为了之后梯度下降法(Gradient descent)计算的方便($\dfrac {1}{2}$可以与平方项求导后得到的$2$抵消)。

梯度下降法

我们已经有了假设方程(hypothesis function)和代价方程(cost function),现在我们需要估计假设方程中的参数,这个时候「梯度下降法」派上用场了。

梯度下降原理:将函数比作一座山,我们站在某个山坡上,往四周看,从哪个方向向下走一小步,能够下降的最快。

一元线性回归模型的梯度下降法算法如下:

重复直到收敛:

$\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta_0, \theta_1)$
其中 $j=0,1$ 表示特征(feature)的下标

特别要注意的一点是,每一次迭代,$\theta_0,\theta_1,…,\theta_n$都应该同时更新:

Correct Incorrect
$temp0:=\theta_0-\alpha \frac{\partial}{\partial \theta_0}J(\theta_0, \theta_1)$ $temp0:=\theta_0-\alpha \frac{\partial}{\partial \theta_0}J(\theta_0, \theta_1)$
$temp1:=\theta_1-\alpha \frac{\partial}{\partial \theta_1}J(\theta_0, \theta_1)$ $\theta_0:=temp0$
$\theta_0:=temp0$ $temp1:=\theta_1-\alpha \frac{\partial}{\partial \theta_1}J(\theta_0, \theta_1)$
$\theta_1:=temp1$ $\theta_1:=temp1$

下面我们考虑$n$元线性回归模型的梯度下降法:

假设方程:$h_\theta(x)=\theta^\mathrm{T}x=\theta_0+\theta_1 x_1+\cdots+\theta_n x_n$

参数:$\theta$ (n+1 - dimensional vector)

代价方程:$J(\theta)=\dfrac{1}{2m}\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^{2}$

梯度下降法算法:

Repeat {
$\theta_j:=\theta_j-\alpha \frac{\partial}{\partial \theta_j}J(\theta)$

} (simultaneously update for every $j=0,\dots,n$)

即:

Repeat {
$\theta_j:=\theta_j- \alpha \frac{1}{m}\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_{j})$

} (simultaneously update $\theta_j$ for every $j=0,\dots,n$)

$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_{0})$

$\theta_1:=\theta_1-\alpha\frac{1}{m}\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_{1})$

$\theta_2:=\theta_2-\alpha\frac{1}{m}\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_{2})$

$\cdots$

实践梯度下降法 I: 特征缩放(Feature Scaling)

特征缩放(Feature Scaling)是为了标准化数据特征的范围,特征缩放也可以加快梯度收敛的速度。

特征缩放还可以使机器学习算法工作的更好。比如在K近邻算法中,分类器主要是计算两点之间的欧几里得距离,如果一个特征比其它的特征有更大的范围值,那么距离将会被这个特征值所主导。因此每个特征应该被归一化,比如将取值范围处理为0到1之间。

  • Mean normalization

实践梯度下降法 II: 学习率(Learning Rate)

梯度下降法 $\theta_j:=\theta_j-\alpha \frac{\partial}{\partial \theta_j}J(\theta)$ 中有一个参数是我们不确定的,它就是$\alpha$——学习率(Learning Rate)。选择一个好的$\alpha$可以使梯度下降法正常地工作。

  • 如果$\alpha$太小:收敛速度太慢。
  • 如果$\alpha$太大:$\theta_j$可能会增大,不会收敛。

如果选择$\alpha$?

尝试不同的值: $…, 0.001, …, 0.01, …, 0.1, …, 1, …$

正规方程(Normal Equation)

正规方程(Normal Equation)是梯度下降法之外的另一种线性回归方法。

梯度下降法是通过数值计算的方法来逐步逼近$\theta$,而正规方程可以通过解析的方法来得到$\theta$.

假设有$m$个样本$(x^{(1)},y^{(1)}),\dots,(x^{(m)},y^{(m)})$, $n$个特征。

$x^{(i)}=\left[\begin{matrix}
x_0^{(i)}\\
x_1^{(i)}\\
x_2^{(i)}\\
\vdots\\
x_n^{(i)}
\end{matrix}\right]\in \mathbb{R}^{n+1}$, $X=\left[\begin{matrix}
(x^{(1)})^{\mathrm{T}}\\
(x^{(2)})^{\mathrm{T}}\\
\vdots\\
(x^{(m)})^{\mathrm{T}}
\end{matrix}\right]=\left[\begin{matrix}
1 & x_1^{(1)} & … & x_n^{(1)}\\
1 & x_1^{(2)} & … & x_n^{(2)}\\
\vdots & \vdots & & \vdots\\
1 & x_1^{(m)} & … & x_n^{(m)}
\end{matrix}\right]$

$$\theta=(X^{\mathrm{T}}X)^{-1}X^{\mathrm{T}}y$$

其中 $(X^{\mathrm{T}}X)^{-1}$是$(X^{\mathrm{T}}X)$的逆。

梯度下降法与正规方程的区别如下:

Gradient Descent Normal Equation
需要选择$\alpha$ 不需要选择$\alpha$
需要迭代 不需要迭代
$O(kn^2)$ $O(n^3)$ 需要计算$(X^\mathrm{T}X)^{-1}$
$n$很大时依然可以使用 $n$很大时就会很慢

关于正规方程与不可逆性

$$\theta=(X^{\mathrm{T}}X)^{-1}X^{\mathrm{T}}y$$

如果$\theta=X^{\mathrm{T}}X$不可逆(non-invertible / singular / degenerate)怎么办?

  • 共线性
    • 比如$x_1$= size in feet和$x_2$= size in $m^2$
  • 特征太多
    • 比如 $m \geq n$. 删除一些特征,或者使用正则化(之后会讨论)。

Logistic 回归

分类问题

  • $y \in {0,1}$ (也可以是 $y \in {0,1,2,…}$ )
  • 阈值分类器 $h_\theta(x) \geq 0.5$, 预测 $y=1$; $h_\theta(x) < 0.5$, 预测 $y=0$.
  • $h_\theta(x)$ 可以大于1或小于0. 对于 Logistic 回归,$0 \leq h_\theta(x) \leq 1$

Logistic 回归模型

$$h_\theta(x)=g(\theta ^\mathrm{T}x)$$
$$g(z)=\dfrac{1}{1+e^{-z}}$$

$$h_\theta(x)=\dfrac{1}{1+e^{-\theta ^\mathrm{T}x}}$$

$h_\theta(x)$是基于样本 $x$ 对 $y=1$ 的概率的估计,即$h_\theta(x)=P(y=1|x;\theta)$.

决策边界(Decision Boundary)

$h_\theta(x)=g(\theta ^\mathrm{T}x)$

Predict $y=1$ if $\theta ^\mathrm{T}x \geq 0$

决策边界(Decision Boundary)就是$\theta ^\mathrm{T}x \geq 0$,可以是线性的,也可以是非线性的。

代价方程(Cost Function)

训练样本:${(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(m)},y^{(m)})}$

$x=\left[\begin{matrix}
x_0\\
x_1\\
\vdots\\
x_n
\end{matrix}\right]\in \mathbb{R}^{n+1}, x_0=1, y={0,1}$

$h_\theta(x)=\dfrac{1}{1+e^{-\theta ^\mathrm{T}x}}$

代价方程:
$$J(\theta)=\dfrac{1}{m}\sum\limits_{i=1}^{m}Cost(h_\theta(x^{(i)}), y)$$

$$Cost(h_\theta(x), y)=\begin{cases}
-\log(h_\theta(x))& if \ y=1\\
-\log(1-h_\theta(x))& if \ y=0
\end{cases}$$

高级最优化方法

最优化方法

已知代价方程$J(\theta)$,想要得到$\min_\theta J(\theta)$.

给定$\theta$,我们可以计算出$J(\theta)$和$\frac{\partial}{\partial \theta_j} J(\theta)$

这是我们之前介绍过的梯度下降法

Repeat {
$\theta_j:=\theta_j-\alpha \frac{\partial}{\partial \theta_j}J(\theta)$

} (simultaneously update for every $j=0,\dots,n$)

但其实还有一些算法可以得到$\theta$:

  • Conjugate gradient
  • BFGS
  • L-BFGS

  • 优点

    • 不需要人工选择 $\alpha$
    • 一般比梯度下降法速度快
  • 缺点
    • 更加复杂

正则化(Regularization)

过拟合问题(Overfitting Problem)

img/02.png img/03.png

Overfitting: If we have too many features, the learned hypothesis may fit the training set very well ($J(\theta)=\frac{1}{2m}\sum\limits_{i=1}^{m}Cost(h_\theta(x^{(i)})-y^{(i)})^2 \approx 0$
), but fail to generalize to new examples.

解决方案:

  1. 减少特征的数量
    • 人工选择需要留下的特征
    • 模型选择算法
  2. 正则化
    • 保留所有的特征,但是降低参数的值。当我们有很多特征,且每一个特征都对预测$y$有贡献的时候,正则化的表现是很好的。

代价方程(Cost function)

img/04.png

$$J(\theta)=\dfrac{1}{2m}\left[\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2 + \lambda \sum\limits_{i=1}^{n} \theta_{j}^{2}\right]$$

$\lambda$: 正则化参数(Regularization parameter)

线性回归的正则化

$$J(\theta)=\dfrac{1}{2m}\left[\sum\limits_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2 + \lambda \sum\limits_{i=1}^{n} \theta_{j}^{2}\right]$$

$$\min \limits_{\theta} J(\theta)$$

我们对共轭梯度法稍作调整,把$\theta_0$与其它的参数分开,因为我们不想对$\theta_0$进行处罚(penalize).

$$\begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2…n\rbrace\newline & \rbrace \end{align*}$$

加入的$\frac{\lambda}{m}\theta_j$实现了正则化。对参数的更新规则稍作整理:

$\theta_j := \theta_j(1 - \alpha\frac{\lambda}{m}) - \alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}$

上式的第一项 $1 - \alpha\frac{\lambda}{m}$ 永远小于1. 直觉上你可以看到$\theta_j$的值会随着每次更新而减小;上式的第二项与之前是完全一样的。

正规方程

$\begin{align*}& \theta = \left(X^TX + \lambda \cdot L \right)^{-1} X^Ty \newline& \text{where}\ \ L = \begin{bmatrix} 0 & & & & \newline & 1 & & & \newline & & 1 & & \newline & & & \ddots & \newline & & & & 1 \newline\end{bmatrix}\end{align*}$

若 $m \leq n$, 则$X^\mathrm{T}X$ 是不可逆的. 然而,我们增加了$\lambda⋅L$这一项后,$X^\mathrm{T}X+\lambda⋅L$就是可逆的了。

Logistic 回归的正则化

Logistic 回归的代价方程为:
$$J(\theta) = - \dfrac{1}{m} \sum\limits_{i=1}^m \large[y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)})) \large]
$$

Logistic 回归的正则化:
$$J(\theta) = - \dfrac{1}{m} \sum\limits_{i=1}^m \large[ y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)}))\large] + \frac{\lambda}{2m}\sum_{j=1}^n \theta_j^2$$

共轭梯度算法:
$$\begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2…n\rbrace\newline & \rbrace \end{align*}$$

$$h_\theta(x)=\dfrac{1}{1+e^{-\theta ^\mathrm{T}x}}$$

神经网络

(#08)

支持向量机

(#12)