universidad centroccidental decanato de...

UNIVERSIDAD CENTROCCIDENTAL“LISANDRO ALVARADO”

Decanato de Ciencias y TecnologíaLicenciatura en Ciencias Matemáticas

Maquinas vectoriales de soporte via lagrangianoaumentado

Trabajo Especial de Grado presentado porBr. Jacobo Alfonso Cortez Alejos.

Como requisito final para obtener el título deLicenciado en Ciencias Matemáticas

Área de Conocimiento: Matemática aplicada.Tutor: Dr. Javier Hernández Benítez.

Barquisimeto - VenezuelaJunio 2012

Maquinas vectoriales de soporte via lagrangianoaumentado

Br. Jacobo A. Cortez A.

En este proyecto se pretende estudiar el trabajo realizado por R.Polyaket. al [6] en el cual se construye una metodología de máquinas devectores de soporte (SVM) lineales basada en lagrangiano aumenta-do no-lineales. La formulación de SVM lineal basadas en lagrangianoaumentado nos lleva a un algoritmo que reduce la cantidad de vecto-res de soporte sin comprender el rendimiento de la clasificación si locomparamos con la formulación de SVM lineal con márgenes suavi-zados. El algoritmo propuesto en [6] calcula en cada paso una aproxi-mación tanto primal como dual. Las variables duales asociadas con ladata dada proveen una importante información acerca de dichos pun-tos y juegan un papel clave en la selección de los vectores de soporte.

A Dios, Anais, a mis padres y hermanos

Índice general

Índice de figuras iv

Agradecimientos vi

Introducción 1

1. Teoría de Optimización 1

1.1. Condiciones de optimalidad . . . . . . . . . . . . . . . . . . . . 2

1.1.1. Condición de primer orden . . . . . . . . . . . . . . . . . 3

1.2. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Lagrangiano Aumentado . . . . . . . . . . . . . . . . . . . . . . 7

i

ii

1.3.1. Propiedades del Lagrangiano Aumentado . . . . . . . . . 11

1.3.2. Métodos Prácticos de Lagrangiano Aumentado . . . . . . 17

1.3.3. Ventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.3.4. Desventajas . . . . . . . . . . . . . . . . . . . . . . . . . 23

2. Máquinas vectoriales de soporte (SVM) 24

2.1. SVM caso linealmente separable . . . . . . . . . . . . . . . . . . 25

2.2. SVM caso linealmente no separable . . . . . . . . . . . . . . . . 32

2.2.1. Funciónes Núcleo . . . . . . . . . . . . . . . . . . . . . . 35

3. Re-escalamiento no lineal para SVM 40

3.1. Métodos de barrera . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2. Formulación del rescalamiento no-lineal para SVM . . . . . . . . 43

4. Pruebas Numéricas 47

A. Códigos en MATLAB 56

A.1. generadatos.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

A.2. fsvmestandar1.m . . . . . . . . . . . . . . . . . . . . . . . . . . 57

A.3. svmlineal.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57


iii

A.4. fsvmestandar2.m . . . . . . . . . . . . . . . . . . . . . . . . . . 60

A.5. svm2.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

A.6. LA_SVM.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

A.7. ENL_SVM.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

A.8. funk.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.9. newtonmod.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.10.grad.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.11.armijo.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

A.12.Vecsoport.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

A.13.corridas.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Bibliografía 73


Índice de figuras

2.1. Caso linealmente separable . . . . . . . . . . . . . . . . . . . . . 29

2.2. Datos separados con hiperplano óptimo . . . . . . . . . . . . . . 31

2.3. Caso linealmente no separable . . . . . . . . . . . . . . . . . . . 32

2.4. Datos linealmente no separables . . . . . . . . . . . . . . . . . . 35

2.5. Efecto del núcleo . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1. Datos 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2. Datos 1 junto con hiperplano separador . . . . . . . . . . . . . . 49

4.3. Datos 1 con vectores de soporte . . . . . . . . . . . . . . . . . . 49

4.4. Datos 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

iv

ÍNDICE DE FIGURAS v

4.5. Datos 2 con hiperplano . . . . . . . . . . . . . . . . . . . . . . . 51

4.6. Datos 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.7. Datos 3 junto con hiperplano . . . . . . . . . . . . . . . . . . . . 52

4.8. penalidad k=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.9. penalidad k=500 . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.10. penalidad k=100 . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.11. Datos 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.12. Vectores de soporte para ε = 1e − 3 . . . . . . . . . . . . . . . . 55

4.13. Vectores de soporte para ε = 1e − 5 . . . . . . . . . . . . . . . . 55


Agradecimientos

Quiero expresar mi agradecimiento primeramente a Dios por darme fuerzas,por guiar mi camino, y darme sabiduría.

A mi tutor, el Dr. Javier Hernández Benítez por su ayuda, sus conocimientos,ideas, consejos y sobre todo por la confianza que depositó en mi.

A Anaís, por ser un pilar fundamental en este logro, por su ayuda, su apoyoincondicional, su comprensión; por estar siempre presente para darme ánimos,fuerzas y esperanzas en la vida. Por ser la luz en mi camino, mi motor para seguiradelante, y acompañarme con su inmenso cariño en todo momento.

A mis padres Jacobo y Carmen por darme el don de la vida, por brindarme suapoyo, por confiar en mi, por darme oportunidades, y por enseñarme lo importantedel respeto y los valores. A mis hermanos Jacobo Gerardo y Carmin, por suscomentarios, por su aliento, y por sus buenos sentimientos hacia mi.

A mis profesores Mario Rodriguez, Edner Pineda, Nicolás Arias, Miguel Vi-vas, Rómulo Castillo, Hugo Lara, Eibar Hernández, Victor Bernal y todos los quede una u otra forma han ayudado a mi formación académica tanto a nivel de se-

Agradecimientos vii

cundaria como universitario y también por haber ayudado en mi formación comopersona.

A mis compañeros y amigos Jonathan, Mariana, Emily, Alexander, Massiel,Rosyani, Juan, Geraldine por de una u otra manera ayudarme en el transcurso demi carrera.

A mi prima Lorena, y mi tía Aide por sus consejos y ayuda.


Introducción

En este trabajo se describe el documento desarrollado por Polak et al. (ver [6])donde expone una metodología de máquinas vectoriales de soporte o máquinas desoporte vectorial (SVM por sus siglas en inglés: Support vector machines) linealesbasadas en lagrangiano aumentado mediante re-escalamiento no lineal. Las SVMhan sido implementadas en diversos lenguajes de programación y con diferentesalgoritmos de optimización.

La versatilidad de las SVM las hace aplicables en áreas muy variadas como: envisión artificial para el reconocimiento de caracteres, rostros, matrículas y objetos;en medicina, para la clasificación de exámenes radiológicos, TAC (TomografíaAxial Computarizada), y para el diagnóstico de tejido humano; en genética parapredicción de genes; en la clasificación de documentos, entre muchas otras áreas.

Las máquinas de soporte vectorial o máquinas de vectores de soporte (SupportVector Machine, SVMs) son un conjunto de algoritmos de aprendizaje supervisa-do desarrollado por Vapnik (ver [9]) y su grupo de trabajo a principio de los años80 y se centra en lo que se conoce como Teoría del Aprendizaje Estadístico. In-tuitivamente, una SVM es un modelo que representa los puntos de una muestraen un espacio, separando estos puntos en clases y separándolos entre sí con la

1

Introducción 2

mayor distancia posible, es decir con un margen máximo. Una SVM, construyeun modelo capaz de predecir si un nuevo punto (cuya categoría es desconocida)pertenece a una categoría o a la otra.

En ese concepto de "separación óptima" es donde reside la característica fun-damental de las SVM: este tipo de algoritmos buscan el hiperplano que tenga lamáxima distancia (margen) con los puntos que estén más cerca de él mismo. Poreso también a veces se les conoce a las SVM como clasificadores de margen má-ximo. De esta forma, los puntos del vector que se etiquetados con una categoríaestarán a un lado del hiperplano y los casos que se encuentren en la otra categoríaestarán al otro lado.

Además, se desarrollará el método de Lagrangiano aumentado el cual es unade las clases generales de métodos de programación no lineal más efectivos, losmétodos de Lagrangiano aumentado se pueden considerar como métodos combi-nados de funciones de penalización cuadrática y de lagrangiano estándar.

La estructura de este trabajo esta diseñada de la forma siguiente: en el capí-tulo 1 se exponen temas de la teoría de optimización, tales como las condicionesde regularidad, las condiciones de optimalidad y dualidad. También se desarro-lla el tema del lagrangiano aumentado, mostrando propiedades y formulacionesreferentes a él.

En el capítulo 2 describimos las máquinas vectoriales de soporte estándar,estudiando en detalle cuando los datos son linealmente separables y cuando nolo son. Se introduce en la sección de caso linealmente separable la resoluciónanalítica del problema y los pasos a llevar a cabo para su solución; mientras quela sección de caso no separable linealmente se expone la estrategia a seguir parapoder separar los datos mediante el uso de funciones núcleo.

En el capítulo 3 se expone teoría sobre los métodos de barrera y se muestra laformulación del método de re-escalamiento no lineal para SVM.


Introducción 3

En capítulo 4 se muestran resultados de la implementación del método dere-escalamiento no lineal para SVM para diversos datos y también la estrategiaempleada para llegar a esos resultados.


1Teoría de Optimización

La teoría de optimización es una rama de las matemáticas relativamente nuevay su estudio ha tomado una gran importancia en la actualidad. Surge a media-dos del siglo XX por el interés de resolver algunos problemas de aquella época,relacionados con la política y la segunda guerra mundial. Esta rama estudia laresolución de problemas que consisten determinar el valor mínimo o máximo deuna función. Con el desarrollo del computador, la teoría de optimización se haconvertido en una rama muy importante de las matemáticas, la cual juega un pa-pel fundamental en la industria, milicia, comercio y muchas otras áreas. Graciasa su estudio se han desarrollado diversos algoritmos que ayudan a resolver pro-blemas y a la toma de decisiones. Uno de los estudios de mayor relevancia esel de determinar las características que cumplen las variables que hacen que unadeterminada función alcance su valor óptimo.

En la formulación de muchos problemas de optimización no se puede hacer lahipótesis de linealidad que caracteriza a la programación lineal. No existen pro-cedimientos generales para problemas no lineales. Se han desarrollado un grannúmero de algoritmos especiales para tratar casos particulares. Muchos de esosprocedimientos se basan en la teoría matemática relacionada con el análisis dela estructura de tales problemas. Esta teoría se llama generalmente optimización

1

Teoría de Optimización 2

clásica. Una de las principales contribuciones modernas a esta teoría son las con-diciones de optimalidad, también conocida como fue hecha por Karush, Kunh yTucker (ver [10]) quienes desarrollaron lo que se conoce como las condicionesKKT.

Las condiciones de optimalidad nos dan las características necesarias o sufi-cientes para saber si un punto x ∈ Rn es o no solución del problema de optimi-zación. Estas condiciones son la guía de una gran gama de algoritmos que nospermiten resolver una inmensa variedad de problemas en la vida cotidiana.

1.1. Condiciones de optimalidad

Consideremos el problema de minimizar una función en Rn sobre un subcon-junto de dicho espacio, una formulación general para minimización de funcionessujetas a restricciones sobre las variables es:

mınx∈Rn

f (x)

s.a. Ci(x) = 0, i ∈ ECi(x) ≥ 0, i ∈ I

(1.1.1)

donde f y las funciones Ci son todas suaves a valores reales sobre un subcon-junto de Rn , e I y E son dos conjuntos finitos de indices. La función f se laconoce como función objetivo, Ci , con i ∈ E son las restricciones de igualdad yCi , i ∈ I son las restricciones de desigualdad.

