首页 | 本学科首页   官方微博 | 高级检索  
     

CP-nets及其表达能力研究
引用本文:刘惊雷.CP-nets及其表达能力研究[J].自动化学报,2011,37(3):290-302.
作者姓名:刘惊雷
作者单位:1.烟台大学计算机学院 烟台 264005
摘    要:偏好处理是人工智能中的一个重要研究内容, 它的4个研究热点是偏好的表示、 提取、 聚合和推理. 条件偏好网(Conditional preference networks, CP-nets)是一种简单直观的偏好表示的图形工具, 但很少有工作研究CP-nets的表达能力. 本文研究CP-nets的表达能力, 详细研究了CP-nets表达偏好的完备性, 其上构造的运算复杂度以及适用的场合. 首先给出了CP-nets模型上的几个运算, 利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n). 其次通过构造CP-nets导出图及其性质的研究, 得出CP-nets特别适合不完全信息下的多属性定性偏好决策. 当需要处理更完全信息时, 可借助于与Agent的交互来完成. 虽然我们给出了CP-nets的强占优测试的理论解, 但其理论上可解, 实际上不可解. 为了解决强占优测试的指数级复杂度问题, 本文最后给出了一种带有软约束的满足问题(Soft constraint satisfaction problem, SCSP)的求解方法. 它把CP-nets中的定性运算转为约束半环中的定量运算, 从而将指数级的复杂度转化为多项式的复杂度, 间接提高了部分CP-nets的表达能力. 本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.

关 键 词:条件偏好网    表达能力    强占优测试    偏好的完备性    改进的Warshall算法    不完全信息下的多属性定性偏好决策    带有软约束的满足问题
收稿时间:2010-5-24
修稿时间:2010-10-13

Research on CP-nets and Its Expressive Power
LIU Jing-Lei.Research on CP-nets and Its Expressive Power[J].Acta Automatica Sinica,2011,37(3):290-302.
Authors:LIU Jing-Lei
Affiliation:1.School of Computer Science and Technology, Yantai University, Yantai 264005
Abstract:Preference handling is one of the important researching contents in artificial intelligence, whose four studying hotspots are preference representation, preference elicitation, preference aggregation and preference inference. The conditional preference networks (CP-nets) is a simple and intuitive graphical tool for representing conditional ceteris paribus preference statements over the values of a set of variables. But there are very few works that address the problem of expressive power of CP-nets. In this paper, the expressive power of CP-nets is studied, in particular, preference completeness, some operations complexity of CP-nets and situation to which the model is applicable are discussed detailedly. Firstly, some operations of CP-nets are discussed; by using the improved Warshall algorithm, we solve the problem of worst case complexity of strong dominance testing with respect to binary-valued CP-nets, and prove its complexity is O(4n). Secondly, by constructing induced graph of CP-nets and studying its properties, we draw a conclusion that CP-nets suit multiple attributes qualitative decision making under incomplete preference information situation especially. When handling complete preference information, it can be fulfilled by interactive communication with agent. Strong dominance testing is a tractable problem in theory, but it is a intractable problem in practice. In order to solve this exponential order complexity, at last, some reduction techniques from qualitative judging to quantitative judging with soft constraint satisfaction problem (SCSP) are given. Because qualitative judging on c-simiring is of linear complexity, it increases the expressive power of some CP-nets. All these can be seen as the improvement and refinement of Boutilier and Bistarelli's related works.
Keywords:Conditional preference networks (CP-nets)  expressive power  strong dominance testing  preferences completeness  improved Warshall algorithm  multiple attribute qualitative decision under incomplete information  soft constraint satisfaction problem (SCSP)
点击此处可从《自动化学报》浏览原始摘要信息
点击此处可从《自动化学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号