Eficiencia de regresión de Kernel Ridge

La Regresión de cresta se puede expresar como donde es la etiqueta predicha , la matriz de identificación , el objeto para el que estamos tratando de encontrar una etiqueta y la matriz de objetos tal que:

$$\hat{y} = (\mathbf{X'X} + a\mathbf{I}_d)^{-1}\mathbf{X}x$$ $\hat{y}$$\mathbf{I}_d$$d \times d$$\mathbf{x}$$\mathbf{X}$$n \times d$$n$$\mathbf{x}_i = (x_{i,1}, ..., x_{i,d})\in \mathbb{R}^d$

$$\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 kernelizar esto de la siguiente manera:

$$\hat{y} = (\mathbf{\mathcal{K}} + a\mathbf{I}_d)^{-1} \mathbf{k}$$

donde es la matriz de las funciones del kernel$\mathbf{\mathcal{K}}$$n \times n$$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 el vector de columna de las funciones del kernel$\mathbf{k}$$n \times 1$$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 que dimensiones, ¿tiene sentido no usar núcleos? Por ejemplo, dejemos que sea ​​una matriz , luego será un y terminaremos invirtiendo una matriz lugar de matriz que tendríamos que invertir si utilizáramos núcleos. ¿Esto significa que si no deberíamos usar núcleos?$\mathbf{x}_i$$\mathbf{X}$$50 \times 3$$\mathbf{X}'\mathbf{X}$$3 \times 3$$3 \times 3$$50 \times 50$$d \leq n$

(b) ¿debería usarse el núcleo más simple posible? Parece que los núcleos en la regresión de crestas se usan para negar las influencias de la dimensionalidad y no para utilizar ciertas propiedades del espacio de características (a diferencia de las máquinas de vectores de soporte). Aunque, los núcleos pueden cambiar las distancias entre los objetos, ¿hay algún núcleo popular que se use con frecuencia en la regresión de crestas?

(c) ¿Cuál es la complejidad del tiempo de la regresión de cresta y / o la regresión de cresta del núcleo?$O$

(a) El propósito de usar un núcleo es resolver un problema de regresión no lineal en este caso. Un buen núcleo le permitirá resolver problemas en un espacio de características posiblemente infinito. Pero, usar un núcleo lineal y hacer la regresión de la cresta del núcleo en el espacio dual es lo mismo que resolver el problema en el espacio primario , es decir, no aporta ninguna ventaja (es mucho más lento a medida que aumenta el número de muestras como observó).$K(\mathbf{x,y}) = \mathbf{x}^\top \mathbf{y}$

(b) Una de las opciones más populares es el núcleo exponencial cuadrado que es universal (ver referencia más abajo). Hay muchos núcleos, y cada uno de ellos inducirá un producto interno diferente (y, por lo tanto, métrico) a su espacio de características.$K(x,y) = \exp(-\frac{\tau}{2} ||\mathbf{x}-\mathbf{y}||^2)$

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

Referencias

1. Bharath Sriperumbudur, Kenji Fukumizu y Gert Lanckriet. Sobre la relación entre universalidad, núcleos característicos e incrustación de medidas RKHS. Journal of Machine Learning Research, 9: 773–780, 2010.
2. Bernhard Schlkopf, Alexander J. Smola. Aprendizaje con kernels: máquinas de vectores de soporte, regularización, optimización y más allá de 2002