贝叶斯分类器

TODO

贝叶斯网、EM 算法

贝叶斯决策论¶

在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记，即选择分类器，使误判带来的损失最小

Info

先验概率：在观察到任何新数据或证据之前，基于已有知识、经验或历史数据，对一个事件或假设发生的初始概率估计。它反映了“事前”信念，不依赖于当前实验数据。通常记为 \(P(H)\)，其中 \(H\) 代表一个假设或事件

后验概率：在观察到新证据或数据之后，对一个事件或假设发生的更新概率。它是先验概率结合新证据计算得出的结果，体现了“事后”信念。记为：\(P(H | E)\)，计算依赖贝叶斯定理：

\[ P(H | E) = \frac{P(E | H) \cdot P(H)}{P(E)} \]

注：其中 \(P(H)\) 为先验概率；\(P(E | H)\) 为类条件概率或似然；\(P(E)\) 为归一化的证据因子，与类标记无关，仅为了让等式左边具有概率含义

联合概率：是两个或多个事件同时发生的概率。它描述了事件的共现关系，不涉及条件依赖。记作 \(P(A, B)\)

\[ P(A, B) = P(A) \cdot P(B | A) = P(B) \cdot P(A | B) \]

贝叶斯定理：可以将上述三者联合起来，即用联合概率和边际概率更新先验为后验

\[ P(H | E) = \frac{P(H, E)}{P(E)} \]

基本原理¶

条件风险¶

\[ R(c_i | x) = \sum_{j = 1}^{N}\lambda_{ij}P(c_j | x) \]

表示将样本 \(x\) 强行归类为 \(c_i\) 所产生的期望损失

其中，\(\lambda_{ij}\) 表示将 \(c_i\) 归类为 \(c_j\) 的损失值；\(P(c_j | x)\) 表示 \(x\) 的真实分类是 \(c_j\) 的概率

总体风险¶

\[ R(h) = \mathbb{E_x}[R(h(x) | x)] \]

表示判定准则 \(h\) 对于样本集合 \(\mathbf{X} (x \in \mathbf{X})\) 中每个样本的条件风险的期望

贝叶斯判定准则¶

寻找判定准则 \(h\) 以总体风险，即相当于在每个样本上选择能使条件风险最小的类别标记

\[ h^{*}(x) = \mathop{\arg\min}_{c \in \mathbf{Y}} \; R(c | x) \]

注：\(\mathbf{Y}\) 为所有类别标记的集合

\(h^{*}\) 为贝叶斯最优分类器，其对应的总体风险 \(R(h^{*})\) 为贝叶斯风险，\(1 - R(h^{*})\) 表示分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限

若目标为最小化分类错误率，则误判损失 \(\lambda_{ij}\) 可写为：\(\lambda_{ij} = 0 \; \mathop{if} \; i = j \; \mathop{otherwise} \; 1\)，此时的条件风险可表示为：

\[ R(c | x) = 1 - P(c | x) \]

因此，最小化分类错误率的贝叶斯最优分类器为：

\[ h^*(x) = \mathop{\arg\max}_{c \in \mathbf{Y}} \; P(c | x) \]

即对每个样本 \(x\) 都选择使其后验概率最大的类别标记

贝叶斯决策论的最终结果是基于后验概率寻找最优的分类器以最小化总体风险/条件风险 (如选择后验概率最大的一项)，而后验概率在实际应用中并不容易得到，因此它可以视为从概率框架的角度对机器学习作出的诠释：机器学习所要实现的是基于有限的训练样本集得到能尽可能准确地估计后验概率的模型

训练得到的模型可分为以下两种类型：

判别式模型：

给定 \(x\)，直接建模 \(P(c | x)\)

包括决策树、BP 神经网路、支持向量机等
生成式模型：

给定 \(x\)，先对联合概率分布 \(P(x, c)\) 建模，再通过贝叶斯定理获得 \(P(c | x)\)

包括：朴素贝叶斯、隐马尔可夫模型等

根据贝叶斯定理，有：

\[ P(c | x) = \frac{P(x, c)}{P(x)} = \frac{P(c)P(x | c)}{P(x)} \]

其中：\(P(c)\) 是类先验概率；\(P(x | c)\) 是样本 x 相对于类标记 c 的类条件概率/似然；\(P(x)\) 是用于归一化的证据因子，与标记无关，因此主要关注基于训练数据估计先验概率 \(P(c)\) 和似然 \(P(x | c)\)

极大似然估计 MLE¶

估计类条件概率的一种方法，假定类别 c 的条件概率 \(P(x | c)\) 具有确定的形式并且被参数向量 \(\theta_c\) 唯一确定 (如：符合正态分布)，因此，任务转化为通过训练集 D 估计参数 \(\theta_c\)，从而可以将 \(P(x | c)\) 记作 \(P(x | \theta_c)\)

令 \(D_c\) 表示训练集 D 中第 c 类样本组成的集合，假设这些样本是独立同分布的，则参数 \(\theta_c\) 对数据集 \(D_c\) 的似然是：

\[ P(D_c | \theta_c) = \prod_{x \in D_c} P(x | \theta_c) \]

对 \(\theta_c\) 进行极大似然估计，就是寻找参数值 \(\hat{\theta}_c\) 以最大化似然值 \(P(D_c | \theta_c)\)

