贝叶斯分类器笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  本文做一些关于贝叶斯分类器(Bayes Classifiers)的笔记,为了方便,本文所讨论的所有属性都为离散型。

朴素贝叶斯分类器(Naive Bayes Classifier)

  关于贝叶斯法则(Bayes Rule),可以看这篇文章。关于最大似然估计(MLE),可以看这篇文章。本文就不描述这两个概念了。
  本文从朴素贝叶斯分类器开始说起,我们知道基于贝叶斯公式来估计后验概率\(P(c | \boldsymbol{x})\)的难点在于条件概率\(P(c | \boldsymbol{x})\)是所有属性上的联合概率,很难从有限的训练样本中直接估计而得。因此,朴素贝叶斯分类器采用了“属性条件独立性假设”来解决这个问题,它假设所有属性相互独立,于是我们可以得到下面的式子: \[ P(c | \boldsymbol{x})=\frac{P(c) P(\boldsymbol{x} | c)}{P(\boldsymbol{x})}=\frac{P(c)}{P(\boldsymbol{x})} \prod_{i=1}^{d} P\left(x_{i} | c\right) \]   其中\(d\)为属性的个数,\(x_i\)为在第\(i\)个属性上的取值。因为对于所有类别来说\(P(\boldsymbol{x})\)相同,所以朴素贝叶斯分类器的表达式可简化为: \[ h_{n b}(\boldsymbol{x})=\underset{c \in \mathcal{Y}}{\arg \max } P(c) \prod_{i=1}^{d} P\left(x_{i} | c\right) \]   因此朴素贝叶斯分类器的训练过程就是基于训练集\(D\)来估计类先验概率\(P(c)\)和为每个属性估计条件概率\(P(x_i|c)\)
  若有充足的独立同分布样本,类先验概率可以很容易的被估计出: \[ P(c)=\frac{\left|D_{c}\right|}{|D|} \]   条件概率也可被估计出: \[ P\left(x_{i} | c\right)=\frac{\left|D_{c, x_{i}}\right|}{\left|D_{c}\right|} \]   如果是连续属性的话,需要考虑PDF,假定\(p\left(x_{i} | c\right) \sim \mathcal{N}\left(\mu_{c, i}, \sigma_{c, i}^{2}\right)\),则有: \[ p\left(x_{i} | c\right)=\frac{1}{\sqrt{2 \pi} \sigma_{c, i}} \exp \left(-\frac{\left(x_{i}-\mu_{c, i}\right)^{2}}{2 \sigma_{c, i}^{2}}\right) \]

拉普拉斯修正(Laplacian Correction)

  通关观察前面的式子,我们可以发现,它是连乘的,因此只要有一个属性的值没有出现过,即它的条件概率值为0的话,那么无论其他属性的取值如何,分类计算的结果都将为0,这是不太合理的。
  因此为了避免其他属性携带的信息被训练集中未出现的属性值抹去,我们需要对估计概率值进行平滑(smoothing)处理,通常都使用拉普拉斯修正。我们记\(N\)\(D\)中可能的类别数,\(N_i\)表示第\(i\)个属性可能的取值数,则前面的式子可被修正为: \[ \begin{aligned} \hat{P}(c) &=\frac{\left|D_{c}\right|+1}{|D|+N} \\ \hat{P}\left(x_{i} | c\right) &=\frac{\left|D_{c, x_{i}}\right|+1}{\left|D_{c}\right|+N_{i}} \end{aligned} \]   需要注意的是,拉普拉斯修正实际上假设了属性值与类别是均匀分布的,这是在朴素贝叶斯学习过程中额外引入的关于数据的先验。除此之外,随着训练集变大,修正过程所引入的先验概率的影响也会逐渐变得可忽略,使得估值渐趋向于实际概率值。
  在现实任务中朴素贝叶斯分类器有多种使用方式。例如,若任务对预测速度要求较高,则对给定训练集,可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来,这样在进行预测时只需“查表”即可进行判别;若任务数据更替频繁,则可采用“懒惰学习”(lazy learning)方式,先不进行任何训练,待收到预测请求时再根据当前数据集进行概率估值。若数据不断增加,则可在现有估值基础上,仅对新增样本的属性值所涉及的概率估值进行计数修正即可,以此来实现增量学习。

