高级人工智能8111课件.pptx

1、高级人工智能高级人工智能第六章第六章 概率推理概率推理 史忠植史忠植 中国科学院计算技术研究所2023-1-231内容提要内容提要6.1概述 6.2贝叶斯概率基础6.3贝叶斯学习理论6.4简单贝叶斯学习模型6.56.5贝叶斯网络的建造贝叶斯网络的建造6.66.6主动贝叶斯网络主动贝叶斯网络6.7贝叶斯潜在语义模型6.8贝叶斯网络的证据推理贝叶斯网络的证据推理2023-1-232贝叶斯网络是什么贝叶斯网络是什么l贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。l贝叶斯方法正在以

2、其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。2023-1-233贝叶斯网络是什么贝叶斯网络是什么l贝叶斯（Reverend Thomas Bayes 1702-1761）学派奠基性的工作是贝叶斯的论文“关于几率性问题求解的评论”。或许是他自己感觉到它的学说还有不完善的地方，这一论文在他生前并没有发表，而是在他死后，由他的朋友发表的。著名的数学家拉普拉斯（Laplace P.S.）用贝叶斯的方法导出了重要的“相继律”，贝叶斯的方法和理论逐渐被人理解和重视起来。但由于当时贝叶斯方法在理论和实际应用中还存在很多不完善

3、的地方，因而在十九世纪并未被普遍接受。2023-1-234贝叶斯网络是什么贝叶斯网络是什么l二十世纪初，意大利的菲纳特（B.de Finetti）以及英国的杰弗莱（Jeffreys H.）都对贝叶斯学派的理论作出重要的贡献。第二次世界大战后，瓦尔德（Wald A.）提出了统计的决策理论，在这一理论中，贝叶斯解占有重要的地位；信息论的发展也对贝叶斯学派做出了新的贡献。1958年英国最悠久的统计杂志Biometrika全文重新刊登了贝叶斯的论文，20世纪50年代，以罗宾斯（Robbins H.）为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛注意，这一方法很快就显示出它的优点，成为很

4、活跃的一个方向。2023-1-235贝叶斯网络是什么贝叶斯网络是什么l随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯理论的内涵也比以前有了很大的变化。80年代贝叶斯网络用于专家系统的知识表示，90年代进一步研究可学习的贝叶斯网络，用于数据采掘和机器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物ISBA2023-1-236贝叶斯网络的应用领域贝叶斯网络的应用领域l辅助智能决策l数据融合l模式识别l医疗诊断

5、l文本理解l数据挖掘2023-1-237统计概率统计概率 统计概率:若在大量重复试验中，事件A发生的频率稳定地接近于一个固定的常数p，它表明事件A出现的可能性大小，则称此常数p为事件A发生的概率，记为P(A),即 pP(A)可见概率就是频率的稳定中心。任何事件A的概率为不大于1的非负实数，即 0P(A)1 2023-1-238条件条件概率概率 条件概率:我们把事件B已经出现的条件下，事件A发生的概率记做为P(A|B)。并称之为在B出现的条件下A出现的条件概率，而称P(A)为无条件概率。若事件A与B中的任一个出现，并不影响另一事件出现的概率，即当P(A)P(AB)或P(B)P(BA)时，则称A与

6、B是相互独立的事件。2023-1-239加法定理加法定理 两个不相容(互斥)事件之和的概率,等于两个事件概率之和,即 P(A+B)P(A)P(B)若A、B为两任意事件，则：P(A+B)P(A)P(B)P(AB)2023-1-2310乘法定理乘法定理 设A、B为两个任意的非零事件，则其乘积的概率等于A(或B)的概率与在A(或B)出现的条件下B(或A)出现的条件概率的乘积。P(AB)P(A)P(B|A)或 P(AB)P(B)P(A|B)2023-1-2311贝叶斯网络定义贝叶斯网络定义贝叶斯网络是表示变量间概率依赖关系的有向无环图，这里每个节点表示领域变量，每条边表示变量间的概率依赖关系，同时对每

7、个节点都对应着一个条件概率分布表(CPT)，指明了该变量与父节点之间概率依赖的数量关系。2023-1-2312贝叶斯网的表示方法贝叶斯网的表示方法=P(A)P(S)P(T|A)P(L|S)P(B|S)P(C|T,L)P(D|T,L,B)P(A,S,T,L,B,C,D)条件独立性假设有效的表示CPT:T L B D=0 D=10 0 0 0.1 0.90 0 1 0.7 0.30 1 0 0.8 0.20 1 1 0.9 0.1 .Lung CancerSmokingChest X-rayBronchitisDyspnoeaTuberculosisVisit to AsiaP(D|T,L,B)P

8、(B|S)P(S)P(C|T,L)P(L|S)P(A)P(T|A)贝叶斯网络是表示变量间概率依赖关系的有向无环图2023-1-2313先验概率先验概率 先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。先验概率一般分为两类，一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。2023-1-2314后验概率后验概率后验概率一般是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率。

9、2023-1-2315联合概率联合概率也叫乘法公式，是指两个任意事件的乘积的概率，或称之为交事件的概率。2023-1-2316 设设A1,A2,An是两两互斥的事件，且是两两互斥的事件，且P(Ai)0，i=1,2,n,A1+A2+,+An=niiiABPAPBP1)()()(全概率公式全概率公式A1A2A3AnB另有一事件另有一事件B=BA1+BA2+,+BAn称满足上述条件的称满足上述条件的A1,A2,An为为完备事件组完备事件组.2023-1-2317全概率全概率例例:某汽车公司下属有两个汽车制造厂某汽车公司下属有两个汽车制造厂,全部产品的全部产品的40%由甲厂由甲厂生产生产,60%由乙厂

10、生产由乙厂生产.而甲乙二厂生产的汽车的不合格率分别而甲乙二厂生产的汽车的不合格率分别为为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.40.01+0.60.02 =0.016甲甲乙乙BA1A22023-1-2318 由此可

11、以形象地由此可以形象地把全概率公式看成为把全概率公式看成为“由原因推结果由原因推结果”，每个原因对结果的发每个原因对结果的发生有一定的生有一定的“作用作用”，即结果发生的可能，即结果发生的可能性与各种原因的性与各种原因的“作作用用”大小有关大小有关.全概率全概率公式表达了它们之间公式表达了它们之间的关系的关系.诸诸Ai是原因是原因B是结果是结果A1A2A3A4A5A6A7A8B全概率全概率2023-1-2319njjjiiiABPAPABPAPBAP1)()()()()|(该公式于该公式于1763年由贝叶斯年由贝叶斯(Bayes)给出给出.它它是在观察到事件是在观察到事件B已发生的条件下，寻找

12、导已发生的条件下，寻找导致致B发生的每个原因的概率发生的每个原因的概率.贝叶斯公式贝叶斯公式 设设A1,A2,An是样本空间中的完备事件组是样本空间中的完备事件组且且P(Ai)0，i=1,2,n,另有一事件另有一事件B，则有则有 ni,212023-1-2320贝叶斯规则贝叶斯规则l基于条件概率的定义lp(Ai|E)是在给定证据下的后验概率lp(Ai)是先验概率lP(E|Ai)是在给定Ai下的证据似然lp(E)是证据的预定义后验概率iiiiiiii)p(AA|p(E)p(AA|p(Ep(E)p(AA|p(EE)|p(Ap(B)A)p(A)|p(Bp(B)B)p(A,B)|p(AA1A2A3A4

13、A5A6E2023-1-2321贝叶斯网络的概率解释贝叶斯网络的概率解释l任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力。完全的枚举需要指数级的规模（相对于领域变量个数）l贝叶斯网络提供了这种联合概率分布的紧凑表示：分解联合分布为几个局部分布的乘积：l从公式可以看出，需要的参数个数随网络中节点个数呈线性增长，而联合分布的计算呈指数增长。l网络中变量间独立性的指定是实现紧凑表示的关键。这种独立性关系在通过人类专家构造贝叶斯网中特别有效。iiinpaxPxxxP)|(),(212023-1-2322简单贝叶斯学习模型简单贝叶斯学习模型简单贝叶斯学习模型（Simple Baye

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

15、结构推理复杂性与网络节点个数呈线性关系2023-1-2324设样本A表示成属性向量，如果属性对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积：)|(*)|(*)|(21imiiCaPCaPCaP ai是样本A的第i个属性 简单贝叶斯学习模型简单贝叶斯学习模型2023-1-2325简单贝叶斯分类模型)|()()()|(1mjijiiCaPAPCPACP)|(ijCaP)(iCP这个过程称之为简单贝叶斯分类(SBC:Simple Bayesian Classifier)。一般认为，只有在独立性假定成立的时候，SBC才能获得精度最优的分类效率；或者在属性相关性较小的情况下，能获得近似最优

16、的分类效果。简单贝叶斯学习模型简单贝叶斯学习模型2023-1-2326基于Boosting简单贝叶斯模型。提升方法（Boosting）总的思想是学习一系列分类器，在这个序列中每一个分类器对它前一个分类器导致的错误分类例子给与更大的重视。尤其是，在学习完分类器Hk之后，增加了由Hk导致分类错误的训练例子的权值，并且通过重新对训练例子计算权值，再学习下一个分类器Hk+1。这个过程重复T次。最终的分类器从这一系列的分类器中综合得出。简单贝叶斯模型的提升简单贝叶斯模型的提升2023-1-2327BoostingBoosting背景背景l来源于:PAC-Learning Model Valiant 19

17、84-11l提出问题:l强学习算法:准确率很高的学习算法l弱学习算法:准确率不高,仅比随机猜测略好l是否可以将弱学习算法提升为强学习算法2023-1-2328BoostingBoosting背景背景l最初的boosting算法 Schapire 1989lAdaBoost算法 Freund and Schapire 19952023-1-2329Boostingconcepts(3)l弱学习机（weak learner):对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨l强学习机（strong learner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情

18、况：almost perfect expert)根据CNN,ABC,CBS以往的预测表现及实际天气情况作出综合准确的天气预测l弱学习机 强学习机Boosting2023-1-2330BoostingBoosting流程流程(loop1)(loop1)强学习机弱学习机原始训练集加权后的训练集加权后的假设X1?1:-1 弱假设2023-1-2331BoostingBoosting流程流程(loop2)(loop2)强学习机弱学习机原始训练集加权后的训练集加权后的假设Y3?1:-1 弱假设2023-1-2332BoostingBoosting流程流程(loop3)(loop3)强学习机弱学习机原始训

19、练集加权后的训练集加权后的假设Z7?1:-1弱假设2023-1-2333BoostingBoostingl过程:l在一定的权重条件下训练数据，得出分类法Ctl根据Ct的错误率调整权重Set of weightedinstances Classifier Ct train classifier adjust weights2023-1-2334流程描述流程描述lStep1:原始训练集输入，带有原始分布lStep2:给出训练集中各样本的权重lStep3:将改变分布后的训练集输入已知的弱学习机，弱学习机对每个样本给出假设lStep4:对此次的弱学习机给出权重lStep5:转到Step2,直到循环到达

20、一定次数或者某度量标准符合要求lStep6:将弱学习机按其相应的权重加权组合形成强学习机2023-1-2335核心思想核心思想l样本的权重l没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/Nl每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大，使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。l弱学习机的权重l准确率越高的弱学习机权重越高l循环控制：损失函数达到最小l在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。2023-1-2336简单问题演示（简单问题演示（BoostingBoosting

21、训练过程）训练过程）+-+-+-+-+-+-loop1Weak learner1(y=0.5)loop2Weak learner2(x=0.7)loop3Weak learner3(y=0.4)loop4Weak learner4(x=0.6)training set等概分布strong learnerw1*(y0.5?1:-1)+w2*(x0.7?1:-1)+w3*(y0.6?1:-1)2023-1-2337算法算法问题描述问题描述l训练集 (x1,y1),(x2,y2),(xN,yN)lxi Rm,yi -1,+1lDt 为第t次循环时的训练样本分布（每个样本在训练集中所占的概率，Dt总和

22、应该为1）lht:X-1,+1 为第t次循环时的Weak learner，对每个样本给出相应的假设，应该满足强于随机猜测：lwt为ht的权重l 为t次循环得到的Strong learner21),()(xhyPtDyxttiitiithwsignH1)()(2023-1-2338算法算法样本权重样本权重l思想：提高分错样本的权重l 反映了strong learner对样本的假设是否正确l采用什么样的函数形式？)(itiHywrongrightHyiti00)()(expitiHy2023-1-2339算法算法弱学习机权重弱学习机权重l思想：错误率越低，该学习机的权重应该越大l 为学习机的错误概

23、率l采用什么样的函数形式？和指数函数遥相呼应：)(),(xhyPtDyxtt tttw1ln212023-1-2340算法算法-Adaboost-AdaboostTtttttittitttttiiNNxhwsignxHZZxhwyiDiDwRhDTtNiDyxyxyx11111)()(:learner)(strongclassifier final Output thefactorion normalizat a is )(exp()()(Update Compute:learner Get weak usinglearner Train weak:,1For 1)(Initialize1,1

24、,where),(,),(:Given2023-1-2341AdaBoost.M1AdaBoost.M1l初始赋予每个样本相等的权重1/N；lFor t=1,2,T Do l学习得到分类法Ct；l计算该分类法的错误率Et Et=所有被错误分类的样本的权重和；lt=Et/（1-Et）l根据错误率更新样本的权重；正确分类的样本：Wnew=Wold*t 错误分类的样本：Wnew=Woldl调整使得权重和为1；l每个分类法Ct的投票价值为log 1/t 2023-1-2342AdaBoost Training ErrorAdaBoost Training Error24112ttttt22expl将t

25、=1/2-Et;lFreund and Schapire 证明:最大错误率为:l即训练错误率随t的增大呈指数级的减小.2023-1-2343AdaBoost Generalization Error(1)AdaBoost Generalization Error(1)l最大总误差:lm:样本个数ld:VC维lT:训练轮数lPr:对训练集的经验概率l如果T值太大,Boosting会导致过适应（overfit）)()(mTdOyxHpr2023-1-2344AdaBoost Generalization Error(2)AdaBoost Generalization Error(2)l许多的试验表

26、明:Boosting不会导致overfit2023-1-2345AdaBoost Generalization Error(3)AdaBoost Generalization Error(3)l解释以上试验现象;l样本(X,Y)的margin:margin(x,y)=lt=1/2 ln(1-t)/t)l较大的正边界表示可信度高的正确的预测l较大的负边界表示可信度高的错误的预测 xhyttt2023-1-2346AdaBoost Generalization Error(4)AdaBoost Generalization Error(4)l解释:当训练误差降低后,Boosting继续提高边界,从

27、而增大了最小边界,使分类的可靠性增加,降低总误差.l总误差的上界:l该公式与T无关)(),(arg(2mdOyxinmPr2023-1-2347BoostingBoosting其它应用其它应用lBoosting易受到噪音的影响;lAdaBoost 可以用来鉴别异常;具有最高权重的样本即为异常.2023-1-2348,ANB是表示变量间连结关系的有向无环图贝叶斯网络的学习结构学习参数学习基于评分函数的结构学习基于条件独立性检验的结构学习构建贝叶斯网络构建贝叶斯网络2023-1-2349构建贝叶斯网络构建贝叶斯网络BayesianNetworkBayesianNetworkBayesianNetw

28、orkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2023-1-2350贝叶斯概率贝叶斯概率(密度估计密度估计)贝叶斯学习理论利用先验信息和样本数据来获得对未知贝叶斯学习理论利用先验信息和样本数据来获得对未知样本的估计，而概率（联合概率和条件概率）是先验信样本的估计，而概率（联合概率和条件概率）是先验信息和样本数据信息在贝叶斯学习理论中的表现形式。如

29、息和样本数据信息在贝叶斯学习理论中的表现形式。如何获得这些概率（也称之为密度估计）是贝叶斯学习理何获得这些概率（也称之为密度估计）是贝叶斯学习理论争议较多的地方。研究如何根据样本的数据信息和人论争议较多的地方。研究如何根据样本的数据信息和人类专家的先验知识获得对未知变量（向量）的分布及其类专家的先验知识获得对未知变量（向量）的分布及其参数的估计。它有两个过程：一是确定未知变量的先验参数的估计。它有两个过程：一是确定未知变量的先验分布；二是获得相应分布的参数估计。如果以前对所有分布；二是获得相应分布的参数估计。如果以前对所有信息一无所知，称这种分布为无信息先验分布；如果知信息一无所知，称这种分布

30、为无信息先验分布；如果知道其分布求它的分布参数，称之为有信息先验分布。道其分布求它的分布参数，称之为有信息先验分布。2023-1-2351密度估计先验分布的选取原则共轭分布杰弗莱原则 最大熵原则2023-1-2352从数据中学习从数据中学习l共轭分布族l先验与后验属于同一分布族l预先给定一个似然分布形式l对于变量定义在0-1之间的概率分布，存在一个离散的样本空间lBeta 对应着 2 个似然状态l多变量 Dirichlet 分布对应 2个以上的状态2023-1-2353共轭分布共轭分布Raiffa和Schaifeer提出先验分布应选取共轭分布，即要求后验分布与先验分布属于同一分布类型。它的一般

31、描述为:设样本X1,X2,Xn 对参数的条件分布为p（x1,x2,xn|），如果先验分布密度函数决定的后验密度)(同属于一种类型，则称)|(x与)(为p（x x|）的共轭分布。)(2023-1-2354杰弗莱原则杰弗莱原则杰弗莱对于先验分布的选取做出了重大的贡献，它提出一个不变原理，较好地解决了贝叶斯假设中的一个矛盾，并且给出了一个寻求先验密度的方法。杰弗莱原则由两个部分组成：一是对先验分布有一合理要求；一是给出具体的方法求得适合于要求的先验分布。先验分布的选取原则2023-1-2355最大熵原则最大熵原则很明显，（1）的不确定性要比（2）的不确定性小得多，而且从直觉上也可以看得出当取的两个值

32、得概率相等时，不确定性达到最大。熵是信息论中描述事物不确定性的程度的一个概念。如果一个随机变量只取与两个不同的值，比较下面两种情况：98.0)(axp02.0)(axp（1）（2）45.0)(axp55.0)(axp2023-1-2356最大熵原则最大熵原则对连续型随机变量x，它的概率密度函数为p(x)，若积分 设随机变量x是离散的，它取至多可列个值，且kaaa21,iipaxp)(,2,1iiiippxHln)(则 称为x的熵)(xp)(xp)(xp)(xp)(xp)(ln)()(xpxpxH有意义，称它为连续型随机变量的熵 2023-1-23571)n(nm/n)m(1variancenm

33、meanx)(1xm)(n(m)(n)n)m,|(xp1mn1mBetaG GG GG G-10123400.511.5xp(x|m,n)m=1,n=2m=2,n=4m=10,n=20先验分布的选取先验分布的选取betabeta分布分布2023-1-2358先验分布的选取多项先验分布的选取多项DirichletDirichlet分布分布1)m(m)m/m(1mstate i theof variancemmstate i theofmean.xxx)(m).(m)(m)m()m,.,m,m|(xpN1iiN1iiN1iiiithN1iiith1m1-m1mN21N1iiN21Dirichlet

34、N21GGGG2023-1-2359不完全数据的密度估计不完全数据的密度估计期望最大化方法（Expectation Maximization EM）Gibbs抽样（Gibbs Sampling GS）Bound and Collapse(BC)2023-1-2360期望最大化方法期望最大化方法分为以下几个步骤：（1）含有不完全数据的样本的缺项用该项的最大似然估计代替；（2）把第一步中的缺项值作为先验信息，计算每一缺项的最大后验概率，并根据最大后验概率计算它的理想值。（3）用理想值替换（1）中的缺项。（4）重复（13），直到两次相继估计的差在某一固定阀值内。2023-1-2361GibbsGib

35、bs抽样抽样lGibbs抽样（Gibbs Sampling GS）GS是最为流行的马尔科夫、蒙特卡罗方法之一。GS把含有不完全数据样本的每一缺项当作待估参数，通过对未知参数后验分布的一系列随机抽样过程，计算参数的后验均值的经验估计。2023-1-2362贝叶斯网络的结构学习贝叶斯网络的结构学习l基于搜索评分的方法:l初始化贝叶斯网络为孤立节点l使用启发式方法为网络加边l使用评分函数评测新的结构是否为更好l 贝叶斯评分（Bayesian Score Metric）l 基于墒的评分l 最小描述长度MDL(Minimal Description Length)l重复这个过程，直到找不到更好的结构 l

36、基于依赖分析的方法:l通过使用条件独立性检验conditional independence(CI)找到网络的依赖结构2023-1-2363基于基于MDLMDL的贝叶斯网结构学习的贝叶斯网结构学习l计算每一点对之间的互信息：l建立完全的无向图，图中的顶点是变量，边是变量之间的互信息l建立最大权张成树l根据一定的节点序关系，设置边的方向yx,Pp(x)p(y)y)p(x,y)logP(x,Y)(X;I2023-1-2364基于条件独立性的贝叶斯网络学习基于条件独立性的贝叶斯网络学习l假定：节点序已知假定：节点序已知l第一阶段(Drafting)l计算每对节点间的互信息，建立完整的无向图.l第二阶

37、段(Thickening)l如果接点对不可能d-可分的话，把这一点对加入到边集中。l第三阶段(Thinning)l检查边集中的每个点对，如果两个节点是d-可分的，那么移走这条边。2023-1-2365基于条件独立性检验基于条件独立性检验(CI)(CI)的的贝叶斯网络结构学习贝叶斯网络结构学习1）初始化图结构B=,A=,R=,S=;2）对每一节点对，计算它们的互信息，并将互信息大于某一域值的节点对按互信息值的大小顺序加入到S中；3）从S中取出第一个点对，并从S中删除这个元素，把该点对加入到边集A中；4）从S中剩余的点对中，取出第一个点对，如果这两各界点之间不存在开放路径，再把该点对加入A到中，否

38、则加入到R中；5）重复4),直到S为空；6）从R中取出第一个点对；7）找出该点对的某一块集，在该子集上做独立性检验，如果该点对的两个节点，仍然相互依赖，则加入到A中；8）重复6),直到R为空；9）对A中的每一条边，如果除这条边外，仍旧含有开放路径，则从A中临时移出，并在相应的块集上作独立性测试，如果仍然相关，则将其返回到A中，否则从A中删除这条边。2023-1-2366树增广的朴素贝叶斯网树增广的朴素贝叶斯网TANTAN的结构学习的结构学习CAAjijijijijiCAPCAPCAAPCAAPCAAI,)|()|()|;(log)|;()|,(2023-1-2367主动贝叶斯网络分类器主动贝叶

39、斯网络分类器 主动学习：主动在候选样本集中选择测试例子，并将这些实例以一定的方式加入到训练集中。选择策略抽样选择投票选择随机抽样相关抽样不确定性抽样2023-1-2368主动贝叶斯网络分类器主动贝叶斯网络分类器 学习过程输入：带有类别标注的样本集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);/用

40、当前的分类器C标注S中的元素，并把它加入到L中。Remove(S,UL);/从UL中移走S.CheckStop(&e);/根据当前状态设置退出条件 Return C;2023-1-2369主动贝叶斯网络分类器主动贝叶斯网络分类器 基于最大最小熵的主动学习首先从测试样本中选择出类条件熵最大和最小的候选样本（MinExample,MaxExample），然后将这两个样本同时加入到训练集中。类条件熵最大的样本的加入，使得分类器能够对具有特殊信息的样本的及早重视；而类条件熵最小的样本是分类器较为确定的样本，对它的分类也更加准确，从而部分地抑制了由于不确定性样本的加入而产生的误差传播问题|1)|(ln(

41、)|()|(CiiixcpxcpxCH2023-1-2370主动贝叶斯网络分类器主动贝叶斯网络分类器 基于分类损失与不确定抽样相结合的主动学习xDDdxxpxcpxcpLL)()|(),|(分类损失：选择过程：从测试样本中选择个熵较大的样本，组成集合maxS，然后对此集合中每个元素计算相对于该集合的分类损失和，选择分类损失和最小的样本做标注并加入到训练样本集中。2023-1-2371主动贝叶斯网络分类器主动贝叶斯网络分类器 ABCDEF精度评定(%)精度召回率A645650000.76700.9832B14013200000.94290.4853C252500000.84750.6494D50

42、233100.91670.8049E90035100.96230.8095F170201641.00000.7619 ABCDEF精度评定(%)精度召回率A6411140000.84120.9771B8119100000.85650.7022C82148 000.85710.6234D60232100.91430.7273E90035100.96230.8095F170201641.00000.7619初始标注样本数：96未标注训练样本数：500测试集样本数：1193ALearnerByMaxMinEntropy测试结果 ALearnerByUSandCL测试结果 2023-1-2372贝叶斯

43、潜在语义模型贝叶斯潜在语义模型随着互联网的普及，网上信息正在呈指数级增长趋势。合随着互联网的普及，网上信息正在呈指数级增长趋势。合理地组织这些信息，以便从茫茫的数据世界中，检索到期理地组织这些信息，以便从茫茫的数据世界中，检索到期望的目标；有效地分析这些信息，以便从浩如烟海的信息望的目标；有效地分析这些信息，以便从浩如烟海的信息海洋中，挖掘出新颖的、潜在有用的模式，正在成为网上海洋中，挖掘出新颖的、潜在有用的模式，正在成为网上信息处理的研究热点。网上信息的分类目录组织是提高检信息处理的研究热点。网上信息的分类目录组织是提高检索效率和检索精度的有效途径，如在利用搜索引擎对网页索效率和检索精度的有

44、效途径，如在利用搜索引擎对网页数据进行检索时，如能提供查询的类别信息，必然会缩小数据进行检索时，如能提供查询的类别信息，必然会缩小与限制检索范围，从而提高查准率，同时，分类可以提供与限制检索范围，从而提高查准率，同时，分类可以提供信息的良好组织结构，便于用户进行浏览和过滤信息。信息的良好组织结构，便于用户进行浏览和过滤信息。2023-1-2373贝叶斯潜在语义模型贝叶斯潜在语义模型聚类分析是文本挖掘的主要手段之一。它的主要作用是：聚类分析是文本挖掘的主要手段之一。它的主要作用是：1 1）通过对检索结果的）通过对检索结果的聚类，将检索到的大量网页以一定的类别提供给用户，使用户能快速定位期望的聚类

45、，将检索到的大量网页以一定的类别提供给用户，使用户能快速定位期望的目标；目标；2 2）自动生成分类目录；）自动生成分类目录；3 3）通过相似网页的归并，便于分析这些网页的共）通过相似网页的归并，便于分析这些网页的共性。性。K-K-均值聚类是比较典型的聚类算法，另外自组织映射（均值聚类是比较典型的聚类算法，另外自组织映射（SOMSOM）神经网络聚类神经网络聚类和基于概率分布的贝叶斯层次聚类（和基于概率分布的贝叶斯层次聚类（HBCHBC）等新的聚类算法也正在不断的研制与等新的聚类算法也正在不断的研制与应用中。然而这些聚类算法大部分是一种无监督学习，它对解空间的搜索带有一应用中。然而这些聚类算法大部

46、分是一种无监督学习，它对解空间的搜索带有一定的盲目性，因而聚类的结果一定程度上缺乏语义特征；同时，在高维情况下，定的盲目性，因而聚类的结果一定程度上缺乏语义特征；同时，在高维情况下，选择合适的距离度量标准变得相当困难。而网页分类是一种监督学习，它通过一选择合适的距离度量标准变得相当困难。而网页分类是一种监督学习，它通过一系列训练样本的分析，来预测未知网页的类别归属。目前已有很多有效的算法来系列训练样本的分析，来预测未知网页的类别归属。目前已有很多有效的算法来实现网页的分类，如实现网页的分类，如Naive BayesianNaive Bayesian、SVMSVM等。遗憾的是获得大量的、带有类别

47、等。遗憾的是获得大量的、带有类别标注的样本的代价是相当昂贵的，而这些方法只有通过大规模的训练集才能获得标注的样本的代价是相当昂贵的，而这些方法只有通过大规模的训练集才能获得较高精度的分类效果。较高精度的分类效果。2023-1-2374贝叶斯潜在语义模型贝叶斯潜在语义模型 Kamal Nigam Kamal Nigam 等人提出从带有类别标注和不带有类别标注的混等人提出从带有类别标注和不带有类别标注的混合文档中分类合文档中分类WebWeb网页，它只需要部分带有类别标注的训练样本，网页，它只需要部分带有类别标注的训练样本，结合未标注样本含有的知识来学习贝叶斯分类器结合未标注样本含有的知识来学习贝叶

48、斯分类器 通过引入贝叶斯潜在语义模型，首先将含有潜在类别主题变量通过引入贝叶斯潜在语义模型，首先将含有潜在类别主题变量的文档分配到相应的类主题中。接着利用简单贝叶斯模型，结合前的文档分配到相应的类主题中。接着利用简单贝叶斯模型，结合前一阶段的知识，完成对未含类主题变量的文档作标注。针对这两阶一阶段的知识，完成对未含类主题变量的文档作标注。针对这两阶段的特点，我们定义了两种似然函数，并利用段的特点，我们定义了两种似然函数，并利用EM算法获得最大似算法获得最大似然估计的局部最优解。这种处理方法一方面克服了非监督学习中对然估计的局部最优解。这种处理方法一方面克服了非监督学习中对求解空间搜索的盲目性；

49、另一方面它不需要对大量训练样本的类别求解空间搜索的盲目性；另一方面它不需要对大量训练样本的类别标注，只需提供相应的类主题变量，把网站管理人员从繁琐的训练标注，只需提供相应的类主题变量，把网站管理人员从繁琐的训练样本的标注中解脱出来，提高了网页分类的自动性。为了与纯粹的样本的标注中解脱出来，提高了网页分类的自动性。为了与纯粹的监督与非监督学习相区别，称这种方法为半监督学习算法。监督与非监督学习相区别，称这种方法为半监督学习算法。2023-1-2375贝叶斯潜在语义模型贝叶斯潜在语义模型潜在语义分析（潜在语义分析（Latent Semantic Analysis:LSA）的基本观点是：把高维的向量

50、空间模型（的基本观点是：把高维的向量空间模型（VSM）表）表示中的文档映射到低维的潜在语义空间中。这个映射示中的文档映射到低维的潜在语义空间中。这个映射是通过对项是通过对项/文档矩阵文档矩阵 的奇异值分解（的奇异值分解（SVD）来实）来实现的。具体地说，对任意矩阵现的。具体地说，对任意矩阵 ，由线性代数的知，由线性代数的知识可知，它可分解为下面的形式：识可知，它可分解为下面的形式：nmNnmNTVUNVU,IVVUUTT12(,)kvdiag a aaavaaa,21是正交阵潜在语义分析通过取k个最大的奇异值，而将剩余的值设为零来近似 是对角阵为N的奇异值2023-1-2376TTUVUVNN