Si definimos el conjunto factible Ω como el conjunto de puntos x ∈ Rn quesatisfacen las restricciones, esto es

Ω =

x ∈ Rn∣∣∣ Ci(x) = 0, i ∈ E; Ci(x) ≥ 0, i ∈ I

, (1.1.2)



entonces podemos volver a escribir (1.1.1) de la forma siguiente

mınx∈Ω

f (x). (1.1.3)

Además, la función lagrangiana para el problema (1.1.1) se define:

L(x, λ) = f (x) −∑

i∈E∪I

λiCi(x). (1.1.4)

El conjunto de restricciones activas A(x) para un x ∈ Ω consiste de losíndices de las restricciones de igualdad de E con los indices de las restriccionesde desigualdad i para los cuales Ci(x) = 0; esto es,

A(x) = E ∪ i ∈ I|Ci(x) = 0 (1.1.5)

Definición 1.1.1 (Condición de regularidad (ver [10])) Dado el punto x∗ y elconjunto A(x∗) , se dice que x∗ es LICQ si el conjunto de los gradientes de lasrestricciones activas ∇Ci(x∗), i ∈ A(x∗) es linealmente independiente.

Tenga en cuenta que si se cumple esta condición, ninguno de los gradientes derestricciones activas puede ser cero.

1.1.1. Condición de primer orden

Las condiciones de primer orden están basadas en el gradiente (vector de lasprimeras derivadas) de la función objetivo y las restricciones.

Teorema 1.1.2 (Condiciones necesarias de primer orden, (ver [10])) Supongamosque x∗ es una solución local de (1.1.1) y que (LICQ) se cumple en x∗ , entonces



existe λ∗ un vector multiplicador de lagrange con componentes λ∗i , i ∈ E ∪ I ,de tal manera que las siguiente condiciones se cumplen para (x∗, λ∗)

∇xL(x∗, λ∗) = 0 (1.1.6)

Ci(x∗) = 0, ∀i ∈ E (1.1.7)

Ci(x∗) ≥ 0, ∀i ∈ I (1.1.8)

λ∗i ≥ 0, ∀i ∈ I (1.1.9)

λ∗i Ci(x∗) = 0, ∀i ∈ E ∪ I. (1.1.10)

Las expresiones (1.1.6) se les conoce como las condiciones de Karush-Kuhn-Tuker, o condiciones KKT para abreviar. Las condiciones de complementariedadimplican los multiplicadores de lagrange correspondiente a las restricciones conindices i < A(x∗) deben ser ceros. De la primera condición (KKT) obtenemos losiguiente:

0 = ∇xL(x∗, λ∗) = ∇ f (x∗) −∑

i∈A(x∗)

λ∗i∇Ci(x∗) (1.1.11)

Definición 1.1.3 (Complementariedad estricta (ver [10])) Dada una solución lo-cal x∗ de (1.1.1) y un vector λ∗ que satisface (1.1.6), diremos que se cumple lacondición de complementariedad estricta si satisface (1.1.10) con λ∗i > 0 paracada i ∈ I

⋂A(x).

Para el problema (1.1.1) y el punto x∗ como solución, pueden haber muchosvectores λ∗ para los que las condiciones KKT se satisfacen. Pero cuando (LICQ)se cumple, el λ∗ óptimo es único.

1.2. Dualidad

En los últimos años, la dualidad ha tenido una función central en el desarro-llo y unificación de la teoría de la optimización. Desde este punto de vista han



aparecido nuevas y valiosas interpretaciones de los multiplicadores de Lagrangey la evolución de nuevos algoritmos efectivos para una amplia clase de problemasprácticos.

Los métodos basados en dualidad, también llamados métodos duales se fun-damentan en que los multiplicadores de Lagrange son las incógnitas principalesasociadas a un problema con restricciones; una vez conocidos estos multiplica-dores, la determinación del punto solución (al menos en algunas situaciones essencilla). Por tanto los métodos duales no tratan directamente el problema conrestricciones original sino que se aplican a un problema alternativo, el problemadual, cuyas incógnitas son los multiplicadores de Lagrange del primer problema.

Así, para un problema con n variables y m restricciones de igualdad, los méto-dos duales operan en el espacio m dimensional de los multiplicadores de Lagran-ge. Los multiplicadores de Lagrange miden la sensibilidad y, por tanto, suelentener interpretaciones intuitivas significativas.

El problema

mınx∈Rn

f (x) sujeto a Ci(x) = 0, i ∈ E; Ci(x) ≥ 0, i ∈ I

se puede reescribir, asumiendo que existen m restricciones de desigualdad comosigue:

mınx∈Rn

f (x)

s.a Ci(x) ≥ 0 i = 1, . . . ,m(1.2.1)

Ahora, considerando:

C(x) := (C1(x),C2, . . . ,Cm(x))T . (1.2.2)

podemos escribir el problema como:

mınx∈Rn

f (x)

s.a C(x) ≥ 0m×1,(1.2.3)



para la cual la función Lagrangiana con vector multiplicador de Lagrange λ ∈ Rm

es:L(x, λ) = f (x) − λTC(x). (1.2.4)

Definamos la función objetivo dual q : Rn 7→ R como sigue:

q(λ) := ınfx∈RnL(x, λ). (1.2.5)

En muchos problemas, este ínfimo es −∞ para algunos valores de λ. Definamosel dominio de q como el conjunto de valores λ para el cual q es finito, esto es

D := x|q(λ) > −∞. (1.2.6)

Cuando f y −Ci son funciones convexas y λ ≥ 0 (el caso en que más estamosinteresados), la función L(·, λ) es también convexa. En esta situación, todo mini-mizador local es también minimizador global.

El problema dual demınx∈Rn

f (x)

s.a C(x) ≥ 0m×1,(1.2.7)

está definido como sigue:maxλ∈Rn

q(λ)

s.a λ ≥ 0.(1.2.8)

El siguiente teorema es un importante resultado de la teoría de optimización:

Teorema 1.2.1 (Dualidad Débil (ver [10])) Para cualquier x factible para (1.2.8)y cualquier λ, tenemos que q(λ) ≤ f (x).

El teorema nos indica que el valor óptimo del problema dual (1.2.8) proveeuna cota inferior para el valor objetivo óptimo del problema primal (1.2.7).

Ahora, el siguiente resultado muestra como el multiplicador de lagrange ópti-



mo (1.2.8) son soluciones del problema dual (1.2.7) bajo ciertas condiciones.

Teorema 1.2.2 (ver [10]) Supongamos que x es una solución de (1.2.3) y que fy −Ci, i = 1, . . . ,m son funciones convexas en Rn que son diferenciables en x .Entonces cualquier λ para el cual (x, λ) satisfacen las condiciones de KKT essolución de (1.2.7)

Teorema 1.2.3 (ver [10]) Supongamos que f y −Ci , i = 1, . . . ,m son conve-xas y continuamente diferenciable en Rn. Supongamos que x es una solución de(1.2.3) en el que LICQ se cumple. Suponga que λ resuelve (1.2.7) y que el ínfi-mo en ınfxL(x, λ) es alcanzado en x. Supongamos además que L(·, λ) es unafunción estrictamente convexa , entonces x = x, que es, x es la única soluciónde (1.2.3) y f (x) = L(x, λ).

1.3. Lagrangiano Aumentado

Una de las clases generales de métodos de programación no lineal más efec-tivos es la de los métodos del lagrangiano aumentado. Estos métodos se puedenconsiderar como métodos combinados de funciones de penalización cuadrática yde lagrangiano estándar; los dos conceptos operan juntos para eliminar muchas delas desventajas asociadas a cada uno de los métodos por separado.

El lagrangiano aumentado para el problema con restricciones de igualdad:

mınx∈Rn

f (x)

s.a. Ci(x) = 0, i ∈ E(1.3.1)

es la función, LA : Rn+m+1 → R, dada por:

LA(x, λ; µ) = f (x) −∑i∈E

λiCi(x) +µ

2

∑i∈E

C2i (x), (1.3.2)



donde m = #(E), λ = (λ1, . . . , λm)T y µ > 0 es un parámetro de penalidad.

Como vemos a diferencia de la función lagrangiana estándar,

L(x, λ) = f (x) −m∑

i=1

λiCi(x),

donde λi representa el multiplicador de Lagrange asociado a la restricción Ci(x), lafunción lagrangiano aumentado se obtiene al “aumentar” la función lagrangianaestándar con un término de penalización cuadrático.

Actualización de la constante de penalización:

En los métodos basados en lagrangiano aumentado es necesario determinar elvalor que toma la constante de penalización. Este parámetro puede permanecerconstante a lo largo de las iteraciones del algoritmo o bien incrementarse pocoa poco. La principal ventaja de los métodos basados en lagrangiano aumentadorespecto a los métodos clásicos de penalización es que no es necesario aumentarhasta un valor muy elevado el parámetro de penalidad, por lo que esta técnica evitaproblemas de estabilidad numérica.

No existe un criterio riguroso que establezca la mejor elección de este pará-metro. En la práctica se deben tener en cuenta las siguientes consideraciones:

• El valor inicial del parámetro de penalización µ0 no debe ser tan grandecomo para que el primer problema resuelto tenga problemas numéricos.

• El valor inicial del parámetro de penalización µ0 no debe ser muy pequeñopues el término cuadrático que se introduce a la función Lagrangiano Au-mentado se hace despreciable y se tendrían los inconvenientes propios de lafunción Lagrangiana.

• El incremento del parámetro de penalización en cada iteración no debe ser



tan grande como para que se produzcan inconvenientes en las primeras ite-raciones del algoritmo.

• El incremento del parámetro de penalización a medida que aumentan lositerados no debe ser tan pequeño (al menos en las primeras iteraciones)como para que no converjan los multiplicadores de Lagrange.

• Como puntos iniciales para las variables de optimización es convenientetomar sus valores en iteraciones previas.

Criterio de Parada:

El algoritmo de lagrangiano aumentado finaliza cuando se anula el gradientede dicha función, lo que se traduce en la práctica que la norma del gradiente esmenor que cierta tolerancia, esto es:

‖∇xLA(xk, λk; µk)‖ ≤ τk.

Convergencia:

La convergencia del algoritmo basado en el lagrangiano aumentado dependeprincipalmente de dos factores: el método de actualización de los multiplicadoresde Lagrange y la elección del parámetro de penalización.

Algoritmo:

Para este método se diseña un algoritmo fijando el parámetro de penalidad µpara algún valor µk > 0 en la k-ésima iteración, fijando λ como el actual estimadoλk y realizando la minimización respecto a x; usando xk como el minimizadoraproximado de LA(x, λk; µk). Así, por las condiciones necesarias de primer orden,



tenemos:0 ≈ ∇xLA(xk, λ

k; µk),

Por otra parte,

∇xLA(xk, λk, µk) = ∇ f (xk) −

∑i∈E

λki∇Ci(xk) +

µ

2

∑i∈E

2Ci(xk)∇Ci(xk)

= ∇ f (xk) −∑i∈E

λki∇Ci (xk) + µ

∑i∈E

Ci (xk)∇Ci (xk)

= ∇ f (xk) −∑i∈E

(λk

i − µkCi(xk))∇Ci(xk)

Por tanto,

∇ f (xk) −∑i∈E

(λk

i − µkCi(xk))∇Ci(xk) ≈ 0.

Luego, por la condición de optimalidad para el problema (1.3.1), es decir:

∇ f (x∗) − A (x∗)T λ∗ = 0,

donde A denota la matriz de los gradientes de las restricciones, deducimos

λ∗i ≈ λki − µkCi(xk), ∀i ∈ E

en consecuencia,

Ci(xk) ≈−1µk

