Problema de optimización mediante la Reproducción del Núcleo de Hilbert Espacios

Question

Me estoy encontrando con un problema en cuanto a la Reproducción del Núcleo de Hilbert Espacios (RKHS) en el contexto de aprendizaje de la máquina utilizando Máquinas de Soporte Vectorial (SVMs).

Con referencia a este papel [Olivier Chapelle, 2006], Sección 3, voy a tratar de ser breve y centrado en mi problema, por lo que puede evitar dar rigurosa descripción de lo que estoy utilizando a continuación.

Deje que el siguiente problema de optimización: $$ \displaystyle \min_{\mathbf{w},b}\: \lVert\mathbf{w}\rVert^2 + C\sum_{i=1}^{n}L(y_i, \mathbf{w}\cdot\mathbf{x}_i+b), $$ donde $L(y,t)=\operatorname{max}(0,1-yt)$ es una función de pérdida, la llamada "de la bisagra de la pérdida". Thrying para introducir a los granos, a fin de considerar no-lineal de las SVMs, el autor reformula el mencionado problema de optimización, en busca de una función en un RKHS, $\mathcal{H}$, lo que minimiza el siguiente funcional: $$ F[f]=\lambda\lVert f \rVert^2_\mathcal{H} + \sum_{i=1}^{n}L(y_i, f(\mathbf{x}_i)+b). $$ Yo entiendo lo siguiente de su obra; mi pregunta es la siguiente: Lo que si tenía alguna otra función de pérdida (no la bisagra de la pérdida de arriba), que no se expresa solamente por el interior del producto $\mathbf{w}\cdot\mathbf{x}_i$, lo que -si he entendido bien - es "reemplazado" por $f(\mathbf{x}_i)$, pero en lugar de eso había algo de pérdida en función de la forma: $$ \mathbf{w}\cdot\mathbf{x}_i+b+\sqrt{\mathbf{w}^TA\mathbf{w}}, $$ donde $A$ es positivo-definida simétrica la matriz? Quiero decir, ¿hay alguna manera de expresar el anterior quadrativ formulario ($\sqrt{\mathbf{w}^TA\mathbf{w}}$) utilizando la función de $f$, que puedo expresar mi problema de optimización en el contexto de RKHS?

Por otro lado, la teoría sugiere que, independientemente de la pérdida de la función, $L$, es decir, la solución de reformulted problema sería de la forma: $$ f(\mathbf{x})=\sum_{i=1}^{n}\alpha_ik(\mathbf{x}_i, \mathbf{x}), $$ donde $k$ es el núcleo asociado con la adopción de RKHS. He entendido correctamente? La solución sería la de arriba, incluso si mi pérdida de las funciones que se incluyen términos como"$\sqrt{\mathbf{w}^TA\mathbf{w}}$?

Todo comentario o ayuda sería muy apreciada. Sería bueno si alguien quiere discutir sobre esto. Gracias de antemano!

Answer 1

Comenzando con la respuesta a tu segundo problema, supongamos que $f \in H$ donde $H$ es la reproducción del núcleo espacio de hilbert. Deje $S$ ser el subespacio generado por las funciones del kernel $k(x_i, \cdot)$. Entonces por la teoría de espacios de Hilbert, $f$ puede ser escrito como $f = f_S + f_P$ donde $$f_S(x) = \sum_{i=1}^n a_i k(x_i, x),$$ and $f_P$ is a function perpendicular to $S$. Moreover by the Pythagorean theorem $$\| f \|^2 = \| f_S \|^2 + \| f_P \|^2.$$ In particular this tells us that $\|f\| > \|f_S\|$ if $f_P \neq 0$.

Ahora considere el $f(x_i)$, la cual puede ser escrito como $$f(x_i)=\langle f, k(x_i, \cdot) \rangle = \langle f_S, k(x_i, \cdot) \rangle + \langle f_P, k(x_i, \cdot) \rangle = \langle f_S, k(x_i, \cdot) \rangle + 0 = \langle f_S, k(x_i, \cdot) \rangle = f_S(x_i)$$

Por lo tanto para cada $f$ tenemos $$\sum_{i=1}^n L(y_i, f(x_i) + b) = \sum_{i=1}^n L(y_i, f_S(x_i) + b)$$

