Aprendizaje de clasificación

Aprendizaje de clasificación^[1]​ o aprendizaje automático de clasificación (MLR, por sus siglas en inglés) es la aplicación de aprendizaje automático, típicamente supervisado, semisupervisado o aprendizaje reforzado en la construcción de modelos de clasificación para sistemas de recuperación de información.^[2]​ Los datos de entrenamiento consisten en listas de elementos con algún orden parcial especificado entre elementos en cada lista. Este orden es típicamente inducido por dar una puntuación numérica u ordinal o un juicio binario (p. ej., «relevante» o «no relevante») para cada elemento. El propósito del modelo de clasificación es producir una permutación de elementos en nuevas listas, que no se ven de una manera que sea «similar» a clasificaciones en los datos de entrenamiento en algún sentido.

El aprendizaje de clasificación es relativamente una nueva área de investigación que ha surgido en la última década.

Aplicaciones

En la recuperación de información

Clasificar es una parte central de muchos problemas de recuperación de información, como recuperación de documento, filtrado colaborativo, análisis de los sentimientos, y la publicidad en línea.

Una arquitectura posible de un motor de búsqueda del aprendizaje de máquina se muestra en la figura a la derecha.

El entrenamiento de datos consiste en emparejar consultas y documentos, junto con grado de relevancia de cada emparejamiento. Puede ser preparado manualmente por asesores humanos (o raters, como Google les llama), quiénes comprueban resultados para algunas consultas y determinan la relevancia de cada resultado. No es factible de comprobar la relevancia de todos los documentos, y tan típicamente una técnica llamada pooling es utilizada — solo los primeros pocos documentos, recuperados por algunos modelos de clasificación existentes se comprueban. Por otra parte, los datos de entrenamiento se pueden derivar de forma automática mediante el análisis de los registros de clics (es decir, los resultados de búsqueda que recibieron los clics de los usuarios), cadenas de consulta o características motores de búsqueda tales como SearchWiki de Google.

El entrenamiento de datos es utilizado por un algoritmo de aprendizaje para producir un modelo de clasificación que calcula la relevancia de los documentos para consultas reales.

Por lo general, los usuarios esperan completar una consulta de búsqueda en un corto período de tiempo (por ejemplo, unos pocos cientos de milisegundos para la búsqueda web), lo que hace imposible evaluar un modelo de clasificación complejo en cada documento en el corpus, y por eso se utiliza un esquema de dos fases. En primer lugar, un pequeño número de documentos potencialmente relevantes se identifican utilizando modelos de recuperación más simples que permiten la evaluación de consulta rápida, como el modelo de espacio vectorial, modelo booleano, ponderado Y, y BM25. Esta fase se llama recuperación de documentos top-k y muchas heurísticas fueron propuestas en la literatura para acelerarlo, como el uso de la puntuación de calidad estática del documento y en los índices de niveles. En la segunda fase, un modelo de aprendizaje automático más preciso pero costoso computacionalmente se utiliza para volver a clasificar estos documentos.

En otras áreas

Algoritmos de aprendizaje de clasificación han sido aplicados en distintas áreas de la recuperación de información:

• En traducción automática, para clasificar un conjunto de traducciones hipotéticas;^[3]​
• En biología computacional, para la clasificación de estructuras candidatos 3-D en el problema de predicción de estructura de proteína.^[3]​
• En proteómica, para la identificación de péptidos frecuentes de puntuación superior.^[4]​
• En Sistemas de Recomendación, para identificar una lista de clasificación de artículos noticiosos relacionados para recomendar a un usuario después de que este haya leído un artículo de actualidad.^[5]​

Vectores de característica

Para comodidad de los algoritmos MLR, pares de consulta-documento son normalmente representados por vectores numéricos, los cuales se apellidan vectores de característica. Este enfoque se denomina a veces bolsa de características y es análoga a la bolsa de palabras de modelo y de espacio vectorial modelo utilizado en la recuperación de información para la representación de documentos.

Los componentes de tales vectores se apellidan características, factores o señales de clasificación. Se pueden dividir en tres grupos (características de recuperación de documentos se muestran como ejemplos):

