贝叶斯分类器

贝叶斯决策论

先来看几个公式：

条件风险：

其中λij是将一个真实标记为cj的样本错分类为ci所产生的损失，这里的条件风险也叫作expected loss

总体风险

R(h) = Ex[R(h(x)|x)]

其中，h就是我们希望找到的准则，使得R(h)最小化，显然只需要在每个样本上选择那个能使得条件风险R(c|x)最低的类别标记，即**h*(x) = arg min R(c|x)**

因此R(h)就是贝叶斯风险，而1-R(h)则反映了分类器能到达的最好性能。

若将误判损失λij表示为：λij = 1，if i = j; λij = 0, otherwise

那么条件风险将变成：

因此贝叶斯最小分类器就变成了：h*(x) = arg max P(c|x),然后根据贝叶斯定理有：如果要根据贝叶斯判断准则来最小化决策风险，那么就要获得后验概率P(c|x)，总体有两种策略：给定x，通过直接建模P(c|x)来预测c，这叫discriminative models；也可以先对联合概率分布P(x, c)建模，由此得到P(c|x)，这是generative models。一般来说，决策树，BP神经网络，支持向量机，都是前者。

极大似然估计

这里的介绍说的很好，结合一下：https://www.zhihu.com/question/20447622

最好的理解就是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。

举个例子，麻袋里有白球和黑球，抽取十个球，有放回地抽到了七个黑球和三个白球，那么如果我们需要估计黑白球的比例时就可以用极大似然估计。假设抽到黑球的概率为p，也就是求解导致这个结果的参数值的最大可能性：P(七个黑球)=p7 (1-p)*3。要使得概率最大，那就需要求导。

往往求导之前，我们需要取对数，这样就变成了线性相加，避免下溢。

需要注意的是，这种方法需要预先假设概率分数，因此这十分依赖假设的概率分布是否符合真实数据分布。

朴素贝叶斯分类器

基于上面的贝叶斯公式可以看到，计算后验概率的主要困难是条件概率P(x|c)为所有属性上的联合计算，很难直接估计而得。为了避开这个问题，朴素贝叶斯分类器(naive Bayes classifier)采用了属性条件独立性假设。则将贝叶斯公式写成

由于对所有的类别P(x)都是一样的，因此贝叶斯的判断准则就变成了这样的分类器

假设Dc表示训练集D中第c类样本组成的集合，那么

对于离散属性则有

至于连续属性，则可考虑使用概率密度函数，假定

需要注意的是，若某个属性值在训练集中没有与某个类同时出现过，如果直接进行概率估计，那么概率就为0，在分类器的公式计算结果最后也为0。为了便民其它属性携带的信息被该属性值抹去，我们需要在估计概率值时进行拉普拉斯修正。则上面的式子会被修正为（其中N为类别数）：

半朴素贝叶斯分类器

在上面一节中，我们提到了用属性条件独立性假设来降低计算后验概率P(c|x)的困难，但独立性在现实中很难成立。因此人们便提出了半朴素贝叶斯分类器。

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

因此，公式改写成：其中，为属性的父属性，即所依赖的属性。

那么现在的问题就是如何确定每个属性的父属性，有以下两种方法：

一种是假设所有属性都依赖于同一个属性，称为"超父"，即SPODE方法：
另一种则是TAN，在最大带权生成树的基础上，将依赖关系简约为树形结构；

AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制，更加强大的独依赖分类器。它会将每个维度的特征属性作为超父来构建SPODE，然后线性组合出最终的模型。

贝叶斯网

贝叶斯网（Bayesian network）借助有向无环图来刻画属性之间的依赖关系，另外还利用了条件概率表来描述属性的联合概率。所以贝叶斯网是由结构G和参数组成的。

结构

贝叶斯网的结构表示了属性间的条件独立性，因此所有属性的联合概率定义为： \[ P_B(x_1,x_2,...,x_d) = \prod_{i=1}^{d}P_B(x_i|\pi_i) = \prod_{i=1}^{d}\theta_{{x_i}|{\pi_i}} \] 下图展示贝叶斯网中三个变量之间的典型依赖关系

我们一个一个看

在同父结构中，给定父节点x1的取值，则x3与x4条件独立

在V型结构中，给定子结点x4，则x1与x2必不独立，若x4完全未知，则x1与x2独立

在顺序结构中，给定x的值，则y与z条件独立，先要通过贝叶斯公式转化

为了分析有向图中变量间的条件独立性，我们可以使用有向分离的方法将有向图转化为无向图，由上面的叙述可以知道除了V型图的非中间节点没有条件独立性之外，其它两个与依赖是否有向是无关的。

基于这种事实，我们可以找出图中所有的V型结构，在V型结构的两个父节点之间加上一条无向边，并且将所有的有向边改为无向边，构成道德图(moral graph)。

在道德图中，如果变量x和y能够被变量z分开，则称x和y被z有向分离，同时具有条件独立性：

学习

如果得到了贝叶斯网的结构，即得到了属性间的依赖关系，那么只需要对训练样本“计数”即对贝叶斯网进行学习。因此我们的首要任务就是找出结构最“恰当”的结构。

为了达到这个目的，我们定义一个评分函数（score function），来评估贝叶斯网与训练数据的契合度。给定训练集D={x1,x2,...,xm}，贝叶斯网B=<G, >在D上的评分函数为：其中|B|为参数个数，为每个参数需要的字节数，至于LL(B|D)则是贝叶斯网B的对数似然，描述的是B对应的概率分布对D描述得有多好。

推断

贝叶斯网训练好之后就能通过一些属性变量的观测值来推测其它属性变量的取值了。但直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，是一个NP难的问题。

在现实应用中，往往采取的是吉布斯采样（Gibbs sampling）。具体算法原理不大懂，大致的步骤就是首先产生一个与证据变量一致的样本作为初始点，然后每步从当前样本出发产生下一个样本，然后逐个地对非证据变量进行采样以改变其初值。假定经过T次后采样得到的与q一致的样本共有nq个，那么后验概率就是：

EM算法

前面的讨论都是基于所有属性变量的值都已经被观测到了，但很多情况下，训练样本可能是不完整的，那么我们应该怎样对参数进行估计呢。

简单来说就是从某个参数值为起点，执行以下步骤，直至收敛：

基于推断隐变量Z的期望，记为；
基于已经观测的变量X和对参数做极大似然估计；