朴素贝叶斯法
摘录自《统计学习方法》
朴素贝叶斯（Naive Bayes）法是基于贝叶斯定理和特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入输出的联合概率分布；然后基于此模型，对给定的输入 $x$，利用贝叶斯定理求出后验概率最大的输出 $y$。朴素贝叶斯法实现简单，学习与预测效率都很高。
朴素贝叶斯法的学习与分类
基本方法
设输入空间 $\mathcal{X} \subseteq \mathrm{R}^n$ 为 $n$ 维向量的集合，输出空间为类标记集合 $\mathcal{Y}={c_1,c_2,…,c_K}$。输入的特征向量 $x \in \mathcal{X}$，输出为类标记（class label）$y \in \mathcal{Y}$。$X$ 是定 义在输入空间 $\mathcal{X}$ 上的随机向量，$Y$ 是定义在输出空间 $\mathcal{Y}$ 上的随机变量。$P(X,Y)$ 是 $X$ 和 $Y$ 的联合概率分布。训练数据集： \(T=\{(x_1,y_1), (x_2, y_2), ..., (x_N, y_N)\}\) 由 $P(X,Y)$ 独立同分布产生。
朴素贝叶斯法通过训练数据集学习联合概率分布 $P(X,Y)$，具体的，学习以下先验概率分布及条件概率分布。
先验概率分布： \(P(Y=c_k),~~k=1,2,...,K\)
条件概率分布： \(P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k), ~~k=1,2,...K\)
由于条件概率分布 $P(X=x|Y=c_k)$ 有指数级数量的参数，所以朴素贝叶斯法对条件概率分布做了条件独立性的假设： \(\begin{align} P(X=x|Y=c_k) &= P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k), ~~k=1,2,...K \\ &= \prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k) \end{align}\) 朴素贝叶斯法实际上学习到生成数据的机制，属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法简单，但也会损失一定分类准确度。
朴素贝叶斯法分类时，对给定的输入 $x$，通过学习到的模型计算后验概率分布 $P(Y=c_k|X=x)$，将后验概率最大的类作为 $x$ 的类输出。后验概率： \(\begin{align} P(Y=c_k|X=x) &= \frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{k=1}^K P(X=x|Y=c_k)P(Y=c_k)} \\ &= \frac{P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{k=1}^K P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)} \end{align}\) 于是朴素贝叶斯分类器可表示为： \(y = f(x) = \arg \max_{c_k} \frac{P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{k=1}^K P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}\) 由于所求的 $y_{c_k}$ 分母相同，所以上式可化简为： \(y = f(x) = \arg \max_{c_k} P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)\)
后验概率最大化含义
朴素贝叶斯法将实例分到后验概率最大的类中，这等价于期望风险最小化。假设选择 0-1 损失函数： \(L(Y,f(X)) = \begin{cases} 1, & y \ne f(X) \\ 0, & y = f(X) \end{cases}\)
其中， $f(X)$ 是分类决策函数
这时，期望风险函数为： \(\mathrm{R}_{exp}(f) = E[L(Y,f(X))]\) 期望是对联合分布 $P(X,Y)$ 取得，由此取条件期望： \(\mathrm{R}_{exp}(f) = E_X \sum_{k=1}^K [L(c_k, f(X))]P(c_k|X)\) 为了使期望风险最小化，只需要对 $X=x$ 逐个最小化，得： \(\begin{align} f(x) &= \arg \min_{y \in \mathcal{Y}} \sum_{k=1}^K L(c_k,y)P(c_k|X=x) \\ &= \arg \min_{y \in \mathcal{Y}} \sum_{k=1}^K P(y \ne c_k|X=x) \\ &= \arg \min_{y \in \mathcal{Y}} (1 - P(y=c_k|X=x)) \\ &= \arg \max_{y \in \mathcal{Y}} P(y=c_k|X=x) \end{align}\) 这样，根据期望风险最小化准则得到后验概率最大化准组（朴素贝叶斯法采用的原理）： \(f(x) = \arg \max_{c_k} 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{\sum_{i=1}^N 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{\sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^N I(y_i=c_k)} \\ j = 1,2,..,n; ~~l = 1,2,...,S_j;~~k=1,2,...K\)
其中，$x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征 ；$a_{jl}$ 是第 $j$ 个特征 可能取得第 $l$ 个值；$I$ 为指示函数
学习与分类算法
输入：训练数据 $T={(x_1,y_1), (x_2, y_2), …, (x_N, y_N)}$，实例 $x$ 输出：实例 $x$ 的分类
其中 $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}$
计算先验概率及条件概率： \(P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i=c_k)}{N},~~k=1,2,...,K \\ P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^N I(y_i=c_k)} \\ j = 1,2,..,n; ~~l = 1,2,...,S_j;~~k=1,2,...K\)
对于给定的实例 $x=(x^{(1)},x^{(2)},…,x^{(n)})^T$，计算： \(P(Y=c_k)\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k), ~~k=1,2,...,K\)
确定实例 $x$ 的类： \(y = \arg \max_{c_k} P(Y=c_k)\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k), ~~k=1,2,...,K\)
贝叶斯估计
用极大似然估计可能会出现所要估计的概率值为 $0$ 的情况，这会影响后验概率的计算结果，使分类产生偏差。为解决这一问题，可使用贝叶斯估计： \(P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k) + \lambda}{\sum_{i=1}^N I(y_i=c_k) + S_j \lambda} \\ j = 1,2,..,n; ~~l = 1,2,...,S_j;~~k=1,2,...K\)
其中，$\lambda \geqslant 0$
等价于在随机变量各个取值的频数上赋予一个正数 $\lambda > 0$，当 $\lambda = 0$ 时就是极大似然估计。常取 $\lambda = 1$，这时叫拉普拉斯平滑（Laplacian smoothing）。
显然，对任何 $l=1,2,…,S_j, k = 1,2,…,K$，有： \(P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) > 0 \\ \sum_{l=1}^{S_j} P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) = 1\) 同样，先验概率的贝叶斯估计是： \(P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i=c_k)+\lambda}{N+K\lambda},~~k=1,2,...,K\)