Selección de algoritmo

Técnica meta-algorítmica para elegir un algoritmo

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 metaalgoritmica para elegir un algoritmo de una cartera de algoritmos caso por caso. Está motivada 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 se pueda construir) 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 de algoritmos consiste en encontrar una asignación de instancias a algoritmos tal que se optimice el costo en todas las instancias. ^{[1] [2]} ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R} }$ ${\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}$

Ejemplos

Problema de satisfacibilidad booleana (y otros problemas combinatorios difíciles)

Una aplicación bien conocida de la selección de algoritmos es el problema de satisfacibilidad booleana . 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 la cantidad de instancias sin resolver. Por lo tanto, el objetivo es seleccionar un solucionador 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 la programación entera mixta , 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]. ${\displaystyle {\mathcal {NP}}}$

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. Por lo tanto, 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. Al representar las instancias del problema mediante características numéricas , la selección de algoritmos puede considerarse como un problema de clasificación de múltiples clases mediante el aprendizaje de una asignación para una instancia dada . ${\displaystyle f}$ ${\displaystyle f_{i}\mapsto {\mathcal {A}}}$ ${\displaystyle i}$

Las características de instancia son representaciones numéricas de instancias. Por ejemplo, podemos contar la cantidad de variables, cláusulas, longitud promedio de cláusula para fórmulas booleanas, ^[6] o la cantidad de muestras, características y equilibrio de clases para conjuntos de datos de ML para obtener una idea de sus características.

Características estáticas y de sondeo

Distinguimos dos tipos de características:

1. Las características estáticas son, en la mayoría de los casos, algunos recuentos y estadísticas (por ejemplo, la relación cláusulas-variables en SAT). Estas características varían desde características muy económicas (por ejemplo, la cantidad de variables) hasta características muy complejas (por ejemplo, estadísticas sobre gráficos de cláusulas-variables).
2. Las características de sondeo (a veces también llamadas características 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 económico en un conjunto de datos de ML o ejecutando durante un breve período un solucionador de búsqueda local estocástico en una fórmula booleana). Estas características suelen costar más que las características estáticas simples.

Costos de las funciones

Dependiendo de la métrica de rendimiento utilizada , el cálculo de características puede estar asociado con costos. Por ejemplo, si usamos el tiempo de ejecución como métrica de rendimiento, incluimos el tiempo para calcular nuestras características de instancia en el rendimiento de un sistema de selección de algoritmos. La resolución SAT es un ejemplo concreto, donde dichos costos de características no pueden descuidarse, 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 caras (por ejemplo, características de gráficos que pueden costar decenas o cientos de segundos). ${\displaystyle m}$

En la práctica, es importante tener en cuenta los costes de cálculo de las características en estos escenarios; de lo contrario, se crea una impresión errónea del rendimiento del enfoque de selección de algoritmos. Por ejemplo, si la decisión sobre qué algoritmo elegir se puede tomar con perfecta precisión, pero las características son el tiempo de ejecución de los algoritmos de cartera, no hay ningún beneficio para el enfoque de cartera. Esto no sería obvio si se omitieran los costos de las características.

Aproches

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 para una instancia . ^[3] ${\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R} }$ ${\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}$ ${\displaystyle i}$

Enfoque de agrupamiento

Una suposición común es que el conjunto dado de instancias se puede agrupar en subconjuntos homogéneos y para cada uno de estos subconjuntos, existe un algoritmo de buen rendimiento para todas las instancias que lo componen. Por lo tanto, el entrenamiento consiste en identificar los clústeres homogéneos mediante un enfoque de agrupamiento 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] ${\displaystyle {\mathcal {I}}}$

Un enfoque más moderno es la agrupación jerárquica sensible a los costos ^[5] que utiliza 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 múltiples clases 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á asociada con un costo . ^[8] ${\displaystyle i}$ ${\displaystyle {\mathcal {A}}_{1}}$ ${\displaystyle {\mathcal {A}}_{2}}$ ${\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}$

Requisitos

