Contribuciones al problema de agregación de rankings. Aplicaciones al aprendizaje automático

• Autores: David Molina García
• Directores de la Tesis: Juan Angel Aledo Sánchez (dir. tes.) , José Antonio Gámez Martín (codir. tes.)
• Lectura: En la Universidad de Castilla-La Mancha ( España ) en 2015
• Idioma: español
• Tribunal Calificador de la Tesis: José Antonio Lozano Alonso (presid.) , José Miguel Puerta Callejón (secret.) , Antonio Salmerón Cerdán (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • La tesis se centra en el estudio de problemas clásicos como el problema de rankings de Kemeny y el problema de agregación de rankings. En ellos, partiendo de N ordenaciones o rankings de n elementos representando las preferencias de N jueces, se pretende encontrar la permutación que esté a menor distancia del conjunto inicial. Para medir distancias entre rankings, se usan diversas distancias, entre las que tiene especial importancia la distancia de Kendall. Estos problemas son NP-duros para N mayor o igual que 4, lo que hace especialmente interesante su estudio. En el problema de rankings de Kemeny las N ordenaciones son permutaciones, es decir, rankings de n elementos en los que la preferencia entre los elementos está perfectamente determinada. En cambio, para el problema de agregación de rankings las ordenaciones pueden presentar o no empates y pueden ser o no incompletas. Por ello, suele entenderse que este último es una generalización del problema de rankings de Kemeny.

    Para resolver el problema de rankings de Kemeny, se han desarrollado una serie de algoritmos metaheurísticos que obtienen muy buenos resultados al compararlos con los algoritmos del estado del arte. De hecho, se obtiene significancia estadística en gran parte de las pruebas realizadas. Se han llevado a cabo pruebas usando el conocido Modelo de Mallows, tanto para el muestreo inicial como para la estimación de sus parámetros. Asimismo, también se ha estudiado el Modelo de Mallows generalizado, una versión más compleja del anterior (mayor número de parámetros a estimar).

    Para el problema de agregación de rankings, se ha desarrollado una generalización del popular algoritmo Borda, muy empleado en la resolución del problema de rankings de Kemeny dado su equilibrio entre eficacia y rapidez. Dado que este algoritmo está pensado para permutaciones, se ha adaptado el algoritmo para trabajar con ordenaciones que presentan empates o son incompletos.

    Por último se estudió el llamado problema de predicción de rankings, de la rama del aprendizaje automático. En este caso, cada ordenación está etiquetada con k atributos que describen de algún modo la instancia. La finalidad del problema consiste en construir un clasificador que sea capaz de predecir rankings a partir de nuevos atributos. Para ello, el clasificador debe construirse usando un conjunto de instancias (llamado conjunto de entrenamiento) y después pasar a evaluar la calidad de dicho clasificador usando un conjunto diferente de instancias (llamado conjunto de validación).