1.16 (


) In Exercise 1.15, we proved the result (1.135) for the number of independent parameters in the Mth order term of a D-dimensional polynomial. We now find an expression for the total number N(D,M) of independent parameters in all of the terms up to and including the M6th order. First show that N(D,M) satisfies N(D,M) =

M

m=0 n(D,m) (1.138)

where n(D,m) is the number of independent parameters in the term of order m.

Now make use of the result (1.137), together with proof by induction, to show that N(d,M) =

(D +M)!

D!M! . (1.139)

This can be done by first proving that the result holds for M = 0 and arbitrary D  1, then assuming that it holds at order M, and hence showing that it holds at order M + 1. Finally, make use of Stirling’s approximation in the form n!  nne

−n (1.140)

for large n to show that, for D M, the quantity N(D,M) grows like DM, and for M D it grows like MD. Consider a cubic (M = 3) polynomial in D dimensions, and evaluate numerically the total number of independent parameters for (i) D = 10 and (ii) D = 100, which correspond to typical small-scale and medium-scale machine learning applications.