Data-method-04Bayesianlearning当你排除了不可能的，剩下的，无论多么不可能，都一定是真理。--夏洛克·福尔摩斯《四大神签》数据系列：目录｜配置｜代码仓库｜实战对应《数据挖掘导论》第5章、《机器学习》第7章、《统计学习方法（第2版）》第4章.贝叶斯学习是指利用参数的先验分布和从样本信息中得到的后验信息来寻找总体分布的方法。这里主要介绍贝叶斯分类器的相关知识。1.贝叶斯定理、贝叶斯决策理论、参数估计【贝叶斯定理】贝叶斯定理（Bayestheorem），又称贝叶斯推理，是一种先验知识类和从数据中收集的新证据结合统计原理。贝叶斯公式：${\rmP}(Y|X)=\frac{{\rmP}(X\|\Y){\rmP}(Y)}{{\rmP}(X)}$jointprobability${\rmP}(X=x,Y=y)$：表示$X$取$x$和$Y$取$y$的概率；条件概率${\rmP}(Y=y\|\X=x)$：表示当$X$取$x$时$Y$取$y$的概率；是的，${\rmP}(X,Y)={\rmP}(Y\|\X)\times{\rmP}(X)={\rmP}(X\|\Y)\times{\rmP}(Y)$【贝叶斯决策理论】贝叶斯决策理论是在概率论框架下实施决策的基本方法。对于分类任务，在所有相关概率已知的理想情况下，贝叶斯决策理论考虑如何根据这些概率和误判损失来选择最优的类标签。假设：$\mathcal{Y}=\{c_1,c_2,...,c_N\}$：有$N$种可能的类别标签$\lambda_{ij}$：标记一个真正的$c_j$造成的损失样本错误分类为$c_i$是：预期损失：${\rmR}(c_i\|\x)=\sum^N_{j=1}\lambda_{ij}{\rmP}(c_j\|\x)$将样本$x$分类为$c_i$的预期损失；即样本$x$上的条件风险（conditionaldisk）；目标是找到一个判断标准$h:\mathcal{X}\rightarrow\mathcal{Y}$来最小化整体风险${\rmR}(h)={\rmE}_x[{\rmR}(h(x)\|\x)]$对于每个样本$x$，如果$h$可以最小化条件风险${\rmR}(c_i\|\x)$，那么整体风险也可以最小化贝叶斯决策规则）：为了最小化整体风险，我们只需要在每个样本上选择能够使条件风险${\rmR}(c\|\x)$最小的类标签，即即，$h^*(x)={\arg\min}_{c\in\mathcal{Y}}R(c\|\x)$$h^*$：贝叶斯最优分类器（Bayesoptimalclassifier）${\rmR}(h^*)$：贝叶斯风险（Bayesrisk）$1-{\rmR}(h*)$：分类器所能达到的最佳性能，即分类器的理论上限机器学习所能产生的模型准确率是特定的，换句话说，如果目标是最小化误判损失$\lambda_{ij}$:$\begin{equation}\lambda_{ij}=\left\{\begin{aligned}&0,&{\rmif}\i=j\\&1,&{\rmotherwise}\end{aligned}\right.\end{equation}$条件风险：${\rmR}(c\|\x)=1-{\rmP}(c\|\x)$贝叶斯最优分类器：$h^*(x)=\arg\max_{c\in\mathcal{Y}}{\rmP}(c\|\x)$即对每个样本$x$，选择能最大化后验概率的类别标签${\rmP}(c\|\x)$然而在实际任务中，后验概率通常很难直接获得，所以机器学习需要实现的是在有限的训练样本集的基础上尽可能准确地估计后验概率。主要有两种策略：判别模型（discriminativemodels）给定$x$，直接建模${\rmP}(c\|\x)$来预测$c$如决策树、BP神经网络、支持向量机和其他生成模型（generativemodels）给定$x$，首先对联合概率分布${\rmP}(x,c)$建模，然后从中得到${\rmP}(c\|\x)$这个贝叶斯分类器生成模型考虑：${\rmP}(c\|\x)=\frac{{\rmP}(c){\rmP}(x\|\c)}{{\rmP}(x)}$使用贝叶斯定理：${\rmP}(c\|\x)=\frac{{\rmP}(c){\rmP}(x\|\c)}{{\rmP}(x)}$${\rmP}(c)$：类先验（prior）概率，表示样本空间中各种样本的比例，根据大数定律，当训练集包含当有足够的独立同分布样本时，${\rmP}(c)$可以通过各种样本的频率来估计：${\rmP}(x\|\c)$:sample$c$相对于标记$c$或ca的类别条件概率lledlikelihood(likelihood)${\rmP}(x)$:归一化的证据因子对于给定的样本$x$，证据因子${\rmP}(x)$与类标签无关，所以估计${\rmP}(c\|\x)$的问题转化为如何估计先验${\rmP}(c)$和似然${\rmP}(x\|\c)$[参数估计]由于在实际问题中可能只有有限的样本数据，所以先验概率${\rmP}(c)$和条件概率${\rmP}(x\|\c)$是未知的，因此需要先进行估计，然后应用贝叶斯分类器。估计概率的一种常用策略是假设它具有某种形式的概率分布，然后根据训练样本估计概率分布的参数。因此，概率模型的训练过程就是参数估计的过程。对此，统计学界有两种学派。优化似然函数和其他准则来确定参数值，例如最大似然估计、矩估计；贝叶斯（Bayesian）：认为参数是一个不可观测的随机变量，它本身也有一个分布，所以可以假设参数服从一个先验分布，然后根据观测数据。（如何开始套娃）详细介绍请参考基础-参数估计2朴素贝叶斯分类器【基本概念】贝叶斯定理：${\rmP}(c\|\x)=\frac{{\rmP}(c){\rmP}(x\|\c)}{{\rmP}(x)}$估计后验概率${\rmP}(c\|\x)$主要难点是很难从有限的训练样本中直接估计类别条件概率${\rmP}(x\|\c)$。朴素贝叶斯分类器采用属性条件独立假设（attributeconditionalindependenceassumption）：对于已知类别，假设所有属性相互独立可以改为：${\rmP}(c\|\x)=\frac{{\rmP}(c){\rmP}(x\|\c)}{{\rmP}(x)}=\frac{{\rmP}(c)}{{\rmP}(x)}\Pi^d_{i=1}{\rmP}(x_i|c)$对所有类别都是一样的${\rmP}(x)$，朴素贝叶斯可以表示为：$h_{nb}(x)={\arg\max}_{c\in\mathcal{Y}}{\rmP}(c)\Pi^d_{i=1}{\rmP(x_i|c)}$朴素贝叶斯分类器的训练过程是根据训练集估计类先验概率$\rmP(c)$和估计条件概率${\rmP}(x_i|c)$，即具体估计方法可以采用极大似然估计、贝叶斯估计等，具体见下节类先验概率：${\rmP}(c)=\frac{|D_c|}{|D|}$条件概率：离散属性：${\rmP}(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}$连续属性：连续属性可以是离散的，则将连续属性值替换为对应的离散区间；假设连续变量服从一定的概率分布，考虑概率密度函数，然后利用训练数据估计分布的参数。高斯分布常用来表示连续属性的类条件概率分布，假设${\rmP}(x_i|c)～\mathcal{N}(\mu_{c,i},\sigma^2_{c,i})$,$\mu_{c,i}$,$\sigma^2_{c,i}$表示第$c$类样本的值在$i$属性上的均值和方差，有是：${\rmP}(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}})$加上先验概率${\rmP}(x)$和条件概率${\rmP(x_i|c)}$，则模拟后验概率可以计算${\rmP}(c){\rmP}(x|c)={\rmP}(c)\Pi^d_{i=1}{\rmP(x_i|c)}$然后确定类别$h_{nb}(x)={\arg\max}_{c\in\mathcal{Y}}{\rmP}(c)\Pi^d_{i=1}{\rmP(x_i|c)}$[概率估计]先验概率和条件概率估计的数学基础是参数估计，常用的有最大似然估计和贝叶斯估计。最大似然估计类先验概率：${\rmP}(c)=\frac{|D_c|}{|D|}$条件概率：离散属性：${\rmP}(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}$连续属性：可以将连续属性离散化，然后将连续属性值替换为对应的离散区间；假设连续变量服从一定的概率分布，考虑概率密度函数，然后利用训练数据估计分布的参数。高斯分布常用来表示连续属性的类条件概率分布，假设${\rmP}(x_i|c)～\mathcal{N}(\mu_{c,i},\sigma^2_{c,i})$,$\mu_{c,i}$,$\sigma^2_{c,i}$表示第$c$类样本的值在$i$属性上的均值和方差，有是：${\rmP}(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}})$不足：当某个属性值没有出现在训练集中的某个类中时，可能会导致概率值为0，尤其是当训练样例少，属性数量多的时候。贝叶斯估计条件概率：${\rmP}_\lambda(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum^N_{i=1}I(x^{(j)}_i=a_{jl},y_i=c_k)+\lambda}{\sum^N_{i=1}I(y_i=c_k)+S_j\lambda}$其中$\lambda\ge0$，其中相当于给随机变量的每个值的频率分配一个正数$\lambda>0$。当$\lambda=0$时，是最大似然估计${\rmP}(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}$；当$\lambda=1$时，为拉普拉斯平滑（Laplaciansmoothing）${\rmP}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$，$N_i$表示第$i$个属性可能取值的先验概率：${\rmP}_\lambda(Y=c_k)=\frac{\sum^N_{i=1}I(y_i=c_k)+\lambda}{N+K\lambda}$当$\lambda=0$时，最大似然估计${\rmP}(c)=\frac{|D_c|}{|D|}$当$\lambda=1$时，拉普拉斯平滑${\rmP}(c)=\frac{|D_c|+1}{|D|+N}$，$N$表示训练集可能类别数的拉普拉斯校正避免了由于样本不足导致概率估计为零的问题，并且当训练集变大时，校正过程引入的先验影响会逐渐变得可以忽略不计。使估值逐渐趋向于实际概率值。【实际使用】在现实中，朴素贝叶斯分类器可以有多种用途。例如，如果任务需要很高的预测速度，则可以预先计算并存储所有涉及的概率估计。预测时，只需“查表”即可判断；如果任务数据变化频繁，可以采用“惰性学习”的方式，先不进行训练，收到预测请求时根据当前数据集进行概率估计；如果任务数据继续增加，那么在已有估值的基础上，只需要对新增样本的属性值所涉及的概率估值进行技术修正，就可以实现增量学习。朴素贝叶斯是一种典型的生成式学习方法。它从训练数据中学习联合概率分布，然后得到后验概率分布。概率估计方法可以是最大似然估计或贝叶斯估计。朴素贝叶斯的基本假设是条件独立性，虽然在实际应用中往往难以成立，但在很多情况下可以取得相当不错的性能。有以下可能的解释：对于分类任务，只需要对每个类别的条件概率进行正确的排序，不需要精确的概率值就可以得到正确的分类结果；如果属性之间的依赖关系对所有类别的影响相同，或者依赖关系的影响可以相互抵消，则属性条件独立假设正在减少计算开销。而不会对性能产生负面影响。朴素贝叶斯分类器一般具有以下特点：面对孤立的噪声点，朴素贝叶斯分类器具有鲁棒性；面对不相关的属性，朴素贝叶斯分类器是鲁棒的；相关属性可能会减少朴素贝叶斯分类器。是的性能，因为对于这些属性，条件独立性的假设不再成立。这里没有给出朴素贝叶斯分类器的例子。可以阅读书中相应章节或查看相应习题。3.半朴素贝叶斯分类器（semi-na?veBayesclassifeiers）：适当考虑了一部分属性之间的相互依赖信息，既不需要计算完整的联合概率，也不需要忽略比较强的属性依赖。“单相关估计器”（One-DependentEstimator，ODE）是半朴素贝叶斯分类器中常用的一种策略，假设每个属性至多依赖于类别外的另外一个属性，即${\rmP}(c|x)\propto{\rmP}(c)\Pi^d_{i=1}(x_i|c,pa_i)$$pa_i$：属性$x_i$所依赖的属性，称为$x_i的parent$确定属性父属性的方法：SPODE（Super-ParentODE）方法：假设所有属性都依赖于同一个属性，称为“超父”，然后通过交叉验证确定超父属性和其他选型方法；TAN（TreeAugmentedna?veBayes）方法：在最大权生成树算法的基础上，将属性之间的依赖关系简化为一个属性结构；AODE（AveragedOne-DependentEstimator）：基于集成学习机制，更强大的独立依赖分类器，AODE尝试构造以每个属性为超父类的SPODEs，然后将那些有足够训练数据支持的SPODEs整合为最终结果.具体内容不做介绍，这里只做一个大概的了解。4.贝叶斯网络【基本概念】贝叶斯信念网络（Bayesuabbeliefnetworks，BBN），简称贝叶斯网络，借助有向无环图（DirectedAcyclicGraph，DAG）来描述属性之间的依赖关系，并利用条件概率表（ConditionalProbabilityTable，CPT）描述属性的联合概率分布。一个贝叶斯网络$B$由结构$G$和参数$\Theta$组成，即$B=\langleG,\Theta\rangle$。网络结构图$G$：有向无环图，每个节点对应一个属性，如果两个属性有直接依赖关系，则由边连接。参数$\Theta$：定量描述这种依赖关系，假设$G$中属性$x_i$的父节点集为$\pi$，则$\Theta$包含条件概率表$\theta_{x_i|\pi_i}={\rmP}_B(x_i|\pi_i)$网络结构图贝叶斯网络中三个变量之间的典型依赖关系如下，同父结构：给定父节点$x_1$值，则$x_3$和$x_4$是条件独立的V型结构/碰撞结构：如果给定$x_4$的值，则$x_1$和$x_2$不必独立；如果$x_4$的值完全未知，则$x_1$和$x_2$相互独立顺序结构：给定$x$的值，则$y$和$z$条件独立条件独立：对于贝叶斯网络中的一个节点，如果其父节点已知，则它条件独立于其所有非后代节点。条件独立性是分析有向图之间的条件独立性。有向分离（Dseparation）可用于将有向图转化为无向图：找到有向图中的所有V形结构，并在V形结构中的两个父节点之间添加一条无向边；将所有有向边更改为无向边。由此产生的无向边称为“道德图”，连接父节点的过程称为“道德化”。道德图可以直观快速的找出向量之间的条件独立性：假设道德图中有变量$x$、$y$和变量集$z=\{z_i\}$，如果$x$和$y$在图上可以用$z$隔开，那么变量$x$和$y$用$z$定向隔开，$x\perpy\|\z$建立如下图例子，有分别是$x_3\perpx_4\|\x_1$,$x_4\perpx_5\|\x_2$,$x_3\Perpx_2\|\x_1$等条件概率表有向无环图中的每个节点都关联一个概率表：如果节点$x$没有父节点，表只包含先验概率${\rmP}(x)$；如果节点$x$只有一个父节点$y$，则该表包含条件概率${\rmP}(x|y)$；如果节点$x$有多个父节点$\{y_1,y_2,...,y_k\}$，该表包含条件概率${\rmP}(x|y_1,y_2,...,y_k)$【简单例子】下面的例子来自《数据挖掘导论》第五章不运动和健康饮食的人患心脏病的概率的一些计算例子：$$\begin{aligned}{\rmP}(heartdisease={\rmNo}|exercise={\rmNo},diet=health)&=1-{\rmP}(heartdisease={\rmNo}|exercise={\rmYes},diet=health)\\&=1-0.55=0.45\end{aligned}$$在没有先验信息的情况下，一个人有心脏病的概率：$$\begin{aligned}{\rmP}(HD=Yes)&=\sum_\alpha\sum_\beta{\rmP}(HD=Yes|E=\alpha,D=\beta){\rmP}(E=\alpha,D=\beta)\\&=\sum_\alpha\sum_\beta{\rmP}(HD=Yes|E=\alpha,D=\beta){\rmP}(E=\alpha){\rmP}(D=\beta)\\&=0.25\times0.7\times0.25+0.45\times0.7\times0.75+0.55\times0.3\times0.35+0.55\times0.3\times0.75\\&=0.49\end{aligned}$$在高血压的情况下，一个人患心脏病的概率：首先需要计算${\rmP}(BP=high)$,$$\begin{aligned}{\rmP}(BP=high)&=\sum_\gamma{\rmP}(BP=high|HD=\gamma){\rmP}(HD=\gamma)\\&=0.85\times0.49+0.2\times0.51=0.5185\end{aligned}$$然后计算${\rmP}(HD=Yes|BP=High)$$$\begin{aligned}{\rmP}(HD=Yes|BP=high)&=\frac{{\rmP}(BP=high|HD=Yes){\rmP}(HD=Yes)}{{\rmP}(BP=high)}\\&=\frac{0.85\times0.49}{0.5185}=0.8033\end{aligned}$$高血压、健康饮食、经常运动的人患心脏病的概率$$\begin{aligned}&{\rmP}(HD=Yes|BP=High,D=Healthy,E=Yes)\\=&[\frac{{\rmP}(BP=High|HD=Yes,D=Healthy,E=Yes)}{{\rmP}(BP=High|D=Healthy,E=Yes)}]\times{\rmP}(HD=Yes|D=Healthy,E=Yes)\\=&\frac{{\rmP}(BP=High|HD=Yes){\rmP}(HD=Yes|D=Healthy,E=Yes)}{\sum_\gamma{\rmP}(BP=High|HD=\gamma){\rmP}(HD=\gamma|D=Health,E=Yes)}\\=&\frac{0.85\times0.25}{0.85\times0.25+0.2\times0.75}\\=&0.5862\end{aligned}$$[建模与推理]贝叶斯网络建模包括两部分：创建网络结构和估计每个节点概率表中的概率值。此外，“评分搜索”是寻找最“合适”的贝叶斯网络的常用方法。“得分搜索”，首先定义一个得分函数（scorefunction）来评价贝叶斯网络与训练数据的拟合度，然后根据这个得分函数找到最优的贝叶斯网络。贝叶斯网络训练好后，可以通过一些属性变量的观测值进行预测。理想情况是如上例，根据联合概率分布准确计算后验概率，但这已被证明是NP-hard，现实中需要“近似推理”，通常采用吉布斯抽样来完成，这是一种随机抽样方法。对于可能存在的“不完整”训练样本，即存在未观察到的隐变量，可以采用EM算法进行处理。【BBN的特点】BBN提供了一种用图形模型捕捉特定领域先验知识的方法，网络也可以用来编码变量之间的因果依赖关系；构建网络可能费时费力，但网络结构一旦确定，加入新的变量就非常容易；BBN很适合处理不完整的数据，缺失属性的实例可以通过对属性所有可能取值的概率求和或积分来处理；由于数据和先验知识是基于概率的方法相结合的，因此该方法对模型的过拟合问题具有很强的鲁棒性；BBN为不确定性学习和推理提供了一个基础框架，具有很强的表示能力和良好的可解释性；贝叶斯网络学习可以分为结构学习和参数学习两部分，结构学习是NP-hard的。参考资料《数据挖掘导论》Chapter5《机器学习》Chapter7《统计学习方法（第2版）》Chapter4三本书中关于贝叶斯错误率、EM算法、打分函数等的内容这里就不记录了，因为内容太多了，比较复杂，这里是只有对一般概念有清晰的认识。实际遇到的时候可以参考相关资料。终于写完了，内容很多
