La selección de algoritmos (a veces también llamada selección de algoritmos por instancia o selección de algoritmos fuera de línea ) es una técnica meta- algorítmicapara elegir un algoritmo de una cartera en función de cada instancia. Está motivado por la observación de que en muchos problemas prácticos, diferentes algoritmos tienen diferentes características de rendimiento. Es decir, mientras que un algoritmo funciona bien en algunos escenarios, funciona mal en otros y viceversa para otro algoritmo. Si podemos identificar cuándo usar qué algoritmo, podemos optimizar para cada escenario y mejorar el rendimiento general. Esto es lo que pretende hacer la selección de algoritmos. El único requisito previo para aplicar técnicas de selección de algoritmos es que exista (o que pueda construirse) un conjunto de algoritmos complementarios.
Definición
Dada una cartera de algoritmos , un conjunto de instancias y una métrica de costos , el problema de selección del algoritmo consiste en encontrar un mapeo de instancias a los algoritmos tal que el costo en todas las instancias está optimizado. [1] [2]
Ejemplos de
Problema de satisfacibilidad booleano (y otros problemas combinatorios difíciles)
Una aplicación bien conocida de la selección de algoritmos es el problema de satisfacibilidad booleano . Aquí, la cartera de algoritmos es un conjunto de solucionadores SAT (complementarios) , las instancias son fórmulas booleanas, la métrica de costo es, por ejemplo, el tiempo de ejecución promedio o el número de instancias sin resolver. Por lo tanto, el objetivo es seleccionar un solucionador de SAT de buen rendimiento para cada instancia individual. De la misma manera, la selección de algoritmos se puede aplicar a muchos otros-Problemas difíciles (como programación de enteros mixtos , CSP , planificación de IA , TSP , MAXSAT , QBF y programación de conjuntos de respuestas ). Los sistemas ganadores de la competencia en SAT son SATzilla, [3] 3S [4] y CSHC [5]
Aprendizaje automático
En el aprendizaje automático , la selección de algoritmos se conoce mejor como metaaprendizaje . La cartera de algoritmos consta de algoritmos de aprendizaje automático (por ejemplo, Random Forest, SVM, DNN), las instancias son conjuntos de datos y la métrica de costo es, por ejemplo, la tasa de error. Entonces, el objetivo es predecir qué algoritmo de aprendizaje automático tendrá un pequeño error en cada conjunto de datos.
Características de la instancia
El problema de selección de algoritmos se resuelve principalmente con técnicas de aprendizaje automático. Representando las instancias del problema mediante características numéricas, la selección de algoritmos puede verse como un problema de clasificación de clases múltiples al aprender un mapeo para una instancia determinada .
Las características de instancia son representaciones numéricas de instancias. Por ejemplo, podemos contar el número de variables, cláusulas, la longitud promedio de cláusulas para fórmulas booleanas, [6] o el número de muestras, características, balance de clases para conjuntos de datos de AA para obtener una impresión sobre sus características.
Características estáticas frente a características de palpación
Distinguimos entre dos tipos de características:
- Las características estáticas son, en la mayoría de los casos, algunos recuentos y estadísticas (por ejemplo, relación cláusulas / variables en SAT). Estas características van desde características muy económicas (por ejemplo, número de variables) hasta características muy complejas (por ejemplo, estadísticas sobre gráficos de cláusulas variables).
- Las características de sondeo (a veces también llamadas características de marcas de referencia) se calculan ejecutando algún análisis del comportamiento del algoritmo en una instancia (por ejemplo, la precisión de un algoritmo de árbol de decisión barato en un conjunto de datos ML, o ejecutando por un corto tiempo un solucionador de búsqueda local estocástico en un Fórmula booleana). Estas características a menudo cuestan más que las simples características estáticas.
Costos de funciones
Dependiendo de la métrica de rendimiento utilizada , el cálculo de características se puede asociar con costos. Por ejemplo, si usamos el tiempo de ejecución como métrica de rendimiento, incluimos el tiempo para calcular las características de nuestra instancia en el rendimiento de un sistema de selección de algoritmos. La resolución de SAT es un ejemplo concreto, donde dichos costos de características no se pueden descuidar, ya que las características de instancia para fórmulas CNF pueden ser muy baratas (por ejemplo, para obtener el número de variables se puede hacer en tiempo constante para CNF en el formato DIMAC) o muy costosas (por ejemplo, funciones gráficas que pueden costar decenas o cientos de segundos).
Es importante tener en cuenta la sobrecarga del cálculo de características en la práctica en tales escenarios; de lo contrario, se crea una impresión engañosa del rendimiento del enfoque de selección de algoritmos. Por ejemplo, si la decisión de qué algoritmo elegir se puede tomar con perfecta precisión, pero las características son el tiempo de ejecución de los algoritmos de la cartera, el enfoque de la cartera no tiene ningún beneficio. Esto no sería obvio si se omitieran los costos de las funciones.
Enfoques
Enfoque de regresión
Uno de los primeros enfoques exitosos de selección de algoritmos predijo el rendimiento de cada algoritmo. y seleccioné el algoritmo con el mejor rendimiento previsto por una instancia . [3]
Enfoque de agrupación
Una suposición común es que el conjunto dado de instancias se pueden agrupar en subconjuntos homogéneos y para cada uno de estos subconjuntos, hay un algoritmo de buen rendimiento para todas las instancias allí. Entonces, el entrenamiento consiste en identificar los clústeres homogéneos a través de un enfoque de clustering no supervisado y asociar un algoritmo con cada clúster. Se asigna una nueva instancia a un clúster y se selecciona el algoritmo asociado. [7]
Un enfoque más moderno es la agrupación jerárquica sensible a los costos [5] que utiliza el aprendizaje supervisado para identificar los subconjuntos de instancias homogéneas.
Enfoque de clasificación sensible al costo por pares
Un enfoque común para la clasificación de clases múltiples es aprender modelos por pares entre cada par de clases (aquí algoritmos) y elegir la clase que fue predicha con mayor frecuencia por los modelos por pares. Podemos ponderar las instancias del problema de predicción por pares por la diferencia de rendimiento entre los dos algoritmos. Esto está motivado por el hecho de que nos preocupamos más por obtener predicciones con grandes diferencias correctas, pero la penalización por una predicción incorrecta es pequeña si casi no hay diferencia de rendimiento. Por lo tanto, cada instancia para entrenar un modelo de clasificación vs está asociado con un costo . [8]
Requisitos
El problema de selección del algoritmo se puede aplicar de manera efectiva bajo los siguientes supuestos:
- El portafolio de algoritmos es complementario con respecto al conjunto de instancias , es decir, no existe un algoritmo único que domina el rendimiento de todos los demás algoritmos sobre (véanse las figuras a la derecha para ver ejemplos de análisis complementario).
- En algunas aplicaciones, el cálculo de las características de la instancia está asociado con un costo. Por ejemplo, si la métrica de costo es tiempo de ejecución, también debemos considerar el tiempo para calcular las características de la instancia. En tales casos, el costo de calcular las características no debería ser mayor que la ganancia de rendimiento a través de la selección del algoritmo.
Dominios de aplicación
La selección del algoritmo no se limita a dominios individuales, sino que se puede aplicar a cualquier tipo de algoritmo si se cumplen los requisitos anteriores. Los dominios de aplicación incluyen:
- problemas combinatorios difíciles: [10] SAT , programación de enteros mixtos , CSP , planificación de IA , TSP , MAXSAT , QBF y programación de conjuntos de respuestas
- subastas combinatorias
- en el aprendizaje automático, el problema se conoce como metaaprendizaje
- diseño de software
- optimización de caja negra
- sistemas multiagente
- optimización numérica
- álgebra lineal, ecuaciones diferenciales
- algoritmos evolutivos
- problema de ruta del vehículo
- sistemas de poder
Para obtener una lista extensa de literatura sobre la selección de algoritmos, nos referimos a una descripción general de la literatura.
Variantes de selección de algoritmos
Selección online
La selección de algoritmos en línea se refiere al cambio entre diferentes algoritmos durante el proceso de resolución. Esto es útil como hiperheurística . Por el contrario, la selección de algoritmos fuera de línea selecciona un algoritmo para una instancia determinada solo una vez y antes del proceso de resolución.
Cálculo de horarios
Una extensión de la selección de algoritmos es el problema de programación de algoritmos por instancia, en el que no seleccionamos solo un solucionador, sino que seleccionamos un presupuesto de tiempo para cada algoritmo en una base por instancia. Este enfoque mejora el rendimiento de los sistemas de selección, en particular, si las características de la instancia no son muy informativas y es probable que se realice una selección incorrecta de un solo solucionador. [11]
Selección de carteras paralelas
Dada la importancia cada vez mayor del cálculo paralelo, una extensión de la selección de algoritmos para el cálculo paralelo es la selección de cartera paralela, en la que seleccionamos un subconjunto de los algoritmos para que se ejecuten simultáneamente en una cartera paralela. [12]
enlaces externos
Referencias
- ^ Arroz, John R. (1976). "El problema de la selección del algoritmo". Avances en informática . 15 . págs. 65-118. doi : 10.1016 / S0065-2458 (08) 60520-3 . ISBN 9780120121151.
- ^ Bischl, Bernd; Kerschke, Pascal; Kotthoff, Lars; Lindauer, Marius; Malitsky, Yuri; Fréchette, Alexandre; Hoos, Holger; Hutter, Frank; Leyton-Brown, Kevin; Tierney, Kevin; Vanschoren, Joaquín (2016). "ASlib: una biblioteca de referencia para la selección de algoritmos". Inteligencia artificial . 237 : 41–58. arXiv : 1506.02465 . doi : 10.1016 / j.artint.2016.04.003 .
- ^ a b L. Xu; F. Hutter; H. Hoos y K. Leyton-Brown (2008). "SATzilla: Selección de algoritmos basados en cartera para SAT". Revista de Investigación en Inteligencia Artificial . 32 : 565–606. arXiv : 1111.2249 . doi : 10.1613 / jair.2490 .
- ^ S. Kadioglu; Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2011). "Selección y programación de algoritmos". En Lee, J. (ed.). Principios y práctica de la programación de restricciones . Apuntes de conferencias en Ciencias de la Computación. 6876 . págs. 454–469. CiteSeerX 10.1.1.211.1807 . doi : 10.1007 / 978-3-642-23786-7_35 . ISBN 978-3-642-23785-0.
- ^ a b Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2013). "Portafolios de algoritmos basados en agrupación jerárquica sensible a los costos". Actas de la Vigésima Tercera Conferencia Conjunta Internacional sobre Inteligencia Artificial . págs. 608–614. ISBN 978-1-57735-633-2.
- ^ E. Nudelman; K. Leyton-Brown; H. Hoos; A. Devkar; Y. Shoham (2004). "Comprensión del SAT aleatorio: más allá de la relación entre cláusulas y variables" (PDF) . Procesos de CP .
- ^ S. Kadioglu; Y. Malitsky; M. Sellmann; K. Tierney (2010). "ISAC - Configuración del algoritmo específico de la instancia" (PDF) . Actas de la Conferencia europea sobre inteligencia artificial .
- ^ L. Xu; F. Hutter; J. Shen; H. Hoos; K. Leyton-Brown (2012). "SATzilla2012: Selección de algoritmo mejorada basada en modelos de clasificación sensibles al costo" (PDF) . Actas del SAT Challenge 2012: descripciones de Solver y Benchmark .
- ^ A. Frechette; L. Kotthoff; T. Michalak; T. Rahwan; H. Hoos y K. Leyton-Brown (2016). "Uso del valor de Shapley para analizar carteras de algoritmos" . Actas de la Conferencia Internacional sobre AAAI .
- ^ Kotthoff, Lars. " Selección de algoritmos para problemas de búsqueda combinatoria: una encuesta ". Programación de Restricciones y Minería de Datos. Springer, Cham, 2016. 149-190.
- ^ M. Lindauer; R. Bergdoll; F. Hutter (2016). "Un estudio empírico de programación de algoritmos por instancia" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje y Optimización Inteligente . Apuntes de conferencias en Ciencias de la Computación. 10079 : 253-259. doi : 10.1007 / 978-3-319-50349-3_20 . ISBN 978-3-319-50348-6.
- ^ M. Lindauer; H. Hoos y F. Hutter (2015). "De la selección de algoritmos secuenciales a la selección de carteras paralelas" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje y Optimización Inteligente . Apuntes de conferencias en Ciencias de la Computación. 8994 : 1–16. doi : 10.1007 / 978-3-319-19084-6_1 . ISBN 978-3-319-19083-9.