贝叶斯分类器

第7章 贝叶斯分类器

• Page147: 贝叶斯风险(Bayes risk)

  贝叶斯最优分类器对应的条件风险

• Page147: 贝叶斯最优分类器(Bayes optimal classifier)

  为最小化总体风险，只需在每个样本上选择那个能使条件风险最小的类别标记，此时判定准侧称为贝叶斯最优分类器。

• Page147: 风险(risk)

  决策论中将“期望损失”称为风险。

• Page147: 条件风险(conditional risk)

  基于后验概率$P(c_{i}|x)$可获得将样本x分类为ci所产生的期望损失，即在样本x上的条件风险。

• Page148: 贝叶斯定理

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

  其中， P(c)是类“先验”(prior)概率；P(x|c)是样本x相对于类标记c的类条件概率(class-conditional probability)，或称为“似然”(likelihood)；P(x)是用于归一化的“证据”(evidence)因子。估计P(c|x)的问题转化为如何基于训练数据D来估计先验P(c)和似然P(x|c)。

• Page148: 判别式模型(325)（discriminative models）

  给定x,可通过直接建模P(c|x)来预测c，这样得到的是判别式模型。

• Page148: 生成式模型(295,325)(generative models)

  先对联合概率分布P(x,c)建模，然后再由此获得P(c|x)，这样得到的是生成式模型。

• Page148: 似然(likelihood)

  见贝叶斯定理。

• Page148: 先验(Prior)

  见贝叶斯定理

• Page148: 证据（evidence）

  见贝叶斯定理

• Page149: 极大似然估计(maximum likelihood estimation， MLE)

  令$D_{c}$表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的，则参数$\theta_{c}$对于数据集$D_{c}$的似然是：

  $P(D_{c}|\theta_{c}) = \prod_{x \in D_{c}} P(x|\theta_{c})$

• Page150: 朴素贝叶斯分类器(naive bayes classifier)

  基于贝叶斯公式来估计后验概率P(c|x)的主要困难在于：类条件概率P(x|c)是所有属性上的联合概率，难以从有限的训练样本直接估计而得，为避开这个障碍，朴素贝叶斯分类器采用了“属性条件独立性假设”：

  $P(c|x) = \frac{P(c)P(x|c)}{P(x)}=\frac{P(c)}{P(x)} * \prod_{i=1}^{d} P(x_{i}|c)$

  即P(x|c)等于在c的条件下，所有属性的概率的乘积。

• Page150: 条件独立性假设(305)

  对已知类别，假设所有属性相互独立，换言之，假设每个属性独立的对分类结果发生影响。

• Page153: 拉普拉斯修正(Laplacian correction)

  为了避免其他属性携带的信息被训练集中未出现的属性值抹去，在估计概率值时通常要进行“平滑”，常用“拉普拉斯修正”，具体来说，另N表示训练集D中可能的类别数，$N_{i}$表示第i个属性可能的取值书，则类先验概率

  $\hat{P}(c)=\frac{|D_{c}|+1}{|D|+N}$

  条件概率：

  $\widehat{P}(x_{i}|c)=\frac{D_{c,x_{i}}+1}{D_{c}+N_{i}}$

• Page154: 半监督贝叶斯分类器(semi-naive Bayes classifiers)

  半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。

• Page154: 独依赖估计(One-Dependent Estimator)

  独依赖估计是半朴素贝叶斯分类器最常用的一种策略，假设每个属性在类别之外最多仅依赖于一个其他属性，即

  $P(c|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})$，于是问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。

• Page154: 懒惰学习(225,240)（lazy learning）

  若任务数据更替频繁，则可采用“懒惰学习”方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。

• Page155: 超父(super-parent)

  假设所有属性都依赖于同一个属性，称为超父，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了超父独依赖估计(Super-Parent ODE，SPODE).

• Page156: 贝叶斯网(319,339)（Bayesian network）

  借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布。具体来说，一个贝叶斯网有结构G和参数$\theta$两部分构成，即$B=<G,\theta>$。网络结构G是一个有向无环图，每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来；参数$\theta$定量描述这种依赖关系，假设属性$x_{i}$在G中的父结点集为$\pi_{i}$，则$\theta$包含了每个属性的条件概率表$\theta_{x_{i}|\pi_{i}}=P_{B}(x_{i}|\pi_{i})$。

• Page156: 概率图模型(319)

  是一种用图来表达变量相关关系的概率模型，它以图为表示工具，最常见的是用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即“变量关系图”。根据边的性质不同，概率图模型可大致分为两类：第一类是用有向无环图表示变量间的以来关系，称为有向图模型或贝叶斯网；第二类是使用无向图表示变量间的相关关系，称为无向图模型或马尔科夫网。

