CP-nets的完备性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-nets上的强占优运算研究CP-nets的完备性和一致性.首先,通过构造CP-nets导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall算法求出可判断任意CP-nets的强占优;其次,通过求取3种不同结构(可分离的、链表结构和树形结构)的CP-nets的偏好个数,给出了CP-nets可表达的偏好的不完备性定理,并给出了可分离的CP-nets中偏好的计数公式;最后,研究CP-nets的一致性,给出了CP-nets的一致性判定定理及其算法.所做工作不仅解决了Boutilier和Goldsmith提出的一些难题,还深化了CP-nets的基础理论研究.

CP-nets及其表达能力研究

偏好处理是人工智能中的一个重要研究内容,它的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 satisfactionproblem,SCSP)的求解方法.它把CP-nets中的定性运算转为约束半环中的定量运算,从而将指数级的复杂度转化为多项式的复杂度,间接提高了部分CP-nets的表达能力.本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.