Alai

En 2004, Microsoft Research y el equipo de búsqueda web de Microsoft iniciaron un esfuerzo conjunto para mejorar la relevancia de nuestros resultados de búsqueda web. A esto le siguió un esfuerzo sostenido que, durante los siguientes años, dio como resultado nuestro envío de tres generaciones de algoritmos de clasificación de búsqueda web, que culminaron en los conjuntos de árboles potenciados que Bing utiliza hoy en día. Al primero de estos algoritmos de clasificación lo llamamos RankNet. Recientemente, el artículo sobre RankNet, publicado en la Conferencia Internacional sobre Aprendizaje Automático (ICML) en 2005, ganó el premio «Test of Time» de la ICML, un galardón que se concede cada año a aquel artículo presentado en la conferencia diez años antes y que se considera que ha tenido el mayor impacto académico general en los años transcurridos. Es un gran honor y también una oportunidad para echar la vista atrás y evaluar nuestro progreso en la última década. En este artículo, me gustaría contar esta historia.

La búsqueda en la web funciona esencialmente tomando la consulta del usuario y evaluando la relevancia de cada documento indexado para ella. No todas las páginas web están en el índice, pero éste contiene cientos de miles de millones de documentos, almacenados en una estructura de datos especial para que la búsqueda sea rápida. Dado que los mejores resultados deben presentarse al usuario en unos pocos cientos de milisegundos, esto requiere un proceso de filtrado y clasificación extremadamente eficiente. Los clasificadores descritos aquí trabajan con un subconjunto (aún grande) de documentos, elegidos mediante este rápido proceso de filtrado inicial. Básicamente, un clasificador funciona tomando una lista de números, cada uno de los cuales mide la calidad de una determinada coincidencia entre consulta y documento de una manera concreta (por ejemplo, un número binario que representa si la consulta contiene o no una palabra en el título del documento). El clasificador convierte esa lista de números en una única medida de relevancia, que se utiliza para ordenar todos los documentos de la consulta. La lista ordenada de números que el clasificador asigna a una única puntuación se denomina vector de características.

Por lo tanto, cuando se utiliza en tiempo de ejecución, para una consulta determinada, el clasificador toma el vector de características para cada par consulta/documento y lo asigna a un número que captura la relevancia de ese documento para la consulta. RankNet es un modelo de red neuronal de alimentación. Antes de poder utilizarlo, sus parámetros deben aprenderse utilizando una gran cantidad de datos etiquetados, denominados conjunto de entrenamiento. El conjunto de entrenamiento consiste en un gran número de pares de consulta/documento, donde para cada par, un número que evalúa la calidad de la relevancia del documento para esa consulta es asignado por expertos humanos. Aunque el etiquetado de los datos es una tarea lenta y de gran intensidad humana, el entrenamiento de la red, dados los datos etiquetados, es totalmente automático y bastante rápido. El sistema utilizado por Microsoft en 2004 para entrenar el clasificador se llamaba The Flying Dutchman. Descubrimos que, mientras que The Flying Dutchman necesitó varios días y un clúster para producir un modelo entrenado, RankNet fue capaz de producir un modelo de clasificación en sólo un par de horas utilizando una sola máquina. RankNet también mejoró significativamente la relevancia respecto al clasificador utilizado anteriormente, ya que las redes neuronales pueden modelar una gama muy amplia de posibles mapeos, mientras que el sistema anterior se limitaba sólo a mapeos lineales.

Hasta aquí todo bien, pero ¿podríamos haberlo hecho mejor? La respuesta es sí, pero para ver por qué, tengo que explicar un poco cómo se entrena RankNet. Para cada consulta del conjunto de entrenamiento, para cada par de documentos a clasificar para esa consulta, a RankNet se le muestran los dos vectores de características y entonces ajusta un poco sus parámetros, usando un método llamado Stochastic Gradient Descent (SGD), para que las puntuaciones de salida ajustadas para las dos características se muevan en la dirección correcta – es decir, la puntuación para el documento más relevante aumenta, y la del menos, disminuye. Pero eso significa que RankNet se esforzará por elevar los documentos altamente relevantes que están muy abajo en la clasificación, y también por bajar los documentos de alta puntuación pero menos relevantes. Al gastar sus recursos de esta manera, no presta tanta atención como debería a los primeros enlaces que se muestran al usuario. De hecho, en ese momento, nuestra métrica de evaluación era una puntuación llamada NDCG, que da un único número que evalúa la calidad general de la clasificación, con un énfasis mucho mayor en los primeros resultados que se muestran al usuario. El NDCG es, por tanto, una medida más natural para la búsqueda web que el error por pares. Esto nos planteó un reto: el SGD se reduce a una búsqueda en un espacio continuo, pero el NDCG es fundamentalmente una medida discreta, en el sentido de que su valor sólo cambia cuando al menos dos documentos cambian de posición en la lista clasificada. Los cambios suficientemente pequeños en las puntuaciones del modelo no producen ningún cambio en el NDCG, y dado que SGD funciona explorando pequeños cambios en las puntuaciones, es difícil ver cómo optimizar el NDCG utilizando SGD.

