Contenido


Entrene a un agente de software para que se comporte de forma racional con el aprendizaje por refuerzo

Comments

Aprendizaje por refuerzo es un subcampo del aprendizaje automático que se puede utilizar para entrenar un agente de software para que se comporte de forma racional en un entorno. El agente es recompensado en base a las acciones que realiza dentro del entorno. Un ejemplo de aprendizaje proviene de 1992, cuando Gerry Tesauro, de IBM, utilizó el aprendizaje por refuerzo para construir un jugador de backgammon que aprendía por sí mismo. Este artículo explora el aprendizaje por refuerzo, algunas áreas problemáticas a las que es posible aplicarlo, y demuestra la tecnología utilizando una simulación sencilla.

Muchos algoritmos del aprendizaje automático pertenecen a una de estas dos categorías: aprendizaje supervisado o no supervisado. En el aprendizaje no supervisado, un algoritmo toma los datos no etiquetados y los segrega en grupos basándose en su estructura concerniente, lo que convierte los datos en datos comprensibles. Un ejemplo de aprendizaje no supervisado es el algoritmo de clasificación de "k-means", que divide los datos en clústeres con el promedio más próximo. Al otro lado del espectro se encuentra el aprendizaje supervisado. En el aprendizaje supervisado, se utiliza una función de correlación para correlacionar un conjunto de variables de entrada con un conjunto redefinidos de variables de salida (con el objetivo de aproximar nuevos datos de entrada a las predicciones). A la categoría de este proceso se la conoce como supervisada por que un algoritmo utiliza los datos de entrada y de salida para entrenar una función de correlación. Las redes neurales son un ejemplo de aprendizaje supervisado.

El aprendizaje por refuerzo es diferente de esos dos enfoques de aprendizaje, aunque se aproxima más a la parte del supervisado. En el aprendizaje por refuerzo, la correlación entre estado y acción se aprende a través de recompensas o castigos acumulativos debidos a sus acciones. La correlación se realiza online, a través del equilibrio entre exploración (intentar acciones nuevas para un estado dado) y utilización (al utilizar el conocimiento existente sobre la correlación estado/acción). El resultado deseado es una política óptima entre estado y acción que maximiza alguna recompensa general como se muestra a continuación.

A single line showing the spectrum of learning types, with     supervised learning on the left end, unsupervised learning on the right end,     and reinforcement learning just left of center
A single line showing the spectrum of learning types, with supervised learning on the left end, unsupervised learning on the right end, and reinforcement learning just left of center

Comencemos con un caso rápido de aprendizaje por refuerzo. A partir de ahí, mostraré un ejemplo de una implementación de aprendizaje por refuerzo, más concretamente, la técnica Q-learning.

Un caso de aprendizaje por refuerzo

El aprendizaje por refuerzo tiene su origen en la psicología animal: el aprendizaje por el método de ensayo y error. Los primeros investigadores de inteligencia artificial (IA) pensaban que este mecanismo se podía implementar en las máquinas y que se podía utilizar para aprender cómo correlacionar estados (el entorno) con acciones. Marvin Minsky construyó el primer ejemplo de aprendizaje por refuerzo en 1951 para imitar como una rata aprende a solucionar un laberinto (se implementó con tubos de vacío que representaban las 40 neuronas del cerebro simulado de la rata). A medida que la rata robótica solucionaba el laberinto, las sinapsis se reforzaban basándose en su capacidad de escapar.

Cuarenta años después, el aprendizaje por refuerzo ha tenido algunos éxitos. En 1992, el investigador de IBM Gerald Tesauro desarrolló un jugador de backgammon llamado TD-Gammon mediante el uso del aprendizaje por refuerzo. Tesauro utilizó el aprendizaje por diferencia temporal (llamado TD lambda) para entrenar una red neural que estaba formada por 80 unidades ocultas. TD-Gammon aprendió a jugar a backgammon sin conocer el cuerpo, incrementando su experiencia jugando consigo mismo. TD-Gammon jugó al mismo nivel que los mejores jugadores humanos e identificó estrategias nuevas para jugar al juego.

¡IBM aplicó el aprendizaje por refuerzo a IBM Watson®, un sistema de preguntas y respuestas que entiende el idioma natural y que puede responder en el idioma natural. Más específicamente, IBM aplicó el aprendizaje por refuerzo a la estrategia de IBM Watson cuando juega a Jeopardy!, como para saber si debe intentar responder a una pregunta (basándose en las respuestas que ha formulado y en su grado de certeza), qué cuadrado del tablero seleccionar y cómo apostar en el juego (más concretamente, en los dobles diarios). IBM Watson derrotó a antiguos campeones de Jeopardy! en 2011.

