3 朴素Bayes法

#NaiveBayes #MLE #BayesianInference #BayesFormula

1 朴素 Bayes 法的学习与分类

1.1 基本方法

延续上一章的假设， $X \subset R^{n}, Y = {c_{1}, \dots, c_{K}}$ . $X \in X, Y \in Y$ . $P (X, Y)$ 是 $X, Y$ 的联合概率分布，据此采样得到训练数据集 $T = {(x_{1}, y_{1}), \dots, (x_{n}, y_{n})}$ .
朴素Bayes法是通过 $T$ 学习 $P (X, Y)$ 的方法. 它与 Bayes 估计是不同的概念. “朴素“的得名由来是因为它做出了条件独立性的假设.

联合分布 $P (X, Y)$ 可以由先验分布

\begin{matrix} (1.1) & P (Y = c_{k}), 1 \leq k \leq K \end{matrix}

和条件分布

\begin{matrix} (1.2) & P (X = x | Y = c_{k}) = P (X^{(i)} = x^{(i)}, 1 \leq i \leq n | Y = c_{k}) \end{matrix}

得到. 朴素 Bayes 法给出了条件独立性的假设，也即 (2) 可以进一步假设

\begin{matrix} (1.3) & P (X = x | Y = c_{k}) = \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} | Y = c_{k}) . \end{matrix}

这样，依据 Bayes定理计算后验分布

\begin{aligned} P (Y = c_{k} | X = x) \\ = & \frac{P (X = x | Y = c_{k}) P (Y = c_{k})}{\sum_{k} P (X = x | Y = c_{k}) P (Y = c_{k})} \\ (代入(1.3)) & = & \frac{P (Y = c_{k}) \prod_{j} P (X^{(j)} = x^{(j)} | Y = c_{k})}{\sum_{k} P (Y = c_{k}) \prod_{j} P (X^{(j)} = x^{(j)} | Y = c_{k})} \end{aligned}

于是朴素 Bayes 分类器为

\begin{aligned} y = f (x) = & \arg max_{c_{k}} \frac{P (Y = c_{k}) \prod_{j} P (X^{(j)} = x^{(j)} | Y = c_{k})}{\sum_{k} P (Y = c_{k}) \prod_{j} P (X^{(j)} = x^{(j)} | Y = c_{k})} . \\ (1.4) & = & \arg max_{c_{k}} P (Y = c_{k}) \prod_{j} P (X^{(j)} = x^{(j)} | Y = c_{k}) . \end{aligned}

1.2 后验概率最大化的含义

下面我们说明: 朴素 Bayes 法将实例分到后验概率最大的类的做法，与期望风险最小化等价.

事实上，如果 0-1 损失函数

L (Y, f (X)) = {\begin{aligned} 1, Y \neq f (X), \\ 0, Y = f (X), \end{aligned}

则它对应期望风险函数

R_{\exp} = E [L (Y, f (X))] = E_{X} \sum_{k = 1}^{K} [L (c_{k}, f (X))] P (c_{k} | X) .

对 $X = x$ 逐个极小化, 得

\begin{aligned} f (x) = & \arg min_{y \in Y} \sum_{k = 1}^{K} L (c_{k}, y) P (c_{k} | X = x) = \arg min_{y \in Y} \sum_{k = 1}^{K} P (y \neq c_{k} | X = x) \\ = & \arg min_{y \in Y} (1 - P (y = c_{k} | X = x)) = \arg max_{y \in Y} P (y = c_{k} | X = x) . \end{aligned}

这就是朴素 Bayes 方法.

2 朴素 Bayes 法的参数估计

2.1 极大似然估计

在朴素 Bayes 法中，我们要学习 $P (Y = c_{k}), P (X^{(j)} = x^{(j)} | Y = c_{k})$ . 可以用极大似然估计. 首先是先验概率 $P (Y = c_{k})$ :

\begin{matrix} (2.1) & P (Y = c_{k}) = \frac{\sum_{i = 1}^{N} I (y_{i} = c_{k})}{N}, 1 \leq k \leq K . \end{matrix}

(这个结论的推导在这个例子中)
设第 $j$ 个特征 $x^{(j)}$ 可能的取值的集合为 ${a_{j 1}, a_{j 2}, \dots, a_{j S_{j}}}$ , 则条件概率 $P (X^{(j)} = a_{j l} | Y = c_{k})$ 的极大似然估计为

\begin{aligned} (2.2) & P (X^{(j)} = a_{j l} | Y = c_{k}) = \frac{\sum_{i = 1}^{N} I (x_{i}^{(j)} = a_{j l}, y_{i} = c_{k})}{\sum_{i = 1}^{N} I (y_{i} = c_{k})}, \\ j = 1, \dots, n; l = 1, \dots, S_{j}; k = 1, \dots, K . \end{aligned}

2.2 学习与分类算法

朴素 Bayes 算法

输入训练数据 $T$ , 实例 $x$ ( $T = {(x_{1}, y_{1}), \dots, (x_{N}, y_{N})}$ , 其中 $x_{i} = (x_{i}^{(1)}, \dots, x_{i}^{(n)})^{T}$ , $x_{i}^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征, $x_{i}^{(j)} \in {a_{j 1}, \dots, a_{j S_{j}}}, 1 \leq j \leq n, 1 \leq l \leq S_{j}, y_{i} \in {c_{1}, \dots, c_{K}}$ )
输出 $x$ 的分类

计算先验概率和条件概率: (2.1) 和 (2.2).
对给定的 $x = (x^{(1)}, \dots, x^{(n)})^{T}$ , 计算 $P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} | Y = c_{k}) .$
确定 $x$ 的类 $y = \arg max_{c_{k}} P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} | Y = c_{k}) .$

