贝叶斯分类器

参考文献：

• 《统计学习方法》第4章 朴素贝叶斯法
• 《机器学习》第7章 贝叶斯分类器

贝叶斯理论系列在统计学中占用极其重要的地位。本节主要记录的是朴素贝叶斯法。它是一种基于贝叶斯定理和条件独立性假设的分类方法。

和感知机算法中类似，我们作出如下假设：

输入空间$\mathcal{X}\subseteq R^q$，输出空间$\mathcal{Y}=\{ c_1,c_2,\dots,c_k \}$，而输入的特征向量记作$\mathbf{x}\in\mathcal{X}\subseteq R^q$，输出类标记记作$y\in \mathcal{Y}$，而输入输出的随机变量记作$X,Y$。另外，我们把训练数据集表示为

$$\begin{align} T=\{ (\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \cdots, (\mathbf{x}^{(n)},y^{(n)}) \} \end{align}$$

那么，朴素贝叶斯法的基本思路是：

• 基于条件独立性假设，学习输入输出的联合概率分布$P(X,Y)$
• 基于贝叶斯定理，求出后验概率的最大输出$P(Y|X)$

贝叶斯决策论

对于上述假设，记$\lambda_{ij}$是将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失，而基于后验概率$P(c_i|\mathbf{x})$，可以计算将样本$\mathbf{x}$分类为$c_i$所产生的期望损失，即“条件风险”

$$R(c_i|\mathbf{x}) = \sum_{j=1}^k \lambda_{ij}P(c_j|\mathbf{x})$$

优化目标表示为

$$h^{*}(\mathbf{x}) = \arg\min_{c\in \mathcal{Y}}R(c|\mathbf{x})$$

常见地，若目标是最小化分类错误率，则误判损失$\lambda_{ij}$可以表示为

$$\lambda_{ij}=\begin{cases} 0, \ if \quad i=j \\ 1, \ otherwise \end{cases}$$

故此时条件风险可以表示为

$$R(c_i|\mathbf{x}) = 1 - P(c_i|\mathbf{x})$$

而最小化分类错误率的优化目标表示为

$$h^{*}(\mathbf{x}) = \arg\max_{c\in\mathcal{Y}}P(c|\mathbf{x})$$

可以看出，后验概率$P(c|\mathbf{x})$在贝叶斯判定准则中非常关键。

两个基本知识点

学习朴素贝叶斯法，离不开最基本的两个知识点：贝叶斯定理和条件独立性。下面分别记录一下这两者。

贝叶斯定理

概率论与数理统计中已经学过贝叶斯定理，它的基本形式如下

$$P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}$$

其中，可以作出如下理解：$X$是我们观测的变量，$Y$是我们需要估计的变量；而$P(Y)$则是先验概率，因为它实际上是在没有采样之前根据经验得到的一个概率值；$P(Y|X)$则是后验概率，因为此时已经进行了采样（给定$X$）。

具体地，在贝叶斯决策中，我们需要计算

$$P(c|\mathbf{x}) = \frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})}$$

其中，$c$为类别标签，$\mathbf{x}$为样本。

条件独立性

直接给出数学定义：假设三个随机变量（事件）$X,Y,Z$，若满足下式

$$P(X,Y|Z) = P(X|Z)P(Y|Z)$$

则称$X,Y$条件独立。

注意条件独立性不等同于独立性。事实上，这两者并不能互推。

而朴素贝叶斯分类器采用了“属性条件独立性假设”，即假设样本所有的属性相互独立，故

$$P(c|\mathbf{x}) = \frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})} = \frac{P(c)}{P(\mathbf{x})}\prod_{i=1}^dP(x_i|c)$$

朴素贝叶斯

用极大似然法作参数估计

这一部分主要是使用极大似然法估计参数。这一部分由于和课后习题关联甚密，因此在课后习题部分作详细描述。此处仅给出两个公式。

首先给出先验概率的估计

$$P(Y=c_i)=\frac{\displaystyle \sum_{t=1}^n\left[ y^{(t)}=c_i \right]}{n} \tag{2}$$

其次，设$X_j$的取值有$S_j$种可能，记为$\{a_{j1}, a_{j2},\dots,a_{jS_j} \}$，因此条件概率的估计

