2 Introduction Générale

Marvin Minsky, scientifique américain du MIT et l’un des plus grand chercheurs
dans le domaine des sciences Chapitre
cognitives et de4:
l’intelligence artificielle, écrivait en
Random
1991 à propos de l’apprentissage Forest
automatique 1 :

"Pour résoudre des problèmes vraiment difficiles, nous aurons

besoin d’utiliser plusieurs représentations différentes... il est temps
d’arrêter d’argumenter sur quel type de technique de classification
est la meilleure... Nous devrions plutôt travailler à un plus haut
niveau d’organisation et découvrir comment construire des systèmes
managériaux pour exploiter les différents avantages et contourner les
différentes limitations de chacune de ces techniques."
M.L. Minsky: Logical versus analogical or symbolic versus connectionist
or neat versus scruffy. AI Magazine, vol. 12, no. 2, pages 34–51, 1991.
Ce que Minsky a exprimé il y a maintenant presque une vingtaine d’années,
Multiple Classifier Systems: combiner plusieurs experts pour former un comité,
domaine qui exige de formaliser, analyser, comprendre.

ü Aujourd’hui, force est de constater que ce qu’on appelle maintenant systèmes multi-classifieurs (MCS pour
Multiple Classifier Systems) constitue une des voies les plus prometteuses de l’apprentissage automatique.

ü Les Ensemble de Classifieurs (EoC), une des approches MCS les plus populaires et les plus efficaces: consiste à
combiner un ensemble de classifieurs de même type (par exemple un ensemble de réseaux de neurones, un
ensemble d’arbres de décision, ou un ensemble de discriminants),

ü Un grand nombre de méthodes capables de générer automatiquement des ensembles de classifieurs : Bagging,
Boosting, Random Subspaces sont autant de méthodes différentes dont l’objectif commun est de créer la diversité
au sein d’un ensemble de classifieurs performants tout en cherchant à établir le meilleur consensus possible entre
ces classifieurs.

ü Cependant, la diversité dans les ensembles est encore à ce jour très sommaire et les procédés pour parvenir à
produire cette diversité tant désirée encore assez mal maitrisés.
Ensembles de Classifieurs (EoC):
Les architectures que l’on peut u3liser pour la concep3on d’un système mul3-classifieurs:
v Combinaisons parallèle, série ou hybride.
v la combinaison parallèle:
v l’idée de faire par3ciper à une même décision plusieurs experts, d’égale importance.
v Chacun donne son avis pour la prédic3on d’une donnée,
v tous ces avis sont pris en compte dans la décision finale, le plus souvent à l’aide d’un vote.
Ensembles de Classifieurs (EoC):
Les architectures que l’on peut u3liser pour la concep3on d’un système mul3-classifieurs:
v Combinaisons parallèle, série ou hybride.
v la combinaison parallèle:
v l’idée de faire par3ciper à une même décision plusieurs experts, d’égale importance.
v Chacun donne son avis pour la prédic3on d’une donnée,
v tous ces avis sont pris en compte dans la décision finale, le plus souvent à l’aide d’un vote.
v Catégorisa3on des méthodes en fonc3on du type de classifieurs qui composent le comité.
v les comités de classifieurs de types différents, comme ceux qui combinent des réseaux de
neurones, des arbres de décision et des k-plus proches voisins dans un même comité par exemple,
v aux ensembles composés de classifieurs de même type, comme les ensembles d’arbres de
décision.
Ensembles de Classifieurs (EoC):
Les architectures que l’on peut u3liser pour la concep3on d’un système mul3-classifieurs:
v Combinaisons parallèle, série ou hybride.
v la combinaison parallèle:
v l’idée de faire par3ciper à une même décision plusieurs experts, d’égale importance.
v Chacun donne son avis pour la prédic3on d’une donnée,
v tous ces avis sont pris en compte dans la décision finale, le plus souvent à l’aide d’un vote.
v Catégorisa3on des méthodes en fonc3on du type de classifieurs qui composent le comité.
v les comités de classifieurs de types différents, comme ceux qui combinent des réseaux de
neurones, des arbres de décision et des k-plus proches voisins dans un même comité par exemple,
v aux ensembles composés de classifieurs de même type, comme les ensembles d’arbres de
décision.
v Dans la catégorie des EoC, puisque les classifieurs sont de même type: important de générer des
"différences" entre chacun d’eux. Avoir un comité de classifieurs qui fournissent tous exactement les mêmes
prédic3ons n’a pas réellement de sens.

v Catégoriser les méthodes d’induc3on d’EoC en fonc3on de la façon dont elles génèrent ces différences (on
parlera alors de diversité́) au sein du comité.
 En résumé
Pour créer des EoC (Combining Pagern Classifiers ([Kuncheva 2004]), on peut distinguer quatre
principales stratégies, non exclusives,
Ø Manipuler la distribution des données d’apprentissage (ex: Bagging et de Boos3ng) .
Ø Manipuler les espaces de description (ex: Random Subspaces ([Ho 1998]) les sous-espaces
sont sélec3onnés aléatoirement.
Ø Manipuler les paramètres de l’algorithme d’apprentissage(ex. un ensemble de réseaux
de neurones, on ini3alise souvent les poids de ces réseaux de façon aléatoire
Random Forest:Forêts Aléatoires
Ø Les méthodes de forêts aléatoires sont basées sur la combinaison de
classifieurs élémentaires de types arbres de décision.
Ø U:liser des arbres de décision comme classifieurs élémentaires et faire
intervenir l’aléatoire dans leur induc:on ont conduit à l’introduc:on du
formalisme des forêts aléatoires dans le but de générer de la diversité́ dans
l’ensemble.
Ø Sa mise en œuvre nécessite notamment de fixer la valeur de deux paramètres
principaux :
Ø le nombre de caractéris:ques choisies aléatoirement pour chaque
nœud des arbres
Ø le nombre d’arbres aléatoires à induire dans la forêt.
Random Forest: ( Leo Breiman in 2001), Random Forest
Random Forest
Random Forest
ü Instead of using a single large tree construct an ensemble of simpler trees
Decision Trees and Random Forests
Random
ü A Random Forest (RF) is a classifier consis3ng
Decision Trees andForest:
of Random
a collec3on Example
of decision trees
Forests
ü The predic3on is obtained by a majority vo3ng over the predic3on of the single trees
Random Forest :
• Random forests, a type of machine
learning algorithm, are composed
of hundreds of decision trees
consisting of
• randomly selected predicting
variables and
• randomly selected subsamples
• Each single tree makes a
prediction, and
• the final average is obtained by
taking the average of each tree
Idea: randomly sample from a training dataset with replacement

v Supposons que l’on dispose d’un ensemble T = {x1, x2, x3..., xN } de N données
observées de notre popula:on, et que l’on s’intéresse à un sta:s:que notée S(T).

Le bootstrap
v 1.4. va consister
Principes d’induction
à former L échan:llons
d’ensembles de
T k = (x∗ , x∗ , x∗ , ..., x∗ ) pour
∗
classifieurs1 2 3 Nʹ 19
k = 1, .., L, où chaque T ∗ est cons:tué par :rage alétoire avec remise de Nʹ
k

données dans T.

Fig. 1.7: Illustration d’un tirage aléatoire avec remise pour la formation d’un échantillon
 bootstrap Fig. 1.7: Illustration d’un tirage aléatoire avec remise pour la formation d’un échantillon
bootstrap

de la statistique, ou encore son erreur standard pour en mesurer delala dispersion

statistique, ou encore son erreur standard pour en mesurer la dispersion (cf.
(cf.
équation 1.2).
équation 1.2).
L
!
Sboot = S(Tk∗)/L (1.1)
L
! k=1
Sboot = S(Tk∗ )/L (1.1) #$
L ∗ 2
k=1 (S(Tk ) − Sboot )
k=1 se" boot = (1.2)
(L − 1)
#$
L ∗ À partir de ce principe de rééchantillonnage, Breiman en 1996 introduit la mé-
2
k=1 (S(Tk ) − Sboot )
thode de Bagging ([Breiman 1996]). Il s’agit simplement de considérer que la sta-
se
" boot = (1.2)
tistique que l’on cherche à étudier est un algorithme d’apprentissage noté h(x) et
(L − 1)
•Idea: randomly sample from a training dataset with d’appliquer alors le principe de bootstrap tel que nous venons de l’expliquer. Ainsi
replacement À partir de ce principe de rééchantillonnage, Breiman en 1996chaque classifieur élémentaire hk (x) de l’ensemble sera entrainé sur un des L échan-
introduit la mé-
tillons bootstrap de sorte qu’ils soient tous entrainés sur un ensemble d’apprentissage
thode de Bagging ([Breiman 1996]). Il s’agit simplement de considérer
différent. Laque laillustre
figure 1.8 sta-le procédé de Bagging appliqué à un ensemble d’arbres
de décision.
tistique que l’on cherche à étudier est un algorithme d’apprentissage noté h(x) et
d’appliquer alors le principe de bootstrap tel que nous venons de l’expliquer.
T{x1, x2, ..., xNAinsi
}

chaque classifieur élémentaire hk (x) de l’ensemble sera entrainé sur un des L échan- Bagging
•On peut alors calculer S(Tk∗) pour chaquetillons bootstrap de sorte qu’ils soient tous entrainés sur un ensemble d’apprentissage
– Tirage aléatoire avec remise de
N ′ données de T.
échantillon bootstrap, et obtenir ainsi L différent. La figure 1.8 illustre le procédé de Bagging appliqué à un ensembleT1 d’arbres T2 TL – Les Tk pour k = 1..L, sont les
échantillons bootstrap.
estimations de notre statistique. de décision. – Le classifieur hk est entrainé
avec Tk .

•On peut alors calculer la moyenne empirique à – Aggrégation des L classifieurs

résultants pour la prise de
partir de toutes ces valeurs qui nous donnera T {x1, x2, ..., xN } h(x) = y
décision.

alors une estimation plus précise Bagging i

– Tirage aléatoire avec remise de

N ′ données de T . Fig. 1.8: Illustration du principe de Bagging pour un ensemble d’arbres de décision

T1 T2 TL – Les Tk pour k = 1..L, sont les

échantillons bootstrap.
– Le classifieur hk est entrainé
avec Tk .
 Bootstrap Aggregation
v Decisions trees are very sensi:ve to Bagging : Bootstrap Aggrega:on
the data they are trained on: small (Bagging)
changes to the training set can
result in significantly different tree
structures.

v Random forest : takes advantage of

this by allowing each individual tree
to randomly sample with
replacement from the dataset,
resul:ng in different training sets
producing different trees. This
process is known as bagging

Bagging (Bootstrap Aggregation):

❑ Decisions trees are very sensitive to the data they are trained on: small
 The Random Forest
The Random Algorithm
Forest Algorithm
Random
The Forests
Random Forest Algorithm
Algorithm
For b = 1 to B:
• Draw a bootstrap sample Z∗ of size N from the training data.
• Grow a random-forest tree to the bootstrapped data, by recursively repeating the
following steps for each terminal node of the tree, until the minimum node size nmin is reached.
i. Select m variables at random from the p variables.
ii. Pick the best variable/split-point among the m.
iii. Split the node into two daughter nodes.
Output the ensemble of trees

To make a prediction at a new point x we do:

For regression: average the results

For classification: majority vote

3 3
v Appliquer le principe du bagging : créer de
nombreux sous-échantillons aléatoires de notre
ensemble de données avec possibilité de
sélectionner la même valeur plusieurs fois.
v Des arbres de décision individuels sont ensuite
construits pour chaque échantillon. Chaque arbre
est entraîné sur une portion aléatoire afin de
recréer une prédiction.
v Idée: la combinaison de ces modèles
indépendants permet de réduire la variance du
modèle d'ensemble : corriger l’instabilité des
arbres de décisionl.
v chaque arbre va prédire un résultat (target).
v Le résultat avec le plus de votes ( le plus
fréquent) devient le résultat final de notre
modèle.
v Dans le cas de régression, on prendra la moyenne
des votes de tous les arbres.
Why Random Forest works

MSE = Variance + Bias2

vBiais bagging = biais du modèle sous-jacent.

vBagging réduit avant tout la variance.
vIl faut que les modèles sous-jacents aient un biais faible, capturant la
complexité des relations entre les variables (grande profondeur)
vBagging ne sait pas tirer parti des apprenants faibles (weak classifier – cf.
boosting). Il faut que les modèles sous-jacents soient de bonne qualité.
vAugmenter B n’aboutit pas au sur-apprentissage (overfitting). En pratique,
une centaine suffit, mais on peut l’ajuster à l’étude.
Avantages
ü Bonnes performances en prediction
ü Paramétrage simple (B et m)
ü Pas de problème d’overfitting (on peut augmenter B)
ü Mesure de l’importance des variables
ü Possibilité de programmation parallèle
Problems
v Problème si nombre de variables pertinentes très faibles, dans l’absolu et relativement au nombre total
des variables ?

v Le nombre d’ensembles bootstrap qu’il faut générer dans un Bagging pour parvenir à créer un
ensemble le plus performant possible, n’est pas un problème résolu aujourd’hui ?

v Règlage des hyperparamètres et de la compréhension de leurs effets sur le comportement des forêts
aléatoires dont il est question dans ce manuscrit ?
Merci pour votre attention