aprendizaje estadístico, redes neuronales y support … · iii. las máquinas a soporte vectorial,...

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


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


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


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


Contenido





V. Aplicaciones

VI. Conclusiones


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


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



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



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



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


-3 -2 -1 0 1 2 3

0

0.5

1

1.5

2

2.5


-3 -2 -1 0 1 2 3

0

0.5

1

1.5

2

2.5


ε–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(



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?



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.


Contenido





V. Aplicaciones

VI. Conclusiones


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



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

)(



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αα



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)(



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 φ.



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


Contenido





V. Aplicaciones

VI. Conclusiones


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)


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




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


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

α

α

QQ

QQ

α

ααα

αα

,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 α



Contenido





V. Aplicaciones

VI. Conclusiones


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


Modelos SVM–difusos

Comparado a las técnicas: Fuzzy C-means, FCM

Gustafson-Kessel, GK

Fuzzy C-Means Fuzzy Gustafson-Kessel Fuzzy SVM

Aplicaciones


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


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


0

0.5

1

Xen

obio

tic

subs

trat

e


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


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


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


Contenido





V. Aplicaciones

VI. Conclusiones


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

aprendizaje estadístico, redes neuronales y support … · iii. las máquinas a soporte vectorial,...

Documents