En 2016, Google aplicó el aprendizaje por esfuerzo para construir un programa que jugaba a Go. Go es famoso por ser difícil de desarrollar debido a la escala de los movimientos posibles (un tablero de 19x19 que tienen dos tipos de piedras). El movimiento de apertura en ajedrez tiene 20 opciones posibles, pero Go tiene 361 movimientos de apertura posibles. AlphaGo de Google aprendió analizando los movimientos de jugadores profesionales, y después jugó contra sí mismo para incrementar su experiencia (aunque ahora está completamente entrenado mediante el juego con sí mismo). Utilizando el aprendizaje por refuerzo profundo, AlphaGo derrotó a un gran maestro coreano de Go .

Q-learning

Ahora vamos a ver un tipo de aprendizaje por refuerzo llamado Q-learning, y después construiremos una simulación de muestra para demostrarlo.

Considere un agente en un mundo de 2 dimensiones. El mundo está formado por celdas que el agente puede ocupar (los estados). En cada estado existen acciones que el agente puede realizar—a saber, moverse en una de las cuatro direcciones para ir a una celda nueva. Cuando el agente se mueve puede recibir una recompensa (o una recompensa futura que se recibe en base a ese movimiento inicial). Dada esta recompensa, puede asignar una preferencia para la acción de un estado, para que el estado sea preferido en el futuro (ya que el objetivo del agente es maximizar su recompensa). Por tanto, el proceso de aprendizaje es identificar la acción óptima para cada estado, la que brinda la mayor recompensa. El proceso de aprendizaje es la identificación de las políticas de las acciones para los estados dados.

En Q-learning, a cada par de estado-acción se le asigna un valor Q, que representa la suma de refuerzos que son calculados por una función de valores Q. Este trabajo se realiza mientras que el agente explora el entorno. Cuando se realiza una acción particular para un estado dado, se entrega una recompensa y actualiza el valor del Qpar estado–acción para que lo recuerde. A medida que el agente merodea se perfeccionan los valores de Qpara los pares estado–acción, a fin de que posteriormente (post-aprendizaje) el agente pueda aplicar la mejor acción para un estado dado (dado su valor de Q). Observe que durante el aprendizaje, el agente puede elegir, de forma probabilística, una acción para un estado dado (como una función del valor de Qde cada acción en relación con la suma de los valores de Q). Este proceso permite que el agente prefiera una acción para un estado dado (para utilizar el conocimiento que ha aprendido), pero a veces elige utilizar una acción menos óptima, como se muestra a continuación.

Process diagram showing the process loop between the site/feedback      and action for the agent and environment based on the environment,      state, action, and Q-value
Process diagram showing the process loop between the site/feedback and action for the agent and environment based on the environment, state, action, and Q-value

La función del valor de Qincorpora un par de valores que se pueden utilizar para ajustar su funcionamiento. El primero es un índice de aprendizaje (alfa), que define cuánto del valor de Qnuevo sobrescribirá el antiguo. El valor 0 significa que el agente no aprenderá nada (la información antigua es todo lo que importa), mientras que el valor 1 significa que la información descubierta más recientemente es lo único que importa. Al siguiente factor se le llama el factor de descuento (gamma), y define la importancia de las recompensas futuras. El valor 0 significa que sólo se tiene en cuenta las recompensas nuevas, mientras que un valor 1 coloca más importancia en las recompensas a largo plazo. Después de seleccionar un movimiento (la acción para un estado dotado), el valor de Qse actualiza para esa acción utilizando el valor de Qactual y los valores de la recompensa y del Q máximodel estado de destino, tal como se muestra a continuación.

Q-learning equation showing the learning and discount      factors, the reward, the new and current values, and the future      value estimate
Q-learning equation showing the learning and discount factors, the reward, the new and current values, and the future value estimate

Las políticas de los pares estado–acción se crean en episodios. Cuando el agente llega al estado final, el episodio acaba y se puede iniciar un nuevo episodio. El entrenamiento también puede estar delimitado por épocas (pasos del agente en el entorno). Observe que los estados en los que no se entra y las acciones que no se intentan no se registran en la tabla de estado–acción. Si un agente no explora alguna parte del estado-espacio, no tendrá ni idea del beneficio (o castigo) que le espera ahí. En los problemas con enormes cantidades de estados-espacios, es posible encontrar una solución sin explorar todos los estados-espacios. El flujo sencillo de la siguiente figura muestra el proceso de aprendizaje en Q-learning.

Flow chart showing the Q-learning process
Flow chart showing the Q-learning process

