AndrewNg MachineLearning 学习笔记 03

第三课 局部加权回归和 Logistics 回归

1. 摘要

本课中，Ng 教授首先讲了欠拟合(underfitting)和过拟合(overfitting)的概念，然后在线性回归的基础上扩展出了局部加权回归模型。接着插播了一段为何选用最小二乘的原因。最后，介绍了本课第一个分类算法——Logistics 回归。最最后，简单介绍了一下感知器算法。

2. 欠拟合和过拟合

对于一个机器学习模型来说，最理想的结果是算法在训练集和未遇到的输入上都有良好的表现，这样的模型我们是放心用来预测未来的。但事情总没那么简单，当模型不能很好地对未知输入进行预测，通常来说，欠拟合和过拟合是最重要的两个原因。

2.1 欠拟合

欠拟合的概念比较好理解，我们仍然以 Oregon 地区的房价为例。横轴代表房子的 size，纵轴代表房价。如果我们使用线性拟合，则可以得到如下一条直线

2.2 过拟合

如果继续上面的过程，我们用更高次的函数对房价趋势进行预测，比如一个 6 次函数(因为图中有 6 个点)，那么我们就可以得到一条完美穿过所有训练集曲线，它十有八九长成如下样子

2.3 一个神比喻

总的来说，欠拟合和过拟合，都会造成模型在预测未知数据时的表现不理想。在这个问题上有个比喻很有意思：建模的过程就像是学习，欠拟合就如那些不努力也不聪明的人，不管是平时作业或是考试都没法取得好成绩，而过拟合就像那些只知道背例题答案的人，也许他们可以在作业中拿到满分，但在考试中对题目稍加改动，这些人就会不知所措了。

3. 局部加权回归

3.1 非参数学习算法

我们上次介绍过的线性回归算法，属于参数学习算法，因为我们首先用一个训练集，确定了\(\theta\)，至此，我们在预测非训练集数据时，都是用的相同的\(\theta\)，因此，模型的选择就显得非常重要，如果遇到图像类似高斯函数的钟形曲线或其他非常规的曲线，我们的工作可能就是一直在猜测模型的参数，除了多项式还可能加入如 sin 或 cos 的等元素，而这样的无尽的猜测对我们建模的效率会有很大影响。相对地，非参数学习算法，直观上来说，其参数是随着训练集的大小线性增长的，其模型是随着数据变化而变化，因此我们就不需要做那些猜测模型的工作了。局部加权回归就是非参数学习算法的一种。

3.2 局部加权回归思路

局部加权回归的思路非常简单，假设我们想预测的数据位于 x，则我们只需要考虑 x 附近的训练集，然后对这一部分的训练样本做线性回归。下面我们用一个具体例子做一个解释。

首先我们收集了一组数据作为训练样本，其分布如下图所示，同时假设我们想预测的点位于下图 x 的位置

4. 为何是最小二乘？

这一部分解释了在线性回归中，我们为什么选择最小二乘法作为我们计算拟合曲线的方法。其实原因说起来也很简单，就是我们在建模初始，选择了一些基于长期观察得出的假设。这些假设是符合实际经验的。下面介绍的只是某一种假设思路，此外还有很多别的假设，可以证实最小二乘是线性回归最好的选择。

4.1 线性回归的概率意义

我们首先要为训练集赋予一个概率的意义，我们假设：

其中，\(\varepsilon^{(i)}\sim N(0, \sigma^2)\)。因此，\(y^{(i)}\)同样是一个服从正态分布的随机变量，其概率密度函数如下：

或者，我们可以说 \(y^{(i)}|x^{(i)};\theta\sim N(\theta^Tx^{(i)}, \sigma^2)\)。

4.2 似然函数

我们假设，对于所有的\(\varepsilon^{(i)}\)是独立同分布的(或称 IDD)，因此对于所有的训练样本，我们定义似然函数\(L(\theta)\)：
\begin{align}
L(\theta) & = P(Y|X;\theta) \\
& = \prod_{i=1}^{m}P(y^{(i)}|x^{(i)};\theta) \\
& = \prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2})
\end{align}
我们可以这样理解似然函数：对于每个训练样本输出\(y^{(i)}\)，其出现的概率我们可以用\(x^{(i)}\)和\(\theta\)表示出来，也就是这个样本出现的概率。所以，把所有训练样本出现的概率相乘，就是我们整个训练集出现的概率，这个概率就是我们的似然函数。
显然，当这个概率越大时，我们模型对于训练样本的描述就越好，所以我们的工作就是找出一个\(\theta\)使得\(L(\theta)\)最大化。下面我们就来找一找这个最大值。我们定义：
\begin{align}
l(\theta) & = ln L(\theta) \\
& = ln \prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\
& = \sum_{i=1}^{m}ln\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\
& = \sum_{i=1}^{m}(ln\frac{1}{\sqrt{2\pi}\sigma} + lnexp(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2})) \\
& = ln\frac{m}{\sqrt{2\pi}\sigma} + \sum_{i=1}^{m}(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\
& = ln\frac{m}{\sqrt{2\pi}\sigma} - \frac{1}{\sigma^2}\frac{1}{2}\sum_{i=1}^{m}(y{(i)} - \theta^Tx^{(i)})^2
\end{align}
由于\(l(\theta)\)与\(L(\theta)\)有相同的单调性，因此我们要找\(L(\theta)\)的最大值，就相当于找上式最后一部分的最小值。
其实写到这里，相信有些同学已经看出来了(我还特意把\(\sigma^2\)和 2 分开写)，上面最后的部分，就是我们笔记 02 中的\(J(\theta)\)。从而在我们开始的假设下，只要\(J(\theta)\)可以取得最小值，那似然函数就可以取得最大值，这就验证了最小二乘法的正确性。

5. 第一个分类算法 ------ Logistic 回归

5.1 Logistic 函数(又称 Sigmoid 函数)

不同于回归算法，分类算法的预测值是离散值，比如在笔记 01 中提到的判断肿瘤性质的问题，其结果只能是恶性或良性两个值，我们下面讨论问题的范围，也暂时限定在二元分类上(即仅有是非两种结果)。当然，我们也可以强行使用线性回归，但最终的结果通常是欠拟合的，因此为了改进我们的算法，我们至少要做到把我们的假设\(h_{\theta}(x)\)限定在[0, 1]的区间内。一般来说，我们有个不错的选择，称为 Logistic 函数，其形式如下：

Logistic 函数的图像画出来是这样的：

5.2 Logistic 回归

首先，我们把我们的假设改为 Logistic 函数的形式，即：

下面，如同第 4 节中，我们同样为上面的假设，赋予一个概率的意义：
\begin{align}
& P(y=1|x; \theta) = h_{\theta}(x) \\
& P(y=0|x; \theta) = 1 - h_{\theta}(x)
\end{align}
不要忘了我们的 y 只能取 0 或 1 两个值，所以上述两个式子可以合并在一起，写成下面的形式：

接着，按同样的节奏考虑似然函数\(L(\theta)\)：

为了简化数学上的处理，同样对上面的\(L(\theta)\)取对数：
\begin{align}
l(\theta) & = log L(\theta) \\
& = log \prod_{i=1}^{m}h_{\theta}(x^{(i)})^{y^{(i)}}(1 - h_{\theta}(x^{(i)}))^{1-y^{(i)}} \\
& = \sum_{i=1}^{m}log(h_{\theta}(x^{(i)})^{y^{(i)}}(1 - h_{\theta}(x^{(i)}))^{1-y^{(i)}}) \\
& = \sum_{i=1}^{m}logh_{\theta}(x^{(i)})^{y^{(i)}} + \sum_{i=1}^{m}log((1 - h_{\theta}(x^{(i)}))^{1-y^{(i)}}) \\
& = \sum_{i=1}^{m}(y^{(i)}logh_{\theta}(x^{(i)}) + (1-y^{(i)})log(1-h_{\theta}(x^{(i)})))
\end{align}
然后，我们希望可以选出一个\(\theta\)，使似然函数可以取得最大值。这里我们采用**梯度上升算法**，其实和笔记 02 中提到的梯度下降是同样的原理只是\(\alpha\)前的符号不同。

回忆梯度下降算法的过程，上式最重要的就是后面求导的部分，所以我们同样对\(l(\theta)\)求偏导（此处视频中也没有计算过程，不感兴趣同学直接看结论就好了）。
\begin{align}
\frac{\partial}{\partial\theta_{j}}l(\theta) & = \frac{\partial}{\partial\theta_{j}}\sum_{i=1}^{m}(y^{(i)}lnh_{\theta}(x^{(i)}) + (1-y^{(i)})ln(1-h_{\theta}(x^{(i)}))) \\
& = \sum_{i=1}^{m}(\frac{\partial}{\partial\theta_{j}}y^{(i)}lnh_{\theta}(x^{(i)}) + \frac{\partial}{\partial\theta_{j}}(1-y^{(i)})ln(1-h_{\theta}(x^{(i)}))) \\
& = \sum_{i=1}^{m}[y^{(i)}\frac{\partial}{\partial\theta_{j}}lnh_{\theta}(x^{(i)}) + (1 - y^{(i)})\frac{\partial}{\partial\theta_{j}}ln(1 - h_{\theta}(x^{(i)}))] \\
& = \sum_{i=1}^{m}[\frac{y^{(i)}}{h_{\theta}(x^{(i)})}\frac{\partial}{\partial\theta_{j}}h_{\theta}(x^{(i)}) + \frac{1 - y^{(i)}}{1 - h_{\theta}(x^{(i)})}\frac{\partial}{\partial\theta_{j}}(1 - h_{\theta}(x^{(i)}))] \\
& = \sum_{i=1}^{m}[\frac{y^{(i)}}{h_{\theta}(x^{(i)})} - \frac{1 - y^{(i)}}{1 - h_{\theta}(x^{(i)})}]\frac{\partial}{\partial\theta_{j}}h_{\theta}(x^{(i)}) \\
\end{align}
我们又已知如下事实：

因此，前面求偏导的最终结果为：
\begin{align}
\frac{\partial}{\partial\theta_{j}}l(\theta) & = \sum_{i=1}^{m}[\frac{y^{(i)}}{h_{\theta}(x^{(i)})} - \frac{1 - y^{(i)}}{1 - h_{\theta}(x^{(i)})}]h_{\theta}(x^{(i)})(1 - h_{\theta}(x^{(i)}))x_{j}^{(i)} \\
& = \sum_{i=1}^{m}[y^{(i)}(1 - h_{\theta}(x^{(i)})) - (1 - y^{(i)})h_{\theta}(x^{(i)})]x_{j}^{(i)} \\
& = \sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)}
\end{align}
然后我们可以写出梯度上升迭代公式：

还是熟悉的配方还是熟悉的味道。但我们这里的模型显然不是上次的线性回归，其本质是因为这里采用了不同的\(h_{\theta}(x)\)，它不再是一个线性函数了。

6 感知器算法

6.1 简单介绍

视频中对这个算法并没有提及太多，其原因我认为是和 Logistic 回归形式上很相似。回想 Logistic 回归中，我们使用的 Logistic 函数仍然是一个开区间上的连续函数，而在感知器算法中，我们使用的\(g(z)\)只能取 0 或 1，具体定义如下：

所以我们只要把\(h_{\theta}(x)\)变为上述定义的\(g(\theta^Tx)\)，我们仍可以写出同样的迭代公式：

但是，如我前面提到的，该算法和 Logistic 回归 形式上很相似但也仅仅停留在形式上。由于其值域是离散的，我们很难为其赋予概率意义。