Error-Budgeted Classifier Chains

Many classification tasks attach several labels to one input: a chest X-ray can show several diseases, and a news article can belong to several topics. These labels are correlated, and a common way to use that correlation is a classifier chain. A chain predicts labels one at a time and feeds each prediction to the classifiers that come after it. At test time the earlier predictions are sometimes wrong. A wrong early prediction then corrupts every later decision that depends on it, the same snowball effect seen in step-by-step time-series forecasting. The standard way to decide which labels a classifier should look at is to measure how strongly the true labels depend on each other. This proposal argues that this is the wrong criterion. A classifier should condition on an earlier label only when the information it gains from that label outweighs the damage done by the label's own prediction errors. Both quantities can be measured directly on held-out data.

The point matters because the literature contains an unresolved tension. Rectifying Classifier Chains found that strong label dependence is "a double-edged sword": the more a later classifier relies on an earlier label, the more an error in that label hurts it. Yet FACT and Copula Multi-label Learning show that enforcing dependency structure corrects noisy predictions for individual labels. We propose a per-edge quantity that says which regime a given pair of labels is in. We then build chains whose links are kept only where that quantity is positive.

Core Claim

For a candidate parent label $i$ and child label $j$, define the held-out net gain

$$\Delta_{ij} = \underbrace{\big[L(y_j \mid x) - L(y_j \mid x, y_i)\big]}_{\text{oracle gain } G_{ij}} - \underbrace{\big[L(y_j \mid x, \hat y_i^{\mathrm{cf}}) - L(y_j \mid x, y_i)\big]}_{\text{error cost } C_{ij}},$$

where $L(\cdot)$ is the held-out log loss of a classifier for label $j$ given the listed inputs, $x$ is the input, $y_i$ is the true parent label, and $\hat y_i^{\mathrm{cf}}$ is a cross-fitted prediction of $y_i$. A cross-fitted prediction comes from a model that never saw that example during training. The two bracketed terms cancel algebraically, so $\Delta_{ij}$ is simply the improvement from conditioning on the predicted parent. The decomposition is the useful part: it separates "how much $y_i$ tells us about $y_j$ beyond $x$" from "how much the parent's mistakes cost."

Our claim has two parts. First, $C_{ij}$ grows roughly with the product of the child's sensitivity to the parent and the parent's error rate. Edges with large $G_{ij}$ therefore tend to have large $C_{ij}$ as well, which is Senge et al.'s paradox in quantitative form. Second, a chain that keeps only edges with $\Delta_{ij} > 0$ will beat chains whose structure is chosen by dependency strength alone. The edge selection must respect acyclicity and use calibrated parent probabilities as inputs. The gain should show most on subset accuracy (getting the whole label set exactly right) and at late chain positions.

This differs from the closest work, Recurrent Bayesian Classifier Chains (RBCC). RBCC learns a directed acyclic graph over the parts of each label not explained by $x$, and conditions each label only on its graph parents. That graph is fit to true labels, so it encodes $G_{ij}$ and is blind to $C_{ij}$. RBCC is our method-supplying predecessor: we reuse its sparse-parent idea and change the criterion for which parents to keep.

Research Program

The first component is analysis. On a synthetic generator, we control two things independently: the dependence of $y_j$ on $y_i$ given $x$, and the accuracy of the classifier for $y_i$. We will map where $\Delta_{ij}$ changes sign. We will then check whether a simple product of sensitivity and parent error rate predicts $C_{ij}$. That product is the first-order expansion of the child's loss around the true parent value, so it should be accurate only when parent errors are rare. On the real benchmarks, we will compute $G$, $C$ and $\Delta$ for every label pair. This tells us whether the strongest-dependence edges are disproportionately net-harmful.

The second component is the model. We estimate $\Delta_{ij}$ with $K$-fold cross-fitting. Training with cross-fitted predictions, rather than the in-sample shortcut Senge et al. used, also avoids parents that look unrealistically accurate during training. Finding the best graph is NP-hard (Classifier Chains: A Review and Perspectives), so we do not search for it. Instead, we greedily add the edge with the largest positive $\Delta_{ij}$ that does not create a cycle, and re-estimate $\Delta$ for affected children after each round. We stop when no remaining edge has a positive gain beyond a bootstrap confidence threshold. Parents are passed to children as calibrated probabilities, not hard labels. Inference is a single pass in topological order, optionally with a small beam search for subset accuracy. The extra cost is roughly $K$ times training, which we will report.

