Anatomía de los sistemas de recomendación. Primera parte

Trabajo como científico de datos en CleverDATA . Estamos involucrados en proyectos de aprendizaje automático, y una de las solicitudes más frecuentes para el desarrollo de soluciones de marketing basadas en aprendizaje automático es el desarrollo de modelos de recomendación.

En este artículo, hablaré sobre los sistemas de recomendación, trataré de dar una visión general más completa de los enfoques existentes y explicaré con los dedos cómo funcionan los algoritmos. Parte del material se basa en un buen curso sobre los sistemas de recomendación del laboratorio MovieLens (con el que la mayoría de las personas están familiarizadas por el mismo conjunto de datos para evaluar las recomendaciones), el resto es por experiencia personal. El artículo consta de dos partes. El primero describe el enunciado del problema y ofrece una visión general de los algoritmos de recomendación simples (pero populares). En el segundo artículo hablaré sobre métodos más avanzados y algunos aspectos prácticos de implementación.

Fuente

Revisión y exposición del problema.

La tarea del sistema de recomendación es informar al usuario sobre un producto en el que pueda estar más interesado en un momento dado. El cliente recibe información y el servicio gana dinero con la prestación de servicios de calidad. Los servicios no son necesariamente ventas directas de los productos ofrecidos. El servicio también puede ganar comisiones o simplemente aumentar la lealtad del usuario, que luego se traduce en publicidad y otros ingresos.

Dependiendo del modelo de negocio, las recomendaciones pueden ser su base, como, por ejemplo, con TripAdvisor, o simplemente pueden ser un servicio adicional conveniente (como, por ejemplo, en alguna tienda de ropa en línea), diseñado para mejorar la experiencia del cliente y hacer que la navegación por el catálogo sea más Cómodo

La personalización del marketing en línea es una tendencia obvia de la última década. Según McKinsey , el 35% de los ingresos de Amazon o el 75% de los ingresos de Netflix provienen de productos recomendados, y es probable que este porcentaje crezca. Los sistemas de referencia son acerca de qué ofrecer al cliente para hacerlo feliz.

Para ilustrar toda la variedad de servicios de recomendación, daré una lista de las características principales con las que puede describir cualquier sistema de recomendación.

1. Sujeto de recomendación : lo que se recomienda.
   
   Aquí hay mucha variedad: pueden ser bienes (Amazon, Ozon), artículos (Arxiv.org), noticias (Surfingbird, Yandex.Zen), imágenes (500 px), videos (YouTube, Netflix), personas (Linkedin, LonelyPlanet), música (Last.fm, Pandora), listas de reproducción y más. En general, puedes recomendar cualquier cosa.
   
2. El propósito de la recomendación es por qué se recomienda.
   
   Por ejemplo: comprar, informar, capacitar, hacer contactos.
   
3. El contexto de la recomendación es lo que el usuario está haciendo en este momento.
   
   Por ejemplo: mirar productos, escuchar música, hablar con la gente.
   
4. La fuente de la recomendación es quién recomienda:
   
   - audiencia (calificación promedio de restaurante en TripAdvisor),
   - Usuarios interesados
   - comunidad de expertos (a veces cuando se trata de un producto complejo, como, por ejemplo, el vino).
   
5. El grado de personalización .
   
   Recomendaciones no personales: cuando se le recomienda lo mismo que todos los demás. Permiten la orientación por región u hora, pero no tienen en cuenta sus preferencias personales.
   
   Una opción más avanzada es cuando las recomendaciones usan datos de su sesión actual. Has mirado varios productos, y en la parte inferior de la página te ofrecen productos similares.
   
   Las recomendaciones personales utilizan toda la información disponible sobre el cliente, incluido el historial de sus compras.
   
6. Transparencia
   
   Las personas confían más en la recomendación si entienden exactamente cómo se recibió. Por lo tanto, hay menos riesgo de toparse con sistemas "inescrupulosos" que promueven los bienes pagados o colocan a los bienes más caros en el ranking. Además, un buen sistema de recomendación en sí mismo debería ser capaz de manejar las revisiones compradas y los trucos de ventas.
   
   Las manipulaciones, por cierto, tampoco son intencionales. Por ejemplo, cuando se lanza un nuevo éxito de taquilla, lo primero que hacen los fanáticos es, en consecuencia, la calificación puede ser muy alta durante los primeros meses.
   
