The Foundations of Cost-Sensitive Learning

The decision is a threshold, and the cost matrix carries one number. Predicting 1 is optimal when $(1-p)c_{10}+pc_{11}\le(1-p)c_{00}+pc_{01}$, which rearranges to $p\ge p^*$. Adding $k_j$ to the column of true class $j$ adds $k_jP(j\mid x)$ to both actions' expected costs (our reading, stronger than the paper's scaling and shifting invariance), so only the regrets $c_{10}-c_{00}$ and $c_{01}-c_{11}$ matter, and only through their ratio. Reasonableness puts $p^*$ in $(0,1)$ with class 1 predicted above it; a class whose row is entrywise at least another's is never worth predicting.

Costs need one baseline, and they can vary by example. The German credit matrix charges 1 for rejecting a good applicant, 5 for approving a bad one, and 0 on the diagonal. But denying a loan produces the same cash flow whatever the applicant would have done, so in a coherent matrix both entries of the "predict bad" row are equal; measuring benefits from the state before the decision avoids the error. In Elkan's card example, refusing a fraud is worth $+\$20$, refusing a legitimate customer $-\$20$, approving a fraud $-x$ and a legitimate purchase $+0.02x$ for amount $x$, and Step 1 gives $$\text{refuse}\iff P(\text{fraud}\mid x)\ \ge\ \frac{20+0.02x}{40+1.02x},$$ which is 0.5 at $x=0$, about 15% at \$100, about 3.8% at \$1,000, and tends to 2%. A threshold that moves with each transaction cannot come from any single rebalancing of the training set, only from a probability plus a per-example decision.

Under label shift the posterior is the old one reweighted by the prior ratio (Elkan's Theorem 2, and Saerens' correction). Equate the class densities in Bayes for the two populations, $p_t(\omega_i\mid x)p_t(x)/p_t(\omega_i)=p(\omega_i\mid x)p(x)/p(\omega_i)$. The unknown factor $p_t(x)/p(x)$ is common to all classes and fixed by normalization, so$$p(\omega_i\mid x)=\frac{\dfrac{p(\omega_i)}{p_t(\omega_i)}\,p_t(\omega_i\mid x)}{\sum_{j}\dfrac{p(\omega_j)}{p_t(\omega_j)}\,p_t(\omega_j\mid x)},\qquad\text{for two classes}\quad \operatorname{logit}p'=\operatorname{logit}p+\operatorname{logit}b'-\operatorname{logit}b,$$with $b,b'$ the old and new base rates. Elkan's page of algebra is this one line, and it uses nothing about the learner. He reads it as relaxing the assumption that training and test come from one population; it relaxes it only to label shift, where the class proportions move and nothing else does. In logits the correction adds the log prior ratio to each class, which is also the logit adjustment of Menon et al. (later in this section).

