「CS229」Lecture6：拉普拉斯平滑和SVM简介

拉普拉斯平滑

问题引入

在上一节中，我们使用朴素贝叶斯来解决垃圾邮件分类问题。我们设 $x$ 表示邮件内容特征，$x$ 的每一个分量（取值0或1）表示词典中对应位置的单词是否出现，$y$ 表示该邮件是否为垃圾邮件。我们假设$P(x\mid y)$ 和 $P(y)$ 都遵循伯努利分布，因此参数有

• ${\varphi }_{j\mid y=1}=P(x_j=1\mid y=1)$
• ${\varphi }_{j\mid y=0}=P(x_j=1\mid y=0)$
• ${\varphi }_y=p(y=1)$

通过极大似然估计，可以得到这三个参数的最优值
$$
$$\begin{array}{rl}& {\varphi }_y=\frac{\sum _{i=1}^m\mathcal{I}(y^{(i)}=1)}{m}\\ & {\varphi }_{j\mid y=1}=\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=1,y^{(i)}=1)}{\sum _{i=1}^m\mathcal{I}(y^{(i)}=1)}\\ & {\varphi }_{j\mid y=0}=\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=1,y^{(i)}=0)}{\sum _{i=1}^m\mathcal{I}(y^{(i)}=0)}\end{array}$$

$$

尽管这些值都是通过计算得到的，但其实一打眼看上去也很好理解。以${\varphi }_{j\mid y=1}$ 为例，其最优值计算公式的分母 $\sum _{i=1}^m\mathcal{I}(y^{(i)}=1)$ 表示“训练数据集中垃圾邮件的数目”，$\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=1,y^{(i)}=1)$ 表示“包含词典中第 j 个单词的垃圾邮件的数量”。得这些参数的最优值，也就得到了$P(x|y)$ 和 $P(x)$ 。因此当我们预测时，就可以套用下面的公式
$$\begin{array}{rl}P(y=1\mid x)& =\frac{P(x\mid y=1)P(y=1)}{P(x\mid y=1)P(y=1)+P(x\mid y=0)P(y=0)}\\ & =\frac{\prod _{j=1}^{n}P(x_j\mid y=1)P(y=1)}{P(\prod _{j=1}^n{x}_j\mid y=1)P(y=1)+\prod _{j=1}^{n}P(x_j\mid y=0)P(y=0)}\end{array}$$
我们考虑这样一个情况——假设词典中第 k 个单词在训练集所有邮件里都没有出现过，即$P(x_k=1|y=1)=P(x_k\mid y=0)=0$。假设预测时出现一封包含该单词的邮件，此时我们计算 $P(y=1\mid x)$ 会得到
$$P(y=1|0)=\frac{0}{0+0}$$
显然，我们得不到一个有意义的概率值。那么问题的根源在哪里呢?

根源剖析

通过观察我们可以发现，$P(x_k=1|y=1)=P(x_k\mid y=0)=0$ 是有问题的。根据概率论的知识我们知道，“某个事件的概率为 0 ” 表示 “该永远不会发生”。$P(x_k=1|y=1)$ ，也就是${\varphi }_{k|y=0}$，是我们完全根据训练集的数据计算得到的。我们不能奢求训练集可以涵盖所有的情况，因此不能保证垃圾邮件中永远不可能出现 $x_k$ 对应的单词。所以， $P(x_k=1\mid y=1)$ 不能是 $0$，而是应该是一个比较小的非负值。

为了达到这个目的，我们需要在计算 ${\varphi }_{j\mid y=1}$ 的时候做一些“手脚“——也就是使用拉普拉斯平滑（Laplace Smoothing）。

问题解决

绕了这么大一圈，终于引出拉普拉斯平滑。但是别急，我们需要先看一个拉普拉斯平滑的简单案例。假设有一个足球队A，该球队先前和B、C、D、E、F五个队伍都打过比赛，数据如下