A partir de aquí, buscaremos una implementación sencilla de Q-learning en la que un agente aprende a navegar por un entorno lleno de obstáculos con el fin de encontrar una recompensa.

Implementación de la muestra

Esta implementación de la muestra se puede encontrar en GitHub. En esta sencilla implementación creé un entorno de 20x20 celdas. Cada celda puede contener un obstáculo (como un muro o un objeto impasible), un espacio abierto (con una recompensa con valor 0) y la celda objetivo (con una recompensa con valor 1). El agente comienza en la celda superior izquierda, y después utiliza Q-learning para encontrar una ruta óptima hacia el objetivo, que se muestra al final del proceso de aprendizaje.

Empecemos con las importantes estructuras que utilicé para esta implementación de Q-learning. La primera es la estructura estado–acción, que contiene los valores de Qpara las acciones de un estado dado. El símbolo MAX_ACTIONS representa las cuatro acciones que puede realizar un agente dentro de un estado dado (0 = Norte, 1 = Este, 2 = Sur, 3 = Oeste). QVal representa los valores de Qpara cada una de las cuatro acciones y QMax es el mayor valor de Q (se utiliza para determinar la mejor ruta cuando el agente utiliza el conocimiento que ha aprendido). Esta estructura se distancia en cada una de las celdas del entorno. También se crea un entorno, que se representa como caracteres (|, +, -, # como obstáculos; ‘ ‘ como espacio abierto; y $ como el estado objetivo):

typedef struct {
   double QVal[ MAX_ACTIONS ];  // Valor de Q para cada acción.
   double QMax;                 // Valor máximo de Q.
} stateAction_t;
stateAction_t stateSpace[ Y_MAX ][ X_MAX ];
char environment [ Y_MAX ][ X_MAX ]={};

Empecemos desde el principio con la función main . Esta función implementa el bucle de Q-learning, cuando el agente intenta acciones de forma aleatoria; actualiza los valores de Q, y, después de algunas épocas, muestra la mejor ruta que ha encontrado hacia el objetivo:

int main()
{
   pos_t agent = start;

   srand( time( NULL ) );

   // Inicia los datos de Q de estado/acción
   initStateSpace( );

   // Itera un número máximo de pasos.
   for ( int epochs = 0 ; epochs < MAX_EPOCHS ; epochs++ )
   {
      // Selecciona una acción para el agente basándose en la política deseada.
      int action = ChooseAgentAction( &agent, EXPLORE );

      // Actualiza el agente basándose en la acción.
      UpdateAgent( &agent, action );
   }

   // Muestra la ruta del agente
   ExecuteAgent( );

   return 0;
}

Después, la función ChooseAgentAction selecciona la siguiente acción para el agente basándose en la política deseada (explorar o utilizar). Para la política de utilización, la función identifica la acción que tiene el mayor valor de Qy devuelve esa acción. Esta opción representa la mejor acción para este estado e imita cómo el agente utiliza su conocimiento para moverse rápidamente hacia el objetivo. Para la política de exploración, sólo obtengo una acción aleatoria, y después devuelvo esta acción, si es una acción legal (mueve el agente hacia el objetivo o a un espacio abierto, y no a un obstáculo). Otro enfoque para explorar es seleccionar la acción de forma probabilística como una función de QVal (utilizando QVal como una probabilidad sobre la suma de valores de Qpara el estado):

int ChooseAgentAction( pos_t *agent, int actionSelection )
{
   int action;

   // Elige la mejor acción (mayor valor de Q)
   if ( actionSelection == EXPLOIT )
   {
      for ( action = 0 ; action < MAX_ACTIONS ; action++ )
      {
         if ( stateSpace[ agent->y ][ agent->x ].QVal[ action] ==
              stateSpace[ agent->y ][ agent->x ].QMax )
         {
            break;
         }
      }
   }
   // Elige una acción aleatoria.
   else if ( actionSelection == EXPLORE )
   {
      do
      {
        action = getRand( MAX_ACTIONS );
      } while ( !legalMove( agent->y, agent->x, action ) );
   }

   return action;
}

La última función de esta simulación que estoy mostrando se llama UpdateAgent, e implementa el núcleo del algoritmo de Q-learning. Observe que esta función se brinda con la acción deseada (una dirección para moverse), que yo utilizo para identificar el siguiente estado para entrar. La recompensa para este estado se extrae del entorno y después se utiliza para calcular el valor de Qactualizado a partir del estado actual (y para guardar en caché el valor de QMax , si ha cambiado). Si el estado nuevo en el que se ha entrado es el estado objetivo, vuelvo a colocar el agente en el estado inicial para reiniciar el proceso de aprendizaje:

void UpdateAgent( pos_t *agent, int action )
{
   int newy = agent->y + dir[ action ].y;
   int newx = agent->x + dir[ action ].x;
   double reward = (double)getReward( environment[ newy ][ newx ] );

   // Evaluar el valor de Q
   stateSpace[ agent->y ][ agent->x ].QVal[ action ] +=
     LEARNING_RATE *
      ( reward + ( DISCOUNT_RATE * stateSpace[ newy ][ newx ].QMax) -
                 stateSpace[ agent->y ][ agent->x ].QVal[ action ] );

   CalculateMaxQ( agent->y, agent->x );

   // Actualizar la posición del agente
   agent->x += dir[ action ].x;
   agent->y += dir[ action ].y;

   // Si el agente ha llegado al objetivo, devolverlo al estado inicial
   if ( ( agent->x == goal.x ) && ( agent->y == goal.y ) )
   {
      agent->x = start.x; agent->y = start.y;
   }

   return;
}

Esta pequeña cantidad de código (y algunos otros que usted puede revisar en GitHub) implementa el Q-learning para esta demostración. Es posible construir el código utilizando make, y después ejecutarlo usando el nombre del programa qlearn. La siguiente ilustración muestra el resultado del código y la ruta seleccionada como . caracteres. Realice esto en el contexto de la función ExecuteAgent (no se muestra), que utiliza la política de utilización para elegir la mejor ruta:

$ ./qlearn 

+ - - - - - - - - - - - - - - - - - - + 
| . .             # # #   # # # # #   | 
|   .   # # #     # # #   # # # # #   | 
| # .     # # #           #   # #     | 
| # .       # # # # # # # #           | 
| # .       # # # # # # # #   # #     | 
|   .   # # #         # #     # # #   | 
|   . # # # # #       # #     # # #   | 
|   . # #                       # #   | 
|   . . . . . . . .   # # #   # # #   | 
|   #       # # # .   # # #   # # # # | 
| # # #     # # # . . . # #   # $ . . | 
| # # #   # # # #     . . . . # # # . | 
| # # #     # # #   # # # # . # # # . | 
| # # #       # #   # # #   . . # # . | 
| # #           #   #       # . # # . | 
| #       # #           # # # . # # . | 
|       # # # #         # # # . . . . | 
|       # # # # #                     | 
+ - - - - - - - - - - - - - - - - - - + 

$

Yendo más allá

El aprendizaje por refuerzo, que se inspira en la psicología del comportamiento, es una técnica útil de aprendizaje automático que se puede utilizar para identificar acciones para los estados que están dentro de un entorno. El enfoque puede permitir que un agente aprenda a interactuar en el entorno a cambio de una recompensa acumulativa. Este artículo ha explorado el Q-learning, en el que un algoritmo no requiere ningún modelo para entender el entorno y construye una política de selección de acciones. Es posible utilizar este enfoque para solucionar una amplia variedad de problemas.

Otro enfoque para el aprendizaje por refuerzo es Estado-Acción-Recompensa-Estado-Acción, que tiene muchas similitudes con el Q-learning. Ambos tienen similitudes para aprender sistemas clasificadores, que construyen reglas que dependen del contexto para espacios de soluciones complejas.

El aprendizaje de diferencias temporales es un método de predicción del aprendizaje por refuerzo que también funciona sobre la idea de que las predicciones se pueden aprender a partir de observaciones en un entorno. Pero, las variantes del aprendizaje de diferencias temporales pueden actualizar los valores de Q del par estado-acción previo en vez de sólo el actual.

El aprendizaje de diferencias temporales empezó con el trabajo de Arthur Samuel (quien tuvo la fama de desarrollar en IBM la IA para un programa del juego de damas en la plataforma 701 de IBM® ) y en 1992 continuó en el campo de los juegos con TD-Gammon de Gerald Tesauro en IBM. Google continuó con esta tendencia con DeepMind, utilizando el aprendizaje por esfuerzo profundo para jugar y batir puntuaciones de jugadores humanos en 23 de 49 juegos de Atari 2600 (como Atari Breakout). En este modelo, la imagen del videojuego que el jugador ve se aplica al algoritmo de aprendizaje automático y el algoritmo emite la siguiente jugada (cómo mover el jugador) para el juego.


Recursos para Descargar


Comentarios

Inicie Sesión o Regístrese para agregar comentarios.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=90
Zone=Cognitive computing
ArticleID=1054401
ArticleTitle=Entrene a un agente de software para que se comporte de forma racional con el aprendizaje por refuerzo
publish-date=12042017