1

Sistemas óptimos inteligentes para reconocimiento de patrones y navegación robótica (Máquinas de vector soporte y Redes neuronales)

Dra. Nancy Arana Daniel.Nancy_arana@cucei.udg.mx

Guadalajara, Jalisco, Septiembre 2010.

DIVISIÓN DE ELECTRÓNICA Y COMPUTACIÓNCUCEI

UNIVERSIDAD DE GUADALAJARA

2

Introducción. El problema de aprendizaje artificial se aborda como un

problema de clasificación: Supongan que tenemos fotografías de 50 perros y 50 leones

Las digitalizamos en fotografías de 100 x 100 pixeles y entoncestenemos vectores de entrada x ∈ Rn , donde n=10,000.

Ahora dada una nueva fotografía, lo que queremos es responder lapregunta: ¿es un elefante o un tigre?

Interpretación geométrica del aprendizaje artificial en redes neuronales y SVM

3

mx + b = 0

4

Aprendizaje supervisado.

Conjunto de entrenamiento = { [entrada1, salida-deseada1] ,...,[entradan, salida-deseadan]

Entradai Sistema Salida-deseadai

Support Vector Machines (SVM).

Las Support Vector Machines son sistemas que aprenden gracias a laaplicación de las teorías de Vapnik y Chervonenkis y de la optimización;además del uso de las funciones conocidas como kernel, las cualesmapean los datos de entrada hacia espacios vectoriales de dimensiónmucho más elevada que la dimensión del espacio de entrada.

5

Clasificación binaria .

Donde (w,b) ∈ Rn * w,b son losparámetros que controlan lafunción objetivo. La regla dedecisión está dada por sgn(f(x)).

Consideremos el caso en el que f(x) es una función lineal

• w es el vector normal al hiperplano separador.• |b| / ||w|| distancia perpendiculardel hiperplano al origen.• d- y (d+) son la distancia más cortadel hiperplano separador al patrónde entrada negativo (o positivo) máscercano a él.• γ = d- + d+ es el margen del hiperplano separador.• Los vectores que se encuentren a unadistancia d- o d+ del hiperplanoseparador se denominan vectores desoporte.

6

El problema de optimización se reduce entonces a:

* Note que la función es una función del tipo cuadrático.

Lagrangiano Primal:

7

La tarea es minimizar el Lagrangiano primal con respecto aw,b y maximizar con respecto a los multiplicadores deLagrange. En el punto óptimo tendremos las siguientesecuaciones del conocido punto de silla:

lo que se traduce en

Note que w está contenido en el subespacio expandido por(xi).

8

Problema dual de optimización:

La función de decisión no lineal que resuelve el problema :

9

Resultado declasificación binariausando SVM conkernel identidad(). Los vectoresde soporte de cadaclase aparecencomo círculos deradio mayorrespecto a losdemás.

Caso no lineal…y ahora ¿qué hacemos?

10

Encontrar líneas que los separen?...eso hace una MLP,En SVM se usan kernels!

11

Un kernel es una función K, tal que para todo x,z ∈ n

donde es un mapeo de X hacia algún espacio de características con producto punto.

Uso de kernels.

12

Diferentes características de generalizacióndel aprendizaje resultante

Kernel lineal Kernel gaussiano

Uso de diferente kernel

13

Caso 3D

14

Resultado declasificaciónmulticlase (4clases) usandoSVM con kernelgaussiano. Losvectores desoporte de cadaclase aparecencomo círculos deradio mayor conrespecto a losotros.

15

Support Multivector Machines (SMVM)

Se denominan Support Multivector Machines (SMVM) aaquellos sistemas de aprendizaje que se derivan de las SupportVector Machines y se basan en el concepto de multivector delÁlgebra Geométrica.

x Gp,q,rSMVM

Kernelgeométrico

y

16

Resultado declasificaciónbinaria usandokernelgeométrico

KG1Los vectores desoporte se ilustrancomo cuadradoscon longitud delado es mayor conrespecto a losdemás.

17

Resultado declasificaciónbinaria usandokernelgeométrico

KG1Los vectores desoporte se ilustrancomo cuadradoscon longitud delado es mayor conrespecto a losdemás.

18

Resultado de clasificaciónpara problema multiclaseusando kernel geométrico

KG1Los vectores de soporte seilustran como círculoscuya circunferencia esmayor con respecto a losdemás.

Clase Fondo Vectores Entrenamiento

1 Blanco Naranja

2 Azul Verde

3 Naranja Azul

4 Verde Blanco

19

Resultado declasificaciónusando kernelgeométrico

KG2.Los vectores desoporte se ilustrancomo cuadradoscon longitud delado es mayor conrespecto a losdemás.

20

Resultado declasificaciónusando kernelgeométrico

KG2.Los vectores desoporte se ilustrancomo cuadradoscon longitud delado es mayor conrespecto a losdemás.

21

Resultado de clasificaciónpara problema multiclaseusando kernel geométrico

KG2.Los vectores de soporte seilustran como círculoscuya circunferencia esmayor con respecto a losdemás.

Clase Fondo Vectores Entrenamiento

1 Blanco Naranja

2 Azul Verde

3 Naranja Azul

4 Verde Blanco

22

Resultado declasificaciónusando kernelgeométrico

KG3.

23

Comparación de características de generalización de kernel geométrico KG3 contra gaussiano.

= No. De llaves en un lote, Gramos de metal utilizados parafabricar 50 llaves

Conjunto entrenamiento = 1

, tarifa1 ,...,

24

, tarifa24

Conjunto prueba = 1

, tarifa1 ,...,

12

, tarifa12

24

Resultado de clasificación para el problema de la fábrica de llaves usando kernel gaussiano. Los vectores de soporte se ilustran como círculos de radio mayor con respecto a los demás.

Tarifa(Clasedeseada)

Color de clase (Fondo)

Vectores Entrenamiento

1 Naranja Azul

2 Blanco Naranja

3 Azul Verde

4 Verde Blanco

25

Resultado declasificación para elproblema de la fábricade llaves usando kernelgeométrico KG3. Losvectores de soporte seilustran como círculosde radio mayor conrespecto a los demás.

Tarifa(Clasedeseada)

Color de clase (Fondo)

Vectores Entrenamiento

1 Naranja Azul

2 Blanco Naranja

3 Azul Verde

4 Verde Blanco

26

Support Multivector Machines con entradas codificadas como multivectores.

Conjunto de entrenamiento RBF

ci Centroides de clasei Varianzas de clase

Codificamos esferas“contenedoras” en AGC

ci + ½ (ci2 - i2) e + e0

Donde i = i / 2

SMVMClase deseada

27

Esferas contenedoras de los datos de entrenamiento y algunos puntos difusos para espacio de entrada 3D y Álgebra Conformal G4,1

28

Totalidad de los datos de entrenamiento ilustrados como puntos en el espacio 3D.

Máquinas de Vector Soporte Geométricas (Clifford) para

aprendizaje artificial

29

30

Estado del arte.

SVMX ЄRn+1/-1

CLASIFICACIÓN BINARIA

31

Motivación

SVMX ЄRn

+1/-1

Clifford

SVMЄGn

+1/-1

+1/-1

+1/-1

12

2n

Las Clifford Support Vector Machines son una generalización de lasSVM’s reales y complejas, obtenidas mediante la combinación de losmarcos teóricos de la Teoría del Aprendizaje de Vapnik- Chervonenkisy el Álgebra Geométrica (o de Clifford). La ventaja más remarcable deLas CSVM’s es que se puede realizar multi-clasificación y multi-regresiónhaciendo uso de una máquina CSVM, de manera opuesta a lo que Sucede con las SVM reales.

Aplicaciones Las Máquinas de Vector Soporte (SVM)

son un tipo de sistemas de aprendizaje artificial ampliamente usados en aplicaciones que involucren Comportamiento de inteligente de robots,

tales como reconocimiento de patrones (objetos, caras, cuerpos) y navegación en ambientes dinámicos.

32

33

Aplicaciones CSVM en clasificación

1) Espiral 3D con 5 clases

