朴素贝叶斯2021-09-13

朴素贝叶斯的学习方法概念定义学习方法朴素的含义如何做分类贝叶斯分类器后验概率最大化的含义朴素贝叶斯的参数估计极大似然估计 $P(Y = c_k)$ 估计 $P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)$ 估计学习与分类算法贝叶斯估计

朴素贝叶斯的学习方法

概念定义

$\mathcal{X} \subseteq \mathbf{R}^n$ $n$ 维向量 $\mathcal{Y} = \{c1, c2, \cdots, c_K \}$ 特征向量 $\mathbf{x} \in \mathcal{X}$ $y \in \mathcal{Y}$ $X$ $\mathcal{X}$ $Y$ $\mathcal{Y}$ $P(X,Y)$ $X$ $Y$ $T$ $P(X,Y)$ $T=\{(\mathbf{x_1}, y_1),(\mathbf{x_2},y_2),\cdots,(\mathbf{x_M},y_M) \}$ $注意：\mathbf{x}为n \times 1向量，M为训练集大小$

学习方法

朴素贝叶斯法通过训练数据集学习 $P(X,Y)$ 。具体地，学习以下先验概率分布及条件概率分布。

先验概率分布
$\begin{matrix} (1) & P (Y = c_{k}), k = 1, 2, \dots, K \end{matrix}$
条件概率分布

\begin{matrix} (2) & P (X = x ∣ Y = c_{k}) = P (X^{(1)} = x^{(1)}, \dots, X^{(n)} = x^{(n)} ∣ Y = c_{k}), k = 1, 2, \dots, K \end{matrix}

$P(X,Y)$ ：

\begin{matrix} (3) & P (X = x, Y = c_{k}) = P (Y = c_{k}) \cdot P (X = x ∣ Y = c_{k}) \end{matrix}

朴素的含义

$P\left(X=\mathbf{x} \mid Y=c_{k}\right)=P\left(X^{(1)}={x^{(1)}}, \cdots, X^{(n)}={x^{(n)}} \mid Y=c_{k}\right)$ 的参数是指数级的，其估计实际不可实行。

条件独立性假设 $Y=c_{k}$ $\mathbf{x}$ 的各分量独立。具体如下所示：

\begin{matrix} (4) & \begin{aligned} P (X = x ∣ Y = c_{k}) & = P (X^{(1)} = x^{(1)}, \dots, X^{(n)} = x^{(n)} ∣ Y = c_{k}) \\ = \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k}) \end{aligned} \end{matrix}

朴素贝叶斯实际上学习到生成数据的机制，所以属于生成模型。

如何做分类

$\mathbf{x}$ 后验概率分布 $P\left(X=\mathbf{x} \mid Y=c_{k}\right)$ $\mathbf{x}$ 的预测类别。根据贝叶斯定理：

\begin{matrix} (5) & \begin{aligned} P (Y = c_{k} ∣ X = x) & = \frac{P (Y = c_{k}, X = x)}{P (x)} \\ = \frac{P (X = x ∣ Y = c_{k}) P (Y = c_{k})}{\sum_{k} P (x, y)} \\ = \frac{P (X = x ∣ Y = c_{k}) P (Y = c_{k})}{\sum_{k} P (X = x ∣ Y = c_{k}) P (Y = c_{k})} \\ \approx \frac{P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k})}{\sum_{k} P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k})} \\ 其 中 ， k & = 1, 2, \dots, K \end{aligned} \end{matrix}

$\mathbf{x}$ ，再去判断是否为垃圾邮件，就是所谓的后验概率。

贝叶斯分类器

朴素贝叶斯分类器可以表示为：

\begin{matrix} (6) & 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} P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k})} \end{matrix}

$c_k$ 都是相同的，因此，上式可以简化为：

\begin{matrix} (7) & \begin{aligned} y = f (x) & = \arg max_{c_{k}} P (Y = c_{k} ∣ X = x) \\ = \arg max_{c_{k}} P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k}) \end{aligned} \end{matrix}

后验概率最大化的含义

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

假设选择0-1损失函数：

