Evaluating Recommendation Systems

Paula Navarrete
Sep 2, 2018 · 12 min read

A continuación detallo estudios comparativos para evaluar sistemas recomendadores (RecSys), intentando enfocar la comparación de algoritmos de clasificación a través de una métrica de evaluación en lugar de una evaluación comparativa absoluta.

A la hora de diseñar un RecSys, podemos seleccionar el algoritmo que mejor funciona, dadas las restricciones estructurales del problema, como el tipo, la confiabilidad de los datos disponibles, memoria, etc.

En general, es ampliamente aceptado que las predicciones precisas son cruciales pero insuficientes para implementar un buen motor de recomendación. Por lo tanto, debemos identificar el conjunto de propiedades que pueden influir en el éxito de un RecSys en el contexto de una aplicación específica, así podemos evaluar cómo se comporta el sistema en estas propiedades relevantes.

Tipos de evaluacion

Discutiremos lo que se puede y no se puede evaluar para cada uno de estos tipos de experimentos, analizando un gran conjunto de propiedades que pueden ser relevantes para el éxito del sistema y cómo se pueden clasificar los RecSys con respecto a estas propiedades.

Existen tres niveles de experimentación para comparar distintos RecSys

  • Evaluaciones offline

Usualmente es más fácil llevar a cabo experimentos utilizando directamente conjuntos de datos ya existentes y un protocolo que modele o simule el comportamiento del usuario para estimar el desempeño del sistema. Son atractivos ya que no requieren de la interacción con el usuario. Su objetivo es filtrar enfoques inapropiados, dejando un conjunto relativamente pequeño de algoritmos candidatos para ser probados por estudios en usuario o experimentos en línea (que son mas costosos).

Los datos utilizados deben coincidir lo más posible con los datos que se espera que tenga el sistema cuando se implemente en línea y se debe tener cuidado de asegurar que no hayan sesgos en las distribuciones de users, items y clasificaciones seleccionadas. A veces los datos pueden corregirse mediante técnicas reponderar los datos para los sesgos conocidos, pero suele ser difícil.

Dado que es necesario simular el proceso en línea donde el sistema hace predicciones o recomendaciones, y el usuario corrige las predicciones o utiliza las recomendaciones, idealmente, si tenemos acceso a las timestamps para las selecciones de los usuarios, podemos simular las predicciones de los sistemas como si se hubiera estado ejecutando en el momento en que se recopiló el conjunto de datos.

Utilizando modelos avanzados de usuario, podemos ejecutar simulaciones de las interacciones de los usuarios con el sistema, reduciendo así la necesidad de costosos estudios de usuarios y pruebas en línea. Sin embargo, se debe tener cuidado al diseñar modelos de usuario ya que es difícil modelarlo y si es inapropiado el modelo, podemos terminar optimizando un sistema cuyo desempeño no se correlaciona con el de la realidad.

  • Estudios en usuarios

Se solicita a un pequeño grupo de usuarios que realicen una serie de tareas utilizando el sistema, generalmente respondiendo preguntas sobre su experiencia. Podemos recopilar información tanto cuantitativa como cualitativa, teniendo especial cuidado para considerar distintos sesgos en el diseño experimental. Son útiles cuando no podemos realizar simulaciones de usuario confiables como para llevar a cabo un experimento offline pero son más costosos.

Otra consideración importante es que los sujetos de prueba deben representar lo más posible la población de usuarios del sistema real. Sin embargo, incluso cuando está representada correctamente la verdadera población de usuarios, los resultados aún pueden estar sesgados porque son conscientes de que están participando en un experimento. Para evaluar, podemos comparar Between Subjects, donde se le asigna a cada sujeto un método candidato y se experimenta con él, Within Subjects, donde cada sujeto prueba un conjunto de métodos candidatos en diferentes tareas. La primera forma es más cercana a la realidad y también permite evaluar la curva de aprendizaje del usuario.

Por esta vía, también podemos utilizar cuestionarios, que pueden proporcionar información sobre propiedades que son difíciles de medir, como el estado de ánimo del sujeto, o si el sujeto disfrutó del sistema. También pueden proporcionar información engañosa, por lo que es importante hacer preguntas neutrales, que no sugieran una respuesta “correcta”.

  • Evaluaciones online

Son experimentos a gran escala en un sistema desplegado. Dichos experimentos evalúan el rendimiento de los recomendadores en usuarios reales que son inconscientes de el experimento que se lleva a cabo. Este tipo de experimentación es considerada la más cercana a la realidad.