34

Enfoque No. De clasificadores (problemas cuadráticos)

Variables calculadas por problema cuadrático

Total de variables calculadas

CSVM 1 D*N400

D*N400

Uno contra todos K16

N100

K*N1600

Uno contra uno K(K-1)/2120

2*N/K100

N(K-1)1600

DAGSVM K(K-1)/2120

2*N/K100

N(K-1)1600

Un solo problema de optimización con todas

las clases.

1 K*N1600

K*N1600

Análisis del número de variables calculadas por enfoque, donde K=16, D=4, N=100

K es el número de clases involucradas N es el número de datos de entradaD es la dimensión de datos de entrada

35

Comparación de tiempos de entrenamiento en segundos.Enfoque K=3, N=150

Tiempo entrenamiento

(segundos)

K=5, N=250Tiempo

entrenamiento(segundos)

K=16, N=800Tiempo

entrenamiento(segundos)

CSVM 0.10(450)

2.12(750)

22.83(3200)

Uno contra todos

0.18(450)

10.0(1250)

152.5(12800)

Uno contra uno

0.11(300)

3.42(1000)

42.73(12000)

Pentium IV, , Ram y todo eso. Los tres enfoques se trabajaron con segmentación de la matriz gramm.

36

2) Reconocimiento de objetos

