Nonparametric active learning for cost-sensitive classification
This work addresses cost-sensitive learning problems where prediction errors have varying costs, offering a method with proven optimality and explicit performance improvements, though it appears incremental as it builds on existing active learning and noise assumption frameworks.
The paper tackles cost-sensitive classification by designing a nonparametric active learning algorithm that selects informative points and queries only potentially minimal-cost predictions, achieving optimal convergence rates and explicitly characterizing gains over passive learning under noise assumptions.
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.