Es el tipo de experimentación que proporciona la evidencia más sólida en cuanto al valor real del sistema, donde el sistema es utilizado por usuarios reales que realizan tareas reales. Es más confiable comparar algunos sistemas en línea, obteniendo un ranking de alternativas , en lugar de números absolutos que son más difíciles de interpretar.

Conclusiones y Significancia

En todos los tipos de experimentación mencionados, debemos tener en cuenta los aspectos básicos de una experimentación en términos de su hipótesis, variables de control y poder de generalización.

En todos los casos, es importante que podamos estar seguros de que el recomendador candidato que elijamos también será una buena opción para datos aún no vistos que el sistema enfrentará en el futuro, por ende, debemos realizar tests estadísticos de significancia en los resultados como p-value, sign test [2], McNemar’s test [3], Wilcoxon test [4].

Estos tests son adecuados para los casos en que las observaciones están emparejadas. Es decir, cada algoritmo se ejecuta en cada caso de prueba, como suele hacerse en las pruebas de detección. Sin embargo, en las pruebas en línea, a menudo los usuarios son asignados a un algoritmo u otro, de modo que los dos algoritmos no se evalúan en los mismos casos de prueba. El test de Mann-Whitney es una extensión de Wilcoxon test para este escenario.

Otra consideración importante, sobre todo en el escenario offline, es el efecto de evaluar múltiples versiones de algoritmos. Por ejemplo, se puede probar múltiples variantes de un algoritmo de recomendación novedoso y compararlas con un algoritmo base hasta encontrar uno que pase el sign test a nivel p = 0.05 y por lo tanto inferir que el algoritmo mejora con un 95% confianza. Esto conlleva un riesgo que se conoce coloquialmente como “tuning to the test set” y puede evitarse separando a los usuarios del conjunto de prueba en dos grupos: un conjunto de desarrollo (o ajuste) y un conjunto de evaluación. La elección del algoritmo se realiza en función del test de desarrollo, y la validez de la elección se mide ejecutando un test de significancia en el conjunto de evaluación.

Propiedades

A continuación profundizo propiedades que se comúnmente consideran al decidir qué enfoque de recomendación seleccionar y al diseñar poder discernir sobre las propiedades importantes a medir en la aplicación. Algunas de ellas pueden ser sujetas de trade-off, como disminuir la precisión mejorando otras propiedades la diversidad por ejemplo. En esta linea, podemos especular que los usuarios desean recomendaciones diversas o novedosas, pero es esencial asegurarse que esto es realmente importante en la práctica, por lo que al sugerir un método que mejore una de estas propiedades, también se debe evaluar cómo los cambios en esta propiedad afectan la experiencia del usuario.

  • Preferencia del usuario

La opción obvia es ejecutar un estudio de usuario (within subject) y pedir a los participantes que elijan uno de los sistemas y luego seleccionamos al que tenga una mayor cantidad de votos, asumiendo que todos los usuarios son iguales, lo que no siempre es cierto, puede que queramos preferir la opinión de los usuarios que aportan un mayor revenue a la opinión de los usuarios que lo hacen solo marginalmente. Por lo tanto, . necesitamos asignar los pesos de importancia correctos en un estudio de usuario lo que puede no ser fácil.

Es importante saber por qué las personas favorecen un sistema sobre el otro, por lo tanto, aunque la satisfacción total del usuario es importante de medir, descomponer la satisfacción en componentes más pequeños es útil para comprender el sistema y mejorarlo.

  • Precisión (Accuracy)

Es por lejos a propiedad más discutida en la literatura [1][5].Una suposición básica en un RecSys es que el usuario preferirá un sistema que proporcione predicciones más precisas. La precisión de la predicción es típicamente independiente de la interfaz del usuario y, por lo tanto, se puede medir en un experimento directo. La medición de la precisión de predicción en un estudio de usuario mide la precisión dada una recomendación. Este es un concepto diferente de la predicción del comportamiento del usuario sin recomendaciones, y está más cerca de la verdadera precisión en el sistema real.

La forma mas polular de medir Rating Prediction es a través del error medio cuadrático (RMSE) y del error medio absoluto (MAE), algunas variantes lo normalizan y otras lo promedian o lo ajustan para test sets des balanceados.