例子

根据下表学习一个朴素贝叶斯分类器, 并确定 $x = (2, S)^{T}$ 的类标记. 取值集合为 $A_{1} = {1, 2, 3}, A_{2} = {S, M, L}, Y \in C = {1, - 1}$ .

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$X^{(1)}$	1	1	1	1	1	2	2	2	2	2	3	3	3	3	3
$X^{(2)}$	S	M	M	S	S	S	M	M	L	L	L	M	M	L	L
$Y$	-1	-1	1	1	-1	-1	-1	1	1	1	1	1	1	1	-1

解根据朴素 Bayes 算法直接给出 $\begin{aligned} P (Y = 1) = \frac{9}{15}, P (Y = - 1) = \frac{6}{15}, \end{aligned}$
以及 $\begin{aligned} P (X^{(1)} = 1 ∣ Y = 1) = \frac{2}{9}, P (X^{(1)} = 2 ∣ Y = 1) = \frac{3}{9}, P (X^{(1)} = 3 ∣ Y = 1) = \frac{4}{9}, \\ P (X^{(2)} = S ∣ Y = 1) = \frac{1}{9}, P (X^{(2)} = M ∣ Y = 1) = \frac{4}{9}, P (X^{(2)} = L ∣ Y = 1) = \frac{4}{9}, \\ P (X^{(1)} = 1 ∣ Y = - 1) = \frac{3}{6}, P (X^{(1)} = 2 ∣ Y = - 1) = \frac{2}{6}, P (X^{(1)} = 3 ∣ Y = - 1) = \frac{1}{6}, \\ P (X^{(2)} = S ∣ Y = - 1) = \frac{3}{6}, P (X^{(2)} = M ∣ Y = - 1) = \frac{2}{6}, P (X^{(2)} = L ∣ Y = - 1) = \frac{1}{6} . \end{aligned}$
因此对于给定的 $x = (2, S)^{T}$ , 计算 $\begin{aligned} P (Y = 1) P (X^{(1)} = 2 | Y = 1) P (X^{(2)} = S | Y = 1) = \frac{9 \cdot 3 \cdot 1}{15 \cdot 9 \cdot 1} = \frac{1}{45}, \\ P (Y = - 1) P (X^{(1)} = 2 | Y = - 1) P (X^{(2)} = S | Y = - 1) = \frac{6 \cdot 2 \cdot 3}{15 \cdot 6 \cdot 6} = \frac{1}{15}, \end{aligned}$ 其中 $Y = - 1$ 对应的概率更大, 因此 $y = - 1$ .

2.3 Bayes 估计

Bayes 估计用于规避概率值为 $0$ 的情形. 具体地, 条件概率的 Bayes 估计为

\begin{matrix} (2.3) & P_{λ} (X^{(j)} = a_{j l} | Y = c_{k}) = \frac{\sum_{i = 1}^{N} I (x_{i}^{(j)} = a_{j l}, y_{i} = c_{k}) + λ}{\sum_{i = 1}^{N} I (y_{i} = c_{k}) + S_{j} λ} . \end{matrix}

其中 $λ \geq 0$ . 当 $λ = 0$ 就是极大似然估计; $λ = 1$ 称为Laplace 平滑. 显然对任意 $l = 1, \dots, S_{j}, k = 1, \dots, K$ 有

P_{λ} (X^{(j)} = a_{j l} | Y = c_{k}) > 0, \sum_{l = 1}^{S_{j}} P (X^{(j)} = a_{j l} | Y = c_{k}) = 1.

先验概率的 Bayes 估计为

\begin{matrix} (2.4) & P_{λ} (Y = c_{k}) = \frac{\sum_{i = 1}^{N} I (y_{i} = c_{k}) + λ}{N + K λ}, \end{matrix}