Learning Tree-Structured CP-Nets with Local Search
Learning Tree-Structured CP-Nets with Local Search
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thomas E. Allen;Cory Siler;J. Goldsmith
中科院分区：
文献类型：
--
作者：
Thomas E. Allen;Cory Siler;J. Goldsmith
条件偏好网络（CP-nets）是定性偏好的直观和表达性表示。必须以某种方式获得这种模式。心理学家认为直接诱导是可疑的。另一方面，从成对比较中学习一般CP网是NP难的，并且-对于某些学习概念-这甚至扩展到最简单形式的CP网。我们引入了一种新颖、简洁的二进制值、树结构CP网络编码，支持第一个基于局部搜索的CP网络学习算法。虽然二进制值，树结构CP网的精确学习-对于严格的，基于蕴涵的学习概念-已经在P中，但我们的算法是第一个优雅地处理噪声的空间有效学习算法（即，现实的）比较集。
Conditional preference networks (CP-nets) are an intuitive and expressive representation for qualitative preferences. Such models must somehow be acquired. Psychologists argue that direct elicitation is suspect. On the other hand, learning general CP-nets from pairwise comparisons is NP-hard, and — for some notions of learning — this extends even to the simplest forms of CP-nets. We introduce a novel, concise encoding of binary-valued, tree-structured CP-nets that supports the first local-search-based CP-net learning algorithms. While exact learning of binary-valued, tree-structured CP-nets — for a strict, entailment-based notion of learning — is already in P, our algorithm is the first space-efficient learning algorithm that gracefully handles noisy (i.e., realistic) comparison sets.