概率图模型 林琛 博士、副教授.

Presentation on theme: "概率图模型 林琛 博士、副教授."— Presentation transcript:

1 概率图模型 林琛 博士、副教授

2 引子 Siri: iphone 4S上应用的一项语音控制功能 Judea Pearl 生活大爆炸（5-14-0500） 一段对话
“Siri, how’s the weather tomorrow in London?” “Sunny and mild” “How about Shanghai?” Judea Pearl 贝叶斯网络的先驱 奠定不确定性和因果推理在计算机等多个学科中的地位

3 概率基础 世界上许多事情都具有不确定性。 概率论是研究处理这类现象的数学理论 用概率表示事件发生的可能性。例如，P(硬币正面朝上)=0.5。
可能发生多次（频率论） 可能只能发生一次（贝叶斯概率） 随机试验的所有可能结果组成该试验的样本空间 例如，掷硬币，抛之前无法预知哪一面朝上；赌马，理论上每匹马都有跑第一的可能，事先无法预料那匹马一定会赢。

4 课堂测试（1） 事件投1次硬币的样本空间是？ 事件投2次硬币的样本空间是？

5 随机变量 随机变量是定义在样本空间上的函数，其所有可能取值的集合称为它的值域，也称状态空间。掷骰子试验，设X为“扔骰子实验的所有可能结果”，则X为一随机变量. 对单个随机变量X，可用概率函数P(X)来描述它的各个状态的概率 而对于多个随机变量X1，…，Xn，则可用 联合概率分布P(X1，…，Xn)来描述各变量所有可能状态组合的概率 联合分布刻画了变量之间的各种关系，包含了变量关系的所有信息 随机变量X1在另外一个随机变量X2各个状态下的发生概率为条件概率分布表示为P(X1| X2) 随机变量X1的各状态概率，与其他随机变量无关，叫做边际概率 我们首先讨论一下对系统建模的几个要素。

6 乘法法则与加法法则 加法规则 乘法法则 事件 A,B同时发生的概率是： 如果X,Y不相关，则可以表示为 P(X,Y)=P(X)P(Y)

7 课堂测试（2） 设有3个装有黑白两色球的口袋，第一个口袋黑白球各半，第二个口袋黑白球比例为4：1，第三个则全是黑球。用随机变量X，Y，Z分别代表从这3个口袋随机抽出的球的颜色，w表示白，b表示黑。则联合概率分布P(X,Y,Z)如右所示： 计算P(X=w),P(X=w|Y=b,Z=w) X Y Z P(X,Y,Z) w b 0.1 0.4 加和为1，边际概率，条件概率怎么算？

8 利用概率分布推理的例子 故事：Pearl教授家住洛杉矶，那里地震和盗窃时有发生。教授的家里装有警铃，地震和盗窃都有可能触发警铃。听到警铃后，两个邻居Mary和John可能会打电话给他。 问题: 一天，Pearl教授接到Mary的电话，说听到他家警铃响，Pearl教授想知道他家遭盗窃的概率是多大。 常用的解决此类问题的途径，即使用概率方法进行不确定性推理就是： 1) 把问题用一组随机变量来刻画； 2) 把关于问题的知识表示为一个联合概率分布; 3) 按照概率论原则进行推理计算。

9 朴素贝叶斯训练 训练数据集T={<x1,y1>,…,<xn,yn>} 朴素贝叶斯法学习以下先验概率分布及条件概率分布
由联合概率分布P(X,Y)独立同分布产生 朴素贝叶斯法学习以下先验概率分布及条件概率分布 先验概率分布P(Y=c) 条件概率分布P(X=x|Y=c) 朴素贝叶斯假设在类别确定的条件下，各特征是条件独立的即： 降低了计算复杂度 但可能牺牲分类精度

10 朴素贝叶斯预测 计算后验概率P(Y=c|X=x)，将后验概率最大的类作为类别预测输出 后验概率计算根据贝叶斯定理 同样是条件独立性假设

11 朴素贝叶斯的损失函数 假设朴素贝叶斯的决策模型是f(x) 对于一个训练样本x，损失函数L(y,f(x))
对联合分布P(X,Y)，损失函数的期望为 最小期望损失，只需要对每个x极小化

