3.27 VC-dimension of neural networks.

Let C be a concept class over Rr with VC-dimension

d. A C-neural network with one intermediate layer is a concept dened over Rn that can be represented by a directed acyclic graph such as that of Figure 3.7, in which the input nodes are those at the bottom and in which each other node is labeled with a concept c 2 C.

The output of the neural network for a given input vector (x1; : : : ; xn) is obtained as follows. First, each of the n input nodes is labeled with the corresponding value xi 2 R. Next, the value at a node u in the higher layer and labeled with c is obtained by applying c to the values of the input nodes admitting an edge ending in u. Note that since c takes values in f0; 1g, the value at u is in f0; 1g. The value at the top or output node is obtained similarly by applying the corresponding concept to the values of the nodes admitting an edge to the output node.

(a) Let H denote the set of all neural networks dened as above with k  2 internal nodes. Show that the growth function H(m) can be upper bounded in terms of the product of the growth functions of the hypothesis sets dened at each intermediate layer.

(b) Use that to upper bound the VC-dimension of the C-neural networks (Hint:
you can use the implication m = 2x log2(xy) ) m > x log2(ym) valid for m  1, and x; y > 0 with xy > 4).

(c) Let C be the family of concept classes dened by threshold functions C = fsgn(
Pr j=1 wjxj) : w 2 Rrg. Give an upper bound on the VC-dimension of H in terms of k and r.