Une introduction douce à la convergence prématurée

Actualités de de l'Intelligence Artificielle - Machine Learning - Objets connectés

Une introduction douce à la convergence prématurée


La convergence fait référence à la limite d’un processus et peut être un outil analytique utile lors de l’évaluation des performances attendues d’un algorithme d’optimisation.

Il peut également être un outil empirique utile lors de l’exploration de la dynamique d’apprentissage d’un algorithme d’optimisation et des algorithmes d’apprentissage automatique entraînés à l’aide d’un algorithme d’optimisation, tels que les réseaux neuronaux d’apprentissage en profondeur. Cela motive l’étude des courbes d’apprentissage et des techniques, telles que l’arrêt précoce.

Si l’optimisation est un processus qui génère des solutions candidates, alors la convergence représente un point stable à la fin du processus où aucun autre changement ou amélioration n’est attendu. Convergence prématurée fait référence à un mode de défaillance pour un algorithme d’optimisation où le processus s’arrête à un point stable qui ne représente pas une solution globalement optimale.

Dans ce tutoriel, vous découvrirez une introduction douce à la convergence prématurée en machine learning.

Après avoir terminé ce tutoriel, vous saurez :

  • La convergence fait référence au point stable trouvé à la fin d’une séquence de solutions via un algorithme d’optimisation itératif.
  • La convergence prématurée fait référence à un point stable trouvé trop tôt, peut-être proche du point de départ de la recherche, et avec une évaluation pire que prévu.
  • La gourmandise d’un algorithme d’optimisation permet de contrôler le taux de convergence d’un algorithme.

Commençons.

Une introduction douce à la convergence prématurée

Une introduction douce à la convergence prématurée
Photo de Don Graham, certains droits réservés.

Présentation du didacticiel

Ce tutoriel est divisé en trois parties ; elles sont:

  1. Convergence dans l’apprentissage automatique
  2. Convergence prématurée
  3. Aborder la convergence prématurée

Convergence dans l’apprentissage automatique

La convergence fait généralement référence aux valeurs d’un processus qui ont une tendance de comportement au fil du temps.

C’est une idée utile lorsque l’on travaille avec des algorithmes d’optimisation.

L’optimisation fait référence à un type de problème qui nécessite de trouver un ensemble d’entrées qui aboutissent à la valeur maximale ou minimale d’une fonction objectif. L’optimisation est un processus itératif qui produit une séquence de solutions candidates jusqu’à arriver finalement à une solution finale à la fin du processus.

Ce comportement ou cette dynamique de l’algorithme d’optimisation arrivant sur une solution finale de point stable est appelé convergence, par exemple la convergence des algorithmes d’optimisation. De cette manière, la convergence définit la fin de l’algorithme d’optimisation.

La descente locale implique de choisir de manière itérative une direction de descente, puis de faire un pas dans cette direction et de répéter ce processus jusqu’à ce que la convergence ou une condition de fin soit remplie.

— Page 13, Algorithmes d’optimisation, 2019.

  • Convergence: condition d’arrêt pour un algorithme d’optimisation où un point stable est situé et où d’autres itérations de l’algorithme sont peu susceptibles d’entraîner une amélioration supplémentaire.

Nous pourrions mesurer et explorer empiriquement la convergence d’un algorithme d’optimisation, par exemple en utilisant des courbes d’apprentissage. De plus, nous pourrions également explorer la convergence d’un algorithme d’optimisation de manière analytique, telle qu’une preuve de convergence ou une complexité de calcul de cas moyen.

Une forte pression de sélection entraîne une convergence rapide, mais peut-être prématurée. Affaiblir la pression de sélection ralentit le processus de recherche…

— Page 78, Calcul évolutif : une approche unifiée, 2002.

L’optimisation et la convergence des algorithmes d’optimisation sont un concept important dans l’apprentissage automatique pour les algorithmes qui s’adaptent (apprennent) à un ensemble de données d’entraînement via un algorithme d’optimisation itératif, tel que la régression logistique et les réseaux de neurones artificiels.

En tant que tel, nous pouvons choisir des algorithmes d’optimisation qui entraînent un meilleur comportement de convergence que d’autres algorithmes, ou passer beaucoup de temps à régler la dynamique de convergence (dynamique d’apprentissage) d’un algorithme d’optimisation via les hyperparamètres de l’optimisation (par exemple le taux d’apprentissage).

Le comportement de convergence peut être comparé, souvent en termes de nombre d’itérations d’un algorithme requis jusqu’à la convergence, à l’évaluation de la fonction objectif du point stable trouvé à la convergence, et aux combinaisons de ces préoccupations.

Convergence prématurée

La convergence prématurée fait référence à la convergence d’un processus qui s’est produit trop tôt.

En optimisation, cela fait référence à l’algorithme convergeant vers un point stable qui a des performances pires que prévu.

La convergence prématurée affecte généralement les tâches d’optimisation complexes où la fonction objectif est non convexe, ce qui signifie que la surface de réponse contient de nombreuses bonnes solutions différentes (points stables), peut-être avec une (ou quelques) meilleures solutions.

Si nous considérons la surface de réponse d’une fonction objectif sous optimisation comme un paysage géométrique et que nous recherchons un minimum de la fonction, alors l’optimisation prématurée fait référence à la recherche d’une vallée proche du point de départ de la recherche qui a moins de profondeur que la vallée la plus profonde dans le domaine problématique.

Pour les problèmes qui présentent des paysages de fitness hautement multimodaux (rugueux) ou des paysages qui changent au fil du temps, une exploitation excessive entraîne généralement une convergence prématurée vers des pics sous-optimaux dans l’espace.

— Page 60, Calcul évolutif : une approche unifiée, 2002.

