机器学习

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.

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

线性回归

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

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

回归函数：

h_{θ} (x) = θ^{T} x = θ_{0} x_{0} + θ_{1} x_{1} + \dots + θ_{n} x_{n}

$\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$ :

$a^{(1)} = x^{(i)}$
前向传播得到 $a^{(l)}~~(l = 2, 3, \ldots, L)$
利用 $\eqref{eq:error_bp}$ 反向传播计算误差
$\Delta^{(l)} += \Delta^{(l+1)}\left(a^{(l)}\right)^T$
计算 $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})$ .

keep moving

目录

机器学习

线性回归

梯度下降法

逻辑回归

另外一种方法

处理多分类问题

正则化 (Regularization)

正则化线性回归

正则化逻辑回归

神经网络

代价函数

参数估计方法

梯度检查

随机初始化