高级人工智能 第六章 概率推理 史忠植 中国科学院计算技术所 2019/1/10 史忠植 高级人工智能.

Presentation on theme: "高级人工智能 第六章 概率推理 史忠植 中国科学院计算技术所 2019/1/10 史忠植 高级人工智能."— Presentation transcript:

1 高级人工智能 第六章 概率推理 史忠植 中国科学院计算技术所 2019/1/10 史忠植 高级人工智能

2 内容提要 6.1概述 6.2贝叶斯概率基础 6.3贝叶斯学习理论 6.4简单贝叶斯学习模型 6.5贝叶斯网络的建造 6.6主动贝叶斯网络
6.7贝叶斯潜在语义模型 6.8贝叶斯网络的证据推理

3 贝叶斯网络是什么 贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。 贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。 2019/1/10 史忠植 高级人工智能

4 贝叶斯网络是什么 贝叶斯（Reverend Thomas Bayes ）学派奠基性的工作是贝叶斯的论文“关于几率性问题求解的评论”。或许是他自己感觉到它的学说还有不完善的地方，这一论文在他生前并没有发表，而是在他死后，由他的朋友发表的。著名的数学家拉普拉斯（Laplace P. S.）用贝叶斯的方法导出了重要的“相继律”，贝叶斯的方法和理论逐渐被人理解和重视起来。但由于当时贝叶斯方法在理论和实际应用中还存在很多不完善的地方，因而在十九世纪并未被普遍接受。 2019/1/10 史忠植 高级人工智能

5 贝叶斯网络是什么 二十世纪初，意大利的菲纳特（B. de Finetti）以及英国的杰弗莱（Jeffreys H.）都对贝叶斯学派的理论作出重要的贡献。第二次世界大战后，瓦尔德（Wald A.）提出了统计的决策理论，在这一理论中，贝叶斯解占有重要的地位；信息论的发展也对贝叶斯学派做出了新的贡献。1958年英国最悠久的统计杂志Biometrika全文重新刊登了贝叶斯的论文，20世纪50年代，以罗宾斯（Robbins H.）为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛注意，这一方法很快就显示出它的优点，成为很活跃的一个方向。 2019/1/10 史忠植 高级人工智能

6 贝叶斯网络是什么 随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯理论的内涵也比以前有了很大的变化。80年代贝叶斯网络用于专家系统的知识表示，90年代进一步研究可学习的贝叶斯网络，用于数据采掘和机器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物ISBA 2019/1/10 史忠植 高级人工智能

7 贝叶斯网络的应用领域 辅助智能决策 数据融合 模式识别 医疗诊断 文本理解 数据挖掘 2019/1/10 史忠植 高级人工智能

8 统计概率 统计概率:若在大量重复试验中，事件A发生的频率稳定地接近于一个固定的常数p，它表明事件A出现的可能性大小，则称此常数p为事件A发生的概率，记为P(A), 即 p＝P(A) 可见概率就是频率的稳定中心。任何事件A的概率为不大于1的非负实数，即 0＜P(A)＜1 2019/1/10 史忠植 高级人工智能

9 条件概率 条件概率:我们把事件B已经出现的条件下，事件A发生的概率记做为P(A|B)。并称之为在B出现的条件下A出现的条件概率，而称P(A)为无条件概率。 若事件A与B中的任一个出现，并不影响另一事件出现的概率，即当P(A)＝P(A·B)或P(B)＝P(B·A)时，则称A与B是相互独立的事件。 2019/1/10 史忠植 高级人工智能

10 加法定理 P(A+B)＝ P(A)＋P(B) 若A、B为两任意事件，则： P(A+B)＝P(A)＋P(B)－P(AB)
两个不相容(互斥)事件之和的概率,等于两个事件概率之和,即 P(A+B)＝ P(A)＋P(B) 若A、B为两任意事件，则： 　　　　P(A+B)＝P(A)＋P(B)－P(AB) 2019/1/10 史忠植 高级人工智能

11 乘法定理 设A、B为两个任意的非零事件，则其乘积的概率等于A(或B)的概率与在A(或B)出现的条件下B(或A)出现的条件概率的乘积。
　P(A·B)＝P(A)·P(B|A) 或 P(A·B)＝P(B)·P(A|B) 2019/1/10 史忠植 高级人工智能

12 贝叶斯网络定义 贝叶斯网络是表示变量间概率依赖关系的有向无环图，这里每个节点表示领域变量，每条边表示变量间的概率依赖关系，同时对每个节点都对应着一个条件概率分布表(CPT) ，指明了该变量与父节点之间概率依赖的数量关系。 2019/1/10 史忠植 高级人工智能