7. El formato de la recomendación .
   
   Esto puede ser una ventana emergente, una lista ordenada que aparece en una sección específica del sitio, una cinta en la parte inferior de la pantalla u otra cosa.
   
8. Algoritmos
   
   A pesar de los muchos algoritmos existentes, todos se reducen a varios enfoques básicos, que se describirán más adelante. Los más clásicos son los algoritmos basados ​​en resúmenes (no personales), basados ​​en contenido (modelos basados ​​en la descripción del producto), filtrado colaborativo (filtrado colaborativo), factorización matricial (métodos basados ​​en descomposición matricial) y algunos otros.
   

Fuente

En el centro de cualquier sistema de recomendación está la llamada matriz de preferencias. Esta es una matriz, en un eje del cual todos los clientes del servicio (Usuarios) se reservan, y en el otro, objetos de la recomendación (Artículos). En la intersección de algunos pares (usuario, elemento), esta matriz se llena con calificaciones (calificaciones): este es un indicador conocido del interés del usuario en este producto, expresado en una escala dada (por ejemplo, de 1 a 5).


Los usuarios generalmente evalúan solo una pequeña parte de los productos que están en el catálogo, y la tarea del sistema de recomendaciones es resumir esta información y predecir la actitud del cliente hacia otros productos sobre los que no se sabe nada. En otras palabras, debe completar todas las celdas vacías en la imagen de arriba.

Los patrones de consumo de las personas son diferentes y no es necesario recomendar nuevos productos. Puede mostrar posiciones repetidas, por ejemplo, para reponer existencias. Según este principio, se distinguen dos grupos de bienes.

• Repetible Por ejemplo, champús o maquinillas de afeitar que siempre se necesitan.
  
• Único Por ejemplo, libros o películas que rara vez se vuelven a adquirir.
  

Si el producto no se puede asignar explícitamente a una de las clases, tiene sentido determinar la admisibilidad de las compras repetidas individualmente (alguien va a la tienda solo por el bien de la mantequilla de maní de una determinada marca, y para alguien es importante probar todo lo que está en el catálogo).

El concepto de "interés" también es subjetivo. Algunos usuarios solo necesitan cosas de su categoría favorita (recomendaciones conservadoras), mientras que alguien, por el contrario, responde mejor a productos o grupos de productos no estándar (recomendaciones riesgosas). Por ejemplo, el alojamiento de video puede recomendar al usuario solo nuevos episodios de sus series favoritas y periódicamente puede lanzarle nuevos programas o incluso nuevos géneros. Idealmente, debe elegir una estrategia para mostrar recomendaciones para cada cliente por separado, utilizando el modelo de una categoría de cliente.

Las calificaciones de los usuarios se pueden obtener de dos maneras:

• calificaciones explícitas: el usuario coloca la calificación del producto, deja una reseña, le gusta la página,
  
• calificaciones implícitas: el usuario no expresa explícitamente su actitud, pero se puede sacar una conclusión indirecta de sus acciones: compró el producto, eso significa que le gusta, leyó la descripción durante mucho tiempo, significa que hay interés, etc.
  

Por supuesto, las preferencias explícitas son mejores: el propio usuario dice que le gustó. Sin embargo, en la práctica, no todos los sitios brindan la oportunidad de expresar explícitamente su interés, y no todos los usuarios tienen el deseo de hacerlo. Ambos tipos de calificaciones se usan con mayor frecuencia de una vez y se complementan bien.

También es importante distinguir entre los términos Predicción (predicción del grado de interés) y la propia Recomendación (que muestra la recomendación). Qué y cómo mostrar es una tarea separada que utiliza las estimaciones obtenidas en el paso de Predicción, pero se puede implementar de diferentes maneras.

