Exercise 12.11: Feature Map for Polynomial Kernel
Use the Multinomial theorem: \begin{equation} k(x, y) = (1 + \lra{x, z})^m = \sum_{|\alpha|=m}\binom{m}{\alpha}(1, x \had z)^\alpha, \end{equation} where $\alpha = (\alpha_1, \ldots, \alpha_{d+1})$. Use method of stars and bars to count numbers of terms: There are $m$ stars and $(d + 1) - 1 = d$ bars, which gives a total of $d + m$ items, and it suffices to choose the position the stars: a total of $\binom{d + m}{m}$ combinations.