8. 贝叶斯分类器（Bayesian Classifier）

1. 简介

贝叶斯分类器只能用于分类问题，贝叶斯分类器有两种，一种是Exact Bayesian，另一种是Naive Bayesian，贝叶斯分类器的predictor必须得是catogorical的。

2. Exact bayesian

算法一：Exact Bayesian原算法
a. 在训练集中寻找同新数据的predictor完全一致的所有数据
b. 在这些数据中寻找出现频率最多的数据，其分类为Ck
c. 将新的数据分类为Ck

算法二：Exact Bayesian的cutoff算法
a. 定义一个cutoff probability
b. 在训练集中寻找同新数据的predictor完全一致的所有数据
c. 计算这些数据属于class of interest的概率
d. 如果c中计算的概率高于这个cutoff probability，则认为该数据属于class of interest（否则属于另外的class，如果是二分类，则属于另外一类，如果是多分类，则定义其他类的cutoff probability并重复该算法的步骤）

3. 条件概率模型

如果使用算法二，其运用到条件概率模型：(假设d个predictor，m个class)
$p(C_i|x_1,x_2,...,x_d)=\frac{p(x_1,x_2,...,x_d|C_i)p(C_i)}{p(x_1,x_2,...x_d|C_1)p(C_1)+...+p(x_1,x_2,...,x_d|C_m)}$

注: 以下的定义都是针对训练集而言
先验概率(prior probability)
$p(c_k)= \frac{有多少条C_k}{有多少条数据}$
似然函数 likelihood (probability of the profile given class k is true)： $p(x_1,x_2,...x_d|C_k) = \frac{C_k的数据之中有多少条predictor的值正好是x_1,x_2...,x_d}{有多少条C_k}$
后验概率(posterior probability)： $p(C_i|x_1,x_2,...,x_d)$
条件概率公式： $p(C_k|X)=\frac{p(X|C_k)P(C_k)}{P(X)}$
因此：
最大后验等于先验乘以最大似然
$\hat{y}=argmax_{C_k}\{p(C_k|X) \} =argmax_{C_k}\{p(C_k)p(X|C_k) \}$
这解释了为什么Exact Bayesian可以准确地进行分类

4. Naive Bayesian及其假设

显然，Exact Bayesian的问题在于它需要被投喂很多的数据才能够找到对应的记录，如果有20个predictor，每个predictor都有两个值，那么至少需要 $2^{20}$ 来保证每一条数据都有匹配的数据，因此采用Naive Bayesian的手段来缩减所需要的数据量

Naive Bayesian的假设：当给定target class的时候，predictors之间条件独立
在该假设下：
链式法则： $p(x_1,x_2,...,x_d|C_k)=p(x_1|x_2,...,x_d,C_k)p(x_2|x_3,...,x_d,C_k)p(x_d|C_k)$
条件独立的假设
$p(x_1,x_2,...,x_d|C_k)=p(x_1|c_1)p(x_2|c_1)...p(x_d|c_k)= \Pi_{j=1}^{d}p(x_j|C_k)p(C_k)$
因此
$p(C_i|x_1,x_2,...,x_d)=\frac{\Pi_{j=1}^{d}p(x_j|C_k)p(C_k)}{\Pi_{j=1}^{d}p(x_j|C_1)p(C_1)+...+\Pi_{j=1}^{d}p(x_j|C_m)p(C_m)}$
$\hat{y}=argmax_{C_k}\{ \Pi_{j=1}^{d}p(x_j|C_k)p(C_k))$

注：同算法一和二，Naive Bayesian也有有cutoff和无cutoff两种版本

5. Naive Bayesian的计算

对于Naive Bayesian，关键的地方在于如何求出P(x|Ck)
a. 如果是categorical variable，则
$P(x_j|C_k)=\frac{C_k的记录中有多少条是predictor \ x_j}{有多少条C_k的记录}$

