The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
10.1162/jmlr.2003.3.4-5.951
Abstract
In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label's prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems. We discuss the form the algorithms take in the binary case and show that all the algorithms from the first family reduce to the Perceptron algorithm while MIRA provides a new Perceptron-like algorithm with a margin-dependent learning rate. We then return to multiclass problems and describe an analogous multiplicative family of algorithms with corresponding mistake bounds. We end the formal part by deriving and analyzing a multiclass version of Li and Long's ROMMA algorithm. We conclude with a discussion of experimental results that demonstrate the merits of our algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The perceptron: A probabilistic model for information storage and organization in the brain.
Rosenblatt, F. (1958) · Psychological Review · doi:10.1037/h0042519 · Cited by 12,280
Fast Training of Support Vector Machines Using Sequential Minimal Optimization
Platt, J. C. (1998) · Advances in Kernel Methods · doi:10.7551/mitpress/1130.003.0016 · Cited by 5,437
Pattern classification and scene analysis
Chien, Y. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,398
Advances in neural information processing systems 11
Peter Sollich, A. (1999) · Cited by 3,168
Solving Multiclass Learning Problems via Error-Correcting Output Codes
Dietterich, T. G., & Bakiri, G. (1995) · Journal of Artificial Intelligence Research · doi:10.1613/jair.105 · Cited by 2,739
Exponentiated Gradient versus Gradient Descent for Linear Predictors
Kivinen, J., & Warmuth, M. K. (1997) · Information and Computation · doi:10.1006/inco.1996.2612 · Cited by 864
Large Margin Classification Using the Perceptron Algorithm
Freund, Y., & Schapire, R. E. (1999) · Machine Learning · doi:10.1023/a:1007662407062 · Cited by 604
(2000) · Applied Physics Letters · doi:10.1162/15324430152733133 · Cited by 494
The Relaxed Online Maximum Margin Algorithm
Li, Y., & Long, P. M. (2002) · Machine Learning · doi:10.1023/a:1012435301888 · Cited by 225
The AdaTron: An Adaptive Perceptron Algorithm
Anlauf, J. K., & Biehl, M. (1989) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/10/7/014 · Cited by 207
Research works printed but not linked: 8
- Cortes C., 1995, Machine Learning, 20, 273
- 10.1162/15324430260185628 · doi:10.1162/15324430260185628
- T. Friess, N. Cristianini, and C. Campbell. The kernel-adatron: A fast and simple learning procedure for support vector machines. In Machine Learning: Proceedings of the Fifteenth International Conference, 1998.
- 10.1162/15324430260185600 · doi:10.1162/15324430260185600
- Littlestone N., 1988, Machine Learning, 2, 285
- N. J. Nilsson. Learning Machines: Foundations of trainable pattern classification systems. McGraw-Hill, New York, 1965.
- J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
- V. N. Vapnik. Statistical Learning Theory. Wiley, 1998.
Cited by
The Development and Psychometric Properties of LIWC2015
Pennebaker, J. W., Boyd, R. L., Jordan, K., & Blackburn, K. (2015) · University of Texas at Austin · doi:10.15781/t25p41 · Cited by 1,674
An Introduction to Conditional Random Fields
Sutton, C., & McCallum, A. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000013 · Cited by 564
Automatically profiling the author of an anonymous text
Argamon, S., Koppel, M., Pennebaker, J. W., & Schler, J. (2009) · Communications of the ACM · doi:10.1145/1461928.1461959 · Cited by 376
A brief survey of automatic methods for author name disambiguation
Ferreira, A. A., Gonçalves, M. A., & Laender, A. H. F. (2012) · ACM SIGMOD Record · doi:10.1145/2350036.2350040 · Cited by 293
Addressing age-related bias in sentiment analysis,
Diaz, M., Johnson, I., Lazar, A., Piper, A. M., & Gergle, D. (2018) · Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3173574.3173986 · Cited by 138
Metadata
- Venue
- CrossRef Listing of Deleted DOIs
- Publisher
- Unmaintained records
- Published
- 2000
- Volume
- 1
- ISSN
- 0003-6951 (ISSN-L)
- OpenAlex
- W1714704734
- Cited by
- 307
- References
- 13
- FWCI
- 3.33
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: 10.1162/jmlr.2003.3.4-5.951. https://app.cochat.ai/papers/10.1162/jmlr.2003.3.4-5.951
- The paper
- 10.1162/jmlr.2003.3.4-5.951. (2000). CrossRef Listing of Deleted DOIs. https://doi.org/10.1162/jmlr.2003.3.4-5.951
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.