Inteligencia artificial
Benasque 2004
José Ignacio Latorre
Dept. ECM, UB
Orígenes
Un poquito de historia
Alan Turing (37), Church, Post : Turing Machine
McCullough and Pitts (43) : neuronas binarias
John von Neumann : computadora de von Neumann
Dos escuelas de pensamiento, 50 ~ 60:
• Manipulación simbólica
Comportamiento inteligente consiste en reglas de manipulación de
símbolos
• Reconocimiento de patrones
Aprendizaje a partir de ejemplos
Orígenes
top
top
ejemplos
paralelo
difuso
robusto
general
reglas
serial
booleana
frágil
experto
down
down
Prolog, Lisp, IA
Sistemas expertos basados en reglas
1980’s : éxitos mediocres
reexamen del trabajo de los 60s en redes neuronales
Algoritmos
genéticos
Algoritmos genéticos
Idea básica
Problema
complejo
Algoritmo
conocido
Solución
ideal
A menudo este esquema no es realista
• Problemas NP
• Algoritmo desconocido
• Solución “buena y rápida” es aceptable
• ...
Deseamos hallar un método alternativo para analizar un gran número
de soluciones posibles
Aprendamos de la Naturaleza
Algoritmos genéticos
ADN
Operón off/on
Guanina
Adenina
Tiamina
Citosina
codón
gen
mRNA
20 aminoácidos + stops
proteínas
(cristal aperiódico, Schrödinger)
mRNA tRNA
Humanos: 3 109 bases
2 103 bases
pero 30000/40000
• ADN basura
• secuencias repetidas
• genes con multiples copias
• transposición de genes
• exones, intrones
• transposones
1 molécula ADN
1 gen
genes
Algoritmos genéticos
La reproduccion no preserva la forma exacta del material genético
Meiosis
Recombinación de material genético
crossover
Mutaciones
Mecanismos de corrección protegen parcialmente la fidelidad de la copia del ADN
copiado
- correcciones
1 error / 10000 bases
= 1 error / 109 bases
+ Selección Natural
Surpervivencia del mejor “adaptado” antes de la reproducción
Crossover aleatorio y mutaciones filtrados por selección natural a lo
largo de muchas generaciones lleva a especies mejor “adaptadas”.
Grandes poblaciones vienen de unos pocos individuos
Algoritmos genéticos
Estrategia de un Algoritmo Genético
Problema
Complejo
Solución
óptima
Buena
Población de soluciones
mutaciones
bajo ritmo
crossover
frecuencia alta
selección natural
ruleta
Los algoritmos genéticos son potentes
• AGs trabajan con una parametrización del problema
• AGs usan una función premio
• AGs usan reglas de transición probabilísticas
Algoritmos genéticos
Problema del viajante (Travelling Salesman Problem)
n
Hallar el camino que visita
n ciudades sólo una vez
1
2
Problema NP
Hay n! soluciones que explorar
No existe un algoritmo eficiente para hallar la solución
Mínimos locales, frustración
Uso práctico frecuente si se añaden ligaduras (rutas, llamadas de teléfono,..)
Parametrización
e.g.
A1 = {1,7,4,3,8,2,6,9,5}
mutación
crossover
premio
A2 = {1,7,3,4,8,2,6,9,5}
A3 = {1,8,2,6,7,4,3,9,5}
dist = d(1,7) + d(7,4) + ... + d(9,5) + d(5,1)
Algoritmos genéticos
TSP resultados
100 generaciones
10 ciudades
“soluciones” ~ 362880
Mínimo exacto
t ~ 1 min
dist = 3.394975
AG mínimo
t < 1s
distAG = 3.394975
11 ciudades
“soluciones” ~ 3628800
Mínimo exacto
t ~ 10 min
dist = 3.441836
AG mínimo
t < 1s
distAG = 3.441836
Algoritmos genéticos
101 ciudades
“soluciones” ~ 10156
Búsqueda aleatoria entre un millón
de recorridos (t ~ 30s) encuentra
una solución de
dist = 43.26733
AG mínimo t < 1s
distAG = 30.61271
Exploración de 106 “soluciones”
Algoritmos genéticos
¿Por qué funcionan los AGs?
Esquema
H=011* *1 *
Orden de un esquema
O(H) = O(011**1*) =4
(# dígitos fijos)
Longitud de un esquema
d(H) = d(011**1*) = 7
Palabra
Ai
bits l
población A = {A 1, A2, ..., An}
# esquemas posibles 3l
# esquemas presentes en una población de n palabras n 2l
(longitud de un patrón)
ex: A = { {1,0,1}, ...}
esquema: 101, 10*,1*1,
*01, 1**, *0*,
**1,***
Algoritmos genéticos
A tiempo t empezamos con m ejemplos de esquema H dentro de la población A
( hay n palabras en A y l bits en cada palabra )
m = m(H ,t)
Reproducción
Cada palabra es copiada de acuerdo a su adecuación
pi 
Ai
fi

f
j
j
m ( H , t + 1) = m ( H , t )
f (H )
f
Adecuación promedio de H
Adecuación promedio total
El destino de un esquema depende de
f ( H ) = (1 + c ) f
{
C>0 vida
C<0 muerte
m ( H , t ) = m ( H , 0 )(1 + c )
t
crecimiento exponencial
muerte exponencial
Algoritmos genéticos
Crossover + mutación destruye y crea nuevos esquemas
Crossover
Si el crossover es seleccionado al azar uniformemente, el esquema H es destruido
Con probabilidad
δ(H )
pd =
l -1
crossover con probabilidad pc
La probabilidad de supervivencia es
p survival = 1 - p d = 1 -
δ(H )
l -1
= 1 - pc
δ(H )
l -1
Mutación
O(H) posiciones deben mantenerse inalteradas
(1 - p m )
O(H )
 1 - O (H ) pm
mutación con probabilidad pm << 1
Algoritmos genéticos
Teorema fundamental de los Algoritmos Genéticos
m ( H , t ) = m ( H ,0 )
f (H )
f
( 1 - pc
δ(H )
l -1
- O (H ) pm )
Esquemas de bajo orden tienen exponencialmente
más descendientes en subsiguientes generaciones
n 2l (de entre 3l) esquemas son explorados
(sólo n3 son procesados eficientemente: paralelismo implícito)
Algoritmos genéticos
Un día en Las Vegas
0
1
RR
LL
LL
RR
LR
LL
LR
LL
RL
El bandido de dos brazos (Loaded two-arm bandit)
Juega una población de estrategias mutación-crossover-selección:
Beneficio óptimo
Algoritmos genéticos
... y otro día dedicado a las quinielas
4 partidos: 34=81 apuestas posibles
Problema: halla el número mínimo de apuestas que aciertan tres resultados como mínimo
Reducción = problema diofántico
DNA= propuesta de apuestas
Mutación y crossing
Fiteness= errores + #apuestas
1-7-80
3-7-8-14-33-65-81
106 generaciones:
solución óptima= 4apuestas !!!
1-7-34-73
3-7-22-76-80
Problema 1: 13 partidos – 1 error ?
Problema 2: 11 partidos – 2 errores ?
Redes Neuronales
Imitemos a una neurona
pesos entrada
umbral
i
activación
pesos salida
Realidad
Ficción
Redes Neuronales
... y la estructura de una red neuronal
Número de neuronas en la capa l-1
capa
zi
(l)
 n ( l 1 )
(l-1)
(l) 
 f  (  w ij z j  t i  )


 j 1

activación
pesos
Función de activación
umbral
Redes Neuronales
1
f ( x)
=
1+e
x
1,2
saturación
1
0,8
0,6
0,4
0,2
saturación
0
-10
-5
0
5
10
Respuesta lineal
Función de activación: sigmoide
Redes Neuronales
¿Qué controla el flujo de información?
las sinápsis
= pesos
los umbrales
y la arquitectura !!!!
Redes Neuronales
¡Hemos aprendido a aprender!
En el año 1985 se ideó un método para encontrar los
pesos y los umbrales a partir de ejemplos.
No es necesario entender cómo se resuelve un problema.
Podemos “entrenar” una red neuronal artificial con ejemplos.
Construimos una función error
ejemplo:
( in(p) ;
out(p) )
run NN:
z(1)(p) = in(p)
z(n)(p) = F( z(1)(p) )
p=1,...,patterns
error:
patterns
E

p 1
z
(n)
2
( p ) - out ( p )
Redes Neuronales
dEdw+
dEd t
dE=
dw
dt
dE
d w = - 
dw
dE=-
dd E
w
2
+
dE
d t = - 
dt
0
dE
dw
2
Redes Neuronales
w ij
Cambio de pesos
(l )
 w ij
(l )
 δw ij
(l )
( l)
δw ij =
δE
δw ij
Energía (error)
patterns

E
z
(n)
2
( p ) - out ( p )
p 1
Activación
zi
(l )
 n ( l 1 )
l
( l -1 )
(l ) 
 f (   w ji z j
 ti )


j

1


Para la última capa L=n
Δi
(L)
( p ) = f ' ( hi
hi
(L)
( p ))( z i
(L)
( p ) - out i ( p ))
( l)
Redes Neuronales
L
L-1
....
l
l-1 .......
n (l )
i
( l -1 )
( p )  f ' ( hi
( l -1 )

( p ))  
(l )
j
2
( p ) w ij
(l )
j 1
 Δ
patterns
(l)
δw ij =
(l)
i
(p)z
( l - 1)
j
(p)

j 1
patterns
( l)
δt i =

( l)
Δi (p)
j 1
BACK-PROPAGATION
Regla de la cadena

Aplicaciones Redes Neuronales
Créditos
Logística
Seguros
Sociología
Control
Fidelidad
Optimización
Bolsa
Data Mining
Aplicaciones Redes Neuronales
Ejemplo: pérdida de clientes
Una compañía desea saber qué clientes puede perder
Facturación Antigüedad
Líneas de pedido
Localización
1.
Entrenamos una red neuronal
con un subconjunto de datos
de clientes perdidos
y no perdidos
2.
Predecimos la fidelidad del resto
100
80
aciertos
totales
60
sesgo alto
40
Sí / No
sesgo bajo
20
0
1
2
Aplicaciones Redes Neuronales
Reconocimiento de imágenes
Una red neuronal ha
sido entrenada para
reconocer aviones
militares.
La red detecta que
hay un avión militar
escondido bajo el ala
de otro avión de pasajeros
Belgrado 19/04/1999
Aplicaciones Redes Neuronales
Reconocimiento de voz
• Dos personas dicen “Hello”
• Hacemos un análisis de frecuencias (60)
• Entrenamos una red con “hello”s
Steve
1
0
John
Buen reconocimiento
de voz requiere
entrenamiento
0
1
• Discrimnación de la red con “hello”s conocidos = 100%
• Discriminación de la red con “hello”s desconocidos = 100%
Aplicaciones Redes Neuronales
Series temporales de cotizaciones
Promedios sobre redes entrenadas a partir de pesos aleatorios
Si existe un modelo subyacente, las redes son equivalentes
Si no existe un modelo subyacente, las redes producen dispersión
+ 1sigma
Futuro ibex35 a 60 días
NN
Alarmas
Real
Arbitraje
….
-1 sigma
• Lanzamos 100 redes sobre
datos entrenar/validar
• Para cada dato tenemos un
promedio y una dispersión
• Descartamos 3 sigma
Opciones
Alarmas
Arbitraje
Estrategias
….
Aplicaciones Redes Neuronales
Las redes neuronales
Son aproximantes universales que implementan
inferencia bayesiana
Predicción
• enfermedades coronarias
• ventas
• divorcios
Clasificación
• clientes de un banco
• economía
Interpolación
• control de producción
• reconocimiento
Aplicaciones Redes Neuronales
¿Estoy divorciado?
Una red es entrenada con
• superficie de su primera vivienda
• virginidad
• nivel económico
• visitas de los suegros
• enfermedades...
¿Está usted divorciado?
acierto de la red neuronal: 88%
¿Soy matemático o filósofo?
acierto: 100%
¿Seré anoréxica/o?
¿Terminaré la carrera?
¿Lloverá mañana?
¿Ganará el Barça?
Estamos entrando en la era de la información
Descargar

Sin título de diapositiva