Local distance metric learning for efficient conformal predictors

Conformal prediction is a relatively recent approach to classification that offers a theoretical framework for generating predictions with precise levels of confidence. For each new object encountered, a conformal predictor outputs a set of class labels that contains the true label with probability at least 1 − ∈, where ∈ is a user-specified error rate. The ability to predict with confidence can be extremely useful, but in many real-world applications unambiguous predictions consisting of a single class label are preferred. Hence it is desirable to design conformal predictors to maximize the rate of singleton predictions, termed the efficiency of the predictor. In this paper we derive a novel criterion for maximizing efficiency for a certain class of conformal predictors, show how concepts from local distance metric learning can provide a useful bound for maximizing this criterion, and demonstrate efficiency gains on real-world datasets.