Me sorprendí hoy, una vez más por 100…01 día consecutivo, sosteniendo mi caja de cena sin abrir mientras buscaba en Netflix un programa para ver mientras masticaba mi comida. Mi feed está lleno de demasiados romances asiáticos y sugerencias estadounidenses sobre la mayoría de edad, probablemente basadas en una serie o dos de estas categorías que vi hace como uno o dos meses. “No hay nada que ver aquí…” – suspiré mientras terminaba de leer todas las sinopsis, sintiéndome seguro de que podía predecir cómo se revelaría la trama. Saqué mi opción alternativa de entretenimiento, Tiktok, mientras inconscientemente pensaba para mis adentros que probablemente necesitaré No interesado algunos vídeos y Como, Ahorrar otros para… recomendar el algoritmo que me envía un nuevo flujo de contenido hoy.
Los sistemas de recomendación (RecSys) pueden considerarse un algoritmo tan establecido, que se ha implantado profundamente en nuestra vida cotidiana, hasta el punto de que, en la escala de 1 a Chat-GPT, se siente casi como una tendencia de los 80 tanto para el académico. y el mundo no académico. Sin embargo, no es en absoluto un algoritmo casi perfecto. Los desafíos éticos, sociales, técnicos y legales que conlleva el funcionamiento de una aplicación de recomendación nunca han estado a la vanguardia de la investigación (como es el caso de la mayoría de los demás productos tecnológicos…). La injusticia de un grupo selecto y la violación de la privacidad son ejemplos de las preocupaciones populares que giran en torno a RecSys y que las empresas que lo implementaron aún no abordan completamente. Además, existen muchas cuestiones más sutiles a las que rara vez se les da suficiente deliberación, una de las cuales es la pérdida de autonomía en el proceso de toma de decisiones de un individuo. Un RecSys “poderoso” sin duda puede empujar a los usuarios en una dirección particular [2]haciéndoles comprar, mirar, pensar, creer en algo que no habrían hecho si no hubieran estado sujetos a tal manipulación.
Por lo tanto, quiero escribir una serie a lo largo de mi trayectoria en la escuela de posgrado a medida que comienzo a aprender y profundizar en RecSys, sus fortalezas y deficiencias… ¡todo desde cero! Y me imagino que puede empezar pensando en películas y… ¡Thompson Sampling!
Thompson Sampling (TS) es uno de los algoritmos fundamentales no solo en la literatura sobre sistemas de recomendación, sino también en el aprendizaje por refuerzo. Podría decirse que es una mejor prueba A/B en entornos de aprendizaje en línea, como lo explica claramente Samuele Mazzanti en este increíble artículo. En términos simples, en el contexto de la recomendación de películas, TS intenta identificar la mejor película para recomendarme que maximizará las posibilidades de que haga clic para verla. Puede hacerlo de manera efectiva usando relativamente menos datos, ya que permite que los parámetros se actualicen cada vez que me observa hacer clic o no hacer clic en una película. En términos generales, esta característica dinámica permite a TS tener en cuenta, además de mi historial de reproducciones y las series marcadas, factores en tiempo real como la navegación o los resultados de búsqueda dentro de la aplicación que estoy creando en ese momento para darme la información. sugerencia más adecuada. Sin embargo, en este tutorial para principiantes, veamos un análisis simplificado a continuación.
¡Desglosémoslo aún más!
Considere estas 3 películas, para las cuales, por sorprendentes que sean, yo, de manera bastante controvertida, tengo mi propia clasificación personal. De estas 3 películas, digamos, hay una que volveré a ver al 100 % si aparece en mi feed, una que es muy poco probable que vuelva a ver (5 %) y una en la que hay un 70 % de posibilidades de que haga clic. miro cada vez que lo veo. TS obviamente no tiene esta información sobre mí de antemano y su objetivo es conocer mi comportamiento para, como dice la intuición común, recomendarme la película que sabe que seguramente haré clic en ver.
En el algoritmo TS, el flujo de trabajo principal es el siguiente:
- Acción: TS me sugiere una película específica, entre cientos de otras.
- Resultado: Decido que la película me parece bastante interesante y hago clic para verla, o la encuentro aburrida y salgo de la página después de leer la sinopsis.
- Premio: Puede considerarse como el número de “puntos” que obtiene TS si hago clic para ver una determinada película o si TS falla si no hago clic. En la configuración básica de recomendación de películas o anuncios, podemos tratar la recompensa como un equivalente al resultado. , entonces 1 clic en la película = ¡1 punto!
- Actualizar Conocimiento: TS registra mi elección y actualiza su creencia sobre qué película es mi favorita.
- Repetir paso 1 (puede ser dentro de mi sesión de navegación actual, o a la hora de cenar al día siguiente), pero ahora con algunos conocimientos adicionales sobre mis preferencias.
Exploración/Explotación
Este es el término más utilizado en esta literatura y también es lo que distingue a TS y otros algoritmos relacionados. El paso 5 anterior es donde entra en juego esta lógica. En el mundo TS, todo tiene cierto grado de incertidumbre. Que beba café con leche tres veces y matcha cinco veces en una semana no significa necesariamente que amo el matcha más que el café con leche, ¿qué pasa si es solo esa semana (y en realidad estoy bebiendo más café con leche que matcha en promedio por semana)? Por esta razón, todo en TS está representado por algún tipo de distribución, en lugar de solo números individuales.
Al principio, TS obviamente tiene mucha incertidumbre sobre mi preferencia por las películas, por lo que su prioridad es explorar Esto al darme muchas sugerencias de películas diferentes para poder observar mi respuesta a las sugerencias. Después de algunos clics y saltos, TS puede descubrir las películas en las que tiendo a hacer clic y las películas que no producen ningún beneficio y, por lo tanto, ha ganado más confianza en qué película presentarme la próxima vez. Aquí es cuando TS comienza a explotar las opciones muy gratificantes, donde me da la película que hago clic para ver con frecuencia, pero aún deja algo de espacio para una mayor exploración. La confianza aumenta a medida que llegan más observaciones, lo que, en casos simples, llegará al punto en que el trabajo de exploración ahora es mínimo, ya que TS ya tiene mucha confianza para explotar la recomendación que brinda muchas recompensas.
Por lo tanto, a menudo se hace referencia a la exploración versus la explotación como la compensación o el dilema porque demasiada exploración (es decir, poca eliminación de opciones de bajo valor a pesar de que ya se ha obtenido suficiente evidencia para saber que dichas opciones no son óptimas) e incurre en muchas pérdidas, demasiada explotación (es decir, eliminar demasiadas opciones demasiado rápido) y es probable que elimines falsamente la verdadera acción óptima.
Como en el gráfico de matcha-latte anterior, TS trabaja con diferentes tipos de distribuciones para comprender nuestra preferencia por diferentes opciones. En los casos más básicos de películas (y también de anuncios), solemos utilizar el combo Beta-Bernoulli.
Distribución de Bernoulli es una distribución discreta en la que sólo hay dos resultados posibles: 1 y 0. La distribución de Bernoulli consta de un solo parámetro, lo que indica la probabilidad de que alguna variable, digamos Y, sea 1. Entonces, si decimos Y~ Bern(p) , y por ejemplo, p = 0,7, eso significa que Y tiene 0,7 posibilidades de tener el valor de 1, y 1–p = 1–0,7 = 0,3 posibilidades de ser 0. Por lo tanto, la distribución de Bernoulli es adecuada para modelar la recompensa (también resultado en nuestro caso) porque nuestra recompensa solo tiene resultado binario: Se hizo clic o No hecho clic.
Por otro lado, la distribución Beta se utiliza para modelar la creencia de TS con respecto a mis intereses cinematográficos. La distribución Beta toma dos parámetros, alfa y beta, que a menudo se consideran el número de éxitos y fracasos, respectivamente, y ambos tienen que ser ≥ 1. Por lo tanto, es adecuado usar la distribución Beta para modelar el número de veces que Haga clic en Ver y la cantidad de veces que me salto una película. Echemos un vistazo a un ejemplo. En este caso, se trata de 3 distribuciones beta diferentes que representan 3 películas, más de 10 observaciones, por lo que el número total de clics y omisiones para las 3 películas es el mismo (10), pero las tasas de clics y omisiones son diferentes. Para la película 1, hago clic en Ver 2 veces (alfa = 2) y me salto 8 veces (beta = 8); para la película 2, hago clic en Ver 5 veces y me salto 5 veces; Para la película 3, hago clic en Ver 8 veces y me salto 2.
Según el gráfico, podemos ver que la probabilidad de que vuelva a ver la película 2 alcanza un máximo de alrededor del 50%, mientras que esta probabilidad para la película 1 es mucho menor, por ejemplo. Podemos pensar en las curvas aquí como la probabilidad de probabilidad (de que vuelva a ver una película), por lo que la distribución Beta es ideal para representar la creencia de TS sobre mis preferencias cinematográficas.
En esta sección, lo ayudaré a obtener una comprensión clara de la implementación del algoritmo y de la metodología. En primer lugar, aquí hay un fragmento del algoritmo Thompson Sampling, en pseudocódigo y en Python. El pseudocódigo está tomado de un libro sorprendente sobre TS, llamado Un tutorial sobre el muestreo de Thompson [Russo, 2017].