$$P(X_j=a_{jl}|Y=c_i) = \frac{\displaystyle \sum_{t=1}^n\left[ x^{(t)}_j=a_{jl},y^{(t)}=c_i \right]}{\displaystyle \sum_{t=1}^n\left[ y^{(t)}=c_i \right]} \tag{3}$$

参数学习

条件概率分布

$$P(X=\mathbf{x}|Y=c_i)=P(X_1=x_1,X_2=x_2,\dots,X_p=x_p|Y=c_i),i\in\{1,2,\dots,k\}$$

而之前提过，朴素贝叶斯基于条件独立性假设在类确定的条件下，各个特征变量条件独立，因此上式可以转化为

$$P(X=\mathbf{x}|Y=c_i)=\prod_{j=1}^pP(X_j=x_j|Y=c_i),i\in \{1,2,\dots,k\} \tag{4}$$

接下来，基于贝叶斯定理，计算后验概率

$$P(Y=c_i|X=\mathbf{x})=\frac{P(X=\mathbf{x}|Y=c_i)P(Y=c_i)}{\sum\limits_iP(X=\mathbf{x}|Y=c_i)P(Y=c_i)} \tag{5}$$

于是可以把公式$4$代入公式$5$，得

$$P(Y=c_i|X=\mathbf{x})=\frac{P(Y=c_i)\prod\limits_j P(X_j=x_j|Y=c_i)}{\sum\limits_iP(Y=c_i)\prod\limits_jP(X_j=x_j|Y=c_i)}$$

因此，朴素贝叶斯需要求出使得上述后验概率最大的分类结果$c_i$，即

$$c_*=\arg\max_{c_i} = \frac{P(Y=c_i)\prod\limits_j P(X_j=x_j|Y=c_i)}{\sum\limits_iP(Y=c_i)\prod\limits_jP(X_j=x_j|Y=c_i)}$$

而上式的分母与$c_i$无关，因此可以化简为

$$c_*=\arg\max_{c_i} = P(Y=c_i)\prod\limits_j P(X_j=x_j|Y=c_i)$$

贝叶斯估计

这一部分的详细描述同样见课后习题。需要指出的是，贝叶斯估计弥补了之前极大似然估计参数过程中还可能出现概率值为0这种意外的缺陷。我们在随机变量各个取值的频数上，赋予一个参数$\lambda>0$，避免出现概率值为0的情况，于是式$2$变为下式

$$\displaystyle P_\lambda(Y=c_i) = \frac{\displaystyle \sum_{t=1}^n \left[ y^{(t)}=c_i \right] + \lambda}{n+k \lambda}, \quad i= 1,2,\ldots,k \tag{6}$$

式$3$变为下式

$$\displaystyle P_{\lambda}(X_j=a_{jl} | Y = c_i) = \frac{\displaystyle \sum_{t=1}^n \left[ x_j^{(t)}=a_{jl},y^{(t)}=c_i \right] + \lambda}{\displaystyle \sum_{t=1}^n \left[y^{(t)}=c_i\right] + S_j \lambda} \tag{7}$$

半朴素贝叶斯分类器

对于概率$P(\mathbf{x}|c)$，朴素贝叶斯分类器采取了“属性条件独立”的假设，而这个假设在现实中往往很难成立。半朴素分类器适当考虑一些属性之间的相互依赖关系。其中“独依赖估计”是最常用的策略，即假设每个属性最多依赖一个其他属性。我们可以用一张有向图表示属性间的依赖关系。

贝叶斯网络

贝叶斯网络，也称信念网络，记作$B$，通常由结构$G$和参数$\Theta$两部分构成，即$B=(G,\Theta)$。具体地，

• 结构$G$描述属性间的依赖关系；
• 参数$\Theta$包含了每个属性的条件概率表，描述属性间的联合概率分布

网络结构

网络结构用有向无环图描述属性间的依赖关系，表达了属性之间的条件独立性。对于结点$x_i$，记其父结点集合为$\pi_i$，网络假设每个属性结点与其非后裔结点独立，故贝叶斯网络中，属性$x_1,x_2,\cdots,x_d$的联合概率分布表示为

