Navie Bayes

Description

朴素贝叶斯用来对离散随机变量进行分类。

在垃圾邮件分类问题中（文本分类），我们希望可以将垃圾邮件和正常邮件进行分类。 在训练集中，我们有一堆被加了 spam 和 non-spam 的邮件。

特征可以使用 $x=[1,\dots ,0,\dots ,1,\dots ]$ 来表示， 当某封邮件包含特定的词汇时，其对应位置的值为 1，否则为 0。 包含所有特征向量单词的集合叫做 vocabulary ，因此， $x$ 的 shape 与 vocabulary 的 shape 相同。

这里如果想要构建一个 Generative model，即拟合 $p(x|y)$ 。 假设一个 vocabulary 有 50000 个单词，那么 $$\begin{gathered} x\in \\ {0,1 \\ }^{50000} \end{gathered}$$ ， 那么预测的结果将会有 $2^{50000}$ 个，太复杂了。

假设，在给定 $y$ 的条件下， $x_i$ 相互独立。这个假设又被称为朴素贝叶斯假设（Naive Bayes assumption）， 相对应的分类器被称为朴素贝叶斯分类器（Naive Bayes classifier）。 在上诉假设下，有：

\begin{array}{l} p\left(x_{1}, \ldots, x_{50000} \mid y\right) \\ \quad=p\left(x_{1} \mid y\right) p\left(x_{2} \mid y, x_{1}\right) p\left(x_{3} \mid y, x_{1}, x_{2}\right) \cdots p\left(x_{50000} \mid y, x_{1}, \ldots, x_{49999}\right) \\ \quad=p\left(x_{1} \mid y\right) p\left(x_{2} \mid y\right) p\left(x_{3} \mid y\right) \cdots p\left(x_{50000} \mid y\right) \\ \quad=\prod_{j=1}^{d} p\left(x_{j} \mid y\right) \end{array}

尽管朴素贝叶斯假设是一个很强的假设，但在很多问题中表现却很好。

给定训练集 $x^{(i)},y^{(i)};i=1,\dots ,n$ ， 令 ${\varphi }_{j|y=1}=p(x_j=1|y=1),{\varphi }_{j|y=0}=p(x=1|y=0),{\varphi }_y=p(y=1)$ ， 使用极大似然法计算使得 $s(x^{(i)},y^{)i})$ 发生概率最大的参数：

$$\mathcal{L}({\varphi }_y,{\varphi }_{j|y=0},{\varphi }_{j|y=1})=\prod _{i=1}^{n}p(x^{(i)},y^{(i)})$$

求得：

\begin{aligned} \phi_{j \mid y=1} &=\frac{\sum_{i=1}^{n} 1\left\{x_{j}^{(i)}=1 \wedge y^{(i)}=1\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}} \\ \phi_{j \mid y=0} &=\frac{\sum_{i=1}^{n} 1\left\{x_{j}^{(i)}=1 \wedge y^{(i)}=0\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=0\right\}} \\ \phi_{y} &=\frac{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}}{n} \end{aligned}

这些等式也可以使用样本估计参数的方法解释。 其中， $\wedge$ 表示“与”。 ${\varphi }_{j|y=1}$ 表示当邮件是垃圾邮件时，单词 $j$ 出现了。

计算出上诉参数之后，给定输入 $x$ ，我们可以计算 $p(y=1|x)$ ：

\begin{aligned} p(y=1 \mid x) &=\frac{p(x \mid y=1) p(y=1)}{p(x)} \\ &=\frac{\left(\prod_{j=1}^{d} p\left(x_{j} \mid y=1\right)\right) p(y=1)}{\left(\prod_{j=1}^{d} p\left(x_{j} \mid y=1\right)\right) p(y=1)+\left(\prod_{j=1}^{d} p\left(x_{j} \mid y=0\right)\right) p(y=0)} \end{aligned}

Laplace smoothing

虽然朴素贝叶斯具有很好的效果，但还存在一些问题。 比如上诉的文本分类问题，如果测试集中出现了一个训练集中没有的单词，例如第 35000 个单词一次都没出现过：

\begin{array}{l} \phi_{35000 \mid y=1}=\frac{\sum_{i=1}^{n} 1\left\{x_{35000}^{(i)}=1 \wedge y^{(i)}=1\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}}=0 \\ \phi_{35000 \mid y=0}=\frac{\sum_{i=1}^{n} 1\left\{x_{35000}^{(i)}=1 \wedge y^{(i)}=0\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=0\right\}}=0 \end{array}

预测概率为：

\begin{aligned} p(y=1 \mid x) &=\frac{\prod_{j=1}^{d} p\left(x_{j} \mid y=1\right) p(y=1)}{\prod_{j=1}^{d} p\left(x_{j} \mid y=1\right) p(y=1)+\prod_{j=1}^{d} p\left(x_{j} \mid y=0\right) p(y=0)} \\ &=\frac{0}{0} \end{aligned}

这种情况下，我们的模型就不知道该如何做预测。

我们可以使用 Laplace smoothing 解决这个问题，将之前的极大似然解用下面这个等式替换：

$$\begin{gathered} {\varphi }_j=\frac{1+{\sum }_{i=1}^{n}1 \\ {z}^{(i)}=j \\ }{k+n} \end{gathered}$$