Aprendizaje de clasificación​ o aprendizaje de máquina de clasificación (MLR por sus siglas en inglés) es la aplicación de aprendizaje de máquina, típicamente supervisado, semi-supervisado o aprendizaje reforzado en la construcción de modelos de ranking para sistemas de recuperación de información.​ Los datos de entrenamiento consiste 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 ranking es clasificar, es decir, 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 sentimentos, 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 — sólo 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 machine-learned 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;​
  • En biología computacional para la clasificación de estructuras candidatos 3-D en el problema de predicción de estructura de proteína.​
  • En proteómica para la identificación de péptidos frecuentes de puntuación superior.​
  • 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 él o ella ha leído un artículo noticioso actual.​

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.​​
  • 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:​

  • 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.​ 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);​
  • pfound de Yandex.​

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:​

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​ 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​ 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.​
2002 Pranking​ 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 QBRank 2 pairwise
2007 RankCosine 3 listwise
2007 RankGP​ 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.​

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.​
2008 ListMLE 3 listwise Basado en ListNet.
2008 PermuRank 3 listwise
2008 SoftRank 3 listwise
2008 Ranking Refinamiento ​ 2 pairwise

Un enfoque semi-supervisado para aprender a clasificar que utiliza Impulso.

2008 SSRankBoost ​ 2 pairwise

Una extensión de RankBoost para aprender con datos parcialmente etiquetados (aprendizaje semi-supervisado para clasificar)

2008 SortNet ​ 2 pairwise SortNet, un algoritmo de clasificación de adaptación que ordena los objetos utilizando una red neuronal como comparador.
2009 MPBoost 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 BoltzRank 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 ​ 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 IntervalRank 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.​​ 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.​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.​

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.​​

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

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.​​ 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.​ Yahoo Ha anunciado una competición similar en 2010.​

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.​ 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".​


Este artículo utiliza material del artículo de Wikipedia Aprendizaje de clasificación, que se publica en Creative Commons Attribution-Share-Alike License 3.0.