Convex Calibrated Surrogates for the Multi-Label F-Measure

Introduction

• Fβ balances instance-level recall and precision using their possibly weighted harmonic mean in multi-label classification, where several labels may be active at once.Image tagging is an example, since an image can have multiple active tags.Source: §1 · p. 1
• Directly optimizing Fβ is computationally hard; binary relevance trains separate classifiers but ignores label correlations, motivating other approaches.Binary relevance treats labels independently.Source: §1 · p. 1
• For s labels, the Fβ loss matrix has rank at most s^2+1, enabling a convex calibrated surrogate based on s^2+1 binary class-probability estimation problems.Using a suitable binary surrogate, such as binary logistic regression, constructs an (s^2+1)-dimensional surrogate.Source: §1 · pp. 1–2
• The regret-transfer bound carries guarantees from the binary subproblems to overall Fβ-regret, so consistent binary learners yield a consistent multi-label learner.The authors describe their analysis as, to their knowledge, the first quantitative regret-transfer bound for calibrated Fβ surrogates.Source: §1 · p. 2
• Both algorithms estimate the same s^2+1 statistics, despite using different CPE reductions, and Dembczynski et al. (2013)'s algorithm also admits a convex calibrated-surrogate interpretation.The paper views its own algorithm as a plug-in method and reports that both algorithms perform similarly in experiments.Source: §1 · p. 2

Bayes optimal multi-label classifiers

• Dembczynski et al. (2011) showed that s^2 + 1 conditional-label statistics suffice for an F1-optimal classifier, computable in O(s^3) time, and extended the result to Fβ.They also studied Bayes-optimal classifiers for Hamming loss and subset 0-1 loss.Source: §2 · p. 2

Consistent algorithms for multi-label learning

• Dembczynski et al. (2013) estimated the required statistics using s multiclass CPE problems with at most s + 1 classes and one binary CPE, then plugged them into the O(s^3) procedure as the consistent EFP algorithm.Binary relevance is consistent for Hamming loss and, under conditional label independence, Fβ, but can be arbitrarily bad otherwise.Source: §2 · p. 2

Large-margin algorithms for multi-label learning

• RML and SML use StructSVM, but were proven inconsistent for Fβ and outperformed by EFP; Wu & Zhou (2017) proposed LIMO, which the paper compares in experiments.RML and SML are due to Petterson & Caetano (2010; 2011), while StructSVM is due to Tsochantaridis et al. (2005).Source: §2 · p. 2

Multivariate Fβ-measure for binary classification

• Binary-classification approaches also target multivariate Fβ under class imbalance, a use related to but distinct from Fβ in multi-label classification.Source: §2 · p. 2

Consistent algorithms for multi-label learning

• Koyejo et al. (2015) study Fβ under expected utility maximization, whereas this paper uses decision-theoretic analysis; their results are generally incomparable, and thresholding is not optimal for general distributions under DTA.Under EUM, Koyejo et al. (2015) showed thresholding yields Bayes-optimal performance; under DTA, Dembczynski et al. (2011) showed it cannot be optimal for general distributions.Source: §2 · p. 2

Convex calibrated surrogates

• Prior work developed calibrated surrogates for binary, multiclass, subset-ranking, and multi-label problems; Ramaswamy et al. (2014) designed output-coding surrogates for multiclass problems with low-rank loss matrices.The paper draws on that low-rank loss-matrix result to develop its approach.Source: §2 · p. 3

3.1. Problem Setup

• For an s-label problem, each instance has a binary vector of active labels, and Fβ balances recall and precision through a weighted harmonic mean.F1 weights recall and precision equally; F2 favors recall, while F0.5 favors precision.Source: §3.1 · p. 3
• The goal is to minimize Fβ-regret for instance-averaged performance, using a convex surrogate because directly maximizing the discrete measure is computationally hard.A consistent algorithm should drive Fβ-regret to zero as the number of training examples increases.Source: §3.1 · p. 3, §3.2 · p. 3

3.2. Convex Calibrated Surrogates for Multiclass Problems

• A convex surrogate and decoder are L-calibrated when surrogate consistency implies L-consistency, yielding a route to universally L-consistent algorithms with suitable function classes and regularization.The framework minimizes surrogate risk over scoring functions and then decodes their scores into predictions.Source: §3.2 · p. 4
• For a multiclass loss matrix of rank r, Ramaswamy et al. (2014) provide r-dimensional convex calibrated surrogates that decompose the problem into r binary class-probability estimation tasks.The construction uses strictly proper composite binary losses; the paper uses binary logistic loss for these tasks.Source: §3.2 · p. 4

