计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 211-215.doi: 10.11896/j.issn.1002-137X.2018.06.038

• 人工智能 • 上一篇    下一篇

CP-nets学习的复杂度

刘惊雷1,2, 廖士中1   

  1. 天津大学计算机科学与技术学院 天津3000721;
    烟台大学计算机与控制工程学院 山东 烟台2640052
  • 收稿日期:2017-05-30 出版日期:2018-06-15 发布日期:2018-07-24
  • 作者简介:刘惊雷(1970-),男,博士生,副教授,CCF会员,主要研究方向为人工智能基础、理论计算机科学;廖士中(1964-),男,教授,博士生导师,CCF会员,主要研究方向为人工智能基础、理论计算机科学,E-mail:shizhongliao@tju.edu.cn(通信作者)
  • 基金资助:
    本文受国家自然科学基金(61673293,61572419,61773331)资助

Complexity of CP-nets Learning

LIU Jing-lei1,2, LIAO Shi-zhong1   

  1. SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin 3000721;
    SchoolofComputerandControlEngineering,YantaiUniversity,Yantai,Shandong 2640052
  • Received:2017-05-30 Online:2018-06-15 Published:2018-07-24

摘要: CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CP-nets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。

关键词: 二值条件偏好网, 复杂度的上下界, 命题公式的可满足性, 推理与学习, 有界树宽的 CP-nets

Abstract: CP-nets (Conditional Preference networks) are a kind of simple and intuitively graphical tool for representing conditional preference,three fundamental research questions of which are representation,reasoning and learning.Diffe-rently from the research point from statistical learning theory,the binary-valued CP-nets learning issues were studied based on logic theory.Firstly,an intimate relationship between satisfiability of proposition logic formula and preference assertion is given,therefore,the learning problem on CP-nets is transformed into the proposition reasoning.In the se-cond place,the computational complexity for learning two kinds of specific CP-nets is given,the learning problem of most complicated acyclic CP-nets is NP-complete,whereas the learning problem of the simplest set-structured CP-nets is P.These interesting results establish the upper and lower bound of complexity for learning specific structured (e.g.,list-structured,bounded tree-width) CP-nets.

Key words: Binary-valued conditional preference networks, Bounded tree-width CP-nets, Reasoning and learning, Satisfiability of propositional formula, Upper and lower bound of complexity

中图分类号: 

  • TP182
