3.3 Growth function of linear combinations. A linearly separable labeling of a set X of vectors in Rd is a classication of X into two sets X+ and X???? with X+ =

fx 2 X: w
x > 0g and X???? = fx 2 X: w
x < 0g for some w 2 Rd.

Let X = fx1; : : : ; xmg be a subset of Rd.

(a) Let fX+;X????g be a dichotomy of X and let xm+1 2 Rd. Show that fX+ [

fxm+1g;X????g and fX+;X???? [fxm+1gg are linearly separable by a hyperplane going through the origin if and only if fX+;X????g is linearly separable by a hyperplane going through the origin and xm+1.

(b) Let X = fx1; : : : ; xmg be a subset of Rd such that any k-element subset of X with k  d is linearly independent. Then, show that the number of linearly separable labelings of X is C(m;

d) = 2 Pd????1 k=0

????m????1 k

. (Hint: prove by induction that C(m + 1;

d) = C(m;

d) + C(m; d ???? 1).

(c) Let f1; : : : ; fp be p functions mapping Rd to R. Dene F as the family of classiers based on linear combinations of these functions:

F =



x 7! sgn

Xp k=1 akfk(x)



: a1; : : : ; ap 2 R



:

Dene by (x) = (f1(x); : : : ; fp(x)). Assume that there exists x1; : : : ; xm 2 Rd such that every p-subset of f (x1); : : : ; (xm)g is linearly independent.

Then, show that

F(m) = 2 Xp????1 i=0



m ???? 1 i



: