Recommender Systems: Matrix Factorization and Factor Analysis

Como relato en mi post anterior, el filtrado colaboratiovo de contenidos esta basado en los estrategias principales:

  1. Content filtering: crea perfiles para cada usuario e item para caracterizar su naturaleza. Luego, los perfiles permiten asociar usuarios con items que encajen con sus perfiles. La gran complejidad es que requieren recolectar información externa, que puede no ser fácil de recolectar o simplemente no estar disponible.
  2. Collaborative filtering: analiza relaciones entre los usuarios y las interdependencias entre los items para identificar nuevas relaciones (usuario,item). Su principal atractivo es que puede abordar aspectos de datos que a menudo son elusivos y difíciles de capturar utilizando filtrado de contenido. Generalmente es más preciso que content filtering, adolece de cold start (arranque lento), debido a su incapacidad para abordar los nuevos productos y usuarios del sistema. En este aspecto, el filtrado de contenido es superior.

Aún así, el desarrollo en el area del filtrado colaborativo ha traído sus frutos, principalmente impulsado por la industria de consumo audiovisual, que se vio en la necesidad de enfrentar el problema de que aplicar un filtrado de contenidos era imposible [2]. En esta línea, dos áreas han sido las más fructíferas:

Análisis de vecindarios: se centra en computar las relaciones entre usuarios (user based filtering) o entre items (item based filtering). En mi post anterior describo los algoritmos desarrollados en esta área, la siguiente imagen es muy ilustrativa del razonamiento detrás.

  • Modelos de factores latentes: trata de explicar las clasificaciones al caracterizar ítems y usuarios en “f” factores inferidos de los patrones de rating. La siguiente figura resume muy eficazmente el concepto detrás de este modelo.
Fuente: https://www.slideshare.net/jtneill/exploratory-factor-analysis

Métodos de factorización Matricial

Basicamente, los datos de entrada son representados en una matriz donde una dimensión representa a los usuarios y los otra dimensión representa los itemes de interés, con esto caracterizan items y usuarios en vectores o factores inferidos de patrones de rating de items, donde una alta correspondencia entre item e usuario conlleva a una recomendación.

Una de sus fortalezas reside en que permite incorporar información adicional, lo cual es muy útil cuando no hay información explícita disponible. Estos pueden inferir las preferencias del usuario utilizando información implícita. Lo bueno, es que utilizar información implícita generalmente conlleva a una matriz muy poblada, por el contrario de utilizar información explicita que generalmente está caracterizada por una matriz dispersa (cada usario prevee información para un porción muy pequeña de los itemes).

En estos modelos, usuarios e items son mapeados en un espacio de dimension “f” generado por los factores latentes y sus interacciones son modeladas como productos internos en ese espacio. Para comprender bien esta noción, es importante tener en mente que el concepto de “producto interno” nos otorga la “proyección” de un vector sobre otro. La siguiente figura ilustra este concepto.

Fuente: https://www.youtube.com/watch?v=Y72JGMxedms

Lo importante aquí es notar que el producto interno entre dos vectores será menor en la medida que se encuentren cercanos y mayor el caso contrario, por lo tanto, una forma inteligente de capturar la interacción entre el usuario “u” y el item “i”, es con la siguiente expresión:

que refleja el interés general de usuario en las características del item.

Este modelo esta íntimamente relacionado con la técnica de “Singular Value Decomposition” (SVD), pero SVD no está definido para problemas en los que el conocimiento de la matriz incompleto. Por lo que no nos sirve para trabajar con información explícita, pero sí con información implícita. Con esto, para aprender los vectores que factorizan (p y q), es necesario minimizar la suma regularizada de errores en el set de ratings conocidos:

Donde el parametro λ refleja el grado de regularización para que el modelo no haga overfitting sobre los datos de training, usualmente es determinado vía cross-validation y inherentemente es dependiente de los datos. Hay dos formas de enfrentar el problema de minimización anterior:

  • Stochastic Gradient Descent (SGD): recorre todos los ratings en el training set y para cada caso, el sistema predice el rating y calcula el error de predicción dado, luego modifica los parámetros en una proporción γ en dirección opuesta al gradiente (recordemos que es un problema de minimización), es decir:
Error de predicción de rating para usuario u con item i.
Corrección en dirección de menor crecimiento.
  • Alternating Least Squares (ALS): aunque SGD es mas fácil y rápido, ALS es mejor cuando tratamos con un sistema que se alimenta con información implícita, ya que como el set de training no es disperso, no es práctico iterar sobre todos casos en él (como lo haría SGD). ALS opera fijando alternadamente las variables, primero fija p y recalcula q resolviendo un problema de mínimos cuadrados, y viceversa, hasta converger.

Sesgos

