摘要翻译：
在许多应用程序中，希望对实例进行排序而不是分类。在这里，我们考虑学习如何以偏好判断的形式给出反馈的实例排序的问题，即，大意是一个实例应该排在另一个实例之前的陈述。我们概述了一个两阶段的方法，在这个方法中，人们首先通过传统的方法学习一个二元偏好函数，该函数指示是否在另一个实例之前对一个实例进行排序是可取的。这里我们考虑一个在线学习偏好函数的算法，它是基于Freund和Schapire的“hedge”算法。在第二阶段，对新实例进行排序，以使其与学习到的偏好函数最大程度地一致。我们证明了寻找与学习的偏好函数最一致的排序问题是NP完全的。然而，我们描述了简单的贪婪算法，保证找到一个良好的近似值。最后，我们展示了如何将metasearch描述为一个排序问题，并给出了学习“搜索专家”组合的实验结果，每个专家都是web搜索引擎的特定领域查询扩展策略。
---
英文标题：
《Learning to Order Things》
---
作者：
W. W. Cohen, R. E. Schapire, Y. Singer
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference judgments, i.e., statements to the effect that one instance should be ranked ahead of another. We outline a two-stage approach in which one first learns by conventional means a binary preference function indicating whether it is advisable to rank one instance before another. Here we consider an on-line algorithm for learning preference functions that is based on Freund and Schapire's 'Hedge' algorithm. In the second stage, new instances are ordered so as to maximize agreement with the learned preference function. We show that the problem of finding the ordering that agrees best with a learned preference function is NP-complete. Nevertheless, we describe simple greedy algorithms that are guaranteed to find a good approximation. Finally, we show how metasearch can be formulated as an ordering problem, and present experimental results on learning a combination of 'search experts', each of which is a domain-specific query expansion strategy for a web search engine.
---
PDF链接：
https://arxiv.org/pdf/1105.5464