跳转至

斯坦福229：机器学习【P6 Support Vetctor Machine】

【ML】斯坦福CS229：机器学习中英文字幕 by Andrew Ng

关键词：拉普拉斯平滑，支持向量机。

回顾朴素贝叶斯算法

我们已知在最大似然并分析求导后得到的如下参数条件：

\[ \begin{gather} \phi_y=\frac{\sum_{i=1}^mI\{y^{(i)}=1\}}{m}\\ \phi_{j|y=1}=\frac{\sum_{i=1}^mI\{X_j^{(i)}=1\ \&\&\ y^{(i)}=1\}}{\sum_{i=1}^mI\{y^{(i)}=1\}}\\ \phi_{j|y=0}=\frac{\sum_{i=1}^mI\{X_j^{(i)}=1\ \&\&\ y^{(i)}=0\}}{\sum_{i=1}^mI\{y^{(i)}=0\}}\\ \end{gather} \]

则在预测阶段，对于给定的 \(X\) ，我们可以根据贝叶斯规则计算：

\[ \begin{align} P(y=1|X)=&\frac{P(X|y=1)·P(y=1)}{P(X)}\\ =&\frac{P(X|y=1)·P(y=1)}{P(X|y=1)·P(y=1)+P(X|y=0)·P(y=0)} \end{align} \]

然而这个算法会面临一个问题，即如果有一封邮件中的词语不在你的字典库中，那么根据算法我们会猜测这封邮件更有可能是一封垃圾邮件，因为 \(X_j^{(i)}=0\) 所以项 \(P(X|y=1)\) 会偏小，而项 \(P(X|y=0)\) 会偏大。最终导致 \(P(y=1|X)\) 偏小。等于仅凭我们没见过，就估计一个事件的概率是零，这无疑是很荒谬的。

为了解决这种情况，我们研究出了拉普拉斯平滑。

拉普拉斯平滑

下面我们提出一个情境帮助我们理解这个概念：

假设一支足球队近期输了五场比赛，请根据下表中的相关信息（即 \(X\) ）估计下场比赛的胜率（即\(Y\)）：

比赛日期 对手球队 胜负情况
9/12 Wake Forest（客场） 0
10/10 Oregon State（客场） 0
10/17 Arizona（客场） 0
11/21 Caltech（客场） 0
12/31 Oklahoma（主场） ？

这么一来我们不难想到如果比赛是一个很标准的古典概型的话，比赛结果的概率应该是：