De cette manière, une convergence prématurée est décrite comme la recherche d’une solution localement optimale au lieu de la solution globalement optimale pour un algorithme d’optimisation. Il s’agit d’un cas particulier de défaillance d’un algorithme d’optimisation.

  • Convergence prématurée: convergence d’un algorithme d’optimisation vers un point stable pire qu’optimal qui est probablement proche du point de départ.

En d’autres termes, la convergence signifie la fin du processus de recherche, par exemple un point stable a été localisé et d’autres itérations de l’algorithme ne sont pas susceptibles d’améliorer la solution. La convergence prématurée fait référence à l’atteinte de cette condition d’arrêt d’un algorithme d’optimisation à un point stationnaire moins que souhaitable.

Aborder la convergence prématurée

La convergence prématurée peut être une préoccupation pertinente pour toute tâche d’optimisation raisonnablement difficile.

Par exemple, une majorité de recherches dans le domaine du calcul évolutif et des algorithmes génétiques consiste à identifier et surmonter la convergence prématurée de l’algorithme sur une tâche d’optimisation.

Si la sélection se concentre sur les individus les plus adaptés, la pression de sélection peut provoquer une convergence prématurée en raison de la diversité réduite des nouvelles populations.

— Page 139, Computational Intelligence: An Introduction, 2e édition, 2007.

Les algorithmes d’optimisation basés sur la population, comme les algorithmes évolutionnaires et l’intelligence en essaim, décrivent souvent leur dynamique en termes d’interaction entre les pressions sélectives et la convergence. Par exemple, de fortes pressions sélectives entraînent une convergence plus rapide et probablement une convergence prématurée. Des pressions sélectives plus faibles peuvent entraîner une convergence plus lente (coût de calcul plus élevé) bien qu’elles permettent peut-être de localiser des optima meilleurs ou même globaux.

Un opérateur avec une pression sélective élevée diminue la diversité de la population plus rapidement que les opérateurs avec une pression sélective faible, ce qui peut conduire à une convergence prématurée vers des solutions sous-optimales. Une pression sélective élevée limite les capacités d’exploration de la population.

— Page 135, Computational Intelligence: An Introduction, 2e édition, 2007.

Cette idée de pression sélective est utile plus généralement pour comprendre la dynamique d’apprentissage des algorithmes d’optimisation. Par exemple, une optimisation configurée pour être trop gourmande (par exemple via des hyperparamètres tels que la taille du pas ou le taux d’apprentissage) peut échouer en raison d’une convergence prématurée, tandis que le même algorithme configuré pour être moins gourmand peut surmonter une convergence prématurée et découvrir un solution meilleure ou globalement optimale.

Une convergence prématurée peut être rencontrée lors de l’utilisation de la descente de gradient stochastique pour former un modèle de réseau neuronal, signifiée par une courbe d’apprentissage qui chute de manière exponentielle puis cesse de s’améliorer.

Le nombre de mises à jour nécessaires pour atteindre la convergence augmente généralement avec la taille de l’ensemble d’apprentissage. Cependant, à mesure que m tend vers l’infini, le modèle finira par converger vers sa meilleure erreur de test possible avant que SGD n’ait échantillonné chaque exemple de l’ensemble d’apprentissage.

— Page 153, Apprentissage en profondeur, 2016.

Le fait que l’ajustement des réseaux de neurones soit soumis à une convergence prématurée motive l’utilisation de méthodes telles que les courbes d’apprentissage pour surveiller et diagnostiquer les problèmes de convergence d’un modèle sur un ensemble de données d’apprentissage, et l’utilisation de la régularisation, telle que l’arrêt précoce, qui arrête le L’algorithme d’optimisation avant de trouver un point stable se fait au détriment des performances sur un ensemble de données en attente.

En tant que tel, de nombreuses recherches sur les réseaux de neurones d’apprentissage en profondeur visent finalement à surmonter une convergence prématurée.

Empiriquement, on constate souvent que les fonctions d’activation « tanh » donnent lieu à une convergence plus rapide des algorithmes d’apprentissage que les fonctions logistiques.

— Page 127, Réseaux de neurones pour la reconnaissance de formes, 1995.

Cela inclut des techniques telles que le travail sur l’initialisation des poids, ce qui est essentiel car les poids initiaux d’un réseau de neurones définissent le point de départ du processus d’optimisation, et une mauvaise initialisation peut conduire à une convergence prématurée.

Le point initial peut déterminer si l’algorithme converge du tout, certains points initiaux étant si instables que l’algorithme rencontre des difficultés numériques et échoue complètement.

— Page 301, Apprentissage en profondeur, 2016.

Cela inclut également le grand nombre de variations et d’extensions de l’algorithme d’optimisation de la descente de gradient stochastique, telles que l’ajout de quantité de mouvement afin que l’algorithme ne dépasse pas les optima (point stable), et Adam qui ajoute un hyperparamètre de taille de pas automatiquement adapté (apprentissage rate) pour chaque paramètre en cours d’optimisation, accélérant considérablement la convergence.

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous cherchez à approfondir.

Tutoriels

Livres

Des articles

Résumé

Dans ce didacticiel, vous avez découvert une introduction douce à la convergence prématurée en apprentissage automatique.

Concrètement, vous avez appris :

  • La convergence fait référence au point stable trouvé à la fin d’une séquence de solutions via un algorithme d’optimisation itératif.
  • La convergence prématurée fait référence à un point stable trouvé trop tôt, peut-être proche du point de départ de la recherche, et avec une évaluation pire que prévu.
  • La gourmandise d’un algorithme d’optimisation permet de contrôler le taux de convergence d’un algorithme.

Avez-vous des questions?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.