推导与推广

本文旨在解决如下两个问题：

• 为何后验概率最大化是贝叶斯决策？
• 如何导出离散型朴素贝叶斯的算法？

以及旨在叙述一些朴素贝叶斯的推广。具体而言、我们会简要介绍：

• 半朴素贝叶斯
• 贝叶斯网

朴素贝叶斯与贝叶斯决策

可以证明，应用朴素贝叶斯算法得到的模型所做的决策就是 0-1 损失函数下的贝叶斯决策。这里先说一个直观：在损失函数为 0-1 损失函数的情况下，决策风险、亦即训练集的损失的期望就是示性函数某种线性组合的期望、从而就是相对应的概率；朴素贝叶斯本身就是运用相应的概率做决策、所以可以想象它们很有可能等价

下给出推导过程，首先我们要叙述一个定理：令$\rho(x_1,...,x_n)$满足：

$$\rho\left( x_{1},\ldots,x_{n} \right) = \inf_{a\in A}{\int_{\Theta}^{}{L\left( \theta,a \right)\xi\left( \theta \middle| x_{1},\ldots,x_{n} \right)\text{d}\theta}}$$

亦即$\rho(x_1,...,x_n)$是已知训练集$\tilde X=(x_1,...,x_n)$的最小后验期望损失。那么如果一个决策$\delta^*(x_1,...,x_n)$能能使任意一个含有 n 个样本的训练集的后验期望损失达到最小、亦即：

$$\int_{\Theta}^{}{L\left( \theta,\delta^{*}\left( x_{1},\ldots,x_{n} \right) \right)\xi\left( \theta \middle| x_{1},\ldots,x_{n} \right)d\theta = \rho\left( x_{1},\ldots,x_{n} \right)}\ (\forall x_{1},\ldots,x_{n})$$

的话，那么$\delta^*$就是贝叶斯决策。该定理的数学证明要用到比较深的数学知识、这里从略，但从直观上来说是可以理解的

是故如果我们想证明朴素贝叶斯算法能导出贝叶斯决策、我们只需证明它能使任一个训练集$\tilde X$上的后验期望损失$R\left( \theta,\delta(\tilde X)\right)$最小即可。为此，需要先计算$R\left( \theta,\delta(\tilde X)\right)$：

注意：这里的期望是对联合分布取的，所以可以取成条件期望

$$R\left( \theta,\delta(\tilde{X}) \right) = EL\left( \theta,\delta\left( \tilde{X} \right) \right) = E_{X}\sum_{k = 1}^{K}{\tilde{L}(c_{k},f\left( X \right))p(c_{k}|X)}$$

为了使上式达到最小，我们只需逐个对$X=x$最小化，从而有：

$$\begin{align} f\left( x \right) &= \arg{\min_{y\in S}{\sum_{k = 1}^{K}{\tilde{L}\left( c_{k},y \right)p\left( c_{k} \middle| X = x \right)}}} \\ &= \arg{\min_{y\in S}{\sum_{k = 1}^{K}{p\left( y \neq c_{k} \middle| X = x \right)}}} \\ &= \arg{\min_{c_k}\left\lbrack 1 - p\left( c_{k} \middle| X = x \right) \right\rbrack} \\ &= \arg{\max_{c_k}{p\left( c_{k} \middle| X = x \right)}} \end{align}$$

此即后验概率最大化准则、也就是朴素贝叶斯所采用的原理

离散型朴素贝叶斯算法的推导

离散型朴素贝叶斯算法的推导相对简单但比较繁琐，核心的思想是利用示性函数将对数似然函数写成比较“整齐”的形式、再运用拉格朗日方法进行求解

在正式推导前，我们先说明一下符号约定：

