基于精确P值计算学习无环CP­nets

南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (3): 450–.

基于精确P值计算学习无环CPnets

辛冠琳，刘惊雷*

出版日期:2017-05-30 发布日期:2017-05-30
作者简介: 烟台大学计算机与控制工程学院，烟台，264005
基金资助:
基金项目：国家自然科学基金(61572419，61572418，61403328，61403329)，山东省自然科学基金(ZR2014FQ016，ZR2014FQ026，2015GSF115009，ZR2016FB22，ZR2013FM011)
收稿日期：2016－12－19
*通讯联系人，Email：jinglei_liu@sina.com

Learning acyclic CPnets based on exact Pvalue computation

Xin Guanlin，Liu Jinglei*

Online:2017-05-30 Published:2017-05-30
About author: School of Computer and Control Engineering，Yantai University，Yantai，264005，China

摘要/Abstract

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

Abstract: As a simple and intuitive graphical tool，CPnets(conditional preference networks) can represent ceteris paribus preference statements over the values of a set of variables.Moreover，a CPnet is an annotated directed graph that encodes the preference relationships among variables of interest.Learning acyclic CPnets，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 decisionmaking.Especially，learning the structure of acyclic CPnets 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 CPnets，such as acyclicity.Utilizing accurate Pvalue computation method，according to the principle of Dijkstra algorithm，we can design a new algorithm－PALA，and gain the structure of acyclic CPnets through the algorithm.Exact Pvalue computation method for learning acyclic CPnets 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，Pvalue computation is especially suitable for measuring the dependent relationship and determining the causal relationship between variables，which can get the structure of acyclic CPnets.Empirical results show that PALA algorithm usually finds higherquality，often optimal networks，compared with other CPnets learning approaches.Our results also show that solving the problem about the learning acyclic CPnets significantly improves the efficiency of PALA structure learning algorithm.

辛冠琳，刘惊雷*. 基于精确P值计算学习无环CPnets[J]. 南京大学学报(自然科学版), 2017, 53(3): 450–.

Xin Guanlin，Liu Jinglei*. Learning acyclic CPnets based on exact Pvalue computation[J]. Journal of Nanjing University(Natural Sciences), 2017, 53(3): 450–.

参考文献

[1]　Allen T E，Goldsmith J，Justice H E，et al.Generating CPnets 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.KnowledgeBased Systems，2016，100(1)：124－136.
[3] Alanazi E，Mouhoub M．Variable ordering and constraint propagation for constrained CPnets.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．CPnets：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 CPnet 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.CPnets：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] 孙晓燕，陆宜娜，巩敦卫等．基于CPnets的偏好感知交互式遗传算法及其个性化搜索．控制与决策，2015，30(7)：1153－1161.(Sun X Y，Lu Y N，Gong D W，et al.Interactive genetic algorithm with CPnets 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．Orderindependent constraintbased 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.KnowledgeBased Systems，2013，40(0)：7－16.
[23] 辛冠琳，刘惊雷．基于G方检验的CPnets学习．南京大学学报(自然科学)，2015，51(4)：781－795.(Xin G L，Liu J L．Learning CPnets 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(UAI14)．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．Depthfirst heuristic search for software model checking.In：Computer and Information Science 2015.Las Vegas，USA：Springer，2016，75－96.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed