Online Learning contd * The Perceptron Algorithm * Bounds in terms of hinge-loss * Perceptron for Approximately Maximizing the Margins

Plan for today: Last time we looked at the Winnow algorithm, which has a very nice mistake-bound for learning an OR-function, which we then generalized for learning a linear separator (technically we only did the extension to “k of r ” functions in class, but on home-work 2 you will do the full analysis for general linear separators). Today will look at a more classic algorithm for learning linear separators, with a different kind of guarantee. 1 The Perceptron Algorithm One of the oldest algorithms used in machine learning (from early 60s) is an online algorithm for learning a linear threshold function called the Perceptron Algorithm. For simplicity, we’ll use a threshold of 0, so we’re looking at learning functions like: w1x1 + w2x2 +...+ wnxn> 0. We can simulate a nonzero threshold with a “dummy ” input x0 that is always 1, so this can be done without loss of generality. The guarantee we’ll show for the Perceptron Algorithm is the following: Theorem 1 Let S be a sequence of labeled examples consistent with a linear threshold func-tion w ∗ · x> 0, where w ∗ is a unit-length vector. Then the number of mistakes M on S made by the online Perceptron algorithm is at most (1/γ)2, where γ = min x∈S |w ∗ · x| ||x| |. (I.e., if we scale examples to have Euclidean length 1, then γ is the minimum distance of any example to the plane w ∗ · x = 0.) The parameter “γ ” is often called the “margin ” of w ∗ (or more formally, the L2 margin because we are scaling by the L2 lengths of the target and examples). Another way to view the quantity w ∗ · x/||x| | is that it is the cosine of the angle between x and w∗, so we will also use cos(w∗,x) for it