Descomposición de valores singulares frente a factorización matricial en sistemas de recomendación

Recientemente, después de ver la clase de Sistemas de recomendación del curso de aprendizaje automático del profesor Andrew Ng, me sentí muy incómodo al no entender cómo funciona la factorización matricial.

Sé que a veces las matemáticas en Machine Learning son muy oscuras. Es mejor si lo pensamos como una caja negra, pero ese modelo fue muy “mágico” para mis estándares.

En tales situaciones, por lo general trato de buscar en Google más referencias para comprender mejor el concepto. Esta vez me confundí aún más. Mientras que el profesor Ng llamó al algoritmo como factorización matricial (factor bajo), encontré una nomenclatura diferente en Internet: Descomposición de valores singulares.

Lo que más me confundió fue que la descomposición de valores singulares era muy diferente de lo que había enseñado el profesor Ng. La gente seguía sugiriendo que ambos eran lo mismo.

En este texto, resumiré mis hallazgos y trataré de aclarar parte de la confusión que esos términos pueden causar.

Sistemas de recomendación

Los sistemas de recomendación (RS) son solo formas automatizadas de recomendar algo a alguien. Estos sistemas son ampliamente utilizados por empresas de comercio electrónico, servicios de transmisión por secuencias y sitios web de noticias. Ayuda a reducir la fricción de los usuarios cuando intentan encontrar algo que les gusta.

Definitivamente, los RS no son algo nuevo: se han presentado desde al menos 1990. De hecho, parte del reciente bombo de aprendizaje automático se puede atribuir al interés en RS. En 2006, Netflix causó sensación cuando patrocinó un concurso para encontrar el mejor RS para sus películas. Como veremos pronto, ese evento está relacionado con el lío de nomenclatura que siguió.

La representación matricial

Hay muchas formas en que una persona puede pensar en recomendar una película a alguien. Una estrategia que resultó ser muy buena es tratar las calificaciones de las películas como una matriz de Usuarios x Películas como esta:

En esa matriz, los signos de interrogación representan las películas que un usuario no ha calificado. Entonces, la estrategia es predecir esas calificaciones de alguna manera y recomendar a los usuarios las películas que probablemente les gustarán.

Factorización de matrices

Una comprensión realmente inteligente hecha por los chicos que participaron en la competencia de Netflix (especialmente Simon Funk) fue que las calificaciones de los usuarios no eran solo conjeturas al azar. Los evaluadores probablemente siguen alguna lógica en la que ponderan las cosas que les gustan de una película (una actriz o un género específico) con las cosas que no les gustan (larga duración o chistes malos) y luego crean una partitura.

Ese proceso se puede representar mediante una fórmula lineal del siguiente tipo:

donde xₘ es un vector columna con los valores de las características de la película m y θᵤ es otro vector columna con los pesos que el usuario u da a cada función. Cada usuario tiene un conjunto diferente de pesos y cada película tiene un conjunto diferente de valores para sus características.

Resulta que si arreglamos arbitrariamente el número de características e ignoramos las calificaciones faltantes, podemos encontrar un conjunto de valores de pesos y características que crean una nueva matriz con valores cercanos a la matriz de calificación original. Esto se puede hacer con el descenso de gradiente, muy parecido al que se usa en la regresión lineal. En lugar de eso, ahora estamos optimizando dos conjuntos de parámetros (pesos y características) al mismo tiempo.

Usando la tabla que di como ejemplo anterior, el resultado del problema de optimización generaría la siguiente matriz nueva:

Tenga en cuenta que la matriz resultante no puede ser una copia exacta de la original en la mayoría de los conjuntos de datos reales porque en la vida real las personas no están haciendo multiplicaciones y sumas para calificar una película. En la mayoría de los casos, la calificación es solo un presentimiento que también puede verse afectado por todo tipo de factores externos. Aún así, nuestra esperanza es que la fórmula lineal sea una buena manera de expresar la lógica principal que impulsa las calificaciones de los usuarios.

Bien, ahora tenemos una matriz aproximada. Pero, ¿cómo diablos nos ayuda eso a predecir las calificaciones que faltan? Recuerde que para construir la nueva matriz, creamos una fórmula para llenar todos los valores, incluidos los que faltan en la matriz original. Entonces, si queremos predecir la calificación faltante de un usuario en una película, simplemente tomamos todos los valores de características de esa película, multiplicamos por todos los pesos de ese usuario y sumamos todo. Entonces, en mi ejemplo, si quiero predecir la calificación del Usuario 2 de la Película 1, puedo hacer el siguiente cálculo:

Para aclarar las cosas, podemos disociar las θ y las x y ponerlas en sus propias matrices (digamos P y Q ). Eso es efectivamente una factorización matricial, de ahí el nombre utilizado por el Prof. Ng.

Esa factorización de matrices es básicamente lo que hizo Funk. Obtuvo el tercer lugar en la competencia de Netflix, atrayendo mucha atención (que es un caso interesante de que un tercer lugar sea más famoso que los ganadores). Su enfoque se ha replicado y perfeccionado desde entonces y todavía se utiliza en muchas aplicaciones.

Valor singular de descomposición

Introduzca la descomposición de valores singulares (SVD). SVD es una forma elegante de factorizar una matriz en otras tres matrices ( A = UΣVᵀ ). La forma en que se hace SVD garantiza que esas 3 matrices tengan algunas propiedades matemáticas agradables.

Hay muchas aplicaciones para la enfermedad vesicular porcina. Uno de ellos es el análisis de componentes principales (PCA), que simplemente reduce un conjunto de datos de dimensión n a dimensión k ( k <n ).

No les daré más detalles sobre las SVD porque yo mismo no me conozco. El caso es que no es lo mismo que hicimos con Matrix Factorization. La mayor evidencia es que SVD crea 3 matrices mientras que la factorización de matrices de Funk crea solo 2.

Entonces, ¿por qué SVD sigue apareciendo cada vez que busco sistemas de recomendación? Tuve que cavar un poco, pero finalmente encontré algunas gemas ocultas. Según Luis Argerich:

Los algoritmos de factorización de matrices utilizados para los sistemas de recomendación intentan encontrar dos matrices: P, Q como P * Q coincide con los valores CONOCIDOS de la matriz de utilidad. Este principio apareció en el famoso documento SVD ++ "La factorización se encuentra con el vecindario" que desafortunadamente usaba el nombre "SVD ++" para un algoritmo que no tiene absolutamente ninguna relación con la SVD .

Para que conste, creo que Funk, no los autores de SVD ++, propuso por primera vez la factorización de matriz mencionada para los sistemas de recomendación. De hecho, SVD ++, como su nombre indica, es una extensión del trabajo de Funk.

Xavier Amatriain nos da una imagen más amplia:

Comencemos señalando que el método generalmente denominado "SVD" que se utiliza en el contexto de las recomendaciones no es estrictamente hablando la descomposición matemática de valores singulares de una matriz, sino más bien una forma aproximada de calcular la aproximación de rango bajo de la matriz. minimizando la pérdida por error al cuadrado. Una forma más precisa, aunque más genérica, de llamar a esto sería factorización matricial. La versión inicial de este enfoque en el contexto del Premio Netflix fue presentada por Simon Funk en su famosa publicación de blog Try This at Home. Es importante señalar que el enfoque de la “verdadera SVD” se había aplicado años antes a la misma tarea, sin tanto éxito práctico.

Wikipedia también tiene información similar enterrada en su artículo de factorización de matrices (sistemas de recomendación):

El algoritmo original propuesto por Simon Funk en su publicación de blog factorizaba la matriz de calificación usuario-elemento como el producto de dos matrices de menor dimensión, la primera tiene una fila para cada usuario, mientras que la segunda tiene una columna para cada elemento. La fila o columna asociada con un usuario o elemento específico se conoce como factores latentes. Tenga en cuenta que, a pesar de su nombre, en FunkSVD no se aplica una descomposición de valores singulares.

Para resumir:

1. SVD es una técnica matemática algo compleja que factoriza matrices en tres nuevas matrices y tiene muchas aplicaciones, incluyendo PCA y RS.

2. Simon Funk aplicó una estrategia muy inteligente en la competencia de Netflix de 2006, factorizando una matriz en otras dos y usando el gradiente descendente para encontrar valores óptimos de características y pesos. No es SVD , pero usó ese término de todos modos para describir su técnica.

3. El término más apropiado para lo que hizo Funk es Factorización de matrices.

4. Debido a los buenos resultados y la fama que siguió, la gente todavía llama a esa técnica SVD porque, bueno, así es como la llamó el autor.

Espero que esto ayude a aclarar un poco las cosas.