Qu'est-ce que la complexité d'échantillon ?

La complexité d'échantillon est un concept en apprentissage automatique qui détermine le nombre d'échantillons de données requis pour atteindre un certain niveau de performance. Son importance tient à sa capacité à évaluer l'efficacité d'un algorithme d'apprentissage. Un algorithme plus efficace a besoin de moins d'échantillons pour apprendre correctement, ce qui réduit les ressources nécessaires à l'acquisition et au stockage des données.

Comprendre la complexité d'échantillon

La complexité d'échantillon exprime la quantité de données dont un algorithme a besoin pour atteindre un objectif d'apprentissage précis. Elle sous-tend la question : « De combien de données ai-je besoin ? ». Cette valeur varie fortement selon la complexité du problème, la variabilité des données et la précision attendue des résultats.

On distingue souvent deux formes de complexité d'échantillon : le pire cas et le cas moyen. La complexité d'échantillon au pire cas correspond au nombre maximal d'échantillons nécessaires pour atteindre un objectif d'apprentissage, quelle que soit la distribution des données. La complexité d'échantillon en cas moyen considère, elle, le nombre moyen d'échantillons requis en supposant que les données suivent une distribution donnée.

Pourquoi les data scientists et les ingénieurs en apprentissage automatique s'y intéressent-ils ? Comprendre la complexité d'échantillon aide à s'assurer de disposer d'assez de données pour que les modèles apprennent efficacement. Elle entre en jeu lors de la collecte des données, du choix de l'algorithme d'apprentissage et de l'évaluation des performances des modèles.

Explication technique de la complexité d'échantillon

Pour aller plus loin, il faut introduire quelques notions de théorie de l'apprentissage statistique, qui constituent l'ossature mathématique de la complexité d'échantillon.

L'une des notions clés est la dimension VC (Vapnik–Chervonenkis), qui mesure la capacité ou la complexité d'un modèle. Elle fixe une limite quantifiable au « mémorisation » qu'un modèle peut effectuer et est étroitement liée à sa capacité de généralisation à des données inédites. Une dimension VC élevée indique un modèle plus complexe, qui a généralement besoin d'un échantillon plus large pour apprendre efficacement sans surapprentissage.

