On the Consistency of Multiclass Classification Methods

By Ambuj Tewari, Peter L. Bartlett. 2007

367 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Evaluation & Benchmarks

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, background): “Consistency of convex surrogates has been the central question of many studies for such problems as binary classification [2, 24, 19], multi-class classification [23, 21, 1, 17], ranking [11, 4, 5, 18, 15] and, more recently, structured prediction [7, 14].”
On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, background): “The consistency of convex surrogates is well understood in the case of binary classification [50, 5, 43] and there is significant progress in the case of multi-class 0-1 loss [49, 46] and general multi∗DI École normale supérieure, CNRS, PSL Research University †National Research University Higher Sc”
Why ReLU Networks Yield High-Confidence Predictions Far Away From the Training Data and How to Mitigate the Problem (2018, background): “Another approach is the introduction of a rejection option into the classifier [32, 4], in order to avoid decisions the classifier is not certain about.”
Spectrally-normalized margin bounds for neural networks (2017, methodology): “Additionally, the present work operates in the multiclass setting, and avoids an explicit dependence on the number of classes k , which seems to appear in prior work (Zhang, 2004; Tewari and Bartlett, 2007).”
Houdini: Fooling Deep Structured Prediction Models (2017, background): “(1) The use of differentiable surrogates is satisfactory for classification because the relationship between such surrogates and the classification accuracy is well established [34].”
Robust Boosting Algorithm Against Mislabeling in Multiclass Problems (2008, methodology): “For the multi-class problem, the concept of the classification calibrated was proposed [13].”
A Hybrid Loss for Multiclass and Structured Prediction (2014, background): “But SVMs could be inconsistent when there are more than two classes [18, 11].”
Does Distributionally Robust Supervised Learning Give Robust Classifiers? (2016, methodology): “We ﬁrst review Proposition 1 by Bartlett et al. (2006) and Tewari & Bartlett (2007) that justiﬁes the use of classiﬁcation-calibrated losses in ERM for classiﬁcation.”
Knowing what you know: valid confidence sets in multiclass and multilabel prediction (2020, neutral): “[2, 36, 31]), so that s(x, y) > s(x, y′) whenever P (Y = y | X = x) > P (Y = y′ | X = x).”
Statistical Analysis of Bayes Optimal Subset Ranking (2008, background): “Section II discusses earlier work in statistics and machine learning on global and pair-wise ranking.”
Consistent Multiclass Algorithms for Complex Performance Measures (2015, background): “…work has focused on lossbased performance measures, including binary/multiclass 0-1 loss (Bartlett et al., 2006; Zhang, 2004a;b; Lee et al., 2004; Tewari & Bartlett, 2007), losses for specific problems such as multilabel classification (Gao & Zhou, 2011) and ranking (Cossock & Zhang, 2008; Xia…”
Calibrated asymmetric surrogate losses (2012, background): “The case γ = 1 was treated by Bartlett, Jordan and McAuliffe [2], yielding α(1) = 12 .”
Towards good practice in large-scale learning for image classification (2012, methodology): “There exist several flavors of the multiclass SVM including the Weston and Watkins [39] and the Crammer and Singer [10] formulations (see [31] for a comprehensive review).”
Multi-Class Deep Boosting (2014, background): “Tewari and Bartlett [2007] (see also [Zhang, 2004a,b]) showed that, in general, loss functions of the form (s1, . . . , sc, y) 7→ Φ(−(sy − maxy′ 6=y sy′)) are not consistent, while those that can be written as (s1, . . . , sc, y) 7→ ∑ y′ 6=y Φ(−(sy − sy′)) are consistent under some additional regula”
Robust Truncated Hinge Loss Support Vector Machines (2007, background): “Zhang (2004); Tewari and Bartlett (2005) pointed out Fisher inconsistency of H1(min g(f(x), y)).”
Robust Bi-Tempered Logistic Loss Based on Bregman Divergences (2019, background): “2 Bayes-risk consistency Another important property of a multiclass loss is the Bayes-risk consistency [19].”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “Such guarantees are thus both non-asymptotic and hypothesis set-specific and therefore more informative than Bayes consistency guarantees (Zhang, 2004a; Bartlett et al., 2006; Steinwart, 2007; Tewari & Bartlett, 2007).”