Sistemas de recomendación, parte 2: filtrado colaborativo
En la parte 1 de la serie de sistemas de recomendación, mencioné brevemente en que nos ayudan, cuales son sus clasificaciones según su modo de funcionamiento del algoritmo, además de ver un corto ejemplo de Filtrado Colaborativo basado en Usuarios.
Para refrescar la memoria, lo que intentan resolver los sistemas de recomendación es predecir preferencias y/o recomendar un set de items no evaluados que sean relevantes para un usuario.
Las recomendaciones muchas veces forman parte del core de un negocio. Por ejemplo, para motivar el uso continuo del servicio, Netflix recomienda películas relevantes a sus usuarios. En 2006, lanzaron un concurso de tipo crowdsourcing con el objetivo de que alguien fuera lo suficientemente seco para superar su algoritmo de recomendación de películas por al menos 10% con respecto a su medida actual de errores (RMSE 0.9514), donde el ganador se lleva 1 millón de dólares. Les comentaré de esto con un mayor detalle más adelante, pero primero, ahondaré con un poco de teoría sobre algoritmos de Filtrado Colaborativo basado en Items y al final, una breve repasada sobre uno de los más potentes, Singular Value Decomposition (SVD).
Filtrado Colaborativo basado en Items
Análogamente a lo que ocurre con filtrado colaborativo basado en usuarios, cuando es basado en items las recomendaciones se hacen sobre los ratings de items realizados por otros usuarios en el sistema. La mayor diferencia es que para este caso, no se realiza la búsqueda de la vecindad de usuarios y vamos directo a calcular la similaridad entre items.
Slope One
Uno de los algoritmos más simples que podemos revisar dentro de la categoría de filtrado cooperativo y que tiene resultados bastante aceptables es el de Pendiente Uno (Slope One). La intuición detrás de este algoritmo es el diferencial de popularidad, que consiste en el promedio de las diferencias entre items, que es usado como medida para predecir las preferencias con respecto a items no evaluados. Se desea obtener el mejor predictor del estilo f(x)=mx+b, donde la pendiente es 1, es decir, f(x)=x+b (m=1, por eso el nombre “pendiente 1”).
Formalmente, el diferencial de popularidad se define por la desviación entre items i y j,
Ejemplo
Suponiendo que decidimos predecir el rating de un usuario que no ha visto Spiderman pero si ha visto Batman (ver tabla 1, User U3), una forma de obtener el promedio del diferencial es tomando los ratings de usuarios que han evaluado ambas películas, en este caso, para los usuarios U1 y U2 el diferencial entre Batman y Spiderman es [(4–3)+(4–2)]/2=1.5. Es decir, si viene el usuario U3 que si ha visto Batman, pero no ha visto Spiderman y quisiéramos saber como la evaluaría, usamos su rating de Batman (2) y le sumamos el diferencial promedio (1.5), dando un rating estimado de 3.5.
Aplicando lo mismo para Spiderman vs Harry Potter, da como resultado [(4–5)/1]=-1, dando un rating de 3 para el usuario. Finalmente, la predicción está dada por:
Es decir, 1/2*[(1.5+2)+(-1+4)]=3.25. Por lo tanto, el rating que predicho para Spiderman para el usuario U3 es 3.25! Que tratando de ser lo más objetivo posible, es super buena nota porque yo le pondría un 2.
Como vimos, el algoritmo es bastante sencillo en comparación a otros, donde sus principales ventajas son:
- Fácil de Implementar y mantener
- Actualizable en línea: nuevos ratings deberían cambiar las predicciones rápidamente.
- Eficiente al momento de consulta: costo principal debería llevarlo el almacenamiento.
- Funciona con poco feedback del usuario
- Razonablemente preciso, dentro de ciertos rangos en los que una pequeña ganancia en exactitud no signifique un gran sacrificio de simplicidad y escalabilidad.
Variantes de Slope One
En el paper de Slope One, se ofrecen al menos 3 alternativas que usan el principio descrito anteriormente, con algunas variantes. Sin entrar en mayor detalle, sus características generales son:
- Slope One: el modelo descrito anteriormente
- Weighted Slope One: lo anterior, pero tomando en consideración la cantidad de ratings por cada item como peso, ya que entre más ratings haya entre un par de items, tenemos mayor confianza de que sea un mejor predictor.
- Bi-polar Slope One: separa la predicción en 2 componentes, una para ratings positivos y otra para negativos, definiendo el umbral como rating promedio por cada usuario. Si el rating de un usuario supera su umbral promedio, se marca como positivo, de lo contrario, negativo.
A continuación, se expone los resultados de un benchmark del mismo paper para estos métodos versus otros (tabla 2) sobre los datasets EachMovie y Movielens, donde se observa que el menor MAE, por ende, mejor rendimiento, es para Bi-polar Slope One.
Les recomiendo revisar PyRecLab, un lib hecho en C++ con bindings para correr en Python para prototipado rápido de sistemas de recomendación. Las instrucciones de instalación para Linux y MacOS se encuentran en el mismo link.
Antes de dar por finalizado el post semanal, revisaremos brevemente por uno de los algoritmos base más potentes para generar recomendaciones, Singular Value Decomposition.
La recomendación del millón de dólares
Volviendo al tema del premio de Netflix en 2006, uno de los participantes, Simon Funk, publicó en su blog una implementación basada en SVD, un modelo de factorización matricial cuya primera publicación en el contexto de sistemas de recomendación usando esta técnica fue en el paper de Sarwar et al en el año 2000. La implementación realizada por Funk con consideraciones del paper de Gorrel que contenía mejoras que le ayuda a funcionar mejor sobre datos sparse, donde se incluye el uso stochastic gradient descent para la optimización. La implementación en ese entonces le valió temporalmemnte estar en el tercer lugar dentro de la tabla de clasificación (con un RMSE 0.9189, 3.42%), la cual obviamente al tener la información y código fuente en su blog expuesto al público hizo que el algoritmo subiera en popularidad…
SVD y otras hierbas
Como vimos anteriormente, el modelo parece ser bastante potente pero nos hemos quedado sólo en el nombre ¿En que consiste SVD?
SVD viene del mundo del algebra lineal y consiste en la factorización de matrices. Esto no suena muy intuitivo pero básicamente lo que sea desea obtener son los factores latentes, algo que no puedes ver a simple vista pero que tiene influencia sobre un resultado. Para este caso, deseamos obtener los features de los items calificados. Por ejemplo, supongamos que tenemos una matriz de Usuarios por Items, donde el valor representa un rating:
Si aplicamos SVD, podemos separar los features de items y usuarios, donde podríamos estimar que el rating de un usuario sobre un item rᵤᵢ equivale al producto punto entre el feature vector de items qᵢ y el feature vector pᵤ:
Luego, para calcular qi y pu, podemos hacer 2 cosas:
- Calcular SVD de manera tradicional
- Utilizar algoritmo de optimización como Stochastic Gradient Descent u otra variante.
Si se opta por SVD tradicional, es necesario tener en cuenta lo siguiente:
- Calcular la SVD de una matriz es muy costoso, O(m²n), para una matriz m*n
- No funciona bien con datos muy dispersos, hay que recurrir a “hacks” como prellenado de la matriz.
- Corre peligro de overfitting, es decir, memorizar los datos y no ser capaz de generalizar.
Por otro lado, si usamos Stochastic Gradient Descent (como Funk), que se ejecuta sobre cada uno de los ratings donde se hace una aproximación numérica a los factores latentes en vez de usar una solución algebraica.
Para esto, usamos una función de perdida con regularización, donde rᵤᵢ es el rating real, qᵢ y pᵤ son los factores latentes de item y usuario, λ es el factor de regularización.
Eventualmente, dada varias iteraciones se llega a un óptimo donde qᵢ y pᵤ entreguen métricas como RMSE, MAE, etc. que nos dejen conforme.
Al contrario del método SVD tradicional, con SGD ganamos:
- El calculo de los factores latentes es menos costoso.
- Buena aproximación de los datos faltantes en matrices dispersas.
- El uso de regularización disminuye el overfitting.
¿Quien ganó el millón de dólares?
Para concluir con la historia de Netflix, tuvieron que pasar 3 años para encontrar un ganador que superara al menos en 10% al algoritmo original. En detalle fueron 2 equipos, “BellKor’s Pragmatic Chaos” y “The Ensemble” quienes compitieron hasta los últimos minutos para ganar.
Al cierre, en el set de prueba público de quiz o qualifying set, “BellKor’s Pragmatic Chaos” obtuvo 10.09% mientras que “The Ensemble” obtuvo un 10.10% de mejora sobre éste mismo… Pero eso no garantizó al ganador, ya que finalmente es Netflix quien tiene el test set privado donde se valida y confirma el ganador, el cual resultó en un empate!
Por lo tanto, para romper el empate se usó el criterio de quiebre quien entrega primero la solución, dando por ganador a “BellKor’s Pragmatic Chaos” quienes enviaron 20 minutos antes. Son 20 minutos que valieron 1 millón de dólares.
