Winnow Algorithm
•Initialize w = (1,1, …1).
•Let a = 1+d/2.
•Decision: wTx > q
•If learner correct, weights don’t change.  If wrong:
•
Promotion
step
wi:=awi if xi=1
wi unchanged if xi=0
1
0
Demotion
Step
wi:=wi/a if xi=1
wi unchanged if xi=0
0
1
Update
name
Update
Action
Correct
Response
Learner’s
Prediction