2) Cuaternión de características

1)PreprocesamientoNormalizamos losobjetos para tenerun centro y escalacomún 3)

CSV

M

1

16

4) C

onta

dor

Clase ganadora

37

2.1) Reconocimiento de objetos artificiales.

38

2.1) Resultado de reconocimiento de objetos artificiales.Objeto[Clase]a

N.E.b N.P.c No-Nor.d P.N.N.e

%Nor.f P.Nor.g

%

Cilindro[1,1,1,1]

43 26 21 80.77 20 76.92

Esfera[-1,-1,1,1]

42 33 22 66.67 22 66.67

Fuente[-1,-1,-1,1]

42 33 28 84.85 19 57.57

Gusano[1,-1,1,1]

43 33 22 66.67 18 54.55

Diamante[1,-1,-1,1]

40 29 27 93.10 19 65.52

Cubo[-1,-1,-1,-1]

42 33 29 87.88 23 69.70

b Número de datos de entrenamiento

c Número de datos de prueba

d Número de datos de prueba no-normalizados correctamente clasificados

e % efectividad datos de prueba no-normalizados

f Número de datos de prueba normalizados correctamente clasificados

a Cuaternión de clase [ ]

b % efectividad datos de prueba normalizados

39

2.1.1)Comparación CSVM vs 4-7-6 MLP

Objeto N.E.a N.P.b CSVMc %CSVMd MLPe %MLPf

Cilindro 43 26 21 80.76 20 76.92

Esfera 42 33 22 66.67 12 36.36

Fuente 42 33 28 84.85 13 39.39

Gusano 43 33 22 66.67 17 51.51

Diamante 40 29 27 93.10 15 51.72

Cubo 42 33 29 87.88 12 36.36

a Número de datos de entrenamiento

b Número de datos de prueba

c Número de datos de prueba no-normalizados correctamente clasificados por la CSVM

f % efectividad datos de prueba no-normalizados MLP

d % efectividad datos de prueba no-normalizados CSVM

e Número de datos de prueba no-normalizados correctamente clasificados por la MLP

40

2.2) Reconocimiento de objetos reales.

41

Clasificación multiclase 2D

Efectividad

42

Reconocimiento de Objetos 3D

43

Clasificación de objetos

video

44

2.1) Resultado de reconocimiento de objetos reales

b Número de datos de entrenamiento

c Número de datos de prueba

d Número de datos de prueba no-normalizados correctamente clasificados

e % efectividad datos de prueba no-normalizados a Cuaternión de clase [ ]

Objeto[Clase]a

N.E.b N.P.c N.Correc.d P.Efec..e

%Cubo[1,1,1,1]

90 50 38 76.00

Prisma[-1,-1,1,1]

90 43 32 74.42

Media esfera[-1,-1,-1,1]

90 44 29 65.90

Geoda[1,-1,1,1]

90 75 63 84.00

Botella plástica 1[1,-1,-1,1]

90 65 39 60.00

Botella plástica 2[-1,-1,-1,-1]

90 67 41 61.20

45

Entrada T1(T1, F(T1))

Entrada T2(T2, F(T2))

Salida( F(T1),F(T2) )

3) Regresión (interpolación)

46

Dibujo del robot

400 puntosde prueba

47

Sistema recurrente LSTM-CSVMSupuesto usado por SVM’s para estimar la función de clasificación

o regresión f(x): “Los pares de entrenamiento {xi,yi} son independientemente dibujados e idénticamente distribuídos“

¡Datos correlacionados!

1. Ventanas de tiempo de tamaño fijo (m) para realizar tareas como predicción de series de tiempo. 1,2.

1. Las dependencias temporalesexceden el número m.

2. SVM recurrente de Suykens y Vandewalle.

2. Las ecuaciones son no linealesy el problema no convexo.

2. Sistema Evoke. 3. Los problemas multi-clase aumentan su complejidad en gran medida.

48

Sistema recurrente LSTM-CSVM

Módulo que se encarga de detectar y representar

dependencias temporales:procesa secuencias de tiempo ydetecta correlación entre datos.

CSVM y(t)

Módulo que proporcionael proceso de optimizaciónpara añadir precisión a los

datos de salida

Memoriade Corto y Largo Plazo LSTM

Ψ1

Ψ2

Ψ n

u(t)

u(t-1)

u(0)

Espacio de dimensiónarbitraria de las

secuencias temporales

Espacio dedimensión finita

de las activacionesneuronales

49

Módulo LSTM-

50

Neuroevolución del sistema LSTM-CSVM

Cromosoma

I= núm. entradas externasH= núm. Células de memoria

de la red

w1 w2 w(3*(I+H))

sis1 sis10w1 w2 w(3*(I+H)) w1 w2 w(3*(I+H))

Medida de fortaleza: Menor error de predicción.

51

1. Se presentan todos los datos de entrenamiento a cada sistema y al finalse toma su error de predicción.

2. Se elige a los 4 cromosomas más fuertes, reproduzco 4 mezclando 4de los más fuertes y se mutan los 2 más fuertes con ruido de Cauchy

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

Selección de los más fuertes

1

2

3

4

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

Reproducción

5

6

7

8

w1 w2 w(3*(I+H))

w1 w2 w(3*(I+H))

Mutación

9

10

52

Resultados en predicción de series de tiempo.Laguna de Venecia.

Datos de entrenamiento: 400, datos de prueba: 600.Arquitectura: 4 células de memoria LSTM y módulo CSVMEvolución: 100 generaciones y ruido de Cauchy 10-3Error obtenido: 0.0019

53

54

Navegación robótica en laberintos discretos.Aprendizaje reforzado

AgenteI

A

D

T

10-El agente recibe alguna información del

ambiente.-Información valorativa en lugar de instructiva.-El objetivo es aprender una política basada en la retroalimentación del ambiente (recompensas) -> Maximizar recompensas.

AgenteEstado

Ambientals

Medio A

mbiente

Observación o

Acción a

Recompensa r

s*O=[x,y, I,A,D,T]a {VI, VA, VD, VT}r {-0.1, 4}

55

Navegación robótica en laberintos discretos. Simulaciones

7)

4)

6)

-Se tienen un total de 7 laberintos distintos, 3 de ellos constituyen el conjunto de entrenamiento.

-Los laberintos se dividen en bloques de 10*10 pixeles para muestrearlos. Mínimo 88 muestras máximo 110.

Arquitectura:- 6 unidades de entrada, - 8 unidades intermedias divididas en dos capas:

- 4 Neuronas estándar con función sigmoide.- 4 células de memoria

- Módulo CSVM con 4 salidas posibles.

Entrenamiento:- Enfoque ESP por 100 generaciones con medida de

fortaleza: mayor recompensa.- Ruido de Cauchy 10-4- Módulo CSVM con kernel Gabor.- Criterio de paro para cada generación: Alcanzar salida

en 110 acciones u obtener recompensa de 4.0.

56

ResultadosEn

Simulaciones

1) 2)

3) 4)

5) 6)

7)

57

Navegación robótica en laberintos discretos. Sistema de percepción y acción

58

Navegación robótica en laberintos discretos. Sistema de percepción y acción

-Se tienen un total de 4 laberintos distintos, 2 de ellos constituyen el conjunto de entrenamiento.

-Los laberintos se dividen en bloques de 5*5 pixeles para muestrearlos. Máximo 42 muestras.

Arquitectura:- 6 unidades de entrada, - 8 unidades intermedias divididas en dos capas:

- 4 Neuronas estándar con función sigmoide.- 4 células de memoria

- Módulo CSVM con 4 salidas posibles.

Entrenamiento:- Enfoque ESP por 50 generaciones con medida de

fortaleza: mayor recompensa.- Ruido de Cauchy 10-4- Módulo CSVM con kernel Gabor.- Criterio de paro para cada generación: Alcanzar salida en 42

acciones u obtener recompensa de 4.0.

59

60

Salidaizquierda

Preprocesamiento

61

Segmentación por color

62

63

Salida izquierda, camino no óptimo

Salida

derecha

65

Salida derecha, camino no óptimo

66

Equipo con el que se cuentaLaboratorio de Investigación en

Robótica, Control y Biología Computacional

Mobile robots

Stereo vision system

Laser sensor

Linux-ubuntucomputer

Wireless comunication

Wheel encoders

Sistema estereoscópico de visión artificial

Cámaras flea 2 color. Resolution: 2.0

Megapixels Frame Rate: 1288x964