• Consulta-independiente o características estáticas — aquellas características, que dependen sólo en el documento, pero no en la consulta. Por ejemplo, el PageRank o la longitud del documento. Tales características pueden ser precalculados en el modo fuera de línea durante la indexación. Pueden ser utilizados para calcular la puntuación del documento estático de calidad (o rango estático), que a menudo se utiliza para acelerar la evaluación consulta de búsqueda.^[6]​^[7]​
• Características de consultas dependientes o dinámicas — esas características, que dependen tanto del contenido del documento y la consulta, como la puntuación de TF-IDF u otras funciones de clasificación no-machine-learned.
• Características de nivel de la consulta o características de consulta, los cuales dependen sólo en la consulta. Por ejemplo, el número de palabras en una consulta. Información más lejana: característica de nivel de la consulta

Algunos ejemplos de características, que fueron utilizados en el conjunto de datos conocido LETOR:^[8]​

• TF, TF-IDF, BM25 y Lenguaje de Modelado decenas de zonas del documento (título, cuerpo, ancla de texto, URL) para una consulta determinada;
• Longitudes y sumas de las IDF de zonas del documento;
• PageRank de Documento, HITS filas y sus variantes.

Seleccionar y diseñar las características buenas es un área importante en aprendizaje de máquina, el cual se apellida ingeniería de característica.

Medidas de evaluación

Hay varias medidas (métricas) que se utilizan comúnmente para juzgar qué tan bien un algoritmo está haciendo en los datos de entrenamiento y para comparar el rendimiento de diferentes algoritmos de MLR. A menudo, un problema de aprendizaje de clasificación se reformula como un problema de optimización con respecto a una de estas métricas.

Ejemplos de medidas de clasificación de calidad:

• Significado de la precisión media (MAP por sus siglas en inglés);
• DCG y NDCG;
• Precision@n, NDCG@n, donde "@n" denota que las métricas son evaluadas solamente en los primeros n documentos;
• Significado de rango recíproco;
• Tau de Kendall
• Rho de Spearman

DCG y su variante normalizada NDCG es normalmente preferido en búsqueda académica cuando los niveles múltiples de pertinencia son utilizados.^[9]​ Otros indicadores, como MAP, MRR y precisión, se definen sólo para juicios binarios.

Recientemente, se han propuesto varias métricas de evaluación nuevas que pretenden modelar la satisfacción del usuario con resultados de búsqueda mejor que la métrica DCG:

• Clasificación recíproca esperada (ERR por sus siglas en inglés);^[10]​
• pfound de Yandex.^[11]​

Ambos indicadores se basan en la suposición de que es más probable que dejar de mirar a los resultados de búsqueda después de examinar un documento más relevante, que después de un documento menos relevante al usuario.

Aproximaciones

Tie-Yan Liu, de Microsoft Research Asia en su ponencia "Aprendizaje de clasificación para la Recuperación de Información" y habla en varias conferencias principales ha analizado los algoritmos existentes para aprender a clasificar los problemas y los clasifican en tres grupos por su representación de entrada y función de pérdida:^[1]​

Aproximación Pointwise

En este caso está supuesto que cada par consulta- documento en el dato de formación tiene una puntuación numérica u ordinal. Entonces problema de aprendizaje-de-clasificación puede ser aproximado por un problema de regresión — dado un solo par consulta - documento, pronosticar su puntuación.

En este caso se supone que cada par consulta- documento con los datos de entrenamiento tiene una puntuación numérica u ordinal. A continuación, el problema de aprendizaje-de-clasificación puede ser aproximado por un problema de regresión - dado un solo par consulta-documento, predecir su puntuación.

Un número de algoritmos de aprendizaje automático supervisado existentes se puede utilizar fácilmente para este propósito. Algoritmos de regresión y clasificación ordinales se pueden utilizar también en el enfoque puntual cuando se utilizan para predecir la puntuación de un solo par consulta-documento, y se necesita un número pequeño, finito de valores.

Aproximación Pairwise

En este caso el problema aprendizaje-de-clasificación está aproximado por un problema de clasificación — el aprendizaje de un clasificador binario que puede decir que el documento es mejor en un par dado de documentos. El objetivo es minimizar el número medio de inversiones en clasificación.

