Inteligencia artificial y autómatas celulares

Por Colaborador Invitado, el 3 agosto, 2020. Categoría(s): Matemáticas • Tecnología
El “planeador” (glider) es uno de los patrones más conocidos en el Juego de la Vida de Conway. También es el emblema hacker. Esta es una composición del “planeador” y HAL 9000, probablemente la IA más famosa del cine por “2001: Una odisea del espacio”. La imagen del “planeador” es de dominio público. La imagen de HAL 9000 es de Pixabay y tiene licencia Creative Commons CC0 1.0 Universal Public Domain Dedication.

¿De dónde vienen los autómatas celulares?

Los Autómatas Celulares (AC) fueron introducidos por primera vez en los años 40 y 50 por Stanislaw Ulam y John von Neumann. Este último es quizás uno de los matemáticos más relevantes del siglo XX, quien realizó grandes aportaciones al campo de la ciencia de la computación, entre otros muchos campos. En 1970 los AC alcanzaron su máxima popularidad con el denominado “Juego de la vida” de John Horton Conway [1]. Dicho juego mostró cómo a partir de un sencillo conjunto de reglas, el sistema evoluciona de forma autónoma donde es posible que aparezcan patrones complejos, sirviendo como claro ejemplo de uso de emergencia y autoorganización. Como la vida misma. Ha sido y es estudiado por matemáticos, filósofos, sociólogos, y economistas, entre otros. Pero fue en 2002 cuando los AC tomaron relevancia científica de la mano del matemático Stephen Wolfram y de su famoso trabajo “A new kind of science” [2].

¿Qué son?

Un AC no es más que un modelo matemático que modela sistemas dinámicos y que evoluciona en pasos discretos. A pesar de su simplicidad, son capaces de describir y reproducir fenómenos complejos. Una de las características más apreciadas de los AC es que son máquinas de computación universal o máquinas de Turing [3]. Y esto significa que son el más simple modelo de computación lo suficientemente poderoso como para calcular todas las posibles funciones que pueden ser calculadas [4]. Y otra característica que los distingue es que permiten la computación en paralelo, operando sobre el principio de que problemas grandes, que a menudo se pueden dividir en problemas más pequeños, pueden ser resueltos simultáneamente (en paralelo).

Se puede decir que su atractivo reside en su simplicidad. Y es que simplemente a través de la interacción local que se produce entre las celdas de una malla cuando se aplica una regla, los AC son capaces de ofrecer un complejo comportamiento cuando todas las celdas de la malla se actualizan a la vez. Un AC se compone de una malla de celdas, de un conjunto finito de estados, la regla local, y de una vecindad.

  • Las celdas viven en una malla. Hay muchos tipos de AC [5,6], pero este artículo se va a centrar en quizás su versión más popular, los AC de 2 dimensiones. (Ver Figura 1)
  • Cada celda tiene solo un estado. El número y tipo de estados lo define el problema en cuestión, pero la versión más simple tendría, por ejemplo, un estado=0 cuando la celda está apagada y un estado=1 si está activa. (Ver Figura 2)
  • Cada celda tiene una vecindad, es decir, un conjunto de celdas adyacentes. Para calcular la vecindad se usa un radio, que delimita la magnitud de la vecindad. (Ver Figura 1)
  • La vecindad se usa para aplicar la regla local, la cual define la evolución que sigue el AC a medida que se suceden los pasos discretos (generaciones), y que a veces puede entenderse como tiempo. En la Figura 2 se puede ver cómo el estado de la celda (?) viene dado por el estado mayoritario de su vecindad
Figura 1. AC de 2 dimensiones: con vecindad von Neumann de radio=1 (arriba a la izquierda), con vecindad Moore de radio=1 (arriba a la derecha), con vecindad von Neumann de radio=2 (abajo a la izquierda), y con vecindad Moore de radio=2 (abajo a la derecha).

 