半朴素贝叶斯分类器(Semi-naive Bayes Classifiers)

  与朴素贝叶斯分类器不同,半朴素贝叶斯分类器的会适当考虑一部分属性间的相互依赖信息,从而既不需进行完全联合概率计算,又不至于彻底忽略了比较强的属性依赖关系。“独依赖估计”(One-Dependent Estimator,简称ODE)是半朴素贝叶斯分类器最常用的一种策略,也就是假设每个属性在类别之外最多仅依赖于一个其他属性,即: \[ P(c | \boldsymbol{x}) \propto P(c) \prod_{i=1}^{d} P\left(x_{i} | c, p a_{i}\right) \]   其中\(pa_i\)为属性\(x_i\)所依赖的属性,称为父属性。如何确定每个属性的父属性?不同的做法产生不同的分类器。

SPODE(Super-Parent ODE)

  最简单的做法是假设所有属性都依赖于同一个属性,称为“超父”(super-parent),然后通过交叉验证等模型选择方法来确定超父属性,由此形成了SPODE方法。

TAN(Tree Augmented nave Bayes)

  TAN则是在最大带权生成树(maximum weighted spanning tree)算法的基础上,通过下面四个步骤将属性间依赖关系简化为下图所示的树形结构:

  1. 计算任意两个属性之间的条件互信息。 \[ I\left(x_{i}, x_{j} | y\right)=\sum_{x_{i}, x_{j} ; c \in \mathcal{Y}} P\left(x_{i}, x_{j} | c\right) \log \frac{P\left(x_{i}, x_{j} | c\right)}{P\left(x_{i} | c\right) P\left(x_{j} | c\right)} \]
  2. 以属性为结点构建完全图,任意两个结点之间边的权重设为\(I(x_i,x_j|y)\)
  3. 构建此完全图的最大带权生成树,挑选根变量,将边置为有向。
  4. 加入类别结点\(y\),增加从\(y\)到每个属性的有向边。

  条件互信息\(I(x_i,x_j|y)\)刻画了连个属性在己知类别情况下的相关性,因此,通过最大生成树算法,TAN实际上仅保留了强相关属性之间的依赖性。

