18 de Febrero de 2005 Universidad Veracruzana, Xalapa, México
Aprendizaje Estadístico, Redes Neuronales y Support Vector Machines: Un enfoque global
Miguel González [email protected]
ITESM CEM: Intelligent Transportation Systems Research Group
Universidad Veracruzana, Xalapa, México 218 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 318 de Febrero de 2005
El problema del aprendizaje
Tipos de aprendizajeAprendizaje supervisado
Se tienen datos empíricos (datos de un proceso, indicadores de mercado, …), xi∈X (Rn), acompañados de su objetivo yi∈Y , i=1, …, , (estados de fabricación, precio de acciones, …) y se quiere encontrar una función f relacionando x con y.
Clasificación y∈{–1,1}
Regresión y∈R
Aprendizaje no supervisado
Se tienen datos xi∈X (Rn) y se busca encontrar regularidades o formas interesantes a partir de estos datos. Estimación de Densidad
Universidad Veracruzana, Xalapa, México 418 de Febrero de 2005
Teoría del aprendizaje estadístico
Error de aprendizajeEs el error medio del conjunto de aprendizaje
conocido como el riesgo empírico.
Error previstoEs el error medio que se puede prever para las nuevas observaciones.
conocido como el riesgo previsto (expected risk).
Principio de minimización del riesgo empírico (ERM)Conexión entre el error de aprendizaje y el error previsto. ¿Que podemos decir de R[f], a partir de Remp[f]? Evidentemente, R[f] es más pequeño (o igual en el caso idílico) que el error de aprendizaje.
∫= ),())(,(][ ydPfyLfR xx
( )( )∑=
= 1
,1
][i
iiemp fyLfR x
≠=
=)( Si 1
)( Si 0))(,(
x
xx
fy
fyfyL
( ) 2)())(,( xx fyfyL −=
Clasificación
Regresión
( )( ) ( )4
2 log1log][][
η−++≤ hemp
hfRfR
Universidad Veracruzana, Xalapa, México 518 de Febrero de 2005
Teoría del aprendizaje estadístico
Principio inductivo de Minimización Estructural del Riesgo (SRM)
Su objetivo es el de minimizar el riesgo empírico y el intervalo de confianza al mismo tiempo, eligiendo el elemento Sk más apropiado y que minimiza el borne:
Error
Sh*–1 Sh* Sh*+1
Borne real del riesgo
Intervalo de confianza Generalización
Complejidad
R[f h*]
h*–1 h* h*+1
Riesgo empírico Error de aprendizaje
es el número de elementos de aprendizaje,h es la dimensión de Vapnik-Chernovenkis, η 0≤η≤1 (1–η probabilidad de validez del borne o frontera)
( )( ) ( )4
2 log1log][][
η−++≤ hemp
hfRfR
Universidad Veracruzana, Xalapa, México 618 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 718 de Febrero de 2005
El perceptron monocapa y el perceptron multicapa
El perceptron monocapa (single layer perceptron, SLP) es el modelo matemático simplificado de una neurona biológica.
Cuerpo de la neurona o soma
Dendrite
Sinápsis
Axona
Synapsis
Núcleo
Axona de otra neurona
Arborización axonal
Entrada PesosSuma y función de
activaciónSalida
( )bf +xwT y
1x
2x
3x
nx
1w
2w
3w
nw
b
• El cerebro está compuesto de millones de neuronas con un nivel de interconexión elevado.• En una red neuronal artificial las neuronas están organizadas en capas y las neuronas de una capa se interconectan a las de la capa siguiente
Capa de entrada
Capas ocultas Capa de salida
1x
2x
3x
nx
y
( )111w
( )121w
( )11rw
( )11nw
( )12nw
( )1rnw
( )112w
( )12rw
( )122w
( )211w
( )221w
( )21tw
( )21tw
( )22rw
( )2trw
( )212w
( )22tw
( )222w
( )311w
( )31tw
( )312w
Universidad Veracruzana, Xalapa, México 818 de Febrero de 2005
Las redes neuronales
Maquinas lineales
El perceptron monocapa considera un conjunto de funciones lineales:
donde f(net) es una función indicador lineal
( )bfy += xwTˆ
( )netnet
netnet
eeee
netf −
−
+−=tanh
-1
1
net
f (ne
t )
Tangente hyperbolique
( )
<−=>
=0 if 1
0 if 0
0 if 1
sgn
net
net
net
netf
-1
1
net
f (ne
t )Signe
Universidad Veracruzana, Xalapa, México 918 de Febrero de 2005
Las redes neuronales
Maquinas no lineales
Objetivo: Obtener fronteras de decisión no lineales utilizando algorítmos lineales, transformando los vectores de entrada x en un espacio de dimensión más importante con ayuda de una función no lineal, elegida a priori.
ejemplos: Polinomial Funciones de base radial Sumas ponderadas no lineales
( ) ,1 avec ,],,[ 11niixx dii d
≤≤=xφ
( ) ( ) ββββ φ czk +== xvx T ( )∏
=
−−=
n
i
iiz
12
2
2
1
2exp
2
β
β
πσβ σβ
vx ( ) ( )ββββ φ cfz +== xvx T
Universidad Veracruzana, Xalapa, México 1018 de Febrero de 2005
Las redes neuronales
Maquinas no lineales
Transformación de técnicas lineales en espacios de características: Los parámetros σβ, cβ, y vβ se eligen a priori. El resto es encontrar los parámetros w y b del clasificador final. Problema: la maldición de la dimensión.
El perceptron multicapa, MLP: En este esquema los coeficientes cβ, y vβ son sumas ponderadas no lineales que deben encontrarse a partir del conjunto de aprendizaje
con
Las redes de funciones a base radial, RBFN: Arquitectura de una sóla capa oculta. Los coeficientes σβ y vβ de las funciones de base radial deben ser encontrados a partir del conjunto de datos de aprendizaje
con
( ) bbbzwyn
+=+=+= ∑=
xwzw φβ
βββ
TT
1
ˆ
( ) ( )βββφ cf += xwx T( ) by += xw φTˆ
( )∏=
−−==
n
i
ii
i z1
2
2
2 2exp
2
1)(
β
β
β
ββ σπσφ
vxx
( )( )
( ) ( )( )ββββ
ββ πφ vxAvx
Ax −−−== −
iini z 1T
21
2/exp
)det(2
1
( )
∑
∑
=
==β
β
ββ
ββφ
n
i
n
c
w
w
y
1
1ˆ
x
Aβ : matriz de varianza covarianza
Universidad Veracruzana, Xalapa, México 1118 de Febrero de 2005
Las redes neuronales
Proceso de aprendizaje
Para encontrar los parámetros w y b, hay que minimizar una cierta función de costo. Una función objetivo general es:
yi es la salids deseada (objetivo) para la entrada xi (iésima observación) es el número de vectores de aprendizaje,ϑ es la función de pérdida, yλ y c2 son parámetros del término de penalización (regularización).
El método del gradiente (conocido con el nombre de regla delta para el perceptron y backpropagation para el perceptron multicapas) es el método más utilizado.
( )( ) ( ) 22T
1
1cλfyJ
iii −+−= ∑
=
wwx
ϑ( )( ) ( )
42 log1log
][][η−++≤ h
emp
hfRfR
-3 -2 -1 0 1 2 3
0
0.5
1
1.5
2
2.5
3fonction de pertedensite
-3 -2 -1 0 1 2 3
0
0.5
1
1.5
2
2.5
3fonction de pertedensite
-3 -2 -1 0 1 2 3
0
0.5
1
1.5
2
2.5
3fonction de pertedensite
-3 -2 -1 0 1 2 3
0
0.5
1
1.5
2
2.5
3fonction de pertedensite
ε–insensible
de Huber
Laplaciana
Gausiana o cuadrática
Modelo de densidadFunción de pérdida
221)( ξξϑ = ( )22
12
exp)( ξπ
ξ −=p
ξξϑ =)( ( )ξξ −= exp)( 21p
<
=contrario lo de
si )(
221
ξ
σξξξϑ σ ( )
( )
−
<−∝
contrario lo de exp
si exp)(
2
2
2
ξ
σξξ
σ
ξ
p
εξξϑ =)( ( )
εε ξξ −= + exp)( )1(21p
www
∂∂
−=+)(
)()1(k
kk
Jη
b
Jbb k
kk ∂∂
−=+ η)()1(
Universidad Veracruzana, Xalapa, México 1218 de Febrero de 2005
Las redes neuronales
Ejemplo:
Encontrar una frontera de decisón que separe parating el espacio en dos regiones.
Problema de optimizaciónCriterio: Error calculado en los datos (Error empírico).Espacio de búsqueda: conjunto de funciones paramétricas, por ejemplo. Problema mal condicionado (solución no única). ¿Garantías?
Universidad Veracruzana, Xalapa, México 1318 de Febrero de 2005
Las redes neuronales
Bajo-aprendizaje y sobre-aprendizaje
Si los datos son generados por un modelo cuadrático:
El modelo lineal corresponde a una situación de bajo-aprendizaje.
El modelo de alto grado corresponde a una situación de sobre-aprendizaje.
Necesidad de encontrar un compromiso entre la adecuación de los datos y la complejidad que sea capaz de generalizar.
Universidad Veracruzana, Xalapa, México 1418 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 1518 de Febrero de 2005
Las máquinas a soporte vectorial
Las máquinas a soporte vectorial (support vector machines, SVM) son máquinas, de base lineal y a solución única, fundadas teoría del aprendizaje estadístico.
Principio general
Construcción de un clasificador en números reales
Descomposición del problema en varios sub-problemas1. Construcción de un separador lineal óptimo
2. Transformación no lineal del espacio de entrada
Universidad Veracruzana, Xalapa, México 1618 de Febrero de 2005
Las máquinas a soporte vectorial
Caso lineal
La idea de base: el margen óptimo
Función de decisión: f(x) = wTx+b
Definición del hiperplano (frontera de decisión): wTx+b = 0
Distancia de un punto al hiperplano:
Entonces, maximizar el margen es equivalente a minimizar ||w||.
w
xwx
bd
+=
T
)(
Universidad Veracruzana, Xalapa, México 1718 de Febrero de 2005
Las máquinas a soporte vectorial
Caso lineal
Problema primalUn punto xi será bien clasificado si y solo si: yif(xi)>0
pero como el par w, b está asociado a un coeficiente de multiplicación, se impone: yif(xi)≥1
Así tenemos un problema de optimización cuadrático QP:
Problema dualUtilización de los multiplicadores de Lagrange para cada restricción
Problema de dimensión (número de ejemplos). Matriz Hessiana: ijji )( Txx
( )( )
, ,1 ,0
,1 :a Sujeto
21
,,
Minimizar
T
1
T
=≥−≥+
+ ∑
=
i
by
Cb
i
iii
ii
ξξ
ξ
xw
wwξw
, ,1 C0
,0 :a Sujeto
)(2
1)(
Maximizar
1i
1,
T
1
=≤≤
=
−=
∑
∑∑
=
==
i
y
yyL
i
ii
jijijiji
iiD
α
α
ααα xxαα
Universidad Veracruzana, Xalapa, México 1818 de Febrero de 2005
Las máquinas a soporte vectorial
Caso lineal
Propiedades
Sólo los multiplicadores αi asociados a los puntos más cercanos al hiperplano son diferentes de cero. Estos puntos forman el conjunto de los Vectores de Soporte.
Función de decisión:
∑=
=1
**
iiiy
ixw α
byfi
iii += ∑=1
T*)( xxx α
∑=
=nsv
iiii y
1
* xw α
bf += xwx T)(
Universidad Veracruzana, Xalapa, México 1918 de Febrero de 2005
Las máquinas a soporte vectorial
Caso no lineal
Proyección del espacio de entrada a un espacio de Hilbert de dimensión más importante a través de funciones kernel o núcleo:
Ejemplo:
Sea x = [x1 x2]T y
en el espacio resultante, el producto vectorial es:
),()()()()()( 211
212
T
12T
1 xxxzxzzzxx kar
rrr ⇔== ∑∞
=
φφ
)2()( 2221
21 ,xxx,x=xφ
( )( )2T
22211
22
222121
21
21
T
'
2)'()(
xx
xx
=
+=
++=
x'x'xx
x'xx''xxxx'xφφ
z2
z1
z3x2
x1 Por lo tanto, se puede calcular φ(x)Tφ(x’) sin
calcular φ.
Universidad Veracruzana, Xalapa, México 2018 de Febrero de 2005
Las máquinas a soporte vectorial
Caso no lineal
Las funciones kernel más utilizadas son:
Tomando el kernel, el problema de optimización final es:
, ,1 C0
,0 :a Sujeto
),(2
1)(
Maximizar
1i
1,1
=≤≤
=
−=
∑
∑∑
=
==
i
y
kyyL
i
ii
jijijiji
iiD
α
α
ααα xxαα
22
T121 )1)((),( += xxxxk ( )
−−=
2
2
2121
2exp),(
σxx
xxk ( )δκ += )(tanh),( 2T121 xxxxk
Universidad Veracruzana, Xalapa, México 2118 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 2218 de Febrero de 2005
El mecanismo de aprendizaje de las SVM
La fase de aprendizaje de las SVM necesita resolver el problema QP:
con: (Q)ij = yiyj k(xi,xj), i,j=1, …, ,
α = [α1,…, α]T
1 = [11,…, 1]T
y = [y1,…, y]T
C = [C1,…, C]T
Condiciones de optimalidad (Karush-Kuhn-Tucker, KKT):
Cα0
αy
α1Qαααα
≤≤=
−=
,0 : a Sujeto
2
1)(
Minimizar
T
TTq
0T =αy , 0α ≥ and 0αC ≥− (primal feasibility)
0χβy1Qα =+−+− γ , 0β ≥ and 0χ ≥ (dual feasibility)
0T =αβ and 0)(T =− Cαχ (complementary conditions)
Universidad Veracruzana, Xalapa, México 2318 de Febrero de 2005
Los principales métodos de optimización para resolver los QP son:
Métodos de conjunto activo Métodos Primales Métodos Duales
Métodos de punto interior, que buscan aprovechas las condiciones complementarias guardando la realizabilidad primal y dual al mismo tiempo
El mecanismo de aprendizaje de las SVM
Universidad Veracruzana, Xalapa, México 2418 de Febrero de 2005
El mecanismo de aprendizaje de las SVM
Características:
Convergencia a un sistema globalmente óptimo. Incluye la capacidad del control del nivel de complejidad. Construcción basada en un problema de optimización cuadrática.
Inconvenientes:
Problemas de consumo informático para los problemas de gran escala
Talla de memoria : La matriz Hessiana requiere un espacio de memoria igual a ℓ2.
Tiempo de cálculo : de crecimiento exponencial ℓ2.
Para un problema real de 10,000 ejemplos, es necesario:
una memoria de 800MB, sólo para guardar la matriz Hessiana
varios días de cálculo
ijji )( Txx
Universidad Veracruzana, Xalapa, México 2518 de Febrero de 2005
Descomposición del problema de optimización cuadrático SVM
8. Elección de un conjunto activo inicial A de talla nA.
9. Resolver el QP definido por el conjunto activo A.
10. Mientras que exista j∈N sin satisfacer yjg(xj)>1, con
Desplazar los nA vectores xj más erróneos al conjunto activo A,
Desplazar todos los vectores xi con αi=0, i∈A, al conjunto N, y regresar al paso 2
≤
≤
=
−
=
N
A
N
A
N
A
N
A
N
A
N
A
N
A
N
A
NNNA
ANAA
N
ANA
NA
q
C
C
α
α
0
0
α
α
y
y
α
α
1
1
α
α
α
ααα
αα
,0 :nesrestriccio las Bajo
2
1),(
,
Minimizar
T
TT
AAA
AA
AAAAAA
q
Cα0
αy
α1αQααα
≤≤=
−=
,0 :nesrestriccio las Bajo
21
)( Minimizar
T
TT
bkygj
ijjji += ∑=1
),()( xxx α
El mecanismo de aprendizaje de las SVM
Universidad Veracruzana, Xalapa, México 2618 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 2718 de Febrero de 2005
Aplicaciones
Predicción en la bolsa de valores
Dos principales etapas: Predicción de cada índice bursatil o acción
Optimización del portafolio de acciones
Universidad Veracruzana, Xalapa, México 2818 de Febrero de 2005
Modelos SVM–difusos
Comparado a las técnicas: Fuzzy C-means, FCM
Gustafson-Kessel, GK
Fuzzy C-Means Fuzzy Gustafson-Kessel Fuzzy SVM
Aplicaciones
Universidad Veracruzana, Xalapa, México 2918 de Febrero de 2005
0
0.5
1
Bio
mas
s co
ncen
trat
ion
OriginalFuzzy-FCMFuzzy-GKFuzzy-SVM
0
0.5
1
Xen
obio
tic
subs
trat
e
OriginalFuzzy-FCMFuzzy-GKFuzzy-SVM
100 200 300 400 500 600 700 800 900 10000
0.2
0.4
0.6
Time (sec)
Ene
rget
ic s
ubst
rate Original
Fuzzy-FCMFuzzy-GKFuzzy-SVM
0
0.5
1
Bio
mas
s co
ncen
trat
ion
OriginalFuzzy-FCMFuzzy-GKFuzzy-SVM
0
0.5
1
Xen
obio
tic
subs
trat
e
OriginalFuzzy-FCMFuzzy-GKFuzzy-SVM
100 200 300 400 500 600 700 800 900 10000
0.2
0.4
0.6
Time (sec)
Ene
rget
ic s
ubst
rate Original
Fuzzy-FCMFuzzy-GKFuzzy-SVM
Aplicaciones
Comparación de la precisión de la predicción de los modelos FCM-TS, GK-TS et SVM-TS (VAF).
99.7848 %72.5222 %97.5849 %Substrato energético
99.5593 %98.4731 %98.4601 %Substrato xenobiótico
98.9975 %96.8809 %96.0185 %Concentración de biomasa
Validación
99.8391 %94.5855 %96.9935 %Substrato energético
99.7201 %99.1278 %98.2171 %Substrato xenobiótico
99.7626 %99.0082 %98.5309 %Concentración de biomasa
Identificación
Modelo difuso SVM-TSModelo difuso GK-TSModelo difuso FCM-TS
Identificación de modelos TS para sistemas MIMO
Universidad Veracruzana, Xalapa, México 3018 de Febrero de 2005
Los sistemas de transporte inteligentes, ITS
La seguridad vial es un tema prioritario. Cambia el paradigma de la ayuda a la supervivencia de los ocupantes,
durante un accidente, a la asistencia al conductor.
Productos de Información Productos de diagnóstico/pronóstico
Aplicaciones
Universidad Veracruzana, Xalapa, México 3118 de Febrero de 2005
Los sistemas de asistencia al manejo
Seguridad Pasiva
Seguridad Activa
Manejo Normal
Sistemas de alerta
Sistemas de
asistencia
Sistemas de
seguridad automático
s
Sistemas de seguridad para minimizar el impacto
Sistemas de seguridad Soft Level
Sistemas de seguridad Hard Level Sistemas
de seguridad post crash
1. 2.
3. 4.
5.
6.
7.Probabilidad de Crash
Seguridad básica del vehículo
Evitar la cilisión
Protección de los pasajeros
Socorro
Eje
mp
los
AD
AS
N
ive
l de
cri
tici
dad
de
las
situ
acio
ne
s
Crash
Fase de precrash
Sistemas de emergenciaCruz Roja
Estimación de la severidad del accidente por el nivel de ignición y
de la tensión de los cinturones de seguridad
Airbag peatones
Sistema de frenado de urgencia, evitar la collision
Asistencia en el
frenado
Alerta de salida de la
vía
ACCStop & Go
Etc…
Aplicaciones
Universidad Veracruzana, Xalapa, México 3218 de Febrero de 2005
Contenido
I. La teoría del aprendizaje estadístico
II. El enfoque neuronal
III. Las máquinas a soporte vectorial, SVM
IV. El mecanismo de aprendizaje de las SVM
V. Aplicaciones
VI. Conclusiones
Universidad Veracruzana, Xalapa, México 3318 de Febrero de 2005
Conclusiones
Los algoritmos de aprendizaje son, en su base, algoritmos de optimización.
No hay algoritmos que puedan resolver todo. La estrategia de solución de un problema depende de las restricciones impuestas (tiempo de cálculo, requerimientos informáticos, calidad de la solución, etc.)
En general, la metodología de las SVM brinda buenos resultados, pero el principal problema reside en los requerimientos para el cálculo.
18 de Febrero de 2005 Universidad Veracruzana, Xalapa, México
¿Preguntas?¿Preguntas?
Aprendizaje Estadístico, Redes Neuronales y Support Vector Machines: Un enfoque
global
Miguel González [email protected]
ITESM CEM: Intelligent Transportation Systems Research Group