Regularización de las variables duales en SVM

Question

Consideremos el programa de optimización de la SVM kernelizada:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

donde para la matriz $Q$ tenemos: $Q_{ij}=y_iy_j\text{kernel}(x_i,x_j)$ .

Este programa de optimización resulta de tomar el dual de la SVM basada en la pérdida de bisagra con $L_2$ regularización.

Esta es mi pregunta: ¿Por qué ningún organismo regulariza $\alpha$ en este programa de optimización?

Entiendo que $\alpha$ es sólo el vector de las variables duales, pero tengo mucha curiosidad por saber por qué la gente no ha intentado regularizar $\alpha$ .

Por ejemplo, si por las razones que sean queremos forzar al algoritmo a introducir menos vectores de soporte, entonces añadir un $L_1$ regularización en $\alpha$ sería útil, ¿verdad?

Es decir,

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha-\|\alpha\|_1$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

O quizás, una regularización de Tikhonov:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^T(Q+\gamma I)\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

Le agradezco que comparta cualquier comentario que pueda tener.

Answer 1

Desde el punto de vista de la regularización, la SVM es un caso especial de regularización de Tikhonov que utiliza la pérdida de bisagra. Ya estamos induciendo la dispersión en el $\alpha$ vector utilizando la pérdida de bisagra, es decir, la suma de las variables de holgura $\xi$ en el primario:

$$\begin{align} \min_{\alpha, b,\xi}\quad &\frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i, \\ s.t.\quad&y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i\rangle +b\big) \geq 1- \xi_i,\quad \forall i. \end{align}$$

Se puede ver esto elaborando el langrangiano primario (que se está minimizando): $$ L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i)\rangle+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$ Algunas de las condiciones de optimalidad son: $$\begin{align} \frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad &\alpha_i=C-\mu_i, \quad \forall i, \\ \frac{\partial L_p}{\partial \mathbf{w}}=0\quad \rightarrow \quad &\mathbf{w}=\sum_{i=1}^n \alpha_i y_i \varphi(\mathbf{x}_i),\quad \forall i, \end{align}$$ Lo que lleva a $\xi_i = 0 \rightarrow \mu_i = C \rightarrow \alpha_i = 0$ : instancias $i$ que se clasifican correctamente ( $\xi_i=0$ ), ya tienen un doble peso $\alpha_i=0$ y $\xi$ es esencialmente $L_1$ -regularizado.

Añadir regularización en el dual cambiaría inevitablemente la solución y daría lugar a un clasificador que ya no es de margen máximo, que es una de las razones clave por las que SVM es tan popular.

Esta es una de las principales diferencias entre SVM y LS-SVM (que utiliza la suma de cuadrados de los errores (de regresión) y, por tanto, pierde la dispersión en $\alpha$ ).