El Kernel De Regresión Ridge Eficiencia

Question

Cresta de Regresión puede ser expresado como $$\hat{y} = (\mathbf{X'X} + a\mathbf{I}_d)^{-1}\mathbf{X}x$$ where $\hat{y}$ is the predicted label, $\mathbf{I}_d$ the $d \veces d$ identify matrix, $\mathbf{x}$ the object we're trying to find a label for, and $\mathbf{X}$ the $n \times d$ matrix of $n$ objects $\mathbf{x}_i = (x_{i,1}, ..., x_{i,d})\in \mathbb{R}^d$ tales que:

$$ \mathbf{X} = \begin{pmatrix} x_{1,1} & x_{1,2} & \ldots & x_{1,d}\\ x_{2,1} & x_{2,2} & \ldots & x_{2,d}\\ \vdots & \vdots & \ddots & \vdots\\ x_{n,1} & x_{1,2} &\ldots & x_{n,d} \end{pmatrix} $$

Podemos kernelise esto de la siguiente manera: $$\hat{y} = (\mathbf{\mathcal{K}} + a\mathbf{I}_d)^{-1} \mathbf{k}$$

donde $\mathbf{\mathcal{K}}$ $n \times n$ matriz de funciones kernel $K$

$$\mathcal{K} = \begin{pmatrix} K(\mathbf{x}_1,\mathbf{x}_1) & K(\mathbf{x}_1,\mathbf{x}_2) & \ldots & K(\mathbf{x}_1,\mathbf{x}_n)\\ K(\mathbf{x}_2,\mathbf{x}_1) & K(\mathbf{x}_2,\mathbf{x}_2) & \ldots & K(\mathbf{x}_2,\mathbf{x}_n)\\ \vdots & \vdots & \ddots & \vdots\\ K(\mathbf{x}_n,\mathbf{x}_1) & K(\mathbf{x}_n,\mathbf{x}_2) &\ldots & K(\mathbf{x}_n,\mathbf{x}_n) \end{pmatrix} $$

y $\mathbf{k}$ $n \times 1$ vector columna de las funciones del núcleo $K$

$$\mathbf{k} = \begin{pmatrix} K(\mathbf{x}_1,\mathbf{x})\\ K(\mathbf{x}_2,\mathbf{x}) \\ \vdots \\ K(\mathbf{x}_n,\mathbf{x}) \end{pmatrix}$$

Preguntas:

(a) si hay más objetos $\mathbf{x}_i$ que dimensiones tiene sentido a no usar los kernels? E. g. deje $\mathbf{X}$ $50 \times 3$ de la matriz, a continuación, $\mathbf{X}'\mathbf{X}$ $3 \times 3$ y vamos a terminar hasta que la inversión de un $3 \times 3$ de la matriz en lugar de la $50 \times 50$ matriz tendríamos que invertir íbamos a usar kernels. ¿Significa esto que si $d \leq n$ que no deberíamos usar kernels?

(b) debe ser lo más sencillo posible kernel ser utilizado? Parece que los granos estén en la cresta de regresión se utilizan para negar las influencias de la dimensionalidad y no utilizar ciertas propiedades de la función de espacio (a diferencia de las máquinas de vectores soporte). Aunque, los núcleos pueden cambiar las distancias entre los objetos entonces, ¿hay alguna populares núcleos menudo se utilizan en la cresta de la regresión?

(c) ¿cuál es el $O$ tiempo la complejidad de la cresta de regresión de y/o kernel regresión ridge?

Answer 1

(a) El propósito de usar un kernel para resolver un problema de regresión no lineal en este caso. Un buen kernel le permitirá resolver problemas en un posiblemente infinito-dimensional espacio de características. Pero, usando un kernel lineal $K(\mathbf{x,y}) = \mathbf{x}^\top \mathbf{y}$ y haciendo el kernel de regresión ridge en el espacio dual es la misma que la de resolver el problema en el espacio primigenio, es decir, que no aporta ninguna ventaja (es mucho más lento a medida que el número de la muestra crece a medida que se observa).

(b) Una de las opciones más populares es el cuadrado de la exponencial kernel $K(x,y) = \exp(-\frac{\tau}{2} ||\mathbf{x}-\mathbf{y}||^2)$ que es universal (ver ref abajo). Hay muchos kernels, y cada uno de ellos induce diferentes interior del producto (y, por tanto, métrica) a su espacio de características.

(c) aplicación Sencilla requiere la solución de una ecuación lineal de tamaño $n$, por lo que es $O(n^3)$. Hay muchos más rápidos métodos de aproximación tal como Nyström aproximación. Esta es un área de investigación activa.

Referencias:

1. Bharath Sriperumbudur, Kenji Fukumizu, y Gert Lanckriet. Sobre la relación entre la universalidad, característica de los kernels y RKHS la incorporación de medidas. Diario de la Máquina El Aprendizaje De La Investigación, De 9:773-780, 2010.
2. Bernhard Schlkopf, Alexander J. Smola. El aprendizaje con los Núcleos de: Máquinas de Vectores Soporte, la Regularización, la Optimización, y más Allá de de 2002