贝叶斯信念网络简介以及算法整理笔记

这几天在写BayesWipe，写到条件概率表（CPT，Conditional Probability Table）的时候，感觉对贝叶斯网络的参数学习还是有些不清楚，因此想整理一下贝叶斯信念网络（BBN，Bayesian Belief Network）的一些概念，包括一些方法的整理。
1. 参照一份PPT：https://wenku.baidu.com/view/83ed4295b90d6c85ed3ac6a5.html
2. 不知道算不算原创，不过都是我手打下来的
贝叶斯网络简介
1. 概率图模型的关系（包含关系）：
  1. 概率模型
    1. 图模型
      1. 有向图模型（贝叶斯网络）
        
        Alarm network
        
        State-space models
        
        Naive Bayes Classifier 朴素贝叶斯分类器
        
        PCA/ICA 降维？
        
        HMM 隐马尔可夫模型
      2. 无向图模型（Markov网络）
        
        Markov随机场
        
        Boltzmann Machine
        
        Ising model
        
        Max-ent model
        
        Log-linear models
        
        。。只听说过MRF，可以用Markov Logic Network作为模板生成
2. 基本思路
  1. 贝叶斯网络是为了处理人工智能领域研究中的不确定性而发展起来的。
  2. 它将概率统计应用于复杂领域进行不确定性推理和数据分析的工具。
  3. 贝叶斯网络可以系统地描述随机变量之间的关系，然后进行概率推理。
  4. 使用概率论处理不确定性可以保证推理结果的正确性。
3. 重要原理
  1. 链式法则：P(X1,X2,...XN) = P(X1)P(X2|X1)P(X3|X1,X2)...P(XN|X1,X2,...XN)
    1. P(A,B)=P(A)*P(B|A)记住这个就行了
    2. 也简单，知道了A发生的概率，A发生的情况下B发生的概率，相乘显然是A,B同时发生的概率咯
  2. 贝叶斯定理：P(A|B)=P(A)*P(B|A)/P(B)
    1. 基于上述公式P(A,B)=P(A)*P(B|A)=P(B)*P(A|B)
  3. 利用变量间条件独立性
    1. P(X1,X2...XN)=∏P(Xi|π (Xi))
    2. 应该是P(Xi|X1,X2,X3,X4..XN)=∏P(Xi|π (Xi))，其中π (Xi)是父节点，后验概率应该只和父节点有关。
4. 一些问题
  1. BBN是什么
    1. 贝叶斯网络是一个基于网络的用来表达和分析包含了不确定性的模型的框架
  2. BBN用来该拿什么
    1. 辅助智能决策、数据融合，特征识别...
  3. 怎么来的
    1. 交叉了人工智能、决策分析、统计等
贝叶斯网络的几个主要问题
1. 贝叶斯网络概率推理（Probabilistic Inference）
2. 结构学习（Structure Learning）
3. 参数学习（Parameter Learning）
4. 分类（Classification）
5. 隐变量和隐式结构学习（Hidden variables and hidden structure learning）
推导：
1. 详情见图
2. P(Z1|X1)=P(Z1|Y1,X1)P(Y1|X1)+P(Z1|Y2,X1)P(Y2|X1)
  1. 这里X1，X2/Y1，Y2的并集都是数据点的全集，所以可以这么做
  2. P(Z2|X1)=1-P(Z1|X1)
  3. P(W1|X1)可以一样的求出来
3. P(Y1)的话可以用P(X1,Y1)+P(X2,Y1)来求，然后通过贝叶斯公式
  1. 同理P(Z1),P(W1)也可以链式求得
4. 最后我们得到了P(W1|X1)和P(W1)和P(X1)『P(X1) 是一个已知的量』
  1. 可以根据贝叶斯定理求出X1的后验概率了P(X1|W1)