12 朴素贝叶斯算法 学习 预测 估算P(y=c)和P(Xi=xi|Y=c)的概率 估算后验概率P(Y=c|X=x) 确定其中概率最大的类别标记
一般采用最大似然 预测 估算后验概率P(Y=c|X=x) 确定其中概率最大的类别标记

13 平滑 概率值为0的情况 未观测到的样本 拉普拉斯平滑 对特征的条件产生概率 对类别的先验概率 Xj的不同特征值总数 这样确保了还是概率分布
>0 和为1

14 课堂测试（3） 故事：Pearl教授家住洛杉矶，那里地震和盗窃时有发生。教授的家里装有警铃，地震和盗窃都有可能触发警铃。听到警铃后，两个邻居Mary和John可能会打电话给他。 问题: 一天，Pearl教授接到Mary的电话，说听到他家警铃响，Pearl教授想知道他家是否遭盗窃了 B=盗窃，A=警铃，E=地震，M=Mary电话，J=John电话

15 贝叶斯网络 朴素贝叶斯假设各特征间是独立的，实际上可能是互相依赖的 Pearl提出了用如下方法构造一个有向无环图
全依赖的联合概率P(A,B,C,…M)=P(A)P(B|A)P(C|A,B)….P(M|A,B,C,…L) Pearl提出了用如下方法构造一个有向无环图 把每个变量都表示为一个节点； 对于每个节点Xi，都从跟其直接相关的节点画一条有向边到Xi. 要多少次运算？（多少个参数） 2n-1 要多少次运算？（多少个参数） =10 贝叶斯网络的链规则 P(B,E,A,J,M) =P(B)P(E|B)P(A|B,E)P(J|B,E,A)P(M|B,E,A,J) (1) =P(B)P(E)P(A|B,E)P(J|A)P(M|A) (2)

16 从图中可以看出，变量A依赖于B和E，那么A具体是如何依赖于B和E的呢？条件概率分布P(A|B,E)定量的刻画了这个问题：
P(E=1) 0.5 P(E) B E P(A=1) 1 0.29 0.95 P(B=1) 0.3 P(B) P(J|A) J P(J=1) 1 P(A|B,E) M P(M=1) 1 P(M|A) 从图中可以看出，变量A依赖于B和E，那么A具体是如何依赖于B和E的呢？条件概率分布P(A|B,E)定量的刻画了这个问题： 1) 盗窃和地震都发生时，警铃响的概率为P(A=y|B=y,E=y)=0.95 2) 只发生盗窃但没有发生地震时，警铃响的概率为P(A=y|B=n,E=y)=0.29 3) 所有其它情形 类似地，P(M|A)、P(J|A)定量刻画了M和J如何依赖于A . 变量B和E不依赖于其它变量，P(B)和P(E)给出它们的边缘分布 贝叶斯网络=有向五环图+条件概率表

17 贝叶斯网络的主要内容 Inference（推理） Learning（学习） 给定结构和CPT（条件概率表） 回答下面的问题 学习CPT
可以是离散/连续型变量 可以结合专家知识 可以结合数据 回答下面的问题 已经观察到某些变量 回答另一些变量发生的概率 Learning（学习） 学习CPT 可以是某种指定概率分布的参数 学习结构 可以是不完全数据 即有隐含变量

18 贝叶斯网络应用 贝叶斯网络属于产生式模型/生成模型（Generative model） 目标是P(y|x) 步骤 给出贝叶斯网络 学习 推理
P(y),P(x|y)的函数形式 学习 通过最大似然估计参数p(y),p(x|y) 推理 得到p(y|x)

19 课堂讨论 尝试使用贝叶斯网络建立一个自动肺癌诊断系统

20 常用的概率分布函数（基础） 期望=均值 方差

21 常用的概率分布函数（1） 离散变量 二元 假设掷硬币正面朝上（x=1）概率是u 假设投了N次，则其中出现m次正面朝上的概率是
Bernoulli分布 Binomial二项分布

22 常用的概率分布函数（2） Beta分布 Beta函数 Gamma函数

23 常用的概率分布函数（3） 离散变量 多元变量 可以把变量表示为 (0,0,0,1,0,0)，那么和二元变量类似，结果为xk的概率为
统计N次试验结果，其中第1、2…K类结果出现次数分别为m1,m2,…mK次的概率 Multinomial多项分布

24 常用的概率分布函数（4） 连续变量 多元高斯分布 任何一种概率分布可以表示为多个高斯分布的组合 又叫做混合高斯模型 协方差矩阵

25 参数学习（1） 最大似然 频率派观点：参数是固定的 对于给定的数据集，参数使产生该数据集的可能性最大（即最大似然）
由于参数固定，因此给定自变量x，结果y也是固定的

26 课堂测试 二项分布的最大似然估计 假设三次掷硬币结果是『1，1，1』，则最大似然估计下参数是多少？预测下一次掷硬币结果
最大似然估计参数u=1 每一次掷硬币结果都为正面

27 参数学习（2） 贝叶斯估计 贝叶斯派：参数也是随机变量 贝叶斯法则 由于参数不固定，结果也是随机的，因此给出预测的是期望值
如果数据量足够大，最大后验概率和最大似然估计趋向于一致，如果数据为0,最大后验仅由先验决定。 贝叶斯估计 贝叶斯派：参数也是随机变量 贝叶斯法则 无法找到解析解，所以一般用近似的最大后验概率 由于参数不固定，结果也是随机的，因此给出预测的是期望值 先验概率 似然 后验概率 =1

28 课堂测试 假设Bernoulli分布的参数u符合一个先验分布（Beta分布） 使用贝叶斯估计参数 参数自己设定
并解释最大后验概率和最大似然的相关性

29 解释 贝叶斯估计的性质 预测下一次掷硬币结果 由于分子=a0+m-1，分母=N+a0+b0-2，所以不会=1

30 贝叶斯网络v.s.Logistic回归 伯努利分布：掷硬币的分布，x=正/反

31 文本聚类：LDA w~Mul( 𝛽 𝑧 ) θ i ~Dir(α)
𝑝 𝜃,𝑧,𝒘 𝛼,𝛽 =𝑝 𝜃 𝛼 𝑛=1 𝑁 𝑝 𝑧 𝑛 𝜃 𝑝( 𝑤 𝑛 | 𝑧 𝑛 ,𝛽) Z~Mul(θ) 𝑝 𝐷 𝛼, 𝛽 = 𝑑=1 𝑀 𝜃 𝑑 𝑝 𝜃 𝑑 𝛼 𝑛=1 N d 𝑧 𝑑𝑛 𝑝 𝑧 𝑑𝑛 𝜃 𝑑 𝑝( 𝑤 𝑑𝑛 | 𝑧 𝑑𝑛 ,𝛽) ⅆ 𝜃 𝑑 Multinomial分布：投骰子 Dirichlet分布：Multinomial的共轭

32 贝叶斯网络v.s.线性回归

33 贝叶斯网络中可以有隐含变量 隐含变量（观测不到的变量）
例：假设有3枚硬币，分别记作A,B,C。这些硬币正面出现的概率分别是π,p,q。进行如下实验 先掷硬币A 如果是正面选择硬币B 否则选择硬币C 只能记录最终结果，看不到过程（即硬币A的结果） 独立重复10次试验，结果 1，1，0，1，0，0，1，0，1，1 Z Y

34 含有隐含变量的参数估计 观测结果的似然函数为 一种迭代的方法 EM算法 选取π,p,q初值 迭代，直到收敛
计算在给定的π,p,q参数下，观测结果来自掷硬币B的概率 根据观测结果来自硬币B，C的概率重新推断π,,p,q的值

35 其他情况 数据丢失 丢失 删失 截断 人为建立的隐含变量 通常是为了计算便利

36 数据丢失的例子 无丢失数据问题 一个多元变量的概率分布是 假设我们看到的观测变量是 丢失数据 5种可能取值 只观测到了4组变量 似然 ？

37 Example 1:Missing Data Original Problem (Complete Data)
Suppose a multinomial variable that takes four values with probability Observations Observed frequencies for the four values Estimate by maximizing likelihood The likelihood for complete data Set the derivative to be zero

38 朴素解法 迭代 最优参数 猜初值 猜丢失的数据 更新参数

39 删失数据的例子 假设病人的生存年限w是如下分布 如果知道一组病人中有r个非删失，n-r个删失 似然 如果不知道？