Rebalancing is a threshold move (Elkan's Theorem 1). Thinning the negatives is a base-rate change, so Step 3 applies. Multiplying the negatives by $k$ without changing their distribution divides the training odds by $k$, so a learner's rule $p_S\ge p_0$ reads $\operatorname{odds}(p)\ge k\,\operatorname{odds}(p_0)$, and making it act as $p\ge p^*$ needs$$k=\frac{p^*}{1-p^*}\cdot\frac{1-p_0}{p_0},$$which is $c_{10}/c_{01}$ for an accuracy learner with a zero diagonal (Breiman et al., 1984). With $p^*=0.05$ and an accuracy learner, keep one negative in 19 or weight negatives by 1/19. Read backward, a model trained with negatives kept at rate $r$ reports odds inflated by $1/r$, and multiplying its odds by $r$ recovers the population probability. Both directions need the thinning to leave $P(x\mid0)$ alone: random sampling or weights do, while choices that correlate with $x$ (keeping only low-score negatives, say) break the theorem.

For learners that estimate probabilities, rebalancing changes little. This part is argued, without experiments. A Bayesian classifier models each $P(x\mid j)$ separately, so rebalancing changes only the estimated $P(j)$, exactly a threshold move; naive Bayes ranks well but gives probabilities that are too extreme, so its threshold should be set empirically, which rebalancing to 0.5 cannot do. For tree splits with impurity $\alpha(p(1-p))^\beta$, Bayes inside each branch gives$$\frac{I(A)}{\alpha}=P(1)^\beta P(0)^\beta\sum_k P(a_k)^{1-2\beta}\,P(a_k\mid1)^\beta P(a_k\mid0)^\beta,$$so at $\beta=1/2$ the base rates factor out and the best split ignores them (Theorem 3), while for Gini ($\beta=1$) the mixture $P(a_k)$ brings them back. Prevalence matters at pruning instead, where C4.5 often reduces a tree with a rare class to a single leaf predicting the common class, and Laplace pruning (smooth a leaf with $k$ positives out of $n$ to $(k+1)/(n+2)$, prune when the parent's expected loss is below the children's total) is close to no pruning: without smoothing a parent's expected loss is never below its children's total, since the minimum of an average is at least the average of the minima. Hence the recommendation: train on the data as given, smooth the probabilities, and apply the threshold per example.

With unknown new priors, the likelihood in the priors is concave and EM finds its maximum. By the identity of Step 3, a deployment point has $p(x_k)=p_t(x_k)\sum_i\pi_ig_i(x_k)/p_t(\omega_i)$ with $\pi_i=p(\omega_i)$, and $p_t(x_k)$ does not involve $\pi$, so$$\ell(\pi)=\sum_{k=1}^N\log\sum_{i=1}^n\pi_i\,\frac{g_i(x_k)}{p_t(\omega_i)}+\text{const}.$$The classifier never has to produce a density, because $g_i(x_k)/p_t(\omega_i)$ is $p(x_k\mid\omega_i)$ up to a factor common to all classes. A sum of logs of linear functions is concave on the simplex, so the paper's worry that EM might stop at a local maximum does not apply (our observation, the standard fact about mixture weights with fixed components). EM treats the deployment labels as missing: the E-step computes the corrected posteriors at the current priors, and the M-step sets$$p^{(s+1)}(\omega_i)=\frac1N\sum_{k=1}^Np^{(s)}(\omega_i\mid x_k),$$starting from the training priors. A fixed point solves the score equation multiplied by $\pi_i$, and EM started inside the simplex converges to the maximizer, linearly and more slowly when the classes overlap; five iterations sufficed in the paper. The M-step shows how errors propagate: the estimated prior averages posteriors over the whole deployment set, so a systematic calibration error on the bulk of one class passes straight into it.

The competing method matches moments of hard decisions, and a likelihood ratio test asks whether the priors moved. The confusion-matrix method solves $p(\delta_i)=\sum_jp_t(\delta_i\mid\omega_j)p(\omega_j)$ for the new priors, using that a decision is a function of $x$, so its class-conditional law survives label shift. It needs only an invertible confusion matrix, so it stays consistent for a miscalibrated classifier, which EM does not (Lipton et al., shift section). Here the matrix is estimated on the training set, where the classifier looks more accurate than it is (both error rates too small), which plausibly pulls its estimates toward the balanced training prior (our reading, not tested in the paper). For the test, the shared factor $\prod_kp_t(x_k)$ cancels and$$2\log\frac{L}{L_t}=2\sum_{k=1}^N\log\sum_{i=1}^n\frac{\hat p(\omega_i)}{p_t(\omega_i)}\,p_t(\omega_i\mid x_k)$$is referred to $\chi^2_{n-1}$ under unchanged priors (Wilks); the paper adjusts only when it rejects, since adjusting under no shift cost a little accuracy. The null ignores miscalibration of the outputs, so on a very large deployment set a small calibration error alone will produce a rejection.

In the experiments, estimated priors shrink toward 50%, EM less than the confusion matrix, and adjustment recovers most of the lost accuracy. On Ringnorm with a small network trained on balanced data, a true 10% prior was estimated at 14.7% by EM and 18.1% by the confusion matrix, and accuracy rose from 90.1% unadjusted to 93.6% with EM, against 94.0% with the true priors; the test rejected in every shifted run and in none at 50%. On three medical data sets trained 50/50 and tested at 20/80, adjustment always helped. Nothing here covers priors below 10% or shifts that are not pure label shift.