朴素贝叶斯与Laplace平滑

朴素贝叶斯与Laplace平滑

朴素贝叶斯(Naive Bayes)

基本理论

朴素贝叶斯模型是生成学习的一种,用于分类问题。作为生成学习,朴素贝叶斯针对每一个分类,生成一个该分类对应的数据的模型,然后判断一个数据最符合哪一个模型,从而分类。

其核心为贝叶斯公式:

\[P(y\mid x) = \frac{P(x\mid y)P(y)}{P(x)} \]

目标是

\[\operatorname{argmax}_y\{P(y\mid x)\}=\operatorname{argmax}_y\{P(x\mid y)P(y)\} \]

这里的 \(x\) 代表了一系列特征 \(x_1,\dots,x_n\),于是我们的目标也可以写作:

\[\operatorname{argmax}_y\{P(y)P(x_1\mid y)P(x_2\mid x_1, y)\dots P(x_n\mid x_1, \dots, x_{n-1}, y)\} \]

这个式子非常复杂,如果考虑每个特征都是 \(0/1\) 变量,那么学习的参数为 \(O(2^n)\)(对于 \(x_{1},\dots,x_{i-1},y\) 的每种取值情况,都有 \(x_i\) 的分布)。

而朴素贝叶斯采取了一个非常强的假设——\(x_1,\dots,x_n\) 相互独立,于是上式立即化简为:

\[\operatorname{argmax}_y\{P(y)P(x_1\mid y)P(x_2\mid y)\dots P(x_n\mid y)\} \]

