We study the problem of evaluating a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. Reading the value of a variable is done at the expense of some cost, and the goal is to design a strategy (decision tree) for evaluating the function incurring as little cost as possible in the worst case or in expectation (according to a prior distribution on the possible variables assignments). Except for particular cases of the problem, in general, only the minimization of one of these two measures is addressed in the literature. However, there are instances of the problem for which the minimization of one measure leads to a strategy with a high cost with respect to the other measure (even exponentially bigger than the optimal). We provide a new construction which can guarantee a trade-off between the two criteria. More precisely, given a decision tree guaranteeing expected cost @math and a decision tree guaranteeing worst cost @math our method can guarantee for any chosen trade-off value @math to produce a decision tree whose worst cost is @math and whose expected cost is @math These bounds are improved for the relevant case of uniform testing costs. Motivated by applications, we also study a variant of the problem where the cost of reading a variable depends on the variable's value. We provide an @math approximation algorithm for the minimization of the worst cost measure, which is best possible under the assumption @math .
We analyze the expected cost of a greedy active learning algorithm. Our analysis extends previous work to a more general setting in which different queries have different costs. Moreover, queries may have more than two possible responses and the distribution over hypotheses may be non uniform. Specific applications include active learning with label costs, active learning for multiclass and partial label queries, and batch mode active learning. We also discuss an approximate version of interest when there are very many queries. We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O(rK • log N), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value rK is a suitably defined Ramsey number, which is at most log K. We show that it is NP-hard to approximate the problem within a factor of Ω(log N), even for binary tables (i.e. K=2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r2=2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdos. We introduce a natural generalization of submodular set cover and exact active learning with a finite hypothesis class (query learning). We call this new problem interactive submodular set cover. Applications include advertising in social networks with hidden information. We give an approximation guarantee for a novel greedy algorithm and give a hardness of approximation result which matches up to constant factors. We also discuss negative results for simpler approaches and present encouraging early experimental results.  In the general search problem we want to identify a specific element using a set of allowed tests. The general goal is to minimize the number of tests performed, although different measures are used to capture this goal. In this work we introduce a novel greedy approach that achieves the best known approximation ratios simultaneously for many different variations of this identification problem. In addition to this flexibility, our algorithm admits much shorter and simpler analyses than previous greedy strategies. As a second contribution, we investigate the potential of greedy algorithms for the more restricted problem of identifying elements of partially ordered sets by comparison with other elements. We prove that the latter problem is as hard to approximate as the general identification problem. As a positive result, we show that a natural greedy strategy achieves an approximation ratio of 2 for tree-like posets, improving upon the previously best known 14-approximation for this problem. We study simultaneous learning and covering problems: submodular set cover problems that depend on the solution to an active (query) learning problem. The goal is to jointly minimize the cost of both learning and covering. We extend recent work in this setting to allow for a limited amount of adversarial noise. Certain noisy query learning problems are a special case of our problem. Crucial to our analysis is a lemma showing the logical OR of two submodular cover constraints can be reduced to a single submodular set cover constraint. Combined with known results, this new lemma allows for arbitrary monotone circuits of submodular cover constraints to be reduced to a single constraint. As an example practical application, we present a movie recommendation website that minimizes the total cost of learning what the user wants to watch and recommending a set of movies.  We consider the problem of constructing optimal decision trees: given a collection of tests which can disambiguate between a set of m possible diseases, each test having a cost, and the a-priori likelihood of the patient having any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? We settle the approximability of this problem by giving a tight O(logm)-approximation algorithm. We also consider a more substantial generalization, the Adaptive TSP problem, which can be used to model switching costs between tests in the optimal decision tree problem. Given an underlying metric space, a random subset S of cities is drawn from a known distribution, but S is initially unknown to us--we get information about whether any city is in S only when we visit the city in question. What is a good adaptive way of visiting all the cities in the random subset S while minimizing the expected distance traveled? For this adaptive TSP problem, we give the first poly-logarithmic approximation, and show that this algorithm is best possible unless we can improve the approximation guarantees for the well-known group Steiner tree problem. We tackle the fundamental problem of Bayesian active learning with noise, where we need to adaptively select from a number of expensive tests in order to identify an unknown hypothesis sampled from a known prior distribution. In the case of noise-free observations, a greedy algorithm called generalized binary search (GBS) is known to perform near-optimally. We show that if the observations are noisy, perhaps surprisingly, GBS can perform very poorly. We develop EC2, a novel, greedy active learning algorithm and prove that it is competitive with the optimal policy, thus obtaining the first competitiveness guarantees for Bayesian active learning with noisy observations. Our bounds rely on a recently discovered diminishing returns property called adaptive submodularity, generalizing the classical notion of submodular set functions to adaptive policies. Our results hold even if the tests have non-uniform cost and their noise is correlated. We also propose EffECXtive, a particularly fast approximation of EC2, and evaluate it on a Bayesian experimental design problem involving human subjects, intended to tease apart competing economic theories of how people make decisions under uncertainty. In applications such as active learning and disease fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time-critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification. We introduce and study a problem that we refer to as the optimal split tree problem. The problem generalizes a number of problems including two classical tree construction problems including the Huffman tree problem and the optimal alphabetic tree. We show that the general split tree problem is NP-complete and analyze a greedy algorithm for its solution. We show that a simple modification of the greedy algorithm guarantees O(log n) approximation ratio. We construct an example for which this algorithm achieves Ω(log n log log n) approximation ratio. We show that if all weights are equal and the optimal split tree is of depth O(log n). then the greedy algorithm guarantees O(log n log log n) approximation ratio. We also extend our approximation algorithm to the construction of a search tree for partially ordered sets. We give a (ln n+ 1)-approximation for the decision tree (DT) problem. An instance of DT is a set of mbinary tests T= (T 1 , ..., T m ) and a set of nitems X= (X 1 , ..., X n ). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer science with applications ranging from medical diagnosis to experiment design. It also generalizes the problem of finding optimal average-case search strategies in partially ordered sets which includes several alphabetic tree problems. Our work decreases the previous upper bound on the approximation ratio by a constant factor. We provide a new analysis of the greedy algorithm that uses a simple accounting scheme to spread the cost of a tree among pairs of items split at a particular node. We conclude by showing that our upper bound also holds for the DT problem with weighted tests. In several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables' assignments). Our algorithm builds a strategy (decision tree) which attains a logarithmic approximation simultaneously for the expected and worst cost spent. This is best possible since, under standard complexity assumption, no algorithm can guarantee o(log n) approximation.