View Single Post
Old 06-13-2019, 01:03 AM
htlin's Avatar
htlin htlin is offline
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 610
Default Re: Problem 1.3 Question Please Help

Originally Posted by jewelltaylor9430 View Post
Question 1.3 A: Let p = min(1=<n=<N) y(n)(w*Yx(n)). Show that p > 0.

(For lack of any other notation I use brackets to represent subscripts, sorry)

Question 1.3 B: Show that wT(t)w* >= wT(t-1)w* + p, and conclude that wT(t)w* >= tp

My Questions:
- I understand p is defined in A but I am not familiar with the notation and I do not know what it represents. What is the min expression getting at? Is it the fact the value of p such that the value of n is minimized? Can you give me intuition behind what p actually is?

- How does the the RHS of the first inequality relate to the RHS of the second inequality in B? My understanding is t represents the iteration number of the perceptron algorithim. Is this the case or am I mistaken? Does tp somehow equal wT(t-1)w* + p and if so where the heck does it come from? I am so confused

Any help would be much appreciated, I have been stumped on this question for too long
\rho represents the distance from the closest \mathbf{x}_n to the boundary represented by \mathbf{w}^* if the latter is reasonably nromalized.

If you can prove that the inner product increases at least by \rho in each iteration, then after t iterations the inner product naturally increases by t \rho which is what you need to prove in B.

Hope this helps.
When one teaches, two learn.
Reply With Quote