对手	结果
B	输
C	输
D	输
E	输
F	输

下周A队要和G队打比赛，A队胜利的概率有多大？很显然，我们可以根据历史数据对A的胜率进行预测，即
$$P(A\mathrm{队}\mathrm{打}\mathrm{赢}G\mathrm{队})=\frac{A\mathrm{队}\mathrm{赢}\mathrm{的}\mathrm{次}\mathrm{数}}{A\mathrm{队}\mathrm{赢}\mathrm{的}\mathrm{次}\mathrm{数}+A\mathrm{队}\mathrm{输}\mathrm{的}\mathrm{次}\mathrm{数}}=\frac{0}{0+5}=0$$
这里出现了和刚才一样的问题 —— 只通过历史数据不能完全推断未来的数据，因此不能100%断定A队一定输（万一人家奋发图强了呢）。为了解决该问题，拉普拉斯平滑的做法是：将A队赢的次数增加1，A队输的次数也增加1，这样计算出来的概率就不是0了，即
$$P(A\mathrm{队}\mathrm{打}\mathrm{赢}G\mathrm{队})=\frac{A\mathrm{队}\mathrm{赢}\mathrm{的}\mathrm{次}\mathrm{数}+1}{A\mathrm{队}\mathrm{赢}\mathrm{的}\mathrm{次}\mathrm{数}+1+A\mathrm{队}\mathrm{输}\mathrm{的}\mathrm{次}\mathrm{数}+1}=\frac{1}{7}$$
将该思想运用在垃圾邮件分类问题中 ${\varphi }_{j\mid y=1}$ 和 ${\varphi }_{j\mid y=0}$ 的计算上，有
$$\begin{array}{rl}{\varphi }_{j\mid y=1}& =\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=1,y^{(i)}=1)+1}{\sum _{i=1}^m\mathcal{I}(y^{(i)}=1)+2}\\ {\varphi }_{j\mid y=0}& =\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=1,y^{(i)}=0)+1}{\sum _{i=1}^m\mathcal{I}(y^{(i)}=0)+2}\end{array}$$

泛化

更一般的，假设特征 $x$ 有多个分量，并且每个分量取值有k个——即$x\in \{1,2,\dots ,k\}$ 。根据朴素贝叶斯的思想，$P(x\mid y)$的计算公式为——
$$P(x\mid y)=\prod _{j=1}^{n}P(x_j\mid y)$$
我们可以根据历史数据预测 $P(x_j=x\ast \mid y=y\ast )$ 的值，有
$$P(x_j=x^{\ast }\mid y=y^{\ast })=\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=x^{\ast }\mid y=y^{\ast })}{\sum _{i=1}^m\mathcal{I}(y=y^{\ast })}$$
应用拉普拉斯平滑，我们可以改写$P(x_j=k\mid y=y\ast )$ 的计算公式，即
$$P(x_j=x^{\ast }\mid y=y^{\ast })=\frac{\sum _{i=1}^m\mathcal{I}(x_j^{(i)}=x^{\ast }\mid y=y^{\ast })+1}{\sum _{i=1}^m\mathcal{I}(y=y^{\ast })+k}$$

两种事件模型

多元伯努利事件模型

