Average-Case Active Learning with Costs
  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.