• 记已有的数据为$\tilde X=(x_1,x_2,...,x_N)$，其中： $$x_{i} = \left( x_{i}^{\left( 1 \right)},x_{i}^{\left( 2 \right)},\cdots,x_{i}^{\left( n \right)} \right)^{T}\ (i = 1,2,\cdots,N)$$
• $X^{\left( j \right)}$表示生成数据$x^{\left( j \right)}$的随机变量
• 随机变量$X^{\left( j \right)}$的取值限制在集合$K_{j} = \{ a_{j1},a_{j2},\ldots,a_{jS_j}\}\ (j = 1,2,\cdots,n)$中
• 类别$Y$的可能取值集合为$S = \{ c_{1},c_{2},\ldots,c_{K}\}$
• 用$\theta^{c_{k}}(k = 1,2,\ldots,K)$表示先验概率$p(Y = c_{k})$
• 用$\theta_{j,a_{jl}}^{c_{k}}$表示条件概率$p(X^{\left( j \right)} = a_{jl}|Y = c_{k})\ (j \in \left\{ 1,\ldots,n \right\},l \in \{ 1,\ldots,S_{j}\},k \in \{ 1,\ldots,K\}$

接下来就可以开始算法推导了：

计算对数似然函数

$$\begin{align} \ln L &= \ln{\prod_{i = 1}^{N}\left( \theta^{y_{i}} \cdot \prod_{j = 1}^{n}{\theta_{j,x_{i}^{\left( j \right)}}^{y_{i}}\ } \right)} \\ &= \sum_{k = 1}^{K}{n_{k}\ln{\theta^{k} + \sum_{j = 1}^{n}{\sum_{k = 1}^{K}{\sum_{l = 1}^{S_{j}}{n_{j,l}^{k}\ln\theta_{j,a_{jl}}^{c_{k}}}\ }}}} \end{align}$$

其中

$$\begin{align} n_{s} &= \sum_{i = 1}^{N}{I\left( y_{i} = c_{s} \right)} \\ n_{j,l}^{k} &= \sum_{i = 1}^{N}{I\left( x_{i}^{\left( j \right)} = a_{jl}{,y}_{i} = c_{k} \right)} \end{align}$$

极大化似然函数

为此，只需分别最大化

$$f_{1} = \sum_{k = 1}^{K}{n_{k}\ln\theta^{k}}$$

和

$$f_{2} = \sum_{j = 1}^{n}{\sum_{k = 1}^{K}{\sum_{l = 1}^{S_{j}}{n_{j,l}^{k}\ln\theta_{j,a_{jl}}^{c_{k}}}\ }}$$

对于后者，由条件独立性假设可知、我们只需要对$j=1,2,...,n$分别最大化：

$$f_{2}^{\left( j \right)} = \sum_{k = 1}^{K}{\sum_{l = 1}^{S_{j}}{n_{j,l}^{k}\ln\theta_{j,a_{jl}}^{c_{k}}}\ }$$

即可。我们利用拉格朗日方法来求解该问题，用到的约束条件是：

$$\begin{align} \sum_{k = 1}^{K}\theta^{k} &= \sum_{k = 1}^{K}{p\left( Y = c_{k} \right)} = 1 \\ \sum_{l = 1}^{S_{j}}{\theta_{j,l}^{k}} &= \sum_{l = 1}^{S_{j}}{p\left( X^{\left( j \right)} = a_{jl} \middle| Y = c_{k} \right) = 1\ \left( \forall k \in \left\{ 1,\ldots,K \right\},j \in \left\{ 1,\ldots,n \right\} \right)} \end{align}$$

从而可知

$$L_{1} = \sum_{k = 1}^{K}{n_{k}\ln{\theta^{k} + \alpha\left( \sum_{k = 1}^{K}{\theta^{k} - 1} \right)}}$$

由一阶条件

$$\frac{\partial L_{1}}{\partial\theta_{k}} = \frac{\partial L_{1}}{\partial\alpha} = 0$$

可以解得

$$p\left( Y = c_{k} \right) = \theta^{k} = \frac{n_{k}}{N} = \frac{\sum_{i = 1}^{N}{I(y_{i} = c_{k})}}{N}$$

同理，对$f_2^{(j)}$应用拉格朗日方法，可以得到

$$p\left( X^{\left( j \right)} = a_{jl} \middle| Y = c_{k} \right) = \theta_{j,l}^{k} = \frac{n_{j,l}^{k}}{\sum_{i = 1}^{N}{I(y_{i} = c_{k})}} = \frac{\sum_{i = 1}^{N}{I(x_{i}^{\left( j \right)} = a_{jl},y_{i} = c_{k})}}{\sum_{i = 1}^{N}{I(y_{i} = c_{k})}}$$

以上，我们完成了离散型朴素贝叶斯算法的推导

半朴素贝叶斯

由于提出条件独立性假设的原因正是联合概率难以求解，所以在弱化假设的时候同样应该避免引入过多的联合概率，这也正是半朴素贝叶斯的基本想法。比较常见的半朴素贝叶斯算法有如下三种：

ODE 算法（One-Dependent Estimator，可译为“独依赖估计”）

（常微分方程：？？？）
顾名思义，在该算法中、各个维度的特征至多依赖一个其它维度的特征。从公式上来说，它在描述条件概率时会多出一个条件：

$$p\left( c_{k} \middle| X = x \right) = p\left( y = c_{k} \right)\prod_{i = 1}^{n}{p\left( X^{\left( j \right)} = x^{\left( j \right)} \middle| Y = c_{k},X^{\left( pa_{j} \right)} = x^{\left( pa_{j} \right)} \right)}$$

这里的$\text{pa}_{j}$代表着维度 j 所“独依赖”的维度

SPODE 算法（Super-Parent ODE，可译为“超父独依赖估计”）

这是 ODE 算法的一个特例。在该算法中，所有维度的特征都独依赖于同一个维度的特征，这个被共同依赖的特征就叫“超父（Super-Parent）”。若它的维度是第 pa 维，知：

$$p\left( c_{k} \middle| X = x \right) = p\left( y = c_{k} \right)\prod_{i = 1}^{n}{p\left( X^{\left( j \right)} = x^{\left( j \right)} \middle| Y = c_{k},X^{\left( \text{pa} \right)} = x^{\left( \text{pa} \right)} \right)}$$

一般而言，会选择通过交叉验证来选择超父

AODE 算法（Averaged One-Dependent Estimator，可译为“集成独依赖估计”）

这种算法背后有提升方法的思想。AODE 算法会利用 SPODE 算法并尝试把许多个训练后的、有足够的训练数据量支撑的SPODE模型集成在一起来构建最终的模型。一般来说，AODE 会以所有维度的特征作为超父训练 n 个 SPODE 模型、然后线性组合出最终的模型

贝叶斯网

贝叶斯网又称“信念网（Belief Network）”，比起朴素贝叶斯来说、它背后还蕴含了图论的思想。贝叶斯网有许多奇妙的性质，详细的讨论不可避免地要使用到图论的术语，这里仅拟对其做一个直观的介绍。 贝叶斯网既然带了“网”字，它的结构自然可以直观地想成是一张网络，其中：

• 网络的节点就是单一样本的各个维度上的随机变量$X^{(1)},...,X^{(n)}$
• 连接节点的边就是节点之间的依赖关系

需要注意的是，贝叶斯网一般要求这些边是“有方向的”、同时整张网络中不能出现“环”。无向的贝叶斯网通常是由有向贝叶斯网无向化得到的，此时它被称为 moral graph（除了把所有有向边改成无向边以外，moral graph 还需要将有向网络中不相互独立的随机变量之间连上一条无向边，细节不表），基于它能够非常直观、迅速地看出变量间的条件独立性

显然，有了代表各个维度随机变量的节点和代表这些节点之间的依赖关系的边之后，各个随机变量之间的条件依赖关系都可以通过这张网络表示出来。类似的东西在条件随机场中也有用到，可以说是一个适用范围非常宽泛的思想

贝叶斯网的学习在网络结构已经确定的情况下相对简单，其思想和朴素贝叶斯相去无多：只需要对训练集相应的条件进行“计数”即可，所以贝叶斯网的学习任务主要归结于如何找到最恰当的网络结构。常见的做法是定义一个用来打分的函数并基于该函数通过某种搜索手段来决定结构，但正如同很多最优化算法一样、在所有可能的结构空间中搜索最优结构是一个 NP 问题、无法在合理的时间内求解，所以一般会使用替代的方法求近似最优解。常见的方法有两种，一种是贪心法、比如：先定下一个初始的网络结构并从该结构出发，每次增添一条边、删去一条边或调整一条边的方向，期望通过这些手段能够使评分函数的值变大；另一种是直接限定假设空间、比如假设要求的贝叶斯网一定是一个树形的结构

相比起学习方法来说，贝叶斯网的决策方法相对来说显得比较不平凡。虽说最理想的情况是直接根据贝叶斯网的结构所决定的联合概率密度来计算后验概率，但是这样的计算被证明了是 NP 问题 [Cooper, 1990]。换句话说，只要贝叶斯网稍微复杂一点，这种精确的计算就无法在合理的时间内做完。所以我们同样要借助近似法求解，一种常见的做法是吉布斯采样（Gibbs Sampling），它的定义涉及到马尔科夫链相关的（我还没有学的）知识，这里就不详细展开了