Figura 2. AC de 2 dimensiones: con vecindad von Neumann de radio=1 donde se aplica una regla de mayoría (arriba), y con vecindad Moore de radio=1 donde se aplica una regla de mayoría (abajo).

Los AC tienen 3 interesantes propiedades:

  • Paralelismo o sincronicidad, por la que todas las celdas de la malla se actualizan a la vez. Aquí mencionar que existen AC asíncronos, en los cuales no todas las celdas de la malla se actualizan al mismo tiempo, sino que siguen ciertas reglas para hacer la actualización
  • Localismo, donde el estado de una celda depende de su anterior estado y del estado anterior de todas las celdas de su vecindad
  • Homogeneidad, donde la misma regla es aplicada a todas las celdas de la malla

¿Cómo funcionan?

Al principio es necesario inicializar la malla asignando un estado a cada celda (por ejemplo, 0 y 1). En la siguiente generación se aplica la regla local a todas las celdas de la malla al mismo tiempo, y de esta manera se obtiene un nuevo estado para todas ellas. Normalmente se aplica la misma regla a todas las celdas de la malla simultáneamente, aunque hay variaciones [7]. Y así sucesivamente, hasta alcanzar una condición concreta, como por ejemplo hasta completar un número determinado de generaciones, o hasta que los estados de las celdas no cambien.

Figura 3. Evolución de un AC de 2D con vecindad Moore y radio=1 al aplicar una regla de mayoría durante 4 generaciones.

¿Para qué se usan?

Tradicionalmente, los AC se han usado para simular sistemas biológicos y físicos. Pero cada vez son más los problemas de la vida real que se resuelven con ellos [8, 9].

  • Diseño de circuitos electrónicos. En la era del Very Large Scale Integration (VLSI), la simplicidad, paralelismo, y modularidad de los AC han llamado la atención de los investigadores y constructores
  • Procesamiento de imágenes. Los AC son capaces de procesar con éxito algunas de las tareas habituales como: translation, zooming, rotation, segmentation, thinning, compression, edge detection y noise reduction
  • Medicina. Evolución de secuencias de ADN, modelado de aminoácidos, predicción y clasificación de enzimas, predicción de estructura de proteínas, etc. Y para estudiar la evolución de epidemias y predecirlas, por lo que los AC son uno de los métodos que se están aplicando al COVID-19.
  • Computación. Por las limitaciones de la tecnología CMOS en circuitos integrados, se ha explorado en profundidad el uso de Quantum-dot Cellular Automata
  • Problemas de Optimización y Job Scheduling
  • Otros. Juegos, comportamientos sociales, expansión de fuego, simulación de tráfico, evolución y movimientos poblacionales, criptografía, etc.

Pero uno de los usos que más llama la atención, y que podría revolucionar alguno de los avances que está por venir, es su papel en la Inteligencia Artificial (IA).

¿Cuál es su relación con la IA?

A pesar de que los AC como método de Pattern recognition fueron introducidos en [10, 11, 12], no fue hasta [13] cuando tomaron cierta relevancia gracias a Tom Fawcett, quién los presentó como un método serio a tener en cuenta. A raíz de este trabajo, los AC demostraron ser capaces de extraer con éxito patrones de los datos, y generar modelos explicables. Para que los AC sean un método aplicable al campo de Pattern recognition, hay que hacer algunas modificaciones:

  • Se asigna una dimensión a cada una de las características (features) del conjunto de datos
  • Cada dimensión se divide en varias particiones (bins) en función de los rangos de los valores que tiene cada una de las características (features)
  • Cada estado corresponderá con cada uno de los diferentes valores que tenga la clase de la variable a predecir (target variable), también llamadas etiquetas (labels)
  • Se define la vecindad y la regla local como en cualquier AC
  • Se “siembra” la malla del AC con unos datos iniciales. Aquí, cada instancia es asignada a una celda concreta en función de los valores de sus características, y esta celda adopta el estado de la label de dicha instancia
  • Después, se aplica la regla local hasta que la malla está completa (todas las celdas tienen un estado asignado). Entonces, la regla se puede seguir aplicando hasta que la malla no cambie o hasta un número predeterminado de generaciones. Ver Figura 4

