¿Cómo uso el SVD en el filtrado colaborativo?

30

Estoy un poco confundido con cómo se usa la SVD en el filtrado colaborativo. Supongamos que tengo un gráfico social y construyo una matriz de adyacencia desde los bordes, luego tomo un SVD (olvidemos la regularización, las tasas de aprendizaje, las optimizaciones de dispersión, etc.), ¿cómo uso este SVD para mejorar mis recomendaciones?

Supongamos que mi gráfico social corresponde a instagram, y me encargaron la responsabilidad de recomendar a los usuarios en el servicio, basado únicamente en el gráfico social. Primero construiría una matriz de adyacencia , tomaría la SVD, , elegiría los primeros valores propios, ¿y luego qué? ( m × m ) A = U s V kA (m×m)A=UsVk

Presumiblemente crearía un nuevo conjunto de matrices: entonces, ¿qué hace uno?

Unortemiwmetro×ksnortemiwk×kVnortemiwk×metro

He buscado en la web, y la mayoría de los enlaces se centran en calcular el SVD, pero nadie te dice qué hacer con él. ¿Entonces qué debo hacer?

Vishal
fuente
1
Esto puede responder a su pregunta: datascience.stackexchange.com/a/16523
avli

Respuestas:

7

Sin embargo: con SVD puro de vainilla, es posible que tenga problemas para recrear la matriz original, y mucho menos para predecir valores para elementos faltantes. La regla general útil en esta área es calcular la calificación promedio por película y restar este promedio para cada combinación de usuario / película, es decir, restar el sesgo de película de cada usuario. Luego , se recomienda que ejecute SVD y, por supuesto, tendría que registrar estos valores de sesgo en alguna parte, para recrear clasificaciones o predecir valores desconocidos. Había leído la publicación de Simon Funk sobre SVD para obtener recomendaciones: inventó un enfoque SVD incremental durante la competencia de Netflix.

http://sifter.org/~simon/journal/20061211.html

Supongo que la degradación de la matriz A antes de SVD tiene sentido, ya que PCA primo cercano de SVD también funciona de manera similar. En términos de cálculo incremental, Funk me dijo que si no degrada, la dirección del primer gradiente domina el resto del cálculo. He visto esto de primera mano, básicamente sin degradar las cosas no funcionan.

BBDynSys
fuente
24

Me gustaría ofrecer una opinión disidente:

Bordes faltantes como valores perdidos

En un problema de filtrado colaborativo, las conexiones que no existen (el usuario no ha calificado el elemento j , la persona x no se ha hecho amigo de la persona y ) generalmente se tratan como valores faltantes para predecir, en lugar de como ceros. Es decir, si el usuario i no ha valorado elemento j , queremos adivinar lo que podría evaluar si él había clasificado. Si persona xyojXyyojX no se ha hecho amiga de , queremos adivinar qué tan probable es que quiera ser su amigo. Las recomendaciones se basan en los valores reconstruidos.y

Cuando toma la SVD del gráfico social (por ejemplo, conéctelo svd()), básicamente está imponiendo ceros en todos esos puntos faltantes. Que esto es problemático es más obvio en la configuración de clasificación de elementos de usuario para el filtrado colaborativo. Si tuviera una manera confiable de completar las entradas faltantes, no necesitaría usar SVD en absoluto. Solo daría recomendaciones basadas en las entradas completadas. Si no tengo una manera de hacer eso, entonces no debería llenarlos antes de hacer el SVD. *

SVD con valores perdidos

Por supuesto, el svd() función no sabe cómo hacer frente a los valores perdidos. Entonces, ¿qué se supone que debes hacer exactamente? Bueno, hay una manera de replantear el problema como

"Encuentra la matriz de rango que está más cerca de la matriz original"k

Ese es realmente el problema que estás tratando de resolver y no vas a usar svd()para resolverlo. Una forma que funcionó para mí (en los datos del premio de Netflix) fue esta:

  • Tratar de encajar las entradas con un modelo simple, por X^yo,j=μ+αyo+βj . Esto realmente hace un buen trabajo.

  • Asigne a cada usuario un vector k u i y cada elemento j un vector k v j . (En su caso, cada persona obtiene un vector k derecho e izquierdo ). En última instancia, estará prediciendo los residuos como productos de punto: u i m v j myoktuyojkvjktuyometrovjmetro

  • Use algún algoritmo para encontrar los vectores que minimizan la distancia a la matriz original. Por ejemplo, usa este papel

¡La mejor de las suertes!

