Exercise 12.11: Feature Map for Polynomial Kernel

chapter 12

Use the Multinomial theorem: $$\begin{array}{}\text{(1)}& k(x,y)=(1+⟨x,z⟩{)}^m=\sum _{|\alpha |=m}(\genfrac{}{}{0ex}{}{m}{\alpha })(1,x\circ z{)}^{\alpha },\end{array}$$ where $\alpha =({\alpha }_1,\dots ,{\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 $(\genfrac{}{}{0ex}{}{d+m}{m})$ combinations.