keep moving

机器学习

Posted on Jul 18, 2014 By condy

some are stolen from jiyeqian

机器学习

  • Definition:
    • (1959) Machine learning is the field of study that gives computers the ability to learn without being explicitly programmed.
    • (1998) A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

它可以用于数据挖掘、手写识别、自然语言处理、计算机视觉、推荐系统等等。

线性回归

监督学习：对于每个例子给出正确的答案。

回归问题：预测下一次的输出。

回归函数：

\[\begin{equation} h_\theta(x) = \theta^Tx = \theta_0x_0 + \theta_1x_1 + \cdots + \theta_nx_n \end{equation}\]

常数项 $ x_0 = 1 $ 线性回归模型也可以用于多项式回归（polynomial regression），例如当$ x_1 = x, x_2 = x^2, x_3 = x^3, \ldots $时。

代价函数： \begin{equation} J(\theta) = \frac{1}{2m}\sum_{i=1}^{m}{\left(h_{\theta}\left(x^{(i)}\right) - y^{(i)}\right)^2} \label{cost_function_linear_regresion} \end{equation}

$m$为样本数量， $n$为特殊数量。

这里我们要选择最合适的$\theta_0, \theta_1, \theta_2, \cdots$，使得Cost Function最小。

梯度下降法

这算是一种搜索算法，总体思路就是从某$\theta_0, \theta_1, \theta_2, \cdots$开始，改变$\theta$的值来减小$J(\theta)$直到到达一个较好的最小值。

Repeat { \[ \theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta)~~~~~~(j = 0, 1, \ldots, n) \] }

将$\frac{\partial}{\partial\theta_j}J(\theta)$展开得到： \(\begin{align*} \frac{\partial}{\partial\theta_j}J(\theta) &= \frac{1}{m}\sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)\frac{\partial}{\partial\theta_j}\left(\sum_{k=0}^{m}{\theta_k{x_k^i}} - y^{(i)}\right) \\ &= \frac{1}{m}\sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_j^{(i)} \end{align*}\)

代入得到

Repeat {

\begin{equation} \theta_j := \theta_j - \alpha\frac{1}{m}\sum_{i=1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_j^{(i)}~~~~~~(j = 0, 1, \ldots, n) \label{eq:linear_regression_gradient_descent} \end{equation}

}

$\alpha$是学习率，选得太小会导致$J(\theta)$收敛太慢，太大可能会错过极值点，不能收敛甚至有可能会发散。

其中有些数据的取值范围相差太多，所以就有了Regularize，其目标是要将数据的范围限定在$[-0.5, 0.5]$，这样梯度下降会较快地收敛。

常用的方法有2种：

\[ \hat {x_i} = \frac{x_i - x_{mean}}{x_{max} - x_{min}} \]

\[ \hat {x_i} = \frac{x_i - x_{mean}}{x_{std}} \]

此外还可以用normal equations来求解。

某些需要预先知道的东西～

对于一个函数$f: R^{m \times n} $ -> R，定义它的导数为：

\[\begin{align*} & \nabla_A{f(A)} = \left[ \begin{array}{ccc} \frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{m1}} & \cdots & \frac{\partial f}{\partial A_{mn}} \end{array} \right] \end{align*}\]

还引入trace操作，写作tr。对于一个$n \times n$的矩阵$A$来说，A的trace被定义为它的对角线上的数字之和。

\[tr A = \sum_{i=1}^{n}{A_{ii}}\]

如果A是一个实数（即1x1的矩阵），则A的trA＝A

还有如下性质：

\[tr ABC = tr CAB = tr BCA\] \[tr ABCD = tr DABC = tr CDAB = tr BCDA\] \[tr A = tr A^T\] \[tr(A + B) = tr A + tr B\] \[tr aA = a tr A\] \[\nabla_AtrAB = B^T\] \[\nabla_{A^T}f(A) = \left(\nabla_Af(A)\right)^T\] \[\nabla_{A} tr ABA^TC = CAB + C^TAB^T\] \[\nabla_{A} | A | = | A | \left(A^{-1}\right)^T\]

上方公式的简单推导过程可见这里。

有了上面这些的基础，就可以开始推导了。

\[\begin{align*} \nabla_\theta J\left(\theta\right) &= \nabla_\theta\frac{1}{2}\left(X\theta - \vec{y}\right)^T\left(X\theta - \vec{y}\right) \\ &= \frac{1}{2}\nabla_\theta\left(\theta^TX^TX\theta - \theta^TX^T\vec{y} - \vec{y}^TX\theta + \vec{y}^T\vec{y}\right) \\ &= \frac{1}{2}\nabla_\theta tr\left(\theta^TX^TX\theta - \theta^TX^T\vec{y} - \vec{y}^TX\theta + \vec{y}^T\vec{y}\right) \\ &= \frac{1}{2}\nabla_\theta\left(tr \theta^TX^TX\theta - 2tr \vec{y}^TX\theta\right) \\ &= \frac{1}{2}\left(X^TX\theta + X^TX\theta - 2X^T\vec{y}\right) \\ &= X^TX\theta - X^T\vec{y} \end{align*}\]

为了使$J\left(\theta\right)$最小，令$\nabla_\theta J\left(\theta\right) = 0$，即

\begin{equation} \theta = \left(X^TX\right)^{-1}X^T\vec{y} \end{equation}

当$X^TX$不可逆时，

  • 使冗余数据线性相关
  • 特征数目过多，删除过多的特征或者应用接下来的正则化(regularize)
Gradient Descent（梯度下降） Normal Equation
需要学习因子$\alpha$ 不需要$\alpha$
需要迭代计算 不需要
当特征数$n$很大时工作良好 $n$很大时速度慢

逻辑回归

逻辑回归用于二分类的问题，其回归函数值只能取${0, 1}$。其回归模型：

\begin{equation} h_\theta(x) = g\left(\theta^Tx\right) \end{equation}

若$h_\theta(x) \ge 0.5$，则$y = 1$; 若$h_\theta(x) < 0.5$, 则$y = 0$。 其中\(g\left(z\right) = \frac{1}{1 + e^{-z}}\)

$g\left(z\right)$被称为sigmoid function, logistic function。它有一个非常美妙的性质: $g’(z) = g(z)\left(1 - g(z)\right)$

让我们来参想一下

\[\begin{align*} P(y = 1|x; \theta) &= h_\theta(x) \\ P(y = 0|x; \theta) &= 1 - h_\theta(x) \end{align*}\]

由观察发现，这个还可以写成$P(y|x; \theta) = \left(h_\theta(x)\right)^y + \left(1-h_\theta(x)\right)^{1-y}$

假设$m$组训练数据都是独立的，则计算似然值得到

\[\begin{align*} L\left(\theta\right) &= P(\vec{y}|X; \theta) \\ &= \prod_{i=1}^{m}P\left(y^{(i)}|x^{(i)}; \theta\right) \\ &= \prod_{i=1}^{m}\left(h_\theta(x^{(i)})\right)^{y^{(i)}} + \left(1-h_\theta(x^{(i)})\right)^{1-y^{(i)}} \end{align*}\]

注意到其有指数，可以取对数来简化运算，得到：

\[\begin{align*} \ell(\theta) &= \log L\left(\theta\right) \\ &= \sum_{i=1}^{m}y^{(i)}\log\left(h_\theta(x^{(i)})\right)+(1-y^{(i)})\log\left(1-h_\theta(x^{(i)})\right) \end{align*}\]

通过梯度下降来极大化$\ell(\theta)$

$\vec{\theta} := \vec{\theta} + \nabla_\vec{\theta} \ell(\vec{\theta})$

\[\begin{align*} \frac{\partial}{\partial \theta_j}\ell(\theta) &= \left(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)}\right)\frac{\partial}{\partial \theta_j} g(\theta^Tx) \\ &= \left(y\frac{1}{g(\theta^Tx)} - (1-y)\frac{1}{1-g(\theta^Tx)}\right)g(\theta^Tx)(1-g(\theta^Tx))\frac{\partial}{\partial \theta_j}\theta^Tx \\ &= \left(y(1-g(\theta^Tx)) - (1-y)g(\theta^Tx)\right)x_j \\ &= \left(y-h_\theta(x)\right)x_j \end{align*}\]

由此得到了梯度下降的公式：

$\theta_i := \theta_i + \alpha\sum_{i=1}^{m}\left(y^{(i)}-h_\theta(x)\right)x_j^{(i)}$

化简一下就变成了线性回归时的梯度下降公式\eqref{eq:linear_regression_gradient_descent}，只是里面$h_\theta(x)$的含意变了。

选择对数似然损失函数作为Cost Function.即：

\begin{equation} J(\theta) = -\frac{1}{m}\sum_{i=1}^{m}\left(y^{(i)}\log h_\theta\left(x^{(i)}\right) + \left(1 - y^{(i)}\right)\log \left(1 - h_\theta\left(x^{(i)}\right)\right)\right) \end{equation}

另外一种方法

$\ell(\theta)$必定有最大值，则其$\ell’(\theta)$必有零点。则可以运用Newton法来求解，它收敛的速度比较快。

$\theta := \theta - \frac{\ell’(\theta)}{\ell’’(\theta)}$

其他优化算法：

  • Conjugate gradient
  • BFGS
  • L-BFGS

其他优化算法不需要$\alpha$学习因子，但是较复杂。（PS：一般高效的算法哪个不复杂？）

处理多分类问题

  • 针对第一类训练一个logistic 分类器$h_\theta^{(i)}(x)$, 这是第$i$类与其他类别的二分类问题。
  • 新输入$x$所属的类别满足$\max_ih_\theta^{(i)}(x)$（属于概率最大的那个类别）。

正则化 (Regularization)

overfitting: 对于训练集拟合较完全，但不适合新的数据。

如何解决？

  • 减少特征数目
  • 正则化，减小$\theta_j$对$y$的贡献。

underfitting: 对于训练拟合不完全。

如何解决？

  • 可增加1个特征来增加拟合度。

just right: 这个是最棒的！

如何解决？

  • 最好的拟合！能够达到这个就最好了。

正则化线性回归

Cost Function:

\begin{equation} J(\theta) = \frac{1}{2m}\left(\sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)^2 + \lambda\sum_{j=1}^n\theta_j^2\right) \end{equation}

增大$\lambda$来减小$\theta$的贡献度以减小overfitting; 但是,$\lambda$如果太大（$10^{10}$），有$\theta_j\approx 0~~(j = 1,2,\ldots,n)$, 则$h_\theta(x) = \theta_0$, 这会导致underfitting.

梯度下降法：

Repeat {

\[\begin{align*} \theta_0 &:= \theta_0 - \alpha\frac{1}{m}\sum_{i=1}\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_0^{(i)} \\ \theta_j &:= \theta_j - \alpha\frac{\partial}{\partial \theta_j}J(\theta)~~~~~~(j = 1,2,\ldots, n) \end{align*}\]

}

正则化只作用于非常数项。

正则化逻辑回归

Cost Function:

\begin{equation} J(\theta) = -\frac{1}{m}\sum_{i=1}^{m}\left(y^{(i)}\log h_\theta\left(x^{(i)}\right) + \left(1-y^{(i)}\right)\log \left(1-h_\theta\left(x^{(i)}\right)\right)\right) + \frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2 \end{equation}

梯度下降法：

