Hispanopedia Wiki
Articulo de referencia

Muestreo de Thompson

Ejemplo concreto del muestreo de Thompson aplicado a la simulación de la evaluación de la eficacia del tratamiento. El muestreo de Thompson , [ 1 ] [ 2 ] [ 3 ] llamado así en ho...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo concreto del muestreo de Thompson aplicado a la simulación de la evaluación de la eficacia del tratamiento.

El muestreo de Thompson , [ 1 ] [ 2 ] [ 3 ] llamado así en honor a William Rae Thompson , es una heurística para elegir acciones que aborden el dilema exploración-explotación en el problema del bandido multi-brazo . Consiste en elegir la acción que maximiza la recompensa esperada con respecto a una creencia extraída aleatoriamente.

Descripción

Consideremos un conjunto de contextosincógnita{\displaystyle {\mathcal {X}}}, un conjunto de accionesA{\displaystyle {\mathcal {A}}}y recompensas enR{\displaystyle \mathbb {R} }El objetivo del jugador es realizar acciones en los distintos contextos, como maximizar las recompensas acumuladas. Específicamente, en cada ronda, el jugador obtiene un contexto.incógnita∈incógnita{\displaystyle x\in {\mathcal {X}}}, juega una accióna∈A{\displaystyle a\in {\mathcal {A}}}y recibe una recompensar∈R{\displaystyle r\in \mathbb {R} }siguiendo una distribución que depende del contexto y de la acción emitida.

Los elementos del muestreo de Thompson son los siguientes: [ 3 ] : sec. 4

  1. una función de probabilidadPAG(r|θ,a,incógnita){\displaystyle P(r|\theta ,a,x)};
  2. un conjuntoΘ{\displaystyle \Theta }de parámetrosθ{\displaystyle \theta }de la distribución der{\displaystyle r};
  3. una distribución previaPAG(θ){\displaystyle P(\theta )}en estos parámetros;
  4. tripletes de observaciones pasadasD={(incógnita;a;r)}{\displaystyle {\mathcal {D}}=\{(x;a;r)\}};
  5. una distribución posteriorPAG(θ|D)∝PAG(D|θ)PAG(θ){\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}, dóndePAG(D|θ){\displaystyle P({\mathcal {D}}|\theta )}es la función de verosimilitud.

El muestreo de Thompson consiste en reproducir la accióna∗∈A{\displaystyle a^{\ast }\in {\mathcal {A}}}según la probabilidad de que maximice la recompensa esperada; accióna∗{\displaystyle a^{\ast }}se elige con probabilidad [ 3 ] : Algoritmo 4

∫I[mi(r|a∗,incógnita,θ)=máximoa′mi(r|a′,incógnita,θ)]PAG(θ|D)dθ,{\displaystyle \int \mathbb {I} \left[\mathbb {E} (r|a^{\ast },x,\theta )=\max _{a'}\mathbb {E} (r|a',x,\theta )\right]P(\theta |{\mathcal {D}})d\theta ,}

dóndeI{\displaystyle \mathbb {I} }es la función indicadora .

En la práctica, la regla se implementa mediante muestreo. En cada ronda, los parámetrosθ∗{\displaystyle \theta ^{\ast }}se muestrean de la parte posteriorPAG(θ|D){\displaystyle P(\theta |{\mathcal {D}})}, [ 3 ] : 7 y una accióna∗{\displaystyle a^{\ast }}elegido que maximizami[r|θ∗,a∗,incógnita]{\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}, es decir, la recompensa esperada dados los parámetros muestreados, la acción y el contexto actual. Conceptualmente, esto significa que el jugador instancia sus creencias aleatoriamente en cada ronda según la distribución posterior y luego actúa de forma óptima según ellas. En la mayoría de las aplicaciones prácticas, resulta computacionalmente oneroso mantener y muestrear a partir de una distribución posterior sobre modelos. Por ello, el muestreo de Thompson se utiliza a menudo junto con técnicas de muestreo aproximado. [ 3 ] : sec. 5

Historia

El muestreo de Thompson fue descrito originalmente por Thompson en 1933. [ 1 ] Posteriormente fue redescubierto numerosas veces de forma independiente en el contexto de problemas de bandidos multi-brazos. [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] Una primera prueba de convergencia para el caso del bandido se ha mostrado en 1997. [ 4 ] La primera aplicación a procesos de decisión de Markov fue en 2000. [ 6 ] Un enfoque relacionado (ver regla de control bayesiana ) fue publicado en 2010. [ 5 ] En 2010 también se demostró que el muestreo de Thompson es instantáneamente autocorrectivo . [ 9 ] Los resultados de convergencia asintótica para bandidos contextuales fueron publicados en 2011. [ 7 ] El muestreo de Thompson ha sido ampliamente utilizado en muchos problemas de aprendizaje en línea, incluyendo pruebas A/B en diseño de sitios web y publicidad en línea, [ 10 ] y aprendizaje acelerado en toma de decisiones descentralizada. [ 11 ] Se ha propuesto un algoritmo de muestreo de Thompson doble (D-TS) [ 12 ] para bandidos duelistas , una variante del MAB tradicional, donde la retroalimentación se presenta en forma de comparación por pares.

