中文摘要：

作为一种简单直观的图形表示工具,条件偏好网（conditional preference networks,CP-nets）可表示ceteris paribus（其他条件都不变）的偏好关系.学习无环CP-nets是人工智能领域中的一个重要的研究内容,它可广泛使用在推荐系统、信息检索和群体抉择中.特别是有效地学习无环CP-nets的结构,即获取变量之间的因果关系,是当前最主要的研究任务.传统的算法利用不同的方式对CP-nets的结构进行学习,但很多方法学习得到的并不是无环CP-nets.采用精确P值计算学习方法,根据Dijkstra算法原理,设计了新的算法——PALA,并通过该算法学习无环CP-nets结构.随后证明了算法的时间复杂度是O（n3·2n）.作为一种精确学习方法,精确P值计算方法可有效衡量变量之间的依赖程度,确定变量之间的因果关系,进而学习得到无环CP-nets结构.实验结果表明,与其他算法相比,PALA算法通常能够发现高质量的、结构最优的无环CP-nets.研究结果还表明,无环CP-nets学习问题的解决显著地提高了PALA算法的效率.

英文摘要：

As a simple and intuitive graphical tool, CP-nets （conditional preference networks） can represent ceteris parihus preference statements over the values of a set of variables. Moreover,a CP-net is an annotated directed graph that encodes the preference relationships among variables of interest. Learning acyclic CP-nets, which has received great attention recently,is one of the important research contents in the field of artificial intelligence,and it can be applied in recommender systems, information retrieve and group decision-making. Especially, learning the structure of acyclic CP-nets is one of the attractive tasks of the current study for the sake of achieving their structures efficiently,and testing the causal relationship between variables. Traditionally, there have been put forward many algorithms to solve this problem. However,all these techniques suffer from having no constraint on the structure of CP-nets, such as acyclicity. Utilizing accurate P-value computation method, according to the principle of Dijkstra algorithm,we can design a new algorithm-PALA, and gain the structure of acyclic CP-nets through the algorithm.Exact P-value computation method for learning acyclic CP-nets guarantee to find provably optimal networks. Fur- thermore,it is proved that the time complexity of proposed algorithm is O（n3 ~ 27）. As an accurate approach,P-value computation is especially suitable for measuring the dependent relationship and determining the causal relationship between variables, which can get the structure of acyclic CP-nets. Empirical results show that PALA algorithm usually finds higher-quality, often optimal networks, compared with other CP-nets learning approaches. Our results also show that solving the problem about the learning acyclic CP-nets significantly improves the efficiency of PALA structure learning algorithm.