AODE(Averaged One-Dependent Estimator)

  AODE基于集成学习机制,是一种更为强大的独依赖分类器,与SPODE通过模型选择确定超父属性不同,AODE尝试将每个属性作为超父来构建SPODE,然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果,即 \[ P(c | \boldsymbol{x}) \propto \sum_{i=1 \atop |D_{x_{i}}| \geqslant m^{\prime}}^{d} P\left(c, x_{i}\right) \prod_{j=1}^{d} P\left(x_{j} | c, x_{i}\right) \]   其中\(D_{x_i}\)是在第\(i\)个属性上取值为\(x_i\)的样本的集合,\(m^{'}\)为阈值常数。
  AODE所需的先验概率和条件概率的估计也需要更加复杂一些: \[ \begin{aligned} \hat{P}\left(c, x_{i}\right) &=\frac{\left|D_{c, x_{i}}\right|+1}{|D|+N_{i}} \\ \hat{P}\left(x_{j} | c, x_{i}\right) &=\frac{\left|D_{c, x_{i}, x_{j}}\right|+1}{\left|D_{c, x_{i}}\right|+N_{j}} \end{aligned} \]   不难看出,与朴素贝叶斯分类器类似,AODE的训练过程其实也是“计数”,即在训练数据集上对符合条件的样本进行计数的过程。与朴素贝叶斯分类器相似,AODE无需模型选择,既能通过预计算节省预测时间,也能采取懒惰学习方式在预测时再进行计数,并且易于实现增量学习。
  如果想进一步提升泛化性能,可以将属性\(pa_i\)替换为包含k个属性的集合\(\mathbf{p} \mathbf{a}_{i}\),从而将ODE拓展为kDE,但是随着\(k\)的增加,准确估计概率\(P\left(x_{i} | y, \mathbf{p a}_{i}\right)\)所需的训练样本数量将以指数级增加。因此,若训练数据非常充分,泛化性能有可能提升,但在有限样本条件下,则又陷入估计高阶联合概率的泥沼。

贝叶斯网(Bayesian Network)

  贝叶斯网借助有向无环图(Directed Acyclic Graph, DAG)来刻画属性之间的依赖关系,并使用条件概率表(Conditional Probability Table,CPT)来描述属性的联合概率分布。
  贝叶斯网\(B=\langle G, \Theta\rangle\)由结构\(G\)和参数\(\Theta\)两部分构成,网络结构\(G\)是一个有向无环图,其每个结点对应于一个属性,若两个属性有直接依赖关系,则它们由一条边连接起来。参数\(\Theta\)定量描述这种依赖关系,假设属性\(x_i\)\(G\)中的父结点集为\(\pi_i\),则\(\Theta\)包含了每个属性的条件概率表 \(\theta_{x_{i} | \pi_{i}}=P_{B}\left(x_{i} | \pi_{i}\right)\)
  下图是西瓜书中一个简单的例子:

  下面我们分结构,学习和推断三块简单的来介绍下贝叶斯网。

结构

  贝叶斯网结构有效地表达了属性间的条件独立性,给定父结点集,假设每个属性与它的非后裔属性独立,即: \[ P_{B}\left(x_{1}, x_{2}, \ldots, x_{d}\right)=\prod_{i=1}^{d} P_{B}\left(x_{i} | \pi_{i}\right)=\prod_{i=1}^{d} \theta_{x_{i} | \pi_{i}} \]   以上图为例,联合概率分布定义为: \[ P\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right)=P\left(x_{1}\right) P\left(x_{2}\right) P\left(x_{3} | x_{1}\right) P\left(x_{4} | x_{1}, x_{2}\right) P\left(x_{5} | x_{2}\right) \]   如下图所示,贝叶斯网中,三个变量之间有三种典型依赖关系:

  这里需要特别说明一下的是V型结构,给定子结点\(x_4\)的取值,\(x_1\)\(x_2\)必不独立, 然而,若\(x_4\)的取值完全未知,它们却又是独立的了: \[ \begin{aligned} P\left(x_{1}, x_{2}\right) &=\sum_{x_{4}} P\left(x_{1}, x_{2}, x_{4}\right) \\ &=\sum_{x_{4}} P\left(x_{4} | x_{1}, x_{2}\right) P\left(x_{1}\right) P\left(x_{2}\right) \\ &=P\left(x_{1}\right) P\left(x_{2}\right) \end{aligned} \]   这样的独立性称为“边际独立性”(marginal independence)。
  我们再深入一点,一个变量取值的确定与否,能对另两个变量间的独立性发生影响。在同父结构中,条件独立性\(x_{3} \perp x_{4} | x_{1}\)成立,但若\(x_1\)的取值未知,则\(x_3\)\(x_4\)就不独立,它们不存在边际独立性。在顺序结构中,\(y \perp z | x\),但\(y\)\(z\)也不具有边际独立性。
  为了分析有向图中变量间的条件独立性,可使用“有向分离”(D-separation),找出有向图中的所有的V型结构,在V型结构的两个父结点之间加一条无向边,将所有有向边改为无向边,由此我们把有向图转变为一个无向图。这样产生的无向图也称为“道德图”(moral graph),令父结点相连的过程称为”道德化”(moralization)。
  基于道德图能直观迅速地找到变量间的条件独立性。假定道德图中有变量\(x,y\)和变量集合\(z=\{z_i\}\),若变量\(x\)\(y\)能在图上被\(z\)分开,即从道德图中将变量集合\(z\)去除后,\(x\)\(y\)分属两个连通分支,则称变量\(x\)\(y\)\(z\)有向分离,即\(x \perp y | z\)成立。
  如下图所对应的道德图,我们可以得到这些条件独立关系:\(x_{3} \perp x_{4}\left|x_{1}, x_{4} \perp x_{5}\right| x_{2}, x_{3} \perp x_{2}\left|x_{1}, x_{3} \perp x_{5}\right| x_{1}, x_3 \perp x_5 | x_2\)

学习

  若网络结构已知,即属性间的依赖关系已知,则贝叶斯网的学习过程只需通过对训练样本“计数”,估计出每个结点的条件概率表即可。但在实际中我们往往并不知晓网络结构,于是,贝叶斯网学习的首要任务就是根据训练数据集来找出结构最“恰当”的贝叶斯网。
  “评分搜索”是求解这一问题的常用办法,我们需要定义一个评分函数(score function)来评估贝叶斯网与训练数据的契合程度,然后基于这个评分函数来寻找结构最优的贝叶斯网,评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好。
  常用评分函数通常基于信息论准则,此类准则将学习问题看作一个数据压缩任务,学习的目标是找到一个能以最短编码长度描述训练数据的模型,此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。对贝叶斯网学习而言,模型就是个贝叶斯网,每个贝叶斯网描述了一个在训练数据上的概率分布,自有一套编码机制能使那些经常出现的样本有更短的编码。根据“最小描述长度”(Minimal Description Length, MDL)准则我们应选择那个综合编码长度(包括描述网络和编码数据)最短的贝叶斯网。
  我们可将评分函数定义为,其中\(f(\theta)\)表示每个参数\(\theta\)所需的字节数,\(|B|\)是贝叶斯网的参数个数: \[ s(B | D)=f(\theta)|B|-L L(B | D) \\ L L(B | D)=\sum_{i=1}^{m} \log P_{B}\left(\boldsymbol{x}_{i}\right) \]   上式的第一项是计算编码贝叶斯网\(B\)所需的字节数,第二项是计算\(B\)所对应的概率分布\(P_B\)多对\(D\)描述得有多好,于是学习任务就转化为一个优化任务,即寻找个贝叶斯网\(B\)使评分函数\(s(B|D)\)最小。
  根据\(f(\theta)\)的不同,常有这几种评分函数:

  • \(f(\theta)=1\),得到AIC(Akaike Information Criterion)评分函数: \[ \operatorname{AIC}(B | D)=|B|-L L(B | D) \]
  • \(f(\theta)=\frac{1}{2}log m\),得到BIC(Bayesian Information Criterion)评分函数: \[ \operatorname{BIC}(B | D)=\frac{\log m}{2}|B|-L L(B | D) \]
  • \(f(\theta)=0\),不计算对网络进行编码的长度,评分函数退化为负对数似然,相应的,学习任务退化为极大似然估计。

  不难发现,若贝叶斯网的网络结构\(G\)固定,则评分函数第一项为常数,此时,最小化\(s(B|D)\)等价于对参数\(\Theta\)的极大似然估计,参数\(\theta_{x_{i} | \pi_{i}}\)能直接在训练数据\(D\)上通过经验估计获得,即: \[ \theta_{x_{i} | \pi_{i}}=\hat{P}_{D}\left(x_{i} | \pi_{i}\right) \]   其中\(\hat{P}_{D}(\cdot)\)\(D\)上的经验分布,因此,为了最小化评分函数,只需对网络结构进行搜索,而候选结构的最优参数可直接在训练集上计算得到。然而,从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题,难以快速求解,通常有两种常用的策略能在有限时间内求得近似解:

  • 贪心法,例如从某个网络结构出发,每次调整一条边(增加、删除或调整方向),直到评分函数值不再降低为止。
  • 通过给网络结构施加约束来削减搜索空间,例如将网络结构限定为树形结构等。

推断

  训练完贝叶斯网后就能用来进行推断(inference),即通过一些属性变量的观测值(已知变量观 测值称为“证据”(evidence))来推测其他属性变量的取值。
  最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率,然而这样的“精确推断”也已被证明是NP难的,也就是说当网络结点较多、连接稠密时,难以进行精确推断,此时需借助“近似推断”, 通过降低精度要求,在有限时间内求得近似解。
  在现实应用中,贝叶斯网的近似推断常使用吉布斯采样(Gibbs Sampling)来完成,这是一种随机采样方法,西瓜书中的算法流程如图所示:

  吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据\(\boldsymbol{E} = \boldsymbol{e}\)一致的子空间中进行“随机漫步”(random walk),每一步仅依赖于前一步的状态,这实际上也是一个马尔可夫链(Markov chain)。在一定条件下,无论从什么初始状态开始,马尔可夫链第\(t\)步的状态分布在\(t \to \infty\)时必收敛于一个平稳分布(stationary distribution),对于吉布斯采样来说,这个分布恰好是\(P(\mathbf{Q} | \mathbf{E}=\mathbf{e})\)。因此,在\(T\)很大时,吉布斯采样相当于根据\(P(\mathbf{Q} | \mathbf{E}=\mathbf{e})\)采样,从而保证了最后的收敛:\(P(\mathbf{Q}=\mathbf{q} | \mathbf{E}=\mathbf{e}) \simeq \frac{n_{q}}{T}\)

  所需要注意的是,由于马尔可夫链通常需很长时间才能趋于平稳分布,因此吉布斯采样算法的收敛速度较慢。此外,若贝叶斯网中存在极端概率0或1,则不能保证马尔可夫链存在平稳分布,此时吉布斯采样会给出错误的估计结果。

西瓜书里周老师关于吉布斯采样说的有点抽象,可以看看这篇文章来加强理解。

EM算法(Expectation-Maximization Algorithm)

  之前我们一直假设训练样本所有属性变量的值都已被观测到,即训练样本是“完整”的,但当遇到“不完整”的训练样本,即出现为观测的“隐变量”(latent variable)时,该如何进行估计呢?
  令\(\boldsymbol{X}\)表示已观测变量集,\(\boldsymbol{Z}\)表示隐变量集,欲对\(\Theta\)做极大似然估计,则应最大化对数似然: \[ L L(\Theta | \mathbf{X}, \mathbf{Z})=\ln P(\mathbf{X}, \mathbf{Z} | \Theta) \]   然而由于\(\boldsymbol{Z}\)是隐变量,上式无法直接求解,此时我们可通过对\(\boldsymbol{Z}\)计算期望,来最大化己观测数据的对数“边际似然”(marginal likelihood): \[ L L(\Theta | \mathbf{X})=\ln P(\mathbf{X} | \Theta)=\ln \sum_{\mathbf{Z}} P(\mathbf{X}, \mathbf{Z} | \Theta) \]   此时我们就可以用EM算法,它是常用的估计参数隐变量的利器,它是一种迭代式的方法,其基本想法是:若参数\(\Theta\)已知,则可根据训练数据推断出最优隐变量\(\boldsymbol{Z}\)的值(E-step),反之,若\(\boldsymbol{Z}\)的值己知,则可方便地对参数\(\Theta\)做极大似然估计(M-step)。
  实际上这也是一个迭代的过程:

  • 基于\(\Theta^t\)推断隐变量\(\boldsymbol{Z}\)的期望,记为\(\boldsymbol{Z}^t\)
  • 基于已观测变量\(\boldsymbol{X}\)\(\boldsymbol{Z}^t\)对参数\(\Theta\)做极大似然估计,记为\(\Theta^{t+1}\)

  进一步,若我们不是取\(\boldsymbol{Z}\)的期望,而是基于\(\Theta^t\)计算隐变量\(\boldsymbol{Z}\)的概率分布\(P\left(\mathbf{Z} | \mathbf{X}, \Theta^{t}\right)\),则EM算法的两个步骤是:

  • E-step(Expectation):以当前参数\(\Theta^t\)推断隐变量分布\(P\left(\mathbf{Z} | \mathbf{X}, \Theta^{t}\right)\),并计算对数似然\(LL(\Theta | \mathbf{X}, \mathbf{Z})\)关于\(\boldsymbol{Z}\)的期望: \[ Q\left(\Theta | \Theta^{t}\right)=\mathbb{E}_{\mathbf{Z} | \mathbf{X}, \Theta^{t}} L L(\Theta | \mathbf{X}, \mathbf{Z}) \]
  • M-step(Maximization):寻找参数最大化期望似然,即: \[ \Theta^{t+1}=\underset{\Theta}{\arg \max } Q\left(\Theta | \Theta^{t}\right) \]   上述过程不断迭代收敛到局部最优解。
      事实上,隐变量估计问题也可通过梯度下降等优化算法求解,但由于求和的项数将随着隐变量的数目以指数级上升,会给梯度计算带来麻烦,而EM算法则可看作一种非梯度优化方法。

关于EM算法,这个关于抛硬币的例子解释的很生动。

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 朴素贝叶斯分类器(Naive Bayes Classifier)
    1. 2.1. 拉普拉斯修正(Laplacian Correction)
  3. 3. 半朴素贝叶斯分类器(Semi-naive Bayes Classifiers)
    1. 3.1. SPODE(Super-Parent ODE)
    2. 3.2. TAN(Tree Augmented nave Bayes)
    3. 3.3. AODE(Averaged One-Dependent Estimator)
  4. 4. 贝叶斯网(Bayesian Network)
    1. 4.1. 结构
    2. 4.2. 学习
    3. 4.3. 推断
  5. 5. EM算法(Expectation-Maximization Algorithm)
  6. 6. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...