1b68cnwwkpobifme2r22nsw.jpeg

Aprendizaje por refuerzo: el problema de decisión de Markov para la selección de funciones

Se ha demostrado que las técnicas de aprendizaje por refuerzo (RL) pueden ser muy eficientes para problemas como la resolución de juegos. El concepto de RL se basa en el proceso de decisión de Markov (MDP). El punto aquí no es definir profundamente el MDP sino tener una idea general de cómo funciona y cómo puede ser útil para nuestro problema.

La idea ingenua detrás de RL es que un agente comienza en un entorno desconocido. Este agente tiene que tomar acciones para completar una tarea. En función del estado actual del agente y de la acción que haya seleccionado previamente, el agente estará más inclinado a elegir algunas acciones. Por cada nuevo estado alcanzado y acción realizada, el agente recibe una recompensa. Estos son los parámetros principales que debemos definir para fines de selección de funciones:

  • ¿Qué es un estado?
  • ¿Qué es una acción?
  • ¿Cuáles son las recompensas?
  • ¿Cómo elegimos una acción?

En primer lugar, el estado es simplemente un subconjunto de características que existen en el conjunto de datos. Por ejemplo, si el conjunto de datos tiene tres características (Edad, Sexo, Altura) más una etiqueta, estos serán los estados posibles:

[]                                              --> Empty set                           
[Age], [Gender], [Height] --> 1-feature set
[Age, Gender], [Gender, Height], [Age, Height] --> 2-feature set
[Age, Gender, Height] --> All-feature set

En un estado, el orden de las características no importa y se explicará por qué un poco más adelante en el artículo. Tenemos que considerarlo como un conjunto y no una lista de características.

En cuanto a las acciones, de un subconjunto podemos pasar a cualquier otro subconjunto que tenga una característica aún no explorada más que el estado actual. En el problema de selección de características, una acción selecciona una característica aún no explorada en el estado actual y la agrega al siguiente estado. A continuación se muestra una muestra de posibles acciones:

[Age] -> [Age, Gender]
[Gender, Height] -> [Age, Gender, Height]

Aquí hay un ejemplo de acciones imposibles:

[Age] -> [Age, Gender, Height]
[Age, Gender] -> [Age]
[Gender] -> [Gender, Gender]

Hemos definido los estados y las acciones pero no la recompensa. La recompensa es un número real que se utiliza para evaluar la calidad de un estado. Por ejemplo, si un robot está intentando llegar a la salida de un laberinto y decide ir a la salida como siguiente acción, entonces la recompensa asociada a esta acción será “buena”. Si elige como siguiente acción caer en una trampa, la recompensa “no será buena”. La recompensa es un valor que aporta información sobre la acción anterior realizada.

En el problema de la selección de características, una recompensa interesante podría ser un valor de precisión que se agrega al modelo al agregar una nueva característica. A continuación se muestra un ejemplo de cómo se calcula la recompensa:

[Age] --> Accuracy = 0.65
[Age, Gender] --> Accuracy = 0.76
Reward(Gender) = 0.76 - 0.65 = 0.11

Para cada estado que visitemos por primera vez se entrenará un clasificador con el conjunto de características. Este valor se almacena en el estado y el entrenamiento del clasificador, que es muy costoso, sólo se realizará una vez, incluso si el estado se alcanza nuevamente más tarde. El clasificador no considera el orden de la característica. Por eso podemos ver este problema como un gráfico y no como un árbol. En este ejemplo, la recompensa de la acción de seleccionar Género como una nueva característica para el modelo es la diferencia entre la precisión del estado actual y el siguiente.

Ejemplo de los posibles estados y acciones con recompensas asociadas a cada uno
Cada estado tiene varias posibles acciones y recompensas asociadas (Imagen del autor)

En el gráfico anterior, cada característica se ha asignado a un número (es decir, «Edad» es 1, «Género» es 2 y «Altura» es 3). Es totalmente posible tomar otras métricas para maximizar y encontrar el conjunto óptimo. En muchas aplicaciones empresariales se tiene más en cuenta la recuperación que la precisión.

La siguiente pregunta importante es cómo seleccionamos el siguiente estado a partir del estado actual o cómo exploramos nuestro entorno. Tenemos que encontrar la forma más óptima de hacerlo ya que rápidamente puede convertirse en un problema muy complejo. De hecho, si exploramos ingenuamente todo el conjunto posible de características en un problema con 10 características, el número de estados sería

10! + 2 = 3 628 802 possible states

El +2 se debe a que consideramos un estado vacío y un estado que contiene todas las características posibles. En este problema tendríamos que entrenar el mismo modelo en todos los estados para obtener el conjunto de características que maximice la precisión. En el enfoque RL no tendremos que ir a todos los estados y entrenar un modelo cada vez que vayamos a un estado ya visitado.

Tuvimos que determinar algunas condiciones de parada para este problema y se detallarán más adelante. Por ahora se ha elegido la selección de estados codiciosos de épsilon. La idea es que a partir de un estado actual seleccionamos la siguiente acción al azar con una probabilidad de épsilon (entre 0 y 1 y, a menudo, alrededor de 0,2) y, de lo contrario, seleccionamos la acción que maximiza una función. Para la selección de características, la función es el promedio de recompensa que cada característica ha aportado a la precisión del modelo.

El algoritmo épsilon-codicioso implica dos pasos:

  1. Una fase aleatoria: con una probabilidad épsilon, seleccionamos aleatoriamente el siguiente estado entre los posibles vecinos del estado actual (podemos imaginar una selección uniforme o softmax)
  2. Una fase codiciosa: seleccionamos el siguiente estado de modo que la característica agregada al estado actual tenga la máxima contribución de precisión al modelo. Para reducir la complejidad del tiempo, hemos inicializado una lista que contiene estos valores para cada característica. Esta lista se actualiza cada vez que se elige una función. La actualización es muy óptima gracias a la siguiente fórmula:
Actualización del promedio de la lista de recompensas para cada característica (Imagen del autor)
  • AORf : Promedio de recompensa aportada por la función «f»
  • k : número de veces que se ha seleccionado “f”
  • V(F) : valor del estado del conjunto de características F (no se detalla en este artículo por razones de claridad)

La idea global es encontrar qué característica ha aportado la mayor precisión al modelo. Es por eso que necesitamos explorar diferentes estados para evaluar en muchos entornos diferentes el valor más preciso global de una característica para el modelo.

Finalmente detallaré las dos condiciones de parada. Dado que el objetivo es minimizar la cantidad de estados que visita el algoritmo, debemos tener cuidado con ellos. Cuanto menos estado nunca visitado visitemos, menos cantidad de modelos tendremos que entrenar con diferentes conjuntos de características. Entrenar el modelo para obtener la precisión es la fase más costosa en términos de tiempo y potencia de cálculo.

  1. El algoritmo se detiene en cualquier caso en el estado final que es el conjunto que contiene todas las características. Queremos evitar llegar a este estado ya que es el más caro para entrenar un modelo.
  2. Además, deja de navegar por el gráfico si una secuencia de estados visitados ve sus valores degradarse sucesivamente. Se ha establecido un umbral tal que después de la raíz cuadrada del número total de entidades en el conjunto de datos, se deja de explorar.

Ahora que se ha explicado el modelado del problema, detallaremos la implementación en Python.