\begin{matrix} (8) & L (Y, f (X)) = {\begin{cases} 1, & Y \neq f (X) \\ 0, & Y = f (X) \end{cases} 其 中 ， f (X) 是 分 类 决 策 函 数 \end{matrix}

$P(X,Y)$ 取的，期望风险函数为：

\begin{matrix} (9) & \begin{aligned} R_{\exp} (f) = E [L (Y, f (X))] \\ = & \int_{χ \times y} L (y, f (x)) P (x, y) d x d y \\ = & \int_{χ \times y} L (y, f (x)) P (y ∣ x) P (x) d x d y \\ = & \int_{χ} \int_{Y} L (y, f (x)) P (y ∣ x) d y P (x) d x \end{aligned} \end{matrix}

$H(x) = \int_{Y} L(y, f(x)) P(y \mid x) d y$ $H(x)$ $P(y \mid x)$ $H(x)$ $P(x)$ $X=x$ $P(x)$ （先验概率）为常数，因此期望风险最小化可转换为条件期望最小化，即

\begin{matrix} (10) & \arg min_{y \in Y} R_{\exp} (f) = \arg min_{y \in Y} H (x) \end{matrix}

$T$ $\mathbf{x}$ 逐个最小化即可，由此可得到：

\begin{matrix} (11) & \begin{aligned} f (x) & = \arg min_{y \in Y} R_{\exp} (f) \\ = \arg min_{y \in Y} H (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) \\ 其 中 ， & y 为 模 型 预 测 的 输 出 类 别 ， c_{k} 为 真 是 类 别 \end{aligned} \end{matrix}

$公式解释：y必然属于\mathcal{Y} = \{c1, c2, \cdots, c_K \}中的一个，假设为c_k。那么剩下的c_1,c_2,c_{k-1},c_{k+1},\cdots,c_K的概率和必然为1-P(c_k)$

这样一来，根据期望风险最小化准则就得到了后验概率最大化准则，即朴素贝叶斯采用的原理：

\begin{matrix} (12) & f (x) = \arg max_{c_{k}} P (c_{k} ∣ X = x) \end{matrix}

朴素贝叶斯的参数估计

极大似然估计

在朴素贝叶斯方法中，学习意味着估计：

$P(Y = c_k)$
$P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)$
因此，可以使用极大似然法估计相应的概率。

$P(Y = c_k)$ 估计

$P(Y = c_k)$ 的极大似然估计是：

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

$P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)$ 估计

$j$ $x^{(j)}$ $\{a_{j1}, a_{j2}, \cdots, a_{jS_j} \}$ $P(X^{(j)} = a_{jl} \mid Y=c_k)$ 的极大似然估计是：

\begin{matrix} (14) & \begin{aligned} 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, 2, \dots, n; l = 1, 2, \dots, S_{j}; k = 1, 2, \dots, K \end{aligned} \end{matrix}

$x_i ^{(j)}$ $i$ $j$ $a_{jl}$ $j$ $l$ $I$ 为指示函数。

学习与分类算法

$算法 1.1 (朴素贝叶斯算法)$

$输入: 训练数据 T=\left\{\left(\mathbf{x_{1}}, y_{1}\right),\left(\mathbf{x_{2}}, y_{2}\right), \cdots,\left(\mathbf{x_{N}}, y_{N}\right)\right\}, 其中 \mathbf{x_{i}}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots,\right., \left.x_{i}^{(n)}\right)^{\mathrm{T}}, {x_{i}^{(j)}} 是第 i 个样本的第 j 个特征,\\ \quad \; \mathbf{x_{i}^{(j)}} \in\left\{a_{j 1}, a_{j 2}, \cdots, a_{j S_{j}}\right\}, a_{j l} 是第 j 个特征可能取的第 l 个值, j=1,2, \cdots, n, l=1,2, \cdots, S_{j}, y_{i} \in\left\{c_{1}, c_{2}, \cdots, c_{K}\right\};\\ \quad \; 实例 \mathbf{x};$

$输出：\mathbf{x}的分类$

$(1)计算先验概率及条件概率$

\begin{matrix} (15) & \begin{matrix} P (Y = c_{k}) = \frac{\sum_{i = 1}^{N} I (y_{i} = c_{k})}{N}, k = 1, 2, \dots, K \\ 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, 2, \dots, n; l = 1, 2, \dots, S_{j}; k = 1, 2, \dots, K \end{matrix} \end{matrix}

$(2) 对于给定的实例 \mathbf{x}=\left(x^{(1)}, x^{(2)}, \cdots, x^{(n)}\right)^{\mathrm{T}}$ ，计算

\begin{matrix} (16) & P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k}), k = 1, 2, \dots, K \end{matrix}

$(3) 预测实例\mathbf{x}的类别$

\begin{matrix} (17) & y = \arg max_{c_{k}} P (Y = c_{k}) \prod_{j = 1}^{n} P (X^{(j)} = x^{(j)} ∣ Y = c_{k}) \end{matrix}

贝叶斯估计

使用极大似然估计可能会出现所要估计的概率值为0的情况。这时会影响到后验概率的计算结果，使分类产生误差。解决这一问题的方法是使用贝叶斯估计。具体地，条件概率的贝叶斯估计是：

\begin{matrix} (18) & 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} λ} 其 中 ， λ \geq 0 \end{matrix}

$\lambda > 0$ $\lambda = 0$ 时就是极大似然估计。

$\lambda = 1$ $l=1,2,\cdots,S_j，k=1,2,\cdots,K$ ，有：

\begin{matrix} (19) & \begin{aligned} 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 \end{aligned} \end{matrix}

$公式(18)$ 确实为一种概率分布。

同样，先验概率的贝叶斯估计是：

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