¿Es posible el Descenso de degradado para SVM kernelized (si es así, ¿por qué las personas usan la programación cuadrática)?

¿Por qué las personas usan técnicas de programación cuadrática (como SMO) cuando se trata de SVM kernelized? ¿Qué hay de malo en el descenso de gradiente? ¿Es imposible de usar con los núcleos o es demasiado lento (y por qué?).

Aquí hay un poco más de contexto: tratando de entender un poco mejor los SVM, usé Gradient Descent para entrenar un clasificador lineal de SVM usando la siguiente función de costo:

$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}$

Estoy usando las siguientes anotaciones:

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

I derivado de un vector (sub) gradiente (con respecto a y ) de esta ecuación, y pendiente de descenso funcionaba bien.$\mathbf{w}$$b$

Ahora me gustaría abordar problemas no lineales. ¿Puedo reemplazar todos los productos de punto con en la función de costo, donde es la función del núcleo (por ejemplo el RBF gaussiano, ), luego use el cálculo para obtener un vector (sub) gradiente y seguir con Gradient Descent?$\mathbf{u}^t \cdot \mathbf{v}$$K(\mathbf{u}, \mathbf{v})$$K$$K(\mathbf{u}, \mathbf{v}) = e^{-\gamma \|\mathbf{u} - \mathbf{v}\|^2}$

Si es demasiado lento, ¿por qué es eso? ¿La función de costo no es convexa? ¿O es porque el gradiente cambia demasiado rápido (no es Lipschitz continuo) por lo que el algoritmo sigue saltando a través de los valles durante el descenso, por lo que converge muy lentamente? Pero incluso entonces, ¿cómo puede ser peor que la complejidad de tiempo 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 GD estocástico con recocido simulado superarlos?

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

m × m u m × $\mathbf{K}$ es una matriz , y es una matriz . Tampoco es infinito.$m \times m$$\mathbf{u}$$m \times 1$

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

Ahora, por qué el dual es mucho más prominente no es obvio en absoluto: [1]

Las razones históricas por las cuales la mayor parte de la investigación en la última década ha sido sobre la optimización dual no están claras . Creemos que se debe a que los SVM se introdujeron por primera vez en su formulación de 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, se deben preferir los SVM de margen blando, 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 entrenamiento [Chapelle et al., 2000]

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

_{[1] Chapelle, O. (2007). Entrenamiento de una máquina de vectores de soporte en el primario. Cálculo neuronal, 19 (5), 1155-1178.}

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

$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 reemplaza por . Dado que el vector de peso es no transformado, el truco del núcleo no se puede aplicar a la función de coste superior .K ( u , v ) $\phi(\mathbf{u})^t \cdot \phi(\mathbf{v})$$K(\mathbf{u}, \mathbf{v})$$\mathbf{w}$

La función de costo anterior corresponde a la forma primaria del objetivo 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}}$

sujeto a y paraζ ( i ) ≥ 0 i = 1 , ⋯ , $y^{(i)}(\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b) \ge 1 - \zeta^{(i)})$$\zeta^{(i)} \ge 0$$i=1, \cdots, m$

La 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}}$

sujeto a y para0≤ α i ≤Ci=1,2,⋯,$\mathbf{y}^t \cdot \mathbf{\alpha} = 0$$0 \le \alpha_i \le C$$i = 1, 2, \cdots, m$

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

Ahora podemos usar el truco del kernel calculando así:$Q_{ij}$

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

Por lo tanto, el truco del kernel solo se puede usar en la forma dual del problema SVM (además de algunos otros algoritmos como la regresión logística).

Ahora puede usar bibliotecas de programación cuadrática disponibles para resolver este problema, o usar multiplicadores lagrangianos para obtener una función sin restricciones (la función de doble costo), luego busque un mínimo usando Gradient Descent o cualquier otra técnica de optimización. Uno de los enfoques más eficientes parece ser el algoritmo SMO implementado por la libsvmbiblioteca (para SVM kernelized).

Podría estar equivocado, pero no veo cómo podemos reemplazar los productos de punto con núcleos sin convertirlo en el doble problema.

Los núcleos asignan la entrada implícitamente a algún espacio de características donde convierte en , la función de pérdida se convierte en Si se aplica el núcleo gaussiano, tendrá ifinite dimensiones, también lo hará .ϕ ( x ) J ( w , b ) = C m ∑ i = 1 m a x ( 0 , 1 - y ( i ) ( w t ⋅ ϕ ( x ( i ) ) + b ) $x$$\phi(x)$
ϕ(x(i))$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}$
$\phi(\mathbf{x}^{(i)})$$\mathbf{w}$

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

La respuesta de Actualización de Firebug ofrece una forma de reemplazar los productos de punto con granos en la formulación primaria.