Soy incapaz de entender Muestreo de Thompson y cómo funciona. Estaba leyendo sobre Multi Arm Bandit y después de leer Upper Confidence Bound Algorithm, muchos textos sugieren que Thompson Sampling funciona mejor que UCB. ¿Qué es el muestreo de Thompson, en términos sencillos?
Siéntase libre de proporcionar artículos de referencia para una mayor comprensión.
Voy a intentar dar una explicación sin matemáticas. Parte de esta respuesta se repite de algunos puntos que hice en una respuesta a otra pregunta sobre los problemas del MAB .
El compromiso estratégico en los problemas de bandidos de brazos múltiples: En problemas de bandidos de brazos múltiples el jugador juega un "bandido" en cada ronda e intenta maximizar su rendimiento total esperado en un número determinado de rondas. El rendimiento esperado de cada uno de los bandidos está descrito por algunos parámetros desconocidos en el problema, por lo que a medida que observamos más resultados en cada ronda, obtenemos más información sobre estos parámetros desconocidos y, por tanto, sobre el rendimiento esperado de cada uno de los bandidos. En cada ronda de juego (excepto la última), el problema MAB implica un compromiso estratégico por el jugador entre dos objetivos:
Recompensas inmediatas: En cada ronda le gustaría elegir una distribución que le dé una alta recompensa esperada en esta ronda, lo que implica una preferencia por las distribuciones que (actualmente) infiere que tienen una alta recompensa media;
Recompensas futuras (afectadas por la ganancia de información): Por otro lado, quiere perfeccionar su conocimiento de las verdaderas recompensas esperadas obteniendo más información sobre las distribuciones (especialmente las que no ha jugado tanto como otras), para poder mejorar sus elecciones en futuras rondas.
La importancia relativa de estas dos cosas determinará la compensación, y esta importancia relativa se ve afectada por una serie de factores. Por ejemplo, si sólo hay un pequeño número de rondas restantes en el problema, entonces la inferencia para las pruebas futuras es relativamente menos valiosa, mientras que si hay un gran número de rondas restantes, entonces la inferencia para las recompensas futuras es relativamente más valiosa. Por tanto, el jugador debe considerar hasta qué punto quiere centrarse en maximizar las recompensas inmediatas en la ronda actual, y hasta qué punto quiere desviarse de esto, para aprender más sobre los parámetros desconocidos que determinan la recompensa esperada de cada uno de los bandidos.
Muestreo de Thompson: La idea básica del muestreo de Thompson es que en cada ronda, tomamos nuestro conocimiento existente de las máquinas, que está en forma de una creencia posterior sobre los parámetros desconocidos, y "muestreamos" los parámetros de esta distribución posterior. Este parámetro muestreado da lugar a un conjunto de recompensas esperadas para cada máquina, y ahora apostamos por la que tenga la mayor recompensa esperada, bajo ese parámetro muestreado.
A primera vista El esquema de muestreo de Thompson parece implicar un intento de maximizar el rendimiento esperado inmediato en cada ronda (ya que implica este paso de maximización después del muestreo del parámetro). Sin embargo, dado que implica el muestreo aleatorio del parámetro a partir de la parte posterior, el esquema implica un implícito variación de maximizar la recompensa actual, frente a la búsqueda de más información. La mayoría de las veces obtendremos una "muestra" de parámetros que se encuentre en algún lugar de la parte principal de la posterior, y la elección de la máquina se aproximará aproximadamente a la maximización de la recompensa inmediata. Sin embargo, a veces obtendremos una muestra aleatoria de un valor de parámetro que está muy lejos en las colas de la distribución posterior, y en ese caso acabaremos eligiendo una máquina que no maximice la recompensa inmediata, es decir, esto constituirá más bien una "búsqueda" para ayudar a las recompensas futuras.
El esquema de Thompson también tiene la agradable propiedad de que tendemos a disminuir nuestra "búsqueda" a medida que obtenemos más información, y esto imita la deseable compensación estratégica en el problema, donde queremos centrarnos menos en las búsquedas a medida que obtenemos más información. A medida que jugamos más y más rondas y obtenemos más y más datos, la posterior converge más cerca de los verdaderos valores de los parámetros, por lo que el "muestreo" aleatorio en el esquema de Thompson se hace más ajustado en torno a los valores de los parámetros que conducirán a la maximización de la recompensa inmediata. Por lo tanto, hay una tendencia implícita de este esquema a estar más "orientado a la búsqueda" al principio con poca información, y menos "orientado a la búsqueda" más tarde cuando hay muchos datos.
Ahora bien, dicho esto, un claro inconveniente del esquema de muestreo de Thompson es que no tiene en cuenta el número de rondas que quedan en el problema MAB. Este esquema se formula a veces sobre la base de un juego con rondas infinitas, y en este caso eso no es un problema. Sin embargo, en los problemas MAB con rondas finitas, es preferible tener en cuenta el número de rondas restantes para disminuir la "búsqueda" a medida que el número de rondas futuras disminuye. (Y en particular, la jugada óptima en la última ronda es ignorar completamente las búsquedas y apostar simplemente por el bandido con el mayor rendimiento esperado posterior). El esquema de Thompson no hace esto, por lo que jugará partidas de rondas finitas de una manera que es claramente subóptima en ciertos casos.
Me gustaría poder dar a esta respuesta varios pulgares arriba. Probablemente añadiría cómo actualizaría los posteriors - por ejemplo, si los posteriors se representaran como distribuciones normales - cómo se calculan las actualizaciones de la media y la desviación estándar de los posteriors. Digo esto porque yo mismo no sé
Lo intentaré y espero que os guste. Hay algunas fórmulas más abajo que podrían asustarte. No lo espero, porque haré todo lo posible para explicarlas de la manera más sencilla que pueda.
Estas son las dos fórmulas:
TL;DR
Thompson Sampling le permite
¿Probabilidad?
La probabilidad es algo que define cómo probablemente las cosas son. En este caso la probabilidad dice cómo probablemente es que recibimos la recompensa $r$ si se trata de una acción de juego $a$ en contexto $x$ . Por ejemplo, si llueve (¡contexto!) y coges un paraguas (¡acción!) te mantienes seco (¡premio! :) ). En cambio, si no llueve (¡contexto!) y coges un paraguas (¡acción!) tienes que cargar con un peso extra (¡recompensa negativa! :( ). Por lo tanto, la probabilidad es lo más importante que hay que entender. Si lo sabes todo sobre la probabilidad, es fácil actuar de forma óptima.
¿Qué pasa con ese extraño círculo?
Como habrás notado no escribí nada sobre ese extraño círculo $\theta$ que se llama theta. (Los matemáticos tienen la costumbre de indicar qué partes son las más difíciles dándoles letras griegas, lo que dificulta aún más su comprensión). Este $\theta$ representa el parámetro del modelo. Estos parámetros se utilizan cuando la relación entre el contexto+acciones y la recompensa es más difícil. Por ejemplo, un parámetro del modelo podría ser cuánto baja tu recompensa si te cae 1mm de lluvia encima de la cabeza. Otro parámetro del modelo podría ser cuánto disminuye tu recompensa si coges un paraguas. Acabo de decir que la probabilidad es lo principal que quieres entender, y que los parámetros del modelo son lo principal de la probabilidad. Si conoces los parámetros del modelo $\theta$ , sabes cómo se relaciona el contexto+acciones con la recompensa y es fácil actuar de forma óptima.
Entonces, ¿cómo podemos conocer estos parámetros del modelo para obtener la máxima recompensa?
Esta es la cuestión esencial para el problema del bandido de brazos múltiples. En realidad, tiene dos partes. Se quiere conocer con precisión los parámetros del modelo explorando todos los tipos de acciones en diferentes contextos. Pero si ya sabes qué acción es buena para un contexto específico, quieres explotar esa acción y obtener la mayor recompensa posible. Así que si no estás seguro de los parámetros de tu modelo $\theta$ es posible que quieras hacer una exploración adicional. Si estás bastante seguro de los parámetros de nuestro modelo $\theta$ También está bastante seguro de qué acción tomar. Esto es lo que se conoce como el compromiso de exploración versus explotación.
No has dicho nada sobre esto después
La clave de este comportamiento óptimo es su (des)certeza sobre los parámetros del modelo $\theta$ . Y la posterioridad dice exactamente eso: dadas todas las recompensas anteriores que obtuvimos por acciones anteriores en contextos anteriores, ¿cuánto se sabe de $\theta$ . Por ejemplo, si nunca has salido a la calle, no sabes lo infeliz que te vuelves cuando te llueve en la cabeza. En otras palabras, no tienes muy claro el parámetro del modelo de infelicidad cuando llueve sobre la cabeza. Si has estado alguna vez bajo la lluvia, con y sin paraguas, puedes empezar a aprender algo sobre este oscuro parámetro del modelo.
Ahora bien, ¿qué sugiere Thomson Sampling para hacer frente a todas estas incertidumbres?
El muestreo de Thomson propone algo muy sencillo: basta con elegir un parámetro aleatorio del modelo a posteriori, realizar una acción y observar lo que ocurre. Por ejemplo, si nunca has salido a la calle, el parámetro de infelicidad cuando llueve en la cabeza puede ser cualquier cosa. Así que elegimos uno, suponemos que nos sentimos muy infelices cuando nos llueve en la cabeza. Vemos que está lloviendo (contexto), así que cogemos un paraguas (acción) porque el parámetro de nuestro modelo nos dice que así podemos obtener la máxima recompensa. Y efectivamente, observas que te pones un poco de mal humor al caminar bajo la lluvia con un paraguas, pero no eres realmente infeliz. De esto aprendemos que lluvia+paraguas es malhumorado. La próxima vez que llueva vuelves a elegir una creencia al azar sobre lo que ocurre cuando la lluvia cae sobre tu cabeza. Esta vez puede ser que no te moleste en absoluto. Sin embargo, cuando estás a mitad de camino hacia tu destino te mojas y aprendes que la lluvia sin paraguas es realmente mala. Esto reduce tu incertidumbre sobre la infelicidad cuando llueve sobre la cabeza, porque ahora sabes que probablemente sea alta.
¡¡Esto suena tan simple!!
Sí, no es tan complejo. La parte difícil es el muestreo a partir de un parámetro posterior del modelo. Conseguir y mantener una distribución sobre todos los parámetros del modelo, que además sea apropiada para su problema específico, es difícil. Pero... es definitivamente factible :).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