Repeat {

\[\begin{align*} \theta_0 &= \theta_0 - \alpha\frac{1}{m}\sum_{i=1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_0^{(i)} \\ \theta_j &= \theta_j - \alpha\frac{\partial}{\partial \theta_j}J(\theta)~~~~~~(j = 1,2, \ldots, n) \end{align*}\]

}

实现的时候坐标是从1开始的，所以$\ldots$

神经网络

神经网络是一个巨复杂的东西，具体是啥我也不知道啦。

代价函数

\[\begin{equation} \begin{aligned} J(\theta) = -\frac{1}{m} \sum\_{i=1}^{m}\sum\_{k=1}^{K}\left(y\_k^{(i)}\log\left(h\_\theta\left(x^{(i)}\right)\right)\_k + \left(1-y\_k^{(i)}\right)\log\left(1-\left(h\_\theta\left(x^{(i)}\right)\right)\_k\right)\right) \\\ + \frac{\lambda}{2m} \sum\_{l=1}^{L-1}\sum\_{i=1}^{s\_l}\sum\_{j=1}^{s\_{l+1}}\left(\theta\_{ji}^{(l)}\right)^2 \end{aligned} \end{equation}\]

别看上面这个公式这么复杂，其实它只是在求对于m个数据而言K个分类器造成的误差再加上Regularized项。

$h_\theta(x) \in \mathbb{R}^K$, $(h_\theta(x))_i$是第$i$个输出;$s_l$表示第$l$层神经元的个数(不含bias unit);共$m$组训练数据，$K$个输出，$L$层。

参数估计方法

\[ \min_\theta J(\theta) \]

反向传播(BackPropagation algorithm)

依旧是经典的梯度下降法：

\[\theta_{ij}^{l} = \theta_{ij}^{l} - \alpha \frac{\partial}{\partial\theta_{ij}^{l}}J(\theta)\]

$\alpha$还是如前文所说的学习因子，这里比较「关键」的是$\frac{\partial}{\partial\theta_{ij}^{l}}J(\theta)$

现在利用反向传播算法来求它，它是一种计算偏导数的有效方法。关于这算法的具体思路可参考这里和这里。

由于ml课程上用的Cost Function比较复杂（相对于方差代价函数而言），还是按照BP的思路来推导一下。

$\frac{\partial}{\partial\theta_{ij}^{l}}J(\theta) = \frac{1}{m}\sum_{i=1}^{m}{\frac{\partial}{\partial\theta_{ij}^{l}}J(\theta;x,y)} + \frac{\lambda}{m}\theta_{ij}^{l}$，关键就在$\frac{\partial}{\partial\theta_{ij}^{l}}J(\theta;x,y^i)$.

$J(\theta;x,y)=y log\left(f(x)\right)+(1-y)log\left(1-f(x)\right)$

使用反向传播的时候到啦。首先计算出输出层的残差：

\[\delta_{i}^{l} = -\frac{\partial}{\partial z_{i}^{l}}J(\theta;x,y) = -\frac{f'(z_i^l)(y-f\left(z_i^l\right))}{f(z_i^l)\left(1-f(z_i^l)\right)} = f(z_i^l) - y\]

再计算输出层(l)的前一层残差(l-1):

\[\begin{align*} \delta_{i}^{l-1} &= -\frac{\partial}{\partial z_{i}^{l-1}}J(\theta;x,y) = -\sum_{j=1}^{N}{\frac{y_j-a_j^l}{a_j^l(1-a_j^l)}\frac{\partial a_j^l}{\partial z_i^{l-1}}} \\ &= -\sum_{j=1}^{N}{\frac{y_j-a_j^l}{a_j^l(1-a_j^l)}\frac{\partial f(z_j^l)}{\partial z_i^{l-1}}} = -\sum_{j=1}^{N}{\frac{y_j-a_j^l}{a_j^l(1-a_j^l)}\frac{\partial f(z_j^l)}{\partial z_j^l}\frac{\partial z_j^l}{\partial z_i^{l-1}}} \\ &= -\sum_{j=1}^{N}{\frac{y_j-a_j^l}{a_j^l(1-a_j^l)}f'(z_j^l)\frac{\partial z_j^l}{\partial z_i^{l-1}}} = -\sum_{j=1}^{N}{\left(y_j-a_j^l\right)\frac{\partial z_j^l}{\partial z_i^{l-1}}} \\ &= -\sum_{j=1}^{N}{\left(y_j-a_j^l\right)\frac{\partial}{\partial z_i^{l-1}}\sum_{k=1}^{M}\theta_{jk}^{l-1}a_k^{l-1}} = -\sum_{j=1}^{N}{\left(y_j-a_j^l\right)\frac{\partial \theta_{ji}^{l-1}f(z_i^{l-1})}{\partial z_i^{l-1}}} \\ &= \sum_{j=1}^{N}{\delta_j^l\theta_{ji}^{l-1}f'(z_i^{l-1})} \end{align*}\]

f(x)为sigmoid函数。

由此可得$\delta_i^l$与$\delta_j^{l+1}$的关系：

\[\delta_i^l = \left(\sum_{j=1}^{N}\theta_{ji}^l\delta_j^{l+1}\right)f'(z_i^l)\]

综上所述，各层误差估计为：

\begin{equation} \delta^{(l)} = \left\{ \begin{aligned} & a^{(l)} - y & (l = L)~~~~~~~~~~~~~~~~~~~~~~~~~~~ \
& \left(\theta^{(l)}\right)^T\delta^{(l+1)}.*f’\left(z^{(l)}\right) & (l = L-1, L-2, \ldots, 2) \end{aligned} \right. \label{eq:error_bp} \end{equation}

由于$\theta_{ij}^{l-1}$只能影响到$z_i^{l}$,所以$\frac{\partial}{\partial \theta_{ij}^l}J(\theta;x,y)=a_j^l \delta_i^{l+1}$

Now, put it together!

训练数据$\left\{\left(x^{(1)}, y^{(1)}\right), \ldots, \left(x^{(m)}, y^{(m)}\right)\right\}$

初始化:$\delta_{ij}^{(l)} = 0$ for all $i,j,l$

for i in [1, m]:

  1. $a^{(1)} = x^{(i)}$
  2. 前向传播得到$a^{(l)}~~(l = 2, 3, \ldots, L)$
  3. 利用\eqref{eq:error_bp}反向传播计算误差
  4. $\Delta^{(l)} += \Delta^{(l+1)}\left(a^{(l)}\right)^T$
  5. 计算$D_{ij}^{(l)} = \frac{\partial}{\partial \Theta_{ij}^{(l)}}J(\theta)$:
\[\begin{aligned} D_{ij}^{(l)} & = \frac{1}{m}\Delta_{ij}^{(l)} + \frac{\lambda}{m}\Theta_{ij}^{(l)} & (j \neq 0) \\ D_{ij}^{(l)} & = \frac{1}{m}\Delta_{ij}^{(l)} & (j = 0) \end{aligned}\]

注意，上面的公式均是向量化的。

梯度检查

当进行反向传播时可能会因为各种错误造成梯度的误差，可以应用「梯度检查」来检查是否发生错误(感觉好绕口…).

\[\frac{\partial}{\partial \theta_{ij}^l}J(\theta)\approx \frac{J\left(\theta (where \theta_{ij}^l=\theta_{ij}^l+\epsilon)\right) - J\left(\theta (where \theta_{ij}^l=\theta_{ij}^l-\epsilon)\right)}{2\epsilon}\]

随机初始化

因为不可将$\theta_{ij}^l$都初始化为0,因而取胜随机化的方法，可取范围为$[-\epsilon, \epsilon]$,选择$\epsilon$的有效策略是根据每层神经元数目$\epsilon=\frac{\sqrt{6}}{\sqrt{L_{in}+L_{out}}}~(L_{in} = s_l,L_{out}=s_{l+1})$.