Recherche quasi aléatoire

Ce module porte sur la recherche quasi-aléatoire.

Pourquoi utiliser la recherche quasi-aléatoire ?

La recherche quasi-aléatoire (basée sur des séquences à faible écart) est notre préférence par rapport à des outils d'optimisation de boîte noire plus sophistiqués lorsqu'elle est utilisée dans le cadre d'un processus de réglage itératif visant à maximiser les insights sur le problème de réglage (ce que nous appelons la "phase d'exploration"). L'optimisation bayésienne et les outils similaires sont plus adaptés à la phase d'exploitation. La recherche quasi-aléatoire basée sur des séquences à faible écart décalé de manière aléatoire peut être considérée comme une "recherche irrégulière et aléatoire", car elle explore de façon uniforme, mais aléatoire, un espace de recherche donné et étend les points de recherche plus qu'une recherche aléatoire.

Les avantages de la recherche quasi-aléatoire par rapport aux outils d'optimisation par boîte noire plus sophistiqués (par exemple, optimisation bayésienne, algorithmes évolutifs) incluent:

• L'échantillonnage non adaptatif de l'espace de recherche permet de modifier l'objectif du réglage dans l'analyse post-hoc sans réexécuter les tests. Par exemple, nous voulons généralement trouver le meilleur essai en termes d'erreurs de validation réalisées à tout moment de l'entraînement. Cependant, la nature non adaptative de la recherche quasi-aléatoire permet de trouver le meilleur essai en fonction de l'erreur de validation finale, de l'erreur d'entraînement ou d'une autre métrique d'évaluation sans réexécuter aucun test.
• La recherche quasi-aléatoire se comporte de manière cohérente et statistiquement reproductible. Il devrait être possible de reproduire une étude datant de six mois, même en cas de modification de la mise en œuvre de l'algorithme de recherche, à condition qu'il conserve les mêmes propriétés d'uniformité. Si vous utilisez un logiciel d'optimisation bayésien sophistiqué, l'implémentation peut varier considérablement d'une version à l'autre, ce qui rend la reproduction d'une ancienne recherche beaucoup plus difficile. Il n'est pas toujours possible de revenir à une ancienne implémentation (par exemple, si l'outil d'optimisation est exécuté en tant que service).
• Son exploration uniforme de l'espace de recherche facilite l'explication des résultats et de ce qu'ils pourraient suggérer à propos de l'espace de recherche. Par exemple, si le meilleur point du balayage d'une recherche quasi-aléatoire se trouve à la limite de l'espace de recherche, c'est un bon signal (mais pas infaillible) indiquant que les limites de l'espace de recherche doivent être modifiées. Toutefois, un algorithme d'optimisation adaptative par boîte noire a peut-être négligé le milieu de l'espace de recherche en raison de premiers essais malchanceux, même s'il s'avère qu'il contient des points tout aussi bons, car c'est ce type de non-uniformité qu'un bon algorithme d'optimisation doit employer pour accélérer la recherche.
• L'exécution de nombres d'essais différents en parallèle ou de manière séquentielle ne produit pas de résultats statistiquement différents lorsque vous utilisez la recherche quasi-aléatoire (ou d'autres algorithmes de recherche non adaptatifs), contrairement aux algorithmes adaptatifs.
• Les algorithmes de recherche plus sophistiqués ne gèrent pas toujours correctement les points impossibles à atteindre, en particulier s'ils ne sont pas conçus en tenant compte du réglage des hyperparamètres des réseaux de neurones.
• La recherche quasi-aléatoire est simple et fonctionne particulièrement bien lorsque de nombreux essais de réglage s'exécutent en parallèle. D'un point de vue anecdotique¹, il est très difficile pour un algorithme adaptatif de surpasser une recherche quasi-aléatoire dont le budget est multiplié par deux, en particulier lorsque de nombreux essais doivent être exécutés en parallèle (et que les chances d'utiliser les résultats d'essais précédents sont donc très faibles lors du lancement de nouveaux essais). Sans expérience de l'optimisation bayésienne et d'autres méthodes avancées d'optimisation par boîte noire, vous risquez de ne pas profiter des avantages qu'elles offrent en principe. Il est difficile de comparer les algorithmes avancés d'optimisation par boîte noire dans des conditions réalistes de réglage du deep learning. Il s'agit d'un domaine très actif de la recherche actuelle, et les algorithmes plus sophistiqués présentent leurs propres pièges pour les utilisateurs inexpérimentés. Les experts de ces méthodes peuvent obtenir de bons résultats, mais dans des conditions de parallélisme élevé, l'espace de recherche et le budget ont tendance à être beaucoup plus importants.

Cela dit, si vos ressources de calcul ne permettent qu'un petit nombre d'essais à s'exécuter en parallèle et que vous pouvez vous permettre d'exécuter de nombreux essais à la suite, l'optimisation bayésienne devient beaucoup plus attrayante, bien que les résultats de vos réglages soient plus difficiles à interpréter.

Où puis-je trouver une implémentation de la recherche quasi-aléatoire ?

Open-Source Vizier dispose d'une implémentation de la recherche quasi-aléatoire. Définissez algorithm="QUASI_RANDOM_SEARCH" dans cet exemple d'utilisation de Vizier. Il existe une autre implémentation dans cet exemple de balayages d'hyperparamètres. Ces deux implémentations génèrent une séquence Halton pour un espace de recherche donné (destinées à implémenter une séquence Halton décalée et brouillée, comme recommandé dans Hyper-Parameters critiques: No Random, No Cry).

Si un algorithme de recherche quasi-aléatoire basé sur une séquence à faible écart n'est pas disponible, il est possible de remplacer la recherche uniforme pseudo-aléatoire, bien que cela soit probablement un peu moins efficace. Pour les dimensions 1 ou 2, la recherche par quadrillage est également acceptable, mais pas dans les dimensions supérieures. (voir Bergstra et Bengio, 2012).

Combien d'essais sont nécessaires pour obtenir de bons résultats avec une recherche quasi-aléatoire ?

Il n'existe aucun moyen de déterminer le nombre d'essais nécessaires pour obtenir des résultats avec une recherche quasi-aléatoire en général, mais vous pouvez examiner des exemples spécifiques. Comme le montre la figure 3, le nombre d'essais d'une étude peut avoir un impact important sur les résultats:

Figure 3:ResNet-50 affiné sur ImageNet avec 100 essais L'amorçage a permis de simuler différentes quantités de budgets de réglage. Des diagrammes en boîte indiquant les meilleures performances pour chaque budget test sont représentés.

 

Notez les points suivants à propos de la figure 3:

• Les plages interquartiles lorsque six essais ont été échantillonnés sont beaucoup plus importants que lors de l'échantillonnage de 20 essais.
• Même avec 20 essais, la différence entre les études particulièrement chanceuses et les études malchanceuses est probablement plus importante que la variation typique entre les réentraînements de ce modèle sur différentes sources aléatoires, avec des hyperparamètres fixes, qui pour cette charge de travail pourrait se situer autour de +/- 0,1% sur un taux d'erreur de validation d'environ 23%.

---

1. Ben Recht et Kevin Jamieson ont souligné à quel point la recherche aléatoire à double budget constitue une base de référence (l'article sur Hyperband fournit des arguments similaires). Toutefois, il est certainement possible de trouver des espaces de recherche et des problèmes où des techniques d'optimisation bayésiennes de pointe brisent une recherche aléatoire dont le budget est deux fois supérieur. Toutefois, d'après notre expérience, il est beaucoup plus difficile de battre la recherche aléatoire à deux budgets dans le régime du haut parallélisme, car l'optimisation bayésienne n'a aucune possibilité d'observer les résultats des essais précédents. ↩