$$P_B(x_1,x_2,\cdots,x_d) = \prod_{i=1}^dP_B(x_i|\pi_i) = \prod_{i=1}^d\theta_{x_i|\pi_i}$$

学习

鉴于贝叶斯网络的两个关键部分：结构和参数，后者的学习过程相对简单——只需统计样本数量，估计各个属性结点的条件概率表即可。故最首要的任务，便是学习贝叶斯网络的结构：根据给定的训练数据集，找出最合适的网络结构。常见的做法是，定义一个评分函数，用以衡量训练数据集和贝叶斯网络结构的“契合度”，基于该评分函数，寻找结构最优的贝叶斯网络。

评分函数记作

$$s(B|D) = f(\theta)|B| - LL(B|D)$$

其中，$f(\theta)$为每个参数$\theta$的编码长度，$|B|$为贝叶斯网络参数数量，$LL(B|D)$为对数似然。于是，贝叶斯网络的学习便可描述为如下优化问题

$$\min_B s(B|D) = f(\theta)|B| - LL(B|D)$$

推断

基于训练好的贝叶斯网络，可以进行推断，即根据已知变量的观测值来推测待查询变量。具体地，令$\mathbf{Q}=\{ Q_1,Q_2,\dots,Q_n \}$表示待查询变量，$\mathbf{q}=\{q_1,q_2,\dots,q_n\}$为待查询变量的一组取值，$\mathbf{E}=\{ E_1,E_2,\dots,E_k \}$表示已知变量（也称证据变量），$\mathbf{e}=\{e_1,e_2,\dots,e_k\}$为证据变量的一组取值，贝叶斯推断的目标是计算后验概率$P(\mathbf{Q}=\mathbf{q}|\mathbf{E}=\mathbf{e})$。现实应用中，该后验概率无法精确计算得到的（即无法进行精确推断），因此只能进行近似推断，而贝叶斯推断中常用的近似推断为吉布斯采样。

课后习题

习题1

使用极大似然估计法推导出朴素贝叶斯法中的概率估计公式。为了和上文相匹配，此处摘录的证明公式符号和原书略有出入。

1. 公式$2$，这里再次给出 $$P(Y=c_i)=\frac{\displaystyle \sum_{t=1}^n\left[ y^{(t)}=c_i \right]}{n}$$

1. 公式$3$，这里再次给出 $$P(X_j=a_{jl}|Y=c_i) = \frac{\displaystyle \sum_{t=1}^n\left[ x^{(t)}_j=a_{jl},y^{(t)}=c_i \right]}{\displaystyle \sum_{t=1}^n\left[ y^{(t)}=c_i \right]}$$

极大似然估计

我们知道极大似然估计法是一种典型的频率学派方法，思想是给定观测样本集$T$，求解出使得所有样本出现概率最大的参数，进而转化为优化问题

$$\max f(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\dots,\mathbf{x}^{(n)}|\theta)$$

更方便地，记

$$\mathcal{L}(\theta) = f(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\dots,\mathbf{x}^{(n)}|\theta)$$

则极大似然估计最终转化为求解最优参数

$$\theta_* = \arg\max_\theta \mathcal{L}(\theta)$$

接下来求（偏）导数即可。

正是基于这样的思路，此处我们的思路就是将$P(Y=c_i)$转换为参数表示，求解出最优的参数即$P(Y=c_i)$的结果。

证明1

设$P(Y=c_i)=\theta_i,i\in \{1,2,\dots,k\}$，则似然函数表示为

$$\mathcal{L}(\theta_i) = P(y^{(1)},y^{(2)},\dots,y^{(n)}|\theta_i) \tag{8}$$

记$n$个样本中出现$y^{(j)}=c_i,j\in \{1,2,\dots,n\}$的样本数量为$m$，即

$$m = \sum_{j=1}^n \left[ y^{(j)}=c_i \right]$$

因此，类别变量可以视为满足伯努利分布，$Y\sim B(n,\theta_i)$，因此似然函数式$8$可以化为

$$\begin{aligned} \mathcal{L}(\theta_i) &= \prod_{j=1}^n P(y^{(j)}) \\ &= C_n^m \theta_i^m(1-\theta_i)^{n-m} \end{aligned}$$

为了方便计算，我们对上式取对数，得到对数似然函数

