The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
A Winnow-Based Approach to Context-Sensitive Spelling Correction
Open accessAbstract
A large class of machine-learning problems in natural language require the characterization of linguistic context. Two characteristic properties of such problems are that their feature space is of very high dimensionality, and their target concepts depend on only a small subset of the features in the space. Under such conditions, multiplicative weight-update algorithms such as Winnow have been shown to have exceptionally good theoretical properties. In the work reported here, we present an algorithm combining variants of Winnow and weighted-majority voting, and apply it to a problem in the aforementioned class: context-sensitive spelling correction. This is the task of fixing spelling errors that happen to result in valid words, such as substituting to for too, casual for causal, and so on. We evaluate our algorithm, WinSpell, by comparing it against BaySpell, a statistics-based method representing the state of the art for this task. We find: (1) When run with a full (unpruned) set of features, WinSpell achieves accuracies significantly higher than BaySpell was able to achieve in either the pruned or unpruned condition; (2) When compared with other systems in the literature, WinSpell exhibits the highest performance; (3) While several aspects of WinSpell's architecture contribute to its superiority over BaySpell, the primary factor is that it is able to learn a better linear separator than BaySpell learns; (4) When run on a test set drawn from a different corpus than the training set was drawn from, WinSpell is better able than BaySpell to adapt, using a strategy we will present that combines supervised learning on the training set with unsupervised learning on the (noisy) test set.
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
Cortes, C., & Vapnik, V. (1995) · Machine Learning · doi:10.1007/bf00994018 · Cited by 59,421
A decision-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1504 · Cited by 20,466
Statistical Methods for Rates and Proportions
Fleiss, J. L., Levin, B., & Paik, M. C. (2003) · Wiley Series in Probability and Statistics · doi:10.1002/0471445428 · Cited by 18,646
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
(1967) · Medical Entomology and Zoology · Cited by 7,532
Building a Large Annotated Corpus of English: The Penn Treebank
Marcus, M. (1993) · doi:10.21236/ada273556 · Cited by 7,405
Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms
Dietterich, T. G. (1998) · Neural Computation · doi:10.1162/089976698300017197 · Cited by 3,840
On the Optimality of the Simple Bayesian Classifier under Zero-One Loss
Domingos, P., & Pazzani, M. (1997) · Machine Learning · doi:10.1023/a:1007413511361 · Cited by 3,101
A desicion-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-59119-2_166 · Cited by 2,252
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Estimation of probabilities from sparse data for the language model component of a speech recognizer
Katz, S. (1987) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1987.1165125 · Cited by 1,637
Improved backing-off for M-gram language modeling
Kneser, R., & Ney, H. (2002) · 1995 International Conference on Acoustics, Speech, and Signal Processing · doi:10.1109/icassp.1995.479394 · Cited by 1,473
Techniques for automatically correcting words in text
Kukich, K. (1992) · ACM Computing Surveys · doi:10.1145/146370.146380 · Cited by 1,257
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
An empirical study of smoothing techniques for language modeling
Chen, S. F., & Goodman, J. (1996) · Proceedings of the 34th annual meeting on Association for Computational Linguistics - · doi:10.3115/981863.981904 · Cited by 770
An Empirical Study of Smoothing Techniques for Language Modeling
Chen, S. F., & Goodman, J. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.cmp-lg/9606011 · Cited by 612
Herbster, M., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007424614876 · Cited by 560
A method for disambiguating word senses in a large corpus
Gale, W. A., Church, K., & Yarowsky, D. (1992) · Computers and the Humanities · doi:10.1007/bf00136984 · Cited by 532
On structuring probabilistic dependences in stochastic language modelling
Ney, H., Essen, U., & Kneser, R. (1994) · Computer Speech & Language · doi:10.1006/csla.1994.1001 · Cited by 517
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
Integrating multiple knowledge sources to disambiguate word sense
Ng, H. T., & Lee, H. B. (1996) · Annual Meeting of the Association for Computational Linguistics (ACL) · doi:10.3115/981863.981869 · Cited by 408
Yarowsky, D. (1994) · Proceedings of the 32nd annual meeting on Association for Computational Linguistics - · doi:10.3115/981732.981745 · Cited by 356
Concept learning and the problem of small disjuncts
Holte, R. C., Acker, L., & Porter, B. (1989) · Cited by 351
Context based spelling correction
Mays, E., Damerau, F. J., & Mercer, R. L. (1991) · Information Processing & Management · doi:10.1016/0306-4573(91)90066-u · Cited by 266
Additive versus exponentiated gradient updates for linear prediction
Kivinen, J., & Warmuth, M. K. (1995) · Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 · doi:10.1145/225058.225121 · Cited by 223
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.37 · Cited by 186
Learning to Resolve Natural Language Ambiguities: A Unified Approach
Roth, D. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/9811010 · Cited by 173
Self-citationMistake-Driven Learning in Text Categorization
Dagan, I., Karov, Y., & Roth, D. (1997) · arXiv (Cornell University) · doi:10.48550/arxiv.cmp-lg/9706006 · Cited by 171
Self-citationActive Learning with Committees for Text Categorization
Liere, R., & Tadepalli, P. V. (1997) · Cited by 146
Random House unabridged dictionary
Flexner, S. B., & Hauck, L. C. (1993) · Random House eBooks · Cited by 146
A Bayesian hybrid method for context-sensitive spelling correctionPreprint
Golding, A. R. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.cmp-lg/9606001 · Cited by 113
Self-citationLearning Boolean Functions in an Infinite Attribute Space
Blum, A. L. (1992) · Machine Learning · doi:10.1007/bf00994112 · Cited by 86
Contextual spelling correction using latent semantic analysis
Jones, M. P., & Martin, J. (1997) · Conference on Applied Natural Language Processing · doi:10.3115/974557.974582 · Cited by 65
Valiant, L. G. (1995) · Conference on Learning Theory · doi:10.1145/225298.225299 · Cited by 13
Cited by
Li, X., & Roth, D. (2002) · Proceedings of the 19th international conference on Computational linguistics - · doi:10.3115/1072228.1072378 · Cited by 1,234
Self-citationScaling to very very large corpora for natural language disambiguation
Banko, M., & Brill, E. (2001) · Proceedings of the 39th Annual Meeting on Association for Computational Linguistics - ACL '01 · doi:10.3115/1073012.1073017 · Cited by 675
An improved error model for noisy channel spelling correction
Brill, E., & Moore, R. C. (2000) · Proceedings of the 38th Annual Meeting on Association for Computational Linguistics - ACL '00 · doi:10.3115/1075218.1075255 · Cited by 531
The Importance of Syntactic Parsing and Inference in Semantic Role Labeling
Punyakanok, V., Roth, D., & Yih, W.-T. (2008) · Computational Linguistics · doi:10.1162/coli.2008.34.2.257 · Cited by 391
Self-citationNormalization of non-standard words
Sproat, R., Black, A. W., Chen, S., Kumar, S., Ostendorf, M., & Richards, C. D. (2001) · Computer Speech & Language · doi:10.1006/csla.2001.0169 · Cited by 342
Metadata
- Authors
- Golding, A. R., & Roth, D.
- Venue
- Machine Learning
- Published
- 1999-02
- Volume
- 34
- Issue
- 1-3
- Pages
- 107-130
- ISSN
- 0885-6125 (ISSN-L)
- 1573-0565
- OpenAlex
- W2118996379
- Cited by
- 291
- References
- 35
- FWCI
- 17.50
- Type
- journal article
- Language
- en
- Open access
- bronze
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
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.