$k-$ degree polynomial regression

Question

$\phi: \mathbb{R}^d \to \mathbb{R}^m $ is the feature mapping for performing $k-$ degree polynomial regression on a $d-$ dimensional input. for example when $k=3$ and $d=2$ then, $$ \phi([x_1, x_2 ]) = [1, x_1, x_2, x_1^2, x_2^2, x_1^3, x_2^3, x_1x_2, x_1^2x_2, x_1x_2^2]$$

For any arbitrary $d$ and $k$, how to write $m$ as a function of $d$ and $k$?

Answer 1

You ask for the number of distinct monomials in $d$ variables $x_1,x_2,\ldots,x_d$ of total degree less than or equal to $k.$ These are the monomials of the form

$$x_1^{e_1}\,x_2^{e_2}\,\cdots x_d^{e_d}$$

where the $e_1$ are non-negative integers whose sum (the total degree) does not exceed $k.$

One simple way to count them is to consider the sequence of natural numbers

$$\left(f_0, f_1, \ldots, f_d\right) = \left(k-e_1-\cdots-e_d+1, e_1+1, e_2+1, \ldots, e_d+1\right)$$

These sum to $k+d+1.$ For $i=1,\ldots, d,$ their partial sums

$$s_i = f_0 + f_1 + \cdots + f_{i-1}$$

form a sequence of $d$ distinct, increasing integers in the range $\{1,2,\ldots, k+d\}$ (with $s_{d+1}=k+d+1$ always) and thereby correspond to a subset of those integers of size $d.$ Conversely, any such subset when ordered gives a sequence of such $s_i$ from which the powers $e_i$ can be recovered from the successive differences

$$s_i - s_{i-1} - 1 = e_i,\ i=1,2,\ldots, d.$$

Consequently the number of such monomials is the same as the number of such subsets, given by

$$\binom{k+d}{d} = \frac{(k+d)!}{k!\,d!}.$$

For instance, with $k=3$ and $d=2$ the value is $(3+2)!/(3!\,2!) = 10.$

It may be instructive to examine the correspondence explicitly in a small example like this. Here is a table of the monomials and the corresponding sequences.

$$\begin{array}{lcr} \text{Monomial} & \text{Sequence} & \text{Subset} \\ \hline 1 & (4,1,1) & \{4,5\}\\ x_1 & (3,2,1) & \{3,5\}\\ x_2 & (3,1,2) & \{3,4\}\\ x_1^2 & (2,3,1) & \{2,5\}\\ x_1x_2 & (2,2,2) & \{2,4\}\\ x_2^2 & (2,1,3) & \{2,3\}\\ x_1^3 & (1,4,1) & \{1,5\}\\ x_1^2x_2 & (1,3,2) & \{1,4\}\\ x_1x_2^2 & (1,2,3) & \{1,3\}\\ x_2^3 & (1,1,4) & \{1,2\} \end{array}$$

Finally -- again as an illustration -- the following R code uses combn to produce an array of subsets and converts that into a representation of the monomials. Here is the output for $k=d=3;$ that is, a list of the monomials in three variables up to degree $3:$

monomials <- function(k, d, varname="x") {
  vars <- paste0(varname, "[", 1:d, "]")
  s <- function(e) ifelse(e > 1, paste0(vars, "^", e, sep=""), ifelse(e==1, vars, ""))
  mult <- function(a) paste(a[a > ""], collapse="*")
  a <- apply(apply(apply(rbind(combn(k+d, d), k+d+1), 2, diff) - 1, 2, s), 2, mult)
  a[a==""] <- "1"
  rev(a)
}

mai <- par("mai")
par(mai=rep(0,4))
a <- monomials(3,3)
plot(c(1, length(a)), 0:1, type="n", xaxt="n", yaxt="n", xlab="", ylab="", bty="n")
invisible(sapply(seq_along(a), function(i) text(i, 1/2, parse(text=a[i]))))
par(mai=mai)