16.1 NetFlix: Matrix Completion
Content and Collaborative filtering
Content and Collaborative Filtering2
Prof Steven Burnton, Washington University
Martix Completion and Norms
1. Introducción
El uso de sistemas de recomendación se ha disparado durante la última década, haciendo que las recomendaciones personalizadas sean ubicuas en línea. La mayoría de las principales empresas, incluidas Google, Facebook, Twitter, LinkedIn, Netflix, Amazon, Microsoft, Yahoo !, eBay, Pandora, Spotify y muchas otras utilizan sistemas de recomendación (RS) dentro de sus servicios. Estos sistemas se utilizan para recomendar una amplia gama de artículos, incluidos productos de consumo, películas, canciones, amigos, artículos de noticias, restaurantes y varios otros.
Los sistemas de recomendación constituyen una tecnología de misión crítica en varias empresas. Por ejemplo, Netflix informa que al menos el 75% de sus descargas y alquileres provienen de su RS, lo que lo hace de importancia estratégica para la empresa.
De alguna manera, los sistemas que producen estas recomendaciones son sofisticados,incorporan una variedad de señales sobre las características de los usuarios. Más importante aún, las recomendaciones son de calidad significativa en promedio. En las pruebas empíricas, las personas eligen los elementos sugeridos con mucha más frecuencia que los elementos sugeridos basándose en algoritmos de referencia no personalizados, como la popularidad general.
De otras formas, los sistemas que producen estas recomendaciones son a veces notablemente malos. Ocasionalmente, hacen recomendaciones que son vergonzosas para el sistema, como recomendar a un miembro de la facultad un libro introductorio de la serie "para tontos" sobre un tema en el que ella es experta. O continúan recomendando elementos que el usuario ya no necesita.
Los sistemas de recomendación son un campo de investigación muy activo en la actualidad. Para proporcionar una comprensión del estado del arte de los sistemas de recomendación, este artículo comienza con un poco de historia, que culminó en el desafío de Netflix del millón de dólares. Ese desafío condujo a una formulación del problema de recomendación como uno de completación de una matriz, dada una matriz de usuarios vs elementos, donde cada celda representa un rating del usuario con respecto al elemento:
¿Qué tan bien puede un algoritmo predecir los valores en algunas celdas que se ocultan deliberadamente?
2. Historia
Ya en 1982, el presidente de la ACM se quejó de la “basura electrónica (correo electrónico)” y abogó por el desarrollo de sistemas más inteligentes que ayuden a organizar, priorizar y filtrar los flujos entrantes de información [8]. Una de sus propuestas incluía la idea de utilizar “autoridades de confianza” que evalúan la calidad de los documentos; los receptores solo leerían documentos que superen algún nivel de calidad definido. En 1987, se propuso el sistema de procesamiento de correo personal “Information Lens” [25]. El sistema se basaba principalmente en reglas de filtrado definidas manualmente, pero los autores ya imaginaron un sistema donde los receptores de correo electrónico podrían respaldar a otras personas cuyas opiniones valoran. Los mensajes entrantes serían priorizados por el número y la fuerza de los endosos. El sistema de filtrado de correo electrónico Tapestry en Xerox PARC [14] adoptó un enfoque similar de emplear reglas especificadas por el usuario. Además, introdujo la idea de que algunos lectores podían clasificar (calificar) los mensajes y otros lectores podían acceder a esta información, lo que se denominó "filtrado colaborativo" (CF).
n 1994, Resnick et al. [33] presentó el sistema GroupLens, que continuó las ideas de Tapestry e introdujo un componente del sistema, el "Better Bit Bureau", que hizo predicciones automatizadas sobre qué elementos le gustaría a las personas basándose en un esquema de vecino más cercano. Otros grupos de investigación que trabajaban de forma independiente desarrollaron ideas similares [18, 36]. La idea estaba “en el aire” de que las opiniones de otras personas eran un recurso valioso y había comenzado la carrera para convertir la idea en resultados prácticos.
3. El Problema de la Completación de Matrices
Para entonces, la comunidad de investigadores había desarrollado algunos conceptos y terminología estándar. El elemento central es la matriz de calificación del elemento del usuario, las filas representan a los usuarios, las columnas representan los elementos y cada celda representa la preferencia subjetiva del usuario por cualquier elemento, determinada en función de un informe explícito (por ejemplo, de 1 a 5 estrellas) o en función del comportamiento del usuario ( por ejemplo, hacer clic, comprar o dedicar tiempo al artículo). La matriz usuario-artículo es generalmente escasa: la mayoría de los usuarios no han interactuado con la mayoría de los artículos. Una formulación del problema del recomendador, entonces, es la de un problema de compleción de matrices. Es decir, el problema es predecir cuáles serán las celdas que faltan, en otras palabras, ¿cómo calificarán los usuarios los elementos que aún no han calificado? Con esa formulación, era natural aplicar y adaptar técnicas de aprendizaje automático de otros entornos de problemas, incluidas varias formas de agrupamiento, clasificación, regresión o descomposición de valores singulares [3, 4]. En consecuencia, la comunidad adoptó medidas de evaluación de los campos de aprendizaje automático e IR como Precision / Recall y la medida Root Mean Squared Error (RMSE). Estas técnicas de evaluación retienen algunas de las calificaciones conocidas, usan el algoritmo para predecir las calificaciones de esas celdas y luego comparan las calificaciones predichas con las retenidas. La disponibilidad de algunos conjuntos de datos de calificación comunes, distribuidos por proveedores y proyectos académicos, permitió a los investigadores realizar evaluaciones comparando el desempeño de algoritmos alternativos de llenado de matrices entre sí.
4. El Premio Netflix
Netflix, que vio el valor estratégico de mejorar sus recomendaciones, superó el proceso de horneado para los algoritmos de compleción de matrices en 2006. Netflix ofreció un premio de un millón de dólares, un conjunto de datos para entrenamiento y una infraestructura para probar algoritmos sobre datos retenidos. Los datos de formación incluyeron 100 millones de valoraciones reales de clientes. El premio fue para el primer algoritmo que superó el rendimiento del sistema interno de Netflix en un 10% en RMSE (consulte el recuadro 1). El interés en esta competencia fue enorme. Más de 5.000 equipos se inscribieron para la competencia y el premio se otorgó finalmente en 2009. Se logró un progreso sustancial con respecto a la aplicación de enfoques de aprendizaje automático para la tarea de predicción de calificaciones. En particular, varias formas de factorización de matrices, así como técnicas de aprendizaje por conjuntos, se desarrollaron más en el transcurso de la competencia y demostraron ser altamente exitosas.
5. Más allá de la Completación
Al concluir la competencia del Premio Netflix, podría haber sido plausible pensar que los sistemas de recomendación fueron un problema resuelto. Después de todo, muchos investigadores muy talentosos se habían dedicado durante un período prolongado a mejorar la predicción de calificaciones retenidas. Los beneficios de ese esfuerzo parecían estar disminuyendo con bastante rapidez, con las pequeñas mejoras finales que fueron suficientes para ganar el premio de combinar los esfuerzos de muchos participantes independientes. Sin embargo, resulta que los sistemas de recomendación están lejos de ser un problema resuelto. En la siguiente sección, primero daremos ejemplos de por qué optimizar la precisión de la predicción para las calificaciones históricas retenidas puede ser insuficiente o incluso engañoso. Luego discutiremos los factores de calidad seleccionados de los sistemas recomendados que no están cubiertos en absoluto por la tarea de finalización de la matriz y daremos ejemplos de investigaciones recientes que van más allá de la compleción de la matriz.