A veces, el término "recomendación" se usa en un sentido más amplio y se refiere a cualquier optimización, ya sea una selección de clientes para el envío de publicidad, determinar el precio óptimo de oferta o simplemente elegir la mejor estrategia de comunicación con el cliente. En el artículo, me limito a la definición clásica de este término, que denota la elección del producto más interesante para el cliente.

Recomendaciones no personalizadas

Comencemos con recomendaciones no personalizadas, ya que son las más fáciles de implementar. En ellos, el interés potencial del usuario se determina simplemente por la calificación promedio del producto: "A todos les gusta, por lo que te gustará". La mayoría de los servicios funcionan según este principio cuando el usuario no ha iniciado sesión en el sistema, por ejemplo, el mismo TripAdvisor.

Las recomendaciones se pueden mostrar de diferentes maneras, como un banner al lado de la descripción del producto (Amazon), como resultado de una solicitud ordenada por un parámetro específico (TripAdvisor), o de alguna otra manera.

Las clasificaciones de productos también se pueden mostrar de varias maneras. Esto puede ser estrellas junto al producto, la cantidad de me gusta, la diferencia entre votos positivos y negativos (como se hace generalmente en los foros), la proporción de altas calificaciones o incluso un histograma de calificaciones. Los histogramas son la forma más informativa, pero tienen un inconveniente: son difíciles de comparar entre sí u ordenar, cuando necesita enumerar productos.

Problema de arranque en frío

Un arranque en frío es una situación típica en la que aún no se han acumulado suficientes datos para que el sistema de recomendación funcione correctamente (por ejemplo, cuando un producto es nuevo o apenas se compra). Si la calificación promedio se calcula mediante las estimaciones de solo tres usuarios (igor92, xyz_111 y oleg_s), dicha evaluación claramente no será confiable, y los usuarios entienden esto. A menudo, en tales situaciones, las calificaciones se ajustan artificialmente.

La primera forma es mostrar no el valor promedio, sino el promedio suavizado (media amortiguada). El significado es este: con una pequeña cantidad de calificaciones, la calificación mostrada está más inclinada hacia algún tipo de indicador "promedio" seguro, y tan pronto como se reúne una cantidad suficiente de nuevas calificaciones, el ajuste "promedio" deja de funcionar.

Otro enfoque es calcular los intervalos de confianza para cada calificación. Matemáticamente, cuanto más estimaciones, menor variación del promedio y, por lo tanto, más confianza en su corrección. Y como calificación, puede mostrar, por ejemplo, el límite inferior del intervalo (Low CI Bound). Al mismo tiempo, está claro que dicho sistema será bastante conservador, con una tendencia a subestimar las calificaciones de los nuevos productos (a menos, por supuesto, que esto sea un éxito).

Dado que las estimaciones están limitadas a cierta escala (por ejemplo, de 0 a 1), la forma habitual de calcular el intervalo de confianza es poco aplicable aquí: debido a las colas de distribución que van al infinito y la simetría del intervalo en sí. Hay una forma alternativa y más precisa de calcularlo: el intervalo de confianza de Wilson . En este caso, se obtienen intervalos asimétricos de aproximadamente este tipo.


En la imagen de arriba, se traza la calificación horizontal de la calificación promedio, y la vertical es la distribución alrededor del promedio. El color indica diferentes tamaños de muestra (obviamente, cuanto mayor es la muestra, menor es el intervalo de confianza).

El problema del arranque en frío es tan relevante para las recomendaciones no personalizadas. El enfoque general aquí es reemplazar lo que no se puede contar en este momento con varias heurísticas (por ejemplo, reemplazar con una calificación promedio, usar un algoritmo más simple o no usar un producto hasta que se recopilen los datos).

Relevancia de las recomendaciones

En algunos casos, también es importante tener en cuenta la "frescura" de la recomendación. Esto es especialmente cierto para artículos o publicaciones en foros. Las nuevas entradas a menudo deberían llegar a la cima. Para hacer esto, use factores de amortiguación. A continuación hay un par de fórmulas para calcular la clasificación de artículos en sitios de medios.

Ejemplo de cálculo de calificación en la revista de noticias Hacker:

donde U = votos positivos, D = votos negativos y P (penalización): ajuste adicional para la implementación de otras reglas comerciales

Cálculo de calificación en Reddit:

donde U = número de votos a favor, D = número de votos en contra, T = tiempo de registro. El primer término estima la "calidad de grabación", y el segundo hace una corrección por tiempo.

Obviamente, no existe una fórmula universal, y cada servicio inventa la fórmula que mejor resuelve su problema: se verifica empíricamente.

Recomendaciones basadas en contenido

Las recomendaciones personales sugieren el uso máximo de la información sobre el propio usuario, principalmente sobre sus compras anteriores. Uno de los primeros fue el enfoque de filtrado basado en contenido. En el marco de este enfoque, la descripción del producto (contenido) se compara con los intereses del usuario obtenidos de sus calificaciones anteriores. Cuanto más satisfaga el producto estos intereses, mayor será el interés potencial del usuario evaluado. El requisito obvio aquí es que todos los productos en el catálogo deben tener una descripción.

Históricamente, el tema de las recomendaciones basadas en contenido ha sido a menudo productos con una descripción no estructurada: películas, libros, artículos. Tales signos pueden ser, por ejemplo, descripciones de texto, reseñas, reparto y más. Sin embargo, nada impide el uso de signos numéricos o categóricos ordinarios.

Las características no estructuradas se describen de una manera típica para el texto: vectores en el espacio de las palabras ( modelo Vector-Space ). Cada elemento de dicho vector es una característica que potencialmente caracteriza el interés del usuario. Del mismo modo, un producto es un vector en el mismo espacio.

A medida que el usuario interactúa con el sistema (por ejemplo, compra películas), las descripciones vectoriales de los productos comprados por él se combinan (resumen y normalizan) en un solo vector y, por lo tanto, se forma un vector de sus intereses. Además, es suficiente encontrar un producto cuya descripción esté más cerca del vector de intereses, es decir, resuelve el problema de encontrar n vecinos más cercanos.

No todos los elementos son igualmente significativos: por ejemplo, las palabras aliadas, obviamente, no llevan ninguna carga útil. Por lo tanto, cuando se determina el número de elementos coincidentes en dos vectores, todas las mediciones deben sopesarse primero por su significado. Esta tarea se resuelve mediante la transformación TF-IDF , bien conocida en Text Mining , que asigna más peso a los intereses más raros. La coincidencia de tales intereses es más importante para determinar la proximidad de dos vectores que la coincidencia de los populares.


El principio TF-IDF aquí es igualmente aplicable a los atributos nominales ordinarios, como, por ejemplo, género, director, idioma. TF - una medida de la importancia del atributo para el usuario, IDF - una medida de la "rareza" del atributo.

Hay toda una familia de transformaciones similares (por ejemplo, BM25 y similares), pero en esencia todas repiten la misma lógica que TF-IDF: los atributos raros deberían tener más peso al comparar productos. La imagen a continuación ilustra cómo el peso del TF-IDF depende del TF y el IDF. El eje horizontal más cercano es DF: frecuencia de atributo entre todos los productos, el eje horizontal lejano es TF: logaritmo de frecuencia de atributo del usuario.


Algunos puntos que pueden tenerse en cuenta durante la implementación.

• Al formar una presentación de bienes en el espacio vectorial, en lugar de palabras individuales, puede usar tejas o n-gramos (pares consecutivos de palabras, triples, etc.). Esto hará que el modelo sea más detallado, pero se necesitarán más datos para la capacitación.
  
• En diferentes lugares de la descripción del producto, el peso de las palabras clave puede diferir (por ejemplo, la descripción de una película puede consistir en un título, una breve descripción y una descripción detallada).
  
• Las descripciones de productos de diferentes usuarios se pueden ponderar de manera diferente. Por ejemplo, podemos dar más peso a los usuarios activos que tienen muchas calificaciones.
  
• Del mismo modo, puede pesar y producto. Cuanto mayor sea la calificación promedio de un objeto, mayor será su peso (similar al PageRank ).
  
• Si la descripción del producto permite enlaces a fuentes externas, puede confundirse y analizar también toda la información de terceros relacionada con el producto.
  

Se puede ver que el filtrado basado en contenido repite casi por completo el mecanismo de coincidencia de documentos de consulta utilizado en motores de búsqueda como Yandex y Google. La única diferencia está en la forma de una consulta de búsqueda: aquí es un vector que describe los intereses del usuario, y están las palabras clave del documento solicitado. Cuando los motores de búsqueda comenzaron a agregar personalización, la distinción se borró aún más.

Como medida de la proximidad de dos vectores, la distancia coseno se usa con mayor frecuencia.


Cuando se agrega una nueva evaluación, el vector de intereses se actualiza de forma incremental (solo para aquellos elementos que han cambiado). Al contar, tiene sentido dar a las nuevas estimaciones un poco más de peso, ya que las preferencias pueden variar.

Filtrado colaborativo (opción basada en el usuario)

Esta clase de sistemas comenzó a desarrollarse activamente en los años 90. Como parte del enfoque, las recomendaciones se generan en función de los intereses de otros usuarios similares. Dichas recomendaciones son el resultado de una "colaboración" de muchos usuarios. De ahí el nombre del método.

La implementación clásica del algoritmo se basa en el principio de k vecinos más cercanos. En los dedos: para cada usuario, buscamos k más similares a él (en términos de preferencias) y complementamos la información sobre el usuario con datos conocidos sobre sus vecinos. Entonces, por ejemplo, si se sabe que sus vecinos interesados ​​están encantados con la película "Sangre y concreto", y no la han visto por alguna razón, esta es una excelente ocasión para ofrecerles esta película para verla el sábado.


La imagen de arriba ilustra el principio del método. En la matriz de preferencias, el usuario se resalta en amarillo para el que queremos determinar las calificaciones de los nuevos productos (signos de interrogación). Tres de sus vecinos más cercanos están resaltados en azul.

En este caso, "similitud" es sinónimo de "correlación" de intereses y puede considerarse de muchas maneras (además de la correlación de Pearson, también hay una distancia coseno, hay una distancia Jacquard, distancia Hamming, etc.).

La implementación clásica del algoritmo tiene una desventaja obvia: es poco aplicable en la práctica debido a la complejidad cuadrática.De hecho, como cualquier método del vecino más cercano, requiere el cálculo de todas las distancias por pares entre usuarios (y puede haber millones de usuarios). Es fácil calcular que la complejidad de calcular la matriz de distancia será$$$O(n^2m)$donde n es el número de usuarios ym es el número de productos. Con un millón de usuarios, se requiere un mínimo de 4 TB para almacenar la matriz de distancia sin procesar.

Este problema puede resolverse parcialmente comprando hierro de alto rendimiento. Pero si se acerca sabiamente, es mejor introducir correcciones en el algoritmo:

• actualizar distancias no con cada compra, sino con lotes (por ejemplo, una vez al día),
  
• No vuelva a calcular la matriz de distancia por completo, sino actualícela gradualmente,
  
• optar por algoritmos iterativos y aproximados (por ejemplo, ALS).
  

Para que el algoritmo sea efectivo, es importante que se cumplan algunos supuestos.

• Los gustos de las personas no cambian con el tiempo (o cambian, pero para todos lo mismo).
  
• Si los gustos de las personas coinciden, entonces coinciden en todo.
  
  Por ejemplo, si dos clientes prefieren las mismas películas, también les gustan los mismos libros. Esto sucede a menudo cuando los productos recomendados son homogéneos (por ejemplo, solo películas). Si esto no es así, entonces un par de clientes pueden tener las mismas preferencias alimentarias, y las opiniones políticas son directamente opuestas: aquí el algoritmo será menos efectivo.
  

El vecindario del usuario en el espacio de preferencia (sus vecinos), que analizaremos para generar nuevas recomendaciones, se puede elegir de diferentes maneras. Podemos trabajar con todos los usuarios del sistema en general, podemos establecer un cierto umbral de proximidad, podemos seleccionar varios vecinos al azar o tomar los n vecinos más similares (este es el enfoque más popular).

Los autores de MovieLens como el número óptimo de vecinos dan cifras de 30-50 vecinos para películas y 25-100 para recomendaciones arbitrarias. Está claro aquí que si tomamos demasiados vecinos, tendremos más posibilidades de ruido aleatorio, y viceversa, si tomamos muy poco, obtendremos recomendaciones más precisas, pero se pueden recomendar menos productos.

Una etapa importante en la preparación de datos es la normalización de las estimaciones.

Estandarización de datos (escalado)

Dado que todos los usuarios evalúan de manera diferente (alguien pone cinco en una fila y rara vez espera cuatro de alguien), es mejor normalizar los datos antes de calcular, es decir conducir a una escala única para que el algoritmo pueda compararlos correctamente entre sí.

Naturalmente, la estimación pronosticada deberá traducirse a la escala original mediante la transformación inversa (y, si es necesario, redondear al entero más cercano).

Hay varias formas de normalizar:

• centrado (centrado medio): de las calificaciones del usuario simplemente restamos la calificación promedio,
  
  * relevante solo para matrices no binarias
  
• estandarización (puntaje z): además del centrado, dividimos su calificación por la desviación estándar del usuario,
  
  * aquí, después de la conversión inversa, la calificación puede ir más allá de la escala (es decir, 6 en una escala de cinco puntos), pero tales situaciones son bastante raras y se resuelven simplemente redondeando hacia la estimación aceptable más cercana.
  
• doble estandarización: la primera vez que normalizamos las calificaciones de los usuarios, la segunda vez, las calificaciones de los productos.
  
  Si la película "La mejor película" tiene una calificación promedio de 2.5, y el usuario le da 5, entonces este es un factor importante que indica que tales películas son claramente de su gusto.
  

La "similitud" o correlación de las preferencias de dos usuarios puede considerarse de diferentes maneras. De hecho, solo necesitamos comparar dos vectores. Enumeramos algunos de los más populares.

1. — , .
   
   
   
   
   — , .
   
   50 / min(50, Rating intersection) damping factor, .
   
2. 
   
   — , .. , . .
   
   
   
3. 
   
   . , — , .
   
   
   
   — , (.. ), . , .
   

Un desarrollo interesante del enfoque de colaboración son las llamadas recomendaciones basadas en la confianza, que tienen en cuenta no solo la proximidad de las personas de acuerdo con sus intereses, sino también su proximidad "social" y el grado de confianza entre ellas. Si, por ejemplo, vemos que en Facebook la niña visita periódicamente la página con las grabaciones de audio de su amiga, entonces confía en su gusto musical. Por lo tanto, las recomendaciones para la niña pueden mezclar completamente nuevas canciones de la lista de reproducción de la amiga.

Justificación de recomendaciones

Es importante que el usuario confíe en el sistema de recomendación, y para esto debe ser simple y comprensible. Si es necesario, siempre debe estar disponible una explicación comprensible de la recomendación (en la explicación terminológica en inglés).

Como parte de la explicación, es bueno mostrar la evaluación del producto de los vecinos, de acuerdo con qué atributo (por ejemplo, el actor o el director), hubo una coincidencia, así como mostrar la confianza del sistema en la evaluación (confianza). Para no sobrecargar la interfaz, puede poner toda esta información en el botón "Más información".

Por ejemplo:

• "Puede que te guste la película ... porque se reproduce allí ... y ..."
• "Los usuarios con gustos musicales similares calificaron el álbum ... 4.5 de 5".

Resumen

Esto finalizará la primera parte del artículo. Examinamos el enunciado general del problema, hablamos de recomendaciones no personales, describimos dos enfoques clásicos (filtrado basado en contenido y colaborativo), y también tocamos el tema de las recomendaciones sustanciales. En general, estos dos enfoques son suficientes para construir un sistema de recomendación listo para la producción. En la siguiente parte, continuaré la revisión y hablaré sobre métodos más modernos, incluidos los que involucran redes neuronales y aprendizaje profundo, así como sobre modelos híbridos.