We will now prove step-by-step the mistake bound for the Modified Perceptron Algo- rithm (MPA) algorithm. i. Show that after T rounds Ty < ||wrl|, and observe that if ||wrl| < 4R2/y, then T <AR? /72. In what follows, we will assume that ||wr|| 2 4R2/7. ii. Show that for any iteration t when mistake was made, the following holds: 1/20 + 112 5 (1/ 204-1/1 + 7/2)2 + 12. iii. Infer from that that for any iteration t, we have 1/ well = 1 2t-1/1+ 7/2+ R2 1/ 20t-1/1 + 1/well + 7/2 iv. Using the previous question, show that for any iteration t such that either | |wt-1|| 2 4R or well 2 4R- , we have v. Show that |woll < R < 4R2/y. Since by assumption we have |wrl| 2 4R- conclude that there must exist some largest iteration to such that | |Wto-1/| 5 4R2 and ||wto || 2 4R2 vi. Show that (|will < ||wto-1/| + Ty, and finally deduce the mistake bound.

2 A better output Perceptron algorithm guarantee In class, we saw that when the training sample S is linearly separable with a maximum margin y > 0, then the Perceptron algorithm run cyclically over S is guaranteed to converge after T < (R/y) updates, where R is the radius of the sphere containing the sample points. This does not guarantee however that the hyperplane solution returned by Perceptron, i.e. wr achieves a margin close to y. (i) Show an example training dataset S in R2 that has margin y, and an order of updates made by the Perceptron algorithm where the hyperplane solution returned has arbitrarily bad margin on S. (ii) Consider the following modification to the perceptron algorithm: Modified Perceptron Algorithm Input: training dataset S = (Xi, yi)i=1,...,n Output: learned vector w - Initialize wo := 0, t := 0 - while there exists an example (x, y) E S, such that 2y(wt . x) S yl|well set Wt+1 := Wt + yx - set t := t+1 - return Wt. (a) If the Modified Perceptron Algorithm (MPA) terminates after I rounds, what margin guarantee is achieved by the hyperplane wy returned by MPA? Justify your answer.

pur-new-sol

Related Questions