(15 points) In this problem you will prove that PLA eventually converges to a linear separator for separable data. The following steps will guide you through the proof. Let w be a vector which separates the data, and assume that PLA is initialized with the vector 0( i.e. w(0)=0 ). (a) Let =min1nNyn(wTxn). Show that >0. (b) Show that w(t)ww(t1)w+, and conclude that w(t)wt. Hint: Use induction. (c) Show that w(t)2w(t1)2+x(t1)2. Hint: y(t1)(w(t1)x(t1))0, because x(t1) was misclassified by w(t1). (d) Show by induction that w(t)2tR2, where R=max1nNxn. (e) Using (b) and (d), show that w(t)w(t)wtR, and hence prove that t2R2w2 Hint: w(t)wc(t)w1 (why?)