20.9 Exercises 283
if we feed the network with the real number 0.x 1 x 2 ...xn, then the output
of the network will bex.
Hint:Denoteα= 0.x 1 x 2 ...xnand observe that 10kα− 0 .5 is at least 0. 5
ifxk= 1 and is at most− 0 .3 ifxk=−1.
- Construct a network,N 2 , withO(n) weights, which implements a function
from [n] to{ 0 , 1 }nsuch thatN 2 (i) =eifor alli. That is, upon receiving
the inputi, the network outputs the vector of all zeros except 1 at thei’th
neuron.
- Letα 1 ,...,αnbenreal numbers such that everyαiis of the form 0.a( 1 i)a( 2 i)...a(ni),
witha(ji)∈{ 0 , 1 }. Construct a network,N 3 , withO(n) weights, which im-
plements a function from [n] toR, and satisfiesN 2 (i) =αifor everyi∈[n].
- CombineN 1 ,N 3 to obtain a network that receivesi∈[n] and outputa(i).
- Construct a networkN 4 that receives (i,j)∈[n]×[n] and outputsa(ji).
Hint:Observe that the AND function over{ 0 , 1 }^2 can be calculated using
O(1) weights.
- Conclude that there is a graph withO(n) weights such that the VC di-
mension of the resulting hypothesis class isn^2.
- Prove Theorem 20.7.
Hint:The proof is similar to the hardness of learning intersections of halfs-
paces – see Exercise 32 in Chapter 8.
