南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (3): 450.
辛冠琳,刘惊雷*
Xin Guanlin,Liu Jinglei*
摘要: 作为一种简单直观的图形表示工具,条件偏好网(conditional preference networks,CPnets)可表示ceteris paribus(其他条件都不变)的偏好关系.学习无环CPnets是人工智能领域中的一个重要的研究内容,它可广泛使用在推荐系统、信息检索和群体抉择中.特别是有效地学习无环CPnets的结构,即获取变量之间的因果关系,是当前最主要的研究任务.传统的算法利用不同的方式对CPnets的结构进行学习,但很多方法学习得到的并不是无环CPnets.采用精确P值计算学习方法,根据Dijkstra算法原理,设计了新的算法——PALA,并通过该算法学习无环CPnets结构.随后证明了算法的时间复杂度是O(n3·2n).作为一种精确学习方法,精确P值计算方法可有效衡量变量之间的依赖程度,确定变量之间的因果关系,进而学习得到无环CPnets结构.实验结果表明,与其他算法相比,PALA算法通常能够发现高质量的、结构最优的无环CPnets.研究结果还表明,无环CPnets学习问题的解决显著地提高了PALA算法的效率.
[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. |
No related articles found! |
|