13 = P(A) P(S) P(T|A) P(L|S) P(B|S) P(C|T,L) P(D|T,L,B)
贝叶斯网的表示方法 贝叶斯网络是表示变量间概率依赖关系的有向无环图 P(D|T,L,B) P(B|S) P(S) P(C|T,L) P(L|S) P(A) P(T|A) Lung Cancer Smoking Chest X-ray Bronchitis Dyspnoea Tuberculosis Visit to Asia CPT: T L B D=0 D=1 ... P(A, S, T, L, B, C, D) = P(A) P(S) P(T|A) P(L|S) P(B|S) P(C|T,L) P(D|T,L,B) 条件独立性假设 有效的表示 2019/1/10 史忠植 高级人工智能

14 先验概率 先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。先验概率一般分为两类，一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。 2019/1/10 史忠植 高级人工智能

15 后验概率 后验概率一般是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率。 2019/1/10
史忠植 高级人工智能

16 联合概率 联合概率也叫乘法公式，是指两个任意事件的乘积的概率，或称之为交事件的概率。 2019/1/10 史忠植 高级人工智能

17 全概率公式 另有一事件B = BA1+BA2+…,+BAn A1 A3 An B A2 称满足上述条件的 A1,A2,…,An为完备事件组.
　 设A1,A2,…,An是两两互斥的事件，且P(Ai)>0， i =1,2,…,n, A1+A2+…,+An=Ω 另有一事件B = BA1+BA2+…,+BAn A1 A3 An B A2 称满足上述条件的 A1,A2,…,An为完备事件组. 2019/1/10 史忠植 高级人工智能

18 全概率 甲 乙 B A1 A2 P(B/A1)=0.01, P(B/A2)=0.02
例:某汽车公司下属有两个汽车制造厂,全部产品的40%由甲厂生产,60%由乙厂生产.而甲乙二厂生产的汽车的不合格率分别为1%,2%.求从公司生产的汽车中随机抽取一辆为不合品的概率. 解:设A1,A2分别表示{甲厂汽车} {乙厂汽车},B表示{不合格品} P(A1)=0.4, P(A2)=0.6 P(B/A1)=0.01, P(B/A2)=0.02 ∵A1A2=φ P(B)=P(A1B+A2B) =P(A1B)+P(A2B) =P(A1)P(B/A1)+P(A2)P(B/A2) =0.4× ×0.02 =0.016 甲 乙 B A1 A2 2019/1/10 史忠植 高级人工智能

19 全概率 诸Ai是原因 B是结果 由此可以形象地把全概率公式看成为 A3 A5 A1 B A4 A6 A2 A8 A7
“由原因推结果”，每个原因对结果的发生有一定的“作用”，即结果发生的可能性与各种原因的“作用”大小有关. 全概率公式表达了它们之间的关系 . A3 A5 A1 B A4 A6 A2 A8 A7 2019/1/10 史忠植 高级人工智能

20 贝叶斯公式 该公式于1763年由贝叶斯(Bayes)给出. 它是在观察到事件B已发生的条件下，寻找导致B发生的每个原因的概率.
　 设A1,A2,…,An是样本空间中的完备事件组且P(Ai)>0，i=1,2,…,n, 另有一事件B，则有 该公式于1763年由贝叶斯(Bayes)给出. 它是在观察到事件B已发生的条件下，寻找导致B发生的每个原因的概率. 2019/1/10 史忠植 高级人工智能

