We construct near optimal linear decision trees for a variety of decision
problems in combinatorics and discrete geometry. For example, for any constant
$k$, we construct linear decision trees that solve the $k$-SUM problem on $n$
elements using $O(n \log^2 n)$ linear queries. Moreover, the queries we use are
comparison queries, which compare the sums of two $k$-subsets; when viewed as
linear queries, comparison queries are $2k$-sparse and have only $\{-1,0,1\}$
coefficients. We give similar constructions for sorting sumsets $A+B$ and for
solving the SUBSET-SUM problem, both with optimal number of queries, up to
poly-logarithmic terms.
Our constructions are based on the notion of "inference dimension", recently
introduced by the authors in the context of active classification with
comparison queries. This can be viewed as another contribution to the fruitful
link between machine learning and discrete geometry, which goes back to the
discovery of the VC dimension.

本文研究了求解离散几何和组合问题中的线性决策树，提出了一种基于推理维度的新方法来构造线性决策树，并通过比较查询来解决 $K$-SUM 问题、排序 sumsets $A+B$ 以及解决子集 - SUM 问题，与统计学习和离散几何的研究有着密切联系。

k-SUM 和相关问题的近似最优线性决策树

Near-optimal linear decision trees for k-SUM and related problems

We study an extension of active learning in which the learning algorithm may
ask the annotator to compare the distances of two examples from the boundary of
their label-class. For example, in a recommendation system application (say for
restaurants), the annotator may be asked whether she liked or disliked a
specific restaurant (a label query); or which one of two restaurants did she
like more (a comparison query).
We focus on the class of half spaces, and show that under natural
assumptions, such as large margin or bounded bit-description of the input
examples, it is possible to reveal all the labels of a sample of size $n$ using
approximately $O(\log n)$ queries. This implies an exponential improvement over
classical active learning, where only label queries are allowed. We complement
these results by showing that if any of these assumptions is removed then, in
the worst case, $\Omega(n)$ queries are required.
Our results follow from a new general framework of active learning with
additional queries. We identify a combinatorial dimension, called the
\emph{inference dimension}, that captures the query complexity when each
additional query is determined by $O(1)$ examples (such as comparison queries,
each of which is determined by the two compared examples). Our results for half
spaces follow by bounding the inference dimension in the cases discussed above.

研究一种扩展主动学习的方法，其中学习算法可以要求注释者比较两个示例与其标签类边界的距离，并使用半空间的框架展示这种方法的优越性。