40 EM算法 输入：观测变量Y，隐变量Z，联合分布P(Y,Z|θ),条件分布P(Z|Y, θ) 输出： 模型参数θ 初始化θ 迭代
在迭代的第i+1轮 E步 M步：求上述Q最大的θ 可以任意初始化，但是EM算法对初值敏感 停止条件一般是模型参数变化收敛

41 EM算法原理 挑战： 解决：最大下界 Log( 括号内有加法操作无法获得解析解 ) 引入Z上的另一个分布q(Z)
q(Z)=p(Z|Y,θ) E步：通过q(Z)最大下界L(q,θ) 这时候θ没变 q(Z)=p(Z|Y,θ) M步：通过θ最大下界L(q,θ) q(Z)不变， θ变 所以KL距离大于0 似然增大 上面这个等式是否成立？代入

42 课堂测试 假设有3枚硬币，分别记作A,B,C。这些硬币正面出现的概率分别是π,p,q。进行如下实验。先掷硬币A，如果是正面选择硬币B，否则选择硬币C。独立重复10次试验，结果【1，1，0，1，0，0，1，0，1，1】。估计π,p,q 假设观测数据【-67,-48,6,8,14,16,23,24,28,29,41,49,56,60,75】是由两个分量的高斯混合模型生成，试估计模型的5个参数（系数、高斯模型的参数）

43 E步 M步 给定o,p,q,计算观测数据来自掷硬币B的概率 估计新π,p,q 初值取0.5,0.5,0.5
第一轮之后：0.5，0.6，0.6 第二轮之后：0.5，0.6，0.6 初值取0.4,0.6,0.7 得到：0.4064，0.5368，0.6432

44 初始 完全数据，假设rjk=1代表来自第k个高斯模型 写出完全数据的对数似然函数 E步 Q函数 M步 最大化

45 文本聚类：LDA w~Mul( 𝛽 𝑧 ) θ i ~Dir(α)
𝑝 𝜃,𝑧,𝒘 𝛼,𝛽 =𝑝 𝜃 𝛼 𝑛=1 𝑁 𝑝 𝑧 𝑛 𝜃 𝑝( 𝑤 𝑛 | 𝑧 𝑛 ,𝛽) Z~Mul(θ) 𝑝 𝐷 𝛼, 𝛽 = 𝑑=1 𝑀 𝜃 𝑑 𝑝 𝜃 𝑑 𝛼 𝑛=1 N d 𝑧 𝑑𝑛 𝑝 𝑧 𝑑𝑛 𝜃 𝑑 𝑝( 𝑤 𝑑𝑛 | 𝑧 𝑑𝑛 ,𝛽) ⅆ 𝜃 𝑑 Multinomial分布：投骰子 Dirichlet分布：Multinomial的共轭

46 随机变量序列 生活大爆炸（5-14-0500） 自然语言处理中的一系列问题 语音识别 词性标注 机器翻译 … Online demo
其他涉及到时间的问题 人的行为分析 视频中预测走路/步行/网球动作 网络中的入侵检测 其他涉及到序列的问题 基因组序列中蛋白质编码区域的预测 What's your name? My name? It's Siri. Are you single? I don't have a marital status, if that's what you're asking. How about a cup of coffee? I've found six coffee shops.

47 观测与状态序列 语音识别 wo3 ai4 bei3 jing1 tian1 an1 men1 我 爱 北 京 天 安 门 我 爱 北京 天安门 我爱/VV 北京/NR 天安门/NN 观测 额的神 中文分词 状态（隐含） 方 吗 词性标注

48 模型 隐马尔可夫模型定义 隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列；再由各个状态生成一个观测而产生观测随机序列的过程。 隐藏的马尔可夫链随机生成的状态的序列，称为状态序列 每个状态生成一个预测，由此产生的观测的随机序列，称为观测序列 序列的每一个位置可以看作是一个时刻

49 隐马尔可夫模型的基本假设 齐次马尔可夫性假设 观测独立性假设
假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关 观测独立性假设 假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关

50 HMM实例——描述 设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下
根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,…，称为观察值序列O。 不知道缸序列

51 HMM实例——示意 观测数据： Urn 3 Urn 1 Urn 2 Veil

52 HMM组成 Markov链 （, A） 随机过程 （B） HMM的组成示意图 状态序列 观察值序列 q1, q2, ..., qT
o1, o2, ..., oT HMM的组成示意图