(λ∗i − λki ), ∀i ∈ E. (1.3.3)

Así concluimos que, sí λk es cercano al vector multiplicador óptimo λ∗, lainfactibilidad en xk será mucho más pequeña que 1

µk.

Una fórmula para nuestro estimador actual λk, del vector de lagrange, nos lasugiere (1.3.3), esto es,



λ∗i ≈ λki − µkCi(xk), ∀i ∈ E.

Con esto, formulamos un algoritmo diseñado para encontrar el punto dondees alcanzado el valor mínimo de una función, bajo restricciones de igualdad, me-diante el método lagrangiano aumentado.

Algoritmo 1 Algoritmo Lagrangiano Aumentado (para restricciones de igualdad)DATOS DE ENTRADA: µ0 > 0, τ0 > 0 (tolerancia), puntos iniciales xs

0 y λ0

for k = 0, 1, 2, ... doEncontrar un minimizador aproximado xk de LA(·, λk, µk), desde el punto ini-cial xs

k y terminar cuando ‖LA(xk, λk; µk)‖ ≤ τk;

if una prueba de convergencia para (1.3.1) es satisfecha thenfinalizar con solución aproximada xk;

end ifActualizar:

λk+1i = λk

i − µkCi(xk) (multiplicador de Lagrange)µk+1 ≥ µk (parámetro de penalización)xs

k+1 = xk

Seleccionar: τk+1 (nueva tolerancia)end for

1.3.1. Propiedades del Lagrangiano Aumentado

Ahora, veremos que la convergencia de este método se puede asegurar sin te-ner que incrementar µ indefinidamente. Por lo tanto, el mal condicionamiento esmenos problemático que en los métodos de función de penalidad cuadrática, yde esta manera la elección del punto xs

k+1 en el algoritmo es menos crítica (só-lo tenemos que comenzar la búsqueda en la iteración k + 1 con el minimizadoraproximado previo, xk). La tolerancia τk podría ser escogida dependiendo de la



infactibilidad∑i∈E|C(xk)|, y el parámetro de penalidad µ puede ser incrementado si

la reducción en la medida de la infactibilidad es insuficiente en la presente itera-ción.

Ahora, veremos dos resultados que justifican el uso de la función lagrangianoaumentado y el método de multiplicadores para problemas de restricciones deigualdad.

Teorema 1.3.1 (ver [10]) Sea x∗ solución local del problema (1.3.1), donde∇xCi(x∗),con i ∈ ε, son linealmente independientes y donde son satisfechas las condionessuficientes de segundo orden para λ = λ∗. Entonces, existe µ tal que para todoµ ≥ µ, x∗ es un mínimo local estricto de LA(x, λ∗; µ).

Demostración:

Probemos que x∗ satisface las condiciones suficientes de segundo orden paratodo µ suficientemente grande, esto es,

∇xLA(x∗, λ∗, µ) = 0 y

∇2xxLA(x∗, λ∗, µ) es definida positiva.

Ahora, ya que x∗ es solución local del problema (1.3.1) y ∇xCi(x∗), i ∈ E sonvectores l.i; entonces por teorema, tenemos que:

∇xL(x∗, λ∗) = 0 y

Ci(x∗) = 0, ∀i ∈ E.



Veamos,

∇xLA(x∗, λ∗; µ) = ∇x f (x) −∑i∈E

(λ∗i − µCi(x∗)

)∇xCi(x∗)

= ∇x f (x) −∑i∈E

λiCi(x∗), ya que Ci(x∗) = 0, ∀ i ∈ E

= ∇xL(x∗, λ∗)

= 0

Así, hemos probado que:∇xLA(x∗, λ∗, µ) = 0. (1.3.4)

Definamos, A(x∗)t = [∇xCi(x)]i∈E.

Luego, como:

∇xLA(x∗, λ∗; µ) = ∇xL(x∗, λ∗) +∑i∈E

µCi(x∗)∇xCi(x∗),

entonces,

∇2xxLA(x∗, λ∗, µ) = ∇2

xxL(x∗, λ∗) +∑i∈E

µ∇xCi(x∗)t∇xCi(x∗) +∑i∈E

µCi(x∗)∇2xxCi(x∗)

=⇒ ∇2xxLA(x∗, λ∗; µ) = ∇2

xxL(x∗, λ∗) +∑i∈E

µ∇xCi(x∗)t∇xCi(x∗),

dado que Ci(x∗) = 0,∀ i ∈ E.

Así, podemos escribir:

∇2xxLA(x∗, λ∗; µ) = ∇2

xxL(x∗, λ∗) + µAt A. (1.3.5)

Supongamos por absurdo que ∇2xxLA(x∗, λ∗, µ) no es definida positiva, así, po-

demos construir una sucesión µk con µk → ∞, tal que para cada µk podemosencontrar un vector wk con ‖wk‖ = 1, tal que:



0 ≥ wtk∇

2xxLA(x∗, λ∗, µ)wk.

Así,

0 ≥ wtk

(∇2

xxL(x∗, λ∗) + µAt A)

wk

0 ≥ wtk∇

2xxL(x∗, λ∗)wk + wt

kµAt A wk

0 ≥ wtk∇

2xxL(x∗, λ∗)wk + µk ‖A wk‖

22 (1.3.6)

‖A wk‖22 ≥ −

1µk

wtk∇

2xxL(x∗, λ∗)wk,

en consecuencia se tiene,

‖A wk‖22 → 0 cuando µk → ∞.

Como los vectores wk están en un conjunto compacto (sobre la superficie dela esfera unitaria), entonces wk tiene un punto de acumulación, digamos w. Así,

A w = 0 (1.3.7)

De (1.3.6), tenemos:

wtk∇

2xxL(x∗, λ∗)wk ≤ −µk‖A wk‖

22 ≤ 0

=⇒ wt∇2xxL(x∗, λ∗)w ≤ 0, tomando limites en ambos lados, y (1.3.7).

Esto último es una contradicción, ya que contradice la condición de segundo ordenpara el lagrangiano estándar L(x∗, λ∗).

Así, wt∇2xxL(x∗, λ∗)w > 0 para todo vector w distinto del vector nulo, con

A w = 0.



Por tanto,

wtk∇

2xxLA(x∗, λ∗; µ)wk > 0,∀w , ∅ con A w = 0. (1.3.8)

Finalmente, de (1.3.4) y (1.3.8) podemos concluir que x∗ satisface las condi-ciones suficientes de segundo orden para todo µ suficientemente grande, así x∗ esun mínimo local estricto de LA(x, λ∗; µ).

Esto nos demuestra que cuando conocemos el vector multiplicador de Lagran-ge exacto λ∗, la solución del problema (1.3.1) es un minimizador local estricto deLA(x, λ∗; µ) para todo µ suficientemente grande. Y aunque en la práctica no cono-cemos λ∗, estos resultados nos sugieren que podemos obtener un buen estimadorde x∗ minimizando LA(x, λ; µ), incluso cuando µ no es particularmente grande,siempre que λ sea un buen estimador de λ∗.

El siguiente teorema, describe más la situación real, cuando λ , λ∗; nos pro-porciona las condiciones bajo las cuales existe un minimizador de LA(x, λ; µ) quese encuentra cerca de x∗; además de los márgenes de error para xk y λk+1 obtenidosa partir de la solución del subproblema en la k-ésima iteración.

Teorema 1.3.2 (ver [10]) Supongamos que las hipótesis del teorema 1 son satis-fechas para x∗ y λ∗, y sea µ, como en el teorema 1. Entonces existen escalarespositivos δ, ε, y M tales que se verifican las siguientes afirmaciones:

1. Para todo λk y µk satisfaciendo:

‖λk − λ∗‖ ≤ µk δ, µk ≥ µ, (1.3.9)

el problema:

mınx∈RnLA(x, λk; µk)

sujeto a ‖x − x∗‖ ≤ ε,



tiene única solución xk. Además,

‖xk − x∗‖ ≤ M‖λk − λ∗‖

µk. (1.3.10)

2. Para todo λk y µk que satisfacen (1.3.9),

‖λk+1 − λ∗‖ ≤ M‖λk − λ∗‖

µk, (1.3.11)

donde λk viene dado por (1.3.3).

3. Para todo λk satisfaciendo (1.3.9), la matriz ∇2xxLA(xk, λ

k; µk) es definidapositiva y los gradientes de las restricciones∇Ci(xk), i ∈ E, son linealmenteindependientes.

Este teorema ilustra algunas de las propiedades sobresalientes del método delagrangiano aumentado, (1.3.10) prueba que xk estará cerca de x∗ si λk = λ∗ oel parámetro de penalidad µk es grande. Por tanto, este método nos da dos for-mas de mejorar la exactitud de xk, mientras que los métodos de función de pe-nalidad cuadrática solo nos ofrece una, la de incrementar µk. Por otro lado, de(1.3.11) podemos garantizar una mejora en la exactitud de la escogencia de losmultiplicadores, para µk suficientemente grande. Y por su parte 3, muestra que lascondiciones suficientes de segundo orden para minimización sin restricciones sonsatisfechas en el subproblema de la k-ésima iteración, bajo las condiciones dadas;y con esto podemos esperar un buen desempeño de la aplicación de las técnicasde minimización sin restricciones.



1.3.2. Métodos Prácticos de Lagrangiano Aumentado

Formulación de restricciones acotadas:

Dado un programa no lineal:

mınx

f (x) sujeto a Ci(x) = 0, i ∈ ε Ci(x) ≥ 0, i ∈ I

podemos convertirlo a un problema con restricciones de igualdad y restriccio-nes acotadas introduciendo variables de exceso si y reemplazando las desigualda-des generales Ci(x) ≥ 0, i ∈ I, por:

Ci(x) − si = 0, si ≥ 0 ∀i ∈ I

Las restricciones acotadas, ` ≤ x ≤ u, no necesitan ser transformadas.

mınx

f (x) sujeto a Ci(x) = 0, i = 1, 2, . . . ,m, ` ≤ x ≤ u (1.3.12)

Las variables de exceso si fueron incorporadas en el vector x y las funcionesde restricciones Ci fueron redefinidas adecuadamente.

Tenemos enumeradas las restricciones consecutivamente con i = 1, 2, . . . ,m yestas restricciones van a ser reunidas en el vector función C : Rn → Rm.

Algunas de las componentes del vector de las cotas inferiores ` puede ser−∞, lo cual significa que no existe cota inferior de la componente x en cuestión,similarmente para u.



El Lagrangiano de las restricciones acotadas (BCL por sus siglas en inglés)incorpora sólo las restricciones de igualdad para (1.3.12).

Esto es,

LA(x, λ; µ) = f (x) −m∑

i=1

λiCi(x) +µ

2

m∑i=1

C2i (x)

Las restricciones acotadas se hacen cumplir explícitamente en el subproblema,el cual tiene la forma:

mınxLA(x, λ; µ) sujeto a ` ≤ x ≤ u

Después, este problema es resuelto aproximadamente, los multiplicadores λ yel parámetro de penalidad µ son actualizados y el proceso se repite.

Una técnica eficiente para resolver el programa no-lineal con restriccionesacotadas (para λ y µ fijos) es el método del gradiente proyectado (no lineal).

Especificando las condiciones KKT para el problema:

mınxLA(x, λ; µ) sujeto a ` ≤ x ≤ u

podemos hallar las condiciones necesarias de primer orden para x que será solu-ción de mın

xLA(x, λ; µ) sujeto a ` ≤ x ≤ u, esto es:

x − P(x − ∇xLA(x, λ; µ), `, u) = 0

donde P(g, `, u) es la proyección del vector g ∈ Rn sobre la caja rectangular [`, u]definida como sigue:



P(g, `, u)i =

