Understanding Machine Learning: From Theory to Algorithms

120 Linear Predictors

byyi. That is,Ai,j=yixi,j, wherexi,jis thej’th element of the vectorxi. Let

vbe the vector (1,...,1)∈Rm. Then, Equation (9.1) can be rewritten as

Aw≥v.

The LP form requires a maximization objective, yet all thewthat satisfy the

constraints are equal candidates as output hypotheses. Thus, we set a “dummy”

objective,u= (0,...,0)∈Rd.

9.1.2 Perceptron for Halfspaces

A different implementation of the ERM rule is the Perceptron algorithm of

Rosenblatt (Rosenblatt 1958). The Perceptron is an iterative algorithm that

constructs a sequence of vectorsw(1),w(2),.... Initially,w(1)is set to be the

all-zeros vector. At iterationt, the Perceptron finds an exampleithat is mis-

labeled byw(t), namely, an example for which sign(〈w(t),xi〉) 6 =yi. Then, the

Perceptron updatesw(t)by adding to it the instancexiscaled by the labelyi.

That is,w(t+1)=w(t)+yixi. Recall that our goal is to haveyi〈w,xi〉>0 for

alliand note that

yi〈w(t+1),xi〉=yi〈w(t)+yixi,xi〉=yi〈w(t),xi〉+‖xi‖^2.

Hence, the update of the Perceptron guides the solution to be “more correct” on

thei’th example.

Batch Perceptron

input: A training set (x 1 ,y 1 ),...,(xm,ym)

initialize: w(1)= (0,...,0)

fort= 1, 2 ,...

if(∃i s.t. yi〈w(t),xi〉≤0) then

w(t+1)=w(t)+yixi

else

output w(t)

The following theorem guarantees that in the realizable case, the algorithm

stops with all sample points correctly classified.

theorem9.1 Assume that(x 1 ,y 1 ),...,(xm,ym)is separable, letB= min{‖w‖:

∀i∈[m], yi〈w,xi〉 ≥ 1 }, and letR= maxi‖xi‖. Then, the Perceptron al-

gorithm stops after at most(RB)^2 iterations, and when it stops it holds that

∀i∈[m], yi〈w(t),xi〉> 0.

Proof By the definition of the stopping condition, if the Perceptron stops it

must have separated all the examples. We will show that if the Perceptron runs

forTiterations, then we must haveT≤(RB)^2 , which implies the Perceptron

must stop after at most (RB)^2 iterations.

Letw?be a vector that achieves the minimum in the definition ofB. That is,