Classic machine learning algorithms learn from labelled examples. For
example, to design a machine translation system, a typical training set will
consist of English sentences and their translation. There is a stronger model,
in which the algorithm can also query for labels of new examples it creates.
E.g, in the translation task, the algorithm can create a new English sentence,
and request its translation from the user during training. This combination of
examples and queries has been widely studied. Yet, despite many theoretical
results, query algorithms are almost never used. One of the main causes for
this is a report (Baum and Lang, 1992) on very disappointing empirical
performance of a query algorithm. These poor results were mainly attributed to
the fact that the algorithm queried for labels of examples that are artificial,
and impossible to interpret by humans.
In this work we study a new model of local membership queries (Awasthi et
al., 2012), which tries to resolve the problem of artificial queries. In this
model, the algorithm is only allowed to query the labels of examples which are
close to examples from the training set. E.g., in translation, the algorithm
can change individual words in a sentence it has already seen, and then ask for
the translation. In this model, the examples queried by the algorithm will be
close to natural examples and hence, hopefully, will not appear as artificial
or random. We focus on 1-local queries (i.e., queries of distance 1 from an
example in the training sample). We show that 1-local membership queries are
already stronger than the standard learning model. We also present an
experiment on a well known NLP task of sentiment analysis. In this experiment,
the users were asked to provide more information than merely indicating the
label. We present results that illustrate that this extra information is
beneficial in practice.

该研究旨在解决人工标注数据的不足之处，提出了一种新的局部会员查询模型，以解决在机器学习和自然语言处理任务中的动态标记问题，并通过实验证明了这种方法的实用性。

使用 1 - 局部会员查询进行学习

Learning Using 1-Local Membership Queries

We introduce a new model of membership query (MQ) learning, where the
learning algorithm is restricted to query points that are \emph{close} to
random examples drawn from the underlying distribution. The learning model is
intermediate between the PAC model (Valiant, 1984) and the PAC+MQ model (where
the queries are allowed to be arbitrary points).
Membership query algorithms are not popular among machine learning
practitioners. Apart from the obvious difficulty of adaptively querying
labelers, it has also been observed that querying \emph{unnatural} points leads
to increased noise from human labelers (Lang and Baum, 1992). This motivates
our study of learning algorithms that make queries that are close to examples
generated from the data distribution.
We restrict our attention to functions defined on the $n$-dimensional Boolean
hypercube and say that a membership query is local if its Hamming distance from
some example in the (random) training data is at most $O(\log(n))$. We show the
following results in this model:
(i) The class of sparse polynomials (with coefficients in R) over $\{0,1\}^n$
is polynomial time learnable under a large class of \emph{locally smooth}
distributions using $O(\log(n))$-local queries. This class also includes the
class of $O(\log(n))$-depth decision trees.
(ii) The class of polynomial-sized decision trees is polynomial time
learnable under product distributions using $O(\log(n))$-local queries.
(iii) The class of polynomial size DNF formulas is learnable under the
uniform distribution using $O(\log(n))$-local queries in time
$n^{O(\log(\log(n)))}$.
(iv) In addition we prove a number of results relating the proposed model to
the traditional PAC model and the PAC+MQ model.

本文提出了一种新的分布学习模型，即在分布数据的随机样例附近进行局部查询来学习，并证明在该模型下，一些多项式和决策树相关的问题可以通过局部查询在多项式时间内进行学习。