*: Lo que recomienda Tenali es básicamente vecinos más cercanos. Intenta encontrar usuarios similares y hacer recomendaciones al respecto. Desafortunadamente, el problema de la escasez (~ 99% de la matriz carece de valores) hace que sea difícil encontrar vecinos más cercanos usando la distancia del coseno o similitud de jaccard o lo que sea. Por lo tanto, recomienda hacer una SVD de la matriz (con ceros imputados a los valores faltantes) para comprimir primero a los usuarios en un espacio de características más pequeño y luego hacer comparaciones allí. Hacer SVD-vecinos más cercanos está bien, pero aún así recomendaría hacer el SVD de la manera correcta (quiero decir ... a mi manera). ¡No es necesario hacer una imputación de valor sin sentido!

Stumpy Joe Pete
fuente
Esta fue en realidad la respuesta que estaba buscando y quería escuchar :) ¡Muchas gracias!
Vishal
Curiosamente, la pregunta era "He buscado en la web, y la mayoría de los enlaces se centran en calcular el SVD, pero nadie te dice qué hacer con él. Entonces, ¿qué debo hacer?" o para el caso, el título dice: "¿Cómo uso el SVD en el filtrado colaborativo?"
TenaliRaman
Sí, y mi respuesta resumió cómo lo uso en el filtrado colaborativo.
Stumpy Joe Pete
1
+1, según tengo entendido, no estás calculando la matriz de bajo rango usando SVD, sino un método iterativo para minimizar el error al cuadrado, ¿verdad? Sin embargo, si quiero usar SVD, entonces debo completar las entradas faltantes con algunos valores antes de hacer la factorización matricial, ¿verdad?
aguacate
1
svre()
14

La razón por la que nadie te dice qué hacer con él es porque si sabes lo que hace SVD, entonces es un poco obvio qué hacer con él :-).

Como sus filas y columnas son del mismo conjunto, explicaré esto a través de una matriz diferente A. Deje que la matriz A sea tal que las filas sean los usuarios y las columnas sean los elementos que le gusten al usuario. Tenga en cuenta que esta matriz no necesita ser simétrica, pero en su caso, supongo que resulta ser simétrica. Una forma de pensar en SVD es la siguiente: SVD encuentra un espacio de características oculto donde los usuarios y elementos que les gustan tienen vectores de características que están estrechamente alineados.

UNA=U×s×VUV matriz representa los vectores de características correspondientes a los elementos en el espacio de características ocultas.

Ahora, si le doy dos vectores del mismo espacio de características y le pido que encuentre si son similares, ¿qué es lo más simple que se le ocurre para lograrlo? Producto punteado.

yojyoUj

TenaliRaman
fuente
Dos preguntas: 1) ¿Rellena los valores faltantes con cero (elemento j no revisado por el usuario i) antes de ejecutar SVD? 2) ¿Cómo calcula si a un nuevo usuario le gustará el elemento j?
B_Miner
1
@B_Miner Hola, perdón por la respuesta tardía. Las respuestas: 1) Bueno, sí, generalmente llenamos los valores faltantes con cero antes de ejecutar SVD. Sin embargo, generalmente recomiendo llenarlo con una calificación distinta de cero; por ejemplo, puede completar los valores faltantes por la calificación promedio que el usuario ha dado hasta ahora. 2) El enfoque basado en SVD es solo para usuarios conocidos y artículos conocidos. No puede manejar nuevos usuarios o nuevos elementos. Y cómo puede hacerlo, si entra un nuevo usuario, no sabemos nada sobre él en este marco para predecir.
TenaliRaman
1
@B_Miner Si desea trabajar con nuevos usuarios / elementos, debemos suponer que tenemos acceso a algunas características de usuario y características de elementos. Luego, puede usar un modelo más sofisticado como PDLF (modelo predictivo de factor latente discreto). Esto le permitirá manejar nuevos usuarios / elementos porque funciona con un espacio de características conocido.
TenaliRaman el
@TenaliRaman No estoy seguro si verá esto, pero aquí va. Así que he estado usando modelos de temas (LDA) para crear características para los usuarios (literalmente usuarios) en función de los documentos que han leído. Acabo de promediar los vectores de tema para obtener un "vector de tema de usuario". Quiero hacer algo similar con SVD (o ALS posiblemente). Digamos que calculo SVD utilizando datos conocidos de elementos de usuario, y luego tengo nuevos usuarios que "visitan" varios elementos conocidos. En este caso, los vectores del elemento son conocidos pero los vectores del usuario son desconocidos. ¿Puedo usar los vectores de elementos para calcular el vector de usuario o necesito calcular SVD nuevamente usando todos los datos?
thecity2
gran respuesta tenali. muy útil para entender el concepto
Nihal
3

Esto es para tratar de responder la parte de "cómo" de la pregunta para aquellos que desean implementar prácticamente recomendaciones de SVD dispersas o inspeccionar el código fuente para obtener detalles. Puede usar un software FOSS estándar para modelar SVD disperso. Por ejemplo, vowpal wabbit, libFM, o redsvd.