ì si gi ≤ ì

gi si gi ∈ (ì, ui) ∀i = 1, 2, . . . , nui si gi ≥ ui

Formulación de Restricciones Lineales:

La principal idea detrás de los métodos de lagrangiano con restricciones li-neales (LCL por sus siglás en inglés) es generar un paso para minimizar el la-grangiano (o lagrangiano aumentado) sujeto a linealización de restricciones. Siusamos la formulación del problema de PNL:

mınx

F(x) sujeto a C(xk) + Ak(x − xk) = 0, ` ≤ x ≤ u,

existen opciones elecciones para Fk(x).

Una opción es definir:

Fk(x) = f (x) −m∑

i=1

λki C−ki (x),

donde λk es el actual estimado del multiplicador de Lagrange y C−ki (x) es la dife-

rencia entre Ci(x) y su linealización en xk, esto es,

C−ki (x) = Ci(x) −Ci(xk) − ∇Ci(xk)T (x − xk)

Se puede mostrar que cuando xk converge a la solución x∗, el multiplicador deLagrange asociado con la restricción de igualdad en;



C(xk) + Ak(x − xk) = 0, ` ≤ x ≤ u

converge a el multiplicador optimal.

Formulación sin restricciones:

Podemos obtener una forma sin restricciones para el subproblema Lagran-giano aumentado para problemas de desigualdades restringidas, usando una deri-vación basada en la aproximación de puntos próximos. Supongamos por simplici-dad que el problema no tiene restricciones de igualdad (ε = ∅). Así, reescribimosel problema:

mınx

f (x) sujeto a Ci(x) = 0, i ∈ ε, Ci(x) ≥ 0, i ∈ I

de forma equivalente, como un problema de optimización sin restricciones

mınx∈Rn

F(x)

donde,

F(x) = maxλ≥0 f (x) −

∑i∈ε

λiCi(x) =

f (x), si x es factible∞, en otro caso

Para verificar esta expresión para F, consideramos primero el caso en el que xno es factible, esto es Ci(x) < 0 para algún i. Podemos escoger λi arbitrariamentegrande y positivo mientras colocamos λ j = 0, ∀ j , i, y verificamos que F(x) esinfinito en este caso. Si x es factible, entonces tenemos que Ci(x) ≥ 0,∀i ∈ I. Así,



el máximo es logrado en λ = 0, y F(x) = f (x) en este caso.

Así, obtenemos:

mınx∈Rn

F(x) = mınx factible

f (x)

el cual es simplemente el problema original con desigualdades restrictas. Mi-nimizar F directamente no es practico, de cualquier modo, como la función no essuave, ella salta desde un valor finito a un valor infinito, cruzando la frontera delconjunto factible.

Podemos aproximar de modo más practico reemplazando F por una aproxima-ción suave F(x, λk, µk) la cual depende del parámetro de penalidad µk y el estimadodel multiplicador de Lagrange λk. Esta aproximación es definida, como sigue:

F(x, λk, µk) = maxλ≥0 f (x) −

∑i∈ε

λiCi(x) −1

2µk

∑i∈ε

(λi − λki ) (1.3.13)

El término final en esta expresión aplica una penalidad para cualquier movi-miento de λ lejos del estimado previo λk; esto anima al nuevo maximizador λ aquedarse proximo al estimado previo λk. Como representa un problema cuadráti-co de restricciones acotadas en λ, separable en las componentes individuales λi,podemos ejecutar la maximización explícita, para obtener:

λi =

0 , si −Ci(x) +λk

iµk≤ 0

λki − µkCi(x), en otro caso

Sustituyendo estos valores en (1.3.13), encontramos que:



F(x, λk, µk) = f (x) +∑i∈I

ψ(Ci(x), λki ; µk);

donde la función ψ de tres argumentos escalares es dada por:

ψ(t, σ, µ) =

−σt +µ

2 t2, si t − σµ≤ 0

− 12µσ

2, en otro caso

Por lo tanto, podemos obtener el nuevo iterado xk por minimización de F(x, λk, µk)con respecto a x, y usar la fórmula para obtener la actualización del multiplica-dor de Lagrange estimado λk+1. Por comparación con el algoritmo, vemos que Fjuega el rol de LA y el de salto describe la extensión del método de Lagrangianoaumentado para restricciones de igualdad.

Concluiremos esta sección mencionando algunas de las ventajas y desventajasdel método lagrangiano aumentado:

1.3.3. Ventajas

La principales ventajas de los métodos de Lagrangiano Aumentado es que, porun lado evitan los problemas numéricos propios de los métodos de penalizaciónal limitar el incremento de este parámetro; y por otro, evitan un comportamientooscilatorio en el acercamiento al valor óptimo del problema dual, común en losmétodos de relajación Lagrangiana, puesto que convexifican la función objetivodel problema primal.



1.3.4. Desventajas

La principal desventaja es que la elección del parámetro de penalización estácondicionada por la estructura particular del problema a resolver y, normalmenteno es posible establecer un rango de variación general para el mismo.


2Máquinas vectoriales de soporte (SVM)

Las máquinas de soporte vectorial o máquinas de vectores de soporte (SupportVector Machine, SVMs) son un conjunto de algoritmos de aprendizaje supervisa-do desarrollado por Vapnik (ver [9]) y su grupo de trabajo. Intuitivamente, unaSVM es un modelo que representa los puntos de una muestra en un espacio, se-parando estos puntos en clases y separándolos entre sí con la mayor distanciaposible, es decir con un margen máximo. Una SVM, construye un modelo capazde predecir si un nuevo punto (cuya categoría es desconocida) pertenece a unacategoría o a la otra.

Más formalmente, supongamos que tenemos un conjunto de puntos de datosque se han clasificado de una o dos maneras: ellos tienen cierta propiedad o nola tienen. Estos puntos de datos pueden representar los subtítulos de email, loscuales son clasificados como email legítimos o falsos; o pueden representar datosmédicos tales como la edad, sexo, peso, presión sanguínea, niveles de colesterol,o a alguna característica genética de pacientes que pueda ser clasificada como deriesgo ó bajo riesgo para un ataque al corazón, etc.

Supongamos ahora que se obtiene un nuevo punto como dato. La meta esdeterminar si este nuevo punto de dato tiene o no la propiedad. El conjunto de

24

Máquinas vectoriales de soporte (SVM) 25

técnicas para hacer esto es ampliamente conocido como clasificación de patrones(ver [1]). La principal idea es identificar alguna regla basada sobre la data (conoci-do como el entrenamiento de los datos) que caracterice al conjunto de puntos quetengan la propiedad, lo cual puede ser usado para determinar si un nuevo puntotiene la propiedad o no la posee.

2.1. SVM caso linealmente separable

Definición 2.1.1 (Hiperplano de separación (ver [8])) Sean C1 y C2 conjuntosno vacíos en Rn. Un hiperplano H se dice que separa a C1 y C2 sí C1 está con-tenido en uno de los semiespacios cerrados asociados con H y C2 yace en elsemiespacio cerrado opuesto. El se dice que separa a C1 y C2 propiamente sí C1

y C2 no están ambos al mismo tiempo contenidos en H. El se dice que separafuertemente a C1 y C2 si existe algún ε > 0 tal que C1 + εB está contenida enuno de los semiespacios abiertos asociados con H y C2 + εB está contenido enel semiespacio abierto opuesto, donde B es la bola Euclidea unitaria x||x| ≤ 1.Otra clase de separación es la separación estricta, donde C1 y C2 simplementepertenecerían a los semiespacios opuestos abiertos.

El siguiente teorema nos garantiza, bajo determinadas asunciones la existenciade un hiperplano de separación:

Teorema 2.1.2 (ver [8]) Sean C1 y C2 conjuntos no vacíos enRn. Entonces existeun hiperplano que separa C1 y C2 propiamente si y sólo si existe un vector b talque

ınf〈x, b〉|x ∈ C1 ≥ sup〈x, b〉|x ∈ C2,

sup〈x, b〉|x ∈ C1 > ınf〈x, b〉|x ∈ C2.

Entonces existe un hiperplano que separa C1 y C2 fuertemente si y sólo si existe



un vector b tal que

ınf〈x, b〉|x ∈ C1 > sup〈x, b〉|x ∈ C2.

Supongamos que tenemos un conjunto etiquetado de entrenamiento de los da-tos xi con clasificación yi, donde yi = 1 ó yi = −1.

Es decir, existe un hiperplano en Rn que nos separa la muestra en dos clases,ya que los vectores xi asociados a los datos de una clase estarán a un lado delhiperplano y los asociados a la otra clase en en otro lado del hiperplano. El procesoanteriormente descrito, puede verse también como si los puntos positivos quedana un lado del hiperplano y los puntos negativos del otro. O de otra manera, existeun par (w, b) ∈ Rn+1 tal que xT

i w + γ > 0 si el punto i está en la clase positiva yxT

i w + γ < 0 si el punto i está en la clase negativa.

Para obtener mejores resultados quisiésemos que la separación de los hiperpla-nos fuese la más amplia posible. Consideremos las distancias d+ y d−. La distanciad+ es la distancia euclídea entre el hiperplano y la clase positiva. Es decir, la dis-tancia entre el hiperplano y la clase positiva. De manera similar, pero respecto ala clase negativa se define d−. Una vez determinadas estas distancias, se define elmargen de separación del hiperplano como la suma d+ + d−.

Ya que no es una buena práctica incluir desigualdades estrictas en los proble-mas de optimización, sería bueno poder conseguir condiciones equivalentes a lasanteriores pero que sean del tipo “mayor o igual” o “menor o igual”.

Ahora, ya que si un hiperplano está definido por el par (w, b), entonces cual-quier par de la forma (λw, λb) con λ > 0 también define el mismo hiperplano, ysi xT

i w + γ > 0 para un par en particular (w, γ) entonces existe un par (wi, γi) quedefine el mismo hiperplano y tal que xT

i wi + γi ≥ 1. De manera similar podemosproceder para la clase negativa. Ya que el conjunto de entrenamiento es finito, siexiste un par (w, γ) que satisface las restricciones para todos los datos, entoncesexiste un par (w′, γ) que define el mismo hiperplano tal que el lado izquierdo de



las restricciones tiene valor absoluto mayor o igual a 1.

De esta manera, las condiciones planteadas pueden ser incluidas en el proble-ma de optimización de la forma:

xTi w + γ ≥ +1, para yi = +1,

xTi w + γ ≤ −1, para yi = −1.

Las observaciones para las cuales una de estas restricciones es activa, es de-cir |xT

i w + γ| = 1 tienen especial importancia. En particular, estos puntos yacenexactamente en los llamados hiperplanos canónicos que están definidos por lasecuaciones:

xT w + γ = +1,

xT w + γ = −1.

Se denotará por x+ a una observación cualquiera que esté en el hiperplano ca-nónico de la clase positiva (lado derecho igual a +1) y por x− a un dato cualquieraque este en el hiperplano canónico de la clase negativa. El hiperplano definidopor el par (w, γ) es paralelo al hiperplano canónico. Ahora, con esta notación, elmargen de separación del hiperplano definido por el par (w, γ) y denotado por γ,puede ser expresado como:

γ =12

[(xT

+w‖w‖

)−

(xT−w‖w‖

)]

Así,

γ =1

2‖w‖(xT

+w − xT−w)

Luego, como x+, x− están sobre los hiperplanos canónicos entonces xT+w −



xT−w = 2. Así, podemos concluir que

γ =1‖w‖

.

Se tiene entonces que la distancia entre el hiperplano definido por el par (w, γ)a cada uno de los hiperplanos canónicos es igual a 1/‖w‖. Además, los puntos máscercanos a este hiperplano en el conjunto de entrenamiento están en los hiperpla-nos canónicos. Por lo tanto, el margen de separación de este hiperplano es igual a2/‖w‖.