• A slightly shifted Fβ-loss matrix has rank at most s² + 1.The learning problem is treated analytically as a multiclass problem with 2^s classes, although the resulting algorithms use only O(s²) real-valued score functions.Source: §4 · p. 4
• The rank result yields a family of (s² + 1)-dimensional convex calibrated surrogates, constructed from any strictly proper composite binary loss.The surrogate and its decoding map are calibrated for the Fβ loss.Source: §4 · p. 5
• With a universal function class and suitable regularization, surrogate risk minimization is consistent for the Fβ-measure and solves s² + 1 binary CPE problems with standard binary labels.The labels are non-probabilistic binary labels.Source: §4 · p. 5
• The decoding map runs in O(s³) time and applies the procedure of Dembczynski et al. (2011) to estimates of the same s² + 1 statistics used for Bayes-optimal Fβ prediction.This makes the algorithm a plug-in multi-label classifier for the Fβ-measure.Source: §4 · p. 5

5. Regret Transfer Bound

• The logistic loss satisfies the condition with λ = 4 and the logit link.The section identifies the condition as relatively mild and notes that several common strictly proper composite losses satisfy it.Source: §5 · p. 6
• For every distribution D and model f, Theorem 5 bounds Fβ-regret by sqrt(2(ln s + 1) regretψ_D[f] / λ) when φ is λ-strongly proper composite.The target classifier is decode composed with f.Source: §5 · p. 6
• Theorem 5 also provides a self-contained proof that the surrogate-mapping pair (ψ, decode) is LFβ-calibrated.The transfer bound implies calibration for sequences of models learned from increasingly large training samples.Source: §5 · p. 7

6. Relationship with Plug-in Algorithm of Dembczynski et al. (2013)

• EFP estimates the first statistic with binary logistic regression and the remaining s statistics via s multiclass logistic-regression CPE problems with s+1 classes; our s^2+1 components use binary CPE.Source: §6 · p. 7
• Both methods can restrict estimation to small k in sparse-label data: EFP uses the training-set maximum number of active labels, while ours keeps k values observed in training.Source: §6 · p. 7
• The proposed method estimates q_jk(x)=P(||y||_1=k, y_j=1|x), matching EFP’s core statistics needed for a Bayes-optimal multi-label Fβ classifier.Source: §6 · p. 7

7.1. Synthetic Data: Convergence to Bayes Optimal F1

• With logistic binary loss and a linear function class, the algorithm converged to Bayes-optimal F1 as synthetic training samples grew.The synthetic data used six labels, and its 37 statistics needed for Bayes-optimal prediction were generated from a linear function of the 100-dimensional input; F1 was measured on 15,000 test points.Source: §7.1 · pp. 7–8

7.2. Real Data: Comparison with Other Algorithms

• The benchmark evaluation used prescribed train/test splits and instance-averaged F1, comparing linear models for our algorithm, EFP, LIMO, and binary relevance (BR).Regularization parameters were selected by five-fold cross-validation on training data.Source: §7.2 · p. 8
• On Mulan benchmarks, our algorithm performed similarly to EFP; BR was generally relatively weak, while LIMO was sometimes competitive (Table 2).For Birds, both our algorithm and EFP used full estimation of all s^2 + 1 statistics because estimating only statistics corresponding to observed label counts performed poorly.Source: Table 2 · p. 8, §7.2 · p. 8

8. Conclusion

• The proposed convex calibrated surrogates decompose Fβ learning over s labels into at most s^2+1 binary class probability estimation problems.A quantitative regret transfer bound carries regret guarantees for the binary learners to the overall Fβ learner.Source: §8 · p. 8
• The algorithm can also be viewed as a plug-in approach to Fβ and applied to binary sequence labeling tasks where Fβ is useful.The paper relates this perspective to the EFP algorithm of Dembczynski et al. (2013), though from a different viewpoint.Source: §8 · p. 8

Implementation of ‘decode’

• The learned score is transformed through the inverse link to estimate the s^2+1 conditional statistics used by the decode procedure.The procedure of Dembczynski et al. (2011) computes a Bayes-optimal F1 prediction from those statistics and generalizes easily to Fβ.Source: Implementation of ‘decode’ · p. 11
• Dembczynski et al. (2011) provide an O(s^3)-time procedure for computing a Bayes-optimal F1 prediction from the s^2+1 statistics.The approach generalizes easily to Fβ; decode applies it to statistics estimated from the training sample.Source: Implementation of ‘decode’ · p. 11
• The combinatorial search is stratified into s+1 sets, one for each possible number of predicted labels from 0 through s.For an input vector u, each set contains predictions with a fixed number of active entries.Source: Implementation of ‘decode’ · p. 11
• Within the set for cardinality l, the optimal prediction sets to 1 the l entries corresponding to the smallest T_jl values.The remaining entries are set to 0.Source: Implementation of ‘decode’ · p. 11
• The cardinality subproblems take O(s^2 ln(s)) time in total, while computing the s^2 values T_jl takes O(s^3) time.The algorithm computes T by matrix multiplication QV.Source: Implementation of ‘decode’ · p. 11
• Faster matrix multiplication taking o(s^3) time is possible in principle but would help in practice only for extremely large s.Source: Implementation of ‘decode’ · p. 11