When running the Perceptron on this sequence of examples it makesm
updates before converging.
Hint:Choosed=mand for everyichoosexi=ei.
4.(*)Given any numberm, find an example of a sequence of labeled examples
((x 1 ,y 1 ),...,(xm,ym))∈(R^3 × {− 1 ,+1})mon which the upper bound of
Theorem 9.1 equalsmand the perceptron algorithm is bound to makem
mistakes.
Hint:Set eachxito be a third dimensional vector of the form (a,b,yi), where
a^2 +b^2 =R^2 −1. Letw∗be the vector (0, 0 ,1). Now, go over the proof of
the Perceptron’s upper bound (Theorem 9.1), see where we used inequalities
(≤) rather than equalities (=), and figure out scenarios where the inequality
actually holds with equality.
Suppose we modify the Perceptron algorithm as follows: In the update step,
instead of performingw(t+1)=w(t)+yixiwhenever we make a mistake, we
performw(t+1)=w(t)+ηyixifor someη >0. Prove that the modified Per-
ceptron will perform the same number of iterations as the vanilla Perceptron
and will converge to a vector that points to the same direction as the output
of the vanilla Perceptron.
In this problem, we will get bounds on the VC-dimension of the class of
(closed) balls inRd, that is,
Bd={Bv,r:v∈Rd,r > 0 },
where
Bv,r(x) =
{
1 if‖x−v‖≤r
0 otherwise.
Consider the mappingφ:Rd→Rd+1defined byφ(x) = (x,‖x‖^2 ). Show
that ifx 1 ,...,xmare shattered byBdthenφ(x 1 ),...,φ(xm) are shattered
by the class of halfspaces inRd+1(in this question we assume that sign(0) =
1). What does this tell us about VCdim(Bd)?
2.(*)Find a set ofd+ 1 points inRdthat is shattered byBd. Conclude that
d+ 1≤VCdim(Bd)≤d+ 2.
