朴素贝叶斯法

思想: 基于特征条件独立假设, 学习输入输出的联合概率分布; 然后基于此模型对给定的输入 $x$, 利用贝叶斯定理求出后验概率最大的输出 $y$.

基本方法

$x$ 是 $\mathcal{X}$ 上的随机向量, $Y$ 是 $\mathcal{Y}$ 上的随机向量, $P(X, Y)$ 是 $X$ 和 $Y$ 的联合概率分布 $T$ 由 $P(X,Y)$ 独立同分布产生.

朴素贝叶斯法学习 $P(X,Y)$, 具体学习 $P(Y=c_k)$ 和 $P(X=x|Y=c_k)$.

朴素贝叶斯法对条件概率分布作了条件独立性的假设： $$ P(X=x|Y=y)=P(X^{(1)}=x^{(1)}, ..., X^{(n)}=x^{(n)}|Y=c_k) \\ =\underset{j=1}{\overset{n}{\prod}}P(X^{(j)}=x^{(j)}|Y=c_k) $$ 条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单，但有时会牺牲一定的分类准确率。

朴素贝叶斯法分类时，对给定的输入 $x$，通过学习到的模型计算后验概率分布 $P(Y=c_k|X=x)$，将后验概率最大的类作为 $x$ 的类输出。

后验概率计算根据贝叶斯定理进行： $$ P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\underset{k}{\sum}P(X=x|Y=c_k)P(Y=c_k)} \quad (1) $$

\[ P(Y=c_k|X=x)=\frac{P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k)}{\underset{k}{\sum}P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k)} \quad (2) \]

$(2)$ 式是朴素贝叶斯分类法的基本公式。于是，朴素贝叶斯分类器可表示为 $$ y=f(x)=\arg \underset{c_k}{max}\ \frac{P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k)}{\underset{k}{\sum}P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k)} \quad (3) $$ 在 $(3)$ 中分母对所有 $c_k$ 都是相同的，所以 $$ y=\arg \underset{c_k}{max}\ P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k) $$

后验概率最大化

朴素贝叶斯法将实例分到后验概率最大的类中，这等价于期望风险最小化。

假设选择 $0-1$ 损失函数： $$ L(Y,f(X))= \begin{cases} 1 & Y\neq f(X) \\ 0 & Y=f(X) \ \end{cases} $$ 式中 $f(X)$ 是分类决策函数。这时，期望风险函数为 $$ R_{exp}(f)=E[L(Y,f(X))] $$ 期望是对联合分布 $P(X,Y)$ 取的。由此取条件期望 $$ R_{exp}(f)=E_X \underset{k=1}{\overset{K}{\sum}}[(c_k,f(X))]P(c_k|X) $$ 为了使期望风险最小化，只需对 $X=x$ 逐个极小化，由此得到： $$ \begin{aligned} f(x)&=\arg \underset{y\in \mathcal{Y}}{\min}{\underset{k=1}{\overset{K}{\sum}}}L(c_k,y)P(c_k|X=x) \\ &=\arg \underset{y\in \mathcal{Y}}{\min}{\underset{k=1}{\overset{K}{\sum}}}I(y \neq c_k)P(y=c_k|X=x) \\ &=\arg \underset{y \in \mathcal{Y}}{\min}(1-P(y=c_k|X=x)) \\ &=\arg \underset{y \in \mathcal{Y}}{\max}P(y=c_k|X=x) \end{aligned} $$ 这样一来，根据期望风险最小化准则就得到了后验概率最大化准则： $$ f(x)=\arg \underset{c_k}{\max}P(c_k|X=x) $$ 即朴素贝叶斯法所采用的原理。

朴素贝叶斯法的参数估计

极大似然估计

在朴素贝叶斯法中，学习意味着估计 $P(Y=c_k)$ 和 $P(X^{(j)}=x^{(j)}|Y=c_k)$。可以应用极大似然估计法计算相应的概率。

先验概率 $P(Y=c_k)$ 的极大似然估计是 $$ P(Y=c_k)=\frac {\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)}{N},\ k=1,2,...,K $$ 设第 $j$ 个特征 $x^{(j)}$ 可能取值的集合为 $\{a_{j1},a_{j2},...,a_{jS_j}\}$，条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$ 的极大似然估计是 $$ P(X^{(j)}=a_{jl}|Y=c_k)=\frac {\underset{i=1}{\overset{N}{\sum}}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)} $$

\[ j=1,2,...,n;\ l=1,2,...,S_j;\ k=1,2,...,K \]

朴素贝叶斯算法

输入：训练数据 $T=\{(x_1, y_1), (x_2,y_2), ..., (x_N,y_N)\}$，其中 $x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$，$x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征，$x_i^{(j)} \in \{a_{j1},a_{j2},...,a_{jS_j}\}$，$a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值，$j=1,2,...,n$，$l=1,2,...,S_j$，$y_i \in \{c_1,c_2,...,c_K\}$；实例 $x$；

输出：实例 $x$ 的分类。

(1) 计算先验概率及条件概率 $$ P(Y=c_k)=\frac{\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)}{N}, k=1,2,...,K $$

\[ P(X^{(j)}=a_{jl}|Y=c_k)=\frac {\underset{i=1}{\overset{N}{\sum}}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)} \]

\[ j=1,2,...,n;\ l=1,2,...,S_j;\ k=1,2,...,K \]

(2) 对于给定的实例 $x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$，计算 $$ P(Y=c_k)\underset{j}{\overset{n}{\prod}}P(X^{(j)}=x^{(j)}|Y=c_k),\ k=1,2,...,K $$ (3) 确定实例 $x$ 的类 $$ y=\arg \underset{c_k}{max}\ P(Y=c_k)\underset{j}{\prod}P(X^{(j)}=x^{(j)}|Y=c_k) $$

贝叶斯估计

用极大似然估计可能会出现所要估计的概率值为 $0$ 的情况，会影响到后验概率的计算结果，解决这一问题的方法是采用贝叶斯估计。

条件概率的贝叶斯估计是 $$ P(X^{(j)}=a_{jl}|Y=c_k)=\frac {\underset{i=1}{\overset{N}{\sum}}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)+S_j\lambda},\ \lambda \ge 0 $$ 等价于在随机变量各个取值的频数上赋予一个正数 $\lambda \gt 0$。当 $\lambda=0$ 时就是极大似然估计。常取 $\lambda=1$，这时称为拉普拉斯平滑。

先验概率的贝叶斯估计是 $$ P_{\lambda}(Y=c_k)=\frac{\underset{i=1}{\overset{N}{\sum}}I(y_i=c_k)+\lambda}{N+K\lambda} $$ 其中，$S_j$ 是 $x^{(j)}$ 取值个数，$K$ 是 $Y$ 类别数。