b. 如果是continuous variable (Gaussian Naive Bayesian)
假设其服从高斯分布
$P(x_j|C_k)=\frac{1}{2\pi\sigma_j}exp({-\frac{(x_j-\mu_{j,c_k})^2}{2\sigma_{j,c_k}^2}})$
其中
$\mu_{j,c_k}=\frac{C_k的记录中该predictor的数值总和}{C_k的记录条数}$
$\sigma_{j,c_k}=\frac{(每条C_k记录的predictor的值-\mu_{j,c_k})^2 }{C_k的记录条数}$

c. Laplace Smoothing
当记录中缺少某个predictor的某个category的值的时候，Naive Bayes会输出该概率为0，为了解决这个问题，则需要一个smoothing parameter $\alpha$
$P(X_j=t|y=C_k)=\frac{(多少条X_j=t且y=C_k的数据)+\alpha}{C_k有多少条数据+(\alpha*(X_j有多少种类))}$
由上可以看出:
a. $\alpha$ 保证了概率的取值范围在(0,1)，并且不会为0或者1
b. 如果category variable的取值越多，则相同的alpha会给出更小的概率值
Laplace Smoothing在Multinomial Naive Bayes(指X服从multinomial distribution)和Categorical Naive Bayes上都扮演重要的角色

d. 如果是binary variable (Bernoulli Naive Bayes)
Bernouli NB rule常用于NLP文档的在短文上面表现比较出色
$P(x_j|C_k)=P(j|C_k)x_j+(1-P(j|C_k))(1-x_j)$
如果 $x_j$ 在原文档里面出现过一次，则 $P(j|C_k)=1$ ，否则为0
由上公式可以看出，Bernouli NB rule会对没有出现的情形产生高惩罚项，然而Multinomial NB rule则是选择忽视

6. 示例分析

对于Exact Bayesian和Naive Bayesian的区别，用以下的例子比较容易说明：

图一：Bayesian示例

目标：对新纪录(Light, Fine, Brown)进行分类，这里以cat为例
a. Exact Bayesian
计算先验：P(Cat) = 4/8 = 0.5 # 记录里面有4条分类为猫，总共8条记录
计算似然：P(Light, Fine, Brown | Cat) = 2/4 = 0.5 # 4条猫的记录里面，有2条所有的predictor与记录一致
最大后验：P(Cat | Light, Fine, Brown)

\propto

P(Cat) * P(Light, Fine, Brown | Cat) =0.5*0.5=0.25
同样的方法求出 P(Dog | Light, Fine, Brown) = 0
因此分类为猫

b. Naive Bayesian
计算先验：P(Cat) = 4/8 = 0.5 # 记录里面有4条分类为猫，总共8条记录
计算每个predictor的conditional probability
P(Light|Cat) = 3/4 = 0.75 # 4个cat的记录里面有3个是light
P(Fine|Cat) = 3/4 = 0.75
P(Brown|Cat) = 2/4 = 0.5
最大后验：
P(Cat│Light, Fine, Brown) ∝ 0.75 x 0.75 x 0.5 x 0.5 = 0.14
同理可得
P(Dog│Light, Fine, Brown) ∝ 0.25 x 0.25 x 0.5 x 0.5 = 0.015
因此分类为猫

7. 对比分析以及Bayesian模型的优缺点

a. 数据量上，假设是d个binary variable，则Exact Bayesian需要至少 $2^d$ 个数据，而Naive Bayesian只需要 $2d$ 个数据（仅仅随predictor的数量线性增长）
b. Naive Bayesian比Exact Bayesian简单而且速度更快
c. Naive Bayesian robust to noise data，因此其overfitting的概率比Exact Bayesian小
d. Naive Bayesian的结果的可靠性需要大量的数据来支撑
e. Naive Bayesian只保留了propensity(属于该class的概率)的顺序，但不能求出其具体的值
f. 两个Bayesian算法在处理categorical variable上都是直接而且高效的