Anatomía de los sistemas de recomendación. Parte dos

Hace una semana, hice una descripción general de los algoritmos de recomendación existentes aquí . En este artículo continuaré esta revisión: hablaré sobre la variante basada en elementos del filtrado colaborativo, sobre métodos basados ​​en descomposiciones de matrices, problemas de prueba, así como algoritmos menos "no retorcidos" (pero no menos interesantes).

Filtrado colaborativo (opción basada en elementos)

El enfoque basado en elementos es una alternativa natural al enfoque clásico basado en el usuario descrito en la primera parte, y lo repite casi por completo, excepto por un punto: se aplica a la matriz de preferencias transpuesta. Es decir buscando productos relacionados, no usuarios.

Permítame recordarle que el filtrado colaborativo basado en el usuario (CF basado en el usuario) busca para cada cliente un grupo de clientes más similar (en términos de compras anteriores) y promedia sus preferencias. Estas preferencias promedio sirven como recomendaciones para el usuario. En el caso del filtrado colaborativo de productos (CF basado en artículos), se buscan los vecinos más cercanos en el conjunto de productos, columnas de la matriz de preferencias. Y el promedio ocurre precisamente en ellos.

De hecho, si los productos son sustancialmente similares, lo más probable es que les guste o no les guste al mismo tiempo. Por lo tanto, cuando vemos que dos productos tienen correlaciones fuertes, esto puede indicar que son productos similares.

Ventajas de basado en artículo sobre basado en usuario:

• Cuando hay muchos usuarios (casi siempre), la tarea de encontrar al vecino más cercano se vuelve poco computable. Por ejemplo, para 1 millón de usuarios necesita calcular y almacenar $$$\ frac {1} {2} 10 ^ 6 * 10 ^ 6$~ 500 mil millones de distancias. Si la distancia está codificada con 8 bytes, esto da como resultado 4TB solo para la matriz de distancia. Si lo hacemos basado en elementos, entonces la complejidad de los cálculos disminuye con $$$O (N ^ 2n)$antes $$$O (n ^ 2N)$y la matriz de distancia ya no tiene una dimensión (1 millón por 1 millón), sino, por ejemplo, (100 por 100) por el número de bienes.
  
• El índice de proximidad es mucho más preciso que el índice de proximidad. Esta es una consecuencia directa del hecho de que generalmente hay muchos más usuarios que bienes, y por lo tanto, el error estándar al calcular la correlación de bienes es mucho menor. Solo tenemos más información para sacar una conclusión.
  
• En la versión basada en el usuario, las descripciones de los usuarios suelen ser muy escasas (hay muchos productos, pocas clasificaciones). Por un lado, esto ayuda a optimizar el cálculo: multiplicamos solo aquellos elementos donde hay una intersección. Pero, por otro lado, cuántos vecinos no toma, la lista de productos que puede recomendar es muy pequeña.
  
• Las preferencias del usuario pueden cambiar con el tiempo, pero la descripción del artículo es mucho más estable.
  

El resto del algoritmo repite casi por completo la opción basada en el usuario: la misma distancia del coseno que la medida principal de proximidad, la misma necesidad de normalización de datos. El número de bienes vecinos N generalmente se elige en la región de 20.

Debido al hecho de que la correlación de productos se considera en un mayor número de observaciones, no es tan crítico recalcularla después de cada nueva evaluación, y puede hacerlo periódicamente en el modo batalla.

Varias posibles mejoras al algoritmo:

• Una modificación interesante es considerar la "similitud" de los productos no como distancias típicas del coseno, sino al comparar su contenido (similitud basada en el contenido). Si al mismo tiempo no se tienen en cuenta las preferencias del usuario, dicho filtrado deja de ser "colaborativo". Además, la segunda parte del algoritmo, obtener estimaciones promedio, no cambia de ninguna manera.
• Otra posible modificación es sopesar a los usuarios al calcular la similitud de elementos. Por ejemplo, cuantos más usuarios hagan valoraciones, más peso tendrán al comparar dos productos.
• En lugar de simplemente promediar las estimaciones de productos vecinos, los pesos se pueden seleccionar haciendo una regresión lineal.

Cuando se utiliza el enfoque basado en ítems, las recomendaciones tienden a ser más conservadoras. De hecho, la dispersión de recomendaciones es menor y, por lo tanto, es menos probable que muestre productos no estándar.

Si en la matriz de preferencias usamos la vista de descripción del producto como una calificación, entonces los productos recomendados tienen más probabilidades de ser análogos, productos que a menudo se ven juntos. Si calculamos las calificaciones en la matriz de preferencias en función de las compras, lo más probable es que los productos recomendados sean accesorios, bienes que a menudo se compran juntos.

Evaluación de calidad del sistema

Probar el sistema de recomendación es un proceso difícil y siempre plantea muchas preguntas, principalmente debido a la ambigüedad del concepto mismo de "calidad".

En general, en las tareas de aprendizaje automático, hay dos enfoques principales para las pruebas:

• prueba fuera de línea del modelo en datos históricos usando pruebas retro,
• probando el modelo terminado usando pruebas A / B (lanzamos varias opciones, veamos cuál da el mejor resultado).

Ambos enfoques se utilizan activamente en el desarrollo de sistemas de recomendación. Comencemos con las pruebas fuera de línea.

La principal limitación que tiene que enfrentar es evaluar la precisión del pronóstico que solo podemos hacer en aquellos productos que el usuario ya ha calificado.

El enfoque estándar es la validación cruzada con los métodos Leave-One-Out y Leave-P-Out. La repetición repetida de la prueba con un promedio de los resultados permite obtener una evaluación de calidad más estable.

• Leave-One-Out: el modelo se entrena en todos los objetos evaluados por el usuario, excepto uno, y se prueba en este único objeto. Esto se hace para todos los n objetos, y el promedio se calcula entre las n estimaciones de calidad obtenidas.
• dejar-p-out es lo mismo, pero los puntos p se excluyen en cada paso.

Todas las métricas de calidad se pueden dividir en tres categorías:

• Precisión de predicción: evalúe la precisión de la calificación prevista,
• Apoyo a la decisión: evaluar la relevancia de las recomendaciones,
• Métricas de precisión de clasificación: evalúe la calidad de la clasificación de las recomendaciones emitidas.
  

Desafortunadamente, no existe una única métrica recomendada para todas las ocasiones, y todos los que participan en la prueba del sistema de recomendación lo seleccionan para sus propios fines.

Cuando las calificaciones se califican en una escala continua (0-10), las métricas de clase de precisión de predicción suelen ser suficientes.
Las métricas de clase de soporte de decisiones funcionan con datos binarios (0 y 1, sí y no). Si en nuestra tarea las calificaciones se posponen inicialmente en una escala continua, se pueden convertir a formato binario aplicando la regla decisiva; por ejemplo, si la calificación es inferior a 3.5, consideramos que la calificación es "mala" y, si es mayor, entonces "buena".
Como regla general, las recomendaciones se muestran en una lista de varias posiciones (primero superior, luego en orden descendente de prioridad). Las métricas de clase de precisión de rango miden cuán correcto es el orden en que se muestran las recomendaciones en una lista ordenada.
Si tomamos sistemas de recomendación en negocios en línea, entonces, como regla, tienen dos objetivos (a veces conflictivos):

1. informar al usuario sobre un producto interesante,
2. Aliéntelo a hacer una compra (por correo, compilando una oferta personal, etc.).

Como en cualquier modelo destinado a motivar al usuario a la acción, solo se debe evaluar el aumento incremental en la acción objetivo. Es decir, por ejemplo, cuando se calculan las compras por recomendación, debemos excluir aquellas que el propio usuario hubiera hecho sin nuestro modelo. Si esto no se hace, el efecto de presentar el modelo será sobreestimado en gran medida.

La elevación es un indicador de cuántas veces la precisión de un modelo excede un cierto algoritmo de referencia. En nuestro caso, el algoritmo de referencia puede ser simplemente la falta de recomendaciones. Esta métrica captura bien la parte de compras incrementales y le permite comparar efectivamente diferentes modelos.

Prueba de usuario

Fuente

El comportamiento del usuario es algo poco formalizado y ni una sola métrica describirá completamente los procesos de pensamiento en su cabeza al elegir un producto. La decisión está influenciada por muchos factores. Hacer clic en un enlace con un producto recomendado aún no tiene una calificación alta o incluso interés. Las pruebas en línea ayudan a comprender parcialmente la lógica del cliente. Los siguientes son algunos escenarios para tales pruebas.

El primer y más obvio escenario es el análisis de los eventos del sitio. Observamos qué está haciendo el usuario en el sitio, si está prestando atención a nuestras recomendaciones, si las sigue, qué características del sistema tienen demanda, cuáles no, qué productos se recomiendan mejor y cuáles son peores. Para entender cuál de los algoritmos en su conjunto funciona mejor o simplemente probar una nueva idea prometedora, realizamos pruebas A / B y recopilamos el resultado.

El segundo escenario es recibir comentarios de los usuarios en forma de encuestas y encuestas. Como regla general, estas son preguntas generales para comprender cómo los clientes usan el servicio, lo cual es más importante: relevancia o diversidad, si es posible mostrar productos duplicados o es demasiado molesto. La ventaja del script es que proporciona una respuesta directa a todas estas preguntas.

Dichas pruebas son complicadas, pero para los servicios de grandes recomendaciones es simplemente necesario. Las preguntas pueden ser más complicadas, por ejemplo, "cuál de las listas le parece más relevante", "cuánto se ve la hoja completa", "¿verá esta película / leerá un libro"?

Calificaciones implícitas y datos unarios

Al comienzo de su desarrollo, se utilizaron sistemas de recomendación en servicios en los que el usuario evalúa claramente el producto al calificarlo: estos son Amazon, Netflix y otros sitios de comercio en línea. Sin embargo, con la popularidad de los sistemas de recomendación, era necesario usarlos también donde no hay calificaciones: pueden ser bancos, talleres de reparación de automóviles, quioscos con shawarma y cualquier otro servicio donde, por alguna razón, es imposible establecer un sistema de evaluación. En estos casos, los intereses del usuario solo pueden calcularse mediante signos indirectos: ciertas acciones con el producto indican las preferencias del usuario, por ejemplo, ver la descripción en el sitio, agregar el producto a la cesta, etc. Utiliza el principio de "comprado, ¡significa amor!". Tal sistema de calificación implícita se llama Calificaciones implícitas.

Las clasificaciones implícitas obviamente funcionan peor que las explícitas, ya que agregan un orden de magnitud más ruido. Después de todo, un usuario puede comprar un producto como regalo para su esposa o ir a una página con una descripción del producto, solo para dejar un comentario allí al estilo de "qué tipo de maldad es igual" o para satisfacer su curiosidad natural.

Si en el caso de calificaciones explícitas, tenemos el derecho de esperar que al menos una calificación negativa sea no, no y sí, entonces no tomaremos una calificación negativa de ninguna parte. Si el usuario no compró el libro "Cincuenta sombras de Grey", podría hacerlo por dos razones:

• ella realmente no está interesada en él (este es un caso negativo),
  
• ella está interesada en él, pero él simplemente no sabe de ella (este es un caso positivo perdido).
  

Pero no tenemos datos para distinguir el primer caso del segundo. Esto es malo, porque al entrenar un modelo, debemos reforzarlo en casos positivos y bien en casos negativos, por lo que casi siempre estaremos bien, y como resultado, el modelo estará sesgado.

El segundo caso es la capacidad de dejar solo calificaciones positivas. Un ejemplo sorprendente es el botón Me gusta en las redes sociales. La calificación aquí ya está establecida explícitamente, pero como en el ejemplo anterior, no tenemos ejemplos negativos: sabemos qué canales le gustan al usuario, pero no sabemos cuáles no le gustan.

En ambos ejemplos, la tarea se convierte en una tarea de Clasificación de clase unaria .

La solución más obvia es seguir un camino simple y considerar la ausencia de una calificación como una calificación negativa. En algunos casos esto está más justificado, en algunos menos. Por ejemplo, si sabemos que el usuario probablemente vio el producto (por ejemplo, le mostramos la lista de productos y cambió al producto que le sigue), entonces la falta de transición realmente puede indicar una falta de interés.

Fuente

Algoritmos de factorización

Sería genial describir los intereses del usuario en "trazos" más grandes. No en el formato "le encantan las películas X, Y y Z", sino en el formato "le encantan las comedias rusas modernas". Además del hecho de que esto aumentará la generalización del modelo, también resolverá el problema de una gran dimensionalidad de los datos, porque los intereses se describirán no por un vector de bienes, sino por un vector de preferencias significativamente más pequeño.

Tales enfoques también se denominan descomposición espectral o filtrado de paso alto (ya que eliminamos el ruido y dejamos una señal útil). Hay muchas descomposiciones diferentes de matrices en álgebra, y una de las más utilizadas se llama descomposición SVD (descomposición de valor singular).

El método SVD se usó a fines de los años 80 para seleccionar páginas que tenían un significado similar, pero no contenido, y luego comenzó a usarse en tareas de recomendaciones. El método se basa en la descomposición de la matriz inicial de calificaciones ® en un producto de 3 matrices:

$$$R = U * D * S$donde los tamaños de las matrices $$$(k, m) = (k, r) * (r, r) * (r, m)$y r es
rango de descomposición: un parámetro que caracteriza el grado de detalle de descomposición.

Aplicando esta descomposición a nuestra matriz de preferencias, obtenemos dos matrices de factores (descripciones abreviadas):

U - descripción compacta de las preferencias del usuario,
S es una descripción compacta de las características del producto.

Es importante que con este enfoque no sepamos qué características corresponden a los factores en las descripciones reducidas, para nosotros están codificadas con algunos números. Por lo tanto, SVD es un modelo no interpretado.

Para obtener una aproximación de la matriz de preferencias, es suficiente multiplicar la matriz de factores. Una vez hecho esto, obtenemos un puntaje de calificación para todos los pares cliente-producto.

La familia general de tales algoritmos se llama NMF (factorización matricial no negativa). Como regla, el cálculo de tales expansiones lleva mucho tiempo, por lo tanto, en la práctica, a menudo recurren a sus variantes iterativas aproximadas.

ALS (mínimos cuadrados alternos) es un algoritmo iterativo popular para descomponer una matriz de preferencias en un producto de 2 matrices: factores de usuario (U) y factores de producto (I). Funciona según el principio de minimizar el error estándar de las clasificaciones. La optimización se realiza alternativamente, primero por factores del usuario, luego por factores del producto. Además, para evitar el reentrenamiento, se agregan coeficientes de regularización al error estándar.


Si complementamos la matriz de preferencias con una nueva dimensión que contenga información sobre el usuario o el producto, podremos expandir no la matriz de preferencias, sino el tensor. Por lo tanto, utilizaremos más información disponible y posiblemente obtendremos un modelo más preciso.

Otros enfoques

Reglas de asociación

Las reglas asociativas generalmente se usan en el análisis de correlaciones de productos (Market Basket Analysis) y se ven así: "si hay leche en el cheque del cliente, en el 80% de los casos habrá pan". Es decir, si vemos que el cliente ya ha puesto leche en la canasta, es hora de recordar el pan.

Esto no es lo mismo que el análisis de compras espaciadas en el tiempo, pero si consideramos toda la historia como una gran canasta, entonces podemos aplicar completamente este principio aquí. Esto puede estar justificado cuando, por ejemplo, vendemos bienes caros de una sola vez (crédito, vuelo).

RBM (Máquinas de Bolzman restringidas)

Las máquinas de Boltzmann limitadas son un enfoque relativamente antiguo basado en redes neuronales recurrentes estocásticas. Es un modelo con variables latentes y en esto es similar a la descomposición SVD. También busca la descripción más compacta de las preferencias del usuario, que se codifica utilizando variables latentes. El método no se desarrolló para buscar recomendaciones, pero se usó con éxito en las principales soluciones del Premio Netflix y todavía se usa en algunas tareas.

Autoencoders

Se basa en el mismo principio de descomposición espectral, razón por la cual esas redes también se denominan autocodificadores de eliminación de ruido. La red primero colapsa los datos del usuario que conoce en una representación compacta, tratando de dejar solo información significativa, y luego restaura los datos a su dimensión original. El resultado es un tipo de plantilla promediada y sin ruido mediante la cual puede evaluar el interés en cualquier producto.

DSSM (modelos de similitud semántica profunda)

Uno de los nuevos enfoques. Todo el mismo principio, pero en el papel de las variables latentes, aquí están las descripciones internas del tensor de los datos de entrada (incrustaciones). Inicialmente, el modelo se creó para la coincidencia de consultas con documentos (así como recomendaciones basadas en contenido), pero se transforma fácilmente en la tarea de hacer coincidir usuarios y productos.


La variedad de arquitecturas de redes profundas es infinita, por lo que Deep Learning proporciona un campo de experimentación verdaderamente amplio para los sistemas de recomendación.

Soluciones híbridas

En la práctica, rara vez se usa un solo enfoque. Como regla, varios algoritmos se combinan en uno para lograr el máximo efecto.

Las dos ventajas principales de combinar modelos son una mayor precisión y la posibilidad de una sintonización más flexible para diferentes grupos de clientes. Las desventajas son menos interpretabilidad y mayor complejidad de implementación y soporte.

Varias estrategias combinadas:

• Ponderación: lea el pronóstico promedio ponderado para varias estimaciones,
  
• Apilamiento: las predicciones de modelos individuales son entradas de otro (meta) clasificador que aprende a ponderar correctamente las estimaciones intermedias,
  

• Conmutación: aplique diferentes algoritmos para diferentes productos / usuarios,
  
• Mezcla: se calculan las recomendaciones sobre diferentes algoritmos y luego se combinan en una sola lista.
  

Por ejemplo, se utiliza un recomendador basado en contenido y, como una de las características, el resultado del filtrado colaborativo.

Apilamiento ponderado de características (lineal):

$$

$$P(u,i) = w_1 P_1(u,i) + w_2 P_2(u,i) + … + w_n P_n(u,i)$$

Pesas $$$w_1,w_2 … w_n$

$$

$$P(u,i) = f_1(u,i) P_1(u,i) + f_2(u,i) P_2(u,i) + … + f_n(u,i) P_n(u,i)$$

Netflix

El Premio Netflix fue una competencia celebrada en 2009 que exigía a los usuarios predecir las calificaciones de los usuarios de la biblioteca de películas de Netflix. Un buen premio de $ 1 millón en premios causó revuelo y atrajo a un gran número de participantes, incluidas personas muy famosas en IA.

Fue una tarea con calificaciones explícitas, los puntajes se establecieron en una escala de 1 a 5 y la precisión del pronóstico fue evaluada por RMSE. La mayoría de los primeros lugares fueron ocupados por grandes conjuntos de clasificadores.

El conjunto ganador utilizó modelos de las siguientes clases:

• modelo básico: un modelo de regresión basado en estimaciones promedio
  
• filtrado colaborativo - filtrado colaborativo
  
• RBM - Máquinas limitadas de Boltzmann
  
• bosques aleatorios - modelo predictivo
  

El aumento de gradiente tradicional se usó como un meta-algoritmo que combinaba estimaciones de algoritmos locales.

Resumen

La tarea de generar recomendaciones es muy simple: compilamos una matriz de preferencias con estimaciones de los usuarios que conocemos, si resulta, complementamos estas estimaciones con información sobre el cliente y el producto, e intentamos completar los valores desconocidos.

A pesar de la simplicidad de la declaración, se publican cientos de artículos que describen métodos fundamentalmente nuevos para resolverlo. En primer lugar, esto se debe a un aumento en la cantidad de datos recopilados que se pueden usar en el modelo y un aumento en el papel de las calificaciones implícitas. En segundo lugar, con el desarrollo del aprendizaje profundo y el advenimiento de nuevas arquitecturas de redes neuronales. Todo esto multiplica la complejidad de los modelos.

Pero en general, toda esta diversidad se reduce a un conjunto muy pequeño de enfoques, que traté de describir en este artículo.