Cs229学习笔记

Published: by Creative Commons Licence

  • Tags:

基本流程

将训练数据(training set)喂给某个学习算法(learning algorithm),之后算法计算出一个假说(hypothesis),$h$。之后对于给定的输入$x$,假说会估算出来结果$h(x)$。

现在的问题是该如何表示一个假说$h$。

我们记录$n$为输入向量的长度,$k$为训练集的大小。因此训练集可以表示为$(x^{(1)},y^{(1)}),\ldots,(x^{(k)},y^{(k)})$。其中每个元素$(x^{(i)},y^{(i)})$叫做一个训练样本。

如果我们有多个假说,我们还需要设计一套误差计算的函数$D$,$h$在第$i$个样本上的误差为$D(h(x^{(i)})-y^{(i)})$。而在所有训练集上的总误差一般为$J(h)=\sum_{i=1}^kD(h(x^{(i)})-y^{(i)})$。这样我们就能比较两个不同的假说的优劣了。

线性回归(linear regression)

在线性回归中,假说$h(x)=ax+b$,即一个仿射函数。

举个例子。通过房子的信息,我们要估算房子的价格。其中$x$是一个长度为$2$的列向量$(size_of_house, number_of_bedrooms)$,而$a$则是一个$1\times 2$的矩阵,$b$是一个实数。为了让公式更加紧凑,我们可以将$x$增加一个维度,增加的维度的值始终是一个守护值$1$,这样我们就可以将假说重写为$h(x)=\theta x$,一个线性函数。

线性回归算法的目标就是为你选择合适的$A$来产生尽可能精确的结果。

线性回归中,误差函数一般为$D(v)=\frac{1}{2}|v|^2$,即离原点的距离的平方。

梯度下降(gradient descent)

梯度下降是用来寻找假说中系数$\theta$的算法。

我们可以从任意一个随机向量$\theta$出发。之后让

\[\theta_{i}:=\theta_{i}-\frac{\partial J}{\partial \theta_{i}}(\theta)\cdot J(\theta)\cdot \alpha\]

其中$\alpha$是一个常量,称为学习率(learning rate),决定了学习的速率。

下面推导一下偏导数:

\[\begin{aligned} \frac{\partial J}{\partial \theta_{i}}(\theta)&=\frac{\partial}{\partial \theta_{i}}\sum_{t=1}^kD(\theta x^{(t)}-y^{(t)})\\ &=\frac{1}{2}\frac{\partial}{\partial \theta_{i}}\sum_{t=1}^k(\theta x^{(t)}-y^{(t)})^2\\ &=\frac{1}{2}\sum_{t=1}^k 2(h(x^{(t)})-y^{(t)})x^{(t)}_i\\ &=\sum_{t=1}^k (h(x^{(t)})-y^{(t)})x^{(t)}_i \end{aligned}\]

在线性回归模型中,只有唯一的极小值点,因此不会陷入局部最小值的情况。

上面的方法成为批量梯度下降(batch gradient descent)。在训练集非常大的情况下,由于批量梯度下降每一轮迭代都需要遍历整个训练集,因此会非常慢。

还有一种方法叫做随机梯度下降(stochastic gradient descent)。具体做法就是遍历整个训练集,但是对于每个单独的训练集元素都执行一轮迭代(即可以认为每次迭代的时候$k=1$)。其最后还是会停止在全局最小值处。

随机梯度下降也不是完美的,较少的错误数据或噪音可能对结果造成很大的影响。我们可以在随机梯度下降的过程中加入优化,比如每次一次性取$100$条记录来训练(每次迭代的时候$k=100$),这样就能避免噪音带来的影响,同时训练的速度也非常快。这种方法叫做微批量梯度下降(Mini-batch gradient descent)。

除了梯度下降外,线性回归问题,我们可以不需要多次迭代,通过矩阵运算即可直接求出解。具体我们可以发现在全局最小值处,$J$的导数矩阵应该是个$0$矩阵。这时候可以发现我们可以将问题写成线性方程组,并最后通过高斯消元求解$A$。

局部加权回归(locally weighted regression)

线性回归存在一个问题,就是如果图像是曲线或者存在$\ln x$或$x^2$这种形式的关系,那么线性回归是无法预测出一个合理的模型的。

局部加权回归能帮助我们在求解某个$h(x)$的时候,使用一个带权的惩罚函数,某个训练集中样本的权值大小与这个训练集的输入与$x$的距离成反比。第$i$个样本的权值的具体公式为:

\[w^{(i)}=\exp(-\frac{(x^{(i)}-x)^2}{2\tau})\]

其中$\tau$是预先选择的常量,它的大小会影响实际作用的训练样本,同时也会影响我们的训练是否会过拟合。

而惩罚函数的公式为:

\[J(h)=\sum_{i=1}^m w^{(i)}D(h(x^{(i)})-y^{(i)})\]

直观看,如果样本$i$的输入与$x$非常接近,那么其权重将接近$1$,而如果样本$i$的输入离$x$非常远,则其权重接近于$0$。

逻辑回归(logistic regression)

如果$h$的值域为${0,1}$,那么这样的问题称为分类问题。

逻辑回归的假说形式为$h(x)=g(\theta x)=\frac{1}{1+e^{-\theta x}}$。它是一个递增函数,且值域为$[0,1]$。

我们可以理解$h(x)$表示$p(y=1|x;\theta)$,即给定系数$\theta$,对于输入$x$,输出为$1$的概率。

考虑到$y\in{0,1}$,因此我们可以得出

\[p(y|x;\theta)=h(x)^y(1-h(x))^{1-y}\]

根据最大似然估计,得出:

\[\begin{aligned} l(\theta)&=p(y|x;\theta)\\ &=\prod_{i=1}^kp(y^{(i)}|x^{(i)};\theta)\\ &=\prod_{i=1}^kh(x^{(i)})^{y^{(i)}}(1-h(x^{(i)}))^{1-y^{(i)}} \end{aligned}\]

其对数形式为:

\[\begin{aligned} \ln l(\theta) &= \ln \prod_{i=1}^kh(x^{(i)})^{y^{(i)}}(1-h(x^{(i)}))^{1-y^{(i)}}\\ &= \sum_{i=1}^k y^{(i)}\ln h(x^{(i)})+(1-y^{(i)})\ln(1-h(x^{(i)})) \end{aligned}\]

我们希望最大化$l(\theta)$,等价于最大化$\ln l(\theta)$。

梯度下降

记$J(h)=\ln l(\theta)$,我们需要最大化$J(h)$:

\[\theta_{i}:=\theta_{i}+\frac{\partial J}{\partial \theta_{i}}(\theta)\cdot \alpha\]

其中

\[\begin{aligned} \frac{\partial J}{\partial \theta_i}(\theta)&=-\sum_{t=1}^k (h(x^{(t)})-y^{(t)})x^{(t)}_i \end{aligned}\]

可以发现逻辑回归和线性回归的递推公式是相同的。

牛顿法

使用一般的大步小步走算法会导致我们的轮数非常多。牛顿法可以减少这样的轮次。

牛顿法用于计算某个函数$f$的零点的$x$值,其具体方法就是随机一个初始的$x^{(0)}$。之后不断找到$f$在上一轮点处的切线与$x$轴的交点,将它作为这一轮的点$x^{(t)}$。具体公式为

\[x^{(t+1)}=x^{(t)}-\frac{f(x^{(t)})}{f'(x^{(t)})}\]

上面讨论的是$x$是实数的情况,如果$x$是某个向量$\theta$,则迭代公式为:

\[\theta^{(t+1)}=\theta^{(t)}+H^{-1}\frac{\Delta f(\theta^{(t)})}{\Delta \theta^{(t)}}\]

其中$H_{i,j}=\frac{\partial f}{\partial \theta_i \partial \theta_j}(\theta^{(t)})$

牛顿法需要我们处理很大的矩阵(长宽均为特征数),需要很大的计算量。因此对于特征较少的模型比较好用。

指数族(Exponential family)

如果一个概率分布$f_X(x;\eta)$满足下面公式:

\[f_X(x;\eta)=b(x)\exp[\eta \cdot T(x)-A(\eta)]\]

则称该概率分布属于指数族$\eta$。

比如伯努利分布,正态分布等都属于指数族。

指数族有一些很好的性质:

  • $E(x;\eta)=\frac{\partial}{\partial \eta}A(x)$
  • $\mathrm{Var}(x;\eta)=\frac{\partial^2}{\partial \eta^2}A(\eta)$

如果$\eta$是向量,则$E(x;\eta)$也是向量,而$\mathrm{Var}(x;\eta)$是黑塞(hessian)矩阵。

我们希望最大化MLE,即