引言
前面介绍的分类算法，我们都是期望这个分类算法能够给我们一个确定的分类。但是，有时候，分类器也像我们人类一样，对自己的判断并不是非常有把握。这时候，我们需要分类器告诉我们，它将样本x归为A类的“把握”有多大，即概率有多大。
本文介绍一个非常常见的基于概率框架的分类器：贝叶斯分类器。这个主题分为两个部分：这篇属于理论篇，下一篇文章属于实战篇。
这篇文章分四个部分：1. 贝叶斯决策论；2. 朴素贝叶斯分类器； 3. 半朴素贝叶斯分类器及4.贝叶斯网络
贝叶斯决策论
在介绍贝叶斯决策论之前，先介绍两个概念：先验概率（prior probability）和后验概率（posterior probability）。
直观上来讲， 先验概率 是指在事件未发生时，估计该事件发生的概率。比如投掷一枚匀质硬币，“字”朝上的概率。后验概率是指基于某个发生的条件事件，估计某个事件的概率，它是一个条件概率。比如一个盒子里面有5个球，两个红球，三个白球，求在取出一个红球后，再取出白球的概率。
在wiki上， 先验概率的定义为：A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence。 后验概率的定义为：The posterior probability is the conditional probability of the variable taking the evidence into account. The probability is computed from the prior and the likelihood function via Baye's theorem.
现在以分类任务为例。 首先假设有N种可能的类别标签， 即y={c1, c2, ..., cN}, λij 表示将一个真实标记为cj的样本误分类为ci时产生的损失。后验概率p(ci|x)表示将样本x分类给ci是的概率。那么将样本x分类成ci产生的条件风险（conditional risk）为：
其中，P(cj|x) 表示样本x分类成cj类的概率，λij 表示将真实cj类误分类为ci类的损失。所以这个公式就是将x属于其他类（除ci类外）的概率与对应的误分类为ci的损失乘积之和。
我们的目标是寻找一个判定标准，以最小化总体的风险。这个判定准则也叫做贝叶斯判定准则(Bayes decision rule)： 为最小化总体风险，只需要在每个样本上选择那个能使条件风险R(c|x)最小的类别标记，即
此时，h称为贝叶斯最优分类器(Bayes optional classifier)，与之对应的总体风险R(h)称之为贝叶斯风险(Bayes risk). 1-R(h*)反映了分类器所能达到的最好性能，即理论上限。
如果把λij定义为：
那么风险函数可以改写为：
那么贝叶斯最优分类器的公式可以改写为：
为了最优化上面的函数，我们必须要知道后验概率p(c|x).但是在现实任务中，很难直接知道这个概率值，所以需要我们使用现有的训练数据估计出这个后验概率。这时候就需要使用贝叶斯公式：
其中，P(c)是类先验概率，表示在样本空间中，各类样本所占的比例。P(x|c)表示样本x相对于类标签c的类条件概率。直接通过样本计数的方式计算会有点麻烦。原因如下： 假设样本共有d个属性，且属性值都是二值的。那么样本空间至少有2^d个不同的样例。但是在现实生活中，样本空间的个数会远远小于这个数。所以通过计数的方式，直接算出这个概率的方式是不可靠的。
极大似然估计 一般估计类条件概率使用的是极大似然估计。首先我们假设样本符合某个确定的概率分布形式，然后使用极大似然法估计这个分布的参数θ。公式如下：
其中，Dc表示样本空间中c类组成的样本集和。所以对参数θ的最大似然估计为：
朴素贝叶斯
前面我们已经讲到，要估计条件概率P(c|x)，我们必须得求得类条件概率P(x|c)。但是这个类条件概率很难从有限的训练样本中直接获得，为了避开这个假设，我们使用朴素贝叶斯分类器（naive Bayes Classifier)，朴素贝叶斯分类器采用了“属性条件独立性假设”(attribute conditional independence assumption): 即对已知类别，假设所有的属性相互独立，那么P(c|x)可以重写为：
对应的朴素贝叶斯判定准则为：
半朴素贝叶斯分类器
前面讲到， 为了降低估计后验概率P(c|x)的难度，朴素贝叶斯分类器采用了属性条件独立性假设，但是在现实任务中这个假设往往不成立。于是，人们放松了这个假设的限制，提出了半朴素贝叶斯分类器的假设(semi-naive Bayes classifiers)的学习方法。其中， 独依赖估计(one-Dependent Estimator ODE)是半朴素贝叶斯分类器的一种常用的策略。独依赖估计假设所有的属性都依赖于某一个属性。这里介绍三种基于独依赖估计的半朴素贝叶斯分类器。第一种是SPODE(Super-Parent ODE),即假设所有的属性都依赖于同一个属性，这个属性也被称之为超父。超父属性的确定通过交叉验证的方式确定。第二种是TAN(Tree Augmented navie Bayes)。这种方法的做法是先计算任意两个属性之间的条件互信息(conditional mutual information),这样就可以建立一个完全连接图。基于这个图，就可以生成一棵最大带权生成树。这棵树之间的连接关系便是属性之间的依赖关系。最后一种是AODE(Averaged One-Dependent Estimator)，这种方法的做法是使用每个节点作为超父属性来构造SPODE，然后将具有足够训练数据支撑的SPODE集成起来作为最终的结果。
贝叶斯网
贝叶斯网(Bayesian network) 也称为信念网(belief network) ,它借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布。在贝叶斯网中三个变量之间的依赖关系共有三种情况：
V型结构也成冲撞结构，给定c的取值，a,b必不独立，但是当c的取值不知道时，a,b反而独立。
第二种结构是同父结构，示意图如下：
当c已知时，a和b独立。
最后一种是顺序结构，示意如下：
如果已知C，那么a和b条件独立。
基于贝叶斯网，可以很容易分析出各个属性之间的条件独立关系。我们只需生成对应的道德图(moral graph)就行。具体的做法如下：1）找到图中所有的V型结构，在V型结构的两个父节点之间加上一条无向边；2）然后将所有的有向边改为无向边。假设在道德图中，有变量x，y和变量集合z = {zi}，如果将z从变量集合中去除后，x和y分属两个连通分支，那么成变量x和y被z有向分离，记为x⊥y|z成立，即已知z，x和y相互独立。
如果要使用贝叶斯网络进行预测，一般包括两个步骤：1）学习；2）推断。即先通过学习来构建贝叶斯网络，再使用构建好的贝叶斯网络进行推断。对于学习过程，如果从所有的网络结构空间来搜索最优的贝叶斯网络，会是一个NP hard的问题。通常有两个近似解决方法：一种是使用贪心算法，即从某个网络结构出发，每次调整一条边(增加，删除或调整方向)，直到评分函数值不再下降为止。另一种是通过给网络结构施加约束来削减搜索空间。对于推断过程，如果是精确推断，也将会是NP hard问题，常用的解决方法是吉布斯采样法(Gibbs sampling)来得到近似的答案。
这篇的理论主要介绍到这里，对于其中没有说明的细节问题，有兴趣的读者可以查询其他的资料。