Se desea entonces maximizar este margen y esto es equivalente a minimizar lanorma euclidiana de w. De esta manera el problema de optimización que vamos aresolver es el siguiente:

mınw,b

‖w‖2

2(2.1.1)

sujeto a yi(xTi w + γ) − 1 ≥ 0 i = 1, . . . ,m

Resolviendo este problema se obtiene un vector óptimo w∗ que permite calcu-lar el margen geométrico máximo de un hiperplano de separación, γ∗ = 2/‖w‖.

Como el problema anterior es un problema cuadrático convexo y el problematiene una única solución óptima global, podemos obtener la solución encontrandolas condiciones de optimalidad de primer orden, conocidas como las condicionesKarush, Kuhn, Tucker (ver [10]). Para esto hacemos uso del Lagrangiano:

LP =‖w‖2

2−

m∑i=1

αi(yi(xTi w + γ) − 1)

=‖w‖2

2−

m∑i=1

αiyi(xTi w + γ) +

m∑i=1

αi

donde los αi son los multiplicadores de Lagrange asociados a las restricciones del



0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 2.1: Caso linealmente separable

problema (2.1.1).

Luego, tomando en cuenta el Lagrangiano podemos plantear las condicionesde optimalidad (KKT):

∂LP

∂w j= w j −

m∑i=1

αiyixji = 0, j = 1, . . . , n, (2.1.2)

∂LP

∂γ= −

m∑i=1

αiyi = 0, (2.1.3)

yi(xTi w + γ) − 1 ≥ 0, i = 1, . . . ,m, (2.1.4)

αi ≥ 0, i = 1, . . . ,m, (2.1.5)

αi(yi(xTi w + γ) − 1) = 0, i = 1, . . . ,m. (2.1.6)



De (2.1.2) y (2.1.3) obtenemos en el óptimo, las siguientes relaciones:

w =

m∑i=1

αiyixi (2.1.7)

m∑i=1

αiyi = 0 (2.1.8)

Luego,

LP =‖w‖2

2−

m∑i=1

αiyi(xTi w + γ) +

m∑i=1

αi

=

m∑i=1

αi +12

m∑i=1

m∑j=1

αiα jyiy j(xTi x j) −

m∑i=1

αiyi(xTi w) por (2.1.7) y (2.1.8)

=

m∑i=1

αi +12

m∑i=1

m∑j=1

αiα jyiy j(xTi x j) −

m∑i=1

m∑j=1

αiα jyiy j(xTi x j) por (2.1.7)

=

m∑i=1

αi −12

m∑i=1

m∑j=1

αiα jyiy j(xTi x j)

A partir de esta expresión, y aplicando dualidad Lagrangiana se puede obtenerel dual de Wolfe de (2.1.1), el cual vendría dado por:

maxα

LD =

m∑i=1

αi −12

m∑i=1

m∑j=1

αiα jyiy j(xTi x j),

s.a.m∑

i=1

αiyi = 0,

αi ≥ 0, i = 1, . . . ,m.

En el caso de problemas de optimización convexos regulares, como el proble-ma (2.1.1), el Dual de Wolfe (2.1.9) es un dual fuerte. La solución se reduce, en-tonces, a obtener los valores óptimos para los multiplicadores de Lagrange αi. Una



vez conocidos éstos, los valores óptimos de las variables primales w se obtienende las ecuaciones (2.1.7) y (2.1.8). Además, definimos la función discriminantecomo:

f (x) = wT x + γ =

m∑i=1

αiyi(xTi x) + γ.

En resumen, para encontrar el par (w∗, b) que define el hiperplano de separa-ción óptimo se resuelve el problema Dual (2.2.1) obteniéndose los multiplicadoresα∗ óptimos.

Ejemplo 2.1.3 Caso Linealmente separable

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-0.2

0

0.2

0.4

0.6

0.8

1

1.2

Figura 2.2: Datos separados con hiperplano óptimo

La construcción del hiperplano óptimo de la figura anterior, y la separaciónde la muestra como tal fue generada por el algoritmo svmlineal.m (ver A.3).



2.2. SVM caso linealmente no separable

Si colocáramos en práctica al algoritmo anterior en un caso en que los datosno son separables, no se llegará a una solución factible ya que no existirá un hiper-plano que cumpla con la condición yi(xT

i w + γ) − 1 ≥ 0. Permitiremos ahora quelos puntos violen las ecuaciones del hiperplano de separación, pero impondremosuna penalidad para la violación.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 2.3: Caso linealmente no separable

Denotemos por ξi la variable no-negativas de holgura , la cual denotará la can-tidad por la cual el punto xi viola la restricción del margen; ahora vamos a requerirlas siguientes condiciones:

yi(xTi w + γ) ≥ 1 − ξi

ξi ≥ 0 ∀i

Ahora, una manera común de imponer la penalidad es añadir a la función ob-



jetivo un costo extra. Es decir, cambiarla de,

mınw,b

‖w‖2

2

a una expresión de la forma,

mınw,b,ξ

‖w‖2

2+ C

m∑i=1

ξi

k

donde C es un parámetro que se puede definir, notemos que si le asignamos a Cun valor muy alto, lo que se esta haciendo es asignar una penalidad grande paralas violaciones de separación.

El problema anterior es convexo para cualquier k entero positivo; y ademáspara k = 2 y k = 1 es un problema de programación cuadrática. La elección dek = 1 tiene una ventaja adicional ya que ni los ξi ni sus multiplicadores de La-grange asociados a estas variables aparecen en el problema Dual de Wolfe, y ladiferencia estaría en que en este caso, para el hiperplano óptimo los αi están aco-tados superiormente por C.

Esto es,

max LD =

m∑i=1

αi −12

m∑i=1

m∑j=1

αiα jyiy j(xTi x j) (2.2.1)

s.a.m∑

i=1

αiyi = 0

0 ≤ αi ≤ C i = 1, . . . ,m



La solución está nuevamente dada por:

w =

Ns∑i=1

αiyixi

donde Ns es el número de vectores de soporte.

Necesitaremos las condiciones Karush-Kuhn-Tucker para el problema primal.El Lagrangiano primal es,

LP =‖w‖2

2+ C

∑i

ξi −∑

i

αi[yi(xTi w + γ) − 1 + ξi] −

∑i

µiξi

Pues los µi representan los multiplicadores de Lagrange asociados a la condiciónξi ≥ 0.

Las condiciones KKT para el problema primal son por lo tanto,

∂LP

∂wv= wv −

∑i

αiyixiv = 0

∂LP

∂γ= −

∑i

αiyi = 0

∂LP

∂ξi= C − αi − µi = 0

yi(xTi w + γ) − 1 + ξi ≥ 0

ξi ≥ 0

αi ≥ 0

µi ≥ 0

αi[yi(xTi w + γ) − 1 + ξi] = 0

µiξi = 0



Ejemplo 2.2.1 Caso linealmente no separable

Al aplicar el algoritmo svmlineal.m a la muestra antes mencionada obtenemosel siguiente resultado:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 2.4: Datos linealmente no separables

2.2.1. Funciónes Núcleo

En 1951 Kuhn y Tucker generalizaron la teoría de Lagrange permitiéndoseentonces la introducción de restricciones de desigualdad en los problemas de op-timización en el que se utiliza el producto del punto, con funciones en el espaciode características que son llamadas Kernels.

La minimización del Riesgo Empírico y la dimensión de Vapnik-Chervonenkis(ver [1]) son fundamentales para lograr la búsqueda de la solución óptima me-diante funciones que en un espacio numérico determinado, logre el hiperplanoseparador. En la representación de estos conjuntos de entrenamiento, los mismospueden estar linealmente separados. De no ser así, se utilizan las funciones Ker-



nels para llevar estas muestras a un plano de mayor dimensión donde puedan serlinealmente separables (ver [3]).

Las funciones núcleo o también llamadas funciones kernel, son funciones ma-temáticas que se emplean en las máquinas de soporte vectorial (SVM, por sussiglas en inglés). Estas funciones son las que permiten convertir lo que sería unproblema de clasificación no lineal en el espacio dimensional original a un pro-blema de clasificación lineal mas sencillo en un espacio dimensional mayor. Esdecir, la transformación de los datos de un espacio de entrada a un espacio demayor dimensión se logra a mediante el uso de una función núcleo (ver [2]).

No cualquier función puede ser una función kernel, ella debe satisfacer la con-dición de Mercer, la cual dice lo siguiente:

Definición 2.2.2 (Condición de Mercer (ver [1])) Para toda función g(x) tal que:∫g(x)2dx

es finita, entonces la función kernel K(x, y) tiene que cumplir que:∫K(x, y)g(x)g(y)dxdy ≥ 0

Ahora, se define formalmente lo que es una función kernel o función núcleo,

Definición 2.2.3 (Función núcleo (ver [1])) Una función núcleo es un productointerno en el espacio de características que tiene su equivalente en el espacio deentrada:

K(x, xt) = 〈φ(x), φ(xT )〉,

donde K es una función simétrica definida positiva y debe cumplir la condiciónde Mercer.



( )

( )

( )

Espacio de entrada Espacio de caracteristicas

φ

φ

( ) φ( ) φ ( ) φ

( ) φ( ) φ ( ) φ( ) φ( ) φ

( ) φ( ) φ

( ) φ( ) φ

( ) φ ( ) φ( ) φ

( ) φ

( ) φ

( ) φ

( ) φ

( ) φ

( ) φ

( ) φ( ) φ

( ) φ

( ) φ

( ) φ( ) φ

( ) φ

( ) φ

( ) φφ

Figura 2.5: Efecto del núcleo

Algunos Tipos de Núcleos



Nombre Expresión Comentario

PolinomialHomogé-

nea

K(xi, x j) = (xTi x j)n

Consiste de elevar a una po-tencia el producto punto usualxT

i x j.

Kernelperceptron K(xi, x j) = ‖xi − x j‖

El Perceptron es un muy impor-tante modelo de aprendizaje re-lacionado con el aprendizaje enredes neuronales. Se ha demos-trado que el trabajo con el kernelPerceptron equivale a construiruna red neuronal con un núme-ro infinito de neuronas.

NúcleoGaussiano K(xi, x j) = exp

(−‖xi − x j‖

2

2σ2

) A partir del kernel Perceptronobtenemos un equivalente delpopular kernel exponencial, ex-presado como árbol de decisio-nes, Perceptron infinitas

SigmoideK(xi, x j) = tanh(xT

i x j − θ)

Consiste del uso de la tangentehiperbólica en conjunto con elparámetro θ.

Ejemplo 2.2.4 Suponga que la data son vectores enR2, y supongamos K(xi, x j) =

〈xi, x j〉2. Entonces es sencillo hallar un espacio H, y un mapeo Φ de R2 a H, tal

que 〈x, y〉2 = 〈Φ(x),Φ(y)〉.

Escojamos H = R3 y Φ(x) =

x2

1√2x1x2

x22



Veamos que 〈x, y〉2 = 〈Φ(x),Φ(y)〉

〈x, y〉2 =

⟨x1

x2

, y1

y2

⟩2

= (x1y1 + x2y2)2

= x21y2

1 + 2x1y1x2y2 + x22y2

2

Por otro lado,

〈Φ(x),Φ(y)〉 =

⟨x2

1√2x1x2

x22

,

y21√

2y1y2

y22

⟩

= x21y2

1 + 2x1y1x2y2 + x22y2

2

∴ 〈x, y〉2 = 〈Φ(x),Φ(y)〉.


3Re-escalamiento no lineal para SVM

El principio de re-escalamiento no lineal (NRP, por sus siglas en inglés: non-linear rescaling principle) consiste en la transformación de la función objetivo y/osus restricciones de un problema de optimización restringida dado en otro proble-ma que es equivalente a la original en el sentido de que sus conjunto óptimo desoluciones coinciden (ver [7]). Una transformación no lineal parametrizada porun parámetro escalar positivo y en base a una función de escalado suave se utilizapara transformar las restricciones. Los métodos basados en NRP consisten de mi-nimizacion secuencial sin restricciones del lagrangiano clásico para el problemaequivalente, seguido por una fórmula explícita actualizar los multiplicadores deLagrange (ver [5]).

Más formalmente, dado un problema general:

mın f (x)s.a. x ∈ Ω

(3.0.1)

donde f : Rn 7→ R es una función convexa y Ω = x ∈ Rn | Ci(x) ≥ 0, i =

1, . . . ,m con Ci : Rn 7→ R funciones cóncavas (i = 1 . . . ,m).

Consideremos funciones ψ : (t0, t1) 7→ R, dos veces continuamente diferen-

40

Re-escalamiento no lineal para SVM 41

ciables tales que:

1. ψ(0) = 0, ψ′(0) = 1,

2. ψ′(t) > 0,

3. ψ′′(t) < 0

donde −∞ < t0 < 0 < t1 < ∞.

De las características de las funciones ψ tenemos que:

Ω = x ∈ Rn | k−1ψ(kCi(x)) ≥ 0, i = 1, . . . ,m,

donde k > 0 es un parámetro de relajación. Por tanto, el problema (3.0.1) esequivalente a

mın f (x)s.a. x ∈ x ∈ Rn | k−1ψ(kCi(x)) ≥ 0, i = 1, . . . ,m

(3.0.2)

Además, la función lagrangiana

LA : Rn+m+1 → R

LA(x, λ; k) = f (x) − k−1m∑

i=1

λiψ(kci(x))

es la principal herramienta en el método de lagrangiano aumentado.

Una de las más importantes aplicaciones del algoritmo proximal, es cuandose aplica al dual de un problema de programación convexa. Rockafellar (ver [8])muestra que la aplicación de un logaritmo proximal al dual de un programa conve-xo es equivalente al método cuadrático aumentada de Lagrange (también llama-dos métodos multiplicadores). Los métodos de Lagrangiano Aumentado tienenmuchas más ventajas que los métodos de penalización.



Recientemente, métodos lagrangianos aumentados no cuadráticos han recibi-do mucha atención, ya que se ha reconocido que en los términos de uso de lapenalidad que no sean de segundo grado en una función Lagrangiano aumentado,pueden afectar la velocidad de convergencia de los métodos iterativos asociadosy en consecuencia, su rendimiento. Por otra parte, mientras que la clásica funciónde Lagrangiano aumentado cuadrático es diferenciable sólo una vez (incluso silos datos del problema poseen mayor diferenciación), los lagrangianos aumenta-dos no cuadráticos a menudo son C2 si los Objetivos / restricciones también sondos veces continuamente diferenciables. Esta es una ventaja importante ya que losmétodos de tipo Newton se pueden aplicar.

3.1. Métodos de barrera

Los métodos de barrera convierten un problema con restricciones en una su-cesión de problemas sin restricciones. La solución óptima de estos problemas caeen el interior de la región factible y converge a la solución del problema con res-tricciones a medida que el parámetro de barrera tiende a cero.

Ejemplo 3.1.1mın f (x)s.a g(x) = 0

(3.1.1)

Donde f (x) = (x1 − 1)2 + (x2 − 2)2 y g(x) = x1 + x2 + 2.

Se puede transformar utilizando una de las funciones de barrera más conoci-das, la función de barrera logarítmica, en el siguiente problema:

B(x, τ) = f (x) − τ ln(g(x)) (3.1.2)

donde τ es un escalar positivo llamado parámetro de barrera.

A medida que x se aproxima a la restricción, g(x) se aproxima a cero y el tér-



mino −τ ln[g(x)] se aproxima a infinito. La minimización fuerza a B a encontrarun mínimo sin restricciones en el interior de la región factible, y su localizacióndependerá del parámetro τ. A medida que τ tiende a cero la solución tiende a serdel problema original.

La Hessiana se hace mal condicionada cuando τ tiende a cero ∇2xB(x(τ), τ),

tiende a infinito.

La idea original detrás del principio de rescalamiento no-lineal y la correspon-diente función de barrera modificada (ver [4]), fue para permitir la ampliación delconjunto factible de las restricciones. Mientras que el MBF teóricamente ofrececomo una extensión, desde el punto de vista computacional esto podría no sersuficiente, ya que para una penalidad suficientemente grande, la barrera logarít-mica desplazada por ejemplo, tiene casi el mismo comportamiento que la barreraclásica.

3.2. Formulación del rescalamiento no-lineal paraSVM

Para un conjunto de puntos de datos etiquetados (ai, yi) ∈ Rm+1, i ∈ I =

1, . . . , n, yi ∈ −1, 1, construir una SVM significa hallar un hiperplano h =

h(ω, b) = x : ωT x − b = 0 tal que los conjuntos I+ = i : (ai, 1) y I− = i :(ai,−1) sean separados con margen máximo.

Para cada i ∈ I+ en el semiespacio "positivo", consideramos la distancia d(ai, h) =

ωT ai−b ≥ 0 desde ai con i ∈ I+ al hiperplano h y para cada i ∈ I− en el semiespacio"negativo", consideraremos la distancia d(ai, h) = −ωT ai + b ≥ 0, i ∈ I−.

Para hallar el hiperplano h, el cual separa los conjuntos I+ de I− con margenmáximo, tenemos el siguiente problema:



∆∗ = max‖ω‖2=1,b∈R

mıni∈I

d(ai, h)

Al asignar ∆ = mıni∈I d(ai, h), podemos reescribir el problema de hallar ∆∗

como:max ∆ (3.2.1)

sujeto a

Ci(x) ≡ Ci(ω, b,∆) = ωT ai − b − ∆ ≥ 0, i ∈ I+ (3.2.2)

Ci(x) ≡ Ci(ω, b,∆) = −ωT ai + b − ∆ ≥ 0, i ∈ I− (3.2.3)

‖ω‖2 = 1 (3.2.4)

donde I+ e I− consisten de los puntos de datos etiquetados respectivamente.

Para describir el método de re-escalamiento no lineal para SVM (NR-SVM,por sus siglas en inglés) para resolver (3.2.1)-(3.2.4), consideramos un problemaequivalente. Para cualesquiera parámetros positivos k > 0, τ > 0 y una transfor-mación ψ ∈ Ψ = ψ : (t0, t1) 7→ R|ψ(0) = 0, ψ′(0) = 1, ψ′(t) > 0, ψ′′(t) < 0, elsiguiente problema:

mın−τ∆ (3.2.5)

sujeto a

k−1ψ(·) = k−1ψ(kCi(x)) ≥ 0, i ∈ I+ (3.2.6)

k−1ψ(·) = k−1ψ(kCi(x)) ≥ 0, i ∈ I− (3.2.7)12‖ω‖2 − 1 = 0 (3.2.8)

es equivalente a (3.2.1)-(3.2.4).



El Lagrangiano

L(·) = L(ω,∆, λ, γ, τ) (3.2.9)

= −τ∆ − k−1∑i∈I+

λiψ(kCi(x)) − k−1∑i∈I−

λiψ(kCi(x)) + γ12

(‖ω‖2 − 1)

para el problema (3.2.5)-(3.2.8) es la herramienta básica. Este lagrangiano es usa-do para describir el algoritmo NR-SVM.

El método NR-SVM consiste en hallar el mínimo del Lagrangiano (3.2.9) pa-ra el problema equivalente en x = (ω,∆, b); lo cual es equivalente a resolver elsistema:

∇ωL(·) = −

∑i∈I+

λiψ′(·)ai +

∑i∈I−

λiψ′(·)ai + γω = 0,

∇∆L(·) = −τ +∑i∈I+

λiψ′(·) +

∑i∈I−

λiψ′(·) = 0,

∇bL(·) =∑i∈I+

λiψ′(·) −

∑i∈I−

λiψ′(·) = 0,

ya que se está trabajando con funciones convexas, diferenciables y por ello lascondiciones necesarias de primer orden pasan a ser también condiciones suficien-tes (ver [10]).

Además, usamos los multiplicadores de Lagrange λ∗ ∈ Rn para seleccionarlos vectores de soporte por eliminación de ai cuando 0 < λi ≤ ε.

Así, fijado un parámetro positivo k y ε > 0, el procedimiento a seguir es:



Algoritmo 2 Algoritmo Re-escalamiento no lineal para SVMDATOS DE ENTRADA: k > 0, ε > 0Resolver el sistema de ecuaciones:

∇ωL(·) = −∑i∈I+

λiψ′(·)ai +

∑i∈I−

λiψ′(·)ai + γω = 0

∇∆L(·) = −τ +∑i∈I+

λiψ′(·) +

∑i∈I−

λiψ′(·) = 0

∇bL(·) =∑i∈I+

λiψ′(·) −

∑i∈I−

λiψ′(·) = 0

Actualizar los multiplicadores de Lagrange con la fórmula:

λi = λiψ′(·), i ∈ I+ ∪ I−

Hallar γ desde ‖ω‖2 = 1 donde

ω = γ−1

∑i∈I+

λiai −∑i∈I−

λiai

Calcular

τ =∑i∈I+

λi +∑i∈I−

λi

Hagaλ := (λiτ

−1, i = 1, . . . , n)

if ‖λ − λ‖ > ε thenhaga (x, λ, γ, τ) := (x, λ, γ, τ) y regrese al paso 1. Sino x∗ = x, λ∗ = λ.

end if


4Pruebas Numéricas

En este capítulo se exponen algunos resultados de la implementación del al-goritmo de re-escalamiento no lineal para SVM, lo aplicaremos a muestras sepa-rables linealmente y también a conjuntos de datos no separables linealmente.

Además, se presentan diversas formas en que pueden estar los puntos en elplano y se varía la penalidad para ver el comportamiento del algoritmo con lamodificación de este parámetro.

Para la resolución del sistema:∇ωL(·) = −

∑i∈I+

λiψ′(·)ai +

∑i∈I−

λiψ′(·)ai + γω = 0,

∇∆L(·) = −τ +∑i∈I+

λiψ′(·) +

∑i∈I−

λiψ′(·) = 0,

∇bL(·) =∑i∈I+

λiψ′(·) −

∑i∈I−

λiψ′(·) = 0,

se empleó un algoritmo tipo BFGS (ver A.9), con búsqueda lineal de Armijo (verA.11).

Es importante destacar que la función de barrera que fue usada en la imple-

47

Pruebas Numéricas 48

mentación del algoritmo NR-SVM, fue la función de barrera logarítmica:

ψ(t) = ln(t + 1).

A continuación mostraremos algunos resultados de la implementación del algorit-mo de re-escalamiento no lineal a diversos datos.

Ejemplo 4.0.1 Caso linealmente separable

Consideremos la data:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.1: Datos 1

penalidad τ ‖ω0‖ maxiter solución tiempo100 -0.0013 1.0000 1000 [0.6374; 0.7705; 7.4017; 0.7817]T 23.106709150 -8.7475e-004 1.0000 1000 [0.6374; 0.7705; 7.3893; 0.7817]T 23.733513500 -2.6421e-004 1.0000 1000 [0.6374; 0.7705; 7.3332; 0.7817]T 23.3741521 NaN NaN 3 [NaN; NaN; NaN; NaN]T 0.521834

Cuadro 4.1: Tabla de Datos 1

La siguiente figura muestra el hiperplano que arroja el programa con una



penalidad de k = 100, y se ve que el hiperplano que arroja el algoritmo NR-SVMcon esta penalidad logra el objetivo de separar los datos:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.2

0.4

0.6

0.8

1

1.2

1.4

Figura 4.2: Datos 1 junto con hiperplano separador

A continuación se muestra la figura con los vectores de soporte (color cyan)para un ε = 1e − 5, se tiene la siguiente selección:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.3: Datos 1 con vectores de soporte

Ejemplo 4.0.2 Caso linealmente separable 2




0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.4: Datos 2

Luego al aplicar el NR-SVM obtenemos:

penalidad τ ‖ω0‖ maxiter solución tiempo50 -0.0026 1.0000 870 [0.6664;−0.7456; 8.9814;−1.4589]T 16.4319045 -0.0030 1.0000 858 [0.6664;−0.7456; 8.7720;−1.4259]T 16.47660210 -0.0088 1.0000 1000 [0.6286;−0.7777; 11.1041; 0.0380]T 11.1141902000 NaN NaN 840 [NaN; NaN; NaN; NaN]T 16.326272


La siguiente figura muestra el hiperplano que arroja el programa con unapenalidad baja para esta muestra de k = 5, y se ve que el hiperplano que arroja elalgoritmo NR-SVM con esta penalidad no logra el objetivo de separar los datos:



0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-5

-4

-3

-2

-1

0

1

2

Figura 4.5: Datos 2 con hiperplano

Ejemplo 4.0.3 Caso no separable


0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.6: Datos 3

Al aplicar el algoritmo de NR-SVM obtenemos:



penalidad τ ‖ω0‖ maxiter solución tiempo0.5 0.0389 0.9994 1000 [−0.8733;−0.4861;−49.3000;−0.7711]T 47.9981660.01 0.2331 1.0005 1000 [−0.7641;−0.6459;−167.6160; 2.5920]T 48.773431 0.0399 1.0003 1000 [−0.8611;−0.5077;−23.9480;−0.7771]T 48.4071742 0.0351 1.0000 1000 [−0.8689;−0.4950;−13.6774;−0.7657]T 48.420339


0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.7: Datos 3 junto con hiperplano

Ejemplo 4.0.4 Variación del parámetro de penalidad

En este ejemplo vemos como el aumento o disminución de la penalidad se vereflejado notoriamente en el hiperplano que arroja el algoritmo de re-escalamientono lineal para SVM.



0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

1.2

Figura 4.8: penalidad k=10

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-3.5

-3

-2.5

-2

-1.5

-1

-0.5

0

0.5x 10

4




0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.2

0.4

0.6

0.8

1

1.2

1.4


Ejemplo 4.0.5 Vectores de soporte

En este ejemplo vemos como ajustando el ε > 0 podemos reducir la selecciónde los vectores de soporte.


0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.11: Datos 4

Para ε = 1e − 3 obtenemos:



0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.12: Vectores de soporte para ε = 1e − 3

Para ε = 1e − 5 obtenemos:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 4.13: Vectores de soporte para ε = 1e − 5


ACódigos en MATLAB

Para estudiar el método de re-escalamiento no lineal para SVM, se realizaronun conjunto de algoritmos desarrollados en MATLAB versión R2011a.

A.1. generadatos.m

La función generadatos permite crear matrices de dos clases de puntos, A1y A2. Los puntos son ingresados a gusto del usuario mediante el uso del cursor.Además, luego esos puntos son graficados en el plano.

1 function [A1,A2]=generadatos(v,c)

2 %v permite el ajuste de los ejes v=[-a b -c d].

3 %c indica el número de la figura.

4 figure(c)

5 axis(v)

6 [x1 y1]=ginput();

7 [x2 y2]=ginput();

8 %plot(x1,y1,’ro’,x2,y2,’b+’);

9 A1=[x1 y1];

56

Códigos en MATLAB 57

10 A2=[x2 y2];

11 plot(A1(:,1),A1(:,2),’o’,’LineWidth’,2,’MarkerEdgeColor’,’...

k’,’MarkerFaceColor’,’r’,’MarkerSize’,18)

12 hold on


k’,’MarkerFaceColor’,’b’,’MarkerSize’,18)

A.2. fsvmestandar1.m

La función fsvmestandar1.m representa la función objetivo de un programade svm estándar. En esta función x=(omega,gamma,y); es decir omega, gamma, yvan implícitamente dentro del vector fila x. En este caso el valor de v=10000.

1 function f = fsvmestandar1(x)

2 m=length(x);

3 t=0;

4 for i=4:m

5 t=t+x(i);

6 end

7 f=((1/2)*(x(1)^2+x(2)^2))+10000*t;

A.3. svmlineal.m

Este algoritmo consigue la solución de manera lineal a un programa que des-cribe una svm estándar. El algoritmo realiza una separación óptima de una muestraen el plano consiguiendo el hiperplano que las separa, hace uso del toolbox de op-timización de MATLAB llamado fmincon, por ende todas los cálculos realizadosdentro del algoritmo son hechos de manera tal, que que el programa que describe



la svm estándar quede en la forma:

mın f (x)

s.a. Ax ≤ b

g(x) ≤ 0 (restriccines no lineales)

1 function [ww,gg,yy,KK]=svmlineal(v,c)

2 %Variables de Entradas:

3 %v permite el ajuste de los ejes v=[-a b -c d].

4 %c indica el número de la figura.

5 figure(c)

6 axis(v)

7 [x1 y1]=ginput(); %en esta parte el algoritmo

8 [x2 y2]=ginput(); %pide ingresar los puntos

9 %plot(x1,y1,’ro’,x2,y2,’b+’);

10 A1=[x1 y1];

11 A2=[x2 y2];

12 %plot(A1(:,1),A1(:,2),’RO’,A2(:,1),A2(:,2),’B+’)


k’,’MarkerFaceColor’,’r’,’MarkerSize’,12)

14 hold on


k’,’MarkerFaceColor’,’b’,’MarkerSize’,12)

16 A=[A1;A2];

17 nn=size(A1);

18 n=nn(1);

19 nn1=size(A2);

20 n1=nn1(1);

21 m=n+n1;

22 d=[ones(n,1);-ones(n1,1)];

23 D=diag(d);

24 m=n+n1;



25 DA=D*A;

26 DE=D*(ones(m,1));

27 I=eye(m,m); %corresponde a la identidad de orden m por m

28 O1=zeros(m,2);

29 O2=zeros(m,1);

30 E=ones(m,1);

31 O2=zeros(m,1);

32 B1=[-DA DE -I];

33 C1=[O1 O2 -I];

34 AA=[B1;C1] %es la matriz asociada a las restricciones de ...

desigualdad en la svm estandar para ser empleada en el ...

toolbox

35 C=[-E;O2]

36 z=3+m;

37 w=ones(1,z);

38 [x,fval,flag,output]=fmincon(’fsvmestandar1’,w,AA,C...

,[],[],[],[],[])

39 ww=[x(1) x(2)];

40 gg=x(3);

41 yy=x(4:z);

42 hold on

43 t=[v(1):v(2)];

44 xx1=(1+gg-ww(1)*t)/ww(2);

45 xx2=(-1+gg-ww(1)*t)/ww(2);

46 xx=(gg-ww(1)*t)/ww(2);

47 %plot(t,xx1,’k’,t,xx2,’k’,t,xx,’b’)

48 plot(t,xx1,’k’,’LineWidth’,3.5)

49 plot(t,xx2,’k’,’LineWidth’,3.5)

50 plot(t,xx,’b’,’LineWidth’,3.5)

51 KK=AA;



A.4. fsvmestandar2.m

La función fsvmestandar2.m representa la función objetivo de un programasvm estándar. Funciona muy bien para longitud del vector fila x mayor que 5. Esuna manera general de programar la función objetivo de la svm estándar.

1 function f = fsvmestandar2(x)

2 m=length(x);

3 u=0;

4 for i=1:m-2

5 u=u+(x(i))^2;

6 end

7 t=0;

8 for i=4:m

9 t=t+x(i);

10 end

11 T=10000*t;

12 f=T+((1/2)*u);

A.5. svm2.m

Este algoritmo intenta realizar una separación óptima de una muestra en elplano de un modelo svm estándar, en el caso en que sw , 1, el algoritmo imple-menta el núcleo Gaussiano:

K(xi, x j) = exp(−‖xi − x j‖

2

2σ2

)

1 function [ww,gg,yy,KK,D,VE]=svm2(A1,A2,sw)

2 % A1, A2 representan los puntos a clasificar



3 % sw es una variable que de tomar el valor 1 trata de ...

separar linealmente los datos

4 % de tomar un valor distinto de uno aplica el núcleo ...

Gaussiano a los datos

5 A=[A1;A2];

6 nn=size(A1);

7 n=nn(1);

8 nn1=size(A2);

9 n1=nn1(1);

10 m=n+n1;

11 if sw==1

12 d=[ones(n,1);-ones(n1,1)];

13 D=diag(d);

14 m=n+n1;

15 DA=D*A;


17 I=-eye(m,m);

18 O1=zeros(m,2);

19 O2=zeros(m,1);

20 E=-ones(m,1);

21 O2=zeros(m,1);

22 B1=[-DA DE I];

23 C1=[O1 O2 I];

24 AA=[B1;C1]

25 C=[E;O2]

26 z=3+m;

27 w=zeros(1,z);

28 [x,fval,flag,output]=fmincon(’fsvmestandar1’,w,AA,C...

,[],[],[],[],[])

29 ww=[x(1) x(2)];

30 gg=x(3);

31 yy=x(4:z);

32 hold on



33 t=[0:0.1:1];

34 xx1=(1+gg-ww(1)*t)/ww(2);

35 xx2=(-1+gg-ww(1)*t)/ww(2);

36 xx=(gg-ww(1)*t)/ww(2);

37 plot(t,xx1,’k’,t,xx2,’k’,t,xx,’b’)

38 KK=AA;

39 else

40 %en este caso ww se refieren a las variables duales u

41 A;

42 K=zeros(m,m);

43 for i=1:m

44 for j=1:m

45 nor=norm(A(i,:)-A(j,:)); %empleo del núcleo

46 K(i,j)=exp((-(nor)^2)/500); %Gaussiano

47 end

48 end

49 K;

50 d=[ones(n,1);-ones(n1,1)];

51 D=diag(d);

52 DKD=-D*K*D;


54 I=-eye(m,m);

55 OO1=zeros(m,m);

56 OO2=zeros(m,1);

57 E=-ones(m,1);

58 O2=zeros(m,1);

59 BB1=[DKD DE I];

60 CC1=[OO1 OO2 I];

61 AAA=[BB1;CC1]

62 CC=[E;O2];

63 z=m+1+m;

64 w=ones(1,z);



65 [x,fval,flag,output]=fmincon(’fsvmestandar2’,w,AAA,CC...

,[],[],[],[],[]);

66 ww=x(1:m);

67 gg=x(m+1);

68 yy=x(m+2:2*m+1)

69 KK=K*D;

70 VE=KK*ww’-gg;

71 size(VE);

72 s=size(VE);

73 eps=0.0001;

74 for i=1:s

75 if (1-eps<=VE(i)& VE(i)<=1+eps) || (-1-eps<=VE(i)& VE(i)...

<=-1+eps); %selección de los vectores de soporte

76 i;

77 A(i,:);

78 hold on

79 plot(A(i,1),A(i,2),’y+’) %indican los vectotes de soporte

80 end

81 end

82 hold on

83 plot(A1(:,1),A1(:,2),’ro’,A2(:,1),A2(:,2),’bo’)

84 end

A.6. LA_SVM.m

En este algoritmo se implementa el método de re-escalamiento no lineal confunción de barrera ψ(t) = ln(1 + t).

