Desearía que hubiera uno.
Lamentablemente, no existe tal métrica. Es decir, no puede haber ninguna métrica que se pueda conectar y esperar que se correlacione positivamente con los resultados de la prueba A / B. Si lo hubiera, podríamos resolver el problema de inferencia causal general a partir de datos de observación (más sobre eso más adelante).
Dicho esto, hay varias métricas fuera de línea que podrían funcionar para un sistema de recomendación dado, pero solo si tenemos razones suficientes para creer que sus suposiciones serían válidas. La respuesta larga a continuación describe esas métricas y críticamente, sus suposiciones.
- Cómo identificar la ubicación de cualquier mensaje de texto usando ML o NLP
- ¿Cuál es el mejor algoritmo para descubrir todos los nodos de la red y mantener esa red en tiempo real?
- ¿Los analistas de datos serán reemplazados por aprendizaje automático e inteligencia artificial pronto?
- En PNL, ¿cómo se crean los corpus anotados?
- Como científico de datos, ¿qué te inspiró a seguir una carrera en ciencia de datos?
¿Por qué las métricas tradicionales fuera de línea no se correlacionan con las pruebas A / B?
Antes de analizar las métricas fuera de línea que son prometedoras, veamos por qué las métricas fuera de línea tradicionales del paradigma de prueba de tren de aprendizaje automático no funcionan.
En un escenario típico para la evaluación fuera de línea de un sistema de recomendación, tenemos uno o más algoritmos para probar contra un algoritmo en producción, y queremos saber cuál es mejor. Por simplicidad, supongamos que queremos optimizar una sola métrica, aunque en la práctica generalmente es apropiada una colección de diferentes métricas. También asumiremos que las calificaciones son la forma principal de comentarios de los usuarios sobre los artículos.
Podríamos crear un conjunto de datos a partir de la actividad anterior de los usuarios, dividirlo en conjuntos de entrenamiento, validación y prueba y luego entrenar el algoritmo en el conjunto de entrenamiento, ajustar los parámetros mediante validación cruzada en el conjunto de validación y evaluar el rendimiento de cada algoritmo en el conjunto de prueba . Esto sigue el estándar de oro de la práctica de aprendizaje automático, pero a menudo no proporciona una respuesta que se correlacione, incluso en la dirección de su efecto, con una prueba aleatoria A / B.
¿Por qué?
- Porque los datos pasados están muy sesgados por la preferencia de un usuario. Es más probable que los usuarios consuman y califiquen el contenido que les gusta. O, en el lenguaje de datos faltantes, las calificaciones no faltan al azar. [1] Eso significa que las calificaciones de 4/5 serían mucho más comunes, y cualquier algoritmo que funcione bien en elementos similares a lo que un usuario ya ha visto, y no en un amplio conjunto de elementos alternativos, igualmente relevantes, parecerá tener un mayor rendimiento que otro algoritmo que captura las preferencias del usuario en todo tipo de elementos. Véanse los documentos de Marlin et al. [2] y Schnabel y col. [3] para ejemplos simples sobre cómo puede suceder esto.
- Porque los datos pasados también están sesgados por el algoritmo de producción actual. Los usuarios no solo califican lo que les gusta, sino que también tienen más probabilidades de calificar lo que se les muestra. Eso significa que el conjunto de prueba en sí está sesgado hacia el algoritmo de producción; no podemos evaluar el rendimiento de un algoritmo de recomendación en un elemento que el usuario aún no ha calificado.
Combinados, estos dos efectos significan que un algoritmo que solo minimiza el error de predicción en elementos que un usuario ya ha visto, tiene la mejor oportunidad de obtener buenos resultados en las evaluaciones tradicionales fuera de línea. Es decir, en lugar de centrarse en la capacidad de un algoritmo para aprender las preferencias del usuario sobre un amplio conjunto de elementos, o nuevos elementos que deberían mostrarse a un usuario, este paradigma de prueba de tren es el más adecuado para encontrar un algoritmo que prediga el pasado de un usuario. Por ejemplo, un algoritmo trivial que predice una calificación alta para casi todos los elementos puede funcionar mejor en la evaluación fuera de línea que otros, seguramente mejores algoritmos. [4] No es sorprendente entonces, encontramos rutinariamente que los algoritmos que funcionan bien en la evaluación fuera de línea no cumplen con su promesa cuando se someten a una prueba A / B. Aquí hay una “crítica” del curso Coursera sobre sistemas de recomendación que describe mejor este problema.
Estimadores de puntaje de propensión inversa (IPS)
Una solución simple sería debiar de alguna manera los datos de actividad pasada para parecerse mejor a una prueba A / B. Esto se puede lograr al volver a ponderar las calificaciones anteriores de los usuarios, de una manera, que los elementos con todas las calificaciones (esperadas) tengan la misma probabilidad de ocurrir en los conjuntos de datos fuera de línea. Si conocemos el mecanismo de selección de cada usuario para elegir los elementos a calificar, entonces existe un procedimiento estándar de la literatura de inferencia causal para hacerlo. Asignamos una ponderación a cada calificación observada para un artículo que es inversamente proporcional a la probabilidad de que un usuario califique ese artículo, y luego calculamos la calificación promedio ponderada. Este método se llama estimación de puntaje de propensión inversa (IPS) y se ha utilizado en una amplia gama de campos, desde el desvanecimiento de las respuestas de la encuesta hasta el rendimiento de los anuncios en línea. [5]
Para un sistema de recomendación, esto significa que necesitamos estimar la probabilidad de calificación para cada par de elementos de usuario. Sin embargo, sin observar cómo los usuarios calificarán dada una muestra aleatoria de artículos, no tenemos los datos necesarios para estimar esta probabilidad. Como una aproximación, podemos suponer que las personas seleccionan artículos para calificar con una probabilidad proporcional a su calificación (esperada) para el artículo. [6] Luego, utilizando datos de actividades pasadas, podemos aproximar la probabilidad de que un usuario califique un elemento ([math] P_ {u, i} [/ math]) como proporcional a la calificación observada para cada elemento. Por ejemplo, la métrica de IPS para el error absoluto medio (MAE) se puede escribir como:
[matemáticas] \ textit {IPS Metric} = \ frac {1} {N} \ sum_ {u, i \ in TestSet} \ frac {| r_ {u, i} – \ hat {r} _ {u, i} |} {P_ {u, i}} [/ matemáticas]
donde [math] r_ {u, i} [/ math] es la calificación real, [math] \ hat {r} _ {u, i} [/ math] es la calificación pronosticada, y [math] N [/ math ] es el número total de clasificaciones. Para ser más precisos, también podríamos agregar otra información sobre el par usuario-elemento para estimar esta probabilidad, por ejemplo, características sobre el contenido del elemento o diferencias en los mecanismos de selección de los usuarios. Se ha demostrado que la métrica IPS es mejor que las métricas tradicionales fuera de línea para la música y la recomendación de comercio electrónico. [7] Sin embargo, una limitación clave es que nunca podemos saber cuándo hemos aproximado suficientemente el proceso de selección de cada usuario.
Evaluadores fuera de política
Otra forma de pensar sobre un sistema de recomendación es en términos de aprendizaje por refuerzo. En el aprendizaje por refuerzo, el objetivo es capacitar a un agente (por ejemplo, un robot) para que realice una tarea compleja. Sin embargo, a diferencia del aprendizaje supervisado, donde los resultados para todo el conjunto de datos se conocen de antemano, aquí el agente conoce el resultado (recompensa) solo después de realizar una acción. Por lo tanto, necesita encontrar una política óptima de tomar medidas que maximicen la recompensa a largo plazo para el agente. Esto es adecuado para robots que aprenden a mover, volar u operar instrumentos, pero como veremos, es igualmente aplicable a un sistema de recomendación.
En el mundo del ‘sistema de recomendación’, una acción es mostrarle a un usuario un artículo, la recompensa es la calificación del usuario de ese artículo, y una política es simplemente el algoritmo que selecciona los artículos para mostrar a un usuario. Al igual que un robot podría estar interesado en conocer las recompensas a largo plazo de las políticas alternativas que podría haber tomado, un sitio web puede querer estimar las recompensas a largo plazo de los algoritmos de recomendación alternativos que podría haber intentado.
En general, este es un problema difícil. La única excepción es cuando podemos inyectar algo de aleatorización en el algoritmo de producción, usando un caso especial de aprendices de refuerzo llamados bandidos contextuales . Para simplificar, suponga que un algoritmo de producción elige al azar mostrar sus recomendaciones el 90% del tiempo, pero también muestra elementos aleatorios uniformes el 10% del tiempo (esto se llama algoritmo greedy [math] \ epsilon [/ math]). Luego, las calificaciones de estos elementos seleccionados al azar se pueden considerar como una muestra representativa de las preferencias de las personas. Probar cualquier algoritmo nuevo en este conjunto de calificaciones debería dar una estimación que se espera que esté cerca de los resultados de una prueba A / B, como se mostró para una recomendación de noticias en Yahoo. [8] [9] [10] El apagado -la métrica del evaluador de políticas para MAE ahora se ve así:
[matemáticas] \ textit {Explorar métrica fuera de política} = \ frac {1} {N} \ sum_ {u, i \ en TestSet} | r_ {u, i} – \ hat {r} _ {u, i} | [/ matemáticas]
Sin embargo, en la práctica, una estrategia de exploración tan pura puede ser perjudicial para la experiencia del usuario para [math] \ epsilon = 10 \% [/ math] de los usuarios. Afortunadamente, hay estimadores fuera de la política que nos permiten hacer una compensación entre explorar y explotar . Por ejemplo, podemos usar aleatorización restringida, como hacer que la probabilidad de seleccionar un elemento, [math] P_a [/ math], sea proporcional a su puntaje de relevancia. [11] Este tipo de mezcla entre explore-exploit también se ha demostrado que dar una estimación que concuerde con una prueba A / B, [12] porque nuestro esquema de aleatorización explícito proporciona una forma confiable de estimar [matemáticas] P_a [/ matemáticas] (aunque ahora podría requerir más datos que antes). La métrica fuera de política se convierte en [*]:
[matemáticas] \ textit {Explorar-explotar métrica fuera de política} = \ frac {1} {N} \ sum_ {u, i \ in TestSet} \ frac {| r_ {u, i} – \ hat {r} _ {u, i} |} {P_a} [/ math]
Como puede ver, el ingrediente clave aquí es la capacidad de estimar [math] P_a [/ math] de manera confiable. Si hay una exploración implícita en los datos de registro pero no sabemos [math] P_a [/ math] a priori, entonces todas las apuestas están canceladas. Existen estimadores complicados para [matemáticas] P_a [/ matemáticas] [13], pero dependiendo de los supuestos, la estimación puede o no coincidir con los resultados reales de la prueba A / B. Una limitación final es que las estimaciones fuera de política funcionan mejor cuando hay un pequeño número de acciones. Si necesitamos estimar la métrica sobre millones de elementos (como en películas o canciones), este enfoque puede requerir muchos datos de exploración antes de ser utilizables. Para obtener más detalles, consulte este excelente tutorial de Lihong Li.
Estimaciones de experimentos naturales.
Los dos métodos anteriores son útiles, pero comparten su talón de Aquiles : la suposición de que uno puede estimar con precisión la probabilidad de seleccionar un elemento por parte de los usuarios o mediante un algoritmo de recomendación. En muchos casos esto no es posible.
En lugar de tratar de modelar cómo se generaron los datos registrados, el tercer enfoque intenta encontrar variaciones naturales en los datos que se asemejan a las pruebas A / B. En otras palabras, en lugar de modelar todos los datos, encontramos subconjuntos donde se puede suponer que los supuestos de la prueba A / B son válidos. Encontrar tales experimentos naturales ha sido popular en las ciencias sociales y biomédicas durante mucho tiempo, y también puede aplicarse de manera fructífera a los sistemas de recomendación.
La tarea crítica es encontrar las condiciones bajo las cuales los datos observados pueden tratarse como casi al azar, como en una prueba A / B. Consideremos un ejemplo. Supongamos que realizamos una prueba A / B para un nuevo algoritmo B, pero descubrimos que el algoritmo de referencia A era mejor. Entonces podríamos mejorar el algoritmo B ligeramente a B ‘, y nuevamente querríamos probarlo contra A. En lugar de ejecutar otro experimento, los experimentos naturales nos permiten registrar datos del experimento anterior para comparar los dos algoritmos.
Ingenuamente, uno podría usar las calificaciones proporcionadas durante el experimento como un conjunto de prueba para el nuevo algoritmo B ‘, pero sufre el mismo sesgo de selección que discutimos anteriormente. Para resolver este problema, intentemos encontrar un experimento natural en los datos. Dado que B y B ‘son algoritmos relacionados, deberíamos esperar que sus recomendaciones sean más similares entre sí que con las recomendaciones de A. Por lo tanto, en los datos de registro experimentales, esperamos tener muchas más coincidencias para las clasificaciones de elementos del conjunto aleatorio de usuarios que se asignaron a B frente a A. Es decir, retrospectivamente , podemos pensar en la asignación aleatoria de usuarios a A y B como un estímulo para que esos usuarios vean recomendaciones de B ‘o A. Este es el diseño clásico de estímulo para experimentos aleatorios, y puede analizarse para estimar el efecto de usar B’ en lugar de A usando técnicas estándar de estimación de variables instrumentales [14]. El estimador se puede derivar como:
[matemáticas] \ textit {Métrica variable instrumental} = \ frac {\ bar {r} _ {Z = AlgB} – \ bar {r} _ {Z = AlgA}} {\ bar {I} (u, i \ in RecB ‘) _ {Z = AlgB} – \ bar {I} (u, i \ en RecB’) _ {Z = AlgA}} [/ math]
donde restamos la calificación promedio de las dos subpoblaciones aleatorias del experimento A / B, y la dividimos por el número medio de recomendaciones de B ‘([matemáticas] RecB’ [/ matemáticas]) que también se mostraron a los usuarios en El experimento A / B. [math] I [/ math] es la función del indicador que es 1 cada vez que el algoritmo B ‘recomienda el par [math] (u, i) [/ math] en el experimento A / B.
Lamentablemente, esta capacidad para derivar estimaciones sin saber nada sobre los algoritmos que generan los datos no es gratuita. La búsqueda de experimentos naturales depende en gran medida del objetivo en cuestión; un instrumento para el algoritmo B ‘puede no funcionar bien para otro algoritmo C. Además, el éxito (y la validez) a menudo depende de la creatividad del investigador para encontrar un experimento natural y experiencia para justificar sus suposiciones.
El trabajo reciente aborda parcialmente estos problemas mediante la automatización del descubrimiento de experimentos naturales. En lugar de comenzar con argumentos lógicos sobre la validez de un experimento natural y luego encontrarlos en los datos de registro, esta línea de trabajo caracteriza las propiedades de los experimentos aleatorios, y luego busca en los registros de recomendaciones para encontrar todos esos experimentos naturales. Por ejemplo, podemos estimar el CTR adicional que agrega un sistema de recomendación, más allá de lo que hubiera sucedido en su ausencia, al usar cambios repentinos en el tráfico como una variable de estímulo (o instrumental). [15] Tales estimaciones tienen el beneficio de la generalización a un conjunto más amplio de elementos, pero aún están sujetas a la suposición central detrás de los experimentos naturales: que los subconjuntos de datos son posiblemente aleatorios como si vinieran de una prueba A / B.
Entonces, ¿qué métrica elegir?
Si es posible inyectar aleatorización en el algoritmo de producción, entonces la respuesta es simple: los evaluadores fuera de política basados en bandidos contextuales son la mejor opción.
De lo contrario, cualquiera de los estimadores puede funcionar, según el contexto de un sistema de recomendación y la aplicabilidad de los supuestos. Una regla general es intentar múltiples enfoques con diferentes supuestos, o combinarlos con técnicas como la estimación doblemente sólida [16]. En la medida en que sus resultados coincidan, hay una mejor posibilidad de correlación con una prueba A / B futura que con un solo método. Algunas veces, estos enfoques también pueden ser complementarios. Por ejemplo, se pueden usar técnicas como experimentos naturales o IPS para inicializar la política de exploración de bandidos contextuales.
Finalmente, aunque esta respuesta tiende a transmitir una perspectiva optimista, es una buena idea moderar nuestras expectativas. Sin suposiciones importantes o control del procedimiento de recopilación de datos, en el mejor de los casos podemos utilizar métricas fuera de línea como un mecanismo de filtrado para seleccionar qué experimentos ejecutar, no como su sustituto. Esto se debe a que esperamos responder una pregunta causal: ¿Qué sucedería si el algoritmo A se reemplaza por B? Con datos estadísticos anteriores, sin ningún dato sobre el reemplazo real. Con solo datos de registro anteriores, no podemos encontrar la respuesta correcta, y nunca podemos saber si tenemos la respuesta correcta.
[*] Si la métrica Explore-Exploit Off-policy se parece a la métrica IPS, no es una coincidencia. Ambos están tratando de controlar el sesgo de selección. La única diferencia es que en la métrica de IPS, estamos modelando el proceso de selección de un usuario para calificar, y en la métrica fuera de la política, estamos modelando el proceso de selección de un algoritmo para mostrar un elemento. Ambas son equivalentes siempre y cuando supongamos que un usuario da algunos comentarios para cada elemento que se muestra (como un clic), pero no cuando hay comentarios explícitos de dicha calificación. Por lo tanto, intuitivamente, los bandidos contextuales hacen la suposición simplificada de que los usuarios proporcionan comentarios sobre cada elemento que se les muestra. El trabajo reciente intenta remediar esto, suponiendo que a los usuarios se les muestra una lista de artículos, y formulando la recompensa como una composición de recompensas para cada artículo en la lista. [17] [18]
Notas al pie
[1] https://arxiv.org/ftp/arxiv/pape…
[2] http://openscholar.cs.umass.edu/…
[3] https://www.cs.cornell.edu/peopl…
[4] https://www.cs.cornell.edu/peopl…
[5] Más dinero por su dinero: evaluación de nuevas características para anunciantes en línea
[6] http://www.cs.toronto.edu/~zemel…
[7] https://www.cs.cornell.edu/peopl…
[8] http://www.research.rutgers.edu/…
[9] http://www.jmlr.org/proceedings/…
[10] http://www.gatsby.ucl.ac.uk/~chu…
[11] http://research.microsoft.com/pu…
[12] http://research.microsoft.com/pu…
[13] http://research.microsoft.com/pu…
[14] Econometría principalmente inofensiva:
[15] [1510.05569] Estimación del impacto causal de los sistemas de recomendación a partir de datos de observación
[16] Evaluación doblemente robusta fuera de la política para el aprendizaje por refuerzo
[17] http://www2016.net/proceedings/p…
[18] https://arxiv.org/pdf/1605.04812…
