MU-SVM improves multiclass classification accuracy.
problem Multiclass classification problems.
method Proposes MU-SVM for multiclass learning and an analytic span bound for model selection.
result Achieves > 20% improvement in test accuracies compared to multi-class SVM.
New loss function calibrates WW-hinge loss for multiclass SVM.
problem WW-hinge loss not calibrated with 0-1 loss.
method Introduced ordered partition loss and proved WW-hinge loss is calibrated.
result WW-hinge loss is calibrated with ordered partition loss.
Unified SVM framework tackles multiclass and multilabel classification.
problem Extending SVM to handle multiclass and multilabel problems.
method Unified framework with class-specific weight vectors and penalizing patterns close to an origin.
result Unified framework achieves competitive performance for multiclass and multilabel classification.
New research shows SVM and related methods can overfit without harm in multiclass classification.
problem Understanding benign overfitting in multiclass classification.
method Analyzing three training algorithms: ERM with cross-entropy, least-squares, and one-vs-all SVM.
result All three algorithms can lead to classifiers that interpolate training data and have equal accuracy under high overparameterization.
Class ambiguity is typical in image classification problems with a large number of classes. When classes are difficult to discriminate, it makes sense to allow k guesses and evaluate classifiers based on the top-k error instead of the standard zero-one loss. We propose top-k multiclass SVM as a direct method to optimiz…
Exact solver speeds up Weston-Watkins SVM subproblem significantly.
problem Improving performance of Weston-Watkins multiclass SVM.
method Novel reparametrization for exact subproblem solving.
result Significant speed-up over state-of-the-art solvers for large number of classes.
Support vector machines (SVMs) have been recognized as a potential tool for supervised classification analyses in different domains of research. In essence, SVM is a binary classifier. Therefore, in case of a multiclass problem, the problem is divided into a series of binary problems which are solved by binary classifi…
The support vector machine (SVM) was originally designed for binary classifications. A lot of effort has been put to generalize the binary SVM to multiclass SVM (MSVM) which are more complex problems. Initially, MSVMs were solved by considering their dual formulations which are quadratic programs and can be solved by s…
In this paper, we consider asymptotic properties of the support vector machine (SVM) in high-dimension, low-sample-size (HDLSS) settings. We show that the hard-margin linear SVM holds a consistency property in which misclassification rates tend to zero as the dimension goes to infinity under certain severe conditions. …
We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including …
Adaptive caching strategy improves SVM training efficiency.
problem Expensive SVM training for large datasets.
method Proposed EFU and HCST caching strategies for kernel value reuse.
result HCST achieves 20% more reduction in training time.
A robust multiclass SVM tackles imbalanced data uncertainty.
problem Imbalanced multiclass classification with uncertain labels.
method Wasserstein distributionally robust optimization for multiclass SVM.
result Our model outperforms state-of-the-art OVA models in imbalanced settings.
Two SVM frameworks are introduced for classification problems.
problem Classifying data with nonparallel hyperplanes.
method Two SVM frameworks: separate and simultaneous construction of hyperplanes.
result Max-min distance-based NSVM for multiclass classification.
We prove new fast learning rates for the one-vs-all multiclass plug-in classifiers trained either from exponentially strongly mixing data or from data generated by a converging drifting distribution. These are two typical scenarios where training data are not iid. The learning rates are obtained under a multiclass vers…
Top-k error is currently a popular performance measure on large scale image classification benchmarks such as ImageNet and Places. Despite its wide acceptance, our understanding of this metric is limited as most of the previous research is focused on its special case, the top-1 error. In this work, we explore two direc…
Efficient skin lesion analysis combines deep CNN and handcrafted features.
problem Skin lesion analysis for melanoma detection.
method Combines deep learning and handcrafted features, introduces hybrid features.
result 0.841 score on validation dataset using SVM classifier.
Portable, Wearable and Wireless electrocardiogram (ECG) Systems have the potential to be used as point-of-care for cardiovascular disease diagnostic systems. Such wearable and wireless ECG systems require automatic detection of cardiovascular disease. Even in the primary care, automation of ECG diagnostic systems will …
In order to push the performance on realistic computer vision tasks, the number of classes in modern benchmark datasets has significantly increased in recent years. This increase in the number of classes comes along with increased ambiguity between the class labels, raising the question if top-1 error is the right perf…
Paper designs optimal ECOCs using IP for robust multiclass classification.
problem Designing robust ECOCs for multiclass classification.
method Integer Programming formulation to minimize codebooks with desirable error-correcting properties, leveraging graph-theoretic structure and edge clique covers.
result IP-generated codebooks achieve high nominal and robust adversarial accuracy.
The paper presents a new framework for complex Support Vector Regression as well as Support Vector Machines for quaternary classification. The method exploits the notion of widely linear estimation to model the input-out relation for complex-valued data and considers two cases: a) the complex data are split into their …
Novel method for multiclass ROC curves using multidimensional Gini index.
problem Multiclass performance evaluation, especially for imbalanced datasets.
method Extends ROC curve methodology to multiclass settings using multidimensional Gini index.
result Validated through case studies in health care and finance.
New research determines the optimal sample complexity for multiclass and list learning.
problem Determining the optimal sample complexity for multiclass classification.
method Algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.
result Proves a longstanding conjecture and determines the optimal dependence of sample complexity on DS dimension.
Unified binary and multiclass margin-based classification methods.
problem No consensus on multiclass loss functions analogous to binary margin loss.
method Showed multiclass loss functions can be expressed in relative margin form.
result Extended classification-calibration result to multiclass.
FOLKLORE algorithm speeds up online multiclass logistic regression.
problem Efficiently solving online multiclass logistic regression without high computational cost.
method Developed FOLKLORE algorithm with improved runtime and regret bound.
result First practical algorithm for online multiclass logistic regression.
API technique improves multiclass GAM interpretability.
problem Interpretability breakdown in multiclass GAMs.
method Developed two axioms and API technique for multiclass GAMs.
result API technique transforms multiclass GAMs to be visually interpretable.
Proposes a robust framework for multiclass classification.
problem General multiclass classification with adversarial robustness.
method Dual formulation as convex optimization with adversarial surrogate loss.
result Competitive performance in multiclass classification problems.
Enhanced word embeddings boost multiclass text classification accuracy.
problem Improving multiclass text classification accuracy using pre-trained embeddings.
method Proposed word-class embeddings (WCEs) to enhance pre-trained word embeddings.
result WCEs significantly improve multiclass text classification accuracy.
Study shows exponential error reduction in multiclass classification without bias-variance trade-off.
problem Multiclass classification with margin conditions.
method Analysis of classification error under hard-margin conditions.
result Exponential decrease in classification error without bias-variance trade-off.
New method debiases word embeddings for multiclass settings like race and religion.
problem Word embeddings in online texts perpetuate human stereotypes, including race and religion.
method Proposes a novel methodology to debias word embeddings in multiclass settings.
result Demonstrates robust multiclass debiasing that maintains NLP task efficacy.
This work shows how disentangled and sparse representations improve multi-task learning.
problem Improving generalization in multi-task learning with disentangled and sparse representations.
method Proved a new identifiability result and proposed a practical approach using sparsity-promoting bi-level optimization.
result Maximally sparse base-predictors yield disentangled representations under certain conditions.
The paper analyzes how overparameterized models can generalize well in multiclass classification.
problem Generalization in multiclass classification with overparameterized models.
method Survival/contamination analysis framework adapted for multiclass classification.
result Multiclass classification can generalize well even with many classes, unlike regression tasks.
New methods detect unfairness in multiclass classifiers using DCP.
problem Detecting unfairness in multiclass classifiers.
method Generalizes DCP to multiclass, provides optimization methods.
result Detects classifiers treating a significant fraction of the population unfairly.
New method for multiclass classification reduces error bounds.
problem High-dimensional multiclass classification with sparse coefficients.
method Sparse multinomial logistic regression with convex penalties.
result Plug-in classifiers achieve minimax generalization error bounds.
Study online multiclass classification under bandit feedback, extending previous results.
problem Online multiclass classification with bandit feedback, focusing on label space unboundedness.
method Extend Daniely and Helbertal's results, show necessity and sufficiency of Bandit Littlestone dimension for learnability.
result Sequential uniform convergence is necessary but not sufficient for bandit online learnability.
This work extends implicit bias analysis to multiclass classification using a new loss framework.
problem The implicit bias of gradient descent on multiclass data without explicit regularization.
method Employing the PERM framework to introduce a multiclass extension of the exponential tail property.
result Extended implicit bias result to multiclass classification using a new loss framework.
Paper studies multiclass classifiers from binary classifiers, proving methods and demonstrating advantages.
problem Constructing efficient multiclass classifiers from binary ones.
method Two methods: one vs. all and hierarchical classification, with a new leverage-hierarchical method introduced.
result Proves upper bounds and exact formulas for multiclass regret in terms of binary regrets.
New method boosts multiclass classification speed and accuracy.
problem Multiclass classification problem
method Factorized MultiClass Boosting (decomposing into regression tasks, solving with CART trees)
result Significantly faster and same quality as state-of-the-art solutions
Establishes a condition for multiclass classification-calibration of Gamma-Phi losses.
problem Ensuring classification-calibration of multiclass Gamma-Phi losses.
method Develops a general sufficient condition for classification-calibration of Gamma-Phi losses.
result Proves the first family of nonconvex multiclass surrogate losses for which classification-calibration has been fully justified.
Recent work has extended the theoretical analysis of boosting algorithms to multiclass problems and to online settings. However, the multiclass extension is in the batch setting and the online extensions only consider binary classification. We fill this gap in the literature by defining, and justifying, a weak learning…
Learnable multiclass hypothesis classes don't always have a sample compression scheme of fixed size.
problem The limitation of sample compression schemes for multiclass hypothesis classes.
method Analysis of DS dimension and sample compression schemes.
result Learnable multiclass hypothesis classes do not always have a sample compression scheme of fixed size.
Consistent algorithms for multiclass learning with complex metrics and constraints.
problem Learning with complex performance metrics and constraints.
method General framework for designing consistent algorithms by viewing the problem as an optimization over feasible confusion matrices.
result Rates of convergence to the optimal (feasible) classifier, showing asymptotic consistency.
In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle (SFO). We propose a general framework for such methods, for which we prove almost sure conve…
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Study extends binary omniprediction to multiclass setting with improved sample complexity.
problem Suboptimality bounds for each loss function against infinite comparator family in multiclass prediction.
method Design of a framework for solving Blackwell approachability problems with coupled actions.
result Sample complexity of ≈ε−(k+1) for ε-omniprediction in a k-class problem. Efficient algorithms for large-scale multiclass classification with linear classifiers.
problem Training ℓ1-regularized linear classifiers with high dimensionality and many classes. method Combines quasi-bilinear objective, stochastic mirror descent, and non-uniform sampling.
result Proposes a sublinear algorithm for multiclass hinge loss.
Paper proposes online algorithms for multiclass classification with partial labels.
problem Classifying data with partial labels.
method Avg Perceptron, Max Perceptron, Avg Pegasos, Max Pegasos algorithms.
result Mistake bounds for Avg Perceptron and regret bound for Avg Pegasos.
Proposes top-label calibration and M2B framework for multiclass to binary calibration.
problem Multiclass calibration and interpretation issues.
method Top-label calibration and M2B reduction framework.
result M2B + HB achieves lower calibration error than other methods.
We study consistency properties of surrogate loss functions for general multiclass learning problems, defined by a general multiclass loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning pro…