We consider an active learning scheme in so-called the transductive learning model, in which the test set is known in advanced and the learner picks the points for which labels are given. We identify a useful general purpose property of such learning problems, giving rise to a corresponding query-efficient iterative procedure that achieves approximately optimal loss at an exponentially fast rate. To show the effectiveness of our ideas, we demonstrate them on the problem of \emph{learning to rank from pairwise preference labels}, also known in the world of combinatorial optimization as the {minimum feedback arc-set in tournaments}. The net result is a selective sampling method for this problem, achieving a $(1+\eps)$-competitive result using an almost optimal number of $O(n\poly(\log n, \eps^{-1}))$ preference queries. As is the unfortunate case with most learning theoretical results bounding query complexity, we do not know how to perform our iterative optimization steps in polynomial time. However, our ideas transfer seamlessly to their relaxed counterparts, giving rise to an iterative algorithm for obtaining an $(1+\eps)$ competitive solution to a natural SVM relaxation (known as SVM-rank) using only $O(n\poly(\log n, \eps^{-1}))$ pairwise preference queries. Additionally, the geometric structure of the solution space in this particular case allows an additional slight improvement in the query complexity using the powerful notion of $\eps$-relative approximations in bounded VC dimension spaces. We believe that our iterative scheme and analysis method are interesting in their own right and will find use in other learning theoretical problem.

我们提出了一种基于池泛型主动学习的不同工具，该工具基于学习器计算假设损失和某个固定“关键”假设之间差异的估计器能力，进而得到一些显著意义上的主动学习界限，尤其对于那些只依赖于不一致性系数限制的方法在某些问题上无法提供有用边界的情况下。

使用平滑相对遗憾逼近技术的主动学习及其应用