由于连乘操作不易实现求导求最大化的过程，所以通常使用对数似然：

\[ LL(\theta_c) = \log{P(D_c | \theta_c)} = \sum_{x \in D_c} \log{P(x | \theta_c)} \]

\(\theta_c\) 的极大似然估计可表示为：

\[ \hat{\theta}_c = \mathop{\arg\max}_{\theta_c} \; LL(\theta_c) \]

若假设 \(P(x | c)\) 符合正态分布(高维)，则对正态分布的均值 \(\mu\) 和方差 \(\sigma^2\) 的极大似然估计为：

\[ \begin{align} \hat{\mu}_c &= \frac{1}{|D_c|}\sum_{x \in D_c} x \\ \hat{\sigma}^2 &= \frac{1}{|D_c|}\sum_{x \in D_c} (x - \hat{\mu}_c) (x - \hat{\mu}_c)^T \end{align} \]

Info

\[ \begin{align} P(x) &= \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x - \mu)^2}{2\sigma^2}} \\ LL(\mu, \sigma^2) &= \sum_{x \in D_c}(-\frac{1}{2}\log{2 \pi \sigma^2} - \frac{(x - \mu)^2}{2 \sigma^2}) \\ \frac{\partial{LL}}{\partial{\mu}} &= \sum_{x \in D_c}\frac{x - \mu}{\sigma^2} = 0 \rightarrow \sum_{x \in D_c} x = \sum_{x \in D_c} \mu _c \\ \frac{\partial{LL}}{\partial{\sigma^2}} &= \sum_{x \in D_c} -\frac{1}{2 \sigma^2} + \frac{(x - \mu)^2}{2 \sigma^4} = 0 \rightarrow \sum_{x \in D_c} (x - \mu)^2 = \sum_{x \in D_c} \sigma^2 \\ \hat{\mu}_c &= \frac{1}{|D_c|}\sum_{x \in D_c} x \\ \hat{\sigma}^2 &= \frac{1}{|D_c|}\sum_{x \in D_c} (x - \hat{\mu}_c)^2 \end{align} \]

朴素贝叶斯分类器¶

属性条件独立性假设：对已知类别，假设所有属性相互独立

由此可得：

\[ P(c | x) = \frac{P(c)P(x | c)}{P(x)} = \frac{P(c)}{P(x)}\prod_{i = 1}^{d}P(x_i | c) \]

\(d\) 为属性数目，\(x_i\) 为 x 在第 i 个属性上的取值

根据贝叶斯判定准则：

\[ h^*(x) = \mathop{\arg\max}_{c \in y} \; P(c | x) = \mathop{\arg\max}_{c \in y} \; \frac{P(c)}{P(x)}\prod_{i = 1}^{d}P(x_i | c) \]

对于所有类别来说，分母 \(P(x)\) 都是相同的，所以在比较大小时可以忽略：

\[ h_{nb}(x) = \mathop{\arg\max}_{c \in y} \; P(c) \prod_{i = 1}^{d} P(x_i | c) \]

估计 \(P(c)\):

\[ P(c) = \frac{| D_c |}{| D |} \]

估计 \(P(x_i | c)\):

离散属性：

\[ P(x_i | c) = \frac{|D_{c,x_i}|}{|D_c|} \]

连续属性可使用概率密度函数，如假定该属性符合正态分布，则可计算均值和方差，获得正态分布密度函数，从而获得该属性的概率估计

拉普拉斯修正¶

在计算 \(P(x_i, c)\) 时，如果遇到某个属性值未出现，可能导致最终的连乘式为0，该样本其他属性的信息被抹去，这种情况下，在估计概率值时需要进行平滑处理，常用“拉普拉斯修正”

\[ \hat{P}(c) = \frac{|D_c| + 1}{|D| + N} \]

\[ \hat{P}(x_i | c) = \frac{|D_{c,x_i}| + 1}{|D_c| + N_i} \]

其中 \(N\) 为训练集 D 中所有可能的类别数，\(N_i\) 表示第 i 个属性的可能取值数

半朴素贝叶斯分类器¶

适当考虑一部分属性间的相互依赖关系，从而既不需要进行完全联合概率计算，又不至于忽略了比较强的属性依赖关系

独依赖估计 ODE¶

假设每个属性在类别之外最多依赖于一个其他属性，即：

\[ P(c | x) \propto P(c) \prod_{i = 1}^{d}P(x_i | c, pa_i) \]

其中 pa_i 为属性 \(x_i\) 所依赖的属性，称为 \(x_i\) 的父属性

超父独依赖估计 SPODE¶

假设所有属性都依赖于同一个“超父”属性

\[ \begin{align} P(c | x) = \frac{P(x, c)}{P(x)} &= \frac{P(c, x_i)P(x_1, ..., x_{i - 1}, x_{i + 1}, ..., x_d | c, x_i)}{P(x)} \\ &\propto P(c, x_i)P(x_1, ..., x_{i - 1}, x_{i + 1}, ..., x_d | c, x_i) \\ &= P(c, x_i)\prod_{j = 1}^{d}(x_j | c, x_i) \end{align} \]

Info

\[ P(x_i | c, x_i) = 1 \]

TAN¶

AODE¶

尝试将每一个属性作为超父来构建 SPODE，选择其中具有足够训练数据支撑的 SPODE 作为最终结果