为什么要用贝叶斯网络进行概率推理
1. 理论上，概率推理所需要的知识一个联合概率分布，但是联合概率分布的复杂度相对于变量个数成指数增长，所以变量众多的时候不可行。
2. 贝叶斯网络解决了这个问题
  1. 它把复杂的联合概率分布分解成一系列相对简单的模块，那样就可以降低知识获取（Knowledge Acquisition）和概率推理的复杂度，可以把概率论应用到大型问题上。
  2. 统计学、系统工程、信息论和模式识别等众多学科中的多种模型：
    1. 朴素贝叶斯模型
    2. 隐类模型
    3. 混合模型
    4. HMM
    5. ...
  3. 动态贝叶斯网络主要用于对多维离散时间序列的监控和预测。
  4. 多层隐类模型，能够揭示观测变量背后的隐结构。
概率论基础
1. 一个核心概念是条件独立：Conditional Independence
2. 给定变量集合X=(X1,X2,...,Xn)，变量Xi的父节点结合π (Xi)。我们可以用有向图来表示变量之间依赖和独立关系
  1. 每个变量（也就是Feature）都是一个节点
  2. 对每个节点Xi，都从π (Xi)中的每个节点引一条有向边道Xi。
    1. 父节点->子节点
3. BBN是一个DAG，节点表示随机变量，节点间的边表示变量间的直接依赖关系。
BBN应用
1. 医疗诊断、工业、编码学、生物信息学、时序数据等等
贝叶斯网络学习
1. 结构学习：发现变量之间的图关系
  1. 选择具有最大后验概率的结构
    1. P(Mi|D)=P(D|Mi)P(Mi)/P(D)
  2. 基于评分函数（Scoring function）
    1. BIC/MDL/AIC等等
    2. BNJ和Banjo都有实现这种方法
    3. BIC:
  3. 结构学习算法
    1. K2算法：
      1. 通过为每个结点寻找父结点集合来学习贝叶斯网络结构。它不断往父结点中集中添加节点，并选择能够最大化数据和结构的联合概率『P(X1,X2,X3...X4)』的节点集合。
    2. HillClimbing
      1. 从一个无边结构开始，在每一步，它添加能够最大化BIC的边。算法在通过添加边不能再提高结构得分时停止。
    3. 缺值数据结构学习：Structural EM
      1. SEM不是每次迭代都同时优化结构模型和参数，而是先固定模型结构进行数次参数优化后，再进行一次结构加参数优化，如此交替进行（大概跟GMM差不多吧）
      2. 目的是减小计算复杂度。
  4. BN结构
    1. 建立过程
    2. 从数据中学习BN的结构
      1. 基于熵（Entropy）的算法
        
        最早的方法
        
        用树和多边树的形式
      2. 条件独立
        
        定义每个结点的条件独立性（Markov边界）
        
        从Markov边界中推理出依赖性
      3. 基于score的度量
        
        实现得最多最广泛的方法
        
        定义一个质量的度量，并且最大化
        
        使用贪心搜索来决定要添加的最佳的结构
        
        但度量不再增加的时候，停止
      4. 模拟退火法和遗传算法
        
        相比于贪心搜索，更加高级的方法，同样用于score-based method
2. 参数学习：发现变量之间的互相关联的量化关系
  1. 最大似然估计
    1. 完全基于数据，不需要先验概率
    2. L(θ；D)=∏P(X[m]，Y[m]；θ) 其中m是每一条数据
      1. 我们可以在网络结构中知道X[m]，Y[m]在θ下的公式，然后再进行最大似然估计
    3. 如图：
  2. 贝叶斯估计
    1. 有了最大似然估计的函数，加上先验概率，然后最大化后验概率就可以了。
    2. 这个比较复杂
  3. 缺值数据最大似然估计(EM算法)
    1. 基于θt 对数据进行修补，使之完整『E-step』
    2. 对修补后的完整数据计算最大似然估计θt+1『M-step』
  4. 隐结构模型学习
    1. 隐变量是取值未被观察到的变量，通过数据分析：
      1. 隐变量个数
      2. 隐结构
      3. 隐变量的势
      4. 模型参数
    2. 方法：基于评分函数的爬山法
      1. BIC：
      2. 隐变量势学习爬山算法
      3. 隐结构学习双重爬山法。。。。
贝叶斯网络推理：建立了贝叶斯网络后，我们可以基于BBN推理得到变量的概率
1. 贝叶斯网络可以利用变量间的条件独立对联合分布进行分解，降低参数个数。
  1. 推理是通过计算来回答query的过程
  2. 计算后验概率分布P(Q|E=e)
2. 基础知识
  1. 图分割和变量独立（图分割、有向分割）
    1. 变量X和Y通过第三个变量Z相连接的三种情况
    2. 阻塞
      1. 设X为一节点集合，X和Y是不在Z中的两个节点，考虑X和Y之间的一条通路，如果满足下面的条件之一，则称被X阻塞：
        
        有一个在Z中的顺连节点；
        
        有一个在Z中的分连节点；
        
        有一个汇连节点，它和它的后代均不在Z中。
    3. 如果X和Y之间的所有通路都被Z阻塞，那么我们说Z有向分割X和Y，简称d-separate，d分割
      1. 则X和Y在给定条件Z时，条件独立。
      2. =》（定理）整体Markov性设X和Y为贝叶斯网N中的两个变量，Z为N中一个不包含X和Y的节集合，如果Z d-分割X和Y，那么X和Y在给定Z时条件独立
      3. d-分割是图论的概念，而条件独立是概率论的概念，所以定理揭示了贝叶斯网络图论侧面和概率论侧面之间的关系。
  2. Markov边界与端正图
    1. Markov边界
      1. 在贝叶斯网络中，一个节点的Markov边界包括了它的父节点、子节点以及子节点的父节点
        
        也就是爸爸儿子叔叔
    2. 端正图（Moral graph）：团树传播算法-junction tree
      1. 设G是一个DAG，如果将G中每个节点的不同步节点结合，也就是在它们之间加一条边，然后去掉所有边的方向，所得到的无向图就是G的端正图。
3. 网络推理算法
  1. 精确推理算法
    1. 变量消元算法
      1. 利用概率分解降低推理复杂度
        
        如果有贝叶斯网络如下：
        
        A->B->C->D
        
        可以利用一系列规则去掉、提取出条件独立的概率
      2. 使得运算局部化，消元过程实质上就是一个边缘化的过程。
      3. 最优消元顺序：最大势搜索，最小缺边搜索
        
        ...不是很懂
    2. 团树传播算法
      1. 利用步骤共享来加快推理的算法
      2. 团树是一种无向树，其中每一个节点代表一个变量集合，成为团(Clique)。团树必须满足变量的连通性，也就是包含同一变量的所有团所导出的子图必须是连通的。
      3. http://www.cnblogs.com/ironstark/p/5151713.html
  2. 近似推理
    1. 随机抽样：
      1. 这是一类应用于数值积分和统计物理中的近似计算方法。基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似计算感兴趣的量。
      2. MCMC算法-Gibbs Sampling
        
        首先随机生成一个与Evidence E=e一致的样本s1作为起始样本，此后，每个样本呢si的产生都依赖于前一个样本si-1，且si与si-1最多只有一个非证据变量的取值不同，记改变量为X。
        
        X的取值可以从非证据变量中随机选取，也可以按照某个固定顺序轮流决定。
        
        在si中，X的值通过随机抽样决定，抽样分布是
        
        当样本数N趋向于无穷的时候，Markov Chain理论保证了算法返回的结果收敛于真正的后验概率，Gibbs Sampling的缺点是收敛速度很慢，因为Markov Chain要花很长时间才能真正达到平稳分布。
      3. 随机抽样算法的理论基础是大数定理。
    2. 变分法（没解释）
jibenshang

秒客网

贝叶斯信念网络简介以及算法整理笔记

相关文章