Learning conditionally lexicographic preference relations
Learning conditionally lexicographic preference relations
复制标题
DOI：
--
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
R. Booth;Y. Chevaleyre;J. Lang;J. Mengin;Chattrakul Sombattheera
中科院分区：
文献类型：
--
作者：
R. Booth;Y. Chevaleyre;J. Lang;J. Mengin;Chattrakul Sombattheera
我们考虑学习用户在多属性域上的顺序偏好的问题，假设她的偏好是按字典顺序排列的。我们引入了一种称为 LP 树的通用图形表示，它捕获此类偏好关系的各种自然类别，具体取决于属性之间的重要性顺序和/或每个属性域上的局部偏好是否以其他属性的值为条件。对于每个类别，我们确定 Vapnik-Chernovenkis 维度、偏好引发的通信复杂性，以及识别类别中与一组用户提供的示例一致的模型的复杂性。
We consider the problem of learning a user's ordinal preferences on a multiattribute domain, assuming that her preferences are lexicographic. We introduce a general graphical representation called LP-trees which captures various natural classes of such preference relations, depending on whether the importance order between attributes and/or the local preferences on the domain of each attribute is conditional on the values of other attributes. For each class we determine the Vapnik-Chernovenkis dimension, the communication complexity of preference elicitation, and the complexity of identifying a model in the class consistent with a set of user-provided examples.