La forêt aléatoire est une méthode d'apprentissage ensembliste utilisée pour la classification, la régression et d'autres tâches. Elle construit un grand nombre d'arbres de décision pendant l'entraînement et combine leurs sorties : pour la classification, elle renvoie la classe sélectionnée par la majorité des arbres ; pour la régression, elle fait la moyenne des prédictions des arbres individuels. La méthode corrige la tendance des arbres de décision profonds à surapprendre leur ensemble d'entraînement, réduisant la variance tout en maintenant un biais faible.
Le premier algorithme de forêt aléatoire a été développé en 1995 par Tin Kam Ho, basé sur la méthode du sous-espace aléatoire, qui implémente l'approche de discrimination stochastique proposée par Eugene Kleinberg. Leo Breiman et Adele Cutler ont ensuite étendu l'approche en combinant le bagging avec la sélection aléatoire de caractéristiques, et ils ont enregistré « Random Forests » comme marque déposée en 2006 ; depuis 2019, la marque appartient à Minitab, Inc.
Contexte : Arbres de décision et leurs limites
Les arbres de décision sont une méthode largement utilisée en apprentissage automatique. Ils partitionnent l'espace des caractéristiques par une série de divisions binaires, ce qui les rend évolutifs et faciles à interpréter. Cependant, les arbres profonds tendent à apprendre des motifs très irréguliers, conduisant à un biais faible mais à une variance très élevée. En pratique, les arbres entraînés sur un ensemble de données particulier peuvent changer radicalement si quelques points d'entraînement sont modifiés, et leurs prédictions sont souvent précises uniquement pour les données d'entraînement. Ils sont rarement précis sur des données non vues, comme l'ont noté Trevor Hastie et ses collègues. Les forêts aléatoires répondent à cela en faisant la moyenne de nombreux arbres profonds, chacun entraîné sur différents sous-ensembles de données, pour réduire considérablement la variance.
La difficulté avec les méthodes d'arbre est que faire croître trop d'arbres sur les mêmes données produit des prédictions corrélées. Pour décorréler les arbres, les forêts aléatoires utilisent le bootstrap et la sélection aléatoire de caractéristiques, ce qui rend les arbres individuels divers mais forts.
Histoire et développement
L'idée générale des forêts de décision aléatoires apparaît dans les travaux de 1993 de Salzberg et Heath, qui ont proposé d'utiliser un algorithme d'arbre de décision randomisé pour générer plusieurs arbres et les combiner par vote majoritaire. En 1995, Tin Kam Ho a étendu cette idée, montrant que les forêts d'arbres qui se divisent sur des hyperplans obliques peuvent gagner en précision en grandissant sans souffrir de surapprentissage, à condition que les forêts soient restreintes aléatoirement à un sous-ensemble de dimensions de caractéristiques. La méthode de Ho, appelée méthode du sous-espace aléatoire, construisait des arbres en projetant les données d'entraînement dans des sous-espaces de caractéristiques sélectionnés aléatoirement. Cette approche a été une étape clé dans le développement des forêts aléatoires.
Des travaux ultérieurs d'Amit et Geman ont indépendamment introduit l'idée de rechercher un sous-ensemble aléatoire de décisions disponibles à chaque division, bien qu'ils l'aient appliquée à un seul arbre. Indépendamment, Thomas Dietterich a introduit l'idée d'optimisation de nœud randomisée, dans laquelle l'attribut choisi à chaque nœud est sélectionné par une procédure aléatoire plutôt que par un critère d'optimalité déterministe. Ces idées, combinées aux travaux antérieurs de Leo Breiman sur le bagging, ont conduit à la formulation moderne des forêts aléatoires. L'article influent de Breiman de 2001, l'un des plus cités en apprentissage automatique, a combiné ces objectifs et a fourni une borne théorique sur l'erreur de généralisation basée sur la force et la corrélation des arbres dans la forêt.
L'article de Breiman a également établi des outils pratiques : l'erreur hors-bag pour estimer l'erreur de généralisation sans ensemble de validation séparé, et l'importance des variables basée sur la permutation, qui mesure comment la performance se dégrade lorsque les valeurs d'une caractéristique sont mélangées aléatoirement. Ces éléments restent des aspects centraux des forêts aléatoires aujourd'hui.
Bagging et apprentissage ensembliste
La technique de base dans l'entraînement des forêts aléatoires est l'agrégation bootstrap, ou bagging. Étant donné un ensemble d'entraînement avec des caractéristiques X et des réponses Y, l'algorithme échantillonne B fois avec remplacement à partir des données d'entraînement, créant à chaque fois un nouvel ensemble de données de même taille. Un arbre de décision, généralement cultivé profond et non élagué, est ajusté à chaque échantillon bootstrap. Après l'entraînement, les prédictions pour un nouveau point sont faites en faisant la moyenne pour la régression ou en prenant le vote majoritaire pour la classification. Ce méta-algorithme diminue la variance globale sans augmenter le biais, car la moyenne de nombreux arbres non corrélés est plus stable que n'importe quel arbre individuel.
L'échantillonnage bootstrap décorrèle les arbres en leur montrant différents ensembles d'entraînement. Si tous les arbres étaient entraînés sur les mêmes données originales, ils seraient très similaires et sujets aux mêmes erreurs. En utilisant le bootstrap, chaque arbre capture des variations aléatoires. Le modèle gagne en réduction de variance à mesure que B augmente, mais après quelques centaines d'arbres, l'amélioration marginale diminue. En pratique, B est souvent fixé à 500 ou 1000 arbres, bien que les implémentations modernes s'arrêtent automatiquement lorsque l'erreur hors-bag se stabilise.
Un aspect critique des forêts aléatoires est que chaque arbre est généralement entraîné sur un ensemble de données différent en raison de l'échantillonnage avec remplacement : environ deux tiers des observations apparaissent au moins une fois dans chaque échantillon bootstrap, tandis que le tiers restant est hors-bag. Les prédictions hors-bag peuvent être utilisées pour estimer l'erreur de généralisation, sans avoir besoin d'un ensemble de validation dédié, mais basées sur la prédiction agrégée pour chaque observation en utilisant les arbres pour lesquels cette observation n'était pas incluse dans les données d'entraînement.
Sélection aléatoire de caractéristiques
L'innovation clé dans les forêts aléatoires est la sélection aléatoire des caractéristiques à chaque division de nœud. Les arbres de décision traditionnels optimisés choisissent, à chaque nœud, la division parmi toutes les caractéristiques qui réduit le mieux l'impureté, par exemple, l'impureté de Gini pour la classification ou l'erreur quadratique en régression. Dans les forêts aléatoires, cependant, chaque division ne considère qu'un sous-ensemble de caractéristiques choisi aléatoirement, souvent de taille environ la racine carrée du nombre total de caractéristiques. Cela force les arbres à être structurés différemment et réduit la corrélation entre eux. Parfois, des divisions alternatives sont choisies parce que certaines caractéristiques globales pourraient dominer toutes les autres, conduisant à de nombreux arbres presque identiques. En restreignant aléatoirement les caractéristiques candidates, la forêt peut explorer des permutations qui autrement pourraient être négligées, obtenant une prédiction plus robuste.
Cette approche de sous-espace aléatoire a été introduite par Ho et ensuite combinée avec la randomisation de nœud d'Amit et Geman. La formulation finale de Breiman utilisait une sélection de sous-ensemble aléatoire à chaque nœud, mais certaines variantes utilisent une sélection aléatoire uniquement avant d'ajuster chaque arbre. Les implémentations modernes diffèrent ; de nombreuses bibliothèques supportent soit la stratégie de « sous-espace aléatoire » soit la stratégie de « division aléatoire ». Communément, la dimension de caractéristiques d est utilisée, avec un sous-ensemble de taille sqrt(d) pour la classification ou d/3 pour la régression.
Comportement du modèle et résistance au surapprentissage
Les forêts aléatoires sont connues pour leur résistance au surapprentissage. Chaque arbre est profond et peut surapprendre, mais l'ensemble réduit la variance. Les forêts plus profondes tendent à mieux performer à mesure que plus d'arbres sont ajoutés, tant que la randomisation des caractéristiques les restreint. Cela est soutenu par les résultats théoriques de l'article de Breiman, qui montre une borne sur l'erreur de généralisation qui se resserre avec une meilleure force des arbres et une corrélation plus faible. Cependant, si le nombre d'arbres est trop grand, le modèle n'est pas surappris ; l'erreur est approchable à mesure que B augmente, mais elle peut toujours être sensible au bruit dans les étiquettes. Si les caractéristiques ne sont pas sélectionnées aléatoirement, les arbres peuvent être corrélés et annuler l'avantage. Avec une sélection aléatoire de caractéristiques, la forêt tend à maintenir sa précision même lorsque la complexité du classifieur augmente. Cela contraste avec l'augmentation de la profondeur d'un seul arbre, qui conduit au surapprentissage.
Pour la classification, la sortie de la forêt est la classe avec le plus de votes. Pour la régression, la prédiction est la moyenne des arbres individuels, et l'écart type des prédictions des arbres est une estimation naturelle de l'incertitude.
Utilisations pratiques et extensions
Les forêts aléatoires sont appliquées dans de nombreux domaines, y compris la télédétection, la bioinformatique, la finance et la vision par ordinateur. Elles sont robustes aux caractéristiques non pertinentes, peuvent gérer les non-linéarités et produisent une certaine compréhensibilité, mais elles sont moins interprétables qu'un seul arbre. Les métriques d'importance des variables permettent aux chercheurs d'identifier quelles caractéristiques sont pertinentes. Les forêts aléatoires sont également utilisées en intelligence artificielle, et sont un algorithme fondamental dans les opérations traditionnelles comme référence pour de nombreuses tâches modernes d'apprentissage automatique, aux côtés de apprentissage profond et réseau de neurones.
Les extensions incluent les arbres extrêmement randomisés - avec des seuils de division encore plus aléatoires - et l'utilisation de forêts aléatoires pour la détection d'anomalies, le classement et l'imputation de valeurs manquantes. Elles sont également utilisées comme éléments de base du bagging et de l'apprentissage ensembliste dans les pipelines de apprentissage automatique.
Comparaison avec d'autres modèles
Les forêts aléatoires diffèrent des modèles basés sur apprentissage profond tels que réseau de neurones en ce qu'elles sont interprétables, nécessitent moins de données et sont plus simples. Elles peuvent être entraînées sur CPU tandis que les réseaux de neurones profonds nécessitent souvent des accélérateurs. Mais elles peuvent avoir du mal avec les données de haute dimension, tout en pouvant équilibrer entre biais et erreur. Elles sont moins efficaces pour les données non structurées comme les images et le texte, où apprentissage profond excelle. Le compromis est notable : les forêts aléatoires restent une référence solide, mais manquent d'apprentissage de représentation hiérarchique.
À la frontière de la recherche moderne en intelligence artificielle, des méthodes comme grand modèle de langage et les architectures basées sur transformeur dominent les tâches linguistiques, mais les forêts aléatoires et autres ensembles d'arbres sont encore courants dans des domaines comme les données tabulaires et l'IA explicable.
Voir aussi
- apprentissage automatique
- intelligence artificielle
- arbre de décision non disponible dans les liens du système.
Références
Les sources originales sont citées dans l'article, mais aucune URL externe n'est pertinente.