1
Sistemas óptimos inteligentes para reconocimiento de patrones y navegación robótica (Máquinas de vector soporte y Redes neuronales)
Dra. Nancy Arana [email protected]
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