in

Búsqueda de árboles de Monte Carlo: Introducción

0Wv4gteWiNUUvm7gw

Búsqueda de árboles de Monte Carlo: Introducción

MCTS es la piedra angular de AlphaGo y de muchas aplicaciones de inteligencia artificial. Nuestro objetivo es construir algunas intuiciones y en el camino ensuciarnos las manos.

Benjamín Wang

10 de enero·6 min de lectura

0*Wv4gteWiNUUvm7gw

Monte Carlo Tree Search (MCTS) es un algoritmo importante detrás de muchos de los principales éxitos de las aplicaciones de IA recientes, como el sorprendente enfrentamiento de AlphaGo en 2016.

En este blog, primero comenzaremos con búsqueda desinformada en el que simplemente recorremos todo el espacio de búsqueda para encontrar el óptimo. Incluye búsqueda en profundidad primero y búsqueda primero en amplitud.

Luego seguimos describiendo cómo funciona el algoritmo MCTS. Al final, lo aplicamos a un problema de ejemplo de juguete para encontrar el nodo hoja más gratificante de un árbol binario.

Búsqueda desinformada

Mar desinformadorch, como su nombre indica, es un tipo de algoritmos de búsqueda genéricos a los que no se les da más información que la definición abstracta de un problema. Aunque se pueden aplicar universalmente con la abstracción correcta de problemas, normalmente sufren problemas de eficiencia cuando el problema se agranda.

Un árbol con factor de rama de B y profundidad de D tendría b ^ d (leer como B al poder de D) número de nodos de hojas.

En los juegos, usamos el llamado árbol de juegos en el que cada nodo representa un estado de un juego y sus nodos secundarios representan los siguientes estados posibles para todas las acciones posibles que puede realizar un jugador.

0*zZdO6w2GJnpR1O5l

Para dar algunas ideas, Go tiene un factor de rama promedio de 250 según Wikipedia. Algunos cálculos del reverso del sobre mostrarán rápidamente lo prohibitivo que es utilizar la búsqueda desinformada en Go:

  • En el paso 1: 250
  • En el paso 2: 250² = 62500
  • En el paso 3: 250³ = 15,625,000
  • En el paso 4: 250⁴ = 3,906,250,000
  • En el paso 5: 250⁵ = 976,562,500,000
  • En el paso 10: 250¹⁰ = 953,674,316,406,250,000,000,000

Después de 10 pasos, ya vemos una cantidad cosmética de posibles estados de juego. Esto también da cierto sentido por qué la victoria de AlphaGo es un hito para la humanidad.

Búsqueda de árboles de Montecarlo

Ahora entendemos el hecho de que necesitamos algo mas inteligente que la búsqueda desinformada para navegar a través de un espacio estatal gigantesco como el juego de Go. MCTS es uno de esos algoritmos inteligentes que nos da una salida.

Esencialmente, MCTS utiliza la simulación de Monte Carlo para acumular estimaciones de valor para guiar hacia trayectorias altamente gratificantes en el árbol de búsqueda.. En otras palabras, MCTS presta más atención a los nodos que son más prometedores, por lo que evita tener que forzar todas las posibilidades, lo que no es práctico.

En esencia, MCTS consta de iteraciones repetidas (idealmente infinitas, en la práctica limitadas por el tiempo y los recursos de cálculo) de 4 pasos: selección, expansión, simulación y respaldo.

Selección

En este paso, usamos política de árboles para construir el camino desde la raíz hasta el más prometedor nodo hoja.

Un nodo hoja es un nodo que tiene nodos secundarios inexplorados.

Una política de árbol es una política informada que se utiliza para la selección de acciones (nodos) en el capa de nieve (parte explorada del árbol del juego en contraposición a la vasta parte inferior inexplorada). Una consideración importante de tal política es el equilibrio de exploración vs explotación, un tema recurrente en la IA, especialmente en el aprendizaje por refuerzo.

En el algoritmo detrás de AlphaGo, se utiliza una política basada en UCB. Más específicamente, cada nodo tiene un valor UCB asociado y durante la selección siempre elegimos el nodo hijo con el valor UCB más alto.

Como podemos ver, cuanto más un nodo I se visita, menor es el segundo término en UCB, por lo que disminuye su probabilidad de ser seleccionado nuevamente. Por lo tanto, el algoritmo UCB tiene la exploración y la explotación intrínsecamente incorporadas. ¡Inteligente y ordenado!