53 HMM的基本要素 用模型五元组 ＝（ N, M, π ，A，B）用来描述HMM，或简写为 =(π ，A，B) 参数 含义 实例 N 状态数目
缸的数目 M 每个状态可能的观察值数目 彩球颜色数目 A 与时间无关的状态转移概率矩阵 在选定某个缸的情况下，选择另一个缸的概率 B 给定状态下，观察值概率分布 每个缸中的颜色分布 p 初始状态空间的概率分布 初始时选择某口缸的概率

54 HMM可解决的问题 问题1：给定观察序列O=O1,O2,…OT,以及模型 , 如何计算P(O|λ)？
概率计算问题 问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列 S =q1,q2,…qT，使得S能够最为合理的解释观察序列O？ 预测问题 问题3：如何调整模型参数 使得P(O|λ)最大？ 学习问题

55 概率计算问题（朴素解法） 直接枚举所有可能的状态序列 N=5, M=100, => 计算量10^72
给定一个固定的状态序列S=(q1，q2，q3…) 表示在qt状态下观测到Ot的概率 概率加法法则 N=5, M=100, => 计算量10^72

56 前向算法 动态规划 递推 定义到时刻t，部分观测序列O1,O2,…Ot，且时刻t的状态为qt的概率为前向概率
利用状态序列的路径结构递推计算，将前向概率“推”往全局，从而避免重复计算 初始化： 递归： 终结：

57 前向法示意图 N=5, M=100, => 计算量3000 1 ... t t+1 ... qN atN . qi qj ati
aNj aij a1j at1 t t N=5, M=100, => 计算量3000

58 后向法 定义后向变量 初始化： 递归： 终结：

59 课堂测试 假设从三个箱子中取球，每个箱子中分别有红球、白球若干 状态转移概率矩阵A，观测概率矩阵B，初始状态概率矩阵π
T=3 观测序列{红，白，红}

60 课堂测试（续） 计算初值 递推计算 终止 a1(1)=0.2x0.5=0.1 a1(2)=0.4x0.4=0.16
a2(1)=(0.1x x x0.2)x0.5=0.077 a2(2)=(0.1x x x0.3)x0.6=0.1104 a2(3)= (0.1x x x0.5)x0.3=0.0606 a3(1)=(0.077x x x0.2)x0.5= a3(2)=(0.077x x x0.3)x0.4= a3(3)=(0.077x x x0.5)x0.7= 终止 P(O|λ)=a3(1)+a3(2)+a3(3)=

61 引申：其他概率的计算 给定模型和观测，在时刻t处于状态qi的概率 给定模型和观测，在时刻t处于状态qi，且在时刻t+1处于状态qj的概率

62 预测问题 近似算法 目标：对给定观测序列最可能的状态序列 近似：每个时刻选择最可能的状态
缺陷：不能保证整体是最可能的，因为有的状态转移是不可能出现的（概率为0） 最大

63 Viterbi算法 动态规划 状态序列=路径 最优路径原理：如果最优路径在时刻t通过节点s*，则从节点s*到终点的部分路径必然是最优的
递推：

64 Viterbi算法(续) 初始化： 递归： 终结： 求S序列： 记录下前一个节点

65 课堂测试 假设从三个箱子中取球，每个箱子中分别有红球、白球若干 状态转移概率矩阵A，观测概率矩阵B，初始状态概率矩阵π
T=3 观测序列{红，白，红}

66 课堂测试（续） 初始化 递归 回溯最优路径【倒】：3，3，3

67 学习算法 监督学习算法 非监督学习算法 训练数据中已知观测序列和对应的状态序列 利用极大似然估计
转移概率、观测概率、初始状态概率都可以使用频度的比率来计算 非监督学习算法 训练数据中已知观测序列，不知道对应的状态序列 由于人工标注耗时耗力，一般情况下非监督学习 EM算法（Baum-welch）

68 Baum-Welch算法 目的：给定观察值序列O，通过计算确定一个模型l ， 使得P(O| l)最大。 E步 M步
利用概率约束，拉格朗日乘子法求最大

69 Baum-Welch算法(续) 定义：

70 Baum-Welch算法(续2) 参数估计：