参数数量 \(O(n\times \#\text{class})\),这样就具有可操作性了。

参数推导

以每个特征都为 \(0/1\) 变量,进行 \(0/1\) 分类为例,推导各个参数的取值。

参数有:

  • \(\phi_y\)\(y=1\) 的先验概率;
  • \(\phi_{j\mid y=0},\phi_{j\mid y=1}\):在 \(y=0\) 以及 \(y=1\) 时,\(x_j=1\) 的概率,根据假设,不同的特征之间的参数是无关的。

仍然采用最大似然估计,用联合概率定义似然函数(\([x]\) 表示 \(x\) 为真即 \(1\),假即 \(0\)):

\[\begin{aligned} \mathcal{L}(\phi_{y=0},\phi_{y=1},\phi_y)=&\prod_{i=1}^mP(x^{(i)},y^{(i)})\\ =&\prod_{i=1}^mP(y^{(i)})\prod_{j=1}^nP(x^{(i)}_j\mid y^{(i)})\\ =&\prod_{i=1}^m\phi_y^{[y^{(i)}=1]}(1-\phi_{y})^{[y^{(i)}=0]}\prod_{j=1}^n\Big[\phi_{j\mid y=0}^{[x^{(i)}_j=1]}(1-\phi_{j\mid y=0})^{[x_j^{(i)}=0]}\Big]^{[y^{(i)}=0]}\\ &\Big[\phi_{j\mid y=1}^{[x^{(i)}_j=1]}(1-\phi_{j\mid y=1})^{[x_j^{(i)}=0]}\Big]^{[y^{(i)}=1]} \end{aligned} \]

取对数似然(其中 “\(\dots\)” 对 \(y=1\) 的情况省略):

\[\begin{aligned} \mathcal{l}=&\sum_{i=1}^m[y^{(i)}=1]\ln\phi_y+[y^{(i)}=0]\ln(1-\phi_y)\\ +&\sum_{i=1}^m\sum_{j=1}^n[y^{(i)}=0][x^{(i)}_j=1]\ln\phi_{j\mid y=0}+[x_j^{(i)}=0]\ln(1-\phi_{j\mid y=0})\dots \end{aligned} \]

先对 \(\phi_y\) 求偏导并令其为零:

\[0=\frac{1}{\phi_y}\sum_{i=1}^{m}[y^{(i)}=1]-\frac{1}{1-\phi_y}\sum_{i=1}^m[y^{(i)}=0] \]

从而

\[\phi_y=\frac{1}{m}\sum_{i=1}^m[y^{(i)}=1] \]

再对 \(\phi_{j\mid y=0}\) 求偏导并令其为零:

\[0=\sum_{i=1}^m[y^{(i)}=0]\left(\frac{[x^{(i)}=1]}{\phi_{j\mid y=0}}-\frac{[x^{(i)}=0]}{1-\phi_{j\mid y=0}}\right) \]

从而

\[\phi_{j\mid y=0}=\frac{\sum_{i}[y^{(i)}=0][x^{(i)}_j=1]}{\sum_{i}[y^{(i)}=0]} \]

同理有

\[\phi_{j\mid y=1}=\frac{\sum_{i}[y^{(i)}=1][x^{(i)}_j=1]}{\sum_{i}[y^{(i)}=1]} \]

实际上这些公式看起来非常显然,就是以频率估计概率,但是都是基于MLE推导而来的。

Laplace平滑

朴素贝叶斯模型非常依赖数据的“完整性”——假如训练集中没有 \(x^{(i)}_j=1,y^{(i)}=0\) 的数据,那么我们对 \(P(x_j=1\mid y=0)\) 的估计就是 \(0\),也即在统计上不可能发生,然而这是很不安全的,我们更倾向于说 \(P(x_j=1\mid y=0)\) 很小,而不是为 \(0\)

以一个例子突出朴素贝叶斯模型的这一问题。

垃圾邮件分类

考虑给定一个纯文本邮件,判断其是否为垃圾邮件。

我们可以用一种很简单的方法处理数据——预设一个字典,假设邮件的所有单词都包含在内(如果没有包含就把它忽略)。设置特征为“某一个单词是否在邮件中出现”,出现即为 \(1\),不出现即为 \(0\)。是垃圾邮件,则目标值为 \(1\),否则为 \(0\)

(其实可以注意到这种特征设置并不满足朴素贝叶斯的假设,比如 buy 和 price 这两个单词是否出现一般来说是不独立的。因此直接这样实现的效果很差,用 UCI 中的数据集 spambase,将其提供的“单词出现频次”改为“是否出现”,大概错误率为 10%。)

那么就可能会有一个问题——字典中的某个单词 \(j\) 没有在 training set 里出现,但是出现在了 test set 中。按照我们的方法,

\[P(x_j=1\mid y=1)=P(x_j=1\mid y=0)=0 \]

那么我们发现模型对 test set 中的这封邮件是垃圾邮件和不是垃圾邮件的概率都是 \(0\)。很有可能这一个单词与是否是垃圾邮件无关,但是它造成了我们根本无法判断这封邮件是否是垃圾邮件。

Laplace平滑

一个非常简单的处理,我们假设每种情况最初都包含有一个数据,也即

\[\phi_{j\mid y=0}=\frac{\sum_{i}[y^{(i)}=0][x^{(i)}_j=1]+1}{\sum_{i}[y^{(i)}=0]+2} \]

同理

\[\begin{aligned} \phi_{j\mid y=1}&=\frac{\sum_{i}[y^{(i)}=1][x^{(i)}_j=1]+1}{\sum_{i}[y^{(i)}=1]+2}\\ \phi_y&=\frac{\sum_{i=1}^m[y^{(i)}=1] +1}{m+2} \end{aligned} \]

更为普遍地,我们考虑有 \(k\) 个分立取值的变量 \(x_j\in\{1,\dots,k\}\),那么我们对其概率估计为:

\[P(x_j=t\mid y=0)=\frac{\sum_{i=1}^m[x^{(i)}_j=t][y^{(i)}=0]+1}{\sum_{i=1}^m[y^{(i)}=0]+k} \]

这样就直接避免了上述问题,但是同时也会造成一定程度的误差,在数据较多时造成的误差不明显。

热门相关:超武穿梭   情生意动   刺客之王   薄先生,情不由己   大神你人设崩了