$$\log \mathcal{L}(\theta_i) = \log C_n^m + m\log \theta_i + (n-m)\log (1-\theta_i)$$

接下来对其求导数即可：

$$\frac{\partial}{\partial \theta_i} \mathcal{L}(\theta_i) = \frac{m}{\theta_i} + \frac{m-n}{1-\theta_i}$$

令上式等于0，得到最优参数，即

$$\theta_* = \frac{m}{n}$$

也就是式子

$$P(Y=c_i) = \theta_* = \frac{\sum\limits_{j=1}^n \left[ y^{(j)} = c_i \right]}{n},i\in \{1,2,\dots,k\}$$

证明2

设$P(X_j=a_{jl}|Y=c_i)=\lambda_l$，则$P(X_j\ne a_{jl}|Y=c_i)=1-\lambda_l$，同样地，设

• $n$个样本中出现$y^{(k)}=c_i,k\in \{1,2,\dots,n\}$的样本数量为$m$
• $n$个样本中同时出现$x^{(k)}_j=a_{jl},y^{(k)}=c_i,k\in\{1,2,\dots,n\},j\in\{1,2,\dots,p\}, l\in \{1,2,\dots,S_j\}$的样本数量为$t$

我们考虑出现这$m$个样本的概率最大值，即似然函数

$$\begin{aligned} \mathcal{L}(\lambda_l) &= C_m^t\lambda_l^t(1-\lambda_l)^{m-t} \end{aligned}$$

同理可以求得

$$\lambda_* = \frac{t}{m}$$

也就是式子

$$P(X_j=a_{jl}|Y=c_i) = \frac{\sum\limits_{k=1}^n \left[ x^{(k)}_j=a_{jl},y^{(k)}=c_i \right]}{\sum\limits_{k=1}^n \left[ y^{(k)}=c_i \right]}$$

习题2

为了和上文相匹配，此处摘录的证明公式符号和原书略有出入。

使用贝叶斯估计，证明

1. 公式$6$

   $$\displaystyle P_\lambda(Y=c_i) = \frac{\displaystyle \sum_{t=1}^n \left[ y^{(t)}=c_i \right] + \lambda}{n+k \lambda}, \quad i= 1,2,\ldots,k$$

2. 公式$7$

   $$\displaystyle P_{\lambda}(X_j=a_{jl} | Y = c_i) = \frac{\displaystyle \sum_{t=1}^n \left[ x_j^{(t)}=a_{jl},y^{(t)}=c_i \right] + \lambda}{\displaystyle \sum_{t=1}^n \left[y^{(t)}=c_i\right] + S_j \lambda}$$

首先，在证明之前，先介绍一下题干中提到的贝叶斯估计，以及它和第一问中的极大似然估计有何区别和联系。

贝叶斯估计

和频率学派的观点不同，贝叶斯学派普遍认为，待估计的参数$\theta$也是一个随机变量，因此它同样也服从某一个分布，它的数学描述如下

$$\pi(\theta|X) = \frac{f(X|\theta)\pi(\theta)}{\displaystyle \int f(X|\theta)\pi(\theta)d\theta}$$

其中，

• $\pi(\theta)$是参数$\theta$的先验分布，往往是基于经验的、非采样的主观认识；
• $\pi(\theta|X)$是后验分布，是基于采样后的、对先验进行了一些校正的分布。

狄利克雷分布（Dirichlet）

狄利克雷分布描述了概率的分布，假设一组变量$\mathbf{x}=(x_1,x_2,\dots,x_d)$和参数$\Alpha=(\alpha_1,\alpha_2,\dots,\alpha_d)$，其中$\sum_ix_i=1$，$\alpha_i>0$且$\hat{\alpha}=\sum_i\alpha_i$，变量满足参数为$\Alpha$的狄利克雷分布，即

$$\mathbf{Dir}(\mathbf{x}|\Alpha) = \frac{\Gamma(\hat{\alpha})}{\displaystyle \prod_{i=1}^d\Gamma(\alpha_i)}\prod_{i=1}^dx_i^{\alpha_i-1}$$

狄利克雷分布有性质：