Agrupamiento de solucionadores SAT del escenario SAT12-INDU ASlib según el coeficiente de correlación de Spearman.

Valores de Shapley para el análisis complementario en el escenario ASlib SAT12-INDU ^[9]

El problema de selección de algoritmos se puede aplicar eficazmente bajo los siguientes supuestos:

• La cartera de algoritmos es complementaria con respecto al conjunto de instancias , es decir, no existe un único algoritmo que domine el rendimiento de todos los demás algoritmos (consulte las figuras a la derecha para ver ejemplos de análisis complementarios). ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$ ${\displaystyle {\mathcal {I}}}$
• En algunas aplicaciones, el cálculo de las características de instancia está asociado a un costo. Por ejemplo, si la métrica de costo es el tiempo de ejecución, también debemos considerar el tiempo para calcular las características de instancia. En tales casos, el costo para calcular las características no debe ser mayor que la ganancia de rendimiento a través de la selección del algoritmo.

Dominios de aplicación

La selección de algoritmos no se limita a dominios únicos, 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 Entera Mixta , 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 energía

Para obtener una lista extensa de literatura sobre la selección de algoritmos, consultamos una descripción general de la literatura.

Variantes de selección de algoritmos

Selección en línea

La selección de algoritmos en línea se refiere a cambiar entre diferentes algoritmos durante el proceso de resolución. Esto es útil como una 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 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 seleccione incorrectamente un único solucionador. ^[11]

Selección de carteras paralelas

Dada la creciente importancia 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 ejecutarlos simultáneamente en una cartera paralela. ^[12]

Enlaces externos

• Biblioteca de selección de algoritmos (ASlib)
• Literatura sobre selección de algoritmos

Referencias

1. Rice, John R. (1976). "El problema de selección de algoritmos". Advances in Computers. Vol. 15. págs. 65-118. doi :10.1016/S0065-2458(08)60520-3. ISBN 9780120121151.
2. 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. S2CID  261945.
3. 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. S2CID  10987043.
4. 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 con restricciones . Apuntes de clase en informática. Vol. 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.
5. Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2013). "Carteras de algoritmos basadas en agrupamiento jerárquico sensible a los costos". Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial . AAAI Press. págs. 608–614. ISBN 978-1-57735-633-2.
6. E. Nudelman; K. Leyton-Brown; H. Hoos; A. Devkar; Y. Shoham (2004). "Entender el SAT aleatorio: más allá de la relación cláusulas-variables" (PDF) . Actas de CP .
7. S. Kadioglu; Y. Malitsky; M. Sellmann; K. Tierney (2010). "ISAC – Instance-Specific Algorithm Configuration" (PDF) . Actas de la Conferencia Europea sobre Inteligencia Artificial .
8. L. Xu; F. Hutter; J. Shen; H. Hoos; K. Leyton-Brown (2012). "SATzilla2012: Selección de algoritmos mejorada basada en modelos de clasificación sensibles a los costos" (PDF) . Actas del Desafío SAT 2012: Descripciones de solucionadores y puntos de referencia .
9. 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 AAAI sobre Inteligencia Artificial . 30 . doi : 10.1609/aaai.v30i1.10440 . S2CID  6676831.
10. Kotthoff, Lars. "Selección de algoritmos para problemas de búsqueda combinatoria: un estudio". Minería de datos y programación con restricciones. Springer, Cham, 2016. 149-190.
11. M. Lindauer; R. Bergdoll; F. Hutter (2016). "Un estudio empírico de la programación de algoritmos por instancia". Aprendizaje y optimización inteligente (PDF) . Apuntes de clase en informática. Vol. 10079. págs. 253–259. doi :10.1007/978-3-319-50349-3_20. ISBN 978-3-319-50348-6.
12. M. Lindauer; H. Hoos y F. Hutter (2015). "De la selección de algoritmos secuenciales a la selección de carteras paralelas". Aprendizaje y optimización inteligente (PDF) . Apuntes de clase en informática. Vol. 8994. págs. 1–16. doi :10.1007/978-3-319-19084-6_1. ISBN 978-3-319-19083-9.