Figura 4. Ejemplo de cómo un AC de 2D con vecindad von Neumann y radio=1 es capaz de extraer patrones y representar fielmente la distribución de los datos con solo unas pocas instancias iniciales después de 7 generaciones. En este caso es un conjunto de datos con 2 características que se mueven en valores que van de 0 a 1, y que corresponde con un problema binario, y por tanto con dos valores en su “target variable” (amarillo claro y oscuro). Se presenta en la parte superior un AC de 5 “bins”, en el medio de 10 “bins”, y abajo de 20 “bins”. Imagen tomada de [14] y modificada.
Recientemente, en [14] se ha presentado un trabajo en el que se adaptan los AC para su funcionamiento en Streaming, es decir, para que los AC se puedan usar en analítica de datos en tiempo real. También se considera en este trabajo la posibilidad de que suceda el fenómeno conocido como concept drift [15], donde los datos pueden cambiar, y por tanto es necesaria una adaptación de los modelos (en este caso de los AC).

Los AC también son también conocidos en las tareas de optimización [16]. Se han hibridado con algoritmos genéticos para abordar problemas de optimización multi-objetivo. En la práctica se han aplicado a problemas como por ejemplo el enrutado de vehículos. Recientes investigaciones apuntan también a un interesante uso en Transfer Optimization [17], donde la idea es aprovechar el aprendizaje obtenido en la optimización de una tarea para ser usado en otra tarea que pueda estar o no relacionada.

¿Por dónde puede ir el futuro de los AC en la IA?

Han surgido en los últimos años algunos paradigmas interesantes, basados en minúsculas unidades de procesamiento interconectadas (ej: sensores, robots, dispositivos varios), donde la capacidad de computación en paralelo de los AC ha atraído la atención de algunos investigadores y fabricantes. Algunos de estos paradigmas son:

  • Smart Dust es “… una hipotética red inalámbrica de minúsculos sensores microelectromecánicos (MEMS), robots o dispositivos que pueden detectar señales de luz, temperatura, vibraciones, etc. Los dispositivos también se llaman motas (motes en inglés: de remote sensing) y se trabaja en disminuir su tamaño hasta el de un grano de arena, o incluso de una partícula de polvo. Imaginariamente cada dispositivo contiene sensores, circuitos que computan, tecnología de comunicaciones sin hilos bidireccional y una fuente de alimentación. Las motas recopilarían datos, realizarían cómputos y se comunicarían por radio con otros en distancias que se acercan a 300 metros (1.000 pies)” [18]
  • Utility Fog es “… una hipotética colección de minúsculos robots que juntos llevarían a cabo una determinada función. Constituirían hipotéticas sustancias polimorfas (capaces de cambiar de forma), que típicamente presentarían una estructura de armadura de octeto (octet truss)” [19]
  • Swarm Robotics hace referencia a la aplicación de métodos y conceptos propios de la inteligencia de enjambre (“Swarm Intelligence”) a escenarios en los que los agentes computacionales representan dispositivos robóticos, ya sean físicamente implementados o simulados. El principal foco es el de analizar cómo un enjambre compuesto por robots de una complejidad e inteligencia baja puede coordinarse de una manera colectiva para poder llevar a cabo tareas de una complejidad elevada, las cuales no podrían ser completadas por un solo robot

Destacar el ya mencionado uso de los AC en tareas de Pattern Recognition, donde se siguen y seguirán realizando avances, como su aproximación a redes convolucionales en [20], a deep learning [21], etc. Por último, puede tomar especial relevancia el uso de Quantum Cellular Automaton (QCA) [22].

 

Este artículo nos lo envía Jesús (Txus) López Lobo, licenciado en Ingeniería Informática por la Universidad de Deusto, Máster en Inteligencia Artificial Avanzada por la UNED, y doctor internacional en Tecnologías de la Información y Comunicaciones en Redes Móviles por la UPV/EHU. Trabaja como Científico de Datos e Investigador en Inteligencia Artificial en TECNALIA, miembro de la Basque Research Technology Alliance (BRTA).También hace divulgación de sus artículos científicos en su blog en Medium y mediante su Linkedin.

Agradecimientos especiales:

En primer lugar, me gustaría agradecer al Dr. Javier Del Ser y al Dr. Eneko Osaba por sus contribuciones a este artículo, y por servir de guía y apoyo en las investigaciones que hemos llevado a cabo juntos en este y otros campos. No quiero perder la ocasión para agradecer también a John Horton Conway y Tom Fawcett (por desgracia para la comunidad científica, ambos fallecidos recientemente) por sus contribuciones al campo de los autómatas celulares. 

Referencias

[1] https://es.wikipedia.org/wiki/Juego_de_la_vida

[2] Wolfram, S. (2002). A new kind of science (Vol. 5, p. 130). Champaign, IL: Wolfram media.

[3] https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

[4] https://psicologiaymente.com/cultura/maquina-de-turing

[5] https://natureofcode.com/book/chapter-7-cellular-automata/

[6] https://en.wikipedia.org/wiki/Cellular_automaton

[7] Schiff, J. L. (2011). Cellular automata: a discrete view of the world (Vol. 45). John Wiley & Sons.

[8] Bhattacharjee, K., Naskar, N., Roy, S., & Das, S. (2018). A survey of cellular automata: Types, dynamics, non-uniformity and applications. Natural Computing, 1–29.

[9] Navid, A. H. F., & Aghababa, A. B. (2013). Cellular learning automata and its applications. Emerging Applications of Cellular Automata, 85–111.

[10] Jen, E. (1986). Invariant strings and pattern-recognizing properties of one-dimensional cellular automata. Journal of statistical physics, 43(1–2), 243–265.

[11] Raghavan, R. (1993). Cellular automata in pattern recognition. Information Sciences, 70(1–2), 145–177.

[12] Chaudhuri, P. P., Chowdhury, D. R., Nandi, S., & Chattopadhyay, S. (1997). Additive cellular automata: theory and applications (Vol. 43). John Wiley & Sons.

[13] Fawcett, T. (2008). Data mining with cellular automata. ACM SIGKDD Explorations Newsletter, 10(1), 32–39.

[14] Lobo, J. L., Del Ser, J., & Herrera, F. (2020). LUNAR: Cellular Automata for Drifting Data Streams. arXiv preprint arXiv:2002.02164.

[15] Gomes, H. M., Read, J., Bifet, A., Barddal, J. P., & Gama, J. (2019). Machine learning for streaming data: state of the art, challenges, and opportunities. ACM SIGKDD Explorations Newsletter, 21(2), 6–22.

[16] Alba, E., & Dorronsoro, B. (2009). Cellular genetic algorithms (Vol. 42). Springer Science & Business Media.

[17] Osaba, E., Martinez, A. D., Galvez, A., Iglesias, A., & Del Ser, J. (2020). dMFEA-II: An Adaptive Multifactorial Evolutionary Algorithm for Permutation-based Discrete Optimization Problems. arXiv preprint arXiv:2004.06559.

[18] https://es.wikipedia.org/wiki/Polvo_inteligente

[19] https://es.wikipedia.org/wiki/Niebla_%C3%BAtil

[20] Gilpin, W. (2019). Cellular automata as convolutional neural networks. Physical Review E, 100(3), 032402.

[21] Nichele, S., & Molund, A. (2017). Deep learning with cellular automaton-based reservoir computing.

[22] https://en.wikipedia.org/wiki/Quantum_cellular_automaton

 



Por Colaborador Invitado, publicado el 3 agosto, 2020
Categoría(s): Matemáticas • Tecnología