Regresión polinómica de grado $k$

Question

$\phi: \mathbb{R}^d \to \mathbb{R}^m $ es la asignación de características para realizar regresión polinómica de grado $k-$ en una entrada dimensional $d-$. por ejemplo, cuando $k=3$ y $d=2$ entonces, $$ \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]$$

Para cualquier $d$ y $k$ arbitrarios, ¿cómo se puede escribir $m$ como una función de $d$ y $k$?

Answer 1

Dado un número determinado de monomios en $d$ variables $x_1,x_2,\ldots,x_d$ de grado total menor o igual a $k.$ Estos son los monomios de la forma

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

donde los $e_1$ son enteros no negativos cuya suma (el grado total) no excede $k.$

Una forma simple de contarlos es considerar la secuencia de números naturales

$$\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)$$

Estos suman $k+d+1.$ Para $i=1,\ldots, d,$ sus sumas parciales

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

forman una secuencia de $d$ enteros distintos y crecientes en el rango $\{1,2,\ldots, k+d\}$ (siempre con $s_{d+1}=k+d+1$) y por lo tanto corresponden a un subconjunto de esos enteros de tamaño $d.$ Del mismo modo, cualquier subconjunto así cuando se ordena proporciona una secuencia de tales $s_i$ a partir de los diferenciales sucesivos

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

Consecuentemente, el número de tales monomios es el mismo que el número de tales subconjuntos, dado por

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

Por ejemplo, con $k=3$ y $d=2$ el valor es $(3+2)!/(3!\,2!) = 10.$

Puede ser instructivo examinar la correspondencia explícitamente en un pequeño ejemplo como este. Aquí hay una tabla de los monomios y las secuencias correspondientes.

$$\begin{array}{lcr} \text{Monomio} & \text{Secuencia} & \text{Subconjunto} \\ \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}$$

Finalmente - nuevamente como ilustración - el siguiente código en R utiliza combn para producir una matriz de subconjuntos y los convierte en una representación de los monomios. Aquí está la salida para $k=d=3;$ es decir, una lista de los monomios en tres variables hasta el grado $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)