Cálculo de coeficientes de Lagrange para SVM en Python

Estoy tratando de escribir una implementación SVM completa en Python y tengo algunos problemas para calcular los coeficientes de Lagrange.

Primero déjame reformular lo que entiendo del algoritmo para asegurarme de que estoy en el camino correcto.

Si es un conjunto de datos e y i ∈ { - 1 , 1 } es la etiqueta de clase de x i , entonces ∀ i , y i ( w T x i + b ) ≥ $x_1, x_2, ..., x_n$$y_i \in \{-1, 1\}$$x_i$

$$\forall i, y_i(w^Tx_i + b) \geq 1$$

Entonces solo necesitamos resolver un problema de optimización para

$\|w\|^2$

sujeto a$y_i(w^Tx_i + b) \geq 1$

En términos de los coeficientes de Lagrange, esto se traduce en la búsqueda de , y y minimizando:$w$$b$$\alpha=(\alpha_1, \alpha_2, ... \alpha_n) \neq0$$\geq0$

$$L(\alpha, w, b) = \frac12 \|w\|^2 - \sum \alpha_i(y_i(w^Tx + b)-1)$$

Ahora desde y podemos reescribirlo como con restricciones

$$\frac{\partial L}{\partial w}=0 \implies w=\sum \alpha_i y_i x_i$$ $$\frac{\partial L}{\partial b}=0 \implies \sum y_i \alpha_i = 0$$ $$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j x_i^T x_j$$ $$\alpha_i \geq 0 \ \text{and} \ \sum \alpha_i y_i = 0$$

Así que estoy tratando de resolver el problema de optimización usando Python, y el único paquete gratuito que pude encontrar se llama cvxopt .

Me gustaría recibir ayuda para resolver esto, no pude encontrar ningún buen ejemplo al respecto, y aunque entiendo la teoría, me cuesta traducirlo a código (hubiera esperado lo contrario ya que estoy más de un fondo de programación).

Tenga en cuenta que en algún momento querré resolverlo usando Kernels pero no estoy seguro de cuáles son las implicaciones con respecto a resolver esto en código.

$$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j K(x_i,x_j)$$

Cualquier ayuda sería muy apreciada, estoy realmente perdido en cómo implementar esto en Python. Si tiene un mejor módulo para resolver el problema de optimización, me gustaría leer sobre él también.

He usado cvxopt para implementar un SVM antes, sin embargo, en matlab no python. Definitivamente servirá a su propósito, ya sea que sea lo suficientemente eficiente dependerá de para qué lo esté utilizando. Los SVM más eficientes no usan un paquete de solucionador QP, aprovechan algunas optimizaciones exclusivas de SVM. Muchos usan un algoritmo de estilo SMO para resolverlo.

LibSVM es un paquete SVM que utiliza el algoritmo en la selección del conjunto de trabajo utilizando información de segundo orden para máquinas de vectores de soporte de capacitación . El código es de código abierto, si está interesado en ver cómo se implementa. También tiene una interfaz de Python.

SVMLight es otro paquete, usan un algoritmo diferente (vea su sitio para referencias). También es de código abierto y tiene una interfaz de Python.

La forma general de su problema de optimización es un programa cuadrático , independientemente de si está utilizando el truco del núcleo o un núcleo lineal. Parece que cvxoptserá suficiente para lo que intentas hacer, pero otros pitonautas aquí también han tenido suerte con OpenOpt .