Query Learning with Exponential Query Costs

Details Query Learning with Exponential Query Costs Query Learning with Exponential Query Costs

2010-02-21

arxiv.org/abs/1002.4019v1

Statistics

Machine Learning

15 pages

Scientific paper

In query learning, the goal is to identify an unknown object while minimizing the number of "yes" or "no" questions (queries) posed about that object. A well-studied algorithm for query learning is known as generalized binary search (GBS). We show that GBS is a greedy algorithm to optimize the expected number of queries needed to identify the unknown object. We also generalize GBS in two ways. First, we consider the case where the cost of querying grows exponentially in the number of queries and the goal is to minimize the expected exponential cost. Then, we consider the case where the objects are partitioned into groups, and the objective is to identify only the group to which the object belongs. We derive algorithms to address these issues in a common, information-theoretic framework. In particular, we present an exact formula for the objective function in each case involving Shannon or Renyi entropy, and develop a greedy algorithm for minimizing it. Our algorithms are demonstrated on two applications of query learning, active learning and emergency response.

Affiliated with

Also associated with

No associations

Rating

Query Learning with Exponential Query Costs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Query Learning with Exponential Query Costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query Learning with Exponential Query Costs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-372800