¿Es posible el descenso gradual para las SVM kernelizadas (si es así, por qué la gente utiliza la programación cuadrática)?

Question

¿Por qué se utilizan técnicas de programación cuadrática (como la SMO) cuando se trata de SVM kernelizadas? ¿Qué tiene de malo el Descenso Gradual? ¿Es imposible utilizarlo con kernels o es simplemente demasiado lento (y por qué?).

Aquí hay un poco más de contexto: tratando de entender las SVM un poco mejor, he utilizado el Descenso Gradiente para entrenar un clasificador SVM lineal utilizando la siguiente función de coste:

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \mathbf{x}^{(i)} + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

Utilizo las siguientes anotaciones:

• $\mathbf{w}$ es el peso de las características del modelo y $b$ es su parámetro de sesgo.
• $\mathbf{x}^{(i)}$ es el $i^\text{th}$ vector de características de la instancia de entrenamiento.
• $y^{(i)}$ es la clase de destino (-1 o 1) para el $i^\text{th}$ instancia.
• $m$ es el número de instancias de entrenamiento.
• $C$ es el hiperparámetro de regularización.

Obtuve un vector (sub)gradiente (con respecto a $\mathbf{w}$ y $b$ ) de esta ecuación, y el descenso por gradiente funcionó bien.

Ahora me gustaría abordar problemas no lineales. ¿Puedo sustituir todos los productos de puntos $\mathbf{u}^t \cdot \mathbf{v}$ con $K(\mathbf{u}, \mathbf{v})$ en la función de costes, donde $K$ es la función del núcleo (por ejemplo, la RBF gaussiana, $K(\mathbf{u}, \mathbf{v}) = e^{-\gamma \|\mathbf{u} - \mathbf{v}\|^2}$ ), luego usar el cálculo para derivar un (sub)vector gradiente y seguir con el Descenso Gradiente?

Si es demasiado lento, ¿a qué se debe? ¿La función de coste no es convexa? ¿O es porque el gradiente cambia demasiado rápido (no es continuo de Lipschitz) y el algoritmo sigue saltando por los valles durante el descenso, por lo que converge muy lentamente? Pero incluso así, ¿cómo puede ser peor que la complejidad temporal de la Programación Cuadrática, que es $O({n_\text{samples}}^2 \times n_\text{features})$ ? Si se trata de mínimos locales, ¿no puede el DG estocástico con recocido simulado superarlos?

Answer 1

Set $\mathbf w = \phi(\mathbf x)\cdot \mathbf u$ para que $\mathbf w^t \phi(\mathbf x)=\mathbf u^t \cdot \mathbf K$ y $\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$ con $\mathbf K = \phi(\mathbf x)^t\phi(\mathbf x)$ , donde $\phi(x)$ es un mapeo de la matriz de entrada original, $\mathbf x$ . Esto permite resolver la SVM a través de la formulación primal. Usando su notación para la pérdida:

$$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{u}^t \cdot \mathbf{K}^{(i)} + b)\right)} + \dfrac{1}{2} \mathbf{u}^t \cdot \mathbf{K} \cdot \mathbf{u}$$

$ \mathbf{K}$ es un $m \times m$ matriz, y $\mathbf{u}$ es un $m \times 1$ matriz. Ninguna de las dos es infinita.

De hecho, el dual suele ser más rápido de resolver, pero el primal también tiene sus ventajas, como las soluciones aproximadas (que no están garantizadas en la formulación dual).

---

Ahora bien, la razón por la que el dual es mucho más prominente no es obvia en absoluto: [1]

Las razones históricas por las que la mayoría de las investigaciones en el último década se ha centrado en la optimización dual no están claras . Creemos que es porque las SVM se introdujeron por primera vez en su formulación de margen duro margen duro [Boser et al., 1992], para lo cual una optimización dual (debido a las restricciones) parece más natural. Sin embargo, en general las SVM de margen suave deberían ser preferibles, incluso si los datos de entrenamiento son separables: el límite de decisión es más robusto porque se tienen en cuenta más puntos de puntos de entrenamiento [Chapelle et al., 2000].

