Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

By Nick Littlestone. 1987

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

Natural Language Processing (Almost) from Scratch (2011, methodology): “Koomen et al. (2005) hold the state-of-the-art with Winnow-like (Littlestone, 1988) classifiers, followed by a decoding stage based on an integer program that enforces specific constraints on SRL tags.”
Security analysis of online centroid anomaly detection (2010, background): “On the other hand, several examples of effective attacks have been demonstrated in the context of specific security and spam detection applications (Lowd and Meek, 2005a; Fogla et al., 2006; Fogla and Lee, 2006; Perdisci et al., 2006; Newsome et al., 2006; Nelson et al., 2008), which has motivated…”
Learning Optimized Or's of And's (2015, background): “The closest work to ours are that of Hauser et al. (2010) in the marketing literature, and Wang et al. (2015) on Bayesian modeling of DNF formulae.”
Paragraph: Thwarting Signature Learning by Training Maliciously (2006, positive): “One approach that bears further investigation is Winnow [11, 12], a machine learning algorithm with proven bounds on the number of mistakes made before generating an accurate classifier.”
Learning in the presence of malicious errors (1988, background): “Littlestone [16] shows that the Vapnik-Chervonenkis dimension ofM s n is (s ln(1+n=s)).”
Kernel Methods for Relation Extraction (2002, methodology): “3 Linear Methods Configuration We evaluated three feature-based algorithms for learning linear discriminant functions: Naive-Bayes (Duda and Hart, 1973), Winnow (Littlestone, 1987), and SVM.”
Regularization Techniques for Learning with Matrices (2009, background): “In the context of learning vectors (rather than matrices), the study of the relative performance of different regularization techniques based on properties of a given task dates back to Littlestone [1988], Kivinen and Warmuth [1997].”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “In online learning (Littlestone, 1988), the algorithm receives training instances one at a time and updates at each step the current hypothesis.”
Hardness of Learning Halfspaces with Noise (2006, methodology): “In practice, simple incremental algorithms such as the famous Perceptron Algorithm [1, 18] or the Winnow algorithm [17] are often used.”
A Survey of Methods for Scaling Up Inductive Algorithms (1999, unknown): “For example, the well-known algorithm WINNOW (Littlestone, 1988) is not only effective at detecting irrelevant features, it is also incremental; it should be straightforward to augment the algorithm to reduce the number of features automatically as the number of examples grows (thus keeping the tota”
Online Machine Learning in Big Data Streams (2018, background): “ing algorithms can naturally adapt to evolving distributions. However, adaptation happens only as the old concepts are diluted due to the new incoming data, which is more suitable for gradual changes [162, 73]. For sudden changes, algorithms that maintain a sliding window of the last seen instances ”
Efficient bandit algorithms for online multiclass prediction (2008, methodology): “We conjecture that it is relatively straightforward to adapt the multiplicative update scheme [Littlestone, 1988, Kivinen and Warmuth, 1997] to the bandit setting while achieving mistake bounds similar to the mistake bounds we derived for the Banditron.”
Learning to detect objects in images via a sparse, part-based representation (2004, methodology): “SNoW learns a linear function over the feature space using a variation of the feature-efficient Winnow learning algorithm [28]; it allows input vectors to specify only active features, and as is the case for Winnow, its sample complexity grows linearly with the number of relevant features and only l”
Online learning with kernels (2001, methodology): “Mesterharm [15] has considered tracking arbitrary linear classifiers with a variant of Winnow [16], and Bousquet and Warmuth [17] studied tracking of a small set of experts via posterior distributions.”
Active Learning with Feedback on Features and Instances (2006, methodology): “While algorithms such as Winnow (Littlestone, 1988) and Support Vector Machines (SVMs) (Joachims, 1998) are robust in the presence of large numbers of features, these algorithms still require a substantial amount of labeled data to achieve adequate performance.”