La théorie PAC (Probably Approximately Correct) fournit un cadre reliant la dimension VC à la complexité d'échantillon. L'apprentissage PAC cherche à identifier la taille minimale d'échantillon qui permettra, avec une forte probabilité, de produire une hypothèse dont l'erreur est dans une tolérance spécifiée par rapport à la meilleure hypothèse possible. En termes simples, il s'agit de déterminer le nombre d'échantillons nécessaires pour apprendre un modèle « probablement » (avec une forte confiance) « à peu près correct » (dans une certaine marge d'erreur).

La borne PAC s'écrit :

N >= (1/ε) * (ln|H| + ln(1/δ))

où :

• N est la taille de l'échantillon,
• ε est l'erreur maximale acceptable (la partie « à peu près correct »),
• |H| est la taille de l'espace d'hypothèses (liée à la dimension VC),
• δ est la probabilité d'échec acceptable (la partie « probablement »).

Cette formule montre que la complexité d'échantillon (N) augmente avec la complexité du modèle (mesurée par |H| ou la dimension VC) et la précision exigée (plus ε est petit), et diminue si l'on accepte une plus forte probabilité d'échec (plus δ est grand).

Un autre concept lié à la complexité d'échantillon est l'erreur de généralisation, qui quantifie l'écart entre les performances du modèle sur les données d'entraînement et ses performances attendues sur des données inédites. Un modèle avec une forte erreur de généralisation présente souvent une complexité d'échantillon élevée, car il lui faut plus de données pour « apprendre » efficacement.

En résumé, la complexité d'échantillon est intrinsèquement liée à la complexité du modèle (dimension VC), à la marge d'erreur acceptable (ε), à la probabilité d'échec (δ) et à l'erreur de généralisation. Ces notions interconnectées fondent notre compréhension de la complexité d'échantillon en apprentissage automatique.

Complexité d'échantillon selon les types d'apprentissage automatique

La complexité d'échantillon concerne tous les types d'algorithmes d'apprentissage automatique, mais elle s'exprime différemment. Par exemple, en apprentissage supervisé — où les modèles apprennent à partir de données étiquetées — elle peut souvent être réduite en acquérant des échantillons plus divers et représentatifs. À l'inverse, l'apprentissage non supervisé — sans données étiquetées — requiert souvent un volume d'échantillons plus important, faute de guidage pendant l'apprentissage.

L'apprentissage par renforcement traite de problèmes de décision séquentielle : la complexité d'échantillon y dépend donc non seulement du nombre d'échantillons, mais aussi de la qualité et de la variété des situations rencontrées par l'agent. En apprentissage semi-supervisé, qui combine données étiquetées et non étiquetées, la complexité d'échantillon est souvent influencée par le ratio entre ces deux types de données.

Exemples d'applications concrètes de la gestion de la complexité d'échantillon

Prenons une entreprise comme Netflix, qui utilise l'apprentissage automatique pour recommander des films à ses utilisateurs. Avec un modèle à forte complexité d'échantillon, il faudrait un très grand nombre d'historiques de visionnage pour produire des recommandations précises. À l'inverse, un modèle à faible complexité d'échantillon pourrait générer des recommandations pertinentes avec moins de données, réduisant les coûts de stockage et de traitement.

Autre exemple dans le domaine médical, où la collecte de données est chronophage et coûteuse. Un modèle de diagnostic avec une complexité d'échantillon plus faible demanderait moins de dossiers patients pour poser des diagnostics fiables, ce qui le rend plus applicable en conditions réelles.

Comment estimer la complexité d'échantillon

Estimer la complexité d'échantillon en pratique est délicat et dépend du problème, des données et du modèle choisi. Voici quelques étapes et repères généraux :

1. Comprendre le problème et le modèle. La complexité du problème d'apprentissage et du modèle utilisé joue un rôle central. Un modèle complexe comme un réseau de neurones profond présente une dimension VC élevée et donc une complexité d'échantillon plus importante.
2. Utiliser des méthodes empiriques. Une approche pratique consiste à tester empiriquement. Commencez avec un petit jeu de données et augmentez progressivement sa taille tout en suivant les performances du modèle. Le point à partir duquel des données supplémentaires n'apportent plus de gain significatif indique la taille d'échantillon nécessaire.
3. Exploiter les bornes PAC. Pour une approche plus théorique, utilisez les bornes PAC. Bien que souvent trop lâches en pratique, elles donnent un ordre de grandeur de la taille d'échantillon requise pour atteindre un niveau de performance donné.
4. Tenir compte de la complexité du modèle. La complexité du modèle (p. ex. : nombre de paramètres d'un réseau de neurones, profondeur d'un arbre de décision) est souvent liée à la complexité d'échantillon. Les modèles plus complexes peuvent nécessiter davantage d'échantillons pour éviter le surapprentissage. Des outils comme les courbes d'apprentissage aident à comprendre cette relation.
5. Apprécier la variabilité des données. Une forte variabilité des données exige souvent un échantillon plus important. Par exemple, pour un modèle de reconnaissance d'images avec des visuels très hétérogènes, il faudra généralement plus de données que pour des images plus homogènes.
6. Recourir au bootstrap. Le bootstrap est une technique de rééchantillonnage utile pour estimer la complexité d'échantillon. En créant plusieurs sous-ensembles de vos données et en évaluant les performances du modèle sur chacun, vous obtenez des indications sur la quantité de données nécessaire pour un apprentissage efficace.
7. Utiliser des outils et des bibliothèques. Des bibliothèques comme scikit-learn en Python offrent des outils pratiques pour estimer la complexité d'échantillon. Par exemple, la fonction learning_curve permet de visualiser l'évolution des performances selon la taille de l'ensemble d'entraînement, offrant ainsi des insights sur la complexité d'échantillon.

Gardez en tête que l'estimation de la complexité d'échantillon est autant un art qu'une science. Elle suppose de trouver le juste équilibre entre les ressources disponibles, la complexité du modèle, la variabilité des données et le niveau de performance requis.

Quels sont les bénéfices de la mesure de la complexité d'échantillon ?

Comprendre la complexité d'échantillon offre plusieurs avantages. Elle permet d'estimer la quantité de données nécessaire à un projet d'apprentissage automatique, en réduisant le risque de sous-apprentissage ou de surapprentissage. Elle aide aussi à allouer efficacement les ressources en évitant des collectes et des stockages de données inutiles. En permettant de comparer clairement l'efficacité d'apprentissage de différents algorithmes, elle oriente le choix de l'algorithme le plus adapté à un problème donné.

Quels sont les défis liés à la complexité d'échantillon ?

Malgré ses atouts, la complexité d'échantillon pose des défis. L'estimer avec précision suppose une compréhension fine du problème, de l'algorithme et des données, ce qui n'est pas toujours le cas. Elle suppose également que « plus de données » rime toujours avec « mieux », ce qui est faux si les données sont bruyantes ou peu pertinentes. En outre, les algorithmes et distributions de données différents impactent fortement la complexité d'échantillon, ce qui en fait une variable délicate à piloter.

Pourquoi les ingénieurs en machine learning considèrent rarement la complexité d'échantillon

À mon sens, la complexité d'échantillon est utile pour la gestion de projet, mais dans la majorité des cas, elle est ignorée par les ingénieurs en apprentissage automatique.

Pourquoi ?

1. Accès à de vastes jeux de données. Avec la disponibilité de grands jeux de données, la complexité d'échantillon préoccupe moins. Les modèles peuvent être entraînés sur des millions, voire des milliards d'exemples pour améliorer leurs performances.
2. Priorité aux performances du modèle. Les ingénieurs visent souvent à maximiser des métriques comme l'exactitude, le score F1, etc. La complexité d'échantillon passe alors au second plan face à la performance brute.
3. Manque de connaissances. Certain·e·s ingénieurs peuvent ne pas maîtriser la théorie sous-jacente à la complexité d'échantillon.
4. Modèles préentraînés de grande taille. Grâce à l'accès ouvert à de grands modèles préentraînés, il n'est plus toujours nécessaire de se soucier de la taille d'échantillon. On peut atteindre l'état de l'art avec quelques centaines d'exemples.

De manière générale, des métriques comme l'exactitude et les capacités du modèle priment sur la complexité d'échantillon. Toutefois, à mesure que les modèles grossissent et que les données se raréfient dans certains domaines, les ingénieurs en ML seront de plus en plus enclins à privilégier l'efficacité en échantillons.

Vous souhaitez en savoir plus sur l'IA et l'apprentissage automatique ? Découvrez :

• Understanding machine learning course
• Introduction to ChatGPT course
• Machine learning cheat sheet
• What is machine learning?