En muchas aplicaciones, el RecSys trata de recomendar a los usuarios los elementos que pueden usar. En este caso, nos interesa no saber si el sistema predice correctamente que el usuario agregará estas películas a la cola (si usará los elementos recomendados), por ende tenemos 4 posibilidades para nuestra predicción:

Podemos contar la cantidad de ejemplos que caen en cada celda de la tabla y calcular las siguientes medidas:

podemos esperar un trade-off entre ellas, mientras que permitir listas de recomendaciones más largas generalmente mejora el Recall, también es probable que reduzca la precisión. En aplicaciones donde se preestablece el número de recomendaciones que se pueden presentar al usuario, la medida de interés más útil es Precision at N. En ocasiones, es preferible evaluar algoritmos en un rango de longitudes de lista de recomendaciones, en lugar de utilizar una longitud fija. Por lo tanto, podemos calcular curvas que comparan la precisión con el Recall, o la tasa positiva verdadera con la tasa positiva falsa. Las curvas del tipo anterior se conocen simplemente como curvas de recuperación de precisión, mientras que las del último tipo se conocen como Característica Operativa del Receptor o curvas ROC[1], la primera enfatiza la proporción de artículos recomendados que se prefieren mientras que las curvas ROC enfatizan la proporción de artículos que no son preferidos y que terminan siendo recomendados.

En algunos casos, la aplicación presenta al usuario una lista de recomendaciones que impone un orden de exploración natural, en este caso estamos interesados en ordenar elementos según las preferencias del usuario. También conocido como clasificación de items. Cuando las calificaciones explícitas de los usuarios están disponibles, podemos clasificar los artículos calificados en orden decreciente de las calificaciones, enlazándolos. Cuando solo tenemos datos de uso, es apropiado construir una clasificación de referencia donde los artículos usados por el usuario se clasifiquen por encima de los artículos no utilizados, donde los artículos usados están enlazados entre sí y los artículos no usados están enlazados entre sí y el sistema no debe ser penalizado por clasificar un ítem sobre otro cuando están empatados en el ranking de referencia, para esto se utiliza la Medida de Rendimiento Basada en Distancia Normalizada (NDPM)[1]

Una alternativa popular es suponer que la utilidad de una lista de recomendaciones es aditiva, obteniendo la suma de las utilidades de las recomendaciones individuales. La utilidad de cada recomendación es la utilidad del elemento recomendado descontado por un factor que depende de su posición en la lista de recomendaciones, esto supone que la probabilidad de que se observe una posición particular en la lista de recomendaciones depende únicamente de la posición y no de los elementos que se recomiendan. Para esto se utiliza la métrica R-Score que asume que el valor de las recomendaciones disminuye exponencialmente en la lista clasificada para obtener el siguiente puntaje para cada usuario u. Cuando se espera que el usuario lea una porcion relativamente larga de la lista (investigación o análisis legal) se utiliza la Ganancia Descontada aCumulada Normalizada (NDCG) o el Average Reciprocal Hit Rank(ARHR), que es una medida no normalizada que asigna una utilidad 1/k a una recomendación exitosa en la posición k. Por lo tanto, ARHR decae más lentamente que la R Score, pero más rápido que NDCG.

  • Covertura

Algunos algoritmos pueden proporcionar recomendaciones con alta calidad, pero solo para una pequeña parte de los ítems (sparse data)[5][6]. Comúnmente, Coverage se refiere a la proporción de elementos que el RecSys puede recomendar. La medida más simple de la cobertura es el porcentaje de los artículos que alguna vez se pueden recomendar, otra medida es el porcentaje de los artículos que se recomiendan a los usuarios durante un experimento. En algunos casos, puede ser conveniente ponderar los artículos, por ejemplo, por su popularidad o utilidad. Otra medida de la cobertura es la diversidad, que mide cómo los usuarios eligen diferentes elementos de manera desigual cuando se utiliza un sistema de recomendación en particular. La métricas más usuales son el Gini Index y Shannon Entropy.

La cobertura también puede ser la proporción de usuarios o interacciones para los cuales el sistema puede recomendar elementos, ya que es posible que el RecSys no proporcione recomendaciones para algunos usuarios debido a la baja confianza en la precisión de las predicciones para ese usuario por ejemplo, esto puede ser medido a traves de la cantidad de dato necesarios antes de comenzar a dar recomendaciones. Centrándonos en el Cold Start [5], podemos usar un umbral para decidir sobre el conjunto de elementos con Cold Start. Es posible que un sistema recomiende mejor los items con Cold Start al precio de una reducción de la precisión.

  • Confidence

