View Single Post
Old 01-10-2013, 08:35 AM
Yann222 Yann222 is offline
Join Date: Jan 2013
Location: SoCal
Posts: 16
Default Re: PLA: Is randomly selecting the update important?

I think the algorithm "moves in the right direction" on the last point, though I think the sign of the dot product could still be incorrect after an iteration (this is what Exc.1.3 in the book walks you through). However, there's no guarantee that improvement will ever get you there (could be monotone sequence of increasingly small steps, though I think it's easy enough to convince oneself this won't happen) or that this point will not get "messed up" later in another iteration when you are taking care of a different misclassified point.

Problem (as opposed to "exercise") 1.3 of chapter one, as magdon pointed out, steps you through a full proof of PLA convergence. I haven't attempted it yet, but seems pretty involved.
Reply With Quote