Sélection de l'algorithme - Algorithm selection

La sélection d'algorithmes (parfois également appelée sélection d'algorithmes par instance ou sélection d'algorithmes hors ligne ) est une technique méta- algorithmique permettant de choisir un algorithme dans un portefeuille instance par instance. Il est motivé par l'observation que sur de nombreux problèmes pratiques, différents algorithmes ont des caractéristiques de performances différentes. Autrement dit, alors qu'un algorithme fonctionne bien dans certains scénarios, il fonctionne mal dans d'autres et vice versa pour un autre algorithme. Si nous pouvons identifier quand utiliser quel algorithme, nous pouvons optimiser pour chaque scénario et améliorer les performances globales. C'est ce que la sélection d'algorithmes vise à faire. Le seul préalable à l'application des techniques de sélection d'algorithmes est qu'il existe (ou qu'il puisse être construit) un ensemble d'algorithmes complémentaires.

Définition

Étant donné un portefeuille d'algorithmes , un ensemble d'instances et une métrique de coût , le problème de sélection d'algorithmes consiste à trouver une correspondance des instances aux algorithmes de telle sorte que le coût de toutes les instances soit optimisé. ${\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)}$

Exemples

Problème de satisfiabilité booléenne (et autres problèmes combinatoires difficiles)

Une application bien connue de la sélection d'algorithmes est le problème de satisfiabilité booléenne . Ici, le portefeuille d'algorithmes est un ensemble de solveurs SAT (complémentaires) , les instances sont des formules booléennes, la métrique de coût est par exemple le temps d'exécution moyen ou le nombre d'instances non résolues. Ainsi, l'objectif est de sélectionner un solveur SAT performant pour chaque instance individuelle. De la même manière, la sélection d'algorithmes peut être appliquée à de nombreux autres problèmes difficiles (tels que la programmation mixte en nombres entiers , CSP , AI planning , TSP , MAXSAT , QBF et la programmation d'ensembles de réponses ). Les systèmes gagnants de la compétition dans SAT sont SATzilla, 3S et CSHC ${\displaystyle {\mathcal {NP}}}$

Apprentissage automatique

En apprentissage automatique , la sélection d'algorithmes est mieux connue sous le nom de méta-apprentissage . Le portefeuille d'algorithmes se compose d'algorithmes d'apprentissage automatique (par exemple, Random Forest, SVM, DNN), les instances sont des ensembles de données et la métrique de coût est par exemple le taux d'erreur. Ainsi, l'objectif est de prédire quel algorithme d'apprentissage automatique aura une petite erreur sur chaque ensemble de données.

Caractéristiques des instances

Le problème de sélection d'algorithme est principalement résolu avec des techniques d'apprentissage automatique. En représentant les instances du problème par des caractéristiques numériques , la sélection d'algorithmes peut être considérée comme un problème de classification multi-classes en apprenant un mappage pour une instance donnée . ${\style d'affichage f}$${\displaystyle f_{i}\mapsto {\mathcal {A}}}$${\style d'affichage i}$

Les entités d'instance sont des représentations numériques d'instances. Par exemple, nous pouvons compter le nombre de variables, de clauses, la longueur moyenne des clauses pour les formules booléennes, ou le nombre d'échantillons, de caractéristiques, d'équilibre de classe pour les ensembles de données ML pour avoir une idée de leurs caractéristiques.

Fonctionnalités statiques ou de palpage

Nous distinguons deux types de fonctionnalités :

1. Les caractéristiques statiques sont dans la plupart des cas des comptes et des statistiques (par exemple, le rapport clauses-variables dans SAT). Ces fonctionnalités vont de fonctionnalités très bon marché (par exemple, le nombre de variables) à des fonctionnalités très complexes (par exemple, des statistiques sur les graphiques à clauses variables).
2. Les caractéristiques de sondage (parfois également appelées caractéristiques de repère) sont calculées en exécutant une analyse du comportement de l'algorithme sur une instance (par exemple, la précision d'un algorithme d'arbre de décision bon marché sur un ensemble de données ML, ou en exécutant pendant une courte période un solveur de recherche locale stochastique sur un formule booléenne). Ces fonctionnalités coûtent souvent plus cher que de simples fonctionnalités statiques.

Coûts des fonctionnalités

Selon la métrique de performance utilisée , le calcul des caractéristiques peut être associé à des coûts. Par exemple, si nous utilisons le temps d'exécution comme mesure de performance, nous incluons le temps nécessaire pour calculer nos caractéristiques d'instance dans les performances d'un système de sélection d'algorithme. La résolution SAT est un exemple concret, où de tels coûts de caractéristiques ne peuvent pas être négligés, car les caractéristiques d'instance pour les formules CNF peuvent être soit très bon marché (par exemple, obtenir le nombre de variables peut être fait en temps constant pour les CNF au format DIMAC) ou très coûteux (par exemple, des caractéristiques graphiques qui peuvent coûter des dizaines ou des centaines de secondes). ${\style d'affichage m}$

