Machine Learning

| 分类 note  | 标签 ml 

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)$展开得到:

代入得到

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,定义它的导数为:

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

如果A是一个实数(即1x1的矩阵),则A的trA=A

还有如下性质:

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

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

为了使$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)$被称为sigmoid function, logistic function。它有一个非常美妙的性质: $g’(z) = g(z)\left(1 - g(z)\right)$

让我们来参想一下

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

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

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

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

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

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

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

}

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


正则化逻辑回归

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 {

}

实现的时候坐标是从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)

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

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

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

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

f(x)为sigmoid函数。

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

综上所述,各层误差估计为:

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

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


梯度检查

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


随机初始化

因为不可将$\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})$.


上一篇     下一篇