Relación con otros enfoques

Coincidencia de probabilidad

La coincidencia de probabilidades es una estrategia de decisión en la que las predicciones de pertenencia a una clase son proporcionales a las tasas base de cada clase. Por lo tanto, si en el conjunto de entrenamiento se observan ejemplos positivos el 60 % de las veces y ejemplos negativos el 40 % de las veces, el observador que utiliza una estrategia de coincidencia de probabilidades predecirá (para ejemplos sin etiquetar) una etiqueta de clase "positivo" en el 60 % de las instancias y una etiqueta de clase "negativo" en el 40 % de las instancias.

Regla de control bayesiana

Se ha demostrado que una generalización del muestreo de Thompson a entornos dinámicos y estructuras causales arbitrarias, conocida como regla de control bayesiana , es la solución óptima al problema de codificación adaptativa con acciones y observaciones. [ 5 ] En esta formulación, un agente se conceptualiza como una mezcla de un conjunto de comportamientos. A medida que el agente interactúa con su entorno, aprende las propiedades causales y adopta el comportamiento que minimiza la entropía relativa al comportamiento con la mejor predicción del comportamiento del entorno. Si estos comportamientos se han elegido de acuerdo con el principio de máxima utilidad esperada, entonces el comportamiento asintótico de la regla de control bayesiana coincide con el comportamiento asintótico del agente perfectamente racional.

La configuración es la siguiente.a1,a2,…,aT{\displaystyle a_{1},a_{2},\ldots ,a_{T}}sean las acciones emitidas por un agente hasta el momentoT{\displaystyle T}y dejaro1,o2,…,oT{\displaystyle o_{1},o_{2},\ldots ,o_{T}}sean las observaciones recopiladas por el agente hasta el momentoT{\displaystyle T}. Luego, el agente emite la acciónaT+1{\displaystyle a_{T+1}}con probabilidad: [ 5 ]

PAG(aT+1|a^1:T,o1:T),{\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}

donde la notación de "sombrero"a^t{\displaystyle {\hat {a}}_{t}}denota el hecho de queat{\displaystyle a_{t}}es una intervención causal (ver Causalidad ), y no una observación ordinaria. Si el agente sostiene creenciasθ∈Θ{\displaystyle \theta \in \Theta }sobre sus comportamientos, entonces la regla de control bayesiana se convierte en

PAG(aT+1|a^1:T,o1:T)=∫ΘPAG(aT+1|θ,a^1:T,o1:T)PAG(θ|a^1:T,o1:T)dθ{\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T})=\int _{\Theta }P(a_{T+1}|\theta ,{\hat {a}}_{1:T},o_{1:T})P(\theta |{\hat {a}}_{1:T},o_{1:T})\,d\theta },

dóndePAG(θ|a^1:T,o1:T){\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}es la distribución posterior sobre el parámetroθ{\displaystyle \theta }acciones dadasa1:T{\displaystyle a_{1:T}}y observacioneso1:T{\displaystyle o_{1:T}}.

En la práctica, el control bayesiano equivale a muestrear, en cada paso de tiempo, un parámetro.θ∗{\displaystyle \theta ^{\ast }}de la distribución posteriorPAG(θ|a^1:T,o1:T){\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}donde la distribución posterior se calcula utilizando la regla de Bayes considerando únicamente las probabilidades (causales) de las observaciones.o1,o2,…,oT{\displaystyle o_{1},o_{2},\ldots ,o_{T}}e ignorando las probabilidades (causales) de las accionesa1,a2,…,aT{\displaystyle a_{1},a_{2},\ldots ,a_{T}}y luego mediante el muestreo de la acciónaT+1∗{\displaystyle a_{T+1}^{\ast }}de la distribución de accionesPAG(aT+1|θ∗,a^1:T,o1:T){\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}.

Algoritmos de límite superior de confianza (UCB)