Baselines

The naive reference is Binary Relevance, which trains one independent classifier per label on the same backbone. It cannot accumulate errors and sets the floor any chain must clear. Second is a standard classifier chain with random and frequency-based orderings, trained on true predecessor labels. Third is Nested Stacking from Rectifying Classifier Chains, which trains each link on predicted predecessors. We run it in both the original within-sample form and a fully cross-fitted form. The cross-fitted form uses all predecessors and is the most important control, because it isolates edge selection from cross-fitting.

The strongest structured competitor is RBCC. It reports subset accuracy of 0.653 on Scene, 0.240 on Yelp and 0.594 on PASCAL VOC 2007, against 0.610 for order-free recurrent chains on Scene (Recurrent Bayesian Classifier Chains). For sequence-style decoding, we include Optimal Completion Distillation from Order-Free Learning, which reports an average score of 0.682 on AAPD versus 0.662 for standard sequence-to-sequence decoding. Two ablations isolate the key ingredient. One builds the same greedy graph using $G_{ij}$ instead of $\Delta_{ij}$. The other uses $\Delta$-selected edges but feeds hard labels.

All methods share the backbone, the data splits, and a fixed hyperparameter search budget per method. Wall-clock training budgets will be reported, so the $K$-fold overhead is visible. Beating the field means two things. On Scene, Yelp and VOC we need higher mean subset accuracy than RBCC's reported numbers and than our own rerun of RBCC, over five seeds with non-overlapping confidence intervals. On the tabular suite we need to beat cross-fitted Nested Stacking with all predecessors.

Why not just…?

Why not just use Binary Relevance and avoid feedback entirely? Binary Relevance cannot snowball, but it also cannot get the label set jointly right. RBCC's gains over unstructured chains, and Senge et al.'s gains of chains over Binary Relevance under moderate dependence, show that conditioning pays when it is done selectively. Our method includes Binary Relevance as a special case: with no positive $\Delta$, the graph is empty. On datasets where it learns almost no edges, matching Binary Relevance is the expected and honest outcome.

Why not just use cross-fitted Nested Stacking, since a child trained on noisy parents should learn to down-weight them? This is the real threat. In principle a well-fit child learns the trust weights itself, which would make explicit pruning redundant. Our counterargument is statistical. With many predecessors and few positive examples per label, a long tail the review flags as an open problem, the child cannot reliably learn to ignore dozens of noisy inputs. Explicit pruning removes that variance. The decisive comparison is the second baseline above. If edge selection gives no gain over cross-fitted all-predecessor stacking, especially on medical, enron and bibtex with their many labels, we will report the contribution as "cross-fitting is what matters" and drop the selection claim.

Why not just model dependencies in the output rather than the input, for example with copulas or subset correction? Copula Multi-label Learning models joint label structure without chaining, but it scales poorly as the number of labels grows. Subset correction can only output label combinations seen in training. Order-Free Learning shows that producing unseen combinations matters, with 30 unseen combinations on AAPD versus 1 for the baseline. We include Copula Multi-label Learning on the five datasets it used (emotions, scene, medical, yeast, enron), for which no reported result was found on Lacuna. We also count the unseen combinations each method produces.

Proposed Experiments

We use Scene, Yelp and PASCAL VOC 2007 for comparison with RBCC, AAPD for comparison with Optimal Completion Distillation, and the tabular suite of emotions, yeast, enron, medical, bibtex, genbase, mediamill and slashdot for comparison with Nested Stacking. Nested Stacking improved Hamming loss on 8 of 11 datasets, but no per-dataset values were found on Lacuna. Metrics are subset accuracy, Hamming loss, example-F1 and macro-F1, and position-wise accuracy along the topological order, following Tsai and Lee's analysis.

Three checks are decisive. First, the held-out $\Delta_{ij}$ must rank-correlate with the realized change in test loss when each edge is added. If it does not, the criterion fails. Second, on real data, edges with high $G$ but negative $\Delta$ must exist. Removing them must help, while removing edges selected by $\Delta$ must hurt. This would directly settle the double-edged-sword tension. Third, accuracy at late chain positions should stay flat rather than decline as it does for standard chains.

If these hold in classification, a short follow-up would test the same edge criterion on multivariate step-by-step forecasting on ETTh1 and Weather. There the "labels" are variables and steps fed back from earlier predictions, and the reference is the iterative Evolutionary Forecasting from To See Far, Look Close, which reports up to 13.92% improvement over direct forecasting.