Understanding Machine Learning: From Theory to Algorithms

30.2 Examples 413

A Compression Scheme:

W.l.o.g. assume all labels are positive (otherwise, replacexibyyixi). The com-

pression scheme we propose is as follows. First,Afinds the vectorwwhich is

in the convex hull of{x 1 ,...,xm}and has minimal norm. Then, it represents it

as a convex combination ofdpoints in the sample (it will be shown later that

this is always possible). The output ofAare thesedpoints. The algorithmB

receives thesedpoints and setwto be the point in their convex hull of minimal

norm.

Next we prove that this indeed is a compression sceme. Since the data is

linearly separable, the convex hull of{x 1 ,...,xm}does not contain the origin.

Consider the pointwin this convex hull closest to the origin. (This is a unique

point which is the Euclidean projection of the origin onto this convex hull.) We

claim thatwseparates the data.^1 To see this, assume by contradiction that

〈w,xi〉 ≤0 for somei. Takew′= (1−α)w+αxiforα= ‖w‖

2

‖xi‖^2 +‖w‖^2 ∈(0,1).

Thenw′is also in the convex hull and

‖w′‖^2 = (1−α)^2 ‖w‖^2 +α^2 ‖xi‖^2 + 2α(1−α)〈w,xi〉

≤(1−α)^2 ‖w‖^2 +α^2 ‖xi‖^2

=

‖xi‖^4 ‖w‖^2 +‖xi‖^2 ‖w‖^4

(‖w‖^2 +‖xi‖^2 )^2

= ‖xi‖

(^2) ‖w‖ 2
‖w‖^2 +‖xi‖^2
=‖w‖^2 ·

1

‖w‖^2 /‖xi‖^2 + 1

<‖w‖^2 ,

which leads to a contradiction.

We have thus shown thatwis also an ERM. Finally, sincewis in the convex

hull of the examples, we can apply Caratheodory’s theorem to obtain thatwis

also in the convex hull of a subset ofd+ 1 points of the polygon. Furthermore,

the minimality ofwimplies thatwmust be on a face of the polygon and this

implies it can be represented as a convex combination ofdpoints.

It remains to show thatwis also the projection onto the polygon defined by the

dpoints. But this must be true: On one hand, the smaller polygon is a subset of

the larger one; hence the projection onto the smaller cannot be smaller in norm.

On the other hand,witself is a valid solution. The uniqueness of projection

concludes our proof.

30.2.3 Separating Polynomials

LetX=Rdand consider the classx7→sign(p(x)) wherepis a degreerpolyno-

mial.

(^1) It can be shown thatwis the direction of the max-margin solution.