Aproximación Listwise

Estos algoritmos tratan de optimizar directamente el valor de una de las medidas de evaluación anteriores, promediado sobre todas las consultas en los datos de entrenamiento. Esto es difícil porque la mayoría de las medidas de evaluación no son funciones continuas con respecto a la clasificación de los parámetros del modelo, y aproximaciones de manera continua o límites sobre las medidas de evaluación tienen que ser utilizados.

Lista de métodos

Debajo se muestra una lista parcial de los algoritmos publicados de aprendizaje de clasificación con los años de la primera publicación de cada método:

Año	Nombre	Tipo	Notas
1989	OPRF^[12]​	2 pointwise	Regresión polinómica (en lugar de aprendizaje automático, este trabajo se refiere al reconocimiento de patrones, pero la idea es la misma)
1992	SLR^[13]​	2 pointwise	Regresión logística por etapas
2000	Ranking SVM (RankSVM)	2 pairwise	Una exposición más reciente es en la que describe una aplicación para la clasificación utilizando registros de clics.^[14]​
2002	Pranking^[15]​	1 pointwise	Regresión ordinal.
2003	RankBoost	2 pairwise
2005	RankNet	2 pairwise
2006	IR-SVM	2 pairwise	Clasificación SVM con la normalización a nivel de consulta en la función de pérdida.
2006	LambdaRank	3 pairwise	RankNet en el que la función de pérdida pairwise se multiplica por el cambio en la métrica IR causado por un intercambio.
2007	AdaRank	3 listwise
2007	Frank	2 pairwise	Basado en RankNet, utiliza una función de pérdida diferente - la pérdida de fidelidad.
2007	GBRank	2 pairwise
2007	ListNet	3 listwise
2007	McRank	1 pointwise
2007		2 pairwise
2007	RankCosine	3 listwise
2007	RankGP^[16]​	3 listwise
2007	RankRLS	2 pairwise	Regularizados por mínimos cuadrados basado en clasificación. El trabajo se extiende a aprender a clasificar a partir de los gráficos de preferencias generales.^[17]​
2007	SVMmap[8][9]	3 listwise
2008	LambdaMART	3 pairwise	Obra ganadora en la reciente Aprendizaje de Clasificación de Yahoo utiliza un conjunto de modelos LambdaMART.^[18]​
2008	ListMLE	3 listwise	Basado en ListNet.
2008	PermuRank	3 listwise
2008	SoftRank	3 listwise
2008	Ranking Refinamiento^[19]​	2 pairwise	Un enfoque semi-supervisado para aprender a clasificar que utiliza Impulso.
2008	^[20]​	2 pairwise	Una extensión de RankBoost para aprender con datos parcialmente etiquetados (aprendizaje semi-supervisado para clasificar)
2008	SortNet el 26 de junio de 2018 en Wayback Machine.^[21]​	2 pairwise	SortNet, un algoritmo de clasificación de adaptación que ordena los objetos utilizando una red neuronal como comparador.
2009		2 pairwise	Preservación de magnitud de variante de RankBoost. La idea es que cuanto más desiguales son las etiquetas de un par de documentos, más difícil si el algoritmo trata de clasificarlos.
2009		3 listwise	A diferencia de los métodos anteriores, BoltzRank produce un modelo de clasificación que se ve durante el tiempo de consulta no sólo en un solo documento, también en pares de documentos.
2009	BayesRank	3 listwise	Un método que combina Modelo Plackett-Luce y red neuronal para minimizar el riesgo de Bayes esperado, relacionada con NDCG, desde el punto de toma de decisiones.
2010	NDCG Impulso^[22]​	3 listwise	Una aproximación de impulso para optimizar NDCG.
2010	GBlend	2 pairwise	Extiende GBRank al problema-aprendizaje de mezcla de resolver conjuntamente problemas múltiples-aprendizaje de clasificación con algunas características comunes.
2010		2 pairwise & listwise
2010	CRR	2 pointwise & pairwise	Combina Regresión y Clasificación. Uso descenso de gradiente estocástico para optimizar una combinación lineal de una pérdida cuadrática puntual y una pérdida de bisagra pairwise de clasificación SVM.

