论文标题
无监督学习词典偏好的复杂性
The complexity of unsupervised learning of lexicographic preferences
论文作者
论文摘要
本文考虑了在线配置器通常使用的一组替代方案中学习用户偏好的任务。在许多设置中，在过去的互动过程中只有一组选定的替代方案可供学习者使用。 Fargier等。 [2018]提出了一种在这种环境中学习用户偏好模型的方法，该模型对先前选择的替代方案进行了排名尽可能高；以及一种在这种情况下学习的算法，是一种特定的偏好模型：词典偏好树（LP-Trees）。在本文中，我们研究了与这种方法相关的复杂性理论问题。我们对学习LP-Tree的样本复杂性给出了上限，这在属性数量上是对数。我们还证明，计算最小化经验风险的LP树当仅限于线性LP-Trees的类别时，可以在多项式时间内完成。
This paper considers the task of learning users' preferences on a combinatorial set of alternatives, as generally used by online configurators, for example. In many settings, only a set of selected alternatives during past interactions is available to the learner. Fargier et al. [2018] propose an approach to learn, in such a setting, a model of the users' preferences that ranks previously chosen alternatives as high as possible; and an algorithm to learn, in this setting, a particular model of preferences: lexicographic preferences trees (LP-trees). In this paper, we study complexity-theoretical problems related to this approach. We give an upper bound on the sample complexity of learning an LP-tree, which is logarithmic in the number of attributes. We also prove that computing the LP tree that minimises the empirical risk can be done in polynomial time when restricted to the class of linear LP-trees.
