- MPI
- Aprendizaje no Supervisado
- Aprendizaje por Refuerzo
- Programación Evolutiva
- Aprendizaje Supervisados
Es uno de los lenguajes más populares para la IA debido a su sintaxis sencilla, amplia variedad de bibliotecas de IA (como TensorFlow, PyTorch, scikit-learn, etc.) y una gran comunidad de desarrolladores. Pero es un lenguaje bastante lento, lo que provoca que a la hora de ejecutar el código demore bastante tiempo en finalizar.
Voy a estar programando en Python, y probando maneras de reducir el tiempo de ejecución.
Es un estándar para una biblioteca de paso de mensajes, cuyo objetivo es facilitar la programación paralela en entornos distribuidos, permitiendo que múltiples procesos independientes se comuniquen para resolver tareas de manera eficiente.
Actualmente hay varias implementaciones: Open MPI, MPICH , MVAPICH, IBM Platform MPI, Intel MPI. En este proyecto se usa mpi4py.
1 programa ejecutado en paralelo. El mismo programa se copia a todos los nodos. Cada proceso tiene su propio su ID (Rank)
La principal diferencia entre la memoria compartida y distribuida radica en cómo se organizan y gestionan los recursos de memoria en sistemas de cómputo paralelos. La memoria compartida tiene una sola memoria que comparte entre todos los procesos, teniendo que ejecutar técnicas para garantizar la sincronización. En su contraparte, la memoria distribuida utiliza memorias independientes entre cada proceso, por lo que estos problemas no ocurren. Sin embargo, la comunicación entre procesos resulta ser más costosa en los sistemas distribuidos.
Esquema básico para ejecutar un programa MPI en Python:
from mpi4py import MPI # Al importar la biblioteca en Python se genera el entorno.
comm = MPI.COMM_WORLD # Comunicador
status = MPI.Status() # Status
myrank = comm.Get_rank() # id de cada proceso
numProc = comm.Get_size() # Numero de procesadores
if myrank==0: # Master
# Carga el conjunto de datos. Los divide y envia.
# Recibe todos los datos procesados.
else: # Workers
# Recibe el subconjunto de datos que le asigna el Master.
# Procesa los datos. Los envia.Carpeta con explicaciones y el código AQUÍ.
Los métodos no supervisados (unsupervised methods, en inglés) son algoritmos de aprendizaje automático que basan su proceso en un entrenamiento con datos sin etiquetar. Es decir, a priori, no se conoce ningún valor objetivo, ya sea categórico o numérico. La meta de este aprendizaje es encontrar patrones o estructuras en los datos proporcionados. Estos algoritmos son útiles en escenarios en los cuales hay escasez de datos etiquetados o éstos no están disponibles.
En este proyecto vamos a reducir el tiempo de ejecución de las técnicas de clustering que se encargan de agrupar individuos basándose en alguna medida de similitud. Los algoritmos son los siguientes:
FASE 1: Crear la matriz de distancias inicial D. Es una matriz simétrica (basta con usar una de las matrices triangulares)
FASE 2: Agrupación de Individuos
o 2.1. Partición inicial P0: Cada objeto es un cluster
o 2.2. Calcular la partición siguiente usando la matriz de distancias D
Elegir los dos clusters más cercanos. Serán la fila y la columna del valor mínimo de la matriz D
Agrupar los dos en un cluster. Eliminar de la matriz la fila y columna con mayor indice de los dos clusters agrupados.
• Actualizar la fila de los dos clusters que se agrupan.
• Calcular la distancia del resto de clusters al cluster nuevo .
Repetir este el paso 2.2. hasta tener sólo un cluster con todos los individuos
FASE 3 (OPCIONAL): Representar el dendograma.
La complejidad con los enlaces simple y completo tienen un coste cúbico O(N^3). Existen implementaciones más eficientes (N^2).Divide la matriz entre todos los procesos. El proceso master se encarga de gestionar la comunicación entre los procesos para dividir el algoritmo entre estos. Dependiendo de la distancia hay más o menos implementaciones.
Distancia por centroides:
Distancias por enlace simple/completo, (complejidad mayor que la anterior distancia):
- El proceso que actualiza la fila trabaja solo.
- El proceso que actualiza la fila trabaja con todos los procesos workers.
Carpeta con explicaciones y el código AQUÍ.
Fijar un valor k.
FASE 1: Inicializar los K centros de los clusters de forma aleatoria.
• Generando puntos aleatorios en el espacio dimensional
• Seleccionando aleatoriamente individuos
FASE 2: Repetir esta fase hasta que los centros no cambien.
o 2.1. (Asignación): Calcular el cluster más cercano para cada individuo.
Requiere el uso de una distancia (normalmente Euclídea o Manhattan).
o 2.2. (Actualización): Calcular los nuevos centros con la asignación calculada de los individuos.
Se calcula con la media de los valores de los individuos de cada cluster.
Como los clusters se generan aleatoriamente, no siempre va a dar un buen resultado a la primera.
Por lo que conviene ejecutar varias veces este algoritmo para encontrar la mejor asignación.Divide la población de individuos matriz entre todos los procesos. El proceso master se encarga de gestionar de calcular los nuevos centros en cada iteración.
Distancia Euclídea:
Distancia Manhattan:
Para la búsqueda se ejecuta un bucle principal con el número de centros máximo que se quiere estudiar, es decir, se ejecuta el algoritmo para los valores de K entre [2, K_max]. En este bucle principal se repite 5 veces para encontrar la mejor asignación para cada valor de K. Hay dos implementaciones, la estrategia MPI comentada en la subsección anterior, o ejecutar en varios procesos el algoritmo secuencial con diferentes valores de K, pero mismos centros.
Carpeta con explicaciones y el código AQUÍ.
Se basa en experiencias y simulaciones, con prueba y error, recibiendo recompensas con las acciones tomadas (también pueden ser negativas). Nadie le dice al agente que hacer, éste toma las decisiones con diferentes estrategias. Se realiza una etapa de entrenamiento para que aprenda a moverse por el entorno, tomando las decisiones que maximicen las recompensas obtenidas en experiencias pasadas.
Los algoritmos desarrollados en este proyecto son los siguientes:
Mezcla entre programación dinámica y Monte Carlo.
- R = Matriz de recompensas.
- Q = Matriz (Estados x Acciones). Que acción elegir en cada estado. (mayor valor)
Para este algoritmo es un laberinto. Se entrena al agente para que consiga llegar desde un punto origen a uno destino en el menor número de acciones necesarias.
- α (tasa de aprendizaje): Este hiper-parámetro controla cuánto modifica una nueva experiencia.
- γ (factor de descuento): Representa cuánto de importancia le damos a las recompensas futuras.
- ϵ (factor de exploración-explotación): Este hiper-parámetro controla el balance entre exploración y explotación. Cuanto más lejos esté el agente de la ejecución inicial, menores actuaciones de exploración y mayor explotación serán necesarias para obtener más utilidad de nuestra póliza, por lo que, en vez de utilizar un valor fijo, a medida que aumentan los ensayos, épsilon debería disminuir. Al principio un epsilon alto genera más episodios de exploración y al final un épsilon bajo explota el conocimiento aprendido.
La función que usa para almacenar las experiencias en la Q-Table es la siguiente:
Q(S, A) = (1−α)*Q(S, A) + α*(R(S, A) + γ*maxi Q(S’, Ai))
Siendo S el estado actual, A la acción tomada, S’ el estado siguiente y Ai una acción de entre todas las acciones del agente.
Al dividir el laberinto entre los procesos, cada proceso controla una zona, y se genera un flujo constante de episodios (iteraciones del algoritmo). Cuando un agente sale del dominio de un proceso, éste le manda un mensaje al proceso que controla esa parte del laberinto con la posición en la que entra
El master recolecta las experiencias de los workers, haciendo la media de los Q-valor obtenidos de los procesos, calculando así las mejores acciones para cada estado.
Igual que la mejora anterior, pero esta vez para encontrar hiper-parámetros. Cada proceso ejecuta combinaciones distintas y almacena en ficheros los resultados obtenidos (Fin, Bucle, ...)
Carpeta con explicaciones y el código AQUÍ.
Este algoritmo combina redes neuronales con la base de aprendizaje por refuerzo, eliminando así la Q-Table.
La estructura de la red neuronal depende del entorno del problema. Los valores de la capa oculta se pueden modificar dependiendo de las necesidades del programador, pero la capa de entrada y salida depende del problema. La entrada se adapta para recibir un estado del entorno, como por ejemplo una imagen representada como una matriz. La salida de la red tendrá tantos nodos como acciones tenga el agente.
El juego Pacman, diseñado por la empresa Namco, y en particular la versión de Atari 2600. El juego consiste en recolectar todas las monedas del laberinto sin ser comido por un fantasma. Implementamos el juego -desde cero- para moldear según nuestros intereses la implementación y que el algoritmo DQN sea más eficiente y sencillo.
- Gamma (factor de descuento [0, 1]). Utilizado para saber cuánto resta a la recompensa adquirida al realizar una acción en un estado.
- Epsilon (tasa de exploración [0, 1]). Probabilidad utilizada para ejecutar una acción aleatoria o la mejor hasta el momento.
- Learning rate (tasa de aprendizaje [0, 1]). Para la propagación hacia atrás de las redes neuronales. Esencialmente, mide cuánto cambian los pesos de los nodos al tener un fallo.
Además de estos parámetros, el algoritmo cuenta con otras variables para desarrollar las redes neuronales.
- Epsilon decay. Utilizado para no usar siempre el mismo valor de epsilon. Esta variable marca cuanto se reduce la variable epsilon entre episodios.
- Número de ejemplos de entrenamiento (batch size}. Se utiliza para actualizar los parámetros de la red neuronal durante una sola iteración del entrenamiento.
- Tamaño de la capa oculta. Marca el número de neuronas en cada capa.
Misma estrategias de búsqueda que la del algoritmo Q-Learning.
Mismas estrategias que en las Redes Neuronales
Carpeta con explicaciones y el código AQUÍ.
La programación evolutiva es una técnica de optimización inspirada en la teoría de la evolución biológica. Se basa en el concepto de selección natural y evolución de las poblaciones para encontrar soluciones a problemas complejos.
Una población está compuesta por individuos, que son sometida a métodos de evaluación, selección, cruce y mutación para, con el paso de las generaciones, maximizar o minimizar un valor fitness. Un individuo tiene un cromosoma, que tiene uno o varios genes, que a su vez cada gen tiene uno o varios alelos. Los individuos se pueden representar de las siguientes formas:
- Binarios: Cada alelo es un bit.
- Reales: Cada alelo es un número real. Estos individuos son más fáciles de manejar.
- Árboles: Cada alelo es un nodo del árbol.
poblacion = iniciar_poblacion(tam_poblacion)
evaluar_poblacion(poblacion)
while(<<condicion>>):
seleccion = seleccionar_poblacion()
# Reproducción
poblacion = cruzar_poblacion(seleccion, prob_cruce)
poblacion = mutar_poblacion(seleccion, prob_muta)
evaluar_poblacion()La población se divide entre los procesos generados. El master se encarga de gestionar las comunicaciones para que la población evolucione.
La población se divide en subpoblaciones repartidas entre los procesos ejecutados, para, en paralelo, evolucionar a la población general. Los procesos se comunican cada cierto tiempo para reiniciar las poblaciones con los mejores individuos de todos los procesos.
Cada parte del algoritmo se divide entre los procesos. El master genera subpoblaciones, y los workers ejecutados se encargan de evaluar, seleccionar, cruzar y mutar las poblaciones que reciben del proceso anterior. Una vez procesan los datos recibidos, los envían hacia adelante y esperan a recibir nuevos datos. Cada proceso se encarga de una parte, generando un flujo constante de mensajes entre los procesos.
Carpeta con explicaciones y el código AQUÍ.
Simple pero potente, resultando muy efectivo para tareas de clasificación y regresión. Se basa en la idea de que los puntos de datos similares tienden a agruparse en el espacio de características. Este algoritmo pertenece al paradigma de aprendizaje perezoso o basado en instancias.
FASE 1: Inicializar las poblaciones categorizadas y a predecir, y la variable K
FASE 2: Para cada individuo. Agruparlo con la población categorizada
o 2.1. Recorrer todos los individuos de la población categorizada, y almacenar las K individuos más cercanos.
o 2.2. Asignar el cluster con más repeticiones al individuo actual.
o 2.3. (opcional) Añadir el individuo actual a la población categorizada.
No hay manera de determinar el mejor valor para K, por lo que hay que ejecutar el algoritmo varias veces con diferentes valores de K.
Valores pequeños de K crean sonido.
Valores grandes con pocos datos hará que siempre clasifique la misma categoría.Las estrategias se dividen en dos principales implementaciones, actualizando la población categorizada conforme se categorizan nuevos individuos, o no actualizando. Si se actualiza se obtienen mejores resultados en cuanto a predicciones se refiere, pero el tiempo de ejecución es mucho mayor.
Se divide la población categorizada entre los procesos para que estos trabajen de manera paralela en un mismo individuo. Es decir, cada worker envía los K vecinos más cercanos de su subpoblación categorizada. No Actualizando:
Actualizando:
Se divide la población a predecir entre los procesos para que estos trabajen en paralelo de manera independiente. Es decir, cada worker envía al proceso master un individuo distinto al terminar un procesado. No Actualizando:
Actualizando:
Carpeta con explicaciones y el código AQUÍ.
Las redes neuronales son un modelo computacional inspirado en el funcionamiento y estructura de las neuronas del cerebro humano. Esencialmente, consisten en capas de nodos interconectados, llamadas neuronas artificiales. La red neuronal se compone de las siguientes capas:
- Capa de entrada, en la cual, habrá tantas neuronas como variables de entrada tenga el modelo de predicción.
- Capa oculta, representada con una o más capas internas. Cada una contiene un número determinado de neuronas.
- Capa de salida. Como en la entrada, tendrá un número de neuronas relacionadas con las variables de salida.
Cada neurona hace una operación simple. Suma los valores de todas las neuronas de la columna anterior. Estos valores multiplicados por un peso que determina la importancia de conexión entre las dos neuronas. Todas las neuronas conectadas tienen un peso que irán cambiando durante el proceso de aprendizaje. Además, un valor bias puede ser añado al valor calculado. Con el valor calculado se aplica a una función de activación, para obtener el valor final.
Proceso de aprendizaje/entrenamiento:
FASE 1: Inicializar los pesos de la red neuronal con los datos de inicialización
FASE 2: Entrenamiento
o 2.1. (Forward) Enviar un individuo por la red neuronal. Suma el valor recibido de la capa anterior multiplicada
por los pesos de la capa actual con la siguiente. Así se determina la importancia de conexión entre las neuronas.
Con el valor calculado se aplica a una función de activación y se pasa a la siguiente capa hasta llegar a la salida.
o 2.2. (Backpropagation) Enviar el error cometido hacia atrás. El valor predicho calculado en la salida es comparado con
la etiqueta, y se calcula el error. Este error se manda para atrás actualizando los pesos. Se suma la multiplicación
del valor predicho en cada capa con la tasa de aprendizaje y el error.Al igual que en los algoritmos evolutivos cada proceso se encarga de una parte del modelo para generar un flujo constante de mensajes. En este caso cada worker se encarga de una capa.
Se divide la población de entrenamiento entre los procesos. Al final se juntan las experiencias haciendo la media. (No funciona correctamente, da malas predicciones)
Al igual que en otros algoritmos, se ejecutan en paralelo ejecuciones secuenciales, en donde cada proceso almacena los resultados.