Cs229学习笔记

Published: September 12, 2020 by Daltao

• Categories:
• learn-note 1

• Tags:

• 基本流程
• 线性回归(linear regression)
  • 梯度下降(gradient descent)
• 局部加权回归(locally weighted regression)
• 逻辑回归(logistic regression)
  • 梯度下降
  • 牛顿法
• 指数族(Exponential family)

基本流程

将训练数据(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，即