Trataré de describir algunas de las ideas aquí. Las técnicas de factorización matricial y los métodos de conjunto son quizás los algoritmos más discutidos en relación con el Premio Netflix, pero también se usaron muchas otras ideas.
(Nota: me estoy saltando muchas cosas y los modelos reales a menudo son mucho más complicados, así que no tome esto como un resumen definitivo).
Normalización de efectos globales
- ¿Son los modelos de aprendizaje profundo / redes neuronales siempre superiores en las tareas de PNL?
- ¿Qué tipo de matemática se usa en el aprendizaje automático? ¿Puedo aprender ML sin él?
- ¿Pueden los algoritmos de aprendizaje profundo predecir los resultados de los partidos deportivos?
- ¿Qué es el aprendizaje no supervisado?
- ¿Cuál es el beneficio de usar la función softmax en la última capa de DNN? ¿Cuál es la relación entre la entropía cruzada y las funciones de pérdida?
Supongamos que Alice clasifica Inception 4 estrellas. Podemos considerar esta calificación como compuesta de varias partes:
- Una calificación de referencia (por ejemplo, quizás la media sobre todas las calificaciones de películas de usuario es de 3.1 estrellas).
- Un efecto específico de Alice (por ejemplo, tal vez Alice tiende a calificar las películas por debajo del usuario promedio, por lo que sus calificaciones son -0.5 estrellas más bajas de lo que normalmente esperamos).
- Un efecto específico de Inception (por ejemplo, Inception es una película bastante impresionante, por lo que sus calificaciones son 0.7 estrellas más altas de lo que normalmente esperamos).
- Un efecto menos predecible basado en la interacción específica entre Alice e Inception que explica el resto de las estrellas (por ejemplo, a Alice realmente le gustó Inception debido a su combinación particular de Leonardo DiCaprio y neurociencia, por lo que esta calificación obtiene 0,7 estrellas adicionales).
En otras palabras, hemos descompuesto la calificación de 4 estrellas en
4 = [3.1 (la calificación de referencia) – 0.5 (el efecto Alicia) + 0.7 (el efecto de inicio)] + 0.7 (la interacción específica)
Entonces, en lugar de que nuestros modelos predigan la calificación de 4 estrellas en sí, primero podríamos tratar de eliminar el efecto de los predictores de referencia (los primeros tres componentes) y hacer que predigan las estrellas específicas de 0.7. (Supongo que también puedes pensar en esto como un simple tipo de impulso).
De manera más general, otros ejemplos de predictores de referencia incluyen:
- Un factor que permite que la calificación de Alice (linealmente) dependa de la (raíz cuadrada del) número de días desde su primera calificación . (Por ejemplo, ¿alguna vez has notado que te conviertes en un crítico más duro con el tiempo?)
- Un factor que permite que la calificación de Alice dependa de la cantidad de días desde la primera calificación de la película por parte de cualquier persona . (Si eres una de las primeras personas en verlo, tal vez sea porque eres un gran fanático y realmente emocionado de verlo en DVD, por lo que tenderás a calificarlo más).
- Un factor que permite que la calificación de Alice dependa de la cantidad de personas que han calificado Inception. (Quizás Alice es una hipster que odia ser parte de la multitud).
- Un factor que permite que la calificación de Alice dependa de la calificación general de la película .
- (Además de un montón de otros.)
De hecho, modelar estos sesgos resultó ser bastante importante: en su artículo que describe su solución final para el Premio Netflix, Bell y Koren escriben que
De las numerosas contribuciones algorítmicas nuevas, me gustaría destacar una: esos humildes predictores (o sesgos) de referencia, que capturan los principales efectos en los datos. Si bien la literatura se concentra principalmente en los aspectos algorítmicos más sofisticados, hemos aprendido que un tratamiento preciso de los efectos principales es probablemente al menos tan significativo como llegar a avances en el modelado.
(Para un ejemplo quizás más concreto de por qué es útil eliminar estos sesgos, suponga que sabe que a Bob le gustan los mismos tipos de películas que a Alice. Para predecir la calificación de Inception de Bob, en lugar de simplemente predecir las mismas 4 estrellas que Alice calificó, si sabemos que Bob tiende a calificar las películas 0.3 estrellas más que el promedio, luego podríamos eliminar el sesgo de Alice y luego agregar las de Bob: 4 + 0.5 + 0.3 = 4.8.)
Modelos de barrio
Veamos ahora algunos modelos un poco más sofisticados. Como se mencionó en la sección anterior, uno de los enfoques estándar para el filtrado colaborativo es usar modelos de vecindario.
Brevemente, un modelo de vecindario funciona de la siguiente manera. Para predecir la calificación de Titanic por parte de Alice, podría hacer dos cosas:
- Enfoque elemento-elemento : encuentre un conjunto de elementos similares a Titanic que Alice también haya calificado, y tome la media (ponderada) de las calificaciones de Alice en ellos.
- Enfoque de usuario a usuario : encuentre un conjunto de usuarios similares a Alice que calificaron Titanic, y nuevamente tome la media de sus calificaciones de Titanic.
(Consulte también mi respuesta a ¿Cómo funciona el motor de recomendación de filtrado colaborativo de Amazon? ¿Cuánto aumento de ventas se atribuye al motor de recomendación de Amazon?)
Las preguntas principales, entonces, son (sigamos el enfoque ítem-ítem por simplicidad):
- ¿Cómo encontramos el conjunto de artículos similares?
- ¿Cómo ponderamos estos elementos cuando tomamos su media?
El enfoque estándar es tomar alguna métrica de similitud (p. Ej., Correlación o un índice Jaccard) para definir similitudes entre pares de películas, tomar las K películas más similares bajo esta métrica (donde K tal vez se elija mediante validación cruzada) y luego usar la misma métrica de similitud al calcular la media ponderada.
Esto tiene un par de problemas:
- Los vecinos no son independientes , por lo que se utiliza una métrica de similitud estándar para definir una información de sobrecuentos medios ponderados. Por ejemplo, suponga que le pregunta a cinco amigos dónde debería comer esta noche. Tres de ellos fueron a México la semana pasada y están enfermos de burritos, por lo que recomiendan encarecidamente contra una taquería. Por lo tanto, las recomendaciones de tus amigos tienen un sesgo más fuerte de lo que obtendrías si le preguntaras a cinco amigos que no se conocían en absoluto. (Compare con la situación en la que las tres películas de El señor de los anillos son vecinas de Harry Potter).
- Las diferentes películas tal vez deberían estar usando diferentes números de vecinos . Algunas películas pueden predecirse bien solo por un vecino (por ejemplo, Harry Potter 2 podría predecirse bien solo por Harry Potter 1), algunas películas pueden requerir más y algunas películas pueden no tener buenos vecinos, por lo que debe ignorar los algoritmos de su vecindario completamente y deje que sus otros modelos de calificaciones se mantengan solos.
Entonces, otro enfoque es el siguiente:
- Todavía puede usar una métrica de similitud como correlación o similitud de coseno para elegir el conjunto de elementos similares.
- Pero en lugar de utilizar la métrica de similitud para definir los pesos de interpolación en los cálculos medios, esencialmente realiza una regresión lineal (escasa) para encontrar los pesos que minimizan el error al cuadrado entre la calificación de un elemento y una combinación lineal de las calificaciones de sus vecinos.
(También es útil un enfoque usuario-usuario un poco más complicado similar a este modelo de vecindario ítem-ítem).
Datos implícitos
Además del enfoque de vecindario, también podemos permitir que los datos implícitos influyan en nuestras predicciones . El mero hecho de que un usuario calificara muchas películas de ciencia ficción pero no westerns, sugiere que al usuario le gusta más la ciencia ficción que los vaqueros. Entonces, utilizando un marco similar al del modelo de clasificación de vecindarios, podemos aprender para Inception un conjunto de pesos de compensación asociados a sus vecinos de películas.
Siempre que deseamos predecir cómo Bob califica a Inception, observamos si Bob calificó a cada uno de los vecinos de Inception. Si lo hizo, agregamos el desplazamiento correspondiente; si no, entonces no agregamos nada (y, por lo tanto, la calificación de Bob está penalizada implícitamente).
Factorización matricial
Complementando el enfoque de vecindad para el filtrado colaborativo es el enfoque de factorización matricial. Mientras que el enfoque de vecindario adopta un enfoque muy local para las calificaciones (si te gustó Harry Potter 1, ¡entonces te gustará Harry Potter 2!), El enfoque de factorización tiene una visión más global (sabemos que te gustan las películas de fantasía y que Harry Potter tiene un fuerte elemento de fantasía, por lo que creemos que le gustará Harry Potter) que descompone a los usuarios y las películas como un conjunto de factores latentes (que podemos considerar categorías como “fantasía” o “violencia”).
De hecho, los métodos de factorización matricial fueron probablemente la clase más importante de técnicas para ganar el Premio Netflix. En su artículo del Premio Progreso 2008, Bell y Koren escriben
Parece que los modelos basados en la factorización matricial se consideraron más precisos (y por lo tanto populares), como lo demuestran las publicaciones y debates recientes en el foro del Premio Netflix. Definitivamente estamos de acuerdo con eso, y nos gustaría agregar que esos modelos de factorización matricial también ofrecen la flexibilidad importante necesaria para modelar efectos temporales y la vista binaria. No obstante, se espera que los modelos de vecindario, que han dominado la mayor parte de la literatura de filtrado colaborativo, sigan siendo populares debido a sus características prácticas: sean capaces de manejar nuevos usuarios / calificaciones sin volver a capacitar y ofrecer explicaciones directas a las recomendaciones.
La forma típica de encontrar estas factorizaciones es realizar una descomposición de valores singulares en la matriz de calificaciones (escasa) (usando el descenso de gradiente estocástico y regularizando los pesos de los factores, posiblemente limitando los pesos para que sean positivos para obtener un tipo de matriz no negativa factorización). (Tenga en cuenta que este “SVD” es un poco diferente del SVD estándar aprendido en álgebra lineal, ya que no todos los usuarios han calificado cada película y, por lo tanto, la matriz de calificaciones contiene muchos elementos faltantes que no queremos tratar simplemente como 0.)
Algunos métodos inspirados en SVD utilizados en el Premio Netflix incluyen:
- SVD estándar : una vez que haya representado a los usuarios y las películas como vectores de factores, puede puntear el vector de Alice con el vector de Inception para obtener la calificación predicha de Alice de Inception.
- Modelo SVD asimétrico : en lugar de que los usuarios tengan su propia noción de vectores de factores, podemos representar a los usuarios como una bolsa de elementos que han calificado (o proporcionado retroalimentación implícita). Por lo tanto, Alice ahora se representa como una suma (posiblemente ponderada) de los vectores de factores de los elementos que ha calificado, y para obtener su calificación prevista de Titanic, podemos puntear esta representación del producto con el vector de factores de Titanic. Desde una perspectiva práctica, este modelo tiene el beneficio adicional de que no se necesitan parametrizaciones del usuario, por lo que podemos usar este enfoque para generar recomendaciones tan pronto como un usuario proporcione algunos comentarios (que podrían ser solo vistas de un elemento y no necesariamente calificaciones ), sin necesidad de volver a entrenar el modelo para factorizar al usuario.
- Modelo SVD ++ : incorpore tanto el SVD estándar como el modelo SVD asimétrico representando a los usuarios con su propia representación de factores y como una bolsa de vectores de elementos.
Regresión
Algunos modelos de regresión también se utilizaron en las predicciones. Los modelos son bastante estándar, creo, así que no pasaré mucho tiempo aquí. Básicamente, al igual que con los modelos de vecindario, podemos adoptar un enfoque centrado en el usuario y un enfoque centrado en la película para la regresión:
- Enfoque centrado en el usuario : aprendemos un modelo de regresión para cada usuario, utilizando todas las películas que el usuario calificó como el conjunto de datos. La respuesta es la calificación de la película, y las variables predictoras son atributos asociados a esa película (que pueden derivarse, por ejemplo, de PCA, MDS o una SVD).
- Enfoque centrado en la película : de manera similar, podemos aprender un modelo de regresión para cada película, utilizando todos los usuarios que calificaron la película como el conjunto de datos.
Máquinas de Boltzmann restringidas
Las máquinas de Boltzmann restringidas proporcionan otro tipo de enfoque de factor latente que se puede utilizar. Consulte este documento (http://www.machinelearning.org/p…) para obtener una descripción de cómo aplicarlos al Premio Netflix. (En caso de que el documento sea un poco difícil de leer, escribí una introducción a los RBM aquí: http://blog.echen.me/2011/07/18/…)
Efectos temporales
Muchos de los modelos incorporan efectos temporales. Por ejemplo, al describir los predictores de línea de base anteriores, utilizamos algunos predictores temporales que permitieron que la calificación de un usuario dependiera (linealmente) del tiempo transcurrido desde la primera calificación que realizó y del tiempo transcurrido desde la primera calificación de una película. También podemos obtener efectos temporales más detallados al, por ejemplo, agrupar elementos en un par de meses de calificaciones a la vez, y permitir que los sesgos de las películas cambien dentro de cada contenedor. (Por ejemplo, tal vez en mayo de 2006, la revista Time nominó a Titanic como la mejor película jamás realizada, lo que causó un aumento repentino en las calificaciones brillantes en ese momento).
En el enfoque de factorización matricial, también se permitió que los factores del usuario dependieran del tiempo. También podemos dar más peso a las acciones recientes de los usuarios.
Regularización
La regularización también se aplicó en casi todos los modelos aprendidos, para evitar el sobreajuste en el conjunto de datos. La regresión de crestas se utilizó mucho en los modelos de factorización para penalizar grandes pesos, y la regresión de lazo (aunque menos efectiva) también fue útil. También se estimaron muchos otros parámetros (p. Ej., Los predictores de referencia, los pesos de similitud y los pesos de interpolación en los modelos de vecindario) utilizando técnicas de contracción bastante estándar.
Métodos de conjunto
Finalmente, hablemos sobre cómo se combinaron todos estos algoritmos diferentes para proporcionar una calificación única que explotara las fortalezas de cada modelo . (Tenga en cuenta que, como se mencionó anteriormente, muchos de estos modelos no fueron entrenados en los datos de calificaciones sin procesar directamente, sino más bien en los residuos de otros modelos).
En el documento que detalla su solución final, los ganadores describen el uso de árboles de decisión impulsados por gradiente para combinar más de 500 modelos ; Las soluciones anteriores utilizaron en cambio una regresión lineal para combinar los predictores.
Brevemente, los árboles de decisión impulsados por gradiente funcionan ajustando secuencialmente una serie de árboles de decisión a los datos; a cada árbol se le pide que prediga el error cometido por los árboles anteriores, y a menudo se le capacita en versiones ligeramente perturbadas de los datos. (Para una descripción más larga de una técnica similar, vea ¿Cómo funcionan los bosques aleatorios en términos simples? Estoy específicamente interesado en cómo los RFs resuelven los problemas de regresión).
Dado que los GBDT tienen la capacidad incorporada de aplicar diferentes métodos a diferentes segmentos de datos, podemos agregar algunos predictores que ayudan a los árboles a hacer agrupaciones útiles:
- Número de películas que calificó cada usuario
- Número de usuarios que calificaron cada película
- Vectores de factores de usuarios y películas
- Unidades ocultas de una máquina de Boltzmann restringida
(Por ejemplo, una cosa que encontraron Bell y Koren al usar un método de conjunto anterior fue que los RBM son más útiles cuando la película o el usuario tienen un bajo número de calificaciones, y que los métodos de factorización matricial son más útiles cuando la película o el usuario tienen un alto número de calificaciones)
Aquí hay un gráfico del efecto del tamaño del conjunto desde el principio de la competencia (en 2007), y la opinión de los autores:
Sin embargo, nos gustaría enfatizar que no es necesario tener una cantidad tan grande de modelos para hacerlo bien. La siguiente gráfica muestra RMSE en función del número de métodos utilizados. Uno puede lograr nuestro puntaje ganador (RMSE = 0.8712) con menos de 50 métodos, usar los 3 mejores métodos puede generar RMSE <0.8800, lo que se ubicaría en el top 10. Incluso el simple uso de nuestro mejor método nos coloca en la clasificación con un RMSE de 0.8890. La lección aquí es que tener muchos modelos es útil para los resultados incrementales necesarios para ganar competencias, pero prácticamente, se pueden construir sistemas excelentes con solo unos pocos modelos bien seleccionados.
Finalmente, ha pasado un tiempo desde que revisé todos los documentos del Premio Netflix, y mi memoria y notas son un poco incompletas, por lo que las correcciones y sugerencias son muy bienvenidas.
