Homepage › Solution manuals › Yaser Abu-Mostafa › Learning from Data › Exercise 3.14

Exercise 3.14

Answers

Consider the $Q$ th order polynomial transform $Φ_{Q}$ for $X = R^{d}$ . Let’s count the terms with exactly $q$ -degree that can be created with $x_{1}, x_{2}, \dots, x_{d}$ . There are total of $(\binom{q + d - 1}{d - 1})$ such terms. See Number of polynomial terms for certain degree and certain number of variables.

So the total terms for the $Q$ th order polynomical transform (which is also the dimensionality $\tilde{d}$ of the feature space $Z$ ) is (Excluding the constant $1$ ):

\begin{array}{l} \tilde{d} (d, Q) & = \sum_{q = 1}^{Q} (\binom{q + d - 1}{d - 1}) \\ = (\binom{d}{d - 1}) + (\binom{d + 1}{d - 1}) + \dots + (\binom{Q + d - 1}{d - 1}) \\ = (\binom{d}{1}) + (\binom{d + 1}{2}) + \dots + (\binom{Q + d - 1}{Q}) \\ = ((\binom{d + 1}{1}) - (\binom{d}{0})) + ((\binom{d + 2}{2}) - (\binom{d + 1}{1})) + \dots + ((\binom{d + Q}{Q}) - (\binom{d + Q - 1}{Q - 1})) \\ = (\binom{d + Q}{Q}) - 1 \end{array}

Where we have applied the equality: $(\binom{N}{k}) = (\binom{N - 1}{k}) + (\binom{N - 1}{k - 1})$

from scipy.special import comb 
print('Feature Space Dimensionality') 
ds = [2,3,5,10] 
Qs = [2,3,5,10] 
for d in ds: 
    for Q in Qs: 
        r = comb(d+Q, Q) - 1 
        print('d = ', d, ' Q = ', Q, ': ', int(r))

Feature Space Dimensionality
d =  2  Q =  2 :  5
d =  2  Q =  3 :  9
d =  2  Q =  5 :  20
d =  2  Q =  10 :  65
d =  3  Q =  2 :  9
d =  3  Q =  3 :  19
d =  3  Q =  5 :  55
d =  3  Q =  10 :  285
d =  5  Q =  2 :  20
d =  5  Q =  3 :  55
d =  5  Q =  5 :  251
d =  5  Q =  10 :  3002
d =  10  Q =  2 :  65
d =  10  Q =  3 :  285
d =  10  Q =  5 :  3002
d =  10  Q =  10 :  184755

niuers

2021-12-07 22:25

Exercise 3.14

Answers

Comments

Add answer