Mistake-Driven Learning in Text Categorization
arXiv (Cornell University)Published 9 June 1997Open access
Ido Dagan, Yael Karov, Dan Roth
Citations33
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Learning problems in the text processing domain often map the text to a space whose dimensions are the measured fea- tures of the text, e.g., its words. Three characteristic properties of this domain are (a) very high dimensionality, (b) both the learned concepts and the instances reside very sparsely in the feature space, and (c) a high variation in the number of active features in an instance. In this work we study three mistake-driven learning algo- rithms for a typical task of this nature - text categorization. We argue
Keywords
Computer Science
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
Information and ComputationExponentiated Gradient versus Gradient Descent for Linear Predictors
880 Citations1997Jyrki Kivinen, Manfred K. Warmuth
The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+/-) has a much smaller loss if only a few components of the input are relevant for the predictions, which is quite tight already on simple artificial data.
An evaluation of phrasal and clustered representations on a text categorization task
547 Citations1992David Lewis
It is shown that optimal effectiveness occurs when using only a small proportion of the indexing terms available, and that effectiveness peaks at a higher feature set size and lower effectiveness level for a syntactic phrase indexing than for word-based indexing.
Context-sensitive learning methods for text categorization
253 Citations1996William W. Cohen, Yoram Singer
Automatic indexing based on Bayesian inference networks
128 Citations1993Kostas Tzeras, Stephan Hartmann
A Bayesian inference network model for automatic indexing with index terms (descriptors) from a prescribed vocabulary is presented, followed by an indexing example and some experimental results about the indexing performance of the network model.
arXiv (Cornell University)Applying Winnow to Context-Sensitive Spelling Correction
95 Citations1996Andrew R. Golding, Dan Roth
This paper applies a Winnow-based algorithm to a task in natural language: context-sensitive spelling correction, and finds that Winnow is better than Bayes at adapting to the unfamiliar test set, using a strategy for combining learning on the training set with unsupervised learning on the test set.
Elsevier eBooksEmpirical support for Winnow and Weighted-Majority based algorithms: results on a calendar scheduling domain
73 Citations1995Avrim Blum
A new variant on the Winnow algorithm is created that is especially suited to conditions with string-valued classifications, and an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
Machine LearningOn-line Prediction and Conversion Strategies
68 Citations1996Nicolò Cesa‐Bianchi, Yoav Freund +2 more
A deterministic algorithm using binomial weights that has a better worst case mistake bound than the best deterministic algorithm using exponential weights is presented.
Elsevier eBooksTracking the Best Expert**The authors were supported by NSF grant IRI-9123692.
30 Citations1995Mark Herbster, Manfred K. Warmuth
Elsevier eBooksComparing Several Linear-threshold Learning Algorithms on Tasks Involving Superfluous Attributes
19 Citations1995Nick Littlestone
Using simulations, several linear-threshold learning algorithms that differ greatly in the effect of superfluous attributes on their learning abilities are compared, including a Bayesian algorithm for conditionally independent attributes and two mistake-driven algorithms, Winnow and the Perceptron algorithm.