基本信息

编辑推荐
概率与逻辑的融合将为大数据的分析和处理提供一种新思路
内容简介
计算机书籍
概率逻辑程序是在逻辑程序的基础上增加对不确定性信息的表示。概率逻辑程序是以下两个用途广泛的领域交叉形成的:逻辑和概率的统一、概率程序。
逻辑用于表示实体之间的复杂关系,而概率论对构建属性和关系的不确定性模型有帮助。统一两个理论是一个非常活跃的研究领域。
概率逻辑程序与带知识表示能力的逻辑语言和带计算能力的图灵复杂语言类似,因此,它是两种语言的最佳组合。
由于概率逻辑程序的出现,越来越多的研究着开始关注它,并已产生了许多语言、推理和学习算法。
本书主要对该领域提供一个概要,同时介绍分布语义下的具体语言。本书主要介绍语义、推理、学习和他们之间的关系。
本书的许多例子和代码见网站http://cplint.eu。
作译者
研究人员一直致力于将逻辑学和机器学习两个领域联结起来,相关研究成果不断产生。如论文“Hybrid Probabilistic Programs”(混合概率程序)在2017年获得了逻辑程序协会颁发的“历经20年考验论文奖”(prize test-of-time, 20 years)。同年,Holger H.Hoos受邀在国际逻辑程序会议上作了题为“The best of both worlds: Machine learning meets logical reasoning”(两全其美:当机器学习遇到逻辑推理)的主题报告。报告中提到,可利用机器学习提升组合问题的启发式搜索效率,比如说借助SAT或ASP技术对组合问题进行编码。几个月后,在意大利人工智能协会(Italian Association for Artificial Intelligence,AI*IA)组织的一次专题讨论会中,机器学习领域的研究者Marco Gori提出了四个问题,这些问题包括:如何将庞大的知识库自然且有效地整合到学习过程中?如何打破机器学习和逻辑程序两个研究领域间的藩篱?如何推导出一个在符号化方法及其子领域中都可用的可计算学习和推理模型?如何学习到潜在的语义?Marco Gori认为,只有解决了上述基本问题,人工智能研究才可能有质的飞跃。同时,逻辑语言才能将结构化语义和统计推理结合到一起。
本书以Fabrizio Riguzzi和他的团队在该研究领域中15年来的优秀研究成果为基础,对前述问题和两个研究领域间的衔接问题进行了阐述和讨论。同时,对几种成熟、一致的概率逻辑程序设计语言进行了回顾。读者可以选择自行探究全部技术细节,或仅通过费拉拉(Ferrara)大学的Fabrizio团队维护的网站来运用这些逻辑程序语言而不必安装相应的编程工具。
本书的内容是自成一体的。书中首先对离散数学(通常作为逻辑推理基础部分)、连续数学、概率和统计(机器学习基础部分)等相关的预备知识作了详细介绍。尽管本书对所有的相关研究都进行了总结,但是作者对基于分布语义的研究进行了更为详尽的介绍。接下来讨论了随着程序(和数据)规模的增加,甚至在非标准推理(如概率推理)情形下,系统如何进行精确或近似的推理。之后介绍了参数学习和结构学习,这使得减小和消除与机器学习之间的距离成为可能。本书在结尾处提供了一个易读的章节,展示了一些概率逻辑程序的代码。拥有一些逻辑编程知识的读者可以先从这一章开始,该章中的测试程序都很有趣,比如,在Truel游戏(一个由三个枪手轮流射击的决斗游戏)中找出最佳策略,之后再过渡到其余的理论章节。
作为意大利逻辑程序协会(Italian Association for Logic Programming)的会长,我为我们的同事、前执行委员会成员取得的这一有意义的成就而感到自豪。我确信本书对于大数据时代的研究人员将会是十分有益的参考,可用来应对来自大数据推理的新挑战。
Agostino Dovier
乌迪内大学
目录
译者序
序言
前言
关于作译者
第1章 预备知识1
1.1 序、格和序数1
1.2 映射和不动点2
1.3 逻辑程序3
1.4 正规逻辑程序的语义8
1.4.1 程序完备化8
1.4.2 良基语义10
1.4.3 稳定模型语义13
1.5 概率论14
1.6 概率图模型21
第2章 概率逻辑程序语言27
2.1 基于分布语义的语言27
2.1.1 带标注析取的逻辑程序27
2.1.2 ProbLog28
2.1.3 概率Horn溯因28
前言
事实上,将逻辑与概率论相结合的尝试可追溯到20世纪50年代\[Carnap,1950;Gaifman,1964\]。但是,直到20世纪80年代后期到90年代初,当研究人员试图在人工智能领域中同时应用概率和逻辑两种方法时\[Nilsson,1986;Halpern,1990;Fagin & Halpern,1994;Halpern,2003],如何协调运用二者的问题才受到人们关注。
将逻辑和概率两种方法结合,即结合了前者表达实体间复杂关系的能力和后者对属性和实体上不确定性进行建模的能力。逻辑程序是一种基于逻辑的图灵完备语言,因而可作为结合逻辑和概率方法的一个非常合适的候选工具。
自概率逻辑程序诞生伊始,该领域的研究热度一直在稳步增长。研究人员提出了多种用于推理和学习的语言和算法。这些语言大致可分为两类:一类是使用分布语义(DS)的一种变体\[Sato,1995\]定义的语言;另一类则是使用知识库模型构造(KBMC)方法进行定义的语言\[Wellman et al.,1992;Bacchus,1993]。
在分布语义下,一个概率逻辑程序定义为一个正规逻辑程序上的概率分布。根据查询和程序的联合概率分布,可计算出基查询的概率。这类语言的代表有概率逻辑程序[Dantsin,1991],概率Horn溯因推理[Poole,1993b],PRISM\[Sato,1995],独立选择逻辑程序[Poole,1997],pD[Fuhr,2000],带标注析取的逻辑程序[Vennekens et al.,2004],ProbLog[De Raedt et al.,2007],P-log[Baral et al.,2009]和CP-logic[Vennekens et al.,2009]。
然而,在知识库模型构造语言中,一个程序被视为一个用于生成基图模型的模板,可以是贝叶斯网,也可以是马尔可夫网。这类语言的代表有关系贝叶斯网[Jaeger,1998],CLP(BN)[Costa et al.,2003],贝叶斯逻辑程序[Kersting & De Raedt,2001]和Prolog因式语言[Gomes & Costa,2012]。基于分布语义的逻辑程序能够转换成图模型,因此DS语言和KBMC语言的区别实际上并非泾渭分明。
本书旨在给出一个概率逻辑程序领域的概览,并且会重点关注基于分布语义的语言。这么做是由于这类语言中结合逻辑和概率的方法相当简单且具有跨语言的一致性,同时又能足够有效地应用于各种领域。此外,只使用纯粹的逻辑术语就能定义它们的语义,而并不需要转换为图模型。
但本书无意于对概率逻辑程序进行完整全面的介绍,即使是只针对基于分布语义的那类。因为自从关于概率逻辑程序的一个专门的研讨会系列在2014年启动之后,该领域的研究内容愈加广泛。我们的目的是介绍语义、推理和学习方面的主要思想,并且指出不同方法间的联系。
本书的目标受众是计算机科学和人工智能领域中希望了解概率逻辑程序概貌的研究人员,可作为本科生和研究生认识该领域的入门读物,也可作为想要了解各种方法内部运作细节的相关领域从业人员的参考材料。
书中的示例程序可通过SWISH网站中的cplint链接(http://cplint.eu)获取,通过它可在线运行代码[Riguzzi,et al.,2016a;Alberti,et al.,2017]。我们在费拉拉大学开发的这个系统包括了各种语言的推理和学习的算法。
本书第1章给出逻辑程序和图模型的基础知识。第2章介绍基于分布语义的概率逻辑程序语言,讨论了语义的基本形式,并将其与概率逻辑程序和人工智能中的其他语义进行比较。第3、4章描述复杂情形下,即带函数符号的语言和带连续随机变量的语言的语义。第5章给出各种精确推理算法。第6、7章分别讨论提升推理和近似推理。第8章描述非标准推理问题。随后的第9、10章分别对学习参数和程序结构问题进行阐述。第11章给出cplint系统的使用示例。第12章对全书进行总结,并对该领域的一些开放问题进行讨论。
致谢
感谢很多人给予的帮助与鼓励。Evelina Lamma和Paola Mello让我爱上逻辑推理,并且一直支持我,特别是在我最困难的时期。在费拉拉大学,与我的同事Elena Bellodi、Riccardo Zese、Giuseppe Cota、Marco Alberti、Marco Gavanelli和Arnaud Naguembang Fadja开展令人振奋的合作和有见地的讨论让我对PLP有了一定的认识和见解。我也足够幸运,能够与Theresa Swift、Nicola Di Mauro、Stefano Bragaglia、Vitor Santos Costa和Jan Wielemaker合作,书中的很多方法源于这些合作。
Agostino Dovier、Evelina Lamma、Elena Bellodi、Riccardo Zese、Giuseppe Cota和Marco Alberti阅读了本书的草稿并给我提出了很多有用的建议。
对很多启示性的想法,我也想感谢Michela Milano、Federico Chesani、Paolo Torroni、Luc De Deadt、Angelika Kimmig、Wannes Meert、Joost Vennekens和Kristian Kersting。
这本书是由很多文献演化而来的。特别是,第2章以文献[Riguzzi & Swift,2018]为基础,第3章以文献[Riguzzi,2016]为基础,5.6节以文献[Riguzzi & Swift,2010,2011,2013]为基础,5.9节以文献[Riguzzi,2014]为基础,7.2节以文献[Riguzzi,2013]为基础,第6章以文献[Riguzzi et al.,2017a]为基础,9.4节以文献[Bellodi & Riguzzi,2013,2012]为基础,10.2节以文献[Riguzzi,2004,2007b,2008b]为基础,10.5节以文献[Bellodi & Riguzzi,2015]为基础,第11章以文献[Riguzzi et al.,2016a;Alberti et al.,2017;Riguzzi et al.,2017b;Nguembang Fadja & Riguzze,2017]为基础。
最后,我想特别感谢我的妻子Cristina,感谢她容忍我放弃休假去写一本书。没有她的支持,我不可能写完这本书。
序言
研究人员一直致力于将逻辑学和机器学习两个领域联结起来,相关研究成果不断产生。如论文“Hybrid Probabilistic Programs”(混合概率程序)在2017年获得了逻辑程序协会颁发的“历经20年考验论文奖”(prize test-of-time, 20 years)。同年,Holger H.Hoos受邀在国际逻辑程序会议上作了题为“The best of both worlds: Machine learning meets logical reasoning”(两全其美:当机器学习遇到逻辑推理)的主题报告。报告中提到,可利用机器学习提升组合问题的启发式搜索效率,比如说借助SAT或ASP技术对组合问题进行编码。几个月后,在意大利人工智能协会(Italian Association for Artificial Intelligence,AI*IA)组织的一次专题讨论会中,机器学习领域的研究者Marco Gori提出了四个问题,这些问题包括:如何将庞大的知识库自然且有效地整合到学习过程中?如何打破机器学习和逻辑程序两个研究领域间的藩篱?如何推导出一个在符号化方法及其子领域中都可用的可计算学习和推理模型?如何学习到潜在的语义?Marco Gori认为,只有解决了上述基本问题,人工智能研究才可能有质的飞跃。同时,逻辑语言才能将结构化语义和统计推理结合到一起。
本书以Fabrizio Riguzzi和他的团队在该研究领域中15年来的优秀研究成果为基础,对前述问题和两个研究领域间的衔接问题进行了阐述和讨论。同时,对几种成熟、一致的概率逻辑程序设计语言进行了回顾。读者可以选择自行探究全部技术细节,或仅通过费拉拉(Ferrara)大学的Fabrizio团队维护的网站来运用这些逻辑程序语言而不必安装相应的编程工具。
本书的内容是自成一体的。书中首先对离散数学(通常作为逻辑推理基础部分)、连续数学、概率和统计(机器学习基础部分)等相关的预备知识作了详细介绍。尽管本书对所有的相关研究都进行了总结,但是作者对基于分布语义的研究进行了更为详尽的介绍。接下来讨论了随着程序(和数据)规模的增加,甚至在非标准推理(如概率推理)情形下,系统如何进行精确或近似的推理。之后介绍了参数学习和结构学习,这使得减小和消除与机器学习之间的距离成为可能。本书在结尾处提供了一个易读的章节,展示了一些概率逻辑程序的代码。拥有一些逻辑编程知识的读者可以先从这一章开始,该章中的测试程序都很有趣,比如,在Truel游戏(一个由三个枪手轮流射击的决斗游戏)中找出最佳策略,之后再过渡到其余的理论章节。
作为意大利逻辑程序协会(Italian Association for Logic Programming)的会长,我为我们的同事、前执行委员会成员取得的这一有意义的成就而感到自豪。我确信本书对于大数据时代的研究人员将会是十分有益的参考,可用来应对来自大数据推理的新挑战。
Agostino Dovier
乌迪内大学
媒体评论
逻辑用于表示实体之间的复杂关系,而概率论对构建属性和关系的不确定性模型有帮助。统一这两个理论是非常有价值的。
概率逻辑程序与带知识表示能力的逻辑语言和带计算能力的图灵复杂语言类似,它是两种语言的完美组合。
越来越多的研究者开始关注概率逻辑程序,并已产生了许多语言、推理和学习算法。
本书主要对该领域提供一个概要,同时介绍分布语义下的具体语言,主要介绍语义、推理、学习和它们之间的关系。
作者简介
法布里奇奥·里古齐(Fabrizio Riguzzi) 是费拉拉大学数学与计算机科学系计算机科学专业副教授,并兼任意大利人工智能协会副主席、官方杂志Intelligenza Artificiale主编。他在机器学习、归纳逻辑程序设计和统计关系学习等领域发表论文150余篇。他致力于开发一个能将人工智能、逻辑和统计进行融合的智能系统。