vowpal wabbittiene 3 implementaciones de algoritmos "SVD-like" (cada uno seleccionable por una de las 3 opciones de línea de comando). Estrictamente hablando, estos deberían llamarse "factorización matricial aproximada, iterativa" en lugar de "SVD" pura "clásica", pero están estrechamente relacionados con la SVD. Puede pensar en ellos como una factorización SVD aproximada muy computacionalmente eficiente de una dispersa (principalmente ceros) matriz.

Aquí hay una receta completa y funcional para hacer recomendaciones de películas al estilo de Netflix vowpal wabbity su --lrqopción "cuadrática de bajo rango" ( ) que parece funcionar mejor para mí:

Archivo de formato del conjunto de datos ratings.vw(cada calificación en una línea por usuario y película):

5 |user 1 |movie 37
3 |user 2 |movie 1019
4 |user 1 |movie 25
1 |user 3 |movie 238
...

Donde el primer número es la calificación (1 a 5 estrellas) seguido de la identificación del usuario que calificó y la identificación de la película que se calificó.

Los datos de prueba están en el mismo formato pero pueden (opcionalmente) omitir la columna de calificaciones:

 |user 1 |movie 234
 |user 12 |movie 1019
...

opcionalmente porque para evaluar / probar predicciones necesitamos calificaciones para comparar las predicciones. Si omitimos las clasificaciones, vowpal wabbittodavía pronosticaremos las clasificaciones pero no podremos estimar el error de predicción (valores pronosticados vs valores reales en los datos).

Para entrenar, le pedimos vowpal wabbitque encuentre un conjunto de Nfactores de interacción latente entre los usuarios y las películas que les gustan (o no) Puede pensar en esto como encontrar temas comunes en los que usuarios similares califican un subconjunto de películas de manera similar y usan estos temas comunes para predecir cómo un usuario calificaría una película que aún no ha calificado.

vw opciones y argumentos que necesitamos usar:

  • --lrq <x><y><N> encuentra factores latentes "cuadráticos de bajo rango".
  • <x><y>: "um" significa cruzar los espacios de nombres u [sers] ym [ovie] en el conjunto de datos. Tenga en cuenta que solo la primera letra de cada espacio de nombres se usa con la --lrqopción.
  • <N>: a N=14continuación se muestra el número de factores latentes que queremos encontrar
  • -f model_filename: escribe el modelo final en model_filename

Entonces, un comando simple de entrenamiento completo sería:

    vw --lrq um14 -d ratings.vw -f ratings.model

Una vez que tengamos el ratings.modelarchivo del modelo, podemos usarlo para predecir calificaciones adicionales en un nuevo conjunto de datos more_ratings.vw:

    vw -i ratings.model -d more_ratings.vw -p more_ratings.predicted

Las predicciones se escribirán en el archivo more_ratings.predicted.

Utilizando demo/movielensen el vowpalwabbitárbol fuente, obtengo ~ 0.693 MAE (Error absoluto medio) después de entrenar en 1 millón de clasificaciones de usuario / película ml-1m.ratings.train.vwcon 14 factores latentes (lo que significa que la matriz media SVD es una matriz de 14x14 filas x columnas) y probar en el independiente equipo de pruebaml-1m.ratings.test.vw . ¿Qué tan bueno es 0.69 MAE? Para el rango completo de posibles predicciones, incluido el caso no calificado (0) [0 a 5], un error de 0.69 es ~ 13.8% (0.69 / 5.0) del rango completo, es decir, aproximadamente 86.2% de precisión (1 - 0.138).

Puede encontrar ejemplos y una demostración completa de un conjunto de datos similar (lente de película) con documentación en el vowpal wabbitárbol de origen en github:

Notas:

  • La movielensdemostración se utiliza varias opciones omití (para simplificar) de mi ejemplo: en particular --loss_function quantile, --adaptivey--invariant
  • La --lrqimplementación en vwes mucho más rápida que --rank, en particular, al almacenar y cargar los modelos.

Créditos

  • --rank La opción vw fue implementada por Jake Hofman
  • --lrq La opción vw (con deserción opcional) fue implementada por Paul Minero
  • Widgetpal Wabbit (también conocido como VW) es el hijo del cerebro de John Langford
arielf
fuente
1

Yo diría que el nombre SVDes engañoso. De hecho, elSVD método en el sistema de recomendación no utiliza directamente la factorización SVD. En cambio, utiliza el descenso de gradiente estocástico para entrenar los sesgos y los vectores de factores.

Los detalles de los algoritmos SVDy SVD++para el sistema de recomendación se pueden encontrar en las Secciones 5.3.1y 5.3.2en el libro Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor. Recommender Systems Handbook. 1st edition, 2010.

En Python, hay un paquete bien establecido que implementa estos algoritmos llamados surprise. En su documentación , también mencionan los detalles de estos algoritmos.

lenhhoxung
fuente