@techreport{
 title = {8803 Machine Learning Theory The Winnow Algorithm},
 type = {techreport},
 id = {d7961f20-4a8a-3f88-9528-c88786503bda},
 created = {2019-02-26T15:52:07.446Z},
 file_attached = {true},
 profile_id = {1a94560e-0af5-3621-ba59-a0241aad2c7d},
 group_id = {9fcff044-d9db-3ece-9111-31d3cb8df27d},
 last_modified = {2019-03-12T11:43:46.953Z},
 read = {true},
 starred = {false},
 authored = {false},
 confirmed = {false},
 hidden = {false},
 private_publication = {false},
 abstract = {We now turn to an algorithm called the Winnow Algorithm developed by Nick Littlestone that performs especially well when many of the features given to the learner turn out to be irrelevant. Like the Perceptron Training Procedure discussed in the previous lectures, Win-now uses linear threshold functions as hypotheses and performs incremental updates to its current hypothesis. Unlike the Perceptron Training Procedure, Winnow uses multiplicative rather than additive updates. Winnow was developed with the goal of providing a significant Mistake Bound improvement when r ≪ n. We will analyze the Winnow algorithm for learning the class of C of monotone disjunctions of r variables. Note that Winnow or generalizations of Winnow can handle other specific concept classes (e.g. non-monotone disjunctions, majority functions, linear spearators), but the analysis is simplest in the case of monotone disjunctions. The Algorithm Both Winnow and Perceptron Algorithms use the same classification scheme: • w · x ≥ θ ⇒ positive classification • w · x < θ ⇒ negative classification For convenience, we assume that θ = n and we initialize w to the "all ones" vector, i.e., w i = 1 for all i 1. The Winnow Algorithm differs from the Perceptron Algorithm in its update scheme. When misclassifying a positive training example x (i.e. the predition was negative because w · x was too small): ∀x i = 1 : w i ← 2w i. When misclassifying a negative training example x (i.e. prediction was positive because w ·x was too large): 1 Note that Perceptron used a threshold of 0 but here we use a threshold of n.},
 bibtype = {techreport},
 author = {Balcan, Maria-Florina}
}

{"_id":"g6QjqDhSr2eC25tvG","bibbaseid":"balcan-8803machinelearningtheorythewinnowalgorithm","downloads":0,"creationDate":"2019-03-05T15:17:16.173Z","title":"8803 Machine Learning Theory The Winnow Algorithm","author_short":["Balcan, M."],"year":null,"bibtype":"techreport","biburl":null,"bibdata":{"title":"8803 Machine Learning Theory The Winnow Algorithm","type":"techreport","id":"d7961f20-4a8a-3f88-9528-c88786503bda","created":"2019-02-26T15:52:07.446Z","file_attached":"true","profile_id":"1a94560e-0af5-3621-ba59-a0241aad2c7d","group_id":"9fcff044-d9db-3ece-9111-31d3cb8df27d","last_modified":"2019-03-12T11:43:46.953Z","read":"true","starred":false,"authored":false,"confirmed":false,"hidden":false,"private_publication":false,"abstract":"We now turn to an algorithm called the Winnow Algorithm developed by Nick Littlestone that performs especially well when many of the features given to the learner turn out to be irrelevant. Like the Perceptron Training Procedure discussed in the previous lectures, Win-now uses linear threshold functions as hypotheses and performs incremental updates to its current hypothesis. Unlike the Perceptron Training Procedure, Winnow uses multiplicative rather than additive updates. Winnow was developed with the goal of providing a significant Mistake Bound improvement when r ≪ n. We will analyze the Winnow algorithm for learning the class of C of monotone disjunctions of r variables. Note that Winnow or generalizations of Winnow can handle other specific concept classes (e.g. non-monotone disjunctions, majority functions, linear spearators), but the analysis is simplest in the case of monotone disjunctions. The Algorithm Both Winnow and Perceptron Algorithms use the same classification scheme: • w · x ≥ θ ⇒ positive classification • w · x < θ ⇒ negative classification For convenience, we assume that θ = n and we initialize w to the \"all ones\" vector, i.e., w i = 1 for all i 1. The Winnow Algorithm differs from the Perceptron Algorithm in its update scheme. When misclassifying a positive training example x (i.e. the predition was negative because w · x was too small): ∀x i = 1 : w i ← 2w i. When misclassifying a negative training example x (i.e. prediction was positive because w ·x was too large): 1 Note that Perceptron used a threshold of 0 but here we use a threshold of n.","bibtype":"techreport","author":"Balcan, Maria-Florina","bibtex":"@techreport{\n title = {8803 Machine Learning Theory The Winnow Algorithm},\n type = {techreport},\n id = {d7961f20-4a8a-3f88-9528-c88786503bda},\n created = {2019-02-26T15:52:07.446Z},\n file_attached = {true},\n profile_id = {1a94560e-0af5-3621-ba59-a0241aad2c7d},\n group_id = {9fcff044-d9db-3ece-9111-31d3cb8df27d},\n last_modified = {2019-03-12T11:43:46.953Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {false},\n hidden = {false},\n private_publication = {false},\n abstract = {We now turn to an algorithm called the Winnow Algorithm developed by Nick Littlestone that performs especially well when many of the features given to the learner turn out to be irrelevant. Like the Perceptron Training Procedure discussed in the previous lectures, Win-now uses linear threshold functions as hypotheses and performs incremental updates to its current hypothesis. Unlike the Perceptron Training Procedure, Winnow uses multiplicative rather than additive updates. Winnow was developed with the goal of providing a significant Mistake Bound improvement when r ≪ n. We will analyze the Winnow algorithm for learning the class of C of monotone disjunctions of r variables. Note that Winnow or generalizations of Winnow can handle other specific concept classes (e.g. non-monotone disjunctions, majority functions, linear spearators), but the analysis is simplest in the case of monotone disjunctions. The Algorithm Both Winnow and Perceptron Algorithms use the same classification scheme: • w · x ≥ θ ⇒ positive classification • w · x < θ ⇒ negative classification For convenience, we assume that θ = n and we initialize w to the \"all ones\" vector, i.e., w i = 1 for all i 1. The Winnow Algorithm differs from the Perceptron Algorithm in its update scheme. When misclassifying a positive training example x (i.e. the predition was negative because w · x was too small): ∀x i = 1 : w i ← 2w i. When misclassifying a negative training example x (i.e. prediction was positive because w ·x was too large): 1 Note that Perceptron used a threshold of 0 but here we use a threshold of n.},\n bibtype = {techreport},\n author = {Balcan, Maria-Florina}\n}","author_short":["Balcan, M."],"urls":{"Paper":"https://bibbase.org/service/mendeley/1a94560e-0af5-3621-ba59-a0241aad2c7d/file/26a6fe8f-b4ba-ce5d-2ff8-fba0eaa2abff/lect0906.pdf.pdf"},"bibbaseid":"balcan-8803machinelearningtheorythewinnowalgorithm","role":"author","downloads":0},"search_terms":["8803","machine","learning","theory","winnow","algorithm","balcan"],"keywords":[],"authorIDs":[]}