In pool-based active learning, the learner is given an unlabeled data set and
aims to efficiently learn the unknown hypothesis by querying the labels of the
data points. This can be formulated as the classical Optimal Decision Tree
(ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for
each pair of test and hypothesis, our objective is to find a low-cost testing
procedure (i.e., decision tree) that identifies the true hypothesis. This
optimization problem has been extensively studied under the assumption that
each test generates a deterministic outcome. However, in numerous applications,
for example, clinical trials, the outcomes may be uncertain, which renders the
ideas from the deterministic setting invalid. In this work, we study a
fundamental variant of the ODT problem in which some test outcomes are noisy,
even in the more general case where the noise is persistent, i.e., repeating a
test gives the same noisy output. Our approximation algorithms provide
guarantees that are nearly best possible and hold for the general case of a
large number of noisy outcomes per test or per hypothesis where the performance
degrades continuously with this number. We numerically evaluated our algorithms
for identifying toxic chemicals and learning linear classifiers, and observed
that our algorithms have costs very close to the information-theoretic minimum.

通过近似算法研究具有噪声结果的最优决策树问题，以及在测试或假设中具有大量噪声结果时性能逐渐下降的情况。