朴素贝叶斯算法原理

朴素贝叶斯分类器（Naive Bayes Classifier）的优点是运算时间短、数学原理清晰，我在MNIST和CIFAR-10数据集上测试，错误率分别为15.74%和58.45%。

实在看不懂，不如先复（yu）习一下概率统计；如果觉得是我写的太烂，周志华教授的《机器学习》书中，朴素贝叶斯分类器写的很清楚。

朴素贝叶斯算法

定义$\boldsymbol x$为样本，$\omega$为标记，则将样本和标记用概率公式表示：

• $P(\omega)$为先验概率，代表$\omega$在所有标记中出现的概率。
• $P(\boldsymbol x|\omega)$为似然，代表在$\omega$标记下，出现样本$\boldsymbol x$的概率。
• $P(\omega|\boldsymbol x)$为后验概率，代表$\boldsymbol x$出现的情况下，样本标记为$\omega$的概率。
• $P(\boldsymbol x)$代表样本$\boldsymbol x$出现的概率。

训练样本

根据Bayes公式，后验概率可以由先验概率和似然表示：

$$P(\omega|\boldsymbol x)=\frac{P(\omega)P(\boldsymbol x|\omega)}{P(\boldsymbol x)}$$
在分类问题中，我们认为 $P(\boldsymbol x)$为常数， $P(\omega)$和 $P(\boldsymbol x|\omega)$可由训练样本计算得到， $P(\omega|\boldsymbol x)$即为所求的结果（在证据 $\boldsymbol x$出现的前提下，取得标记为 $\omega$的概率）。上式可以表示为：
$$P(\omega|\boldsymbol x)\propto P(\omega)P(\boldsymbol x|\omega)$$
在分类时，我们通过上式计算不同 $\omega$值所对应的 $P(\omega)P(\boldsymbol x|\omega)$，找到最大值对应的 $\omega$，即可完成分类。因此，我们将分类问题转化成了根据样本，计算先验概率 $P(\omega)$和似然 $P(\boldsymbol x|\omega)$的问题。

先验概率$P(\omega)$可以用样本中标记为$\omega$的数量占总样本数之比表示：

$$P(\omega)=\frac{D_\omega}{D}$$
但是，根据样本，我们无法直接计算似然 $P(\boldsymbol x|\omega)$。在朴素贝叶斯分类算法中，我们假设样本的每个维度之间相互独立，此时似然就可以计算了。

对于离散的样本空间，第$i$个维度的似然可以表示为：

$$P(x_i|\omega)=\frac{D_{\omega,i}}{D_\omega}$$
考虑到部分样本取值可能没有在全部样本中出现，按上式计算时，没有出现的项就会取值为0。为了解决此问题，$P(\omega)$和$P(x_i|\omega)$的表达式被修正为
$$P(\omega)=\frac{D_\omega+1}{D+N}\\ P(x_i|\omega)=\frac{D_{\omega,i}+1}{D_\omega+N_i}$$
$N$为标记$\omega$可能取值的总数， $N_i$为样本 $\boldsymbol x$可能取值的总数。

若样本连续，且假设样本满足高斯分布，似然可表示为

$$p(x_i|\omega)=\frac{1}{\sqrt{2\pi}\sigma_{\omega,i}}\exp\left(-\frac{(x_i-\mu_{\omega,i})^2}{2\sigma_{\omega,i}^2}\right)$$
高斯分布的系数 $\sigma$和 $\mu$可以由最大似然估计(Maximum Likelihood Estimation, MLE)得到：
$$\hat\mu=\frac{1}{N}\sum_{j=0}^{N}x_{j}=\bar{x}$$

$$\hat\sigma^2=\frac{1}{N}\sum_{j=0}^{N}(x_j-\bar x)^2$$

对于全部维度的似然$P(\boldsymbol x|\omega)$，

$$P(\boldsymbol x|\omega)=\prod_{i=1}^NP(x_i|\omega)$$
至此，我们即可根据给定的样本空间，计算先验概率 $P(\omega)$和似然 $P(\boldsymbol x|\omega)$。

分类

在分类时，因为先验概率$P(\omega)$和似然$P(\boldsymbol x|\omega)$已知，待分类数据$\boldsymbol x$已知，$P(\omega)P(\boldsymbol x|\omega)$可以方便地求得。

又因为

$$P(\omega|\boldsymbol x)\propto P(\omega)P(\boldsymbol x|\omega)=P(\omega)\prod_{i=1}^NP(x_i|\omega)$$
找出使 $P(\omega|\boldsymbol x)$最大的 $\omega_i$， $\omega_i$即为分类结果。

需要注意的是，在实际应用中，样本$\boldsymbol x$的维数通常很高，而概率值均小于1。因此，为避免浮点数连乘出现0，将上式两边取对数

$$\log{P(\omega|\boldsymbol x)}\propto \log{P(\omega)}+\sum_{i=1}^N\log{P(x_i|\omega)}$$
对每个 $\omega_i$计算 $\log{P(\omega_i)}+\sum_{i=1}^N\log{P(x_i|\omega_i)}$，使该式最大的 $\omega_i$即为分类结果。

版本信息

1.0 20171118 initial commit

本作品采用知识共享署名-相同方式共享 3.0 未本地化版本许可协议进行许可。