贝叶斯分类器

1 贝叶斯决策理论

概率框架下实施决策的基本方法。其基于已知概率和误差损失来选择最优类别标记。

显然，每个样本若能最小化风险，则总体风险R（h）也将最小。由此产生了贝叶斯判定准则：为了最小化总体风险，只需要从每个样本选择使得条件风险R（c|x）最小的标记。

h称为贝叶斯最优分类器，总体风险R（h）称为贝叶斯风险。
1 - R（h*）反应了分类器的最好性能。

具体而言，若是要最小化分类误差。误差损失λij 可以记为：

显然，欲使用贝叶斯准则来最小化风险，首先要获取后验概率，然而在现实任务中这很难直接获得。所以，机器学习的目的是尽可能准确的估计出后验概率P（c|x）。有两种策略：
给定x，可以直接通过建模P（c|x）预测c，得到的是判别式模型。
联合概率分布p（x，c）建模，再获得P（c|x），这样是生成式模型。

产生式模型(Generative Model)与判别式模型(Discrimitive Model)是分类器常遇到的概念，它们的区别在于：

对于输入x，类别标签y：
产生式模型估计它们的联合概率分布P(x,y)
判别式模型估计条件概率分布P(y|x)

产生式模型可以根据贝叶斯公式得到判别式模型，但反过来不行。

两类模型对比：

以上关于判别式模型与生成式模型的比较转自：
https://blog.csdn.net/wolenski/article/details/7985426

对于生产式

由此，估计P（c|x）转为基于训练数据集D估计先验概率P（c）和似然概率P（x|c）。
根据大数定律，P（c）可以通过样本出现的概率直接估计。P（x|c）无法直接估计。
解决的办法就是，把估计P（x|c）转化为估计参数。
这里就将概率密度估计问题转化为参数估计问题，极大似然估计就是一种参数估计方法

2 极大似然估计

为了估计类条件概率，一个常用的策略是先假定其有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计。

具体而言：
类条件概率P（x|c），假定其有固定形式且被参数θ唯一确定，那么我们就需要通过训练集D估计参数θ，P（x|c）记为：P（x|θ）

对θ进行最大似然估计，就是去寻找能够使得P（Dc|θc）最大化的参数θ'。

3 朴素贝叶斯分类器

类条件概率P（x|c）是所有属性上的联合概率，难以从有限的训练样本中进行提取，为此，朴素贝叶斯分类器采用了属性条件独立性假设：对已知的类别，假设所有属性相互独立。

显然，朴素贝叶斯分类器的训练过程就是基于训练集D估计类先验概率P(c)和为每个类别估计条件概率P（x|c）

例子：

然后估计每个条件概率p（xi|c）

...

...

需要注意的是，某条属性的属性值在训练集中没有与某个类同时出现过时，会有以下情况：

在连乘过程中会使得结果为0，处理的方式是进行平滑。

4 半朴素贝叶斯分类器

朴素贝叶斯分类器中假设所有的属性调价相互独立，然而事实上，这个假设在实际任务中很难成立。所以，将属性条件独立性假设适当的放松，产生了“半朴素贝叶斯分类器”。
其基本思想就是适度的考虑一部分属性间的相互依赖性。

最常用的策略是ODE，独依赖估计。假设每个属性最多依赖于一个其它属性。

根据不同的选择父属性的策略，产生了不同的独依赖分类器

5 贝叶斯网

贝叶斯网也称为信念网，其借助无环图来刻画属性之间的关系，并借助条件概率表来描述属性的联合概率分布。
一个贝叶斯网B由结构G和参数θ构成。B = <G,θ>。G是一个有向无环图，其每个结点对应一个属性，若是两个属性之间存在直接依赖关系，那么它们将由一条边连接起来；参数θ定量描述这种关系。

联合概率定义为:

以图7.2为例联合概率为：

同父结构下，给定x1，则x3 x4条件独立。
顺序结构下，给定x，则y z条件独立。
V型结构下，不给定x4，则x1 x2相互独立。

为了分析图中变量的条件独立性，可以使用有向分离。首先将有向图转为无向图：
找出所有V型结构，在父节点之间加边。
该有向边为无向边。

• 学习过程
  若网络结构已知，那么我们根据属性间的关系，只需要对训练样本计数，估计出每个结点的条件概率表即可。但是，往往无法知晓网络结构。
  所以贝叶斯网学习的首要任务是找出结构最适合的贝叶斯网。
  通常使用的方法是构建评分函数来评估贝叶斯网和训练数据的切合程度。

• 推测
  贝叶斯网训练完成后就可以用于回答查询，通过一些属性变量的观测值来推断其它属性的取值。
  通过已知变量观测值来推断查询变量的过程叫做推断。已知变量称为证据。
  当网络结点过多且连接稠密时，难以进行精准推断，需要进行近似推断。常用的方法就是吉布斯采样法。

以西瓜问题为例：

吉布斯采样从随机产生一个与证据E = e 一致的样本 q⁰ 开始作为初始点，然后每一步从当前样本出发产生下一个样本。在 t 次采样中，假设 q^t = q^t-1，然后对非证据变量逐个采样。采样概率根据贝叶斯网络B和其它变量的当前取值计算获得。假定经过T次采样后，与q一致的样本共n_q个，则后验概率为：

吉布斯采样实质上是在贝叶斯网所有变量的联合状态空间与证据E = e 一致的子空间进行随机漫步，是一个马尔科夫链（马尔可夫链是满足马尔可夫性质的随机过程）。
马尔科夫性质：已知当前状态为i(n-1)的情况下，下一步状态为i(n)的概率只与i(n-1)有关，与之前的状态无关。

马尔科夫链需要很久才能趋于稳定。

6 EM算法

上面的讨论中，我们假定训练样本中所有属性都可以被观测到，即所有的训练样本都是完整的。但是现实应用中，往往会遇到不完整的训练样本。

然而，由于Z是隐变量，上式无法进行求解。所以通过对Z计算期望，来最大化已观测数据的对数似然。

EM（期望最大化）算法常用来估计参数隐变量，是一种迭代方法。其基本思想是：
E：若参数θ已知，则可以根据训练集推测最优Z
M：若Z已知，则对θ进行最大似然估计

隐变量估计问题也可以通过梯度下降法来进行优化求解。但是因为求和项数随着隐变量的数量指数上升，所以梯度下降法计算不易。EM算法可以视为一种非梯度优化方法。