Puede definirse como la confianza del sistema en sus recomendaciones o predicciones. Cuando el sistema informa una baja confianza en un artículo recomendado, el usuario puede tender a investigar más el artículo antes de tomar una decisión. La medida más común es la probabilidad de que el valor predicho sea cierto, o el intervalo alrededor del valor predicho donde una porción predefinida, p = 95% de los verdaderos valores residen.

Teniendo en cuenta dos recomendaciones que funcionan de manera similar en otras propiedades relevantes, como la precisión, puede ser conveniente elegir la que puede proporcionar estimaciones de confianza válidas.

  • Trust

Nos referimos aquí a la confianza del usuario en la recomendación del sistema o a su credibilidad. Puede ser beneficioso para el sistema recomendar algunos elementos que el usuario ya conoce y le gustan, aunque el usuario no obtiene ningún valor de esta recomendación, observa que el sistema proporciona recomendaciones razonables, lo que puede aumentar su confianza para artículos desconocidos, otra forma es proveer explicaciones a la recomendación.

  • Novelty

Son recomendaciones para artículos que el usuario no conocía[1] [5]. Para evaluarla podríamos dividir el conjunto de datos en el tiempo, es decir, ocultar todas las clasificaciones de usuarios que ocurrieron después de un punto específico en el tiempo. Además, podemos ocultar algunos ratings que ocurrieron antes de ese momento (para no alimentar el modelo con esa data), simulando los elementos con los que el usuario está familiarizado, pero que no informaron las calificaciones. Al recomendar, el sistema se recompensa por cada artículo que se recomendó y calificó después del tiempo de división, pero se castigaría por cada artículo que se recomienda pero es calificado antes del tiempo de división. Es importante controlar la precisión, ya que las recomendaciones irrelevantes pueden ser nuevas para el usuario, pero aún así son inútiles.

  • Serendipity

Se refiere a la medida de qué tan sorprendentes son las recomendaciones exitosas. Por ejemplo, si el usuario ha calificado positivamente muchas películas donde aparece un actor estrella, recomendar la nueva película de ese actor puede ser novedoso, porque el usuario la conoce, pero no es sorprendente. Por supuesto, las recomendaciones aleatorias pueden ser muy sorprendentes y, por lo tanto, debemos equilibrar las casualidades (serendipity) con la precisión. Se puede diseñar una métrica de distancia entre los artículos en función del contenido y calificar una recomendación exitosa según su distancia de un conjunto de ítems previamente calificados en un sistema de filtrado colaborativo, o desde el perfil del usuario en un recomendador basado en el contenido. Por lo tanto, estamos recompensando al sistema por recomendaciones exitosas que están lejos del perfil del usuario.

Otros aspectos importantes en un RecSys giran en torno a la diversidad ya que en algunos casos, sugerir un conjunto de elementos similares puede no ser tan útil para el usuario lo que le puede llevar más tiempo en explorar el rango de elementos desplegados, o en torno a una función de utilidad (utility) y optimizándola, o respecto del riesgo involucrado (mercado accionario). En ocasiones la robustez del sistema toma preponderancia en ambientes que pueden ser víctima de ratings falsos o que deben ser capaces de performar en condiciones extremas como un alto numero de requests. Es importante resguardar la privacidad de los datos en el sistema y que este adaptable y escalable en el tiempo[1][5].


Fuentes:

[1] Shani, Guy, and Asela Gunawardana. “Evaluating recommendation systems.” In Recommender systems handbook, pp. 257–297. Springer US, 2011.

[2] Janez Demsar. Statistical comparisons of classifiers over multiple datasets. J.Mach. Learn. Res., 7:1–30, 2006. ISSN 1533–7928

[3] Steven L. Salzberg. On comparing classifiers: Pitfalls to avoid and a recommended approach. DataMin.Knowl.Discov.,1(3):317–328,1997. ISSN1384–5810. doi: http://dx.doi.org/10.1023/A:1009752403260.

[4] Woolson, R. F. (2007). Wilcoxon signed‐rank test. Wiley encyclopedia of clinical trials, 1–3.

[5] Schafer, J. B., Frankowski, D., Herlocker, J., & Sen, S. (2007). Collaborative filtering recommender systems. In The adaptive web (pp. 291–324). Springer Berlin Heidelberg.

[6] Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer IEEE Magazine, 42(8), 30–37.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade