detección multiusuario para ds-cdma basado en svm...

Detección Multiusuario para DS-CDMA basado en SVM Support Vector Machines..

Página 59 de 162

7 Support Vector Machines. SVM.

El inicio de la teoría en la que se basan las máquinas de vectores soporte data de

los años setenta con los trabajos de Vapnik. En los años noventa el método fue

generalizado y en la actualidad presenta un gran interés. Esta teoría fue discutida en la

sección anterior.

Las Máquinas de Vectores Soporte son nuevas estructuras de aprendizaje basadas

en la teoría estadística del aprendizaje. Se basan en transformar el espacio de entrada en

otro de dimensión superior (infinita) en el que el problema puede ser resuelto mediante

un hiperplano óptimo (de máximo margen).

La formulación de las máquinas de vectores se basa en el principio de

minimización estructural del riesgo que ha demostrado ser superior al principio de

minimización del riesgo empírico. Las maquinas de vectores soporte presentan un buen

rendimiento al generalizar en problemas de clasificación, pese a no incorporar

conocimiento específico sobre el dominio. La solución no depende de la estructura del

planteamiento del problema.

La idea es construir una función clasificadora que:

• Minimice el error en la separación de los objetos dados. Error en

clasificación.

• Maximice el margen de separación (mejora la generalización del

clasificador)


Página 60 de 162

7.1 Un ejemplo introductorio

Suponemos que tenemos los datos empíricos:

(x1,y1).................(xm, ym) ∈ χ x ±1 (7.1)

Aquí el dominio χχχχ es un sistema no vacío, donde los modelos xi son los que se

toman y los yi son los denominados flancos o etiquetas. A menos que se diga lo

contrario, los subíndices i y j, se entenderán de la forma i,j=1,...............,m.

Para estudiar el problema de un aprendizaje necesitamos una estructura

condicional [4]. En el aprendizaje nosotros queremos ser capaces de generalizar para los

datos no vistos. En el reconocimiento del modelo, tendremos una x ∈∈∈∈ χχχχ y querenos

predecir y ∈∈∈∈ ±±±±1. Para esto utilizaremos una medida de semejanza o de similitud en χχχχ

y en ±±±±1. Esto último es fácil , cuando se designan dos valores, pues estos sólo pueden

ser iguales o diferentes. Para realizar ésto, utilizaremos la siguiente medida de similitud:

ℜ→×Κ χχ: (7.2)

)',()',( xxxx κ→

Es decir debemos de encontrar una función que dados dos valores xx, ’,

devuelva un valor real que caracterice su similitud, por razones que se aclararán más

tarde, esta función de llama función de Kernel. ( [8][[9][10])

Un tipo de medida de similitud de una apelación matemática es el producto de

puntos. Por ejemplo dados dos valores xx, ’ ∈∈∈∈ ℜℜℜℜN el producto de puntos canónico están

compuestos de la forma:

)').(()',(1

i

N

i

i xxxx ∑=

= (7.3)

donde ix es la entrada i-ésima del vector.

La interpretación geométrica de este producto es estimada como el coseno del

ángulo entre los vectores x y x ’, normalizados para longitud uno. Es más, ésto nos

permite realizar el cálculo de la longitud de x como ).( xx , y la distancia de los dos

vectores como la diferencia de las longitudes de cada uno de ellos. Por consiguiente si

somos capaces de estimar los productos de puntos, podemos llevar a cabo toda la

construcción en términos geométricos y ser capaces de formularlo en función de

cosenos, longitudes y distancias.


Página 61 de 162

En el orden que seamos capaces de usar el producto de puntos como una medida

de semejanza, necesitaremos transformar nuestro espacio al espacio ℑℑℑℑ, el cual no tiene

por qué ser idéntico a ℜℜℜℜN. Nosotros realizaremos un mapeado de un espacio a otro.

ℑ→Φ χ: (7.4)

xx →

Este espacio es llamado espacio característico. Existen tres beneficios para

transformar los datos a ℑℑℑℑ:

• Nos permite definir una medida de similitud del producto de puntos en ℑℑℑℑ:

))'().(()'.()',( xxxxxxK φφ== (7.5)

• Nos permite el trato con los modelos geométricos y así nos permite

estudiar el algoritmo de aprendizaje usando álgebra lineal y álgebra

analística.

• La libertad de elegir una cartografía ΦΦΦΦ, nos permite elegir una gran

variedad de algoritmos de aprendizaje. Por ejemplo considerar una

situación donde las entradas viven alrededor de un espacio de producto de

puntos. En este caso podríamos elegir directamente una medida de

semejanza como el producto de los puntos. Sin embargo, podríamos elegir

una primera aplicación a un plano no lineal ΦΦΦΦ y cambiar a una

representación más conveniente para un problema dado y algoritmo de

aprendizaje.

Ahora nos encontramos en la posición de describir un algoritmo de aprendizaje

para el reconocimiento del modelo lo más simple posible. La idea básica es estimar las

medias de dos clases de espacios característicos:

∑+=

=11

1

1

1

y

ixm

c (7.6)

∑−=

=12

2

1

1

y

ixm

c (7.7)

Donde m1 y m2, son el número de ejemplos con etiquetas positivas y negativas

respectivamente. Entonces asignaremos a un nuevo punto de entrada x la clase que se

encuentre más cercana. Esta construcción geométrica puede ser proyectada en términos

de puntos. A medio camino entre c1 y c2 se encuentra el punto 2

21 ccc

+= . La

clasificación del nuevo vector x se obtendrá verificando sí el vector que una c con x

forma un ángulo más pequeño que π⁄2 con el vector w = c1-c2 . (figura 7.1)


Página 62 de 162

Figura 7.1: Clasificación geométrica del modelo

