Dinámica no lineal, complejidad y caos en ambientes Microsoft

Billy ReynosoUniversidad de Buenos Aires

Billyr@microsoft.com.ar

Temario

• Teorías de la complejidad– Estructuras disipativas y derivaciones

– Paradigma discursivo - Autopoiesis y enacción

• Sistemas complejos– Autómatas celulares

– Redes booleanas aleatorias

– Programación evolutiva

– Redes neuronales

• Teorías del caos• Geometría fractal

Autómatas celulares

• John von Neumann – Stanislav Ulam

• Modelo de tablero de damas (Checkerboard model) – Sakoda – Schelling

• Autómatas de teselación, estructuras celulares, arrays iterativos

Vecindades• Moore

• Von Neumann

• Margolus (Hexagonal, gases)

John Conway• Juego de la vida

– Reglas:• Inactiva, 3 activas: Nace• Activa, 2 o 3 activas: Estasis• Otros casos: Muere• Survival/birth 23/3

– Estables, periódicos, móviles, reproductores– Deslizadores o planeadores (Gliders)– Arma o pistola deslizadora (Glider gun)– Life32:

• Switchen – Patrón más pequeño que se propaga indefinidamente• Gun30 – Bill Gosper’s

Objetos fijos, periódicos y móviles

Autómatas celulares – Stephen Wolfram

• Tipo I – Atractor de punto fijo

• Tipo II – Atractor periódico (108)

• Tipo III – Atractor caótico (18)

• Tipo IV – Atractor complejo

Wolfram - Tipos

Reglas MCell• Wolfram Class IV

– 1d Totalistic: Roots

• Auto-replicador– Edward Fredkin: regla más simple (Vote / Fredkin)

• Orden a partir del caos– Reacción de Beluzov-Zhabotinsky: Generations – BelZhav,

RainZha– Mescolanza (Hodgepodge) (Gerhard-Schuster): UserDLL-Hodge– Simulated Annealing: Vote-Vote4-5– Majority Rules: LGTG, Majority (Sakoda)

• Conway’s Life: Life

Reglas MCell

• Difusión de agregación limitada (Random walk): – UserDLL-DLA

• Langton, reproducción de DNA– UserDLL-DNA

• Reglas Greenberg-Hastings– CA excitables – Cyclic CA

• 313 – CCA - Cyclic spirals – GH Macaroni• GH (nucleación de espirales simétricos)

Reglas MCell

• Primitivas lógicas– GenBinary – Logic Rules

Parámetro Lambda – Chris Langton

• Fijo - Cristales

• Periódico – Sólido no cristalino

• Caótico - Gases

• Complejo: Filo del caos – Entre sólido y gaseoso

Redes booleanas aleatorias

• Stuart Kauffman

• Redes NK– K=1 – Estado de punto fijo, quietud, stalinismo– K=N – Caos, sensitividad a estado inicial,

anarquía– K=2 – Orden y caos balanceados, auto-

organización, criticalidad auto-organizada

Modalidades

• Algoritmo genético – John Holland• Estrategia evolutiva (Rechenberg-Schwefel)

– Rasgos: conductas– Evaluación: relación entre rasgos– Operadores: mutaciones gaussianas, combinaciones de vectores de

progenitores

• Programación genética (John Koza)– Arboles, LISP

• Memética (Richard Dawkins, Daniel Dennett)– Memes– No crossover, mutación al azar

Algoritmo genético

• Población• Cromosomas: serie de caracteres• Gen: Carácter• Cross-over• Mutación• Ciclo:

– 1. Generar población– 2. Aplicar criterio de fitness– 3. Los mejores se reproducen, los peores mueren– 4. Aplicar mutaciones– 5. Aplicar criterio de fitness– 6. Volver a 3

Algoritmo genético

• Cross-over

Ejemplo…ALGORITMO GENETICO EN EL DF2727

1100 80 0.1

Dos modelos

• IA “fuerte” - MIT– Artificial– Ligada a computadoras, lógica– Modelo mecánico– Deducción: cálculo de predicados– Newell-Simon, Russell/Whitehead, Frege– Atomismo, racionalismo

• Conexionismo – PDP (Parallel Distributed Processing)– Natural– Simulación del cerebro– Redes neuronales

Inteligencia artificial

• IA “fuerte”– Modelo de procesamiento de información– Programación lógica

• Hechos• Reglas• Teoremas

– Modelo de sistema de símbolos físicos– Sistemas expertos

• Máquina de inferencia• Base de dato

– Inferencia clínica (Mycin, Neo-Mycin, Pip, Internist, Dendral, SHRDLU)

Conexionismo• Redes de McCulloch – Pitts (1943)

– Neuronas como puertas lógicas– Pesos: sinapsis excitativas, s. inhibitorias– Capacidad de computación universal– Máquina de lectura para ciegos, percdepción gestáltica

• Von Neumann, Winograd– Redundancia en McC-P para tolerancia a errores

• Sinapsis de Hebb (1949)– Basado en Ramón y Cajal– Modelo distribuido (hologramático)– Aprendizaje: redes neuronales adaptativas (McKay, Uttley, 1950)– Reconocimiento de patrones

Conexionismo

• Perceptrones (Rosenblatt)– Entrenamiento para distinción de patrones

– Unidades sensoriales y motoras

– Aumento o disminución de pesos (conductismo)

• Papert / Minsky– Distinción entre T y C, con rotación etc

– No pueden resolver XOR y funciones lógicas que requieren más alto nivel de tipificación

Modelos ulteriores

• Redes de Hopfield– Spin glass: Problemas de optimización, vendedor ambulante

(simulación de templado, AG, etc) – Atrapadas en configuraciones metaestables

• Máquinas de Boltzmann– Múltiples capas– Propagación hacia atrás– Kohonen: entrenamiento no asistido– Resolución XOR, T/C– NetTalk: lee y habla inglés– Redes amo-esclavo, filtros de Gabor– Modelos mixtos: AARON

Situación actual

• Situación incierta de IA fuerte– Sentido común: Estructuras, templates, frames, scripts,

mapas cognitivos– Dreyfus: What computers can’t do (Flores, Heidegger)– Deep Blue vence a Gasparov

• Divisiones en el paradigma conexionista– Conexionismo eliminativo: sin semántica ni nivel simbólico– Conexionismo implementacional:

representación sub-simbólica– Conexionismo revisionista de procesamiento de símbolos

(escuela de San Diego)