贝叶斯分类器
1. 贝叶斯决策论
贝叶斯决策论（Bayesian decision theory）是概率框架下实施决策的基本方法。对于分类任务，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的标记。
假设有\(N\)中可能的类别标记，即\(Y = \{c_1, c_2, \cdots, c_N\}\)，\(\lambda_{ij}\)是将一个真实标记为\(c_j\)的样本误分类为\(c_i\)所产生的损失。基于后验概率\(P(c_i|\pmb{x})\)可得到样本\(\pmb{x}\)分类为\(c_i\)的期望损失，即在样本\(\pmb{x}\)上的“条件风险”（conditional risk）： \[R(c_i|\pmb{x}) = \sum_{j=1}^N \lambda_{ij} P(c_j|\pmb{x})\] 需要寻找一种判定准则最小化总体风险： \[R(h) = E_x[R(h(\pmb{x})|\pmb{x})]\] 对于每个样本\(\pmb{x}\)，若\(h\)能最小化条件风险\(R(h(\pmb{x})|\pmb{x})\)，则总体风险\(R(h)\)也将被最小化。由此产生贝叶斯准则：为最小化总体风险，只需在每个样本上选择能使条件风险\(R(c|\pmb{x})\)最小的类别标记，即 \[h^*(\pmb{x}) = \arg \min_{c \in Y} R(c|\pmb{x})\] \(h^*\)称为贝叶斯最优分类器（Bayes optimal classifier），与之对应的总体风险\(R(h^*)\)称为贝叶斯风险（Bayes risk），\(1-R(h^*)\)则是通过机器学习所能产生的模型精度的理论上限。
若目标是最小化分类错误率，则误差损失\(\lambda_{ij}\)可写为： \[\lambda_{ij} = \begin{cases} 0, \quad if \quad i = j \\ 1, \quad otherwise \end{cases} \] 此时条件风险： \[R(c|\pmb{x}) = 1 - P(c|\pmb{x})\] 最小化分类错误率的贝叶斯最优分类器为： \[h^*(\pmb{x}) = \arg \max_{c \in Y} P(c|\pmb{x})\] 对于每个样本\(\pmb{x}\)，选择能使后验概率\(P(c|\pmb{x})\)最大的类别标记。
对于贝叶斯分类这种生成式模型，需要考虑 \[P(c|\pmb{x}) = \frac{P(\pmb{x}, c)}{P(\pmb{x})}\] 基于贝叶斯定理，有 \[P(c|\pmb{x}) = \frac{P(c) P(\pmb{x}|c)}{P(\pmb{x})}\] \(P(c)\)是类“先验”概率，表达了样本空间中各类样本所占的比例，根据大数定律，当训练集中包含充足的独立同分布样本时，\(P(c)\)可通过各类样本出现的频率来进行估计。\(P(\pmb{x}|c)\)是样本\(\pmb{x}\)相对于类标记\(c\)的类条件概率（class-conditional probability），或称为“似然”。由于类条件概率\(P(\pmb{x}|c)\)涉及关于\(\pmb{x}\)所有属性的联合概率，直接根据样本出现频率来估计非常困难，因为很多样本取值在训练集中根本没有出现，直接使用频率显然不可行。\(P(\pmb{x})\)是用于归一化的“证据”因子，对于给定的样本\(\pmb{x}\)，证据因子\(p(\pmb{x})\)与类标记无关。
2. 贝叶斯分类器
2.1. 朴素贝叶斯分类器
基于贝叶斯公式估计后验概率\(P(c|\pmb{x})\)的主要困难在于：类条件概率\(P(\pmb{x}|c)\)是所有属性上的联合概率，难以从有限的训练样本直接估计而得。
朴素贝叶斯采用了“属性条件独立性假设”：对已知类别，假设所有属性相互独立，即每个属性独立地对分类结果产生影响。
基于条件独立性假设，有 \[P(c|\pmb{x}) = \frac{P(c) P(\pmb{x}|c)}{P(\pmb{x})} = \frac{c}{\pmb{x}} \prod_{i=1}^d P(x_i|c)\] 其中\(d\)为属性数目，\(x_i\)为\(\pmb{x}\)在第\(i\)个属性上的取值。
由于对所有类别来说\(p(\pmb{x})\)相同，因此贝叶斯判定准则为
\[h_{nb}(\pmb{x}) = \arg \max_{c \in Y} P(c) \prod_{i=1}^d P(x_i|c)\] 这也是朴素贝叶斯分类器的表达式。
朴素贝叶斯分类器的训练过程就是基于训练集\(D\)来估计类先验概率\(P(c)\)，并为每个属性估计条件概率\(P(x_i|c)\)。
令\(D_c\)表示训练集\(D\)中第\(c\)类样本组成的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率： \[P(c) = \frac{|D_c|}{|D|}\] 对于离散属性，令\(D_{c,x_i}\)表示\(D_c\)在第\(i\)个属性上取值为\(x_i\)的样本组成的集合： \[P(x_i|c) = \frac{D_{c,x_i}}{D_c}\] 对于连续属性可考虑概率密度函数，假定\(p(x_i|c) \sim N(\mu_{c,i},\sigma_{c,i}^2)\)，其中\(\mu_{c,i}\)和\(\sigma_{c,i}^2\)分别为第\(c\)类样本在第\(i\)个属性上取值的均值和方差： \[P(x_i|c) = \frac{1}{\sqrt{2\pi} \sigma_{c,i}} \exp{(- \frac{(x_i - \mu_{c,i})^2}{2 \sigma_{c,i}^2})}\] 拉普拉斯平滑：避免因训练集样本不充分而导致概率估计值为0。避免\(P(c|\pmb{x}) \propto P(c) \prod_{i=1}^d P(x_i|c)\)中，\(P(c)\)或\(P(x_i|c)\)为0，进行拉普拉斯平滑： \[\hat{P}(c) = \frac{|D_c| + 1}{|D|+N} \qquad \hat{P}(x_i|c) = \frac{|D_{c,x_i}|+1}{|D_c|+N_i}\] 拉普拉斯平滑避免了因训练集样本不充分而导致概率估值为0的问题，并且在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可以忽略，使得估值渐渐趋向于实际概率值。
现实任务中朴素贝叶斯多种使用方式：
- 查表：若任务对预测速度要求较高，对于给定训练集，将朴素贝叶斯分类器涉及的所有概率估值事先计算并存储，进行预测时只需查表进行判别；
- 懒惰学习：若数据更替频繁，采用懒惰学习的方式，心不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；
- 增量学习：若数据不断增加，则在现有估值的基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正，实现增量式学习。
示例： 
首先估计类别先验概率\(P(c)\)： \[\begin{equation}
P(好瓜 = 是) = \frac{8}{17} \approx 0.471 \nonumber \\
P(好瓜 = 否) = \frac{9}{17} \approx 0.529 \nonumber
\end{equation}\] 
2.2. 半朴素贝叶斯分类器
为了降低贝叶斯公式中估计后验概率\(P(c|\pmb{x})\)的困难，朴素贝叶斯分类器采用属性条件独立性假设，但在现实任务中这个假设往往很难成立。于是，尝试对属性条件独立性假设进行一定程度的放松，由此产生“半朴素贝叶斯分类器”。
半朴素贝叶斯分类器的基本想法：适当考虑一部分属性间的相互依赖信息，既不需要进行完全联合概率计算，也不至于彻底忽略比较强的属性依赖关系。
独依赖估计（One-Dependent Estimator，ODE）是半朴素贝叶斯分类器最常用的一种策略，独依赖是假设每个属性在类别之外最多只依赖一个其他属性，即 \[P(c|\pmb{x}) \propto P(c) \prod_{i=1}^d P(x_i|c,pa_i)\] 其中\(pa_i\)为属性\(x_i\)所依赖的属性，称为\(x_i\)的父属性。对每个属性\(x_i\)，若其父属性\(pa_i\)已知，则可以通过频率统计的方法估计概率值\(P(x_i|c,pa_i)\)，关键在于如何确定每个属性的父属性，不同做法差生不同的独依赖分类器：
- SPODE（Super-Parent ODE）：假设所有属性都依赖于同一属性，称为“超父”，然后通过交叉验证等模型选择方法来确定超父属性。
- TAN（Tree Augmented naive Bayes）：在最大带权生成树算法的基础上，通过以下步骤将属性依赖关系约简如图7.1（c）所示的树形结构：
- 计算任意两个属性之间的条件互信息\(I(x_i,x_j|y) = \sum_{x_i,x_j;c \in Y} P(x_i,x_j|c) \log \frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}\)；
- 以属性为节点构建完全图，任意两个节点之间边的权重设为\(I(x_i,x_j|y)\)；
- 构建此完全图的最大带权生成树，挑选根变量，将边置为有向；
- 加入类别节点\(y\)，增加从\(y\)到每个属性的有向边。
- AODE（Averaged One-Dependent Estimator）：一种基于集成学习机制、更为强大的独依赖分类器，AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果，即\(P(c|\pmb{x}) \propto \sum_{i=1;|D_{x_i}| \geq m'} P(c,x_i) \prod_{j=1}^d P(x_j|c,x_i)\)，其中\(D_{x_i}\)是在第\(i\)个属性上取值为\(x_i\)的样本集合，\(m'\)为阈值常数。AODE需要估计\(P(c,x_i)\)和\(P(x_j|c,x_i)\)，有\(\hat{P}(c,x_i) = \frac{|D_{c,x_i}|+1}{|D|+N \times N_i}\)，\(\hat{P}(x_j|c,x_i) = \frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}\)，其中\(N\)是\(D\)中可能的类别数，\(N_i\)是第\(i\)个属性可能的取值数，\(D_{c,x_i}\)是类别为\(c\)且在第\(i\)个属性上取值为\(x_i\)的样本集合，\(D_{c,x_i,x_j}\)是类别为\(c\)且在第\(i\)和第\(j\)个属性上取值分别为\(x_i\)和\(x_j\)的样本集合。
AODE无需模型选择，既能通过预算节省预测时间，也能采取懒惰学习方法在预测时再进行计数，并且易于实现增量学习。
如果将依赖属性\(pa_i\)替换为包含\(k\)个属性的集合\(\pmb{pa}_i\)，准确估计概率\(P(x_i|y,\pmb{pa}_i)\)所需的训练样本数量将以指数级增加。
2.3. 正态分布的贝叶斯分类器
正态分布的贝叶斯估计是指贝叶斯公式中的类别条件概率\(P(\pmb{x}|c)\)服从正态分布，其中正态分布的概率密度\(N(\mu, \sigma^2)\)： \[p(x) = \frac{1}{\sqrt{2 \pi} \sigma} \exp{(- \frac{(x-\mu)^2}{2 \sigma^2})}\] 
多维正态分布的概率密度\(N(\mu, \Sigma)\)： \[\begin{equation}
p(x) = \frac{1}{(2 \pi)^{d/2} |\Sigma|^{1/2}} \exp{[-\frac{1}{2} (\pmb{x} - \pmb{\mu})^T \Sigma^{-1} (\pmb{x} - \pmb{\mu})]} \nonumber \\
\pmb{\mu} = E[\pmb{x}] = \int \pmb{x} p(\pmb{x}) d \pmb{x} \nonumber \\
\Sigma = E[(\pmb{x} - \pmb{\mu})(\pmb{x} - \pmb{\mu})^T] = \int (\pmb{x} - \pmb{\mu})(\pmb{x} - \pmb{\mu})^T p(\pmb{x}) d \pmb{x}
\end{equation}\] 其中每个维度上都是正态分布：\(\mu_i = E[x_i], \quad \sigma_{ij} = E[(x_i - \mu_i)(x_j-\mu_j)]\)。
在贝叶斯学习过程中，为了便于计算，将结果取对数： \[\begin{align}
g_i(x) &= \ln (p(\pmb{x}|\omega_i)p(\omega_i)) = \ln{p(\pmb{x}|\omega_i)} + \ln{p(\omega_i)} \nonumber \\
&= \frac{1}{2} (\pmb{x} - \pmb{\mu}_i)^T \Sigma_i^{-1} (\pmb{x} - \pmb{\mu}_i) - \frac{d}{2} \ln{2 \pi} - \frac{1}{2} \ln{|\Sigma_i|} + \ln{p(\omega_i)} \nonumber
\end{align}\] 决策函数为\(g_{ij} = g_i(\pmb{x}) - g_j(\pmb{x})\)，其中\(g_{ij} = 0\)为决策界，如果\(g_{ij}(\pmb{x}) \geq 0\)则归为\(i\)类，否则为\(j\)类。
根据不同的高斯参数讨论：
（1）\(\Sigma_i = \sigma^2 I\) \[\begin{align} g_i(x) &= \frac{1}{2} (\pmb{x} - \pmb{\mu})^T \Sigma_i^{-1} (\pmb{x} - \pmb{\mu}) + \ln{p(\omega_i)} + c_i \nonumber \\ &= - \frac{||\pmb{x} - \pmb{\mu}_i||^2}{2 \sigma^2} + \ln{p(\omega_i)} \nonumber \\ &= - \frac{1}{2 \sigma^2} [\pmb{x}^T \pmb{x} - 2 \pmb{\mu}_i^T \pmb{x} + \pmb{\mu}_i^T \pmb{\mu}_i] + \ln{p(\omega_i)} \nonumber \end{align}\]
由此可得： \[g_i(\pmb{x}) = \pmb{w}_i^T \pmb{x} + \omega_{i0}, \quad \pmb{w}_i = \frac{1}{\sigma^2} \pmb{\mu}_i, \quad \omega_{i0} = - \frac{1}{2 \sigma^2} \pmb{\mu}_i^T \pmb{\mu}_i + \ln{p(\omega_i)}\]
此时，决策面为\(g_i(\pmb{x}) - g_j(\pmb{x}) = 0\)，化简为\(\pmb{w}^T (\pmb{x} - \pmb{x}_0) = 0\)，其中 \[\pmb{w} = \mu_i - \mu_j, \quad \pmb{x}_0 = \frac{1}{2} (\pmb{\mu}_i + \pmb{\mu}_j) - \frac{\sigma^2}{||\pmb{\mu}_i - \pmb{\mu}_j||^2} \ln{\frac{p(\omega_i)}{p(\omega_j)}} (\pmb{\mu}_i - \pmb{\mu}_j)\]
特殊情况：当各个类别的先验概率相等时，退化为最小距离分类器，其中 \[\pmb{w} = \pmb{\mu}_i - \pmb{\mu}_j, \quad \pmb{x}_0 = \frac{1}{2} (\pmb{\mu}_i + \pmb{\mu}_j)\]
（2）\(\Sigma_i = \Sigma\) \[ g_i(x) = \frac{1}{2} (\pmb{x} - \pmb{\mu})^T \Sigma_i^{-1} (\pmb{x} - \pmb{\mu}) + \ln{p(\omega_i)} \] 上式分解之后，\(\pmb{x}^T \Sigma^{-1} \pmb{x}\)各类都相等，可忽略： \[g_i(\pmb{x}) = \pmb{w}_i^T \pmb{x} + \omega_{i0}, \quad \pmb{w}_i = \Sigma^{-1} \pmb{\mu}_i, \quad \omega_{i0} = - \frac{1}{2} \pmb{\mu}_i^T \Sigma^{-1} \pmb{\mu}_i + \ln{p(\omega_i)}\] 此时，决策面为\(g_i(\pmb{x}) - g_j(\pmb{x}) = 0\)，化简为\(\pmb{w}^T (\pmb{x} - \pmb{x}_0) = 0\)，其中 \[\pmb{w} = \Sigma^{-1} (\pmb{\mu}_i - \pmb{\mu}_j), \quad \pmb{x}_0 = \frac{1}{2} (\pmb{\mu}_i + \pmb{\mu}_j) - \frac{\ln{[p(\omega_i)/ p(\omega_j)]}}{(\pmb{\mu}_i - \pmb{\mu}_j)^T \Sigma^{-1} (\pmb{\mu}_i - \pmb{\mu}_j)} (\pmb{\mu}_i - \pmb{\mu}_j)\]
特殊情况：当各类别先验概率相等时 \[\pmb{w} = \Sigma^{-1}(\pmb{\mu}_i - \pmb{\mu}_j), \quad \pmb{x}_0 = \frac{1}{2}(\pmb{\mu}_i + \pmb{\mu}_j)\]
（3）\(\Sigma_i = arbitrary\) \[\begin{align} g_i(\pmb{x}) &= \pmb{x}^T W_i \pmb{x} + \pmb{w}_i^T \pmb{x} + \omega_{i0} \nonumber \\ W_i &= - \frac{1}{2} \Sigma_i^{-1} \nonumber \\ \pmb{w}_i &= \Sigma_i^{-1} \pmb{\mu}_i \nonumber \\ \omega_{i0} &= - \frac{1}{2} \pmb{\mu}_i^T \Sigma_i^{-1} \pmb{\mu}_i - \frac{1}{2} \ln{|\Sigma_i|} + \ln{p(\omega_i)} \nonumber \end{align}\]
决策界：\(g_i(\pmb{x}) - g_j(\pmb{x}) = 0\)，情况比较复杂，可能为非线性。