• Page156: 信念网(belief network)

  即贝叶斯网。

• Page158: V型结构（V-structure）

graph TD;
  A[x1]-->B[x4];
  C[x2]-->B[x4];

也称冲撞结构，给定父节点$$x_{4}$$的取值，则$$x_{1}$$与$$x_{2}$$不独立，若x_{4}未知，则V型结构下$$x_{1}$$与$$x\_{2}$$却是相互独立的，这样的独立性称为边际独立性。

• Page158: 边际独立性（marginal independence）

  见V型结构。

• Page158: 边际化(328)(marginalization)

  对变量做积分或求和亦称边际化。

• Page158: 道德图（moral graph）

  为了分析又想吐中变量间的条件独立性，可使用“有向分离”，把有向图转为一个无向图：

  • 找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无箱变；

  • 将所有有向边改为无向边。

    由此产生的无向图称为“道德图”，令父结点相连的过程称为“道德化”（moralization）。

• Page158: 端正图

  即道德图。

• Page158: 有向分离（D-seperation）

  见道德图。

• Page159: 最小描述长度（Minimal Description Length）

  常用评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。对贝叶斯网学习而言，模型就是一个贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码，选择综合编码长度（包括描述网络和编码数据）最短的贝叶斯网，这就是最小描述长度。

• Page161: 吉布斯采样(334)

  吉布斯采样先随机产生一个与证据E=e一致的样本$q^{0}$作为初始点，然后每步从当前样本出发产生下一个样本。具体来说，在第t次采样中，算法先假设$q^{t}=q^{t-1}$，然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网B和其他变量的当前取值（即Z=z）计算获得。假定经过T次采样得到的与q一致的样本共有$n_{q}$个，则可近似估算出后验概率

  $P(Q=q|E=e) \backsimeq \frac{n_{q}}{T}$

• Page161: 近似推断(161)

  当网络结点较多，连接稠密时，难以进行精确推断，此时需借助“近似推断”，通过降低精度要求，在有限时间内求得近似解。

• Page161: 精确推断(328,331)

  最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，精确推断是NP难的。

• Page161: 马尔科夫链(Markov chain)

  吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据E=e一致的子空间中进行“随机漫步”，每一步仅依赖于前一步的状态，这是一个马尔可夫链。在一定条件下，无论从什么初始状态开始，马尔可夫链第t步的状态分布在$t\rightarrow\infty$时必收敛于一个平稳分布，对吉布斯采样来说，这个分布恰好是$P(Q|E=e)$。在T很大的时候，吉布斯采样相当于根据$P(Q|E=e)$采样，从而保证了后验概率收敛于$P(Q=q|E=e)$。

• Page161: 平稳分布（stationary distribution）

  见马尔科夫链。

• Page162: EM算法(208,295,335)(Expectation-Maximization Algorithm)

  常用的估计参数隐变量的利器，它是一种迭代式的方法，基本想法是：若参数$\theta$，则可根据训练数据推断出最优隐变量Z的值（E步）；反之，若Z的值已知，则可方便地对参数$\theta$做极大似然估计。

• Page162: 隐变量(319)（latent variable）

  现实应用中往往会遇到不完整的训练样本，存在未观测的变量，未观测变量的学名是隐变量。

• Page163: 边际似然（marginal likehood）

  令X表示已观测变量集，Z表示隐变量集，$\theta$表示模型参数。若欲对$\theta$做极大似然估计，则应最大化对数似然

  $LL(\theta|X,Z)=ln P(X,Z|\theta)$

  然而由于Z是隐变量，上式无法直接秋季，此时我们可以通过对Z计算期望，来最大化已观测的对数“边际似然”

  $LL(\theta|X) = ln P(X|\theta) = ln \sum_Z P(X,Z|\theta)$

• Page163: 坐标下降(408)（coordinate descent）

  非梯度优化方法，在每步迭代中沿着一个坐标方向进行搜索，通过循环使用不同的坐标方向来达到目标函数的局部极小值，不妨假设目标是求解函数$f(x)$的极小值，其中$x=(x_1,x_2,...,x_d)^T \in R^d$是一个d维向量。从初始点$x^0$开始，坐标下降法通过迭代地构造序列$x^0,x1,x2,...$来解决问题，$x^(t+1)$的第i个分量$x_i^{t+1}$构造为

  $x_i^(t+1) = argmin_{y \in \mathbb{R}}$

  迭代执行该过程，序列$x^0,x1,x2,...$能收敛到所期望的局部极小点或驻点。若目标函数不光滑，可能陷入非驻点。

• Page164: 贝叶斯分类器（Bayes Classifier）

  通过最大后验概率进行单点估计。

• Page164: 贝叶斯学习（Bayes learning）

  进行分布估计。