21 贝叶斯规则 å = p(B) A)p(A) | p(B B) p(A, p(A A2 A3 A4 A1 E = ) )p(A A | p(E
i ) )p(A A | p(E p(E) E) p(A A6 A5 基于条件概率的定义 p(Ai|E) 是在给定证据下的后验概率 p(Ai) 是先验概率 P(E|Ai) 是在给定Ai下的证据似然 p(E) 是证据的预定义后验概率 2019/1/10 史忠植 高级人工智能

22 贝叶斯网络的概率解释 任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力。完全的枚举需要指数级的规模（相对于领域变量个数）
贝叶斯网络提供了这种联合概率分布的紧凑表示：分解联合分布为几个局部分布的乘积： 从公式可以看出，需要的参数个数随网络中节点个数呈线性增长，而联合分布的计算呈指数增长。 网络中变量间独立性的指定是实现紧凑表示的关键。这种独立性关系在通过人类专家构造贝叶斯网中特别有效。 2019/1/10 史忠植 高级人工智能

23 简单贝叶斯学习模型 简单贝叶斯学习模型（Simple Bayes 或 Naïve Bayes ）将训练实例I分解成特征向量X和决策类别变量C。简单贝叶斯模型假定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作用于决策变量。尽管这一假定一定程度上限制了简单贝叶斯模型的适用范围，然而在实际应用中，不仅以指数级降低了贝叶斯网络构建的复杂性，而且在许多领域，在违背这种假定的条件下，简单贝叶斯也表现出相当的健壮性和高效性[111]，它已经成功地应用到分类、聚类及模型选择等数据挖掘的任务中。目前，许多研究人员正致力于改善特征变量间独立性的限制[54]，以使它适用于更大的范围。 2019/1/10 史忠植 高级人工智能

24 简单贝叶斯 Naïve Bayesian 结构简单－只有两层结构 推理复杂性与网络节点个数呈线性关系 2019/1/10
史忠植 高级人工智能

25 简单贝叶斯学习模型 设样本A表示成属性向量，如果属性对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积： ai是样本A的第i个属性
2019/1/10 史忠植 高级人工智能

26 简单贝叶斯学习模型 简单贝叶斯分类模型 这个过程称之为简单贝叶斯分类 (SBC: Simple Bayesian Classifier)。一般认为，只有在独立性假定成立的时候，SBC才能获得精度最优的分类效率；或者在属性相关性较小的情况下，能获得近似最优的分类效果。 2019/1/10 史忠植 高级人工智能

27 简单贝叶斯模型的提升 基于Boosting简单贝叶斯模型。
提升方法（Boosting）总的思想是学习一系列分类器，在这个序列中每一个分类器对它前一个分类器导致的错误分类例子给与更大的重视。尤其是，在学习完分类器Hk之后，增加了由Hk导致分类错误的训练例子的权值，并且通过重新对训练例子计算权值，再学习下一个分类器Hk+1。这个过程重复T次。最终的分类器从这一系列的分类器中综合得出。 2019/1/10 史忠植 高级人工智能

28 Boosting背景 来源于:PAC-Learning Model Valiant 1984 -11 提出问题:
强学习算法: 准确率很高的学习算法 弱学习算法: 准确率不高,仅比随机猜测略好 是否可以将弱学习算法提升为强学习算法 2019/1/10 史忠植 高级人工智能

29 Boosting背景 最初的boosting算法 Schapire 1989 AdaBoost算法
Freund and Schapire 1995 2019/1/10 史忠植 高级人工智能

30 Boosting 基本思想： Boosting也要求“不稳定”的分类方法 每个样本都赋予一个权重
2019/1/10 史忠植 高级人工智能

31 Boosting 过程: Set of weighted instances Classifier Ct
train classifier Set of weighted instances Classifier Ct adjust weights 2019/1/10 史忠植 高级人工智能

32 Boosting AdaBoost AdaBoost.M1 AdaBoost.M2 … 2019/1/10 史忠植 高级人工智能

33 AdaBoost 输入:(X1,Y1), (X2,Y2),…(Xn,Yn) Xi∈X, Yi∈Y={+1,-1} 初始化:D1(i)=1/n
For t=1,…,T 在Dt下训练, 得到弱的假设ht: X->{-1,+1}, 错误率:Εt=ΣDt(i) [ht(Xi)≠Yi] 选择αt=1/2 ln ( (1- Εt)/ Εt ), 更改权值: if ht(Xi)≠Yi , Dt+1(i)=Dt(i)* e αt /Zt if ht(Xi)=Yi , Dt+1(i)=Dt(i)* e -αt /Zt 输出:H(X)=sign( ∑ αtht(X) ) 2019/1/10 史忠植 高级人工智能

34 AdaBoost.M1 初始赋予每个样本相等的权重1/N ； For t = 1, 2, …, T Do
学习得到分类法Ct； 计算该分类法的错误率Et Et=所有被错误分类的样本的权重和； βt= Et/（1 - Et） 根据错误率更新样本的权重； 正确分类的样本： Wnew= Wold* βt 错误分类的样本： Wnew= Wold 调整使得权重和为1； 每个分类法Ct的投票价值为log [ 1 / βt ] 2019/1/10 史忠植 高级人工智能

35 AdaBoost training error
将γt=1/2-Et ; Freund and Schapire 证明: 最大错误率为: 即训练错误率随γt的增大呈指数级的减小. 2019/1/10 史忠植 高级人工智能

36 AdaBoost generalization error(1)
最大总误差: m : 样本个数 d : VC维 T : 训练轮数 Pr: 对训练集的经验概率 如果T值太大,Boosting会导致过适应（overfit） 2019/1/10 史忠植 高级人工智能

37 AdaBoost generalization error(2)
许多的试验表明: Boosting不会导致overfit 2019/1/10 史忠植 高级人工智能

38 AdaBoost generalization error(3)
解释以上试验现象; 样本(X,Y)的margin: margin(x,y)= αt=1/2 ln ( (1- Εt)/ Εt ) 较大的正边界表示可信度高的正确的预测 较大的负边界表示可信度高的错误的预测 2019/1/10 史忠植 高级人工智能

39 AdaBoost generalization error(4)
解释: 当训练误差降低后,Boosting继续提高边界,从而增大了最小边界,使分类的可靠性增加,降低总误差. 总误差的上界: 该公式与T无关 2019/1/10 史忠植 高级人工智能

40 Boosting其它应用 Boosting易受到噪音的影响; AdaBoost 可以用来鉴别异常; 具有最高权重的样本即为异常.
2019/1/10 史忠植 高级人工智能

41 PAC-Bayes 学习 现代学习理论大致可以分为两大类：贝叶斯推理和PAC（Probability Approximation Correct）学习。这两类学习算法都以训练数据集作为输入，经过学习，输出一个概念或模型；它们也都关联着相应的正确性定理：PAC学习对独立同分布的训练样本集提供了很好的性能保证，而贝叶斯正确性定理能保证充分地利用先验信息。结合这两类学习算法的优点，产生了PAC-Bayes学习理论。 David A Mcallester[1999] 给出了两个PAC-Bayes定理 Ralf Herbrich 等提出了贝叶斯点机理论 2019/1/10 史忠植 高级人工智能

42 构建贝叶斯网络 是表示变量间连结关系的有向无环图 贝叶斯网络的学习 基于评分函数的结构学习 结构学习 基于条件独立性检验的结构学习 参数学习
2019/1/10 史忠植 高级人工智能

43 构建贝叶斯网络 Bayesian Network Bayesian Network Bayesian Network Problem
Domain Bayesian Network Probability Elicitor Expert Knowledge Problem Domain Bayesian Network Learning Algorithm Training Data Problem Domain Bayesian Network Expert Knowledge Learning Algorithm Training Data 2019/1/10 史忠植 高级人工智能

44 贝叶斯概率(密度估计) 贝叶斯学习理论利用先验信息和样本数据来获得对未知样本的估计，而概率（联合概率和条件概率）是先验信息和样本数据信息在贝叶斯学习理论中的表现形式。如何获得这些概率（也称之为密度估计）是贝叶斯学习理论争议较多的地方。研究如何根据样本的数据信息和人类专家的先验知识获得对未知变量（向量）的分布及其参数的估计。它有两个过程：一是确定未知变量的先验分布；二是获得相应分布的参数估计。如果以前对所有信息一无所知，称这种分布为无信息先验分布；如果知道其分布求它的分布参数，称之为有信息先验分布。 2019/1/10 史忠植 高级人工智能

45 密度估计 先验分布的选取原则 共轭分布 杰弗莱原则 最大熵原则 2019/1/10 史忠植 高级人工智能

46 从数据中学习 共轭分布族 先验与后验属于同一分布族 预先给定一个似然分布形式 对于变量定义在0-1之间的概率分布，存在一个离散的样本空间
Beta 对应着 2 个似然状态 多变量 Dirichlet 分布对应 2个以上的状态 2019/1/10 史忠植 高级人工智能

47 共轭分布 设样本X1,X2, … ,Xn 对参数θ的条件分布为p（x1,x2, … , xn|θ），如果先验分布密度函数 决定的后验密度 与
Raiffa和Schaifeer提出先验分布应选取共轭分布，即要求后验分布与先验分布属于同一分布类型。它的一般描述为 : 设样本X1,X2, … ,Xn 对参数θ的条件分布为p（x1,x2, … , xn|θ），如果先验分布密度函数 决定的后验密度 与 同属于一种类型，则称 为p（x|θ）的共轭分布。 2019/1/10 史忠植 高级人工智能

48 杰弗莱原则 杰弗莱对于先验分布的选取做出了重大的贡献，它提出一个不变原理，较好地解决了贝叶斯假设中的一个矛盾，并且给出了一个寻求先验密度的方法。杰弗莱原则由两个部分组成：一是对先验分布有一合理要求；一是给出具体的方法求得适合于要求的先验分布。先验分布的选取原则 2019/1/10 史忠植 高级人工智能

49 最大熵原则 熵是信息论中描述事物不确定性的程度的一个概念。 如果一个随机变量只取与两个不同的值，比较下面两种情况： （1） （2）
很明显，（1）的不确定性要比（2）的不确定性小得多，而且从直觉上也可以看得出当取的两个值得概率相等时，不确定性达到最大。 2019/1/10 史忠植 高级人工智能

50 最大熵原则 设随机变量x是离散的，它取 至多可列个值，且 则 称为x的熵 对连续型随机变量x，它的概率密度函数为p(x)，若积分
有意义，称它为连续型随机变量的熵 2019/1/10 史忠植 高级人工智能

51 先验分布的选取－beta分布 x) (1 x m) (n (m) (n) n) m, | (x p - = G n m mean = 1)
variance + - = 2019/1/10 史忠植 高级人工智能

52 先验分布的选取－多项Dirichlet分布
N å G ( m ) i p (x | m , m ,..., m ) = i = 1 x m - 1 x m - 1 ...x m - 1 1 2 N Dirichlet 1 2 N G (m ) G (m )... G (m ) 1 2 N m mean of the i th state = i N å m i i = 1 N å m (1 - m / m ) i i i variance of the i th state = i = 1 N N å å m ( m + 1) i i i = 1 i = 1 2019/1/10 史忠植 高级人工智能

53 不完全数据的密度估计 期望最大化方法（Expectation Maximization EM）
Gibbs抽样（Gibbs Sampling GS） Bound and Collapse (BC) 2019/1/10 史忠植 高级人工智能

54 期望最大化方法 分为以下几个步骤： （1）含有不完全数据的样本的缺项用该项的最大似然估计代替；
（2）把第一步中的缺项值作为先验信息，计算每一缺项的最大后验概率，并根据最大后验概率计算它的理想值。 （3）用理想值替换（1）中的缺项。 （4）重复（1—3），直到两次相继估计的差在某一固定阀值内。 2019/1/10 史忠植 高级人工智能

55 Gibbs抽样 Gibbs抽样（Gibbs Sampling GS）
GS是最为流行的马尔科夫、蒙特卡罗方法之一。GS把含有不完全数据样本的每一缺项当作待估参数，通过对未知参数后验分布的一系列随机抽样过程，计算参数的后验均值的经验估计。 2019/1/10 史忠植 高级人工智能

56 贝叶斯网络的结构学习 基于搜索评分的方法: 基于依赖分析的方法: 初始化贝叶斯网络为孤立节点 使用启发式方法为网络加边
使用评分函数评测新的结构是否为更好 贝叶斯评分（Bayesian Score Metric） 基于墒的评分 最小描述长度MDL(Minimal Description Length) 重复这个过程，直到找不到更好的结构 基于依赖分析的方法: 通过使用条件独立性检验conditional independence (CI) 找到网络的依赖结构 2019/1/10 史忠植 高级人工智能

57 基于MDL的贝叶斯网结构学习 计算每一点对之间的互信息： 建立完全的无向图，图中的顶点是变量，边是变量之间的互信息 建立最大权张成树
根据一定的节点序关系，设置边的方向 2019/1/10 史忠植 高级人工智能

58 基于条件独立性的 贝叶斯网络学习 假定：节点序已知 第一阶段 (Drafting) 第二阶段 (Thickening)
计算每对节点间的互信息，建立完整的无向图. 第二阶段 (Thickening) 如果接点对不可能d-可分的话，把这一点对加入到边集中。 第三阶段 (Thinning) 检查边集中的每个点对，如果两个节点是d-可分的，那么移走这条边。 2019/1/10 史忠植 高级人工智能

59 基于条件独立性检验(CI)的 贝叶斯网络结构学习 1）初始化图结构B=<N,A,>,A=,R=,S=;
3）从S中取出第一个点对，并从S中删除这个元素，把该点对加入到边集A中； 4） 从S中剩余的点对中，取出第一个点对，如果这两各界点之间不存在开放路径，再把该点对加入A到中，否则加入到R中； 5）重复4),直到S为空； 6）从R中取出第一个点对； 7）找出该点对的某一块集，在该子集上做独立性检验，如果该点对的两个节点，仍然相互依赖，则加入到A中； 8） 重复6),直到R为空； 9） 对A中的每一条边，如果除这条边外，仍旧含有开放路径，则从A中临时移出，并在相应的块集上作独立性测试，如果仍然相关，则将其返回到A中，否则从A中删除这条边。 2019/1/10 史忠植 高级人工智能

60 树增广的朴素贝叶斯网 TAN的结构学习 2019/1/10 史忠植 高级人工智能

61 主动贝叶斯网络分类器 主动学习： 主动在候选样本集中选择测试例子，并将这些实例以一定的方式加入到训练集中。 选择策略 随机抽样 相关抽样
不确定性抽样 抽样选择 投票选择 2019/1/10 史忠植 高级人工智能

62 主动贝叶斯网络分类器 学习过程 输入：带有类别标注的样本集L，为带类别标注的候选样本集UL,选择停止标准e，每次从候选集中选择的样本个数M
输出：分类器C. 过程： While not e { TrainClassifer(L,C) //从L中学习分类器C； For each x计算ES； SelectExampleByES(S,UL,M,ES) //根据ES从UL中选择M个例子的子集S. LabeledAndAdd(S,L); //用当前的分类器C标注S中的元素，并把它加入到L中。 Remove(S,UL); //从UL中移走S. CheckStop(&e); //根据当前状态设置退出条件 } Return C; 2019/1/10 史忠植 高级人工智能

63 主动贝叶斯网络分类器 基于最大最小熵的主动学习
首先从测试样本中选择出类条件熵最大和最小的候选样本（MinExample, MaxExample），然后将这两个样本同时加入到训练集中。类条件熵最大的样本的加入，使得分类器能够对具有特殊信息的样本的及早重视；而类条件熵最小的样本是分类器较为确定的样本，对它的分类也更加准确，从而部分地抑制了由于不确定性样本的加入而产生的误差传播问题 2019/1/10 史忠植 高级人工智能

64 主动贝叶斯网络分类器 基于分类损失与不确定抽样相结合的主动学习 分类损失： 选择过程：
从测试样本中选择个熵较大的样本，组成集合maxS，然后对此集合中每个元素计算相对于该集合的分类损失和，选择分类损失和最小的样本做标注并加入到训练样本集中。 2019/1/10 史忠植 高级人工智能

65 主动贝叶斯网络分类器 ALearnerByMaxMinEntropy测试结果 ALearnerByUSandCL测试结果 初始标注
样本数：96 A B C D E F 精度评定(%) 精度 召回率 645 6 5 0.7670 0.9832 140 132 0.9429 0.4853 25 2 50 0.8475 0.6494 33 1 0.9167 0.8049 9 3 51 0.9623 0.8095 17 64 1.0000 0.7619 为标注训练 样本数：500 ALearnerByUSandCL测试结果 测试集 样本数：1193 A B C D E F 精度评定(%) 精度 召回率 641 11 4 0.8412 0.9771 81 191 0.8565 0.7022 8 21 48 0.8571 0.6234 6 2 32 1 0.9143 0.7273 9 3 51 0.9623 0.8095 17 64 1.0000 0.7619 2019/1/10 史忠植 高级人工智能

66 贝叶斯潜在语义模型 随着互联网的普及，网上信息正在呈指数级增长趋势。合理地组织这些信息，以便从茫茫的数据世界中，检索到期望的目标；有效地分析这些信息，以便从浩如烟海的信息海洋中，挖掘出新颖的、潜在有用的模式，正在成为网上信息处理的研究热点。网上信息的分类目录组织是提高检索效率和检索精度的有效途径，如在利用搜索引擎对网页数据进行检索时，如能提供查询的类别信息，必然会缩小与限制检索范围，从而提高查准率，同时，分类可以提供信息的良好组织结构，便于用户进行浏览和过滤信息。 2019/1/10 史忠植 高级人工智能

67 贝叶斯潜在语义模型 聚类分析是文本挖掘的主要手段之一。它的主要作用是：1）通过对检索结果的聚类，将检索到的大量网页以一定的类别提供给用户，使用户能快速定位期望的目标；2）自动生成分类目录；3）通过相似网页的归并，便于分析这些网页的共性。K-均值聚类是比较典型的聚类算法，另外自组织映射（SOM）神经网络聚类和基于概率分布的贝叶斯层次聚类（HBC）等新的聚类算法也正在不断的研制与应用中。然而这些聚类算法大部分是一种无监督学习，它对解空间的搜索带有一定的盲目性，因而聚类的结果一定程度上缺乏语义特征；同时，在高维情况下，选择合适的距离度量标准变得相当困难。而网页分类是一种监督学习，它通过一系列训练样本的分析，来预测未知网页的类别归属。目前已有很多有效的算法来实现网页的分类，如Naive Bayesian、SVM等。遗憾的是获得大量的、带有类别标注的样本的代价是相当昂贵的，而这些方法只有通过大规模的训练集才能获得较高精度的分类效果。 2019/1/10 史忠植 高级人工智能

68 贝叶斯潜在语义模型 Kamal Nigam 等人提出从带有类别标注和不带有类别标注的混合文档中分类Web网页，它只需要部分带有类别标注的训练样本，结合未标注样本含有的知识来学习贝叶斯分类器 通过引入贝叶斯潜在语义模型，首先将含有潜在类别主题变量的文档分配到相应的类主题中。接着利用简单贝叶斯模型，结合前一阶段的知识，完成对未含类主题变量的文档作标注。针对这两阶段的特点，我们定义了两种似然函数，并利用EM算法获得最大似然估计的局部最优解。这种处理方法一方面克服了非监督学习中对求解空间搜索的盲目性；另一方面它不需要对大量训练样本的类别标注，只需提供相应的类主题变量，把网站管理人员从繁琐的训练样本的标注中解脱出来，提高了网页分类的自动性。为了与纯粹的监督与非监督学习相区别，称这种方法为半监督学习算法。 2019/1/10 史忠植 高级人工智能

69 贝叶斯潜在语义分析BLSA—LSA ∑ → 向量的相似性 LSA 的应用 信息滤波 特征的相似性 文档索引 视频检索 2019/1/10
史忠植 高级人工智能

70 贝叶斯潜在语义分析BLSA 文档产生模型 产生如下的联合概率模型 以一定的概率选择文档 d 以一定的概率选择一潜在变量 z
以一定的概率产生特征 w 产生如下的联合概率模型 2019/1/10 史忠植 高级人工智能

71 贝叶斯潜在语义分析BLSA 目的在于估计下面的分布参数 最大化似然函数 2019/1/10 史忠植 高级人工智能

72 EM 算法求得最大似然 E步 M步 似然函数值与迭代步骤的关系 2019/1/10 史忠植 高级人工智能

73 贝叶斯潜在语义分析BLSA 半监督web挖掘算法(1) 算法描述: 已知： 求划分: 2019/1/10 史忠植 高级人工智能

74 半监督web挖掘算法(2) 解决策略： 1. 划分D为两个集和: 2. 使用 BLSA 标注 3. 使用Naive Bayesian标注
2019/1/10 史忠植 高级人工智能

75 半监督web挖掘算法(3) 1. 使用 BLSA 标注 1) 使用 BLSA估计分布参数 2) 使用最大后验概率标注文档 2019/1/10
史忠植 高级人工智能

76 半监督web挖掘算法(3) 2. 使用Naive Bayesian标注 似然 函数 E步: M步: 2019/1/10 史忠植 高级人工智能

77 半监督web挖掘算法(4) 1000 足球类文档 876 特征词 试验结果 2019/1/10 史忠植 高级人工智能

78 贝叶斯网中的证据推理 目的：通过联合概率分布公式，在给定的网络结构 和已知证据下，计算某一事件的发生的概率。 网络 推理 证据 E 查询 =
p(B) A)p(A) | p(B B) p(A, p(A 贝叶斯推理可以在反复使用贝叶斯规则而获得 2019/1/10 史忠植 高级人工智能

79 推理方法概述 NP Hard 精确推理 网络的拓扑结构是推理复杂性的主要原因； 当前的一些精确算法是有效地，能够解决现实中的大部分问题
由于对知识的认知程度，精确推理还存在一些问题 近似推理 证据的低似然性和函数关系 是近似推理中复杂性的主要原因 NP Hard 2019/1/10 史忠植 高级人工智能

80 影响推理的因素 网络结构的特征 网络的拓扑结构 相关查询的特征 证据的特征 网络的大小 网络中变量的类型（离散、连续） 变量的分布墒 任务
查询类型 （批处理、异步执行） 可用的计算资源（嵌入式系统、并行处理） 相关证据的特征 证据的特征 2019/1/10 史忠植 高级人工智能

81 查询的任务类型 预测 给定证据下的后验计算 最可能的假设 一个最可能的 决策策略 对给定的模型，将要发生什么 所有的边界后验 指定的边界后验
指定的联合条件查询 最可能的假设 一个最可能的 n 个最可能的 决策策略 2019/1/10 史忠植 高级人工智能

82 医疗诊断例子 贝叶斯推理中非条件分布和边界分布是常见的查询模式 一个节点的边界分布也称为该节点的信任函数 2019/1/10
史忠植 高级人工智能

83 推理过程中的信任传播 2019/1/10 史忠植 高级人工智能

84 推理算法 精确推理 近似推理 联合概率计算 前向模拟推理 Naïve Bayesian 图约简算法 随机模拟推理 Polytree算法
The algorithm’s purpose is “… fusing and propagating the impact of new evidence and beliefs through Bayesian networks so that each proposition eventually will be assigned a certainty measure consistent with the axioms of probability theory.” (Pearl, 1988, p 143) 2019/1/10 史忠植 高级人工智能

85 精确推理－计算联合概率 任何查询都可以通过联合概率回答 B 步骤： A 计算联合概率 P(AB)=P(A)*P(B|A)
边界化不在查询中的变量 P(B)=ΣAP(AB) 效率低 A 2019/1/10 史忠植 高级人工智能

86 图约简算法－一般原理 基本观点 任何概率查询可以表示成网络的子网，推理的目的是把网络分解成几个子网 三个基本操作
拟转弧操作（Arc Reversal）－贝叶斯公式 孤寡点移出(Barren node removal)－求和公式 值节点归并(Merge with Value node)－期望最大化 2019/1/10 史忠植 高级人工智能

87 约简算法－拟转弧操作 X1 X2 X1 X2 X3 X3 X1 X2 X1 X2 X3 X3
p(x1, x2, x3) = p(x3 | x1) p(x2 , x1) = p(x3 | x1) p(x1 | x2) p( x2) p(x1, x2, x3) = p(x3 | x1) p(x2 | x1) p(x1) X1 X2 X1 X3 X2 X3 p(x1, x2, x3) = p(x3, x2 | x1) p( x1) = p(x2 | x3, x1) p(x3 | x1) p( x1) p(x1, x2, x3) = p(x3 | x2, x1) p(x2) p( x1) 2019/1/10 史忠植 高级人工智能

88 约简算法－孤寡点移出 孤寡点－没有孩子的节点 2019/1/10 史忠植 高级人工智能

89 约简算法－值节点归并 值节点－证据节点或赋值节点 2019/1/10 史忠植 高级人工智能

90 Polytree算法－介绍 该算法由Pearl 于1982年首次提出 基本观点 计算边界后验的消息传递机制
Lambda 算子：消息向上传向父亲 pi 算子：消息向下传向孩子 2019/1/10 史忠植 高级人工智能

91 X Polytree算法－单连通网 定义： 在任何两个节点之间存在且仅存在一条路径（忽略方向） Multiple parents
and/or multiple children X 2019/1/10 史忠植 高级人工智能

92 单连通网的表示 p(y1|x1) p(y2|x1) . . . p(yn|x1)
p(y1|xm) p(y2|xm) p(yn|xm) y = x X 表示 m维随机向量; x 表示随机向量可能的取值 e 表示m维向量的一个取值 My|x 是条件概率p(y|x)的似然矩阵 Bel (x) = p(x|e) 表示随机向量的后验； f(x) × g(x) 表示向量的叉积 f(x)  g(x)表示向量的点积 是标准化常量 2019/1/10 史忠植 高级人工智能

93 概率的双向传播 e+ X Y Z e- 每个节点向儿子节点发送 pi 消息 (e+) 向父节点发送 lambda消息
Bel(Y) = p(y|e+, e-) =  (y)T × (y) 其中 (y) = p(y|e+), 先验证据 (y) = p(e-|y), 似然证据 (y) = x p(y|x, e+) × p(x| e+) = x p(y|x) × (x) = (x)  My|x (y) = z p(e-|y, z) × p(z| y) = z p(e-|z) × p(z| y) = z (z) × p(z| y) = Mz|y  (z) 2019/1/10 史忠植 高级人工智能

94 传播算法 对每个节点引入证据时，产生: 对接收 “p” or “l” 消息的每个节点: 沿着弧的方向传播一组 “p” 消息
节点修正它的“p”或 “l”，并发送到网络中 使用修正的“p”或 “l” ，更改结点的信任函数 BEL T BEL(t) p(t) l(t) U BEL(t) p(t) l(t) X BEL(t) p(t) l(t) Y BEL(t) p(t) l(t) Z BEL(t) p(t) l(t) Mu|t My|x 2019/1/10 史忠植 高级人工智能 Mx|u Mz|y

95 [ ] [ ] 实例－描述 Ch Di .8 .2 .1 .9 A1 A2 C1 C2 C3 .5 .4 .1 .1 .3 .6 B1 B2
p(A1) = 0.9 p(A2) = 0.1 M B|A = M C|B = A1 A2 A B C Ch Di [ ] A1 A2 B1 B2 C1 C2 C3 [ ] B1 B2 C1 C2 C3 2019/1/10 史忠植 高级人工智能

96 实例－算子设定 A B C (1) 初始化 lambda 算子为单位向量; Bel(A) =  (A) × (A)
(2) (B) = (A) MB|A; Bel(B) =  (B) × (B) (B) Bel(B) (B) B B (3) (C) = (B) MC|B; Bel(C) =  (C) × (C) (C) Bel(C) (C) C C C A B C 2019/1/10 史忠植 高级人工智能

97 实例－第一次传播 [ ] [ ] A B C t = p (lR) = .8 .2 t = l ( TR ) = . 5 1 .6
t = 1 (A) = (IR) (A) Bel(A) (A) A A (B) Bel(B) (B) B B (C) Bel(C) (C) C C C (C) = (TR) [ ] p (lR) = Intel. Rpt. A B C Troop Rpt. t = [ ] l T ( TR ) = . 5 1 .6 2019/1/10 史忠植 高级人工智能

98 实例－第二次传播 [ ] [ ] A B C t = p (lR) = .8 .2 t = l ( TR ) = . 5 1 .6
(A) Bel(A) (A) Paris Med t = 2 (B) = (A) MB|A (B) Bel(B) (B) B B (B) = MC|B (A) (C) Bel(C) (C) C C C [ ] p (lR) = Intel. Rpt. Troop A B C t = 2019/1/10 [ ] T l 史忠植 高级人工智能 ( TR ) = . 5 1 .6

99 实例－第三次传播 A B C (A) Bel(A) (A) A1 0.8 0.8 0.71 A2 0.2 0.2 0.71 t = 3
(A) = MB|A(B) (B) Bel(B) (B) B B (C) = (B) MC|B (C) Bel(C) (C) C C C Intel. Rpt. Troop A B C 2019/1/10 史忠植 高级人工智能

100 总结 贝叶斯网络是表示不确定性知识的一种有效方法 贝叶斯网络的参数学习与结构学习是比较活跃的研究领域
贝叶斯网络的推理能够计算出任何给定事件在给定条件下发生的可能性 贝叶斯网络具有广阔的应用前景。 2019/1/10 史忠植 高级人工智能

101 相关网址 http://www.cs.ucla.edu/judea/
2019/1/10 史忠植 高级人工智能

102 谢 谢! 2019/1/10 史忠植 高级人工智能