\[ P(y=1)=\frac{\#\{y=1\}}{\#\{y=0\}+\#\{y=1\}}=\frac04=0 \]

但根据拉普拉斯平滑，他的概率应该是：

\[ P(y=1)=\frac{\#\{y=1\}+1}{\#\{y=0\}+1+\#\{y=1\}+1}=\frac16 \]

更普遍的说，如果你在估计的事件有 \(k\) 种不同的取值，那么他的概率密度函数就应该更正为：

\[ P(y=j)=\frac{\sum_{i=1}^mI\{y^{(i)}=j\}+1}{m+k} \]

至此，我们可以对朴素贝叶斯进行拉普拉斯平滑修正：

\[ \phi_{j|y=0}=\frac{\sum_{i=1}^mI\{X_j^{(i)}=1\ \&\&\ y^{(i)}=0\}+1}{\sum_{i=1}^mI\{y^{(i)}=0\}+2}\\ \]

因为拉普拉斯平滑中的 \(X\) 与 \(Y\) 都需要是离散型的，那么我们如何将连续的值转化为离散的值呢？一个很简单的方法就是设置十个左右的边界自定义的桶，比如：

\(X\) \(X< 100\) \(100\le X < 200\) \(200\le X < 300\) \(300\le X <400\) ...
\(\hat X\) 1 2 3 4 ...

接下来的步骤与先前一样：

\[ \begin{gather} P(X|y)=\prod_{j=1}^nP(X_j|y) \end{gather} \]

而 \(X_j\) 是由单词是否在邮件中出现决定的。毫无疑问这种建模方式回损失很多信息，比如同一个单词出现的次数就无法表示。但实际上我们或许应该给一个高频出现的单词分配更高的权重。下面我们尝试改进表现方式：

假设一条邮件内容为：“Phone！Buy Phone now!”并且字典中的相关单词位置如下：

1 a
2 aardvark
...
800 buy
1600 phone
6200 now

那么我们的特征矩阵表示为：

\[ X=\begin{bmatrix} 1600\\ 800\\ 1600\\ 6200 \end{bmatrix} \]

此时 \(X_j\) 的取值范围被修正为 \([0,n]\) 而不是 \(\{0,1\}\) ，\(X\) 的维数也不再是字典的大小 \(n\) ，而是信息的长度 \(l\) .

至此我们称我们新建的模型为多元伯努利模型，而全新的这个事件类型被称为多项事件模型。既然有了问题事件的模型，我们也自然要给出其生成模型：

\[ \begin{align} P(X,y)=&P(X|y)·P(y)\\ \overset{assume}{=}&\prod_{j=1}^lx\{P(X_j|y)\}·P(y) \end{align} \]

虽然这看上去与高斯判别分布以及朴素贝叶斯的形式很相似，但是由于 \(X_j\) 的意义发生了变化。但尽管如此，参数的形式并不会发生改变：

\[ \phi_y=P(y=1)\ ;\ \phi_{k|y=0}=P(X_j=k|y=0)\ ;\ \phi_{k|y=1}=P(X_j=k|y=1) \]

其中的 \(P(X_j=k|y=0)\) 的含义是在 \(y=0\) 的前提下，第 \(j\) 个单词是 \(k\) 的概率。而这也基于一个假设：对于邮件中的每一个位置，出现单词 \(k\) 的概率是都会是 \(\phi_{k|y=0}\)。然后使用我们的最大似然估计求解参数的表达如下：

\[ \phi_{k|y=0}=\frac{\sum_{i=1}^m\{\ I\{y^{(i)}=0\}·\sum_{j=1}^{n^{(i)}} I\{X_j^{(i)}=k\}\ \}} {\sum_{i=1}^m\{\ I\{y^{(i)}=0\}·n^{(i)}\}} \]

而其显示含义则是：检查训练示例邮件中的所有非垃圾邮件，并查看所有电子邮件中的所有单词，计算单词 \(k\) 在这些单词中的占比是多少。

如果我们在此基础上加以拉普拉斯平滑的话，就会有如下的结果：

\[ P(X_j=k|y=0)=\frac{\sum_{i=1}^m\{\ I\{y^{(i)}=0\}·\sum_{j=1}^{l^{(i)}} I\{X_j^{(i)}=k\}\ \}+1} {\sum_{i=1}^m\{\ I\{y^{(i)}=0\}·l^{(i)}\}+n} \]

如果有个在测试邮件中有一个单词不在字典中怎么办呢，第一种方法是可以直接将其扔弃，另一种方法是建立一个稀有字的索引，将所有稀有字映射到一个索引上。很多时候我们会发现朴素贝叶斯的表现并不如逻辑回归，但是他所具有的优点在于简单和开销少。

尽管有了这样的模型，我们还可能遇到一些问题，比如一些发送方会刻意将单词拼写成特殊形式：

Mortgage -> M0rtgage

而这将会导致一个原先是垃圾邮件的特征变为非垃圾邮件的特征而逃过检测。有一种处理方式是将其映射回原本的单词，以正确进行处理。另一种处理方法是尝试获取电子邮件中引用的URL并分析这个网页。

支持向量机

支持向量机(Support Vectoe Machine)是一种可以帮助我们找到潜在的非线性边界的方法。

我们在线性回归刚结束的时候提到过，如果想找到非线性边界，我们不妨将已知维度的特征构造成更高维度的特征，比如已知 \(x_1,x_2\) ，我们可以得到 \(x_1^2,x_2^2,x_1x_2,x_1^2x_2,...\) 然后在对新的特征进行回归。但我们很难做到对新特征的准确构造。

一些相关前瞻

在接下来的支持向量机算法中，我们会发现这里没有需要设置的参数（如回归算法中的 \(\alpha\) ），也就是说支持向量机最大的特点就在于其完美的封装了一个功能。接下去我们将给出从可分隔的最优间隔分类器（optimal margin classifier）开始，而这也是支持向量机的基本模块，然后我们会导出一个与逻辑回归相似的基本模块俩帮助我们拓展规模到线性分类器。在下节课我们将学习机器学习中最伟大的四象之一——内核思想，也就是怎么将低纬度的 \(X\) 映射到高纬度的特征集上。在这之后我们还要讨论不可分割的案例。

最优间隔分类器

首先我们定义间隔函数，即如何自信且准确地对示例进行分类。接下来我们先从简单的情况开始，我们如果进行二进制分类，我们将使用逻辑回归：

\[ h_\Theta(X)=g(\Theta^TX)\ ,where\ g(x)=\frac1{1+e^{-x}} \]

因此当 \(\Theta^TX>0\) 时，我们预测结果是 1；当 \(\Theta^TX<0\) 时，我们预测结果是 0。反过来说，在训练阶段，我们会希望如果训练示例的 \(y=1\) ，则 \(\Theta^TX \gg 0\) 。只有这样才能当测试的 \(X\) 输入后 \(g(\Theta^TX)\)​ 的结果接近 1 ，即给出一个很自信且准确的结果。

接下来我们将定义几何间隔。当我们的训练示例是离散线性的，我们可以得到很多种决策边界，他们都可以将当前的训练示例集很好的分开。几何间隔就是用来进一步比较几种决策边界的方式：

image-20240217180430738

在上图中，我们可以看到绿线和红线相比，绿线相对训练示例的距离更大，也就是几何间隔更大，所以绿线是更好决策边界。那么我们如何形式化几何间隔呢？以及如何最大化几何间隔呢？这就是我们接下去想做的事情。

一些定义

在支持向量机（下称SVM）中，我们令 \(y\in\{-1,1\}\) ，于是 \(g()\) 也需要改变其值域： \(g(x)=\left\{\begin{matrix}-1,x<0\\1,x \ge 0\end{matrix}\right.\) 。除此之外，我们也需要对我们的假设函数做出修改：

\[ h_{w,b}(X)=g(w^TX+b),其中w,X\in\Bbb R^n,b\in\Bbb R \]

我们可以理解为将 \(X\) 中的 \(\Theta_0 x_0=\Theta_0\) 的常数项直接写为 \(b\) ，显然这不会影响 \(w^TX+b\) 与 \(X\) 是线性关系。而这也是为了方便我们后续的一些操作。接下来我们尝试形式化边界函数。

针对第 \(i\) 个训练示例的函数间隔定义为： \(\hat {\gamma}^{(i)}=y^{(i)}(w^TX^{(i)}+b)\) 。

同样对于训练示例而言，我们会希望当 \(y^{(i)}=1\) 时 \(w^TX^{(i)}+b\gg0\) ；当 \(y^{(i)}=-1\) 时 \(w^TX^{(i)}+b\ll0\) 。因此不论如何，\(\hat{\gamma}^{(i)} \gg 0\) 恒成立。

针对整个训练示例集的函数间隔的定义：\(\hat \gamma=\underset{i}{min}\ \hat\gamma^{(i)},i \in[1,m]\)

需要说明的是，这种定义只是在今天我们提到的离散训练示例集下可以使用。

但是这种定义也出现了一个问题：如果我们将 \(w,b\) 都乘一个数，这实际上并没有改变他的决策边界，但是这却扩大了函数间隔，因此我们需要给出对 \(w,b\) 的规定：例如将 \(w,b\) 在计算 \(\hat\gamma^{(i)}\) 前统一替换为 \(\frac{w}{||w||},\frac{b}{||b||}\)​ 。

接下去我们会给出几何间隔的定义，不妨从一个简单的示例入手。如果你有一个二维直角坐标系，其上一点到其上一线的距离即为几何间隔，其代数表述如下：

按我们原先的假设有一个 \(w,b\) 定义的超平面，并且对于每一个示例 \((X^{(i)},y^{(i)})\) ，几何间隔为：

\[ \gamma^{(i)}=\frac{y^{(i)}(w^TX^{(i)}+b)}{||w||} \]

可以发现，不论训练示例 \(i\) 的 \(w^TX^{(i)}+b\) 的正负，其 \(\gamma^{(i)}\) 都会是正值。也不难发现几何间隔与函数间隔是有一定关系的：

\[ \gamma^{(i)}=\frac{\hat\gamma^{(i)}}{||w||} \]

同样，几何间隔也有针对整个训练示例集而言的概念： \(\gamma=\underset{i}{min}\ \gamma^{(i)},i \in[1,m]\)

有了这几个概念后我们再给出最优间隔分类器概念，即通过选择 \(w,b\) 来最大化几何间隔。也是一种有用于线性可分割的弱化SVM。下面介绍如何实现最优间隔分类器：

根据定义，我们的目标即为：

\[ 找到 \underset{\hat\gamma,w,b}{max}\frac{\hat\gamma}{||w||},\ \ s.t.\ y^{(i)}(w^TX^{(i)}+b)\ge\hat\gamma \]

但是因为 \(\frac{\hat\gamma}{||w||}\) 是一个非凸的目标函数，因此我们就现在的形式很难求解，我们尝试通过分析转变目标。如果我们试图找到满足条件的最大的 \(\frac{\hat\gamma}{||w||}\) ，需要所有示例的函数间隔至少是 \(\hat\gamma\) . 又因为我们先前说过可以任意等倍缩放 \(w,b\) 而不改变实际的平面，那么我们尝试引入一个新的约束： \(\hat\gamma=1\) .将这个约束插入到我们的目标中可以发现想要最大化 \(\frac{\hat\gamma}{||w||}=\frac{1}{||w||}\) ，等价于最小化 \(||w||\) ，也等价于最小化 \(||w||^2\) .因此我们的目标变为：

\[ 找到 \underset{\hat\gamma,w,b}{min}\frac12{||w||^2},\ \ s.t.\ y^{(i)}(w^TX^{(i)}+b)\ge1 \]

这样一来我们的目标函数就变成了凸函数，我们也将保证能够得到最优间隔分类器