---

Chapelle (2007) sostiene que la complejidad temporal de la optimización primal y dual es $\mathcal{O}\left(nn_{sv} + n_{sv}^3\right)$ En el peor de los casos $\mathcal{O}\left(n^3\right)$ pero analizaron pérdidas cuadráticas y aproximadas de bisagra, por lo que no es una pérdida de bisagra propiamente dicha, ya que no es diferenciable para ser utilizada con el método de Newton.

---

_{<a href="https://www.cs.utah.edu/~piyush/teaching/svm-solving-primal.pdf" rel="noreferrer">[1] Chapelle, O. (2007). Training a support vector machine in the primal. Neural computation, 19(5), 1155-1178.</a>}

Answer 2

Si aplicamos una transformación $\phi$ a todos los vectores de pesos de entrada ( $\mathbf{x}^{(i)}$ ), obtenemos la siguiente función de costes:

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

El truco del núcleo sustituye a $\phi(\mathbf{u})^t \cdot \phi(\mathbf{v})$ por $K(\mathbf{u}, \mathbf{v})$ . Dado que el vector de pesos $\mathbf{w}$ est no transformado, el truco del núcleo no puede aplicarse a la función de coste anterior .

La función de coste anterior corresponde a la forma primitiva del objetivo de la SVM:

$\underset{\mathbf{w}, b, \mathbf{\zeta}}\min{C \sum\limits_{i=1}^m{\zeta^{(i)}} + \dfrac{1}{2}\mathbf{w}^t \cdot \mathbf{w}}$

con sujeción a $y^{(i)}(\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b) \ge 1 - \zeta^{(i)})$ y $\zeta^{(i)} \ge 0$ para $i=1, \cdots, m$

El forma dual es:

$\underset{\mathbf{\alpha}}\min{\dfrac{1}{2}\mathbf{\alpha}^t \cdot \mathbf{Q} \cdot \mathbf{\alpha} - \mathbf{1}^t \cdot \mathbf{\alpha}}$

con sujeción a $\mathbf{y}^t \cdot \mathbf{\alpha} = 0$ y $0 \le \alpha_i \le C$ para $i = 1, 2, \cdots, m$

où $\mathbf{1}$ es un vector lleno de 1s y $\mathbf{Q}$ es un $m \times m$ matriz con elementos $Q_{ij} = y^{(i)} y^{(j)} \phi(\mathbf{x}^{(i)})^t \cdot \phi(\mathbf{x}^{(j)})$ .

Ahora podemos utilizar el truco del núcleo calculando $Q_{ij}$ así:

$Q_{ij} = y^{(i)} y^{(j)} K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$

Así que el truco del kernel sólo puede utilizarse en la forma dual del problema SVM (además de otros algoritmos como la regresión logística).

Ahora puede utilizar las bibliotecas de programación cuadrática disponibles para resolver este problema, o utilizar multiplicadores lagrangianos para obtener una función sin restricciones (la función de coste dual), y luego buscar un mínimo utilizando la técnica de ascenso gradual o cualquier otra técnica de optimización. Uno de los enfoques más eficientes parece ser el algoritmo SMO implementado por el libsvm (para la SVM kernelizada).

Answer 3

Puede que me equivoque, pero no veo cómo podemos sustituir los productos punto por los núcleos sin convertirlo en el problema dual.

Los núcleos asignan la entrada implícitamente a un espacio de características en el que $x$ se convierte en $\phi(x)$ la función de pérdida se convierte entonces en
$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$
Si se aplica el núcleo gaussiano, $\phi(\mathbf{x}^{(i)})$ tendrá dimensiones ifinitas, por lo que $\mathbf{w}$ .

Parece difícil optimizar un vector de infinitas dimensiones utilizando directamente el descenso de gradiente.

Actualización
La respuesta de Firebug da una forma de sustituir los productos de puntos por núcleos en la formulación primal.