概率图模型研究进展综述

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],2013,24(11):2476−2497[doi:10.3724/SP.J.1001.2013.04486]©中国科学院软件研究所版权所有.Tel/Fax:[phone]概率图模型研究进展综述∗张宏毅1,2,王立威1,2,陈瑜希1,21(机器感知与智能教育部重点实验室(北京大学),北京100871)2(北京大学信息科学技术学院智能科学系,北京100871)通讯作者:张宏毅,E-mail:[e-mail]摘要:概率图模型作为一类有力的工具,能够简洁地表示复杂的概率分布,有效地(近似)计算边缘分布和条件分布,方便地学习概率模型中的参数和超参数.因此,它作为一种处理不确定性的形式化方法,被广泛应用于需要进行自动的概率推理的场合,例如计算机视觉、自然语言处理.回顾了有关概率图模型的表示、推理和学习的基本概念和主要结果,并详细介绍了这些方法在两种重要的概率模型中的应用.还回顾了在加速经典近似推理算法方面的新进展.最后讨论了相关方向的研究前景.关键词:概率图模型;概率推理;机器学习中图法分类号:TP181文献标识码:A中文引用格式:张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):2476−2497.英文引用格式:ZhangHY,WangLW,ChenYX.Researchprogressofprobabilisticgraphicalmodels:Asurvey.RuanJianXueBao/JournalofSoftware,2013,24(11):2476−2497(inChinese).:ASurveyZHANGHong-Yi1,2,WANGLi-Wei1,2,CHENYu-Xi1,21(KeyLaboratoryofMachinePerception(PekingUniversity),MinistryofEducation,Beijing100871,China)2(DepartmentofMachineIntelligence,SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)Correspondingauthor:ZHANGHong-Yi,E-mail:[e-mail]:Probabilisticgraphicalmodelsarepowerfultoolsforcompactlyrepresentingcomplexprobabilitydistributions,efficientlycomputing(approximate)marginalandconditionaldistributions,andconvenientlylearningparametersandhyperparametersinprobabilisticmodels.Asaresult,theyhavebeenwidelyusedinapplicationsthatrequiresomesortofautomatedprobabilisticreasoning,suchascomputervisionandnaturallanguageprocessing,asaformalapproachtodealwithuncertainty.Thispapersurveysthebasicconceptsandkeyresultsofrepresentation,inferenceandlearninginprobabilisticgraphicalmodels,anddemonstratestheirusesintwoimportantprobabilisticmodels.Italsoreviewssomerecentadvancesinspeedingupclassicapproximateinferencealgorithms,followedbyadiscussionofpromisingresearchdirections.Keywords:probabilisticgraphicalmodel;probabilisticreasoning;machinelearning我们工作和生活中的许多问题都需要通过推理来解决.通过推理,我们综合已有的信息,对我们感兴趣的未知量做出估计,或者决定采取某种行动.例如,程序员通过观察程序在测试中的输出判断程序是否有错误以及需要进一步调试的代码位置,医生通过患者的自我报告、患者体征、医学检测结果和流行病爆发的状态判断患者可能罹患的疾病.一直以来,计算机科学都在努力将推理自动化,例如,编写能够自动对程序进行测试并且诊断∗基金项目:国家自然科学基金(61222307,61075003)收稿时间:2013-07-17;修改时间:2013-08-02;定稿时间:2013-08-27张宏毅等:概率图模型研究进展综述2477错误位置的调试工具、能够辅助医生诊断患者病情的医疗诊断专家系统、理解英语文本的含义并将其转换为汉语的自动翻译系统、从机场监控视频中发现可疑人员的安全监控系统等等.人们设计出多种多样的方法来实现这些应用,其中,将知识陈述式地表示为概率模型,通过计算我们所关心变量的概率分布实现推理的途径具有独特优势:首先,它提供了一个描述框架,使我们能够将不同领域的知识抽象为概率模型,将各种应用中的问题都归结为计算概率模型里某些变量的概率分布,从而将知识表示和推理分离开来[1].模型的设计主要关心如何根据领域知识设计出反映问题本质的概率模型,同时兼顾有效推理的可行性,而推理算法的设计只需关心如何有效地在一般的或者特定的概率模型中进行推理.这种一定程度上的正交性极大地扩展了概率模型的应用,也加快了它的发展速度.其次,它能够评估未知量取值的可能性,对不同取值的概率给出量化的估计.这在涉及风险的决策系统中非常重要.另外,它常常具有良好的复用性.例如,我们不需要为预测父亲和儿子患上某种家族遗传病的概率分别设计算法,只需一个关于基因和表现型的家族遗传路径的概率模型,就能处理关于遗传病风险的各种推理问题.概率图模型就是一类描述这种陈述式表示的概率模型的建模和推理框架,它为简洁地表示、有效地推理和学习各种类型的概率模型提供了可能.在历史上,曾经有来自不同学科的尝试使用图的形式表示高维分布的变量间的相关关系的例子[2,3].在人工智能领域,概率方法始于构造专家系统的早期尝试[4,5].到20世纪80年代末,由于在贝叶斯网络和一般的概率图模型中进行推理的一系列重要进展[6,7],以及大规模专家系统的成功应用[8],以概率图模型为代表的概率方法重新受到了重视.如今,经过20余年的发展,概率图模型的推断和学习已广泛应用于机器学习、计算机视觉、自然语言处理、语音识别、专家系统、用户推荐、社交网络挖掘、生物信息学等研究领域的昀新成果中,成为人工智能相关研究中不可或缺的一门技术.概率图模型的研究方兴未艾,而且应用范围和研究热度仍在继续增长.本文首先介绍概率模型中的推断和学习问题的相关背景,并引入条件独立性这一重要概念;然后,根据研究主题依次综述概率图模型的表示、推理和学习问题核心内容的研究进展;我们还将介绍两种近年来有较大影响的概率图模型——条件随机场和主题模型,以说明概率图模型的表示、推理和学习这3个环节的联系;昀后,讨论关于大规模图模型的一些延伸主题,包括效率更高的推理算法、并行和分布式推理以及针对查询的推理问题.在本文中,我们将统一使用大写字母(例如A,X)表示随机变量,如未指明变量类型,则默认为离散变量;使用小写字母(例如x,y)表示随机变量的赋值;使用大写字母表示集合(例如A,X)或者某种数据结构(例如F,H).•推断问题多数与人工智能相关的应用所解决的问题都可以形式化地表述为概率模型中的推断问题.在推断问题中,目标是推断我们感兴趣的随机变量集合S中变量的取值分布,而我们采用生成式模型或判别式模型为问题建模,并运用一般的或针对具体模型的推断算法来计算这一分布.在生成式模型中,我们已知包含感兴趣变量集合在内的一些相互联系的变量的联合分布,以及其中可观测变量的观测值(或真实值),目标是以可观测变量为条件计算目标变量的条件概率.在判别式模型中,我们已知包含感兴趣变量集合S在内的一些相互联系的变量与另一些可观测变量之间的联系,即以可观测变量为条件的条件分布,以及可观测变量的观测值,目标同样是计算感兴趣变量集合S中的变量的条件概率.例如,在计算机视觉应用中,人们可能感兴趣一个图像区域所表示的物体类别;在自然语言处理应用中,人们可能感兴趣一句汉语文本的语法分析结果;而在用户推荐应用中,人们可能感兴趣某用户对某产品的喜好程度.这些来自不同领域的问题都可以表示成概率模型中的推断问题,并得到统一的处理.在以上描述中,要计算感兴趣变量的条件概率,需要知道感兴趣变量及其相关变量包含可观测变量的联合分布或以可观测变量为条件的条件分布.一般情况下,设全体随机变量的集合为S,感兴趣的变量集合为{X1,X2,…,Xn}=X⊂S,可观测变量集合为{O1,O2,…,Om}=O⊂S,其他变量的集合记为Y=S\(X∪O),则生成式模型确定了2478JournalofSoftware软件学报Vol.24,No.11,November2013联合分布P(X,Y,O),而判别式模型确定了条件分布P(X,Y|O).给定观测值,即O的一个赋值{o1,o2,…,om},在生成式模型中,我们需要使用概率求和规则消去Y中的变量,并重新归一化,得到条件概率分布P(X|O),在判别式模型中,我们只需求和消去Y中的变量即可.然而在实际的推断问题中,我们还要考虑到数据结构的表示开销和运算开销(时间和空间复杂度).假设在某模型中,每个变量可以有两种取值,如果我们简单地定义以上概率分布,并使用求和规则推断目标分布,容易验证时间开销和空间开销都至少是Ω(2|Y|).因此,我们必须寻找更紧凑的表示概率分布的数据结构以及能够在其中有效运行的推断算法.•学习问题推断问题研究如何在已有的模型基础上,根据观测计算目标变量的分布,并没有考虑如何构建模型的问题.一方面,模型可以由领域专家构建,模型的结构以及参数可以由专家根据经验来指定;另一方面,实际应用中可能需要对人类尚不了解的问题建立模型,或建立参数众多的大规模模型,或历史经验以数据的形式而不是人类知识存储等等,在这些情况下,模型的结构和参数并不适合人工指定,因此,我们希望设计算法从已往的数据中学习得到模型的参数和结构.从更一般的角度来讲,学习问题可以看作是推断问题的一类特例:我们感兴趣的随机变量是模型的参数或结构.因此,对学习问题的简单处理将会遇到与推断问题相同的困难,即表示和计算的时间和空间复杂度关于模型的变量数目都是指数级的,而我们需要能够处理实际应用数据规模的有效的学习算法.学习问题特有的困难在于:用于学习的训练样本通常是有限的,并且算法允许的训练时间也是有限的.当我们允许复杂的模型尝试从数据中估计联合分布的每一项概率时,我们将面对所谓的维数灾难.相对于呈指数增长的参数,样本量往往太少,以至于我们对真实分布的估计几乎必定有很大的误差.•条件独立考虑变量集A,B,C,如果P(A,B|C=c)=P(A|C=c)=P(B|C=c),∀c成立,我们就称以C为条件,变量