Antes de explicar el punto de usar el problema dual en SVM, permítanme decir algunas cosas que ayudan a comprender la necesidad de la forma dual en SVM.
Optimización sin restricciones (función objetiva sin restricción)
Un extremo (valor máximo / mínimo de una función) para un problema de optimización sin restricciones generalmente ocurre en un punto donde la pendiente es cero.
- ¿Hay algo que Deep Learning nunca podrá aprender?
- ¿Ya es posible aprender las reglas de un juego como Monopoly utilizando un aprendizaje no supervisado?
- ¿Dónde puedo encontrar algunas empresas que trabajen con técnicas de aprendizaje automático y minería de datos, en el campo biomédico?
- ¿Cuáles son algunas de las estadísticas más importantes y más engañosas en la predicción de partidos de fútbol?
- ¿Cuáles son los casos de uso de aprendizaje profundo en CRM?
Entonces, para encontrar un extremo, solo necesitamos buscar un punto donde la pendiente sea cero. Podemos escribir esta propiedad en una bonita forma matemática. Si [math] x ^ {*} [/ math] es un extremo para un problema de optimización sin restricciones, entonces
[matemáticas] \ bigtriangledown f (x ^ {*}) = 0 \ etiqueta * {} [/ matemáticas]
Optimización restringida con una restricción de igualdad
Si [math] x ^ {*} [/ math] es un extremo para un problema de optimización con una restricción de igualdad, entonces
[matemática] \ bigtriangledowndown f (x ^ {*}) = \ lambda \ times \ bigtriangledown g (x ^ {*}) \ tag * {} [/ math]
[matemáticas] g (x ^ {*}) = 0 \ etiqueta * {} [/ matemáticas]
Para tener una intuición detrás de las condiciones, visite la respuesta de Balaji Pitchai Kannu a ¿Cuál es el significado del valor de un multiplicador de Lagrange al hacer la optimización?
Optimización restringida con una restricción de desigualdad
Si [math] x ^ {*} [/ math] es un extremo para un problema de optimización con una restricción de desigualdad, entonces
Condiciones de KKT:
1. Factibilidad primaria: [matemática] g (x ^ {*}) \ leq 0 [/ matemática]
2. Viabilidad dual: [matemática] \ alpha \ geq 0 [/ matemática]
3. Holgura complementaria: [matemática] \ alpha g (x ^ {*}) = 0 [/ matemática]
4. Estacionariedad lagrangiana: [matemática] \ bigtriangledown f (x ^ {*}) = \ alpha \ times \ bigtriangledown g (x ^ {*}) [/ math]
Para encontrar un extremo para un problema de optimización con una restricción de desigualdad, necesitamos buscar un punto [matemático] (x ^ {*}) [/ matemático] que debe satisfacer todas las condiciones de KKT. Si desea conocer las intuiciones detrás de las condiciones de KKT, visite https://www.quora.com/What-is-an…
SVM (máquina de vectores de soporte)
SVM proporciona un hiperplano de separación óptimo. El hiperplano de separación dado por un SVM es óptimo porque observa el hiperplano de separación maximizando la distancia entre las dos clases en los datos de entrenamiento. Resuelve el siguiente problema de optimización para encontrar un hiperplano de separación óptimo.
[matemática] \ underset {\ beta_ {0}, \ beta_ {1}} {\ mathrm {Min}} \ hspace {0.4cm} \ frac {1} {2} || \ beta || ^ {2} \ etiqueta {1} [/ matemáticas]
[matemáticas] st: \ hspace {0.4cm} y_ {i} (x_ {i} ^ {T} \ beta + \ beta_ {0}) \ geq 1, \ hspace {0.4cm} i = 1 … N \ tag *{}[/matemáticas]
Es un problema de optimización con una restricción de desigualdad. Como ya he dicho
antes, necesitamos aplicar condiciones KKT para encontrar una solución óptima
para el problema anterior
La función lagrangiana (Primal) para el problema es
[matemáticas] L_ {p} = \ frac {1} {2} || \ beta || ^ {2} – \ sum_ {i = 1} ^ {N} \ alpha_ {i} [y_ {i} (x_ {i} ^ {T} \ beta + \ beta_ {0}) -1] \ tag * {} [/ math]
Al aplicar una condición de estacionariedad lagrangiana (una de las condiciones KKT), obtendremos
[matemáticas] \ beta = \ sum_ {i = 1} ^ {N} \ alpha_ {i} y_ {i} x_ {i} \ tag {4} [/ matemáticas]
[matemáticas] \ sum_ {i = 1} ^ {N} \ alpha_ {i} \ y_ {i} = 0 \ tag * {} [/ matemáticas]
Al sustituir la solución anterior en la ecuación 1, obtendremos la siguiente ecuación, que no es más que la forma dual del problema original.
[matemáticas] L_ {D} = \ sum_ {i = 1} ^ {N} \ alpha_ {i} – \ frac {1} {2} \ sum_ {i = 1} ^ {N} \ sum_ {k = 1 } ^ {N} \ alpha_ {i} \ alpha_ {k} y_ {i} y_ {k} \ underset {\ text {Producto interno}} {(x_ {i} ^ {T} x_ {k})} \ etiqueta {2} [/ math]
[matemáticas] st: \ alpha_ {i} \ geq 0 \ tag * {} [/ matemáticas]
[matemáticas] \ hspace {0.5cm} \ sum_ {i = 1} ^ {N} \ alpha_ {i} \ y_ {i} = 0 \ tag * {} [/ matemáticas]
Al aplicar las condiciones KKT restantes para el problema dual, se obtiene
[matemáticas] \ alpha_ {i} \ geq 0 \ etiqueta * {} \ forall i [/ matemáticas]
[matemáticas] \ alpha_ {i} [y_ {i} (x_ {i} ^ {T} \ beta + \ beta_ {0}) -1] = 0 \ forall i \ tag {3} [/ matemáticas]
Al resolver las ecuaciones anteriores, obtenemos [matemática] \ beta [/ matemática] y [matemática] \ beta_ {0} [/ matemática] que ayuda a encontrar un hiperplano de separación óptimo ([matemática] \ beta ^ {T} x + \ beta_ {0} [/ math]).
Ventajas del problema dual en SVM
- Una de las ventajas importantes de usar la forma dual en SVM es que nos permite aplicar núcleos. Kernel busca un hiperplano de separación óptimo en un espacio dimensional superior sin aumentar mucho la complejidad computacional. El núcleo se puede aplicar, si el algoritmo toma los puntos de datos como entrada en términos de su producto interno [matemática] (x_ {i} ^ {T} x_ {k}) [/ matemática]. Consulte la forma dual de la función objetivo (eq.2) que ingresa las características en términos de su producto interno.
- Consulte la ecuación 3 (es decir, condición de flojedad complementaria). (i) Si [math] \ alpha_ {i} \ geq 0 [/ math], entonces [math] y_ {i} (x_ {i} ^ {T} \ beta + \ beta_ {0}) = 1 [/ matemáticas]. En otras palabras, [math] x_ {i} [/ math] está en el límite del hiperplano. (ii) Si [math] y_ {i} (x_ {i} ^ {T} \ beta + \ beta_ {0}) \ geq 1 [/ math], entonces [math] x_ {i} [/ math] es no en el límite del hiperplano y [math] \ alpha_ {i} = 0. [/ math] De la ecuación 4, podemos decir que [math] \ beta [/ math] se define en términos de combinación lineal de [math ] x_ {i} [/ math] (que [math] \ alpha_ {i} \ geq 0, [/ math] es decir [math] x_ {i} [/ math] se encuentra en el límite del hiperplano). Entonces, [math] x_ {i} [/ math] se llaman puntos de soporte. Sabíamos que generalmente la cantidad de puntos de soporte para SVM son pocos. Significa que la mayoría de [math] \ alpha [/ math] (variable dual) son cero.
- Hay algunos algoritmos como SMO (Optimización mínima secuencial) que resuelve el problema dual de manera eficiente.