Por lo tanto, $$F[f] = \lambda \| f\|^2 + \sum_{i=1}^n L(y_i, f(x_i) + b) > \lambda \| f_S\|^2 + \sum_{i=1}^n L(y_i, f_S(x_i) + b) = F(f_S)$$ y esto vale para todos los $f \in H$. Esto significa que si la función va a minimizar $F$, debe ser en el subespacio $S$ y es una combinación lineal de las funciones del núcleo.

---

Como para la primera pregunta, cuadrática términos que se asemeja $w^T A w$ aparecen a través de lo que se conoce como el Graham de la matriz, que está hecho de granos de: $$K = \left( k(x_i,x_j) \right)_{i,j=1}^n.$$ It is straightforward to prove that this matrix is symmetric and positive (semi)-definite, since if $a = (a_1, a_2, ..., a_n)$ then $$a^T K a = \left\langle \sum_{i=1}^n a_i k(x_i, \cdot), \sum_{j=1}^n a_j k(x_j, \cdot)\right\rangle=\left\|\sum_{i=1}^n a_i k(x_i, \cdot)\right\|^2$$

Esto nos da nuestra primera pista de cómo proceder a la refundición de $w^T A w$ a nuestro idioma de la reproducción del núcleo de hilbert espacios.

---

Tomemos, por ejemplo $$A = diag(a_1,a_2,a_3,..., a_n)$$ where each $a_i > 0$. Then $$w^T A w = \sum_{i=1}^n a_i w_i^2$$

Ahora imagine que sustituye $w$$f$, y cada una de las $w_i = f(x_i)$. A continuación, $$\sum_{i=1}^n a_i w_i^2 = \sum_{i=1}^n a_i f(x_i)^2$$

Por el mismo razonamiento anterior, $$\sum_{i=1}^n a_i f(x_i)^2 = \sum_{i=1}^n a_i f_S(x_i)^2$$, y así podemos añadir esto a la función de pérdida y aún así se garantiza que un minimizer es una combinación lineal de las funciones del núcleo.

Así que en resumen, usted puede introducir el término que desea en su función de pérdida. Aquí teniendo en cuenta que $w = (f(x_1), f(x_2),...,f(x_n))$.

Answer 2

Me gustaría aclarar mi pregunta final, según lo expuesto por la discusión con @Joel anteriormente (ver los comentarios).

Vamos $\mathbf{w}=(w_1,\ldots,w_n)^T$, $\mathbf{x}_i=(x_{i1},\ldots,x_{in})^T\in\mathbb{R}^n$, $i=1,\ldots,m$, y $A=\big(a_{ij}\big)_{i,j=1}^{n}$ $n\times n$ simétrica positiva definida real de la matriz.

Supongamos que queremos minimizar la cantidad con respecto a $\mathbf{w}$

$$ J =\mathbf{w}\cdot\mathbf{w} + \sum_{i=1}^{m}\mathbf{w}\cdot\mathbf{x}_i + \mathbf{w}^TA\mathbf{w}. $$

En lugar de la anterior problema de optimización, vamos a buscar una función de $f$ que minimiza el funcional, por lo que el problema sigue siendo equivalente a la primera. Deje que esta función pertenece a una Reproducción de Kernel Espacio de Hilbert $\mathcal{H}$. La adecuada funcional debe ser de la forma $$ \Phi[f]= \big\lVert f \big\rVert^2_{\mathcal{H}} + \sum_{i=1}^{m}f(\mathbf{x}_i) + \cdots, $$ pero no sé cómo expresar la forma cuadrática $\mathbf{w}^TA\mathbf{w}$ en términos de f. Puede usted ayudar?

Lo que he pensado hasta ahora es el siguiente. Nos ha "sustituido" la cantidad de $\mathbf{w}\cdot\mathbf{w}$ por la norma $\big\lVert f \big\rVert^2_{\mathcal{H}}$, así que probablemente podría escribir $$ \mathbf{w}^TA\mathbf{w} = \mathbf{w}^T\big(LDL^T\big)\mathbf{w} = \mathbf{w}^T \big(LD^{1/2}\big)\big(LD^{1/2}\big)^T \mathbf{w} = \mathbf{w}\cdot\mathbf{w}, $$ donde $\mathbf{w'}=\Big(LD^{1/2}\Big)^T\mathbf{w}$. Podemos entonces encontrar una conexión entre la norma que debemos utilizar en su lugar?