Análisis de sistemas complejos usando machine learning

ANÁLISIS DE SISTEMAS COMPLEJOS USANDO MACHINE LEARNING Alejandro Luque Cerpa ANÁLISIS DE SISTEMAS COMPLEJOS USANDO MACHINE LEARNING Alejandro Luque Cerpa Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Dr. Fernando Sancho Caparrini Agradecimientos Muchas gracias a mi tutor, el Prof. Dr. Fernando Sancho Caparrini, primero por haber influido en mi elección de este Trabajo de Fin de Grado al mostrarse como un excelente profesor en la asignatura de Inteligencia Artificial, y segundo, aunque no menos importante, por haberme guiado en su elaboración. Muchas gracias también a mis padres, porque sin ellos no estaría aquí. Agradecimientos también a mi antiguo profesor de matemáticas Curro Piñero, porque sin él las cosas hubieran sido muy distintas. ii análisis de sistemas complejos usando machine learning A Rafael Leal, por acompañarme en esta aventura desde el principio. Índice general English Abstract 1 1. Introducción 3 1.1. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Autómatas Celulares 7 2.1. Introducción................................ 7 2.1.1. Contexto histórico . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2. Aplicaciones............................ 10 2.2. Definiciones y clasificación . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Machine Learning 21 3.1. Introducción................................ 21 3.2. Aproximación Matemática al Aprendizaje Automático . . . . . . . . . 24 3.3. Algoritmos................................. 29 3.3.1. Predictores lineales . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2. k-Vecinos más cercanos . . . . . . . . . . . . . . . . . . . . . 33 3.3.3. Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . 35 iv análisis de sistemas complejos usando machine learning 3.3.4. Boosting.............................. 38 3.3.5. Máquinas de soporte vectorial . . . . . . . . . . . . . . . . . . 40 3.3.6. Multiclases ............................ 43 3.3.7. Redes neuronales . . . . . . . . . . . . . . . . . . . . . . . . . 44 4. Resultados Experimentales 49 4.1. Consideraciones previas . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.1. Autómatas Celulares . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.2. Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2. Implementación.............................. 51 4.3. Aprendizaje ................................ 52 4.3.1. Aprendizaje global: predicción de la mayoría . . . . . . . . . 53 4.3.2. Aprendizaje local: predicción de una célula . . . . . . . . . . 56 4.3.3. Aprendizaje local: predicción de tres células . . . . . . . . . . 61 4.3.4. Otros experimentos . . . . . . . . . . . . . . . . . . . . . . . . 63 5. Conclusiones y Trabajo Futuro 71 5.1. Conclusiones................................ 71 5.2. TrabajoFuturo............................... 72 6. Apéndice 77 English Abstract Nowadays, we can find complex systems in a great variety of fields, such as biology, physics, engineering or social systems. From fluid dynamics to biomolecular interactions, we can find complex systems everywhere, and it is not an easy task to predict their behaviour. Cellular automata are considered great techniques of modelling complex systems. In cellular automata, some simple rules lead sometimes to emergent chaotic or complex behaviours that are interesting in the context of some real-life complex models. Machine Learning algorithms are well known for identifying underlaying patterns in complex structures. In this paper, cellular automata and some Machine Learning algorithms, such as Neural Networks or k-Nearest Neighbours are introduced, and after that some of them are used to analyze cellular automata. The aim of this paper is to define a way of working with cellular automata and machine learning that can be expanded later with new algorithms, new automata or more data. 8análisis de sistemas complejos usando machine learning Figura 2.1: Von Neumann. Recuperada de www.eldiario.es riantes que podían construirse de los primeros modelos formales definidos, a finales de los años 50 y principios de los 60, se obtuvieron una serie de resultados mucho más detallados y técnicos que probaban la capacidad computacional de los autómatas celulares que, bajo determinadas condiciones, era equivalente a los que ofrecían las máquinas de Turing. Debido al carácter dinámico de la evolución de los autómatas celulares, también se produjeron los primeros intentos de conectar éstos con Sistemas Dinámicos. En 1968, a pesar de la poca investigación desarrollada sobre ellos, John Conway comenzó a trabajar, primero a mano y más tarde con ayuda de ordenadores, en una gran variedad de reglas para autómatas celulares de dos dimensiones. Más adelante, en 1970, expuso una serie de reglas a las que llamó "El juego de la vida" (una muestra en la figura 2.2), y que se popularizaron a través de la revista Scientific American por Martin Gardner. Estas reglas exhibían, a pesar de ser bastante simples, un amplio rango de comportamientos complejos. Además, y de forma completamente independiente, algunos casos particulares de autómatas celulares 2D (2.3) se aplicaban desde los 50 a modo de filtros para eliminar el ruido en el procesamiento de imágenes digitales. Mucho más adelante, en algunos artículos de Stephen Wolfram que también se recogen en [1], se define una clasificación de los autómatas celulares en cuatro clases según la complejidad que muestran en sus dinámicas. Esta es una de las clasificaciones más conocidas, y divide el conjunto de posibles autómatas celulares entre aquellos que se estabilizan en un estado, los que repiten una serie de estructuras periódicamente, los que evolucionan a patrones caóticos, y los que evolucionan a patrones complejos, algunos con larga duración. Los límites entre estas clases son difíciles de discernir a veces, especialmente entre los dos últimos. 2. autómatas celulares 9 Figura 2.2: Juego de la vida. Recuperada de www.daviddarling.info Figura 2.3: Ejemplo de la regla 110. Recuperada de mathworld.wolfram.com 10 análisis de sistemas complejos usando machine learning Culik y Yu presentaron en 1988 [2] una clasificación formal que se corresponde con la de Wolfram y que será descrita más adelante en este mismo capítulo. Otra clasificación surge de los trabajos de Li y Packard, que en [3] extienden el esquema de Wolfram a seis clases de complejidad, que también serán descritas más adelante. 2.1.2 Aplicaciones Más allá del estudio teórico acerca de la complejidad que pueden alcanzar los autómatas celulares y su clasificación, existen bastantes aplicaciones a distintos problemas del mundo real. Algunos ejemplos son los siguientes: El crecimiento de algunos cristales, y en concreto los patrones en copos de nieve, pueden ser modelizados por autómatas simples en 2D (Figura 2.4). Los patrones encontrados en las conchas de los moluscos Cymbiola innexa son similares a los generados por la regla 30 en los autómatas celulares 1D (Figura 2.5). En criptografía, si se combinan distintas reglas para determinadas células dentro de un mismo autómata, y se usan reglas lo suficientemente caóticas, se pueden cifrar cadenas, siendo extremadamente costoso en tiempo intentar revertir el proceso sin saber qué reglas se han utilizado. Procesamiento de imágenes digitales en medicina. Modelización de la activación eléctrica del corazón en cada pulsación. Modelización de dinámica de fluidos, como por ejemplo los modelos de Latticegas y Lattice Boltzman. Modelización del flujo de tráfico en ciudades [4]. Figura 2.4: Autómata celular y copo de nieve. Recuperada de www.nap.edu 2. autómatas celulares 11 Figura 2.5: Cymbiola innexa. Recuperada de www.caledonianseashells.com 2.2 Definiciones y clasificación Aunque hay una gran variedad de Autómatas Celulares según sus características, estudiaremos únicamente los más habituales y sencillos, que son autómatas celulares síncronos cuya topología es una cuadrícula rectangular infinita, de forma que cada célula se identifica con una casilla de la cuadrícula. Definición 2.1. Un autómata celular se define a partir de: Una matriz infinita de casillas de dimensión 𝑑. Cada casilla se denomina célula. Formalmente, podemos identificar esta matriz con ℤ𝑑. Un conjunto finito de estados, 𝑆. Cada célula toma en cada momento un valor de este conjunto. Este conjunto se denomina alfabeto. Una configuración inicial, es decir, una asignación inicial de un estado a cada una de las células del espacio. Formalmente, la configuración es una función 𝑐∶ℤ𝑑→𝑆 que especifica el estado de cada célula. Las funciones constantes se denominan configuraciones homogéneas. El conjunto de todas las configuraciones se denota por (𝑑, 𝑆), o por si 𝑑y𝑆se conocen por el contexto. La vecindad de cada célula, que es el conjunto de células que se consideran adyacentes a una dada. Es común especificar el conjunto de vecinos de una célula 𝑥por medio de un vector 𝑁𝑥= (𝑥1, ..., 𝑥𝑛)de 𝑛elementos distintos de ℤ𝑑, de forma que los vecinos son las células de las casillas 𝑥+𝑥𝑖con 𝑖= 1, ..., 𝑛. Normalmente, se considera el mismo vector 𝑁𝑥para todas las células del autómata. Una función de transición local 𝑓∶𝑆𝑛→𝑆 12 análisis de sistemas complejos usando machine learning donde 𝑛es el tamaño del conjunto de células vecinas. Esta función toma como valores de entrada la vecindad de una célula, y devuelve el próximo estado de dicha célula. Con la función de transición local se puede construir una función de transición global, 𝐺∶→. Las células cambian su estado de forma síncrona en intervalos de tiempo discretos. El siguiente estado depende del estado de las células vecinas (la condición de vecindad es distinta para cada autómata). Todas las células usan la misma regla para actualizar su estado. Se muestran algunos ejemplos en las Figuras 2.6, 2.7 y 2.8. Figura 2.6: Autómata hexagonal. Recuperada de www.mced-ecology.org Figura 2.7: Ejemplos de autómatas 1-D. Recuperada de users.math.yale.edu 2. autómatas celulares 13 Figura 2.8: Ejemplo de autómata 2-D. Recuperada de culturacolectiva.com A partir de este momento trabajaremos con autómatas celulares con dimensión 𝑑= 1, alfabeto 𝑆= {0,1}, y considerando que la vecindad de una célula está compuesta por la célula que está a su izquierda y la que está a su derecha. En este caso, será habitual considerar autómatas celulares en los que solo analizamos el comportamiento y evolución de una cantidad finita de células situadas de forma adyacente ocupando posiciones de la forma {1,…, 𝑛}. Con el fin de seguir dando una definición homogénea del autómata es necesario distinguir qué ocurre en la frontera del mismo (es decir, en las células que ocuparían las posiciones extremas adyacentes, 0y𝑛+ 1). Lo habitual es considerar que las posibles vecinas a estos extremos toman valores que son dependientes de la zona considerada por nuestro conjunto finito de células, y podemos distinguir entre: Frontera abierta: las células frontera toman un valor fijo: 𝑐(0) = 𝑐(𝑛) = 𝑠0. Frontera reflectora: las células frontera toman los valores que están dentro, como si fuera un espejo: 𝑐(0) = 𝑐(1), 𝑐(𝑛+ 1) = 𝑐(𝑛). Frontera circular: las células frontera copian el contenido del otro extremo: 𝑐(0) = 𝑐(𝑛), 𝑐(𝑛+ 1) = 𝑐(1) (Figura 2.9). 14 análisis de sistemas complejos usando machine learning Figura 2.9: Frontera circular. Recuperada de www.cs.us.es En el caso de que el autómata sea infinito se denomina sin frontera y no existen células frontera. En dicho caso, cada célula ocupa una posición de ℤ. En lo que sigue, consideraremos que nuestros autómatas tienen frontera circular. Proposición 2.1.En las condiciones expuestas anteriormente (𝑑= 1 y|𝑁|= 3) existen únicamente 256 funciones de transición local posibles. Demostración. Esto se debe a que la función de transición transforma el estado de tres células (la que estudiamos y su vecindad) en un nuevo estado. Esto significa que cada función de transición transforma cada uno de las 8 posibles combinaciones de estados (3 células con 2 posibles estados cada una) en un valor que puede ser 0 o 1. En consecuencia, tenemos 28posibilidades. Notación 2.1.Cada función de transición la notaremos por un número entre 0 y 255 siguiendo el esquema que se especifica a continuación: Dado el siguiente orden prefijado a las posibles configuraciones locales del autómata (que se corresponde con el orden natural de la representación decimal de las configuraciones): 𝑐1= 000, 𝑐2= 001, 𝑐3= 010, 𝑐4= 011, 𝑐5= 100, 𝑐6= 101, 𝑐7= 110, 𝑐8= 111 2. autómatas celulares 15 y supuesto que la regla 𝑟se escribe en binario como 𝑟=𝑟1…𝑟8∈ {0,1}8, la regla 𝑟 asigna a la configuración local 𝑐𝑖el valor 𝑟𝑖. Por ejemplo, la regla 30, que en binario es 00011110, proporciona la función de transición siguiente: 𝑟30(000) = 0, 𝑟30(001) = 0, 𝑟30(010) = 0, 𝑟30(011) = 1 𝑟30(100) = 1, 𝑟30(101) = 1, 𝑟30(110) = 1, 𝑟30(111) = 0 Definición 2.2. Sea 𝐴un autómata celular con función de transición local 𝑓. Podemos definir las siguientes transformaciones (donde 𝑥= 1 − 𝑥): Transformación espejo: 𝑓(𝑥𝑖−1, 𝑥𝑖, 𝑥𝑖+1) = 𝑓(𝑥𝑖+1, 𝑥𝑖, 𝑥𝑖−1)∀𝑥𝑖∈𝑆 Transformación 0-1: 𝑓(𝑥𝑖−1, 𝑥𝑖, 𝑥𝑖+1) = 𝑓(𝑥𝑖−1, 𝑥𝑖, 𝑥𝑖+1)∀𝑥𝑖∈𝑆 Transformación conjunta: 𝑓(𝑥𝑖−1, 𝑥𝑖, 𝑥𝑖+1) = 𝑓(𝑥𝑖+1, 𝑥𝑖, 𝑥𝑖−1)∀𝑥𝑖∈𝑆 Nota 2.1.Con la representación binaria introducida anteriormente, si 𝑓viene dada por la cadena (𝑓0, 𝑓1, 𝑓2, 𝑓3, 𝑓4, 𝑓5, 𝑓6, 𝑓7), las reglas que se obtienen con las transformaciones anteriores son: 𝑓= (𝑓0, 𝑓4, 𝑓2, 𝑓6, 𝑓1, 𝑓5, 𝑓3, 𝑓7) 𝑓= (𝑓7, 𝑓6, 𝑓5, 𝑓4, 𝑓3, 𝑓2, 𝑓1, 𝑓0) 𝑓= (𝑓7, 𝑓3, 𝑓5, 𝑓1, 𝑓6, 𝑓2, 𝑓4, 𝑓0) Proposición 2.2.Utilizando las transformaciones de la definición anterior, podemos extraer únicamente 88 reglas independientes. La tabla 2.1 muestra las distintas clases independientes que existen, y en las que podemos clasificar el conjunto de los 256 autómatas simples 1D. Por otra parte, en el apéndice (ver a partir de 6.1) habrá muestras de las 88 reglas. Demostración. Sea 𝑟una regla de un autómata celular. Consideraremos los posibles resultados que se pueden dar al aplicar las anteriores transformaciones sobre la regla 𝑟: 16 análisis de sistemas complejos usando machine learning 1. (𝑟) = (𝑟) = 𝑟. Esto implica que (𝑟) = 𝑟. 2. (𝑟) = (𝑟)≠𝑟. Esto implica que (𝑟) = (𝑟) = (𝑟)≠𝑟. 3. (𝑟) = 𝑟≠ (𝑟). Esto implica que (𝑟) = (𝑟). 4. (𝑟)≠𝑟=(𝑟). Esto implica que (𝑟) = (𝑟). 5. (𝑟)≠ (𝑟)≠𝑟. Esto implica que (𝑟)≠ (𝑟)≠ (𝑟)≠𝑟(en el sentido de que todos son diferentes al resto). Se puede probar usando que ((𝑟)) = 𝑟 con una de las operaciones El caso 1 da conjuntos de una sola regla. Los casos 2, 3 y 4 dan conjuntos con dos reglas. El caso 5 da conjuntos de 4 reglas. Por tanto, si 𝑛1, 𝑛2, 𝑛3, 𝑛4y𝑛5son el número de elementos en los distintos conjuntos respectivamente, entonces el total de reglas independientes es: 𝑛1+(𝑛2+𝑛3+𝑛4) 2+𝑛5 4 Determinemos ahora los valores de 𝑛𝑖: 1. Se debe cumplir que 𝑡0=𝑡7,𝑡2=𝑡5,𝑡1=𝑡4=𝑡6=𝑡3. Una vez fijados 𝑡0,𝑡1y𝑡2, el resto quedan determinados, luego hay 23posibilidades, y por tanto 𝑛1= 8. 2. 2. Se debe cumplir que 𝑡0=𝑡7,𝑡4=𝑡6,𝑡2=𝑡5y𝑡1=𝑡3. Tenemos 24= 16 posibilidades, pero eliminando las del caso 1 tenemos 𝑛2= 8 posibilidades. 3. 3. Se debe cumplir que 𝑡0=𝑡7,𝑡1=𝑡6,𝑡2=𝑡5y𝑡3=𝑡4. Tenemos 24= 16 posibilidades, pero eliminando las del caso 1 tenemos 𝑛3= 8 posibilidades. 4. 4. Se debe cumplir que 𝑡1=𝑡4y𝑡3=𝑡6. Tenemos por tanto 26= 64 posibilidades, pero eliminando las del caso 1 tenemos 𝑛4= 64 − 8 = 56 posibilidades. 5. 5. El resto, que son 𝑛5= 256 − 8 − 8 − 8 − 56 = 176. Finalmente, la cantidad de reglas independientes es: 8 + (8 + 8 + 56)∕2 + 176∕4 = 8 + 36 + 44 = 88 Esta demostración se ha extraído de [5]. Definición 2.3. Definimos los siguientes conceptos: Se dice que 𝑞∈𝑆es un estado fijo si 𝑓(𝑞, ..., 𝑞) = 𝑞. Una configuración 𝑐es fija si 𝑐(𝑥) = 𝑞para todo 𝑥∈ℤ𝑑. Una configuración 𝑐es finita si solo un número finito de células no son fijas, es decir, si {𝑥∈ℤ𝑑|𝑐(𝑥)≠𝑞}es finito. 2. autómatas celulares 17 Clase Reglas Clase Reglas 0 255 56 98,185,227 1 127 57 99 2 16,191,247 58 114,163,177 3 17,63,119 60 102,153,195 4 223 62 118,131,145 5 95 72 237 6 20,159,215 73 109 7 21,31,87 74 88,173,229 8 64,239,253 76 205 9 65,111,125 77 - 10 80,175,245 78 92,141,197 11 47,81,117 90 165 12 68,207,221 94 133 13 69,79,93 104 233 14 84,143,213 105 - 15 85 106 120,169,225 18 183 108 201 19 55 110 124,137,193 22 151 122 161 23 - 126 129 24 66,189,231 128 254 25 61,67,103 130 144,190,246 26 82,167,181 132 222 27 39,53,83 134 148,158,214 28 70,157,199 136 192,238,252 29 71 138 174,208,244 30 86,135,149 140 196,206,220 32 251 142 212 33 123 146 182 34 48,187,243 150 - 35 49,59,115 152 188,194,230 36 219 154 166,180,210 37 91 156 198 38 52,155,211 160 250 40 96,235,249 162 176,186,242 41 97,107,121 164 218 42 112,171,241 168 224,234,248 43 113 170 240 44 100,203,217 172 202,216,228 45 75,89,101 178 - 46 116,139,209 184 226 50 179 200 236 51 - 204 - 54 147 232 - Cuadro 2.1: Tabla de clases independientes 24 análisis de sistemas complejos usando machine learning los autómatas celulares a partir de una regla y una configuración inicial), utilizaremos fundamentalmente algoritmos de aprendizaje supervisado, aunque también podrían utilizarse algunos de aprendizaje no supervisado para reconocer, por ejemplo, clasificaciones interesantes entre las familias y clasificaciones de autómatas que vimos en el capítulo anterior. En este capítulo se explicarán los fundamentos de los distintos algoritmos de aprendizaje que aplicaremos más adelante a los autómatas celulares. El contenido de este capítulo no intenta ser, ni mucho menos, exhaustivo, sino que se proporciona únicamente con el fin de acotar el contexto de ML del que haremos uso a lo largo del resto del trabajo, así como la notación usada. En las referencias que se proporcionan a lo largo de las siguientes secciones se puede encontrar direcciones para quien desee disponer de un desarrollo más amplio de los temas aquí tratados. En los experimentos concretos que haremos en capítulos sucesivos, se hará uso de las implementaciones de los algoritmos señalados que vienen en la librería de código libre scikit-learn para Python. 3.2 Aproximación Matemática al Aprendizaje Automático El objetivo de esta sección es doble: formalizar nuestro modelo de aprendizaje, y probar bajo qué condiciones nuestros algoritmos nos proveerán de soluciones aproximadas lo suficientemente buenas. El primer objetivo es definir un modelo formal de aprendizaje en el que basar los algoritmos que se estudiarán más tarde. Un modelo formal es el siguiente, el cual se encuentra en [8]: Definición 3.1 (Modelo formal de aprendizaje estadístico). Nuestros algoritmos se definen mediante los siguientes elementos: Entrada del algoritmo: –Dominio: Un conjunto arbitrario, . Este es el conjunto de objetos que deseamos etiquetar. Normalmente, cada elemento de representa un vector de características. –Conjunto de etiquetas: Un conjunto con el que se pueden etiquetar cada uno de los elementos del dominio. Normalmente = {0,1}, aunque puede tomar otros 3. machine learning 25 valores. –Conjunto de entrenamiento: 𝑆=((𝑥1, 𝑦1), ..., (𝑥𝑚, 𝑦𝑚))es una secuencia de pares de 𝑥. Esto es, es una secuencia de puntos del dominio ya etiquetados. Estos son los datos de entrada a los que tiene acceso nuestro algoritmo de aprendizaje. Salida del algoritmo: El algoritmo debe devolver un predictor, ℎ∶→. Esta función puede usarse para etiquetar nuevos puntos del dominio. Denotaremos 𝐴(𝑆)al predictor que devuelve el algoritmo 𝐴tras entrenarlo con el conjunto de entrenamiento 𝑆. Un modelo de generación de datos: Se asume en primer lugar que los elementos del dominio están generados por alguna distribución de probabilidad. Denotamos la distribución sobre por . Asumimos también que existe una función de etiquetado "correcta", es decir, una función 𝑓∶→de modo que 𝑦𝑖=𝑓(𝑥𝑖) para cada 𝑖. Es importante observar que no es necesario que ni 𝑓sean conocidos por el algoritmo (de hecho, 𝑓es lo que se pretende averiguar). Medida de error: Definimos el error de un predictor como la probabilidad de que, para un elemento de , el predictor no sea capaz de determinar correctamente su etiqueta. Formalmente, dado 𝐴 ⊂ , la distribución asigna un número (𝐴), el cual determina la probabilidad de observar un punto 𝑥∈𝐴. Se define el error de un predictor ℎ∶→como: 𝐿,𝑓 (ℎ)=ℙ𝑥∼[ℎ(𝑥)≠𝑓(𝑥)]=({𝑥∶ℎ(𝑥)≠𝑓(𝑥)}) Debido a que normalmente no se conocen ni 𝑓, el verdadero error no puede calcularse. Por este motivo, se buscará minimizar el error empírico, que se puede medir de varias formas, aunque la forma más corriente sea: 𝐿𝑆(ℎ) = |{𝑖∈ [𝑚] ∶ ℎ(𝑥𝑖)≠𝑦𝑖}| 𝑚 con [𝑚]=1, .., 𝑚 Definición 3.2 (ERM). Se llama Minimización de Error Empírico (en inglés, ERM: Empirical Risk Minimization), al paradigma de aprendizaje basado en encontrar un predictor ℎ𝑆que minimice 𝐿𝑆(ℎ). Aunque el paradigma ERM parece natural, si no se tiene cuidado pueden darse situaciones en las que nuestros algoritmos fallen. Una de estas situaciones es que se de sobreajuste, o overfitting en inglés. 26 análisis de sistemas complejos usando machine learning El sobreajuste se da cuando nuestro algoritmo aprende demasiado bien los datos del conjunto de entrenamiento, y se ajusta tanto a ellos que no predice correctamente el comportamiento del resto de elementos del dominio. Por ejemplo, el predictor: ℎ𝑆(𝑥)=⎧ ⎪ ⎨ ⎪ ⎩ 𝑦𝑖𝑠𝑖 ∃𝑖∈ [𝑚] ∶ 𝑥𝑖=𝑥 0𝑐𝑐 cumple que 𝐿𝑆(ℎ𝑆)= 0, pero su predicción del resto del dominio será bastante pobre. En [8] se prueba que si tomamos una clase de predictores finita a la que restringir la búsqueda de predictores para nuestro algoritmo y un conjunto de entrenamiento lo suficientemente grande, entonces el predictor que obtenemos es probablemente correcto (como aproximación). La importancia de este hecho reside en que cualquier predictor que podamos programar en un computador está limitado por un número de bytes dado por el computador. Esto hace que nuestra clase de funciones sea finita, y por tanto se apliquen estos resultados. Con esta idea en mente, definimos el siguiente tipo de aprendizaje: Definición 3.3 (Supuesto de realización). Una clase de hipótesis cumple el supuesto de realización si para algún ℎ∈, se tiene que 𝐿(,𝑓)(ℎ)=0. Definición 3.4 (Aprendizaje PAC). Una clase de hipótesis es PAC (Probably Approximately Correct) aprendible si existe una función 𝑚∶ (0,1)2→ℕy un algoritmo de aprendizaje con la siguiente propiedad: Para cada 𝜖, 𝛿 ∈ (0,1), para cada distribución sobre , y para cada función de etiquetado 𝑓∶→0,1, si se cumple el supuesto de realización respecto a ,, 𝑓, entonces cuando se ejecuta el algoritmo sobre 𝑚≥𝑚(𝜖, 𝛿)ejemplos i.i.d. por y etiquetados por 𝑓, entonces el algoritmo devuelve un predictor ℎtal que, con probabilidad al menos 1 − 𝛿sobre la elección de los ejemplos, cumple que: 𝐿(,𝑓)(ℎ)≤𝜖 Proposición 3.1.Toda clase finita de hipótesis es PAC aprendible con 𝑚(𝜖, 𝛿)≤⌈𝑙𝑜𝑔 (||∕𝛿) 𝜖⌉ 3. machine learning 27 Demostración. Se encuentra en [8]. Llegados a este punto, es interesante estudiar qué ocurre cuando eliminamos alguna de las condiciones. Por ejemplo, ¿qué ocurre al eliminar el supuesto de realización? Definición 3.5 (Aprendizaje PAC agnóstico). Una clase de hipótesis es PAC agnóstica aprendible si existe una función 𝑚∶ (0,1)2→ℕy un algoritmo de aprendizaje con la siguiente propiedad: Para todos 𝜖, 𝛿 ∈ (0,1) y para cada distribución sobre 𝑍, cuando se ejecuta el algoritmo de aprendizaje sobre 𝑚≥𝑚(𝜖, 𝛿)ejemplos i.i.d. generados por , el algoritmo devuelve ℎ∈tal que, con probabilidad al menos 1 − 𝛿sobre la elección de los 𝑚 ejemplos de entrenamiento, se tiene que: 𝐿(ℎ)≤𝑚𝑖𝑛ℎ′∈𝐿(ℎ′) + 𝜖 Esto nos indica que, en caso de que no se cumpla el supuesto de realización, entonces no podremos garantizar que nuestro algoritmo de aprendizaje tenga un error arbitrariamente pequeño, pero sí podemos garantizar que el error de este no sea muy grande en comparación al mejor predictor que podemos obtener. Hasta este momento hemos usado la función de error 𝐿que consideramos al principio. Sin embargo, el aprendizaje PAC agnóstico puede generalizarse a cualquier función que mida el error. Definición 3.6 (Funciones de error). Sea una familia de predictores y 𝑍un dominio. Llamamos función de error (loss function) a cualquier función 𝓁∶𝑥𝑍 → ℝ+. Algunos ejemplos de funciones de error son: Error 0-1: Para esta función 𝑍=𝑥, y se tiene que: 𝓁(ℎ, (𝑥, 𝑦)) =⎧ ⎪ ⎨ ⎪ ⎩ 0𝑠𝑖 ℎ(𝑥) = 𝑦 1𝑠𝑖 ℎ(𝑥)≠𝑦 Error cuadrático: Para esta función 𝑍=𝑥, y se tiene que: 𝓁(ℎ, (𝑥, 𝑦)) =(ℎ(𝑥) − 𝑦)2 28 análisis de sistemas complejos usando machine learning Definición 3.7 (Aprendizaje PAC agnóstico generalizado). Una clase de predictores es PAC agnóstica aprendible respecto a un conjunto 𝑍y a una función de error 𝓁∶𝑥𝑍 →ℝ+, si existe una función 𝑚∶ (0,1)2→ℕy un algoritmo de aprendizaje con la siguiente propiedad: Para cada 𝜖, 𝛿 ∈ (0,1) y cada distribución sobre 𝑍, cuando se ejecuta el algoritmo sobre 𝑚≥𝑚(𝜖, 𝛿)i.i.d. ejemplos generados por , el algoritmo devuelve ℎ∈tal que, con probabilidad al menos 1−𝛿sobre la elección de los 𝑚ejemplos de entrenamiento, es 𝐿(ℎ)≤𝑚𝑖𝑛ℎ′∈𝐿(ℎ′) + 𝜖 donde 𝐿(ℎ) = 𝔼𝑧∼[𝓁(ℎ, 𝑧)]. Una vez presentados los fundamentos anteriores, existe una pregunta fundamental que surge de manera natural: ¿existe un algoritmo de aprendizaje universal? Es decir, ¿existe un algoritmo de aprendizaje que pueda aprender bien cualquier problema? La respuesta, como era de esperar, es que no. Esto queda probado por el teorema No-free- lunch que enunciamos a continuación: Teorema 3.1 (No-free-lunch). Sea 𝐴un algoritmo de aprendizaje cualquiera para la tarea de clasificación binaria respecto al error 0-1 sobre un dominio . Sea 𝑚un número menor que ||∕2, el cual representa el tamaño de un conjunto de entrenamiento. Entonces existe una distribución sobre 𝑥{0,1} tal que: 1. Existe una función 𝑓∶→{0,1} tal que 𝐿(𝑓)=0 2. Con probabilidad al menos 1/7 sobre la elección de 𝑆∼𝑚se tiene que: 𝐿(𝐴(𝑆)) ≥1∕8 Demostración. Una prueba de este teorema se encuentra en [8]. Este resultado implica que, para cada aprendiz, existe una tarea para la que fracasa al intentar aprenderla, aunque probablemente exista otro aprendiz que sea capaz de aprenderla sin problemas. Nos enfrentamos ahora a un nuevo problema: ¿Cómo podemos elegir una clase de predictores que nos permita prevenir estos fallos? Nos enfrentamos además a la siguiente proposición: Proposición 3.2.Sea un conjunto infinito y la clase de funciones que van de  a{0,1}. Entonces no es PAC aprendible. 3. machine learning 29 Por tanto, no podremos tomar clases de predictores demasiado ricas. La solución la encontramos en el llamado bias-complexity tradeoff. Definición 3.8 (Bias-complexity tradeoff). El error de un predictor ERMse puede descomponer en dos componentes como sigue: Sea ℎ𝑆una hipótesis ERM. Entonces se puede escribir: 𝐿=𝜖𝑎𝑝𝑝 +𝜖𝑒𝑠𝑡 donde 𝜖𝑎𝑝𝑝 =𝑚𝑖𝑛ℎ∈𝐿(ℎ)es el error de aproximación, y 𝜖𝑒𝑠𝑡 =𝐿(ℎ𝑆)−𝜖𝑎𝑝𝑝 es el error de estimación: Error de aproximación: Es el menor error que puede lograr un predictor de una clase de hipótesis. Este término mide cuál es el error que cometemos al ajustarnos a una clase de hipótesis específica. Agrandar la clase de hipótesis puede reducir el error de aproximación. Error de estimación: El error de estimación resulta de que el error empírico es sólo una estimación del error real. La calidad de esta estimación depende del tamaño del conjunto de entrenamiento, y de la complejidad de la clase de hipótesis. Como nuestra intención es minimizar el error total, nos enfrentamos a un equilibrio entre ambos errores. Por una parte, enriquecer la clase puede decrecer el error de aproximación pero incrementar el error de estimación, ya que una clase rica puede llevar a que se produzca un sobreajuste. Por otra parte, si tomamos demasiado pequeño, incrementamos el error de aproximación pero decrece el error de estimación. 3.3 Algoritmos En esta sección se describen los algoritmos que se aplicarán más adelante a los datos de los autómatas celulares. La definición de estos algoritmos se ha obtenido de [8] y de [9]. 3.3.1 Predictores lineales Comenzaremos presentando la familia de los predictores lineales, que se clasifica dentro del aprendizaje supervisado. Es una de las familias más útiles, y muchos algoritmos de aprendizaje los utilizan. Los predictores lineales son intuitivos, fáciles de 30 análisis de sistemas complejos usando machine learning interpretar, y ajustan los datos razonablemente bien en muchos problemas de aprendizaje. Definición 3.9. Se define como 𝐿𝑑= {ℎ𝑤,𝑏 ∶𝑤∈ℝ𝑑, 𝑏 ∈ℝ}a la clase de funciones lineales afines ℎ∶ℝ𝑑→ℝ, de modo que ℎ𝑤,𝑏(𝑥) = ⟨𝑤, 𝑥⟩+𝑏=(∑𝑑 𝑖=1 𝑤𝑖𝑥𝑖)+𝑏. Lema 3.1.Cualquier función lineal afín de ℝ𝑑puede convertirse en una función lineal homogénea de ℝ𝑑+1. Demostración. Definimos 𝑤′=(𝑏, 𝑤1, ..., 𝑤𝑑)∈ℝ𝑑+1 y𝑥′=(1, 𝑥1, 𝑥2, ..., 𝑥𝑑)∈ ℝ𝑑+1. Entonces se tiene que ℎ𝑤,𝑏(𝑥) = ⟨𝑤, 𝑥⟩+𝑏=⟨𝑤′, 𝑥′⟩. Definición 3.10. Se define a la clase de los semiespacios como el conjunto 𝐻𝑆𝑑= 𝑠𝑖𝑔𝑛 ◦𝐿𝑑= {𝑥→ 𝑠𝑖𝑔𝑛 (ℎ𝑤,𝑏(𝑥))∶ℎ𝑤,𝑏 ∈𝐿𝑑}. Esta clase está diseñada para problemas de clasificación binaria. Algoritmo 3.1 (Mínimos cuadrados). Mínimos cuadrados es el algoritmo que resuelve el problema ERM para la clase de hipótesis de los predictores de regresión lineales respecto del error cuadrático medio. El problema ERM, dado un conjunto de entrenamien- to 𝑆y usando la versión homogénea de 𝐿𝑑, es encontrar (Figura 3.3): 𝑎𝑟𝑔𝑚𝑖𝑛𝑤𝐿𝑆(ℎ𝑤)=𝑎𝑟𝑔𝑚𝑖𝑛𝑤 1 𝑚 𝑚 ∑ 𝑖=1 (⟨𝑤, 𝑥𝑖⟩−𝑦𝑖)2 Para resolverlo se calcula el gradiente de la función objetivo y se compara con cero. Es decir, hay que resolver: 2 𝑚 𝑚 ∑ 𝑖=1 (⟨𝑤, 𝑥𝑖⟩−𝑦𝑖)𝑥𝑖= 0 Podemos reescribirlo como el problema 𝐴𝑤 =𝑏donde 𝐴=(𝑚 ∑ 𝑖=1 𝑥𝑖𝑥𝑇 𝑖) 𝑏= 𝑚 ∑ 𝑖=1 𝑦𝑖𝑥𝑖 Si 𝐴es invertible, entonces la solución al problema ERM es 𝑤=𝐴−1𝑏 3. machine learning 31 Figura 3.3: Ejemplo de regresión por mínimos cuadrados. Imagen extraída de [9] En caso de que 𝐴no sea invertible, se pueden usar herramientas de álgebra lineal para encontrar 𝐴=𝑃 𝐷𝑃 𝑇, con 𝐷una matriz diagonal y 𝑃una matriz ortogonal. Se define entonces 𝐴+=𝑃 𝐷+𝑃𝑇con : 𝐷+ 𝑖,𝑖 ={0, si 𝐷𝑖,𝑖 = 0 1∕𝐷𝑖,𝑖 , en otro caso Entonces, si  𝑤=𝐴+𝑏, se tiene que: 𝐴 𝑤=𝐴𝐴+𝑏=𝑉 𝐷𝑉 𝑇𝑉 𝐷+𝑉𝑇𝑏=𝑉 𝐷𝐷+𝑉𝑇𝑏=∑ 𝑖∶𝐷𝑖,𝑖≠0 𝑣𝑖𝑣𝑇 𝑖𝑏 Como 𝐴 𝑤es la proyección de 𝑏en el subespacio generado por los 𝑣𝑖para los cuales 𝐷𝑖,𝑖 ≠0, y este subespacio es el mismo que el generado por los 𝑥𝑖, se tiene que 𝐴 𝑤=𝑏. Existen variantes interesantes de este algoritmo que imponen restricciones adicionales para acotar el espacio de soluciones resultante. Por ejemplo, los dos que nombramos a continuación: Algoritmo 3.2 (Regresión de arista). La regresión de arista es otro modelo lineal de regresión en el que se usa también el error cuadrático medio. Sin embargo, en este caso los coeficientes (𝑤) intentan minimizarse lo máximo posible. Esto se puede conseguir, por ejemplo, penalizando aquellas soluciones que proporcionen una norma L2 de los coeficientes demasiado elevada. La penalización se controlará con un parámetro 𝐶, que en el caso 𝐶= 0 resultará en el mismo método de mínimos cuadrados visto anteriormente. 32 análisis de sistemas complejos usando machine learning Figura 3.4: Ejemplos de regresión de arista con distintas C. Imagen extraída de [9] Los efectos del parámetro 𝐶pueden observarse en la figura 3.4, que muestra que cuanto más grande es 𝐶, más trata de ajustarse a los datos. Algoritmo 3.3 (Lasso). Lasso es una alternativa a la regresión de arista. Es idéntico, salvo porque minimizará la norma L1 de los coeficientes en lugar de la norma L2. El hecho de usar L1 en vez de L2 hará que algunos coeficientes puedan llegar a ser exactamente 0, lo que se traducirá en que algunas de las características del modelo se ignorarán completamente. Las consecuencias son modelos más simples pero que muestran cuáles son las características más importantes en los datos de entrada. Nota 3.1.Estos modelos pueden usarse como modelos de clasificación binaria. En este caso, la predicción se realizará usando la siguiente fórmula: 𝑦=⟨𝑤, 𝑥⟩+𝑏 > 0 De esta forma, si el resultado es mayor que 0, entonces se asignará la clase 1, y si es menor que 0, se asignará la clase -1. Los dos algoritmos lineales de clasificación más comunes son la regresión logística y las máquinas de soporte vectorial lineales. Las máquinas de soporte vectorial se explicarán en el correspondiente apartado más adelante. Algoritmo 3.4 (Regresión logística). La regresión logística utiliza una función sigmoidea para aprender una serie de funciones ℎde ℝ𝑑en el intervalo [0,1]. La clase de hipótesis asociada es la composición de dicha sigmoidea con la clase 𝐿𝑑. En particular, se usa la función logística, definida como: 𝜙𝑠𝑖𝑔(𝑧) = 1 1 + 𝑒−𝑧 3. machine learning 33 La clase de hipótesis es, por tanto: 𝐻𝑠𝑖𝑔 =𝜙𝑠𝑖𝑔◦𝐿𝑑= {𝑥→𝜙𝑠𝑖𝑔 (⟨𝑤, 𝑥⟩)∶𝑤∈ℝ𝑑} El problema ERM asociado con la regresión logística se traduce en: 𝑎𝑟𝑔𝑚𝑖𝑛𝑤∈ℝ𝑑 1 𝑚 𝑚 ∑ 𝑖=1 𝑙𝑜𝑔 (1 + 𝑒−𝑦𝑖⟨𝑤,𝑥𝑖⟩) 3.3.2 k-Vecinos más cercanos Este algoritmo es, quizás, el más simple de todos los algoritmos de aprendizaje automático de clasificación que vamos a considerar, pero ofrece resultados razonablemente buenos en muchos casos en los que, incluso, algoritmos más complejos se encuentran con problemas. Para construir este modelo sólo hace falta almacenar los datos del conjunto de entrenamiento y elegir cuántos vecinos se considerarán en su vecindario. Algoritmo 3.5. Sea 𝑆= {(𝑥𝑖, 𝑦𝑖) ∶ 𝑖∈𝐷}un conjunto de entrenamiento, donde 𝑆𝑥= {𝑥𝑖∶𝑖∈𝐷}son puntos de un espacio métrico, e 𝑦𝑖es la clasificación asociada a cada uno de ellos. Para clasificar un nuevo dato 𝑥se calculan los 𝑘puntos de 𝑆𝑥más cercanos a 𝑥, y se le asigna a 𝑥la clase más representada entre esos 𝑘puntos. En la figura 3.5 se muestra un ejemplo de aplicación de este algoritmo para 𝑘= 3. En el caso de clasificación binaria, es habitual considerar 𝑘impar para evitar empates en la asignación de clases. 40 análisis de sistemas complejos usando machine learning Figura 3.9: Intuitivamente, sabemos que la línea negra es mejor predictor que la línea verde. Imagen extraída de [8] 3.3.5 Máquinas de soporte vectorial El objetivo de esta sección es hallar predictores lineales en espacios de dimensiones más grandes, y reducir el error derivado del conjunto de entrenamiento, así como la complejidad computacional. La idea principal es encontrar los predictores que dejen mayor margen de error a las muestras del conjunto de entrenamiento. Por ejemplo, en la figura 3.9 vemos que, aunque tanto la línea negra como la línea verde separan bien las cuatro muestras para clasificarlas, intuitivamente pensaremos que es mejor la línea negra. Formalmente, lo que se busca es resolver el siguiente problema, llamado Hard-SVM: 𝑎𝑟𝑔𝑚𝑎𝑥(𝑤,𝑏)∶||𝑤||=1𝑚𝑖𝑛𝑖∈[𝑚]|⟨𝑤, 𝑥𝑖⟩+𝑏| tal que ∀𝑖, 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)>0. Proposición 3.3.Si existe una solución del problema anterior, entonces este es equivalente a: 𝑎𝑟𝑔𝑚𝑎𝑥(𝑤,𝑏)∶||𝑤||=1𝑚𝑖𝑛𝑖∈[𝑚]𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏) Llamaremos 𝛾𝑖a𝑚𝑖𝑛𝑖∈[𝑚]𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏). 3. machine learning 41 Una formulación equivalente como un problema de optimización cuadrática es la siguiente: 𝑎𝑟𝑔𝑚𝑖𝑛(𝑤,𝑏)||𝑤||2∶ ∀𝑖, 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)≥1 Nota 3.2.A veces será más conveniente trabajar con semiespacios homogéneos. Como vimos al principio de la sección de predictores lineales, podemos convertir el problema anterior en uno homogéneo equivalente: 𝑚𝑖𝑛𝑤||𝑤||2∶ ∀𝑖, 𝑦𝑖⟨𝑤, 𝑥𝑖⟩≥1 Definición 3.13 (Soft-SVM). A veces no se cumplirá la condición 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)≥ 1para algún 𝑖, por lo que introduciremos una versión, llamada Soft-SVM, que suaviza esta restricción introduciendo nuevos parámetros: 𝑚𝑖𝑛𝑤,𝑏,𝜁 (𝜆||𝑤||2+1 𝑚 𝑚 ∑ 𝑖=1 𝜁𝑖) tal que ∀𝑖, 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)≥1 − 𝜁𝑖y𝜁𝑖≥0. El parámetro 𝜆servirá para controlar el equilibrio entre la norma de 𝑤y lo que se relajan las restricciones. En ocasiones no podremos clasificar los datos usando predictores lineales, pero existirán inmersiones que trasladen los datos a espacios de dimensión superior, y en estos sí podremos clasificarlos sin problemas. El coste computacional aumenta a cambio de obtener mayor precisión. El espacio que se obtiene de la inmersión puede ser de dimensión infinita. Un ejemplo visual de lo que se pretende conseguir se encuentra en la figura 3.10. Definición 3.14 (El truco del núcleo). Dada una inmersión 𝜓de un espacio en un espacio de Hilbert, definimos la función núcleo 𝐾(𝑥, 𝑥′) = ⟨𝜓(𝑥), 𝜓(𝑥′)⟩. Algoritmo 3.9 (Máquinas de soporte vectorial lineales con núcleos). El objetivo será resolver el problema 𝑚𝑖𝑛𝑤(𝜆 2||𝑤||2+1 𝑚 𝑚 ∑ 𝑖=1 𝑚𝑎𝑥{0,1 − 𝑦⟨𝑤, 𝜓 (𝑥𝑖)⟩}) . Entrada: Conjunto de entrenamiento 𝑆= {𝑥𝑖, 𝑦𝑖}𝑚 𝑖=1 Número de rondas T 42 análisis de sistemas complejos usando machine learning Figura 3.10: Inmersión de los datos en un espacio de dimensión superior para encontrar un mejor predictor usando SVM. Imagenes extraídas de [9] 3. machine learning 43 Salida:  𝑤=∑𝑚 𝑗=1 𝛼𝑗𝜓(𝑥𝑗)con 𝛼 =1 𝑇∑𝑇 𝑡=1 𝛼(𝑡) Inicializar: 𝛽(1) = 0 para 𝑡= 1,2..., 𝑇 hacer Determinar 𝛼(𝑡)=1 𝜆𝑡 𝛽(𝑡) Elegir 𝑖uniformemente en {1, ..., 𝑚} Para todo 𝑗≠𝑖establecer 𝛽(𝑡+1) 𝑗=𝛽(𝑡) 𝑗 si 𝑦𝑖∑𝑚 𝑗=1 𝛼(𝑡) 𝑗𝐾(𝑥𝑗, 𝑥𝑖)<1entonces Establecer 𝛽(𝑡+1) 𝑖=𝛽(𝑡) 𝑖+𝑦𝑖 si no Establecer 𝛽(𝑡+1) 𝑖=𝛽(𝑡) 𝑖 fin si fin para Nota 3.3.Para las aproximaciones experimentales que se muestran en el capítulo siguiente usaremos el algoritmo SVC de la librería sklearn, que incluye un parámetro 𝐶 en lugar del parámetro 𝜆que encontramos en el algoritmo con las siguientes diferencias: multiplica el argumento a minimizar por 1 𝜆, y luego realiza el cambio 𝐶=1 𝜆⋅𝑚. Las soluciones que se obtienen de la minimización siguen siendo las mismas, pero ahora la constante por la que multiplica es 𝐶. 3.3.6 Multiclases A veces existirán etiquetas que no sean binarias, es decir, existirá un conjunto fini- to de posibles etiquetas con más de dos elementos. Para encontrar un predictor que permita realizar la clasificación deseada dispondremos de varios algoritmos: A partir de este momento tomaremos 𝑆= {𝑥𝑖, 𝑦𝑖}𝑚 𝑖=1 un conjunto de entrenamiento tal que 𝑦𝑖∈= {1, ..., 𝑘}∀𝑖sin pérdida de generalidad. Algoritmo 3.10 (Uno contra todos). La idea de este algoritmo será encontrar k predictores lineales, uno por cada categoría, y realizar la clasificación de 𝑥aplicando 𝑎𝑟𝑔𝑚𝑎𝑥 𝑖∈[𝑘] ℎ𝑖(𝑥). En caso de que haya empate, entonces se tomará uno fijado previamente (por ejemplo, el que tenga menor 𝑖). Entrada: Conjunto S Algoritmo de clasificación binaria A para todo 𝑖∈hacer Establecer 𝑆𝑖= (𝑥1,(−1)𝟙[𝑦1≠𝑖]), ..., (𝑥𝑚,(−1)𝟙[𝑦𝑚≠𝑖]) 44 análisis de sistemas complejos usando machine learning Establecer ℎ𝑖=𝐴(𝑆𝑖) fin para Salida: ℎ(𝑥) ∈ 𝑎𝑟𝑔𝑚𝑎𝑥 𝑖∈ ℎ𝑖(𝑥) Algoritmo 3.11 (Todos los pares). La idea de este algoritmo será comparar parejas de clases. Formalmente, tomaremos para cada 1≤𝑖 < 𝑗 ≤𝑘una secuencia 𝑆𝑖,𝑗 que contendrá a todos los elementos de 𝑆tales que su etiqueta es 𝑖o𝑗. Cada elemento de 𝑆𝑖,𝑗 lo etiquetaremos con +1 si su etiqueta es 𝑖y con -1 si su etiqueta es 𝑗. Luego conseguiremos un predictor binario ℎ𝑖,𝑗 para cada 𝑆𝑖,𝑗, y construiremos el predictor encontrando la clase que tiene mayor cantidad de "victorias". Entrada: Conjunto S Algoritmo de clasificación binaria A para todo 𝑖, 𝑗 ∈tal que 𝑖<𝑗hacer Inicializar 𝑆𝑖,𝑗 como un conjunto vacío. para 𝑡= 1, ..., 𝑚 hacer Si 𝑦𝑡=𝑖, añadir (𝑥𝑡,1) a𝑆𝑖,𝑗. Si 𝑦𝑡=𝑗, añadir (𝑥𝑡,−1) a𝑆𝑖,𝑗. fin para Establecer ℎ𝑖,𝑗 =𝐴(𝑆𝑖,𝑗 ) fin para Salida: ℎ(𝑥) ∈ 𝑎𝑟𝑔𝑚𝑎𝑥 𝑖∈∑𝑗∈𝑠𝑖𝑔𝑛 (𝑗−𝑖)ℎ𝑖,𝑗 (𝑥) Nota 3.4.Todos los algoritmos que usaremos, cuando sean aplicadas a clasificaciones multiclase, utilizarán el algoritmo de Todos los pares. 3.3.7 Redes neuronales En este apartado trabajaremos sobre modelos que imitan el comportamiento de las redes neuronales reales. Utilizaremos grafos dirigidos que no contengan ciclos, y cuyos vértices podremos separar en capas según los vértices a los que estén conectados. Sea 𝐺= (𝑉 , 𝐸)un grafo dirigido sin ciclos y 𝑤∶𝐸→ℝuna función peso definida sobre las aristas. Cada vértice se corresponde con una neurona de nuestra red neuronal. Podemos expresar 𝑉=⋃𝑇 𝑡=0 𝑉𝑡como unión disjunta, de modo que cada arista de 𝐸conecta un vértice de 𝑉𝑡−1 con un vértice de 𝑉𝑡. Las neuronas de 𝑉0tienen como salida los 𝑥𝑖a excepción de la última, que tiene salida constante 1. 3. machine learning 45 Un esquema de una red neuronal con una capa oculta es el de la figura 3.11. En ella vemos que la capa de entrada tiene tres neuronas, la oculta tiene tres, y la de salida tiene dos. Figura 3.11: Esquema de Red Neuronal. Recuperada de es.wikipedia.org Sea 𝑣𝑡+1,𝑗 ∈𝑉𝑡+1 una neurona de la capa 𝑉𝑡+1 y𝑜𝑡,𝑖(𝑥)la salida de la neurona 𝑣𝑡,𝑖. Entonces el valor que recibe como entrada dicha neurona es: ∑ 𝑟∶(𝑣𝑡,𝑟,𝑣𝑡+1,𝑗 )∈𝐸 𝑤((𝑣𝑡,𝑟, 𝑣𝑡+1,𝑗 ))𝑜𝑡,𝑟(𝑥) Para calcular el valor que se utiliza como salida se aplica a dicho valor la función 𝜎, que normalmente es la función signo, una función umbral o la sigmoidea, que es buena aproximación de la umbral y además es derivable (algo fundamental para los procesos de ajuste que veremos después). A la capa 𝑉0se le llama capa de entrada, a la capa 𝑉𝑇capa de salida, y al resto capas ocultas. Para modificar la función peso utilizaremos el algoritmo Backpropagation, que es un algoritmo optimización de la familia de Gradiente Descendiente y hará que obtengamos un buen predictor respecto a los datos de entrada. Algoritmo 3.12 (SGD para redes neuronales). Dada una distribución sobre ×: Parámetros: Número de iteraciones 𝜏 Secuencia de longitudes de paso: 𝜂1, ..., 𝜂𝜏 Parámetro de regularización 𝜆 > 0 Entrada: 46 análisis de sistemas complejos usando machine learning Grafo etiquetado (𝑉 , 𝐸) Función de activación diferenciable 𝜎∶ℝ→ℝ Inicializar 𝑤(1) ∈ℝ|𝐸|al azar de una distribución tal que esté cerca del 0. para t=1,...,𝜏hacer Tomar elemento (𝑥, 𝑦) ∼  Calcular el gradiente 𝑣𝑖=backpropagation(x,y,w,(𝑉 , 𝐸), 𝜎) Actualizar 𝑤(𝑖+1) =𝑤(𝑖)−𝜂𝑖(𝑣𝑖+𝜆𝑤(𝑖)) fin para Salida:  𝑤es el 𝑤(𝑖)con mejor rendimiento en un conjunto de validación El algoritmo de backpropagation se define como: Entrada: Ejemplo (𝑥, 𝑦), vector de pesos 𝑤, grafo etiquetado (𝑉 , 𝐸), función de activación 𝜎∶ℝ→ℝ Inicializar: Denotar las capas del grafo 𝑉0, ..., 𝑉𝑇con 𝑉𝑡=𝑣𝑡,1, ..., 𝑣𝑡,𝑘𝑡 Definir 𝑊𝑡,𝑖,𝑗 como el peso de la arista (𝑣𝑡,𝑗 , 𝑣𝑡+1,𝑖). Si la arista no existe se define como 0. Hacia delante: Establecer 𝑜0=𝑥 para 𝑡= 1, ...𝑇 hacer para 𝑖= 1, ..., 𝑘𝑡hacer Establecer 𝑎𝑡,𝑖 =∑𝑘𝑡−1 𝑗=1 𝑊𝑡−1,𝑖,𝑗𝑜𝑡−1,𝑗 Establecer 𝑜𝑡,𝑖 =𝜎(𝑎𝑡,𝑖) fin para fin para Hacia atrás: Establecer 𝛿𝑇=𝑜𝑇−𝑦 para 𝑡=𝑇− 1, ..., 1hacer para 𝑖= 1, ..., 𝑘𝑡hacer 𝛿𝑡,𝑖 =∑𝑘𝑡+1 𝑗=1 𝑊𝑡,𝑗,𝑖𝛿𝑡+1,𝑗𝜎′(𝑎𝑡+1,𝑗 ) fin para fin para Salida: Para cada arista (𝑣𝑡−1,𝑗, 𝑣𝑡,𝑖) ∈ 𝐸devolver 𝛿𝑡,𝑖𝜎′(𝑎𝑡,𝑖)𝑜𝑡−1,𝑗 Además de las redes neuronales descritas, también llamadas Redes Neuronales Artificiales, o ANN por sus siglas en inglés, existen algunas variantes, como las redes neuronales convolucionales, o CNN, las cuales están especializadas en el reconoci- 3. machine learning 47 miento de imágenes, y que, a pesar de ser de gran interés para la evolución actual de las redes neuronales y de su uso intensivo en tareas de alta complejidad hoy en día (llegando a evolucionar en un nuevo tipo de Machine Learning conocido como Deep Learning) no presentamos con más detalle al no haber sido utilizadas para este trabajo. En todo caso, el lector puede encontrar más información sobre ellas en [14]. 4 Resultados Experimentales En este capítulo se analizan los resultados obtenidos tras aplicar los algoritmos de aprendizaje anteriormente definidos sobre ciertos autómatas celulares. Las especificaciones se definen en la primera sección, la implementación se trata en la segunda sección, y en la tercera se analizan los datos en sí. Todas las imágenes usadas en este capítulo han sido creadas usando el código desarrollado. Concretamente, las gráficas se han creado usando la librería matplotlib de Python. 4.1 Consideraciones previas Una vez que se han introducido los autómatas celulares y los algoritmos de Machine Learning a utilizar, hay que tomar una serie de decisiones sobre los autómatas que se van a estudiar y los algoritmos que se van a utilizar. Estos parámetros pueden ser modificados en el código. La metodología seguida en la etapa experimental que se ha realizado para este trabajo se puede resumir en los siguientes puntos clave: 4.1.1 Autómatas Celulares – Los autómatas celulares serán unidimensionales y tendrán frontera circular. – De las reglas que los definen, se estudiarán las 88 que no son equivalentes entre sí y que representan las clases de equivalencia que se indicaron en el capítulo correspondiente. 56 análisis de sistemas complejos usando machine learning Figura 4.4: Muestra del código del archivo ArbolDecision (II). la regla 110 casi todos los algoritmos predicen la mayoría con probabilidad casi 1, a pesar de pertenecer a la clase IV, y por tanto tener un comportamiento complejo. Esto significa que los algoritmos están aprendiendo algún patrón subyacente que no se ve a simple vista. Es aquí donde destaca la utilidad de la aproximación realizada ya que, a pesar de ser un comportamiento complejo (no caótico), los algoritmos de ML proporcionan aproximaciones suficientemente buenas a la aproximación de la complejidad. Sin embargo, la utilidad de este aprendizaje podría estar limitado por un hecho muy simple, y es que si la mayoría del autómata varía poco durante su evolución (hay que tener en cuenta que se basa en una medida agregada), entonces no hay extracción de patrones, sino aproximación de un valor prácticamente constante, por lo que el error cometido será bajo. 4.3.2 Aprendizaje local: predicción de una célula Abordamos ahora un problema diferente, que es el de intentar predecir el comportamiento de una sección local de la evolución (a diferencia del experimento anterior, en el que se intentaba predecir una característica global del sistema). En concreto, en este segundo experimento nos planteamos el estudio de hasta qué punto los algoritmos de aprendizaje son capaces de predecir el valor de una de las células del sistema (una en concreto prefijado). Aunque el comportamiento de los autómatas es determinista, y las reglas de evolución de los autómatas considerados son locales (solo dependen de 4. resultados experimentales 57 Figura 4.5: Muestra del código del archivo Graficas. los vecinos), al haber dejado pasar muchos pasos de evolución el valor de cualquiera de las células realmente depende de un radio mucho de mayor de valores de células adyacentes, por lo que el algoritmo no puede simplemente memorizar o aprender una regla local para ser capaz de predecir con ciertas garantías el valor de una célula concreta conociendo únicamente la configuración inicial y el número de pasos. Como estamos tratando el problema de predicción para una célula que puede tomar dos valores, cualquier predicción que supere con un cierto margen el valor de 0.5 estará mostrando un comportamiento de aprendizaje predictivo de patrones. Las figuras (Figura 4.10a a 4.13b) muestran la precisión obtenida por los algoritmos 58 análisis de sistemas complejos usando machine learning (a) Aprendizaje de la regla 0. (b) Aprendizaje de la regla 168. Figura 4.6 cuando han tratado de predecir la primera célula de cada autómata: Como es normal, los algoritmos de aprendizaje utilizados predicen con probabilidad 1 la primera célula del autómata para las reglas 0 (Fig. 4.10a) y 168 (Fig. 4.10b) ya que, como hemos comentado, pertenecen a la clase I de Wolfram y por tanto llegan a estados homogéneos. Considerando los autómatas de la clase II de Wolfram, tenemos que para la regla 14 (Fig. 4.11a) los algoritmos apenas mejoran el azar. Sin embargo, para la regla 108 (Fig. 4.11b) la predicción de la primera célula tiene una precisión de más de 0.8, la cual en sí misma es bastante buena, pero cuando observamos el aspecto (ver 6.5) del autómata, resulta sorprendente que no sean capaces de predecir con precisión casi 1 la primera célula de un autómata que se estabiliza siempre. 4. resultados experimentales 59 (a) Aprendizaje de la regla 14. (b) Aprendizaje de la regla 108. Figura 4.7 (a) Aprendizaje de la regla 30. (b) Aprendizaje de la regla 126. Figura 4.12 De nuevo, la precisión de los algoritmos sobre las reglas 30 (Fig. 4.12a) y 126 (Fig. 4.12b) está en torno a 0.5. es decir, similar al azar. Era lo esperado por ser caóticos (pertenecen a la clase III de Wolfram). 60 análisis de sistemas complejos usando machine learning (a) Aprendizaje de la regla 30. (b) Aprendizaje de la regla 126. Figura 4.8 (a) Aprendizaje de la regla 54. (b) Aprendizaje de la regla 54. Figura 4.13 Respecto a las reglas 54 (Fig. 4.13a) y 110 (Fig. 4.13b), tenemos que las precisiones obtenidas son similares a las de los autómatas de la clase III. Esto concuerda con lo que sabemos de los autómatas complejos: estudiando individualmente cada célula no se localizan patrones, pero estudiando determinados rasgos más generales pueden surgir 4. resultados experimentales 61 (a) Aprendizaje de la regla 54. (b) Aprendizaje de la regla 110. Figura 4.9 propiedades interesantes. 4.3.3 Aprendizaje local: predicción de tres células Vamos a poner condiciones un poco más fuertes para los algoritmos de aprendizaje y estudiar cómo se comportan con un problema de aprendizaje local pero que involucra a un segmento, y no a una sola célula. En este caso, analizaremos la capacidad de predicción de 3 células consecutivas del autómata tras la evolución de 130 pasos. En este caso, convirtiendo el problema en un problema de predicción binario (si es capaz de predecir correctamente las 3 células o no) vemos que una decisión al azar conllevaría una probabilidad de acierto de 1/8 (0.125), por lo que cualquier valor que supere con cierto margen esa cantidad mostraría un aprendizaje significativo. Las figuras (Figura 4.14a a 4.17b) muestran la precisión obtenida por los algoritmos cuando han tratado de predecir las tres primeras células de cada autómata: De nuevo, como se podía intuir, todos los algoritmos predicen con probabilidad 1 las tres primeras células para los autómatas de la clase I de Wolfram: las reglas 0 (Fig. 4.14a) y 168 (Fig. 4.14b). La razón es la misma que antes: al evolucionar siempre al mismo estado homogéneo, los algoritmos aprenden que siempre va a dar el mismo resultado, sin importar la entrada. 62 análisis de sistemas complejos usando machine learning (a) Aprendizaje de la regla 0. (b) Aprendizaje de la regla 168. Figura 4.10 Para las reglas 14 (Fig. 4.15a) y 108 (Fig. 4.15b), ambas de la clase II de Wolfram, las cosas cambian bastante. Aunque antes los algoritmos predecían con probabilidad 1 la mayoría para el autómata 108, ahora la mayoría de algoritmos de aprendizaje predicen las tres primeras casillas con probabilidad en torno a 0.6 (salvo por los árboles de decisión, que alcanzan un pico cercano al 0.9). En comparación al azar, con precisión 0.125, está bastante bien, ya que aumenta la precisión en 0.4 en la mayoría de los casos, y los árboles de decisión aprenden bastante bien el funcionamiento de este autómata. Para la regla 14 los resultados son mucho peores, aunque su predicción mejora el azar: la precisión de los algoritmos está en torno a 0.2. Lo que supone una mejora porcentual considerable. Esto nos indica que, aunque los autómatas de la clase II puedan ser similares en algunos aspectos, en ocasiones encontraremos algunos que sean fáciles de aprender por parte de los algoritmos, y otros que se resistirán a estos. Pasando a los autómatas de la clase III, para la regla 30 (Fig. 4.16a), como era de esperar, la precisión es parecida a la del azar, tal y como pasaba en el caso del problema de la mayoría. Nuestro objetivo no está en la posible predicción de la evolución del autómata en el caso caótico, y no porque sea imposible, sino porque los algoritmos que hemos usado de ML son muy básicos y no son capaces de aprender sin memoria 4. resultados experimentales 63 (a) Aprendizaje de la regla 14. (b) Aprendizaje de la regla 108. Figura 4.11 a partir de una muestra temporal. Para la regla 126 (Fig. 4.16b) podemos observar cierta mejoría: la mayoría de algoritmos tienen una precisión de en torno a 0.2. Aunque es algo mejor que el azar, tampoco nos da resultados significativos. Esto nos permite deducir algo que esperábamos, y es que, debido al caos subyacente a los autómatas de la clase III, las predicciones de los algoritmos de aprendizaje básicos serán bastante pobres cuando nos enfrentemos a dinámicas caóticas. Por último, tanto a la regla 54 (Fig. 4.17a) como a la regla 110 (Fig. 4.17b) les pasa algo similar a los de la clase III de Wolfram: el caos subyacente hace que sea difícil para los algoritmos de aprendizaje predecir las tres primeras células del autómata tras un número fijo de iteraciones, y los resultados no son mucho mejores que los del azar. Reservamos para el último capítulo de la memoria el conjunto de conclusiones que podemos extraer de los experimentos realizados. 4.3.4 Otros experimentos Aunque en las secciones anteriores nos hemos centrado en los métodos de clasificación por la naturaleza de los rasgos estudiados, se podrían realizar otras aproximacio- 64 análisis de sistemas complejos usando machine learning (a) Aprendizaje de la regla 0. (b) Aprendizaje de la regla 168. Figura 4.14 nes que utilizasen métodos de regresión, como puede ser la predicción de la densidad final de los autómatas (al final de los pasos dados). Los experimentos adicionales que indicamos en este apartado se muestran solo a modo de ejemplo, como muestra del tipo de análisis de la complejidad de los autómatas que se puede llevar a cabo, así como de la capacidad predictiva de los algoritmos usados. La densidad de un autómata en una configuración determinada se define como: 𝐷𝑒𝑛𝑠𝑖𝑑𝑎𝑑 =nºde células vivas nºde células Utilizando, por ejemplo, el algoritmo de regresión por mínimos cuadrados se consiguen las precisiones que se ven en la figura 4.18 para los 88 autómatas señalados a lo largo de esta memoria. La implementación del algoritmo de regresión por mínimos cuadrados que hemos usado mide el coeficiente 𝑅2de la aproximación y compara los resultados del algoritmo con el azar. Si el algoritmo es mucho peor, se obtienen valores negativos. Se debe tener en cuenta que existen algoritmos de regresión (por ejemplo, las redes neuronales) que pueden obtener resultados más interesantes que los arrojados por nuestra prueba. Como era de esperar, los resultados de predicción usando esta regresión sobre autómatas mínimamente complejos son muy pobres. 4. resultados experimentales 65 (a) Aprendizaje de la regla 14. (b) Aprendizaje de la regla 108. Figura 4.15 Por otra parte, también es interesante analizar qué ocurre cuando se consideran métricas como la distancia entre las soluciones obtenidas en la predicción de tres células en comparación a la configuración real arrojada por la simulación del autómata. No es lo mismo predecir una de las tres células erróneamente, que predecirlas todas mal. En las figuras 4.19, 4.20, 4.21 y 4.22 se muestran mediciones de la distancia de Levenshtein media entre las predicciones obtenidas y las soluciones reales para los 8 autómatas estudiados (esencialmente, se mira el número de errores que se pueden cometer, que por las características del experimento diseñado, puede varias entre 0 y 3). Obsérvese que, en el caso de estar trabajando con cadenas binarias, la distancia de Levenshtein coincide con la distancia de Manhattan. Teniendo en cuenta que la distancia máxima es 3, en las gráficas indicadas podemos observar resultados similares a los obtenidos con los experimentos anteriores: para los autómatas de la clase I de Wolfram se obtiene una distancia media 0; los de la clase II están uno en torno a 1.5 y el otro muy por debajo (en torno a 0.5); y los de la clase III y IV están en torno a 1.5 debido al comportamiento caótico o complejo. Se podría estudiar intentar optimizar los algoritmos para que penalizaran además la distancia Manhattan, obteniendo así mejores resultados. 72 análisis de sistemas complejos usando machine learning lisis de la complejidad, en este caso representada por la dinámica determinista, pero compleja, de pequeños autómatas. En este sentido, y a pesar de la pobreza de los resultados obtenidos desde un punto de vista experimental, se consideran cumplidos los objetivos planteados y, como debe ser en todo trabajo de iniciación a la investigación, son más interesantes las puertas que abre que las que ha conseguido cerrar. Un apunte extra a considerar es que si comparamos los resultados obtenidos de entrenar algunos algoritmos sobre todas las reglas, con los obtenidos de entrenar otros algoritmos sobre las mismas reglas, a veces unos obtienen resultados mejores que los otros y otras veces es al revés. Por ejemplo, se muestra a continuación la comparación entre los resultados obtenidos por los árboles de decisión y los obtenidos por las redes neuronales (Fig. 5.1). En un momento de auge de las redes neuronales, y a pesar de ser modelos mucho más flexibles para muchísimos de los problemas planteados en Inteligencia Artificial, parece mostrarse aquí una versión local del Teorema No-Free- Lunch, en el que no hay un algoritmo de aprendizaje que supere a los demás en todos los casos posibles. 5.2 Trabajo Futuro Por una parte, aunque el problema de clasificar cada autómata en una clase es indecidible (ver 2.4), observando las precisiones obtenidas por los distintos algoritmos se puede estimar una primera clasificación basada únicamente en los resultados experimentales y el rendimiento dado por los diversos algoritmos: Los autómatas que permiten precisiones similares a las del azar pertenecen a la clase III y los que obtienen precisión 1 pertenecen a la clase I. Algunos autómatas de la clase II y los de la clase IV necesitarían de más trabajo para ser distinguibles, quizás de mayor potencia computacional, mayor entrenamiento, y un cambio en el tipo de algoritmos utilizados. En este sentido, es interesante poder asociar la complejidad del autómata a la del algoritmo más sencillo que es capaz de predecir su dinámica. Algo que se relaciona con las técnicas que estudian la complejidad de un sistema desde la complejidad descriptiva de los sistemas que lo simulan. Por otra parte, el enfoque dado a este trabajo se puede extender ahora en direc- 5. conclusiones y trabajo futuro 73 Figura 5.1: Comparación entre la precisión alcanzada por los árboles de decisión y la conseguida por las redes neuronales ciones claramente diferenciadas, pero que convendría abordar de manera unificada y sistemática: ∙Aumentando la dimensión y/o el tamaño de los autómatas. Hay sistemas bidimensionales cuya complejidad evolutiva ha sido tratada desde varios ángulos, y que sería interesante abordar ahora con las herramientas computacionales de búsqueda de patrones que se están desarrollando para otras áreas (como las nombradas Redes Convolucionales). Entre estos autómatas de dimensión superior destaca el conocido Juego de la Vida, cuya dinámica compleja se ha demostrado ilimitada y con una potencia de cálculo similar a las máquina de Turing. ∙Aumentando la cantidad de ejemplos de entrenamiento y test que se les da a los algoritmos de aprendizaje. Es sabido que el tamaño y calidad de los conjunto de entrenamiento son esenciales para obtener resultados predictivos interesantes en todos los modelos de ML. Cuando tratamos con dinámicas que 74 análisis de sistemas complejos usando machine learning se saben complejas (incluso caóticas), este factor se hace más acuciante, ya que el espacio de fase en el que se mueven las órbitas de las configuraciones de los sistemas crece exponencialmente y responde a factores mucho más desconocidos. ∙Utilizando distintos algoritmos de aprendizaje a los aquí usados, o distintos parámetros para los mismos algoritmos. Como hemos comentado en párrafos anteriores, el uso de modelos tan simples es un limitante a la capacidad de reconocimiento de patrones complejos. Además, hemos de añadir que ninguno de los modelos utilizados está diseñado específicamente para el reconocimiento de patrones temporales (característica fundamental de los autómatas estudiados), por lo que la introducción de modelos más complejos, mejor adaptados a los estudios de dinámicas, y con mayor capacidad de ajuste, puede ser un factor determinante para poder aumentar la predicción y mejorar la clasificación resultante. ∙Estudiando otros aspectos de los autómatas celulares que no sean la densidad o un trozo de estos. De nuevo, el proceso de simplificación necesario para los objetivos y características de un Trabajo Fin de Grado, nos han llevado a plantear un conjunto muy limitado de posibles experimentos a realizar. La elección ha sido clara: tomar una métrica local de la dinámica (el estado concreto de 3 de las células del autómata) y una métrica global (la densidad del autómata), pero sería deseable realizar un conjunto más amplio de experimentos sobre otro tipo de métricas con el fin de eavluar también hasta qué punto reflejan la dinámica compleja del proceso subyadente. Extender esta forma de trabajo podría dar lugar a la creación de un algoritmo que nos permita clasificar los autómatas en clases (ya sean las de Wolfram, las de Culik-Yu o las de Li-Packard) con una probabilidad alta a pesar de ser un problema indecidible, o a descubrir rasgos sobre los autómatas que nos permitan avanzar en otros campos más allá de la matemática, como pueden ser la física, la biología o la ingeniería. Como uno de los resultados fundamentales de este trabajo creemos que queda demostrado que no es necesario acudir a sofisticados generadores de complejidad para poner a prueba y ver los límites de nuestras herramientas matemático-computacionales de reconocimiento de patrones, es suficiente acudir a pequeños inventos matemáticos para encontrar un campo de juego lo suficientemente complejo como para disponer de retos que justifiquen la profundización y mejora de técnicas de aproximación y predicción. 5. conclusiones y trabajo futuro 75 Por último, la posibilidad de crear una base de datos pública a la que contribuir añadiendo los algoritmos de ML que mejor hayan aprendido un determinado rasgo de un determinado autómata puede ser una buena idea a largo plazo. Por una parte puede ayudar a descubrir propiedades de los autómatas, y por otra puede plantear nuevos desafíos a la hora de intentar predecir rasgos de autómatas caóticos. 6 Apéndice En este capítulo se incluyen muestras de las 88 clases de equivalencia de autómatas celulares unidimensionales. Todos parten de una configuración inicial aleatoria, y permiten hacerse una idea con un simple vistazo de la complejidad de cada autómata. Figura 6.1 78 análisis de sistemas complejos usando machine learning Figura 6.2 6. apéndice 79 Figura 6.3 80 análisis de sistemas complejos usando machine learning 6. apéndice 81 Figura 6.4