Una gran parte de la variación en los ratings es debido a efectos asociados con usuarios o con los items, comúnmente denominados como biases, independientes de las interacciones. Con esto, el utilizar directamente el producto interno entre p y q puede no ser suficiente para modelar la relación. En su lugar, podemos identificar la porción que puede ser explicada por los biases de los individuos e usuarios analizando solo los datos de la interacción real a través de sus factores.

Aproximación de primer orden del sesgo incorporado en ek rating del usuario u con el item i, donde μ representa el rating promedio y el resto las desviaciones del item y del usuario respectivamente.

Dado que estos sesgos nos capturan en gran medida los datos observados, modelarlos es crucial. La descomposición anterior nos permite estimar ratings a través de la siguiente relación con su problema de minimización respectivo:

Datos Implícitos

Como mencioné anteriormente, incorporar datos implícitos es vital para poder enfrentar el famoso inconveniente del Cold Start. Para modelar esto, de manera simple, consideremos incorporar al modelo feedback implícito a través de variables booleanas.

Denotando por N(u) el set de items con información implícita del usuario u y al set de factores para los items, donde el item i esta asociado con x_i (de f dimensiones). Y, análogamente, como A(u) al set de atributos del usuario u (sexo, edad, etc.) y al vector de factores y_a (de f dimensiones) que describe al usuario a través sus componentes asociadas. Así obtenemos la siguiente relación:

Este modelo puede ser extendido de la misma forma para mejorar la información disponible para los items

Temporalidad

Las técnicas de factorización matricial también permiten modelar la situación cuando hay iterdependencia y evolución de los datos en el tiempo (por ejemplo cambios en los gustos de los usuarios). Es decir podemos modelar los biases de los itemes i, usuarios u y preferencias p como funciones en el tiempo b_i(t), b_u(t) y p_u(t), por el contrario, como los itemes son de naturaleza estática (no varían sus características a lo largo del tiempo), no son modelados en función del tiempo. Con todo esto, podemos actualizar el modelo construido con la reglas de predicción dinámica para un rating en el tiempo t:

Confianza de los datos

Como comentaba en mi post anterior, en ocasiones el sistema puede ser víctima de datos artificiales que terminan dominando las predicciones, producto por ejemplo de campañas de marketing o de inferencias erróneas respecto de datos implícitos. En estos casos, es valioso incorporar métricas de confianza a las estimaciones, que puede surgir de los valores numéricos de las frecuencias o naturaleza de las interacciones. El modelo de factorización matricial puede incorporar fácilmente distintos niveles de confianza asignando menos peso a las observaciones menos significativas (menos frecuentes por ejemplo). Esto se logra simplemente actualizando la función de costo de la siguiente manera:

En el que c_ui, nuestro nivel de confianza, penaliza o premia la estimación.

Hu, koren y Volinski [2] proponen tratar los datos como ratings de preferencia positiva o negativa asociada con niveles de confianza que pueden tener alta variación. Esto conduce a un modelo de factores diseñado especialmente para recomendadores de comentarios implícitos. cuya optimización escala linealmente con el tamaño de los datos… maravilloso!!!

en este sentido destacan que es crucial identificar ciertas características únicas de los datos implícitos que no nos permiten utilizar directamente algoritmos que fueron pensados para el feedback explícito. Es decir:

  1. Ausencia de Feedback negativo. No es posible inferir itemes que al usuario no le gustan, los datos recolectados solo nos permiten inferir feedback positivo, lo cual no es representativo del perfil completo del usuario.
  2. Alta incertidumbre de los datos. No podemos confiar en que la interacción representa ciertamente preferencia ya que puede estar motivada por otros factores.
  3. Su valor numérico indica confianza. Al contrario del feedback explícito que representa preferencia, lo único que podemos inferir del feedback implícito es la confianza en la observación, en el sentido que un evento esporádico puede ser causado por múltiples razones no relacionadas con la preferencia del usuario, mientras que un evento recurrente es mas probable que refleje la opinión del usuario.
  4. Evaluarlo requiere métricas adecuadas. Esto debido a que lo observado simplemente refleja interacción y no la medida específica de preferencia del usuario.

Proponen la siguiente forma de medir la confianza es:

α representa el ratio de crecimiento de la confianza, el cual pondera nuesta observación implícita y otorga un nivel mínimo de confianza.

Y el modelo anterior puede ser reescrito de la siguiente forma:

Un aporte significativo de los autores [2] es que, luego de hacer un algebra matricial un poco extensa, podemos derivar este modelo a uno que permite separar la contribución de cada acción individual en dos fuentes: la importancia de la relación con el usuario u — c_uj, y la similitud con el ítem objetivo i — s_ij. Donde:

Similitud ponderada entre los elementos i y j desde el punto de vista de u
Estimador de preferencia de u para el ítem i