对于以前提到的“垃圾邮件分类任务”，我们用 $x$ 表示邮件内容特征，$x$​ 的每一个分量（取值0或1）表示词典中对应位置的单词是否出现。假设词典为 [a, English， I， like，zoo]，维度为5。有一封邮件的内容为“I like Englist”，则对应的 $x$ 就是
$$x={\left[\begin{array}{ccccc}0& 1& 1& 1& 0\end{array}\right]}^T$$
这种模型我们称作“多元伯努利事件模型”。在该模型中，$x$ 的维度为词典的规模，即$x\in \{0,1{\}}^{\mathrm{\#}dict}$。该模型的缺点也很明显，就是我们只知道某个单词是否存在，无法得知该单词的具体数量，另外单词的位置我们也无法得知。

多项事件模型

为了解决上述的问题，我们换用另一种$x$ 的表示方法。假设词典是这样的

Index	Word
$⋮$	$⋮$
56	English
$⋮$	$⋮$
129	I
$⋮$	$⋮$
234	like
$⋮$	$⋮$

那么对应的$x$ 可以写作
$$x={\left[\begin{array}{ccc}56& 129& 234\end{array}\right]}^T$$
很容易可以看出，$x$ 维度为“邮件的长度”，$x$ 的每一个分量表示“邮件对应位置的单词在词典中的下标”。我们把这种模型称作"多项事件模型"。该模型中$P(y\mid x)$ 的计算公式如下所示（其中n表示邮件长度）
$$\begin{array}{rl}P(y\mid x)& =\frac{P(x\mid y)P(y)}{P(x)}\\ & =\frac{\prod _{j=1}^{n}P(x_j\mid y)P(y)}{P(x)}\end{array}$$
其实本质上需要对 $P(x_j y) $ 和 $P(y)$ 进行预测。假设这两个概率都遵循伯努利分布，则可以设置以下参数

• ${\varphi }_y=P(y=1)$
• ${\varphi }_{k\mid y=0}=P(x_j=k\mid y=0)$
• ${\varphi }_{k\mid y=1}=P(x_j=k\mid y=1)$

可以发现，我们已经做出了如下假设——邮件中每个位置出现单词 $k$ 的概率都是相同的。我们极大化联合似然概率 $P(x,y)=P(x\mid y)P(y)$ ，可以得到参数的估计值
$$\begin{array}{rl}{\varphi }_y& =\frac{\sum _{i=1}^n\mathcal{I}(y^{(i)}=1)}{m}\\ {\varphi }_{k\mid y=0}& =\frac{\sum _{i=1}^n(\mathcal{I}(y^{(i)}=0)\sum _{j=1}^m\mathcal{I}(x_j^{(i)})=k)}{\sum _{i=1}^n\mathcal{I}(y^{(i)}=0)\cdot n_i}\\ {\varphi }_{k\mid y=1}& =\frac{\sum _{i=1}^n(\mathcal{I}(y^{(i)}=1)\sum _{j=1}^m\mathcal{I}(x_j^{(i)})=k)}{\sum _{i=1}^n\mathcal{I}(y^{(i)}=1)\cdot n_i}\end{array}$$
上面公式中$n_i$ 表示训练数据集中第 i 封邮件的长度，也就是 $x^{(i)}$ 的维度。当然，我们可以应用拉普拉斯平滑，将${\varphi }_{k\mid y=0}$ 改写成如下形式，${\varphi }_{k\mid y=0}$ 同理。

$${\varphi }_{k\mid y=0}=\frac{\sum _{i=1}^n(\mathcal{I}(y^{(i)}=0)\sum _{j=1}^m\mathcal{I}(x_j^{(i)})=k)+1}{\sum _{i=1}^n\mathcal{I}(y^{(i)}=0)\cdot n_i+\mathrm{词}\mathrm{典}\mathrm{长}\mathrm{度}}$$

支持向量机简介

支持向量机（Support Vector Machine，SVM）是一种机器学习算法，可以用于分类和回归问题。它通过在高维空间中寻找一个最优的超平面，将不同类别的样本实例分开。在支持向量机中，数据点被看作是高维空间中的向量，不同类别的数据点被分别标记为正样本（+1）和负样本（-1）。SVM的目标是找到一个超平面，使得离该平面最近的数据点的距离最大化，这些离超平面最近的数据点就是支持向量（Support Vector）。

另外，支持向量机还可以将一个简单的特征集（如$[x_1,x_2]$），映射到一个高维的特征集(如$[x_1,x_2,x_1^2,x_2^2,x_1{x}_2]$)，从而找到一个非线性的边界。

特殊记号

• 标签 $y\in \{-1,+1\}$

• h 预测的值在 $\{-1,+1\}$ 之中
  $$g(z)=\{\begin{array}{ll}1,& z\ge 0\\ -1,& z<0\end{array}$$

• $h_{w,b}(x)=g(w^{T}x+b)$，其中 $w\in {\mathbb{R}}^n$，$b\in \mathbb{R}$

Functional margin

Functional margin可以看做数据点到由 $(w,b)$ 决定的超平面的距离的一种度量。对于一个数据点$(x^{(i)},y^{(i)})$，其对应的Functional margin定义如下：
$${\hat{\gamma }}^{(i)}=y^{(i)}(w^T{x}^{(i)}+b)$$
根据${\hat{\gamma }}^{(i)}$ 的定义也定看出，当${\hat{\gamma }}^{(i)}>0$ 时，表示$h(x^{(i)})=y^{(i)}$。我们希望，我们的分类器可以达到一个较大的 Functional Margin， 即${\hat{\gamma }}^{(i)}\gg 0$，也就是说，

• 当$y^{(i)}=1$ 时，我们希望 $w^T{x}^{(i)}+b\gg 0$
• 当$y^{(i)}=-1$ 时，我们希望 $w^T{x}^{(i)}+b\ll 0$

对于整个数据集来说，其 Functional margin 可以被定义为
$$\hat{\gamma }=\underset{i}{min}{\hat{\gamma }}^{(i)}$$
当然，我们可以采取一种trick 来增加${\hat{\gamma }}^{(i)}$ 的值——即把 $w$ 和 $b$ 同时增大相同的倍数，这样${\hat{\gamma }}^{(i)}$ 也会增大相同的倍数，但是边界的位置不会改变。为了解决这个问题，我们可以增加约束，一种是限制 $||w||=1$ ，另一种是$w=\frac{w}{||w||},b=\frac{b}{||b||}$。

Geometric margin

Geometric margin 也是数据点到由 $(w,b)$ 决定的超平面的距离的一种度量，其实就是数据点到超平面的欧几里得距离。对于一个数据点$(x^{(i)},y^{(i)})$，其对应的 Geometric margin 定义如下：
$${\gamma }^{(i)}=\frac{y^{(i)}(w^T{x}^{(i)}+b)}{||w||}$$
结合 Functional margin 的定义，我们可以发现
$${\gamma }^{(i)}=\frac{{\hat{\gamma }}^{(i)}}{||w||}$$
对于整个数据集来说，其 Geometric margin 可以被定义为
$$\gamma =\underset{i}{min}{\gamma }^{(i)}$$
他的几何意义也很简单，就是“距离超平面最近的数据点”到超平面的距离。为了能够获得一个最佳边际分类器（optimal margin classifier），我们需要让选择$(w,b)$ 让 $\gamma$ 最大化，也就是让所有数据点尽量离着超平面远一些。下图中，绿线分界线对应的 $\gamma$ 显然要大于红线分界线，因此绿色分界线更优。

最大化 $\gamma$ 我们可以形式化的描述为
$$
$$\begin{array}{rl}& \underset{\gamma ,w,b}{max}\gamma \\ & s.t.\frac{y^{(i)}(w^T{x}^{(i)}+b)}{||w||}\ge \gamma (i=1,\dots ,m)\end{array}$$ $$\mathrm{通}\mathrm{过}\mathrm{推}\mathrm{导}\mathrm{我}\mathrm{们}\mathrm{可}\mathrm{以}\mathrm{把}\mathrm{这}\mathrm{个}\mathrm{问}\mathrm{题}\mathrm{转}\mathrm{化}\mathrm{为}$$
$$\begin{array}{rl}& \underset{w,b}{min}||w|{|}^2\\ & s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1(i=1,\dots ,m)\end{array}$$

$$