[1]DOMSHLAK C,HULLERMEIER E,KACI S,et al.Preferences in AI:An Overview [J].Artificial Intelligence,2011,175(7/8):1037-1052.
[2]BOUTILER C,BRAFMAN R,DOMSHLAK C,et al.CP-nets:A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements [J].Journal of artificial intelligence research,2004,21(1):135-191.
[3]MATTEI N,PINI M S,ROSSI F,et al.Bribery in Voting withCP-nets[J].Annals of Mathematics and Artificial Intelligence,2013,68(1):1-26.
[4]ALANNAZI E,MOUHOUB M,ZILLES S.The Complexity of Learning Acyclic Cp-nets [C]//The 25th International Joint Conference on Artificial Intelligence.New York,2016:1361-1367.
[5]LIU J L,LIAO S Z.Expressive Efficiency of Two Kinds of Specific CP-nets[J].Information Sciences,2015,295(2):379-394.
[6]LIU J L,LIAO S Z,ZHANG W.On the Completeness and Consistency for CP-nets[J].Journal of Software,2012,23(6):1531-1541.(in Chinese)
刘惊雷,廖士中,张伟.CP-nets的完备性及一致性研究[J].软件学报,2012,23(6):1531-1541.
[7]LIU J T,XIONG Y,WU C H,et al.Learning Conditional Preference Networks from Inconsistent Examples [J].IEEE Transactions on Knowledge and Data Engineering,2014,26(2):376-390.
[8]KOROCHE F,ZANNUTTINI B.Learning Conditional Preference Networks [J].Artificial Intelligence,2010,174(11):685-703.
[9]HUANG S J,JIN R,ZHOU Z H.Active Learning by Querying Informative and Representative Examples [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(10):1936-1949.
[10]LANG J,MENGIN J.The Complexity of Learning Separable Ceteris Paribus Preferences [C]//Proceedings of the 21st International Joint Conference on Artificial Intelligence.2009:848-853.
[11]DIMOPOULOS Y,MICHAEL L,ATHIENITOU F.Ceteris Paribus Preference Elicitation with Predictive Guarantees [C]//Proceedings of the International Joint Conference on Artificial Intelligence.2009:1890-1895.
[12]MUGGLETON S,MARGINEAN F.Logic-based Machine Learning [M]//Logic-based Artificial Intelligence.Springer US,2000:315-330.
[13]GOLDSMITH J,LANG J,TRUSZCZYNSKI M,et al.The Computational Complexity of Dominance and Consistency in CP-nets[J].Journal of Artificial Intelligence Research,2008,33(1):403-432.
[14]LU T,BOUTILIER C.Effective Sampling and Learning for Mallows Models with Pairwise Preferences Data [J].Journal of Machine Learning Research,2014,16(12):3783-3829.
[15]COJAOGHLAN A.Belief Propagation Guided Decimation Fails on Random Formulas [J].Journal of the ACM,2017,63(6):1-49,55.
[16]OBIEDKOV S.Parameterized Ceteris Paribus Preferences Over Atomic Conjunctions under Conservative Semantics [J].Theoretical Computer Science,2016,658(1):375-390.
[17]DAVIDE G,EMILIANO L,FRANCOIS S.The Ceteris Paribus Structure of Logics of Game Forms [J].Journal of Artificial Intelligence Research,2015,53(1):91-126.
[18]BENTHEM V,GIRARD P,ROY O.Everything Else Being Equal:A Modal Logic for Ceteris Paribus Preferences [J].Journal of Philosophical Logic,2009,38(1):83-125.
[19]GOTTLOB G,PICHLER R,WEI F.Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning[J].Artificial Intelligence,2010,174(1):105-132.
[20]ZHOU L,WANG L,LIU L,et al.Learning Discriminative Bayesian Networks from High-dimensional Continuous Neuroimaging Data [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2269-2283.
[1] 王杰, 李晓楠, 李冠宇.
基于自适应注意力机制的知识图谱补全算法
Adaptive Attention-based Knowledge Graph Completion
计算机科学, 2022, 49(7): 204-211. https://doi.org/10.11896/jsjkx.210400129
[2] 方连花, 林玉梅, 吴伟志.
随机多尺度序决策系统的最优尺度选择
Optimal Scale Selection in Random Multi-scale Ordered Decision Systems
计算机科学, 2022, 49(6): 172-179. https://doi.org/10.11896/jsjkx.220200067
[3] 许思雨, 秦克云.
基于剩余格的模糊粗糙集的拓扑性质
Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices
计算机科学, 2022, 49(6A): 140-143. https://doi.org/10.11896/jsjkx.210200123
[4] 蔡晓娟, 谭文安.
一种改进的融合相似度和信任度的协同过滤算法
Improved Collaborative Filtering Algorithm Combining Similarity and Trust
计算机科学, 2022, 49(6A): 238-241. https://doi.org/10.11896/jsjkx.210400088
[5] 李妍妍, 秦克云.
广义粗糙近似算子的拓扑性质
On Topological Properties of Generalized Rough Approximation Operators
计算机科学, 2022, 49(3): 263-268. https://doi.org/10.11896/jsjkx.210100204
[6] 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏.
基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法
Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform
计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[7] 徐进.
面向工业装配的知识图谱构建与应用研究
Construction and Application of Knowledge Graph for Industrial Assembly
计算机科学, 2021, 48(6A): 285-288. https://doi.org/10.11896/jsjkx.200600116
[8] 丁玲, 向阳.
基于分层次多粒度语义融合的中文事件检测
Chinese Event Detection with Hierarchical and Multi-granularity Semantic Fusion
计算机科学, 2021, 48(5): 202-208. https://doi.org/10.11896/jsjkx.200800038
[9] 鲁巡, 李妍妍, 秦克云.
三种近似算子之间的关系
Relationship Among Three Types of Rough Approximation Pairs
计算机科学, 2021, 48(4): 49-53. https://doi.org/10.11896/jsjkx.200900089
[10] 胡平, 秦克云.
基于模糊等价的毕达哥拉斯模糊集相似度构造方法
Similarity Construction Method for Pythagorean Fuzzy Set Based on Fuzzy Equivalence
计算机科学, 2021, 48(1): 152-156. https://doi.org/10.11896/jsjkx.191100102
[11] 郭庆春,马建敏.
对偶区间集概念格上区间集协调集的判定方法
Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices
计算机科学, 2020, 47(3): 98-102. https://doi.org/10.11896/jsjkx.190500098
[12] 冯晨娇,梁吉业,宋鹏,王智强.
基于极端评分行为的相似度计算
New Similarity Measure Based on Extremely Rating Behavior
计算机科学, 2020, 47(2): 31-36. https://doi.org/10.11896/jsjkx.190500130
[13] 石晓玲, 陈芷, 杨立功, 沈伟.
基于自适应样本权重的矩阵分解推荐算法
Matrix Factorization Recommendation Algorithm Based on Adaptive Weighted Samples
计算机科学, 2019, 46(6A): 488-492.
[14] 陈德江, 王君, 张浩为.
基于直觉模糊多属性决策的动态威胁评估模型
Dynamic Threat Assessment Model Based on Intuitionistic Fuzzy Multiple Attribute Decision Making
计算机科学, 2019, 46(4): 183-188. https://doi.org/10.11896/j.issn.1002-137X.2019.04.029
[15] 林洪,秦克云.
决策形式背景基于三支决策规则的属性约简
Attribute Reduction for Decision Formal Contexts Based on Threek-way Decision Rules
计算机科学, 2019, 46(3): 248-252. https://doi.org/10.11896/j.issn.1002-137X.2019.03.037
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!