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

1. 摘要

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

2. 欠拟合和过拟合

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

2.1 欠拟合

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

该拟合直线,只和房子size的一次方式是相关的。而从图像上来看,这条直线对整个房价的描述差强人意。 但如果我们用一条二次曲线来拟合,即,拟合出来的函数是跟房屋size的二次方和一次方均相关的,那么我们也许可以画出如下图像

显然这条曲线比上一条直线对房价的拟合情况要好。这里我们就可以说,用对房价用线性拟合是欠拟合的。

2.2 过拟合

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

它虽然在训练集上有完美的契合,但如果我们再新加入几个样本,恐怕这条曲线的表现就没有那么好了。这样的情况我们就称为过拟合

2.3 一个神比喻

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

3. 局部加权回归

3.1 非参数学习算法

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

3.2 局部加权回归思路

局部加权回归的思路非常简单,假设我们想预测的数据位于 x,则我们只需要考虑 x 附近的训练集,然后对这一部分的训练样本做线性回归。下面我们用一个具体例子做一个解释。
首先我们收集了一组数据作为训练样本,其分布如下图所示,同时假设我们想预测的点位于下图 x 的位置

如果选用线性回归模型,则我们的工作是:

\text{找到}\,\theta, \text{使得} \sum_i(y^{(i)} - \theta^Tx^{(i)})^2最小 \\ \text{输出} \theta^Tx

那么我们拟合出的曲线,很可能是如下的样子,这显然是欠拟合的,而且在 x 附近的预测也不是很理想。

如果选用局部加权回归,实际上我们所做的事情和线性回归很类似,但我们要为每个训练样本赋予一个权值,即:

\text{找到}\,\theta, \text{使得} \sum_i\omega^{(i)}(y^{(i)} - \theta^Tx^{(i)})^2最小 \\ \text{输出} \theta^Tx

其中,\omega^{(i)}称为权重,定义如下

\omega^{(i)} = exp(- \frac{(x^{(i)} - x)^2}{2\tau^2})

从定义我们可以看出,当我们需要预测的x点越接近x^{(i)},则权重会越接近1,相反地,当x^{(i)}x越远,则权值越接近0,因此从直观上来理解,被预测点x附近的训练样本才对模型的建立有最根本的影响。因此,我们做出的回归曲线会是这样的:

此外,有两点需要注意的地方:
第一,定义中有一个参数\tau,该参数如同线性回归中的\alpha是人手动设定的,\tau决定了训练样本输入x^{(i)}x距离变化时,\omega^{(i)}的变化速率,当\tau很小时,随着x^{(i)}远离x,其权值会下降得很快,反之你懂的。
第二,对于\omega^{(i)}的定义并不是唯一的,上文中只是选择了一种通常大家会用的形式,这种形式与高斯分布密度函数很像,但实际上二者并没有什么关系。

4. 为何是最小二乘?

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

4.1 线性回归的概率意义

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

y^{(i)} = \theta^Tx^{(i)} + \varepsilon^{(i)}

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

P(y^{(i)}|x^{(i)};\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2})

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

4.2 似然函数

我们假设,对于所有的\varepsilon^{(i)}是独立同分布的(或称IDD),因此对于所有的训练样本,我们定义似然函数L(\theta)

\begin{aligned} 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{aligned}

我们可以这样理解似然函数:对于每个训练样本输出y^{(i)},其出现的概率我们可以用x^{(i)}\theta表示出来,也就是这个样本出现的概率。所以,把所有训练样本出现的概率相乘,就是我们整个训练集出现的概率,这个概率就是我们的似然函数。
显然,当这个概率越大时,我们模型对于训练样本的描述就越好,所以我们的工作就是找出一个\theta使得L(\theta)最大化。下面我们就来找一找这个最大值。我们定义:

\begin{aligned} 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{aligned}

由于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函数,其形式如下:

g(z) = \frac{1}{1 + e^{-z}}

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

x \to +\infty, g(z) \to 1,当x \to -\infty, g(z) \to 0,当x=0, g(z)=0.5,根据以上三条性质,我们可以定义g(z)大于0.5是一类,小于0.5是另一类。

5.2 Logistic回归

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

h_{\theta}(x) = g(\theta^Tx) = \frac{1}{1 + e^{-\theta^Tx}}

下面,如同第4节中,我们同样为上面的假设,赋予一个概率的意义:

\begin{aligned} & P(y=1|x; \theta) = h_{\theta}(x) \\\\ & P(y=0|x; \theta) = 1 - h_{\theta}(x) \end{aligned}

不要忘了我们的y只能取0或1两个值,所以上述两个式子可以合并在一起,写成下面的形式:

P(y|x; \theta) = h_{\theta}(x)^y(1 - h_{\theta}(x))^{1-y}

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

L(\theta) = P(y|x; \theta) = \prod_{i=1}^{m}h_{\theta}(x^{(1)})^{y^{(i)}}(1 - h_{\theta}(x^{(i)}))^{1-y^{(i)}}

为了简化数学上的处理,同样对上面的L(\theta)取对数:

\begin{aligned} 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{aligned}

然后,我们希望可以选出一个\theta,使似然函数可以取得最大值。这里我们采用梯度上升算法,其实和笔记02中提到的梯度下降是同样的原理只是\alpha前的符号不同。

\theta := \theta + \alpha \nabla_{\theta}l(\theta)

回忆梯度下降算法的过程,上式最重要的就是后面求导的部分,所以我们同样对l(\theta)求偏导(此处视频中也没有计算过程,不感兴趣同学直接看结论就好了)。

\begin{aligned} \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{aligned}

我们又已知如下事实:

g'(z) = (\frac{1}{1 + e^{-z}})' = \frac{e^{-z}}{(1 + e^{-z})^2} = g(z)(1 - g(z))

因此,前面求偏导的最终结果为:

\begin{aligned} \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{aligned}

然后我们可以写出梯度上升迭代公式:

\theta_{j} := \theta_{j} + \alpha \sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)}

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

6 感知器算法

6.1 简单介绍

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

g(z) = \begin{cases} 1, & \text{if z $\ge$ 0} \\ 0, & \text{otherwise} \\ \end{cases}

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

\theta_{j} := \theta_{j} + \alpha \sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)}

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