Factorización de matrices

La factorización de matrices es un modelo de incorporación simple. Dado el matriz de comentarios A \(\in R^{m \times n}\), en la que \(m\) es la la cantidad de usuarios (o consultas) \(n\) y la cantidad de elementos, el modelo aprende:

• Una matriz de incorporación de usuarios \(U \in \mathbb R^{m \times d}\), donde la fila i es la incorporación para el usuario i.
• Una matriz de incorporación de elementos \(V \in \mathbb R^{n \times d}\), en la que la fila j es la incorporación del elemento j.

Las incorporaciones se aprenden de modo que el producto \(U V^T\) es un una buena aproximación de la matriz de retroalimentación A. Observa que los \((i, j)\) el ingreso de \(U . V^T\) es simplemente el producto escalar \(\langle U_i, V_j\rangle\) de las incorporaciones del usuario \(i\) y el elemento \(j\), a los que quieres acercarte \(A_{i, j}\).

Nota: La factorización de matrices suele ofrecer una representación más compacta que la de aprendiendo la matriz completa. La matriz completa tiene entradas \(O(nm)\) , mientras que las matrices de incorporación \(U, \ V\) tienen \(O((n+m)d)\) entradas, en las que la dimensión de incorporación \(d\) suele ser mucho más pequeña que \(m\) y \(n\). Como resultado, la factorización de matrices encuentra estructura latente en los datos, suponiendo que las observaciones se encuentran cerca de un subespacio de baja dimensión. En el ejemplo anterior, los valores de n, m y d son tan bajos que la la ventaja es insignificante. Sin embargo, en los sistemas de recomendación del mundo real, sin embargo, la factorización de matrices puede ser mucho más compacta que el aprendizaje la matriz completa.

Elige la función objetiva

Una función objetiva intuitiva es la distancia al cuadrado. Para ello, minimiza la suma de errores cuadráticos en todos los pares de entradas observadas:

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]

En esta función objetiva, solo sumas los pares observados (i, j), es decir, sobre valores distintos de cero en la matriz de feedback. Sin embargo, solo la suma sobre los valores de uno no es una buena idea, ya que una matriz de todos tendrá una pérdida mínima y producir un modelo que no pueda hacer recomendaciones eficaces y eso se generaliza mal.

Quizás podrías tratar los valores no observados como cero y sumar sobre todos entradas de la matriz. Esto corresponde a minimizar el al cuadrado Frobenius distancia entre \(A\) y su aproximación \(U V^T\):

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]

Puedes resolver este problema cuadrático mediante Descomposición de valor singular (SVD) de la matriz. Sin embargo, SVD tampoco es una gran solución porque, en aplicaciones reales, matrix \(A\) puede estar muy dispersa. Por ejemplo, piensa en todos los videos en YouTube en comparación con todos los videos que un usuario específico miró. La solución \(UV^T\) (que corresponde a la aproximación del modelo de la matriz de entrada) estarán cerca de cero, lo que generará generalización.

En cambio, la factorización de matrices ponderada descompone el objetivo en las siguientes dos sumas:

• Es una suma sobre las entradas observadas.
• Es una suma sobre las entradas no observadas (tratadas como ceros).

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]

Aquí, \(w_0\) es un hiperparámetro que pondera los dos términos para que el objetivo no esté dominado por uno u otro. Ajustar este hiperparámetro es muy importante.

Nota: En aplicaciones prácticas, también debes ponderar los valores observados con cuidado. Por ejemplo, elementos frecuentes (por ejemplo, videos populares de YouTube) o las consultas frecuentes (por ejemplo, usuarios pesados) pueden dominar la función objetiva. Puedes corregir este efecto al ejemplos de entrenamiento con ponderación para considerar la frecuencia de los artículos. En otras palabras, puedes reemplazar la función objetiva por lo siguiente:

\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]

donde \(w_{i, j}\) es una función de la frecuencia de la consulta i y el elemento j.

Minimizar la función objetiva

Entre los algoritmos comunes para minimizar la función objetiva, se incluyen los siguientes:

• Descenso de gradientes estocástico (SGD) es un método genérico para minimizar las funciones de pérdida.

• Weighted Alternating Least Squares (WALS) se especializa en esto. un objetivo concreto.

El objetivo es cuadrático en cada una de las dos matrices U y V. (Nota, sin embargo, que el problema no es conjuntamente convexo). WALS funciona inicializando las incorporaciones de forma aleatoria y alterna entre lo siguiente:

• Corregir \(U\) y resolver \(V\)
• Corregir \(V\) y resolver \(U\)

Cada etapa puede resolverse exactamente (mediante la solución de un sistema lineal) y puede distribuirse. Esta técnica garantiza la convergencia, ya que cada paso garantiza la disminución de la pérdida.

SGD frente a WALS

SGD y WALS tienen ventajas y desventajas. Consulta la siguiente información para compararlas:

SGD

Muy flexible, puede usar otras pérdidas funciones.

Se pueden paralelizar.

Más lento: no converge con tanta rapidez.

Es más difícil manejar las entradas no observadas (necesitan para usar un muestreo negativo o gravedad).

WALS

Depende solo de los cuadrados perdidos.

Se pueden paralelizar.

Convergüen más rápido que el SGD.

Es más fácil administrar las entradas no observadas.