论文部分内容阅读
摘要：站在人工智能角度，从局部化信念修正和Horn信念修正这两个目前的热点，阐述信念修正理论的新世纪研究动态。
关键词：人工智能；信念；修正
中图分类号：TP18 文献标识码：A 文章编号：1007-9599 （2012） 15-0000-02
众所周知，人或智能体的信念随着新信念的获取而不断发生变化。当人或智能体获得新信念时，新获取的信念可能与原有信念产生矛盾。通常认为新获取的信念是正确的，需要放弃部分原有信念使之保持整体信念协调。当放弃部分原有信念时，哪些原有信念被放弃？这个过程满足哪些准则呢？这就是引入信念修正的动机[1-2]。AGM模型[1]是信念修正的开创性工作。信念修正具有很强的现实背景，与更新有关的问题几乎都能看见信念修正的影子，常常可见将信念修正的思想应用到其它学科进行科学研究，如：在研究协商问题中引入信念修正的思想形成了基于逻辑的协商问题研究[3-5]。信念修正是人工智能、数据库理论和哲学逻辑研究中的重要课题，与计算机软件理论的多个学科有广泛的联系，比如：被广泛应用到计算机软件理论的开放逻辑等[6]，它们与信念修正理论有紧密联系[7]。
信念修正是人工智能、数据库理论以及哲学逻辑研究的热点问题。寻找高速有效的算法一直是信念修正理论及其应用的研究重点。信念修正算子的计算及复杂性问题是信念修正研究的核心问题。Eiter和 Gottlob等围绕几类特殊的信念修正算子率先展开研究，获得了开创性成果[8]，该方面研究迅速成为研究者近年来关注的热点问题[8-11]。信念修正算子较高的复杂性使得它的应用受到限制，寻找高效的算法一直是信念修正研究的一个重点主题。一条路径是采用命题逻辑的适当子语言以降低计算信念修正算子的复杂性。如2008年Delgrande和Langlois等利用Horn公式具有较低计算复杂的特性，分别从信念紧缩和信念修正两个方面对基于Horn语言的信念修正进行了开创性研究[12-13]，这使得Horn信念修正研究迅速成为重要国际会议关注的新热点[12-16]。另一条路径是在不降低描述语言能力的前提下，采用局部化的思想对知识表示语言进行适当处理以降低信念修正算子的计算复杂性，如：基于分离的局部化技术。Parikh提出了命题信念集的分离概念[17]，形成相关性准则（即‘无关’信念不会受到信念修正过程影响）。基于分离的局部化思想和方法不但具有较强的现实背景，而且能降低信念修正的计算复杂性，为越来越多的研究者所重视[17-24]。
如上信念修正研究表明：未来数年，信念修正研究仍将围绕降低复杂性进行。作者预测如下的方向将会成为小热点（由于本人水平有限，望读者批评指正）。
（1）继续深入Horn信念修正研究，主要关注Horn信念修正的修正算子和紧缩算子的联系；计算复杂性较好的特殊Horn修正算子研究；利用Horn语言计算性较好的性质设计求解器以及Horn信念修正的应用等工作。
（2）继续深入局部化信念修正研究，主要关注各种局部化信念修正的理论；计算局部化的算法及复杂性；重复的局部化信念修正等工作。
参考文献：
[1]C. Alchouron， P. Gardenfors， and D. Makinson， On the logic of theory change： partial meet contraction and revision functions， J. Symb. Log.，50：510-530，1985.
[2]S. Hansson，logic of belief revision，
http：//plato.stanford.edu/entries/logic-belief-revision/
[3]D. Zhang， N. Foo， T. Meyer and R. Kwok， Negotiation as mutual belief revision， AAAI-04： 317-322， 2004.
[4]D. Zhang， A logic-based axiomatic model of bargaining. Artif. Intell. 174（16-17）： 1307-1322， 2010.
[5]W. Chen， M. Zhang， and M. Wu， A Logic-Program Based Negotiation Mechanism，JCST，24（4）：753-760， 2009.
[6]李未， 一个开放的逻辑系统 中国科学A辑， 1992（10）： 1103-1113， 1992
[7]张东摩，顾红芳，陈世福，信念修正与开放逻辑之间的关系.航空学报， 20（2）：118-121， 1999
[8] T. Eiter and G. Gottlob， On the complexity of propositional knowledge base revision， updates， and counterfactuals. Artif. Intell. 57（2-3）： 227-270， 1992.
[9] B. Nebel. How hard is it to revise a belief base？ In Volume 3 of Handbook of Defeasible Reasoning and Uncertainty Management Systems，1996
[10]罗杰，李未.一个在Horn子句中求解极大缩减的算法，中国科学：信息科学，2011（2）：244-257，2011.
[11]T. Eiter， G. Gottlob， The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions. IJCAI-93：526-533， 1993. [12]J. P. Delgrande， Horn clause belief change： Contraction functions. KR-08， 156–165， 2008.
[13]M. Langlois， R. H.Sloan， B. Szorenyi and G. Turan， Horn complements： Towards Horn-to-Horn belief revision. AAAI-08： 466-471， 2008.
[14]J. P. Delgrande and R. Wassermann， Horn clause contraction functions： Belief set and belief base approaches. KR-10：143-152， 2010.
[15]R. Booth， T. Meyer and J. Varzinczak， Next steps in propositional Horn contraction.IJCAI-09：702-707， 2009.
[16]M. Wu， D. Zhang and M. Zhang， Language Splitting and Relevance-Based Belief Change in Horn Logic， AAAI-2011：268-273， 2011.
[17]R.Parikh， Beliefs， belief revision， and splitting languages. Logic， language and computation.2：266-278， CSLI Publications， 1999.
[18]R. Parikh， Beth definability， interpolation and language splitting，Synthese 179（2）：211-221， 2011.
[19]B. Yang， Y. Zhang， M. Zhang， M. Wu， Splitting Computation of Answer Set Program and Its Application on E-service， IJCIS 4（5）：977-990，2011.
[20]M. Wu and M. Zhang， Algorithms and application in decision-making for the finest splitting of a set of formulae， KBS， 23（1）： 70-76， 2010.
[21]M. Wu， Z. Zhu， M. Zhang. Partial Meet Contraction Based on Relevance Criterion. IMECS2008：7-12， 2008.
[22]G. Kourousias and D. Makinson， Parallel interpolation， splitting， and relevance in belief change， J. of Symbolic Logic 72 （3）：994-1002， 2007.
[23]P. Peppas， S. Chopra and N. Foo， Distance semantics for relevance-sensitive belief revision， KR2004：319-328， 2004.
[24]S. Chopra and R. Parikh， Relevance sensitive belief structures. Ann. Math. Artif. Intell. 28：259-285，2000.
关键词：人工智能；信念；修正
中图分类号：TP18 文献标识码：A 文章编号：1007-9599 （2012） 15-0000-02
众所周知，人或智能体的信念随着新信念的获取而不断发生变化。当人或智能体获得新信念时，新获取的信念可能与原有信念产生矛盾。通常认为新获取的信念是正确的，需要放弃部分原有信念使之保持整体信念协调。当放弃部分原有信念时，哪些原有信念被放弃？这个过程满足哪些准则呢？这就是引入信念修正的动机[1-2]。AGM模型[1]是信念修正的开创性工作。信念修正具有很强的现实背景，与更新有关的问题几乎都能看见信念修正的影子，常常可见将信念修正的思想应用到其它学科进行科学研究，如：在研究协商问题中引入信念修正的思想形成了基于逻辑的协商问题研究[3-5]。信念修正是人工智能、数据库理论和哲学逻辑研究中的重要课题，与计算机软件理论的多个学科有广泛的联系，比如：被广泛应用到计算机软件理论的开放逻辑等[6]，它们与信念修正理论有紧密联系[7]。
信念修正是人工智能、数据库理论以及哲学逻辑研究的热点问题。寻找高速有效的算法一直是信念修正理论及其应用的研究重点。信念修正算子的计算及复杂性问题是信念修正研究的核心问题。Eiter和 Gottlob等围绕几类特殊的信念修正算子率先展开研究，获得了开创性成果[8]，该方面研究迅速成为研究者近年来关注的热点问题[8-11]。信念修正算子较高的复杂性使得它的应用受到限制，寻找高效的算法一直是信念修正研究的一个重点主题。一条路径是采用命题逻辑的适当子语言以降低计算信念修正算子的复杂性。如2008年Delgrande和Langlois等利用Horn公式具有较低计算复杂的特性，分别从信念紧缩和信念修正两个方面对基于Horn语言的信念修正进行了开创性研究[12-13]，这使得Horn信念修正研究迅速成为重要国际会议关注的新热点[12-16]。另一条路径是在不降低描述语言能力的前提下，采用局部化的思想对知识表示语言进行适当处理以降低信念修正算子的计算复杂性，如：基于分离的局部化技术。Parikh提出了命题信念集的分离概念[17]，形成相关性准则（即‘无关’信念不会受到信念修正过程影响）。基于分离的局部化思想和方法不但具有较强的现实背景，而且能降低信念修正的计算复杂性，为越来越多的研究者所重视[17-24]。
如上信念修正研究表明：未来数年，信念修正研究仍将围绕降低复杂性进行。作者预测如下的方向将会成为小热点（由于本人水平有限，望读者批评指正）。
（1）继续深入Horn信念修正研究，主要关注Horn信念修正的修正算子和紧缩算子的联系；计算复杂性较好的特殊Horn修正算子研究；利用Horn语言计算性较好的性质设计求解器以及Horn信念修正的应用等工作。
（2）继续深入局部化信念修正研究，主要关注各种局部化信念修正的理论；计算局部化的算法及复杂性；重复的局部化信念修正等工作。
参考文献：
[1]C. Alchouron， P. Gardenfors， and D. Makinson， On the logic of theory change： partial meet contraction and revision functions， J. Symb. Log.，50：510-530，1985.
[2]S. Hansson，logic of belief revision，
http：//plato.stanford.edu/entries/logic-belief-revision/
[3]D. Zhang， N. Foo， T. Meyer and R. Kwok， Negotiation as mutual belief revision， AAAI-04： 317-322， 2004.
[4]D. Zhang， A logic-based axiomatic model of bargaining. Artif. Intell. 174（16-17）： 1307-1322， 2010.
[5]W. Chen， M. Zhang， and M. Wu， A Logic-Program Based Negotiation Mechanism，JCST，24（4）：753-760， 2009.
[6]李未， 一个开放的逻辑系统 中国科学A辑， 1992（10）： 1103-1113， 1992
[7]张东摩，顾红芳，陈世福，信念修正与开放逻辑之间的关系.航空学报， 20（2）：118-121， 1999
[8] T. Eiter and G. Gottlob， On the complexity of propositional knowledge base revision， updates， and counterfactuals. Artif. Intell. 57（2-3）： 227-270， 1992.
[9] B. Nebel. How hard is it to revise a belief base？ In Volume 3 of Handbook of Defeasible Reasoning and Uncertainty Management Systems，1996
[10]罗杰，李未.一个在Horn子句中求解极大缩减的算法，中国科学：信息科学，2011（2）：244-257，2011.
[11]T. Eiter， G. Gottlob， The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions. IJCAI-93：526-533， 1993. [12]J. P. Delgrande， Horn clause belief change： Contraction functions. KR-08， 156–165， 2008.
[13]M. Langlois， R. H.Sloan， B. Szorenyi and G. Turan， Horn complements： Towards Horn-to-Horn belief revision. AAAI-08： 466-471， 2008.
[14]J. P. Delgrande and R. Wassermann， Horn clause contraction functions： Belief set and belief base approaches. KR-10：143-152， 2010.
[15]R. Booth， T. Meyer and J. Varzinczak， Next steps in propositional Horn contraction.IJCAI-09：702-707， 2009.
[16]M. Wu， D. Zhang and M. Zhang， Language Splitting and Relevance-Based Belief Change in Horn Logic， AAAI-2011：268-273， 2011.
[17]R.Parikh， Beliefs， belief revision， and splitting languages. Logic， language and computation.2：266-278， CSLI Publications， 1999.
[18]R. Parikh， Beth definability， interpolation and language splitting，Synthese 179（2）：211-221， 2011.
[19]B. Yang， Y. Zhang， M. Zhang， M. Wu， Splitting Computation of Answer Set Program and Its Application on E-service， IJCIS 4（5）：977-990，2011.
[20]M. Wu and M. Zhang， Algorithms and application in decision-making for the finest splitting of a set of formulae， KBS， 23（1）： 70-76， 2010.
[21]M. Wu， Z. Zhu， M. Zhang. Partial Meet Contraction Based on Relevance Criterion. IMECS2008：7-12， 2008.
[22]G. Kourousias and D. Makinson， Parallel interpolation， splitting， and relevance in belief change， J. of Symbolic Logic 72 （3）：994-1002， 2007.
[23]P. Peppas， S. Chopra and N. Foo， Distance semantics for relevance-sensitive belief revision， KR2004：319-328， 2004.
[24]S. Chopra and R. Parikh， Relevance sensitive belief structures. Ann. Math. Artif. Intell. 28：259-285，2000.