Publication:

Applying Learning Techniques in SABIO, a Constraint Programming Application for Soccer Analysis.

Resumen en español

El fútbol es uno de los deportes más importantes en el mundo, con un gran impacto en los medios masivos de comunicación y seguido por millones de personas. Una competencia de fútbol consiste en n equipos jugando en un sistema de todos contra todos, ya sea en un torneo o liga. Estas competencias ofrecen una excelente oportunidad para modelar problemas relacionados con preguntas que los hinchas frecuentemente tienen sobre sus equipos favoritos. Por ejemplo, en determinado momento, los hinchas pueden estar interesados en determinar si un equipo aún tiene posibilidades de ganar la competencia, es decir, quedar de primero en la liga o finalizar dentro de los primeros k equipos en un tornero para clasificar al sistema de eliminación. Esta pregunta se denomina el problema de la eliminación, el cual es NP-Completo para el sistema actual de puntos determinado por la FIFA (0, 1, 3). Cero puntos cuando se pierde, un punto cuando se empata, tres puntos cuando se gana. La programación por restricciones (CP), es un paradigma que ha desarrollado diversas técnicas para abordar problemas combinatorios y en los últimos años, un creciente interés en combinar CP con aprendizaje de maquina (ML) ha sido estudiado con el fín de mejorar la eficiencia de CP en la búsqueda de soluciones. SABIO es acrónimo de Soccer Analysis Based on Inference Outputs, una plataforma desarrollada bajo el paradigma de CP con el soporte académico de AVISPA, un grupo de investigación de la Universidad del Valle (www.sabiofutbol.com). SABIO puede ser usado para descubrir información y responder preguntas relacionadas con equipos de fútbol en una competencia particular. La plataforma ofrece interfaces gráficas para establecer preguntas en forma de restricciones. Para encontrar soluciones, SABIO utiliza estrategias de búsqueda que incluyen selección estática de variable/valor que funcionan bien para ciertas instancias. Sin embargo, pruebas empíricas sobre la aplicación, permitieron identificar una familia de instancias donde SABIO presenta bajo rendimiento para encontrar soluciones y los tiempos de ejecución son muy largos (más de 30 segundos) para ser ofrecidos en una aplicación web o móvil. Para afrontar esta dificultad, hemos combinado el uso de programación por restricciones, aprendizaje de máquina y programación entera mixta (MIP) para proponer 2 modelos que resuelvan preguntas relacionadas con fútbol en cualquier momento de la competencia. El primer modelo (CP-ML) combina una serie de nuevas restricciones que incrementan la poda en el árbol de búsqueda, además de un clasificador para selección de valores. El segundo modelo (MIP) es una versión de programación entera mixta de SABIO. Nuestros experimentos demuestran que estos nuevos modelos mejoran el rendimiento de SABIO. Encontramos también que si ambos modelos se combinan en una ejecución mixta, se convierten en un solver muy robusto y rápido