Il est important de prendre en compte la surcharge du calcul des caractéristiques dans la pratique dans de tels scénarios ; sinon, une impression trompeuse de la performance de l'approche de sélection d'algorithme est créée. Par exemple, si la décision de l'algorithme à choisir peut être prise avec une précision parfaite, mais que les caractéristiques sont le temps d'exécution des algorithmes de portefeuille, il n'y a aucun avantage à l'approche de portefeuille. Cela ne serait pas évident si les coûts des fonctionnalités étaient omis.

Approches

Approche de régression

L'une des premières approches de sélection d'algorithmes réussies a prédit les performances de chaque algorithme et sélectionné l'algorithme avec les meilleures performances prévues pour une instance . ${\displaystyle {\hat {m}}_{\mathcal {A}} :{\mathcal {I}}\to \mathbb {R} }$${\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}$${\style d'affichage i}$

Approche de regroupement

Une hypothèse courante est que l'ensemble donné d'instances peut être regroupé en sous-ensembles homogènes et pour chacun de ces sous-ensembles, il existe un algorithme performant pour toutes les instances. Ainsi, l'apprentissage consiste à identifier les clusters homogènes via une approche de clustering non supervisé et à associer un algorithme à chaque cluster. Une nouvelle instance est affectée à un cluster et l'algorithme associé est sélectionné. ${\displaystyle {\mathcal {I}}}$

Une approche plus moderne est le clustering hiérarchique sensible aux coûts utilisant l'apprentissage supervisé pour identifier les sous-ensembles d'instances homogènes.

Approche de classification sensible aux coûts par paire

Une approche courante pour la classification multi-classes consiste à apprendre des modèles par paires entre chaque paire de classes (ici des algorithmes) et à choisir la classe qui a été prédite le plus souvent par les modèles par paires. Nous pouvons pondérer les instances du problème de prédiction par paires par la différence de performance entre les deux algorithmes. Ceci est motivé par le fait que nous nous soucions le plus d'obtenir des prédictions avec de grandes différences correctes, mais la pénalité pour une prédiction incorrecte est faible s'il n'y a presque pas de différence de performance. Par conséquent, chaque instance d'apprentissage d'un modèle de classification vs est associée à un coût . ${\style d'affichage i}$${\displaystyle {\mathcal {A}}_{1}}$${\displaystyle {\mathcal {A}}_{2}}$${\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}$

Exigences

Regroupement des solveurs SAT du scénario SAT12-INDU ASlib selon le coefficient de corrélation de spearman.

Valeurs de Shapley pour une analyse complémentaire sur le scénario SAT12-INDU ASlib

Le problème de sélection d'algorithme peut être appliqué efficacement sous les hypothèses suivantes :

• Le portefeuille d'algorithmes est complémentaire par rapport à l'ensemble d'instances , c'est-à-dire qu'il n'y a pas un seul algorithme qui domine les performances de tous les autres algorithmes (voir les figures à droite pour des exemples d'analyse complémentaire).${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$
• Dans certaines applications, le calcul des caractéristiques d'instance est associé à un coût. Par exemple, si la métrique de coût est le temps d'exécution, nous devons également prendre en compte le temps de calcul des caractéristiques de l'instance. Dans de tels cas, le coût de calcul des caractéristiques ne doit pas être supérieur au gain de performances grâce à la sélection de l'algorithme.

Domaines d'application

La sélection d'algorithmes n'est pas limitée à des domaines uniques mais peut être appliquée à n'importe quel type d'algorithme si les exigences ci-dessus sont satisfaites. Les domaines d'application comprennent :

• problèmes combinatoires difficiles : SAT , programmation en nombres entiers mixtes , CSP , planification de l'IA , TSP , MAXSAT , QBF et Answer Set Programming
• enchères combinatoires
• en apprentissage automatique, le problème est connu sous le nom de méta-apprentissage
• conception de logiciels
• optimisation boîte noire
• systèmes multi-agents
• optimisation numérique
• algèbre linéaire, équations différentielles
• algorithmes évolutionnaires
• problème de tournée de véhicule
• systèmes d'alimentation

Pour une liste exhaustive de la littérature sur la sélection d'algorithmes, nous nous référons à un aperçu de la littérature.

Variantes de sélection d'algorithmes

Sélection en ligne

La sélection d'algorithmes en ligne fait référence à la commutation entre différents algorithmes au cours du processus de résolution. Ceci est utile en tant qu'hyper-heuristique . En revanche, la sélection d'algorithmes hors ligne sélectionne un algorithme pour une instance donnée une seule fois et avant le processus de résolution.

Calcul des horaires

Une extension de la sélection d'algorithmes est le problème d'ordonnancement d'algorithmes par instance, dans lequel nous ne sélectionnons pas un seul solveur, mais nous sélectionnons un budget temporel pour chaque algorithme sur une base par instance. Cette approche améliore les performances des systèmes de sélection en particulier si les caractéristiques d'instance ne sont pas très informatives et qu'une mauvaise sélection d'un seul solveur est probable.

Sélection de portefeuilles parallèles

Compte tenu de l'importance croissante du calcul parallèle, une extension de la sélection d'algorithmes pour le calcul parallèle est la sélection de portefeuille parallèle, dans laquelle nous sélectionnons un sous-ensemble d'algorithmes à exécuter simultanément dans un portefeuille parallèle.

Liens externes

• Bibliothèque de sélection d'algorithmes (ASlib)
• Littérature de sélection d'algorithmes

Les références