• 期望$\displaystyle E(x_i)=\frac{\alpha_i}{\hat{\alpha}}$
• 方差$\displaystyle Var(x_i)=\frac{\alpha_i(\hat{\alpha}-\alpha_i)}{\hat{\alpha}^2(\hat{\alpha}+1)}$

证明1

和第一问类似的，我们将概率参数化，设

$$\theta_i=P_\lambda(Y=c_i)$$

记所有样本中，出现$Y=c_i$的样本数量为$m_i$，即$m_i = \sum\limits_{t=1}^n\left[ y^{(t)}=c_i \right]$，我们把所有的$m_i$表示为$\mathbf{m}=(m_1,m_2,\dots,m_k)^T$，而参数$\Theta=(\theta_1,\theta_2,\dots,\theta_k)^T$；

我们选定参数$\Theta$满足狄利克雷分布，其中参数$\Alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)^T$，于是有

$$\mathbf{Dir}(\Theta|\mathbf{\Alpha}) = \frac{\displaystyle \Gamma(\hat{\alpha})}{\displaystyle \prod_{t=1}^k \Gamma(\alpha_i)}\prod_{t=1}^k\theta_t^{\alpha_t-1} \tag{9}$$

为了方便起见，把与$\Theta$无关的系数记成一个整体

$$C(\Alpha) = \frac{\displaystyle \Gamma(\hat{\alpha})}{\displaystyle \prod_{t=1}^k \Gamma(\alpha_i)}$$

另外，在类别未知前提下，各个类别的样本数量一致，均为$\lambda$，也即

$$\alpha_1=\alpha_2=\dots=\alpha_k=\lambda$$

于是，式$9$可以化为

$$\mathbf{Dir}(\Theta|\mathbf{\Alpha}) = C(\lambda) \prod_{t=1}^k\theta_t^{\lambda-1}$$

考虑给定参数$\Theta$下出现所有样本的概率

$$P(\mathbf{m}|\Theta) = \prod_{t=1}^k\theta_t^{m_t}$$

根据贝叶斯公式，得后验分布

$$\begin{aligned} P(\Theta|\mathbf{m}) &= \frac{P(\mathbf{m}|\Theta)P(\Theta)}{P(\mathbf{m})} \\ &\propto P(\mathbf{m}|\Theta)P(\Theta) \\ &\propto C(\lambda)\prod_{t=1}^k\theta_t^{m_t}\theta_t^{\lambda-1} \\ &\propto \prod_{t=1}^k\theta_t^{m_t+\lambda-1} \end{aligned}$$

仔细观察发现，上式也是一个狄利克雷分布的形式，于是根据狄利克雷分布的性质得到期望值

$$\begin{aligned} E(\theta_i) &= \frac{m_i+\lambda}{\displaystyle \sum_{t=1}^k(m_t+\lambda)} \\ &= \frac{m_i+\lambda}{\displaystyle \sum_{t=1}^km_t+k\lambda} \\ &= \frac{m_i+\lambda}{n+k\lambda} \end{aligned}$$

最后，随机变量$\theta_i$取$\theta_i$的期望，得到公式$6$。

证明2

实际上，和上述证明1思路几乎一致，只不过这里换成了证明条件概率。

我们作出和证明1中类似的假设和记法：

• 设所有样本中出现$X_j=a_{jl},Y=c_i$的样本数量为$m_l$，其中$X_j$有$S_j$种可能取值，即$m_l=\sum\limits_{t=1}^n\left[ x^{(t)}_j=a_{jl},y^{(t)}=c_i \right],l\in \{1,2,\dots,S_j\}$，记$\mathbf{m}=(m_1,m_2,\dots,m_{S_j})^T$
• 设$P_\lambda(X_j=a_{jl}|Y=c_i)=w_l$，记$\mathbf{w}=(w_1,w_2,\dots,w_{S_j})^T$

类似地，给参数$\mathbf{w}$一个先验分布——参数为$\lambda$的狄利克雷分布，因此有

$$\mathbf{Dir}(\mathbf{w}) = C(\lambda) \prod_{t=1}^{S_j}w_t^{m_t}$$

剩下的步骤和证明1后续过程几乎一致了，也是先用贝叶斯公式得到后验分布$P(\mathbf{w}|\mathbf{m})$，然后根据狄利克雷分布求出期望值，随即证明出式$7$。

赏