1 function [x_est,lambda_est,gamma,tao,maxiter] = LA_SVM(A1,...

A2,x0,lambda0,gamma0,tao0,kk,tol,itmax)

2 %Los parámetros de entrada tol e itmax son para



3 %el newtonmod

4 global B1 B2

5 B1=A1;

6 B2=A2;

7 nn1=size(B1);

8 n1=nn1(1);

9 nn2=size(B2);

10 n2=nn2(1);

11 m=2;

12 n=n1+n2;

13 epss=1e-6; %epsilon

14 lambdas=zeros(n,1);

15 maxiter=1;

16 lambda=lambda0;

17 gamma=gamma0;

18 tao=tao0;

19 while norm(lambda-lambdas)>epss && maxiter<1000

20 delta=x0(m+1);

21 b=x0(m+2);

22 wo=x0(1:m)’;

23 %Hallar xs

24 tol=0.1*tol;

25 [x] = newtonmod(x0,lambda,gamma,tao,kk,tol,itmax);

26 disc=norm(x-x0);

27 x0=x

28 EEE = ENL_SVM(x0,lambda,gamma,tao,kk)

29 %Actualización de los multiplicadores de Lagrange

30 lambda_s=zeros(n1,1);

31 for i=1:n1

32 lambda_s(i)=lambda(i)*(1/(1+(kk*(wo(1)*B1(i,1)+wo...

(2)*B1(i,2)-b-delta))));

33 end

34 ls=lambda_s;



35 lambda_ss=zeros(n2,1);

36 for i=1:n2

37 lambda_ss(i)=lambda(i)*(1/(1+kk*(-1*(wo(1)*B2(i,1)+...

wo(2)*B2(i,2))+b-delta)));

38 end

39 lss=lambda_ss;

40 sumA1=[0;0];

41 sumA2=[0;0];

42 for i=1:n1;

43 sumA1=sumA1+(lambda_s(i)*(B1(i,:))’);

44 end

45 for i=1:n2

46 sumA2=sumA2+(lambda_ss(i)*(B2(i,:))’);

47 end

48 Resta_A1_A2=sumA1-sumA2;

49 wo=wo/norm(wo);

50 gamma_s=norm(Resta_A1_A2)/norm(wo); %w0;

51 %Cálculo de tao

52 sum1=0;

53 sum2=0;

54 for i=1:n1;

55 sum1=sum1+lambda_s(i);

56 end

57 for i=1:n2;

58 sum2=sum2+lambda_ss(i);

59 end

60 tao_s=sum1+sum2;

61 tao_inv=1/tao_s;

62 %Vector de multiplicadores de Lagrange

63 lambdavec=tao_inv*ls;

64 lambda_vec=tao_inv*lss;

65 lambdas=[lambdavec;lambda_vec];

66 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %



67 disc2=norm(lambda-lambdas);

68 aux=lambda;

69 lambda=lambdas;

70 lambdas=aux;

71 gamma=gamma_s;

72 tao=tao_s;

73 maxiter=maxiter+1

74 end

75 x_est=x0;

76 gamma=gamma_s;

77 tao=tao_s;

78 lambda_est=lambda;

79 norm([x_est(1);x_est(2)])

80 t=[0:0.01:1];

81 x1=(x_est(4)-(x_est(2).*t))/x_est(1);

82 hold on

83 plot(t,x1,’-g’,’LineWidth’,3.5)

A.7. ENL_SVM.m

La función ENL_SVM.m describe a la función describe al sistema:∇ωL(·) = −

∑i∈I+

λiψ′(·)ai +

∑i∈I−

λiψ′(·)ai + γω = 0,

∇∆L(·) = −τ +∑i∈I+

λiψ′(·) +

∑i∈I−

λiψ′(·) = 0,

∇bL(·) =∑i∈I+

λiψ′(·) −

∑i∈I−

λiψ′(·) = 0.

1 function ENL_SVM = ENL_SVM(x0,lambda,gamma,tao,kk)

2 global B1 B2

3 %x0 es el punto inicial



4 %lambda es el vector de multiplicadores de Lagrange

5 % kk es el parámetro de penalidad

6 % tao el un número mayor que cero

7 % % % % % % % % % %

8 n1=size(B1);

9 n2=size(B2);

10 m=2;

11 wo=x0(1:m);

12 delta=x0(m+1);

13 b=x0(m+2);

14 sum1=[0;0];

15 sum2=[0;0];

16 for i=1:n1

17 sum1=sum1+lambda(i)*(1/(1+(kk*(wo(1)*B1(i,1)+wo(2)*B1(i...

,2)-b-delta))))*[B1(i,1);B1(i,2)]; %I+

18 end

19 for i=1:n2

20 sum2=sum2+lambda(i)*(1/(1+(kk*(-1*(wo(1)*B2(i,1)+wo(2)*...

B2(i,2))+b-delta))))*[B2(i,1);B2(i,2)]; %I-

21 end

22 grad_lagran_w=-sum1+sum2+(gamma*wo);

23 %cálculo de la segunda y tercera función

24 sum_1=0;

25 sum_2=0;

26 for i=1:n1

27 sum_1=sum_1+lambda(i)*(1/(1+(kk*(wo(1)*B1(i,1)+wo(2)*B1...

(i,2)-b-delta)))); %I+

28 end

29 for i=1:n2

30 sum_2=sum_2+lambda(i)*(1/(1+kk*(-1*(wo(1)*B2(i,1)+wo(2)...

*B2(i,2))+b-delta))); %I-

31 end

32 grad_lagran_delta=-tao+sum_1+sum_2;



33 grad_lagran_b=sum_1-sum_2;

34 %cálculo de z

35 AA=grad_lagran_w;

36 DD=grad_lagran_delta;

37 RR=grad_lagran_b;

38 ENL_SVM=[AA;DD;RR];

39 end

A.8. funk.m

1 function y = funk(x0,lambda,gamma,tao,kk)

23 g=ENL_SVM(x0,lambda,gamma,tao,kk);

4 y=0.5*norm(g)^2;

56 end

A.9. newtonmod.m

Este algoritmo emplea un método de BFGS (Broyden-Fletcher-Goldfard-Shanno).

1 function [x]=newtonmod(x0,lambda,gamma,tao,kk,tol,itmax)

2 n=length(x0); k=1;

3 g=grad(x0,lambda,gamma,tao,kk);

4 B0=eye(n);

5 x(:,k)=x0;

6 d=-g;

7 while norm(g)>tol && k<itmax

8 alpha=armijo(x(:,k),d,lambda,gamma,tao,kk);

9 x(:,k+1)=x(:,k)+alpha*d;



10 g1=grad(x(:,k+1),lambda,gamma,tao,kk);

11 y=g1-g;

12 s=x(:,k+1)-x(:,k);

13 B=bfgs(y,s,B0);

14 d=-B\g1;

15 g=g1;

16 k=k+1;

17 B0=B;

18 end

19 iter=k;

20 x=x(:,k);

A.10. grad.m

Este algoritmo calcula el gradiente de una función.

1 function Dy = grad(x0,lambda,gamma,tao,kk)

2 % Este es el gradiente de la función %

3 n=length(x0);

4 E=eye(n);

5 h=10^(-2);

6 h2=2*h;

7 hh=h/2;

8 for k=1:n

9 f1=funk(x0+h*E(:,k),lambda,gamma,tao,kk);

10 f2=funk(x0-h*E(:,k),lambda,gamma,tao,kk);

11 f12=funk(x0+hh*E(:,k),lambda,gamma,tao,kk);

12 f22=funk(x0-hh*E(:,k),lambda,gamma,tao,kk);

13 Dy(k,1)=(8*f12-8*f22-f1+f2)/(6*h);

14 end



A.11. armijo.m

Este algoritmo realiza el cálculo del tamaño de paso mediante búsqueda deArmijo.

1 function alfk=armijo(x,d,lambda,gamma,tao,kk)

2 %

3 % Chequea la condicion de armijo para

4 % una funcion almacenada en funk.m

5 %

6 s=1;

7 c1=0.001;

8 beta=0.5;

9 k=0;

10 alf=1;

11 dist=ENL_SVM(x+alf*d,lambda,gamma,tao,kk);

12 desc=ENL_SVM(x,lambda,gamma,tao,kk) + c1*alf*grad(x,...

lambda,gamma,tao,kk)’*d;

13 while (dist>desc) %&& (alf>10^(-5)),

14 k=k+1;

15 alf=beta*alf;

16 dist=ENL_SVM(x+alf*d,lambda,gamma,tao,kk);

17 desc=ENL_SVM(x,lambda,gamma,tao,kk)+c1*alf*grad(x,...

lambda,gamma,tao,kk)’*d;

18 end

19 alfk=alf;



A.12. Vecsoport.m

Este algoritmo nos da una opción para seleccionar los vectores de soporteluego de correr el algoritmo de LA_SVM.m; además ajustando el ε > 0 se puedenseleccionar una cantidad mayor o menor de vectores de soporte.

1 A=[A1;A2];

2 t=size(A);

3 for i=1:t;

4 if lambda_est(i)>1e-5 %permite ajustar el epsilon

5 i;

6 A(i,:);

7 hold on

8 plot(A(i,1),A(i,2),’o’,’LineWidth’,2,’...

MarkerEdgeColor’,’c’,’MarkerFaceColor’,’c’,’...

MarkerSize’,18)

9 end

10 end

A.13. corridas.m

Este algoritmo posee cargados algunos datos para el uso posterior del algorit-mo LA_SVM.m.

1 x0=[1/sqrt(2); 1/sqrt(2); 5; 5];

2 tao0=1;

3 kk=10;

4 gamma0=1;

5 v=[0 1 0 1];

6 [A1,A2]=generadatos(v,1);

7 global B1 B2



89 A=[A1;A2];

10 nn=size(A1);

11 n=nn(1);

12 nn1=size(A2);

13 n1=nn1(1);

14 mm=n+n1;

1516 B1=A1

17 B2=A2

1819 lambda0=ones(mm,1)


Bibliografía

[1] C. J. C. Burges. A tutorial on support vector machines for pattern recogni-tion. Data Mining and Knowledge Discovery, 2:121–167, 1998.

[2] O. L. Mangasarian. Generalized support vector machines. In B. SchölkopfA. Smola, P. Bartlett and Schuurmans, editors, Advances in Large MarginClassifiers, pages 135–146. MIT Press, Cambridge, MA, 2000.

[3] O. L. Mangasarian. Data mining via support vector machines. In E. W.Sachs and R. Tichatschke, editors, System Modeling and Optimization XX,pages 91–112. Kluwer Academic Publishers, Boston, 2003.

[4] R. Polyak. Modified barrier functions (theory and methods). Math. Pro-gram., 54:177–222, 1992.

[5] R. Polyak. Nonlinear rescaling vs smoothing technique in convex optimiza-tion. Math. Program. Ser. A, 92:197–235, 2002.

[6] R. Polyak, S.-S. Ho, and I. Griva. Support vector machine via nonlinearrescaling method. Optimization Letters, 1(4):367–378, 2007.

73

BIBLIOGRAFÍA 74

[7] R. Polyak and M. Teboulle. Nonlinear rescaling and proximal-like methodsin convex optimization. Math. Program., 76:265–284, 1997.

[8] R. T. Rockafellar. Convex analysis. Princeton University Press, Princeton,NJ, 1970.

[9] V. N. Vapnik. The nature of Stadistical Learning Theory. Springer, NewYork, 2nd edition, 2000.

[10] S. Wright and J. Nocedal. Numerical optimization. Springer series in opera-tions research and financial engineering. Springer, 2nd edition, 2006.


universidad centroccidental decanato de...

Documents