Nonparametric active learning for cost-sensitive classification

Cost-sensitive learning is a common type of machine learning problem where
different errors of prediction incur different costs. In this paper, we design
a generic nonparametric active learning algorithm for cost-sensitive
classification. Based on the construction of confidence bounds for the expected
prediction cost functions of each label, our algorithm sequentially selects the
most informative vector points. Then it interacts with them by only querying
the costs of prediction that could be the smallest. We prove that our algorithm
attains optimal rate of convergence in terms of the number of interactions with
the feature vector space. Furthermore, in terms of a general version of
Tsybakov's noise assumption, the gain over the corresponding passive learning
is explicitly characterized by the probability-mass of the boundary decision.
Additionally, we prove the near-optimality of obtained upper bounds by
providing matching (up to logarithmic factor) lower bounds.