Assume we are given a set of items from a general metric space, but we
neither have access to the representation of the data nor to the distances
between data points. Instead, suppose that we can actively choose a triplet of
items (A,B,C) and ask an oracle whether item A is closer to item B or to item
C. In this paper, we propose a novel random forest algorithm for regression and
classification that relies only on such triplet comparisons. In the theory part
of this paper, we establish sufficient conditions for the consistency of such a
forest. In a set of comprehensive experiments, we then demonstrate that the
proposed random forest is efficient both for classification and regression. In
particular, it is even competitive with other methods that have direct access
to the metric representation of the data.

本论文提出了一个基于三元组比较的新型随机森林算法，用于度量空间中的数据回归和分类，不需要数据点的距离或具体表示方法，并证明其与其他直接访问数据表示的方法相当竞争力强。

基于比较的随机森林

Comparison-Based Random Forests

Learning a model of perceptual similarity from a collection of objects is a
fundamental task in machine learning underlying numerous applications. A common
way to learn such a model is from relative comparisons in the form of triplets:
responses to queries of the form "Is object a more similar to b than it is to
c?". If no consideration is made in the determination of which queries to ask,
existing similarity learning methods can require a prohibitively large number
of responses. In this work, we consider the problem of actively learning from
triplets -finding which queries are most useful for learning. Different from
previous active triplet learning approaches, we incorporate auxiliary
information into our similarity model and introduce an active learning scheme
to find queries that are informative for quickly learning both the relevant
aspects of auxiliary data and the directly-learned similarity components.
Compared to prior approaches, we show that we can learn just as effectively
with much fewer queries. For evaluation, we introduce a new dataset of
exhaustive triplet comparisons obtained from humans and demonstrate improved
performance for different types of auxiliary information.

本研究提出一种新的主动学习算法，该算法从外部数据中找出最具信息量的三元组比较方式；实验表明该方法需要远少于传统方法的三元组比较数量即可达到同等效果。