# Bayes-consistent cost-sensitive classification

In cost-sensitive classification, we have a confusion (or cost) matrix $$C$$, where $$C(i,j)$$ is the cost incurred for predicting label $$i$$ when nature specifies $$j$$. The costs are non-negative, but no other restriction (such as symmetry) need be imposed. In the classic setting (PAC and its multiclass generalization), $$C(i,j)=1[i\neq j]$$.

The notion of Bayes-consistency carries over naturally to the cost-sensitive setting. For any joint distribution $$P$$ over the instances $$\mathcal{X}$$ and labels $$\mathcal{Y}$$, we define the risk of a predictor $$f:\mathcal{X}\to \mathcal{Y}$$ as $$R(f)= \mathbb{E}_{(X,Y)\sim P} C(f(X),Y).$$ Letting $$f^*$$ be a minimizer of $$R(\cdot)$$ over all measurable $$f$$, we define the Bayes-optimal risk as $$R^*:=R(f^*)$$.

Question: What is known about Bayes-consistent classification in the cost-sensitive setting? For example, when $$\mathcal{X}$$ is a metric space and $$C(i,j)=1[i\neq j]$$, various nearest-neighbor methods are known to be strongly Bayes-consistent. Is anything known about other cost matrices?

I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $$L$$ and a link $$\psi$$. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis $$h$$. Then we define $$f(x) = \psi(h(x))$$. This procedure is roughly consistent if, as data $$\to \infty$$, we have $$f \to f^*$$.

The question is, given e.g. $$C$$, what are some nice, consistent surrogate losses? Example: for binary $$0-1$$ loss, one can use hinge loss or logistic loss as a surrogate, and one can show this is consistent as long as the hypothesis class is rich enough.

Tewari and Bartlett (2007) study multiclass classification, but I think not cost-sensitive, and relate consistency to calibration. A more recent work is Agarwal and Agarwal (2015), which has some more references.

[1] Tewari, Bartlett. On the Consistency of Multiclass Classification Methods. JMLR 2007. https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf

[2] A. Agarwal, S. Agarwal. On consistent surrogate risk minimization and property elicitation. COLT 2015. http://proceedings.mlr.press/v40/Agarwal15.pdf

• Thanks, @usul! I should read these carefully, but they all deal with the case where the labels are "atomic" -- i.e., have no cost/metric structure? – Aryeh Mar 24 at 21:40
• @Aryeh I think that's correct for Tewari and Bartlett, but Agarwal and Agarwal consider a general (finite-dimensional) "loss matrix" where predicting $t$ when the true label is $y$ gives loss $L(y,t)$. – usul Mar 25 at 1:41
• Great -- I'll accept it, and hopefully others will add further references that come up. – Aryeh Mar 25 at 8:38