计算机科学 ››2018,Vol. 45 ››Issue (6): 211-215.doi:10.11896/j.issn.1002-137X.2018.06.038
刘惊雷1,2, 廖士中1
LIU Jing-lei1,2, LIAO Shi-zhong1
摘要：CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CP-nets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。
中图分类号:
刘惊雷, 廖士中.CP-nets学习的复杂度[J]. 计算机科学, 2018, 45(6): 211-215. https://doi.org/10.11896/j.issn.1002-137X.2018.06.038
LIU Jing-lei, LIAO Shi-zhong.Complexity of CP-nets Learning[J]. Computer Science, 2018, 45(6): 211-215. https://doi.org/10.11896/j.issn.1002-137X.2018.06.038
| [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 |
| ||
首页