User Tools

Site Tools


keynote:2011-lesson04

第四课 Probabilistic Graphical Models

定义

  • 对含有大量随机变量的真实问题建模
    • 含有依赖关系的变量可以简化建模过程

目标

  • 学习:使用训练数据估计联合分布
    • 计算p(A, B, C, D, E)的概率值
    • 变量数目很大怎么办?
  • 推理:给定分布p(A, B, C, D, E),
    • 计算某个事件发生的概率:给定E=e, 计算 A=a的概率
    • 得到概率最大时对应的各个变量的状态:p(A | E=e)概率最大时A的状态

非结构化方法

  • 特例:Naive Bayesian:假设变量都独立,则P(A,B,C,D,E)=P(A)P(B)P(C)P(D)P(E)

4.1 贝叶斯网络

  • 关于变量a,b,c的任意联合概率分布P(a,b,c)

  • 概率乘法法则:p(a,b,c)=p(c|a,b)p(a,b)=p(c|a,b)p(b|a)p(a)
  • 一般形式:

4.1.1 不完全连通图

  • 联合概率:p(x1,x2, … ,x7)
  • e.g.

  • 一般形式:
    • 对于含K个节点的图,联合概率

其中pak表示xk的父节点集合,x = {x1,… ,xK}

4.1.2 数学定义

  • 令G = (I,E)表示一个有向非循环图形(DAG),其中I代表图形中所有的节点的集合,而E代表有向连接线段的集合,且令X = (Xi)i ∈ I为其有向非循环图形中的某一节点i所代表之随机变数,则途中节点X的联合机率分配可以表示成:P(A), P(B|A=a), P(B|A=a), P(C|A=a), P(C|A=~a), P(D|b, c), P(D|~b, c), P(D|~b,c); P(D|~b,~c), P(E|c), P(E|~c)…
  • 马尔科夫条件:每个变量都独立于其非后代的节点。

4.2 图模型的常用推导方法

  • 变分法:变分贝叶斯,变分EM(参见bishop 第10章)
  • 抽样法:吉布斯抽样法(参见bishop 第11章)

4.3隐马尔可夫模型

4.3.1马尔可夫性质

  • 正式定义

一组随机变量序列X=\{X_n\},n=0…N,其中X_k的取值为s_ks_k\inN,当且仅当P(X_m=s_m|X_0=s_0,…, X_{m-1}=s_{m-1})=P(X_m=s_m|X_{m-1}=s_{m-1}),则X满足马尔可夫性质。

  • 非正式定义

一个过程的“将来”仅依赖“现在”而不依赖“过去”,则此过程具有马尔可夫性质。

4.3.2马尔可夫链的历史

  1. 马尔可夫链理论发展于1900年
  2. 隐马尔可夫模型发展于六十年代晚期
  3. 在六七十年代广泛应用于语音识别
  4. 1989年被引入计算机科学

4.3.3 马尔可夫链的应用

  1. 生物信息学
  2. 信号处理
  3. 数据分析和模式识别

4.3.4 马尔可夫链

  • 一条马尔可夫链由以下三要素确定:
    1. 状态空间 S=\{s_1, s_2, … , s_n\}
    2. 初始分布 a_0
    3. 转移矩阵 A

4.4 最大似然估计

从一个给定的O和Q中,似然值为:\\
$L(A,B,\pi)=a_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_}...a_{i_{T-1}i_T}b_{i_To_T}$\\
Log-likehood 值为\\
$l(A,B,\pi)=\sum_{i=1}^Mf_{i0}ln(a_i)+\sum_{i=1}^M\sum_{j=1}^Mf_{ij}ln(a_{ij})+\sum_{i=1}^M\sum_{o(i)}ln(b_{io})$\\
最大似然估计就是要求以下参量:\\
$a_i=\frac{f_{i0}}{1} a_ij=\frac{f_{ij}}{\sum_{j=1}^Mf_{ij}}$\\

由于直接从似然函数求最大似然估计过于困难,人们采用一些技术来计算:

  1. The Segmental K-means Algorith
  2. The Baum-Welch (E-M) Algorithm

本节编撰作者(请大家在这里报到):

  • 余宙 (ID: 11021026), 编写了定义
  • 孙舒扬 (ID: 11021022), 编写了4.1 贝叶斯网络
  • 于智 (ID: 11021025), 编写了4.4 最大似然估计
  • 张晨逸 (ID: 11021027), 编写了4.2 图模型的常用推导方法
  • 吴越 (ID: 11021024), 编写了4.3隐马尔可夫模型
  • AuthorName6 (ID: xxxxxxxxx), 编写了…

浙江大学2008-2010版权所有,如需转载或引用,请与 作者联系

keynote/2011-lesson04.txt · Last modified: 2014/05/22 08:34 (external edit)