Nota: cuando la mayoría de los algoritmos de aprendizaje supervisado pueden ser aplicados a pointwise, sólo aquellos métodos que están diseñados específicamente con la clasificación en mente aparecen arriba.

Historia

Norbert Fuhr introdujo la idea general de MLR en 1992, describiendo los enfoques de aprendizaje en la recuperación de información como una generalización de la estimación de parámetros; una variante específica de este enfoque (utilizando regresión polinómica) había sido publicada por él tres años antes.^[23]​^[12]​ Bill Cooper propuso regresión logística para el mismo fin en el año 1992 y lo utilizó con su grupo de investigación de Berkeley para entrenar a una función de clasificación exitosa para TREC.^[13]​ Manning et al. sugieren que estos primeros trabajos logrado resultados limitados en el tiempo debido a los pocos datos disponibles de formación y técnicas de aprendizaje automático pobres.^[24]​

Varias conferencias, como NIPS, SIGIR y ICML tenían talleres dedicados a la solución de aprendizaje al rango desde mediados de los años 2000s (década).

Uso práctico por motores de búsqueda

Motores de búsqueda de web comerciales comenzaron a usar aprendizaje de máquina en sistemas de clasificación desde la década de los 2000s. Uno de los primeros motores de búsqueda para comenzar a utilizar era AltaVista (más tarde su tecnología fue adquirida por la insinuación, y luego Yahoo), que lanzó una función de clasificación gradient boosting-trained en abril de 2003.^[25]​^[26]​

La búsqueda de Bing se dice que es impulsado por el algoritmo RankNet, que fue inventado por Microsoft Research en 2005.^[27]​

En noviembre de 2009 un motor de búsqueda ruso Yandex anunció que había aumentado significativamente su calidad de búsqueda debido a la implementación de un nuevo algoritmo MatrixNet propietario, una variante del método de impulsar gradiente que utiliza árboles de decisión ajenos.^[28]​^[29]​ Recientemente también han patrocinado un concurso aprendizaje de clasificación de máquina "Internet Matemáticas 2009", basado en los datos de producción de su propio motor de búsqueda.^[30]​ Yahoo Ha anunciado una competición similar en 2010.^[31]​

A partir de 2008, Peter Norvig de Google negó que su motor de búsqueda se basa exclusivamente en el aprendizaje de máquina de clasificación.^[32]​ CEO de Cuil, Tom Costello, sugiere que prefieren modelos construidos a mano, ya que pueden superar a los modelos de aprendizaje de máquinas si se compara con las métricas como el porcentaje de clics o la hora en la página de aterrizaje, lo que se debe a que los modelos de aprendizaje de máquinas "aprenden lo que la gente dice que como, no lo que la gente realmente le gusta".^[33]​

Referencias