at 30 FPS Dimensions: 29 x 29 x

30 mm Interface: 9-pin IEEE-

1394b 800Mb/s interface.

Costo 6,000 dólares

Grupo de Investigación

Universidad de Guadalajara Dra. Alma Alanís García Dra. Nancy Arana Daniel Dr. Carlos Alberto López Franco Dr. Emmanuel Nuño Ortega

Relaciones de investigación con otras instituciones Cinvestav, Unidad Gdl.

Professor Dr. Eduardo Bayro Corrochacho (SNI III) Professor Dr. Edgar Sánchez Camperos (SNI III)

Intel Dr. Leo Hendrik Reyes Lozano Dr. Julio César Zamora Esquivel

Universidad Anáhuac Mayab Dr. Jorge Rivera Rovelo

Universidad de Amsterdam Dr. Arnoud Visser

Universidad de Oxford Julian de Hoog

Universidad Tecnológica de la República Checa Dr. Franc Vojtech

Universidad Politécnica de Cataluña, Barcelona, España. Professor Dr. Luis Basañez, Robotics Division Head

Proyectos CONACYT CIENCIA BÁSICA

OPTIMIZACIÓN CON PLANOS CORTANTES PARA MÁQUINAS DE VECTOR SOPORTE CON APLICACIONES EN NAVEGACIÓN ROBÓTICA Y PLANEACIÓN DE TRAYECTORIAS EN TERRENOS ESCABROSOS (Dra. Nancy Arana)

CONTROL NEURONAL DE ALTO ORDEN: ENFOQUE POR CONTROL POR BLOQUES Y POR CONTROL ÓPTIMO INVERSO (Dra. Alma Alanís)

Sometidos Robots de búsqueda y rescate (Dr. Carlos López) Teleoperación (Dr. Emmanuel Nuño)

71

Proyectos del grupo de investigación

PROMEP Reconocimiento de patrones Control inteligente Robots de búsqueda y rescate. Complejidad (control de diversos subsistemas)

Intel Procesamiento de imágenes y gráficas por

computadora

72

Sistemas óptimos inteligentes para reconocimiento de patrones y navegación robótica (Máquinas de vector soporte y Redes neuronales)�Introducción.Interpretación geométrica del aprendizaje artificial en redes neuronales y SVMAprendizaje supervisado.Clasificación binaria .Número de diapositiva 6Número de diapositiva 7Número de diapositiva 8Número de diapositiva 9Caso no lineal…y ahora ¿qué hacemos?Número de diapositiva 11Número de diapositiva 12Número de diapositiva 13Número de diapositiva 14Support Multivector Machines (SMVM)Número de diapositiva 16Número de diapositiva 17Número de diapositiva 18Número de diapositiva 19Número de diapositiva 20Número de diapositiva 21Número de diapositiva 22Comparación de características de generalización de kernel geométrico KG3 contra gaussiano.Número de diapositiva 24Número de diapositiva 25Support Multivector Machines con entradas codificadas como multivectores.Número de diapositiva 27Número de diapositiva 28Máquinas de Vector Soporte Geométricas (Clifford) para aprendizaje artificialEstado del arte.MotivaciónAplicacionesAplicaciones CSVM en clasificaciónNúmero de diapositiva 34Comparación de tiempos de entrenamiento en segundos.Número de diapositiva 36Número de diapositiva 37Número de diapositiva 38Número de diapositiva 39Número de diapositiva 40Clasificación multiclase 2DReconocimiento de Objetos 3DClasificación de objetosNúmero de diapositiva 44Número de diapositiva 45Número de diapositiva 46Sistema recurrente LSTM-CSVMSistema recurrente LSTM-CSVMMódulo LSTM-Neuroevolución del sistema LSTM-CSVMNúmero de diapositiva 51Resultados en predicción de series de tiempo.�Laguna de Venecia.Número de diapositiva 53Navegación robótica en laberintos discretos.�Aprendizaje reforzadoNavegación robótica en laberintos discretos. SimulacionesNúmero de diapositiva 56Navegación robótica en laberintos discretos. Sistema de percepción y acción�Navegación robótica en laberintos discretos. Sistema de percepción y acción�Número de diapositiva 59Número de diapositiva 60PreprocesamientoSegmentación por colorNúmero de diapositiva 63Número de diapositiva 64Número de diapositiva 65Número de diapositiva 66Mobile robotsSistema estereoscópico de visión artificialGrupo de InvestigaciónRelaciones de investigación con otras instituciones�ProyectosProyectos del grupo de investigación