Encontramos una respuesta a este rompecabezas, que llamamos LambdaRank. El truco fue notar que todo el procedimiento de entrenamiento de una red neuronal sólo necesita los gradientes de la función de coste, no la función de coste en sí. Se puede pensar en estos gradientes como pequeñas flechas unidas a cada documento de la lista clasificada, que indican en qué dirección queremos que se muevan esos documentos. LambdaRank simplemente tomó los gradientes de RankNet, que sabíamos que funcionaban bien, y los escaló por el cambio en NDCG encontrado al intercambiar cada par de documentos. Descubrimos que este entrenamiento generaba modelos con una relevancia significativamente mejorada (medida por el NDCG) y tenía la ventaja añadida de descubrir otro truco que mejoraba la velocidad general del entrenamiento (tanto para RankNet como para LambdaRank). Además, sorprendentemente, encontramos pruebas empíricas (véase también este artículo) de que el procedimiento de entrenamiento realmente optimiza el NDCG, aunque el método, aunque intuitivo y sensato, no tiene esa garantía.

Hasta aquí todo bien, pero de nuevo, ¿podríamos haberlo hecho mejor? La respuesta fue, de nuevo, que sí. Conocíamos una clase de modelos llamados conjuntos de árboles potenciados que se sabía que hacían clasificadores multiclase muy fuertes. ¿Qué ocurre si tratamos el problema de la clasificación como un problema de clasificación multiclase, con una clase para cada uno de los cinco niveles de relevancia identificados en el conjunto de entrenamiento? Descubrimos que esto ofrecía mejores resultados que LambdaRank (especialmente una variante llamada clasificación multiclase ordinal). Los árboles potenciados tienen la ventaja adicional de que pueden manejar fácilmente características categóricas y otros tipos de características discretas, que son menos adecuadas para las redes neuronales. Creemos que estos resultados se deben a la mejor adecuación de esta clase de modelos a nuestros datos, por lo que la pregunta natural fue: ¿podemos combinar los modelos de árboles potenciados con la idea de LambdaRank para obtener lo mejor de ambos mundos? El entrenamiento de un modelo de árbol reforzado también puede considerarse una forma de SGD, por lo que la respuesta fue afirmativa, en forma de un modelo que denominamos LambdaMART. LambdaMART tenía una ventaja añadida: el entrenamiento de los modelos de conjuntos de árboles puede acelerarse de forma muy significativa con respecto al equivalente de redes neuronales (este trabajo, dirigido por O. Dekel, aún no se ha publicado). Esto nos permite entrenar con conjuntos de datos mucho más grandes, lo que de nuevo proporciona una mayor precisión en la clasificación.

¿Cómo se comparan nuestros clasificadores con otros del sector? En 2010, Yahoo! organizó un desafío de aprendizaje para clasificar, una de cuyas pistas estaba diseñada para ver quién tenía el mejor algoritmo de clasificación de búsqueda web. 1.055 equipos se inscribieron en el desafío. Nuestro equipo ganó el desafío, utilizando un conjunto de modelos LambdaMART.

Al mirar hacia atrás en la última década, quizás la lección técnica más destacada es la importancia de la velocidad de entrenamiento. Un entrenamiento más rápido permite tanto una mayor experimentación como el uso de conjuntos de datos más grandes. Creo que estos dos factores son, al final, más importantes que los algoritmos subyacentes utilizados, siempre y cuando estos últimos sean modelos suficientemente expresivos para la tarea en cuestión. La otra «lección de vida» que extraigo de esta experiencia es la importancia de ser persistente, pero sobre todo, de la importancia del don de poder trabajar con compañeros maravillosos, en los grupos de productos, en Microsoft Research y en el mundo académico.

Chris Burges es investigador principal y director de investigación en Microsoft Research, donde lleva desde el año 2000. Anteriormente trabajó en AT&T Bell Labs, donde se incorporó en 1986. Antes fue becario postdoctoral en el Departamento de Física Teórica del MIT, al que se incorporó tras obtener su doctorado en Física por Brandeis, tras licenciarse con matrícula de honor en Física y Matemáticas por Oxford. Sus intereses han abarcado la ingeniería de sistemas de las grandes redes de comunicaciones (AT&T sigue utilizando sus algoritmos para enrutar varias redes clave), las redes neuronales para el reconocimiento de la escritura a mano y de la impresión a máquina (trabajó en un sistema que ahora se utiliza para leer millones de cheques a diario y, de hecho, su largo descenso en el aprendizaje de las máquinas fue desencadenado por una demostración especialmente interesante de una red neuronal que reconocía los dígitos escritos a mano a principios de los 90), las máquinas de vectores de apoyo (tuvo la suerte de trabajar con Vladimir Vapnik, cocreador de las SVM, en sus inicios, y escribió un tutorial que gustó a algunas personas), la huella digital de audio (su trabajo se utiliza actualmente en Xbox y Windows Media Player para identificar la música), la verificación de hablantes, la recuperación de información y la clasificación (su algoritmo de clasificación es utilizado actualmente por Bing para la búsqueda en la web). La pasión actual de Chris es el desarrollo de nuevos enfoques para la comprensión automática del texto, que aunque es muy ambiciosa, puede enseñarnos algo, a menos que dejemos de intentarlo. Chris fue copresidente del programa de Sistemas de Procesamiento de Información Neuronal 2012 y copresidente general de NIPS 2013.

Para más noticias sobre investigación en ciencias de la computación, visite ResearchNews.com.