1. Tie-Yan Liu (2009), "Learning to Rank for Information Retrieval", Foundations and Trends® in Information Retrieval, Foundations and Trends in Information Retrieval 3 (3): 225–331, doi:10.1561/1500000016, ISBN 978-1-60198-244-5 .
2. Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar (2012) Foundations of Machine Learning, The MIT Press ISBN 9780262018258.
3. Kevin K. Duh (2009), Learning to Rank with Partially-Labeled Data[1] (PDF) 
4. Henneges C., Hinselmann G., Jung S., Madlung J., Schütz W., Nordheim A., Zell A. (2009), Ranking Methods for the Prediction of Frequent Top Scoring Peptides from Proteomics Data[2] (PDF) 
5. Yuanhua Lv, Taesup Moon, Pranam Kolari, Zhaohui Zheng, Xuanhui Wang, and Yi Chang, Learning to Model Relatedness for News Recommendation el 27 de agosto de 2011 en Wayback Machine.[3] el 27 de agosto de 2011 en Wayback Machine., in International Conference on World Wide Web (WWW), 2011.
6. Manning C., Raghavan P. and Schütze H. (2008), Introduction to Information Retrieval, Cambridge University Press .
7. Richardson, M.; Prakash, A.; Brill, E. (2006).
8. LETOR 3.0.
9. http://www.stanford.edu/class/cs276/handouts/lecture15-learning-ranking.ppt
10. Olivier Chapelle, Donald Metzler, Ya Zhang, Pierre Grinspan (2009), "Expected Reciprocal Rank for Graded Relevance" el 24 de febrero de 2012 en Wayback Machine. (PDF), CIKM 
11. Gulin A., Karpovich P., Raskovalov D., Segalovich I. (2009), "Yandex at ROMIP'2009: optimization of ranking algorithms by machine learning methods" (PDF), Proceedings of ROMIP'2009: 163–168  (in Russian)
12. Fuhr, Norbert (1989), "Optimum polynomial retrieval functions based on the probability ranking principle", ACM Transactions on Information Systems 7 (3): 183–204, doi:10.1145/65943.65944 
13. Cooper, William S.; Gey, Frederic C.; Dabney, Daniel P. (1992), "Probabilistic retrieval based on staged logistic regression", SIGIR '92 Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval: 198–210, doi:10.1145/133160.133199 
14. Joachims, T. (2002), "Optimizing Search Engines using Clickthrough Data" (PDF), Proceedings of the ACM Conference on Knowledge Discovery and Data Mining 
15. "Pranking".
16. "RankGP".
17. Pahikkala, Tapio; Tsivtsivadze, Evgeni, Airola, Antti, Järvinen, Jouni, Boberg, Jorma (2009), "An efficient algorithm for learning to rank from preference graphs", Machine Learning 75 (1): 129–165, doi:10.1007/s10994-008-5097-z. 
18. C. Burges. (2010).
19. Rong Jin, Hamed Valizadegan, Hang Li, Ranking Refinement and Its Application for Information Retrieval[4], in International Conference on World Wide Web (WWW), 2008.
20. Massih-Reza Amini, Vinh Truong, Cyril Goutte, A Boosting Algorithm for Learning Bipartite Ranking Functions with Partially Labeled Data el 2 de agosto de 2010 en Wayback Machine.. Archivado desde el original el 2 de agosto de 2010. Consultado el 9 de junio de 2010. , International ACM SIGIR conference, 2008.
21. Leonardo Rigutini, Tiziano Papini, Marco Maggini, Franco Scarselli, "SortNet: learning to rank by a neural-based sorting algorithm", SIGIR 2008 workshop: Learning to Rank for Information Retrieval, 2008
22. Hamed Valizadegan, Rong Jin, Ruofei Zhang, Jianchang Mao, Learning to Rank by Optimizing NDCG Measure[5], in Proceeding of Neural Information Processing Systems (NIPS), 2010.
23. Fuhr, Norbert (1992), "Probabilistic Models in Information Retrieval", Computer Journal 35 (3): 243–255, doi:10.1093/comjnl/35.3.243 
24. Manning C., Raghavan P. and Schütze H. (2008), Introduction to Information Retrieval, Cambridge University Press .
25. Jan O. Pedersen.
26. U.S. Patent 7,197,497
27. Bing Search Blog: User Needs, Features and the Science behind Bing
28. Yandex corporate blog entry about new ranking model "Snezhinsk" el 1 de marzo de 2012 en Wayback Machine. (in Russian)
29. The algorithm wasn't disclosed, but a few details were made public in [6] and [7].
30. Yandex's Internet Mathematics 2009 competition page
31. Yahoo Learning to Rank Challenge el 1 de marzo de 2010 en Wayback Machine.
32. Rajaraman, Anand (2008-05-24).
33. Costello, Tom (2009-06-26).

Enlaces externos

Competiciones y públicos datasets

• LETOR: Un Benchmark Colección para Investigar encima Aprendiendo a Rango para Información Retrieval
• Yandex Matemática de Internet 2009
• !
• Aprendizaje de Microsoft a Rango Datasets

Código de código abierto

• Paralelo C++/MPI implementación de Gradiente Árboles de Regresión Aumentada para ranking, septiembre liberado 2011
• C++ implementación de Gradiente Árboles de Regresión Aumentada y Bosques Aleatorios para ranking
• C++ y herramientas de Pitón para utilizar el SVM-algoritmo de Rango

•   Datos: Q4330127