El muestreo de Thompson y los algoritmos de límites de confianza superiores comparten una propiedad fundamental que subyace a muchas de sus garantías teóricas. En términos generales, ambos algoritmos asignan esfuerzo exploratorio a acciones que podrían ser óptimas y, en este sentido, son "optimistas". Aprovechando esta propiedad, se pueden traducir los límites de arrepentimiento establecidos para los algoritmos UCB a límites de arrepentimiento bayesianos para el muestreo de Thompson [ 13 ] o unificar el análisis de arrepentimiento en ambos algoritmos y en muchas clases de problemas. [ 14 ]

Referencias

  1. 1 2 Thompson, William R. "Sobre la probabilidad de que una probabilidad desconocida supere a otra en vista de la evidencia de dos muestras" . Biometrika , 25(3–4):285–294, 1933.
  2. ↑ Thompson, WR (1935). Sobre la teoría de la distribución. American Journal of Mathematics , 57(2), 450-456.
  3. 1 2 3 4 5 Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband y Zheng Wen (2018), "Un tutorial sobre el muestreo de Thompson", Foundations and Trends in Machine Learning: Vol. 11: No. 1, pp. 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
  4. 1 2 J. Wyatt. Exploración e inferencia en el aprendizaje por refuerzo . Tesis doctoral, Departamento de Inteligencia Artificial, Universidad de Edimburgo. Marzo de 1997.
  5. 1 2 3 4 PA Ortega y DA Braun. "Un principio de entropía relativa mínima para el aprendizaje y la actuación", Journal of Artificial Intelligence Research , 38, páginas 475–511, 2010, http://arxiv.org/abs/0810.3605
  6. 1 2 MJA Strens. "Un marco bayesiano para el aprendizaje por refuerzo", Actas de la Decimoséptima Conferencia Internacional sobre Aprendizaje Automático , Universidad de Stanford, California, 29 de junio-2 de julio de 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
  7. 1 2 BC May, BC, N. Korda, A. Lee y DS Leslie. "Muestreo bayesiano optimista en problemas de bandidos contextuales". Informe técnico, Grupo de Estadística, Departamento de Matemáticas, Universidad de Bristol, 2011.
  8. ↑ Chapelle, Olivier y Lihong Li. «Una evaluación empírica del muestreo de Thompson». Avances en sistemas de procesamiento de información neuronal. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
  9. 1 2 O.-C. Granmo. "Resolución de problemas de bandidos de Bernoulli de dos brazos mediante un autómata de aprendizaje bayesiano", Revista internacional de computación inteligente y cibernética , 3 (2), 2010, 207-234.
  10. ↑ Clarke, Ian (22 de septiembre de 2011). "Pruebas A/B proporcionales" . Archivado del original el 4 de mayo de 2013. Recuperado el 30 de abril de 2013 .
  11. ↑ Granmo, OC; Glimsdal, S. (2012). "Aprendizaje bayesiano acelerado para la toma de decisiones descentralizada basada en el problema del bandido de dos brazos con aplicaciones al juego de Goore". Applied Intelligence . 38 (4): 479– 488. doi : 10.1007/s10489-012-0346-z . hdl : 11250/137969 . S2CID 8746483 . 
  12. ↑ Wu, Huasen; Liu, Xin; Srikant, R (2016), Muestreo de Thompson doble para bandidos en duelo , arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
  13. ↑ Russo, Daniel J.; Van Roy, Benjamin (2014). "Aprendizaje para optimizar mediante muestreo posterior". Matemáticas de la investigación operativa . 39 (4): 1221– 1243. arXiv : 1301.2609 . doi : 10.1287/moor.2014.0650 .
  14. ↑ Daniel J. Russo y Benjamin Van Roy (2013), "Dimensión de eluder y complejidad de la muestra de la exploración optimista", Advances in Neural Information Processing Systems 26, pp. 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf
Lecturas relacionadas
6 articulos
HeurísticoUna heurística [1] o técnica heurística ( resolución de problemas , atajo mental , regla empírica ) [2] [3] [4] [5] es cualquier enfoque para la re...Bandido de múltiples brazosBandido de múltiples brazosEn teoría de probabilidad y aprendizaje automático , el problema del bandido de múltiples brazos (a veces llamado el problema del bandido de K - [1...Función de verosimilitudFunción de verosimilitudUna función de verosimilitud (a menudo llamada simplemente probabilidad ) mide qué tan bien un modelo estadístico explica los datos observados calc...Probabilidad previaProbabilidad previaUna distribución de probabilidad previa de una cantidad incierta, a menudo llamada simplemente la distribución previa , es su distribución de proba...Probabilidad posteriorProbabilidad posteriorLa probabilidad posterior es un tipo de probabilidad condicional que resulta de actualizar la probabilidad previa con información resumida por la p...Función indicadoraFunción indicadoraEn matemáticas , una función indicadora o función característica de un subconjunto de un conjunto es una función que asigna los elementos del subco...