Para obtener un relato más riguroso pero fácil de seguir de la exploración frente a la explotación (incluido UCB), lea el blog de Lilian Weng sobre este tema.

Finalmente, en el paso de selección, podemos atravesar el casquete de nieve o la parte explorada del árbol hasta alcanzar un nodo de hoja.

Expansión

¿Recuerda que llegamos a un nodo hoja al final de la selección?

En el paso de expansión, simplemente elegimos al azar un nodo inexplorado de un nodo hoja.

Simulación (o implementación)

Durante este paso, implementamos una o varias simulaciones con recompensa acumulada para cada simulación. La política de implementación es normalmente simple o incluso puramente aleatoria, de modo que es rápida de ejecutar. Por ejemplo, una victoria puede inducir una recompensa de +1, un empate por 0 y una pérdida por -1.

Uno podría preguntarse, ¿por qué molestarse?

En el juego de Go, este paso es como el algoritmo, como lo haría un maestro de Go en su cabeza, jugando muchas veces el juego hasta el final. El verdadero genio no solo ve el futuro, sino muchas versiones del mismo.

Respaldo

Ahora que hemos realizado muchas simulaciones, ¿qué podemos hacer con ellas para informar el mejor próximo movimiento?

Usamos las recompensas acumuladas de las simulaciones para respaldar y actualizar los valores de los nodos en el capa de nieve.

Nota: ¡no actualizamos los valores de los nodos durante los pasos de implementación! Esto se hace así porque debemos centrarnos en la vecindad del nodo raíz (capa de nieve), en función del cual debemos tomar decisiones sobre los próximos movimientos. Considerando que los valores fuera de snowcap no son relevantes para tal decisión, ni computacionalmente eficientes para almacenar y calcular.

Ponlo junto

1*llm1

El pseudocódigo podría verse a continuación:

def run(node, num_rollout):
"one iteration of select->expand->simulation-> backup"
path = select(node)
leaf = path[-1]
expand(leaf)
reward = 0
for i in range(num_rollout):
reward += simulate(leaf)
backup(path, reward)

Tenga en cuenta que esta es una iteración de MCTS dado un nodo raíz específico, por ejemplo, un nodo en el árbol del juego. En la práctica, podemos hacer tantas iteraciones como sea posible de estos 4 pasos, durante los cuales en el paso de simulación se pueden realizar múltiples implementaciones. Una vez que se agotan los recursos o el tiempo de cálculo, detenemos el ciclo de iteración y decidimos cuál es el siguiente movimiento a tomar, luego terminamos con un nuevo nodo raíz y ejecutamos las iteraciones nuevamente, y así sucesivamente …

Un ejemplo simple pero no más simple

(Código disponible en: git repo)

Supongamos que tenemos un árbol binario de profundidad 7, todos sus nodos de hojas llevan una cierta recompensa entre 0 y 100, extraída de una distribución uniforme. Nuestra tarea es encontrar la recompensa más alta entre los nodos de hoja de 2⁷ (una pequeña nota: los nodos de hoja usados ​​aquí tienen su significado rudimentario, es decir, los nodos en el árbol sin hijos, a diferencia de MCTS, usamos nodos de hoja para denotar nodos con inexplorados niño).

0*nTkon2eZDMcVomkh

El lector puede consultar mi repositorio de git y ejecutar find_max_leaf_binary_tree.py. El código incluye cómodamente algunos parámetros:

  • numb_iter para cambiar el número de iteraciones de MCTS
  • num_rollout para cambiar el número de lanzamientos durante la simulación
  • exploration_weight para controlar el equilibrio entre exploración y explotación

¡Suficiente para jugar!

La ejecución predeterminada muestra los resultados a continuación:

Expected (max) leaf node: node@7_53, value: 99.16984625936269
Expected (min) leaf node: node@7_121, value: 1.2521064278136151
Found optimal (max) leaf node: node@7_104, value: 95.8546572417074

No está mal, el nodo óptimo encontrado está bastante cerca de su valor esperado (tenga en cuenta que es posible que no obtenga el resultado exacto debido a su naturaleza probabilística).

Conclusión

Muchos de los problemas de IA tienen su origen en problemas de búsqueda. Después de todo, la vida se trata de buscar. Espero que todos encuentren su camino óptimo :).

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

vFe4DeV8mi24YmsVi4ehxQ 1200 80

El mejor adaptador de línea eléctrica de 2021

Formularios de Oracle