|本期目录/Table of Contents|

[1]辛冠琳,刘惊雷*. 基于精确P值计算学习无环CP­nets[J].南京大学学报(自然科学),2017,53(3):450.[doi:10.13232/j.cnki.jnju.2017.03.010]
 Xin Guanlin,Liu Jinglei*. Learning acyclic CP­nets based on exact P­value computation[J].Journal of Nanjing University(Natural Sciences),2017,53(3):450.[doi:10.13232/j.cnki.jnju.2017.03.010]





 Learning acyclic CP­nets based on exact P­value computation
 Xin GuanlinLiu Jinglei*
 School of Computer and Control Engineering,Yantai University,Yantai,264005,China
 conditional preference networksexact P­value computationDijkstra algorithm principlecausal relationshipacyclic structure
 作为一种简单直观的图形表示工具,条件偏好网(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 paribus 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.Furthermore,it is proved that the time complexity of proposed algorithm is O(n3·2n).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.


 [1] Allen T E,Goldsmith J,Justice H E,et al.Generating CP­nets uniformly at random.In:Proceedings of the 30th AAAI Conference on Artificial Intelligence.Phoenix,USA:AAAI Press,2016:872-878.
[2] Wang H,Shao S,Zhou X,et al.Preference recommendation for personalized search.Knowledge­Based Systems,2016,100(1):124-136.
[3] Alanazi E,Mouhoub M.Variable ordering and constraint propagation for constrained CP­nets.Applied Intelligence,2016,44(2):437-448.
[4] Jiang S,Wang X,Yuan C,et al.Mining user preferences for recommendation:A competition perspective.In:Sun M,Zhang M,Lin D,et al.Proceedings of the 12th China National Conference.Springer,2013,8202:179-189.
[5] Brafman R,Domshlak C.Preference Handling.AI Magazine,2009,30(1):58-86.
[6] 梁 晋,梁吉业,赵兴旺.一种面向大规模社会网络的社区发现算法.南京大学学报(自然科学),2016,52(1):159-166.(Liang J,Liang J Y,Zhao X W.A community detection algorithm for large social network.Journal of Nanjing University(Natural Sciences),2016,52(1):159-166.)
[7] Xu Z,Zhao N.Information fusion for intuitionistic fuzzy decision making:An overview.Information Fusion,2016,28(0):10-23. 
[8] Allen T E.CP­nets:From theory to practice.In:Walsh T.Proceedings of the 4th International Conference on Algorithmic Decision Theory.Lexington,USA:Springer,2015:555-560.
[9] Guerin J T,Allen T E,Goldsmith J.Learning CP­net preferences online from user queries.In:Perny P,Pirlot M,Tsoukiàs A.Proceedings of the 3rd International Conference on Algorithmic Decision Theory.Springer,2013:208-220.
[10] Conitzer V.Making decisions based on the preferences of multiple agents.Communications of the ACM,2010,53(3):84-94.
[11] de Amo S,Diallo M S,Diop C T,et al.Contextual preference mining for user profile construction.Information Systems,2015,49(0):182-199.
[12] Hüllermeier E,Fürnkranz J.On predictive accuracy and risk minimization in pairwise label ranking.Journal of Computer and System Sciences,2010,76(1):49-62.
[13] Boutilier C,Brafman R,Domshlak C,et al.CP­nets:A tool for representing and reasoning with conditional ceteris paribus preference statements.Journal of Artificial Intelligence Research,2004,21(1):135-191.
[14] Ben Amor N,Dubois D,Gouider H,et al.Possibilistic conditional preference networks.In:Destercke S,Denoeux T.Proceedings of the 13th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty.Complène,France:Springer,2015,9161:36-46.
[15] Lelis L H,Stern R,Arfaee S J,et al.Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces.Artificial Intelligence,2016,230(1):51-73.
[16] 孙晓燕,陆宜娜,巩敦卫等.基于CP­nets的偏好感知交互式遗传算法及其个性化搜索.控制与决策,2015,30(7):1153-1161.(Sun X Y,Lu Y N,Gong D W,et al.Interactive genetic algorithm with CP­nets preference surrogate and application in personalized search.Control and Decision,2015,30(7):1153-1161.)
[17] Liu W Y,Wu C H,Feng B,et al.Conditional preference in recommender systems.Expert Systems with Applications,2015,42(2):774-788. 
[18] 辛冠琳,刘惊雷.从偏好数据库中挖掘Ceteris Paribus偏好.计算机应用,2016,36(8):2092-2098.(Xin G L,Liu J L.Mining ceteris paribus preference from preference database.Journal of Computer Applications,2016,36(8):2092-2098.) 
[19] Chen S M,Lin T E,Lee L W.Group decision making using incomplete fuzzy preference relations based on the additive consistency and the order consistency.Information Sciences,2014,259(0):1-15.
[20] Colombo D,Maathuis M H.Order­independent constraint­based causal structure learning.Journal of Machine Learning Research,2014,15(1):3741-3782.
[21] He Y,Jia J,Yu B.Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs.Journal of Machine Learning Research,2015,16(0):2589-2609.
[22] Liu J,Yao Z,Xiong Y,et al.Learning conditional preference network from noisy samples using hypothesis testing.Knowledge­Based Systems,2013,40(0):7-16.
[23] 辛冠琳,刘惊雷.基于G方检验的CP­nets学习.南京大学学报(自然科学),2015,51(4):781-795.(Xin G L,Liu J L.Learning CP­nets based on G2 test.Journal of Nanjing University(Natural Sciences),2015,51(4):781-795.)
[24] Lerner B,Afek M,Bojmel R.Adaptive thresholding in structure learning of a Bayesian network.In:Proceedings of the 23rd International Joint Conference on Artificial Intelligence.Beijing,China:AAAI Press,2013:1458-1464.
[25] Fan X N,Fan N,Malone B,et al.Finding optimal Bayesian network structures with constraints learned from data.In:Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence(UAI­14).Quebec City,Canada:AUAI,2014:200-209.
[26] Dimopoulos Y,Michael L,Athienitou F.Ceteris paribus preference elicitation with predictive guarantees.In:Proceedings of the 21st International Jont Conference on Artifical Intelligence.San Francisco,USA:Morgan Kaufmann Publishers Inc.,2009,9:1890-1895.
[27] Culberson J C,Schaeffer J.Pattern databases.Computational Intelligence,1998,14(3):318-334. 
[28] Holte R C,Felner A,Newton J,et al.Maximizing over multiple pattern databases speeds up heuristic search.Artificial Intelligence,2006,170(16):1123-1136.
[29] Maeoka J,Tanabe Y,Ishikawa F.Depth­first heuristic search for software model checking.In:Computer and Information Science 2015.Las Vegas,USA:Springer,2016,75-96.



更新日期/Last Update: 2017-05-30