En otras palabras:

)).().sgn(()).(2/)(sgn(()).sgn(( 212121 bcxcxccccxwcxy +−=−+−=−= (7.8)

definiendo el offset como )||||||(||2

1 2

1

2

2 ccb −= (7.9)

Se demostrará de forma constructiva que se puede rescribir esta expresión en

términos de x i en el dominio de entrada χχχχ. De esta manera lo que tenemos es una

medida de similitud en el espacio Κ (7.2). Por consiguiente debemos de rescribirlo todo

en términos de Kernel, evaluándolo sobre los modelos de entrada. Para terminar

realizaremos las sustituciones de (7.6) y (7.7) en (7.8) y (7.9) llegando a la siguiente

función de decisión [11]:

)).(1

).(1

sgn(

)).(1

).(1

sgn(

1211

1211

bxxKm

xxKm

bxxm

xxm

y

ii

ii

y

i

y

i

y

i

y

i

+−=

+−=

∑∑

∑∑

−=+=

−=+= (7.10)

De manera similar a la anterior definimos el offset como

).(1

).(1

(2

1

12

112

2

∑∑+==−==

−=jiji yy

ij

yy

ij xxm

xxm

b (7.11)

Tomemos un caso particular muy típico de este tipo de clasificadores.

Asumimos que la media de las clases tienen la misma distancia al origen (b=0) y que K

podría verse como una densidad, es decir positiva y de integral la unidad.

1)',( =∫ dxxxKχ

∀ x ∈χ (7.12)


Página 63 de 162

Para realizar la anterior suposición, tenemos que requerir que pueda definirse la

integral en todo χχχχ. Suponiendo que esto es verdadero, entonces se corresponderá a lo

denominado decisión límite, separando las dos clases, sujeto a la suposición de que

sean separables desde las dos distribuciones de probabilidad correctamente definidas

por el estimador de dos clases de Parten Windows:

),(1

)(11

1 ∑+=

=iy

ixxKm

xp (7.13)

),(1

)(11

1 ∑+=

=iy

ixxKm

xp (7.14)

Tomando algunos puntos x , obtendremos las etiquetas simplemente cual de las

dos probabilidades es mayor, lo que lleva directamente a (7.10). Esta es la primera

aproximación que podemos hacer si no tenemos información a priori de las

probabilidades de las clases.

La función de decisión (7.10) está muy cercana a los tipos de máquinas de

aprendizaje que nos interesan. Esto es lineal en el espacio característico, mientras que

en el espacio de entrada no, está representado por una expansión de Kernel. Esto es un

ejemplo básico del sentido en el que se centra Kernel sobre los ejemplos de

entrenamiento. El punto principal donde nos encontramos más discusiones es en la

selección de los ejemplos sobre los que se basa el aprendizaje. Y en el paso de éstos a la

función de decisión. Pues no todos los ejemplos de entrenamiento formarán parte de

esta función de decisión.

En la representación del espacio característico, ésto se corresponde con que

estudiaríamos todos los vectores normales a w del hiperplano de separación que pueden

representarse como combinación lineal de los ejemplos de entrenamiento. Por ejemplo,

podríamos querer quitar la influencia de los modelos que están más lejos de la frontera

de decisión, o de aquellos que esperamos que no mejoran la generalización del error de

la función de decisión, de esta manera podríamos reducir el cálculo computacional para

evaluar la función de decisión (7.10) .

El hiperplano sólo dependerá de un subconjunto de ejemplos de entrenamiento,

llamados soporte vectorial.


Página 64 de 162

7.2 Máquinas de vectores soporte lineales.

Comenzamos con máquinas lineales entrenadas con datos linealmente separables

(el caso general y el que finalmente trataremos para la detección CDMA, máquinas no

lineales con datos no separables, se resuelve con un problema de programación

cuadrática muy similar).

Consideremos el conjunto de entrenamiento:

( ){ }Nixzx miii ,...,1,:, =ℜ∈ (7.15)

Supongamos que existe un hiperplano que separa los puntos de ambas clases. Los

puntos x sobre el hiperplano satisfacen wTx + b = 0 donde el vector w es normal al

hiperplano, |b|/||w|| es la distancia perpendicular del hiperplano al origen y ||w|| es la

norma euclídea de w.

Sea d+ (d-) la distancia más corta del hiperplano de separación a la muestra

positiva (negativa, respectivamente) más cercana. Definamos el margen del hiperplano

como la suma d++d-. En el caso linealmente separable, el algoritmo buscará

simplemente el hiperplano con mayor margen. A continuación formularemos esta idea.

Figura7.2: Distintas posibilidades para obtener el margen del hiperplano [12]

Supongamos que todos los datos de entrenamiento satisfacen:

wTxi+b ≥ +1 para zi = +1 (7.16.a)


Página 65 de 162

wTxi+b ≤ -1 para zi = -1 (7.16.b)

esto es zi (wTxi+b) - 1 ≥ 0 i∀ (7.16.c)

Ahora consideramos los puntos para los que se cumple la igualdad en (7.16a) (que

este punto exista es equivalente a elegir una escala adecuada para w y b). Estos puntos

están sobre el hiperplano H1: wTxi + b = 1 con normal w y distancia al origen |1-b|/||w||.

De forma similar, para el hiperplano H2 la distancia al origen es |-1-b|/||w||. Por lo tanto,

d+=d-=1/||w|| y el margen es simplemente 2/||w||. Nótese que H1 y H2 son paralelos

(tienen la misma normal) y que no hay puntos de entrenamiento entre ellos. Podemos,

en definitiva, encontrar el par de hiperplanos que dan el máximo margen minimizando

la función de coste ½ ||w||2 con las restricciones (7.16.c).

Figura 7.3: Ilustración de la idea de hiperplano de separación óptimo para el caso de patrones

linealmente separables. Los vectores soporte(aquellos que yacen sobre H1, H2 y cuya

eliminación cambiaría la solución encontrada) se muestran rodeados por un circulo [13]

Ahora pasaremos a una formulación lagrangiana del problema. Hay dos razones

importantes para hacer esto:

La primera es que las restricciones de la ecuación (7.16.c) se sustituirán por

restricciones sobre multiplicadores de Lagrange, que serán más fáciles de manejar.

La segunda es que con esta reformulación del problema, los datos del

entrenamiento solo aparecen en forma de productos escalares entre vectores. Esta

propiedad es crucial para generalizar el procedimiento al caso no lineal como veremos.

Por lo tanto, introduzcamos N multiplicadores de Lagrange que denotaremos por

α1, α2, ....., αN, uno para cada una de las restricciones de (7.16.c). La regla en

aplicaciones lagrangianas es que para restricciones de la forma ςi ≥ 0 las ecuaciones

que las definen se multiplican por multiplicadores de Lagrange positivos y se restan de


Página 66 de 162

la función objetivo para formar el lagrangiano. En el caso de restricciones de la forma ςi = 0, los multiplicadores de Lagrange no tienen restricciones. Lo anterior da el

lagrangiano

∑∑==

++−=N

i

ii

T

i

N

i

iP bxwzwL11

2

)(2

1αα (7.17)

Ahora debemos minimizar LP con respecto a w, b [14]y a la vez exigir que las

derivadas de LP con respecto a todos los αi se anulen, todo sujeto a las restricciones

αi ≥ 0 (restricciones ς1). Esto quiere decir que podemos resolver de forma equivalente el

siguiente problema dual: maximizar LP sujeto a la restricción de que el gradiente de LP

con respecto a w y b se anule, y sujeto también a la restricción de que αi ≥ 0

(restricciones ς2 ). Esta formulación particular del problema se conoce como dual de

Wolfe y presenta la probabilidad de que el máximo de LP con las restricciones ς2 ocurre

en los mismos valores de w, b y α que el mínimo LP de con las restricciones ς1.

Al requerir que se anule el gradiente de LP con respecto a w y b, obtenemos las

condiciones:

0=∂

∂

w

LP ⇒ ii

N

i

i xzw ∑=

=1

α (7.18.a)

0=∂

∂

b

LP ⇒ 01

=∑=

i

N

i

i zα (7.18.b)

Ya que estas restricciones aparecen igualdades, podemos sustituirlas en la

ecuación (7.13) para obtener

∑∑==

−=N

ji

jijiji

N

i

iD xxzzL1,1 2

1ααα ( 7.19)

La solución se obtiene minimizando LP o maximizando LD y viene dada por la

ecuación (7.18.a). Se trata en definitiva de un problema de programación cuadrática

(QP).

Nótese que hay un multiplicador de Lagrange αi para cada muestra de

entrenamiento. Tras obtener una solución, aquellos puntos para los que αi > 0 se

denominan vectores soporte y yacen sobre los hiperplanos H1, H2. El resto de las


Página 67 de 162

muestras tienen αi = 0 y satisfacen la ecuación (7.16.c). Por ello, el vector w se escribirá

como combinación de los vectores soporte.

Con estas máquinas, los vectores soporte son los elementos críticos del conjunto

entrenamiento: son los más cercanos a la frontera de decisión y si el resto de puntos no

se consideran en un nuevo entrenamiento, el algoritmo encontraría el mismo hiperplano

de separación. Los patrones que conformarán el clasificador son los vectores soporte, el

resto de patrones de entrenamiento son irrelevantes a los efectos de clasificación.

Podemos observar como w está determinado explícitamente por el algoritmo de

entrenamiento, pero no es este el caso del umbral b, aunque su obtención es inmediata:

basta tomar en la ecuación (7.16.c) cualquier i para el que αi ≠ 0 y despejar b (condición

Karush-Kuhn-Tucker); por ejemplo, sí zi = 1 (vector positivo):

b = 1 - wT xi (7.20)

En cualquier caso, siempre es más seguro tomar el valor medio de b que resulta de

todas las ecuaciones.

7.2.1 Fase de validación.

Una vez que hayamos entrenado una máquina de vectores soporte (SVM), para

clasificar un patrón de evaluación x basta determinar en qué parte de la frontera de

decisión se encuentra y asignarle la etiqueta de la clase correspondiente, es decir,

asignamos a x la clase sgn(wT

x + b), donde sgn es la función signo [15]

7.3 SVM con datos no separables.

En el caso no linealmente separable nos interesa poder relajar las restricciones

(7.16), pero únicamente cuando sea necesario, es decir, nos interesa añadir un nuevo

coste a la función objetivo. Es decir, se añadirá una penalización como consecuencia de

los patones mal clasificados. Una posible forma de hacerlo es introduciendo variables

débiles ξi i=1,...,N, en las restricciones para convertirlas en

wTxi+b ≥ +1-ξi para zi = +1 (7.21.a)

wTxi+b ≤ -1+ξi para zi = -1 (7.21.b)


Página 68 de 162

ξi ≥ 0 ∀ i (7.21.c)

esto es zi (wTxi+b) – 1+ξi ≥ 0 i∀ (7.21.d)

El avance consiste en indicar cómo es posible aceptar puntos mal clasificados por

el hiperplano, pero penalizando su error de clasificación a través de una combinación

lineal con la función objetivo. Esta noción de soft margin permite tratar datos más

realistas.

Con esto, para que una muestra quede mal clasificada, el correspondiente ξi debe

ser mayor que la unidad. La suma ∑ ξi es, por tanto, una cota superior en el número

de errores sobre el entrenamiento. Una forma de añadir el coste de los errores a la

función objetivo es intentar minimizar

)(2

1

1

2

∑=

+N

i

iCw ξ (7.22)

donde C es un parámetro ajustable; un valor grande de C equivale a una mayor

penalización de los errores. Así, el primer término hace referencia al inverso del margen

y el segundo término al error de clasificación. Para los patrones que son correctamente

clasificados ξi = 0.

El problema anterior es de nuevo un problema de programación cuadrática

convexa con la agradable propiedad de que ni los ξi ni los multiplicadores de Lagrange

asociados a estos, aparecen en el problema dual de Wolfe, que es ahora maximizar

∑∑==

−=N

ji

jijiji

N

i

iD xxzzL1,1 2

1ααα (7.23)

sujeto a las restricciones

Ci ≤≤ α0 (7.24)

01

=∑=

i

N

i

i zα (7.25)

La solución viene dada nuevamente por

ii

N

i

i szw

S

∑=

=1

α (7.26)


Página 69 de 162

Donde ahora NS es el número de vectores soporte y si es el i-ésimo vector soporte.

De nuevo, la solución óptima puede escribirse como una combinación lineal de vectores

soporte. Por lo tanto, la única diferencia con el caso separable del hiperplano óptimo es

que los valores de αi están ahora acotados superiormente por C. La figura 7.3 ilustra

gráficamente algunas de las ideas anteriores.

Figura 7.4: Las variables débiles ξi permiten relajar la condición de separabilidad para el caso

no linealmente separable.

En cuanto al parámetro C, conforme C�0, la solución converge a la obtenida con

el hiperplano óptimo de datos separables (sobre el problema no separable).

7.4 Máquinas no lineales de vectores soporte.

Mediante una transformación, generalizaremos en este apartado los métodos

anteriores al caso en que la función de decisión no es lineal con los datos.

En primer lugar, observemos que la única forma en que aparecen los datos en las

ecuaciones (7.19) es como productos escalares xi·xj. Supongamos entonces que

llevamos los datos a un nuevo espacio euclídeo H (posiblemente de dimensión infinita),

mediante una transformación Φ (véase la figura 7.4). Transformamos el espacio de

entrada a otro de alta dimensionalidad en el que los datos ahora si son separables

linealmente. De esta forma, podemos aplicar sobre este nuevo espacio el procedimiento

lineal visto en el apartado anterior. Al espacio H se le suele llamar espacio de Hilbert.


Página 70 de 162

Figura 7.5

Esta operación de transformación se realiza de acuerdo con el teorema de Cover

sobre la separabilidad de patrones. Con esto, el algoritmo de entrenamiento solo

dependerá de los datos a través de productos escalares en H, es decir, de funciones de la

forma Φ(xi)·Φ(xj). Si existiera una función núcleo K tal que K(xi,xi) = Φ(xi)·Φ(xj),

podríamos utilizar únicamente K en el algoritmo de entrenamiento sin tener que conocer

explícitamente Φ.

En la mayoría de las ocasiones H es de dimensión infinita y no sería sencillo

trabajar explícitamente con Φ. Sin embargo, si sustituimos xi·xj por K(xi,xi) a lo largo de

todo el algoritmo de entrenamiento, obtendremos una SVM que vive en un espacio de

dimensión infinita y que opera en prácticamente la misma cantidad de tiempo. La

separación sigue siendo lineal, pero en un espacio diferente.

7.4.1 Condición de Mercer

La condición de Mercer [8] permite determinar para qué núcleos existe un par

{H,Φ} con las propiedades descritas anteriormente y para cuales no. Es decir, las

condiciones que deben cumplirse para que el producto escalar en el espacio de salida se

puede escribir a través de un cierto núcleo K(xi,xi) = Φ(xi)·Φ(xj).


Página 71 de 162

Teorema (Condición de Mercer) Existe una transformación Φ y una expansión en

series K(xi,xi) = ∑ Φ(xi)·Φ(xj) si y solo si para cualquier g(x) para la que la integral

∫ g(x)2 dx sea finita, se tiene ∫ K(xy)g(x)g(y)dxdy ≥ 0

7.4.2 Núcleos más utilizados.

Los núcleos más comunes [16] para el reconocimiento y clasificación de patrones

son los siguientes:

PyxyxK )1·(),( += (7.27.a)

)2

exp(),(2

2

σ

yxyxK

−−= (7.27.a)

))·(tanh(),( δγ −= yxyxK (7.27.c)

La ecuación (7.27.a) proporciona un clasificador que es un polinomio de grado p

sobre los datos; la ecuación (7.27.b) da un clasificador basado en funciones de base

radial gausianas y la ecuación (7.27c) es una función de activación sigmoidal neuronal

tipo perceptron (para ciertos valores de δ y γ).

7.4.3 Aplicación de núcleos.

Con la utilización de esta propiedad, el problema se reduce a minimizar

)(2

1

1

2

∑=

+=N

i

iP CwL ξ (7.28)


zi (wT Φ(xi)+b) – 1+ξi ≥ 0 i∀ (7.29)

ξi ≥ 0 i∀ (7.30)

el vector w es combinación de los vectores soporte transformados

)(1

ii

N

i

i szw

S

Φ=∑=

α (7.31)


Página 72 de 162

Para obtener los multiplicadores de Lagrange αi, nuevamente solo es necesario

conocer el núcleo. Podemos aplicar el problema dual maximizando

∑∑==

−=N

ji

jijiji

N

i

iD xxKzzL1,1

),(2

1ααα (7.32)


Ci ≤≤ α0

i∀ (7.33)

01

=∑=

i

N

i

i zα (7.34)

Finalmente la expresión de la SVM adopta la forma

f(x)=sign{ ∑evectsoport

αi zi (Φ(si)·Φ(x)) + b} = sign{ ∑evectsoport

αi zi K(si ,x) + b} (7.35)

Observamos que solo necesitamos conocer el núcleo.

7.5 La dimensión VC de las SVM.

Normalmente llevar los datos a un espacio de características con un elevado

número de dimensiones provoca un bajo rendimiento en la máquina resultante. A fin de

cuentas, los hiperplanos del conjunto{w,b} están parametrizados por dim(H)+1

números. La mayor parte de los sistemas de reconocimiento de muestras ni siquiera

pasaría de la línea de salida con un número tan enorme de parámetros. A mayor

dimensionalidad se requiere mayor número de muestras de entrenamiento, además de

más recursos para llevar a cabo el proceso. ¿Por qué las SVM lo hacen tan bien?

La dimensión VC de una SVM puede ser muy grande (incluso infinita). A pesar de

ello, las SVM suelen generalizar correctamente. Todavía no existe una respuesta

definitiva, pero hay indicios de que el requerir hiperplanos con margen máximo puede

estar jugando un papel importante. Por otro lado, también es importante en la lucha

contra la alta dimensionalidad el hecho de que, gracias a las funciones núcleo y a la

definición del lagrangiano, nos evitamos tener que calcular los parámetros de un

hiperplano óptimo en un espacio de elevada dimensión. Hoy en día, no existe ninguna

teoría que garantice que una determinada familia de SVM se comportarán

correctamente con un problema determinado.


Página 73 de 162

Las SVM basan su funcionamiento en el principio de minimización estructural del

riesgo, del que son una aproximación. Para entender cómo la minimización de ½ ||w||2

es equivalente a la implementación del principio de minimización estructural del riesgo,

supongamos que se cumple ||w|| ≤ A donde la variación de la cota A nos servirá para

definir una estructura anidada de hiperplanos.

Partiendo de la ecuación (7.18), repetida aquí

zi (wTxi+b) ≥ 1 i∀

y como la distancia de un punto x al hiperplano definido por w y b es

w

bxw

xbwd

T

+=);,( (7.36)

tenemos entonces, que

Axbwd

1);,( ≥ (7.37)

Según este resultado, la distancia de cualquiera de los puntos de entrenamiento a

los hiperplanos no puede ser menor que 1/A e, intuitivamente, esto reduce los posibles

hiperplanos y, por tanto, la capacidad. La figura 7.5 ilustra esta idea y el siguiente

teorema la concreta más.

Teorema. La dimensión VC del conjunto de hiperplanos canónicos en un espacio

m dimensional es h ≤ min{R2A

2, m} donde R es el radio de la hiperesfera que

envuelve todos los datos.

Por tanto, la minimización de ||w|| es equivalente a la minimización de una cota

superior de la dimensión VC. La cota de error que resulta ser inversamente

proporcional al margen, y además es independiente de la dimensión del espacio.

Figura 7.6: La minimización de ½ ||w||2 reduce la dimensión VC de la SVM correspondiente.


Página 74 de 162

7.6 Características.

7.6.1 Propiedades destacables.

• El entrenamiento de una SVM es básicamente un problema de programación

cuadrática (QP) convexa, que es atractivo por dos motivos:

o su eficiente computación (existen paquetes software que permiten su

resolución eficientemente)

o Y la garantía de encontrar un extremo global de la superficie de error

(nunca alcanzará mínimos locales). La solución obtenida es única y la

más óptima para los datos de entrenamiento dados.

• A la vez que minimiza el error de clasificación en el entrenamiento, maximiza el

margen para mejorar la generalización del clasificador.

• No tiene el problema de Overfitting (Sobreentrenamiento) como podría ocurrir

en las Redes Neuronales.

• La solución no depende de la estructura del planteamiento del problema.

• Permite trabajar con relaciones no lineales entre los datos (genera funciones no

lineales, mediante kernel). El producto escalar de los vectores transformados se

puede sustituir por el kernel por lo que no es necesario trabajar en el espacio

extendido.

• Generaliza muy bien con pocas muestras de entrenamiento.

7.6.2 Limitaciones.

Pese a los excelentes resultados obtenidos, las SVM tienen algunas limitaciones:

• La elección de un núcleo adecuado es todavía un área abierta de investigación.

Una vez elegido el núcleo, los clasificadores basados en SVM tienen como

único parámetro a ajustar por el usuario: la penalización del error C.

• La complejidad temporal y espacial, tanto en el entrenamiento como en la

evaluación, son también una limitación. Es un problema sin resolver el

entrenamiento con grandes conjuntos de datos (del orden de millones de


Página 75 de 162

vectores soporte). Los algoritmos existentes para resolver esta familia de

problemas tardan un tiempo que depende cuadráticamente del número de puntos.

• Fue inicialmente creado para clasificación binaria. Aunque hay ya algunos

trabajos que estudian el entrenamiento de SVM multiclase en una sola pasada,

aun se está lejos de diseñar un clasificador multiclase óptimo basado en SVM.

• La SVM siempre soluciona un problema bloque: un cambio en los patrones de

entrenamiento supone obtener una nueva SVM pues pueden surgir distintos

vectores soporte (aunque existen ya algunas alternativas para el entrenamiento

on-line de SVM capaces de encajar modificaciones del conjunto de datos sin

necesidad de reentrenar el sistema.).

7.6.3 Multiclasificación.

Cabe señalar que aunque los clasificadores basados en SVM descritos hasta ahora

son todos clasificadores binarios, la combinación de varios de ellos permite manejar el

caso multiclase.

Consideramos en este caso que el conjunto de etiquetas posibles es {θ1,θ2, ...,θk},

siendo k > 2 y sin una relación de orden definida en el etiquetado. Sea Z el conjunto de

entrenamiento definido por Z = { (x1 , y1), ... ,(xn , yn)}, se construyen los subconjuntos

Zk = { (xi , yi), tales que yi = θk } que determinan una partición de Z.

La forma, más habitual, de utilización de las máquinas de vectores soporte para

resolver problemas de multiclasificación admiten dos tipos de arquitectura:

• Máquinas biclasificadoras SV generalizadas: Construyen una función

clasificadora global a partir de un conjunto de funciones clasificadoras

dicotómicas (biclasificadoras). Descomposición-Reconstrucción.

• Máquinas multiclasificadoras SV: Construyen una función clasificadora global

directamente considerando todas las diferentes clases a la vez.

Las máquinas biclasificadoras SV generalizadas dan solución al problema de la

multiclasificación transformando las k particiones del conjunto de entrenamiento en un

conjunto de L biparticiones, en las cuales se construye la función clasificadora (es lo

que se denomina esquema de descomposición) obteniendo f1,..., fL clasificadores

dicotómicos o biclasificadores. A continuación, mediante un esquema de


Página 76 de 162

reconstrucción, realiza la fusión de los biclasificadores fi, i = 1,...,L con objeto de

proporcionar como salida final, una de las k clases posibles, {θ1,θ2, ...,θk}.

Dentro del esquema de descomposición, las máquinas más utilizadas son:

• Máquinas 1-v-r SV (iniciales de one-versus-rest). Máquinas de vectores soporte,

donde cada función clasificadora parcial fi, enfrenta la clase θi contra el resto de

las clases. Se requieren L = k biclasificadores.

• Máquinas 1-v-1 SV (iniciales de one-versus-one). Máquinas de vectores soporte,

donde cada función clasificadora parcial fij , enfrenta la clase θi contra la clase θj,

sin considerar las restantes clases. Se requieren L = k·(k-1)/2 biclasificadores.

Una combinación efectiva para k clases se obtiene entrenando k clasificadores,

dando al clasificador i-ésimo, i=1,...,k, las muestras de la clase i como positivas y las

restantes como negativas. En la etapa de reconstrucción, clasificamos una muestra de

evaluación como perteneciente a aquella clase cuya SVM asociada da la mayor

distancia positiva. Esta distancia puede obtenerse de la ecuación (6.8); y podemos

observar que son valores normalizados, por lo que pueden compararse directamente

entre los distintos biclasificadores.

detección multiusuario para ds-cdma basado en svm...

Documents