Chronologie d’une discipline passionante

add1

Construire une chronologie de cette discipline qu’est la statistique et la modélisation est particulièrement compliquée. Si l’on voudrait être exhaustif, il faudrait si prendre selon les trois axes suivants:

  • Les praticiens qui ont prouvé l’apport des outils statistiques dans l’évolution du monde d’aujourd’hui ;
  • Les théoriciens de la probabilité et de la statistique dont les travaux ont élaboré les outils tel qu’on les connaît ;
  • De manière plus global, les mathématiciens dont l’agrégat des innovations ont permis aux spécialistes de la probabilité et la statistique de développer leurs outils.

En outre, tenir une liste leur rendant grâce à tous n’est donc pas si aisé. Ce milieu manquant cruellement de visibilité, on aura vite fait d’en oublier un très grand nombre.

La chronologie ci-dessous tente (en vain il faut le reconnaître) de donner un aperçu de l’évolution de cette discipline. Elle sera complétée au fur et à mesure tant le travail qu’elle nécessite demeure énorme. N’hésitez pas à me reprendre ou mettre en évidence des oublis fondamentaux afin de m’aider à construire la chronologie la plus pertinente qui soit.

add2

add3

add4

add5

add6

Les méthodes de boosting

add.png

\bullet Présentation:

Le boosting est une famille d’outils d’analyse discriminante très puissants. L’idée est d’améliorer la règle de discrimination d’un classifieur sur plusieurs sous-parties de l’hyperplan formé par (Y, X ^1, \cdots, X ^P) et d’établir la classification finale au travers d’un vote global pondéré. Chaque partie du plan se voit alors attribuer une pondération en fonction de sa performance de discrimination et qui est mise à jour itération par itération afin d’adapter la frontière décisionnelle en fonction des zones les plus difficiles à classer.

Le classifieur utilisé est la plupart du temps la régression linéaire, logistique ou les arbres de décision. Ils portent le nom de « classifieurs fiables » à la fois car ils sont simples d’utilisation mais également car l’objectif du boosting est d’améliorer la règle de discrimination lorsqu’elle est peu performante.

Le boosting appartient à la catégorie des méthodes d’apprentissage statistique nécessitant un jeu de d’apprentissage pour la conception de la règle d’apprentissage et un jeu de test pour sa validation afin de limiter les risques de sur-apprentissage. Comme la plupart d’entre elles, le boosting a le principal défaut de concevoir une règle décisionnelle peu lisible d’où son surnom de boîte noire.

Parmi les méthodes de boosting, la plus célèbre reste l’algorithme AdaBoost conçu par Yoav Freun et Robert Shapire en 1997 et définit pour la discrimination d’une variable réponse Y binaire à partir d’un ensemble de variables continues explicatives \mathbf{X} = (X ^1, \cdots, X ^P).

D’autres algorithmes de boosting sont particulièrement répandus, nous pouvons ainsi citer: l’algorithme Gentle Adaboost, Real Adaboost, MART et RankBoost.

\bullet Les algorithmes de Boosting:

Hypothèse préliminaire: Y binaire ou continue, \mathbf{X} continue.

L’algorithme générale:

Avant d’aborder les algorithmes Adaboost et MART, nous présentons l’algorithme de boosting de base.

– Étape initiale: définir un classifieur faible f et un nombre T d’itérations d’entrainement pour l’optimisation des pondérations.

– Étape 1: Soit \mathbf{E}_1 = \mathbf{E} = [Y \mathbf{X}], la matrice de données d’origine et pour laquelle chaque observation a un poids similaire aux autres et égal à 1.

– Étape 2: Pour t \in \lbrace 2, \cdots, T \rbrace,

—- Nous appliquons notre classifieur faible: h_t = f(\mathbf{E}_1)

—- Nous mesurons le taux d’erreurs de classification de la règle décisionnelle conçue précédemment: \epsilon_t = Pr_{x ~ \mathbf{E}_t, y} I[h_t(x) \neq y]

—- Nous mettons à jour les pondérations et chaque observation mal classée se voit attribuer un poids plus important. Ainsi, \mathbf{E}_t devient \mathbf{E}_{t + 1}

– Étape 3: Nous déterminons la règle décisionnelle finale: H(x) = \mbox{Vote a partir des } h_t(x), \forall t \in [1,T]

L’algorithme AdaBoost

L’Algorithme AdaBoost a été pensé pour le cas où Y est binaire. Il se décline de la manière suivante:

– Étape initiale: initialisation des pondérations associées aux observations,

w_i ^1 = \frac{1}{N}, \forall i \in [1,N]

– Étape 1: \forall t \in [2,T]

—- Application du classifieur paramétré sur le jeu d’apprentissage en utilisant les pondérations w_i ^{t - 1}, \forall i \in [1,N], nous obtenons la règle décisionnelle f_t(x).

—- Calcul du taux d’erreurs de la règle décisionnelle définie précédemment,

\epsilon_t = Pr_{x ~ \mathbf{E}_t, y} I[f_t(x) \neq y]

—-Si \epsilon_t >0.5 alors le classifieur fait mieux qu’une règle aléatoire et nous conservons le modèle, sinon nous ajustons,

  • le coefficient de pondération:

\alpha_t = \frac{1}{2} ln(\frac{1 - \epsilon_t}{\epsilon_t})

  • les pondérations:

w_i ^t = w_i ^{t - 1} e ^{\alpha_t \cdot I_{(y_i \neq f_t (x_i))}}, \forall i \in [1,N]

– Étape 2: Nous obtenons le modèle final,

H(x) = sign[\sum_{t = 1} ^T \alpha_t f_t (x)]

L’algorithme Multiple Additive Regression Trees (MART)

L’Algorithme MART se base sur l’utilisation d’arbres de régression. Par conséquent, il est adapté au cas où Y est continue. Les différentes étapes d’estimation sont les suivantes:

– Étape initiale: Initialiser f_0 (x) = arg min_{\delta} \sum_{i = 1} ^N L(y_i, \delta), avec L fonction de perte à minimiser. Et détermination du nombre d’itérations T.

– Étape 1: Pour t \in [1, T],

— Pour i \in [1, N] calculer,

r_{i,t} = - [\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}]_{f = f_{t - 1}}

— Estimer le modèle par arbre de régression sur r_{i,t} et donnant les régions décisionnelles R_{j,t}, \forall j \in \lbrace 1, \cdots, J_t \rbrace

— Pour j \in \lbrace 1, \cdots, J_t \rbrace, calculer,

\delta_{j,t} = arg min_{\delta} \sum_{x_i \in R_{j,t}} L(y_i, f_{t - 1} (x_i) + \delta)

— Mettre à jour f_t (x) = f_{t - 1} (x) + \sum_{j = 1} ^{J_t} \delta_{j,t} I (x \in R_{j,t})

– Étape 2: Nous avons enfin la règle décisionnelle finale de forme: \hat{f} (x) = f_T (x)

\bullet Annexe théorique:

Cette partie de l’article présente une esquisse de la justification de l’usage de la fonction de perte exponentielle.

L’algorithme AdaBoost se base sur l’idée nouvelle d’une fonction de perte exponentielle dont le principal avantage est computationnel. Ainsi, nous montrons facilement que,

f ^* (x) = arg min_{f(x)} E_{Y|x} (e ^{-Y f(x)}) = \frac{1}{2} log \frac{P(Y = 1 | x)}{P(Y = -1 | x)}

Et équivalent à,

P(Y = 1 | x) = \frac{1}{1 + e ^{-2 f^* (x)}}

De cette manière, l’expansion additive produite par l’algorithme AdaBoost revient à estimer une partie du log-odds de P(Y = 1 | x). Ce qui justifie l’usage de son signe comme règle de classification décrite par la formule,

G(x) = sign (\sum_{m = 1} ^M \alpha_m G_m (x))

Un autre critère de minimisation de perte est la log-vraisemblance de la loi binomial négative (appelée également déviance ou entropie croisée), interprétant f comme une transformation logit. Nous avons,

p(x) = P(Y = 1 | x) = \frac{e ^{f(x)}}{e ^{-f(x)} + e ^{f(x)}}  = \frac{1}{1 + e ^{-2 f(x)}}

, avec Y ' = \frac{Y + 1}{2} \in \lbrace 0, 1 \rbrace. La fonction de perte est alors,

l(Y,p(x)) = Y ' log (p(x)) + (1 - Y ') log(1 - p(x))

Et de déviance,

-l (Y, f(x)) = log (1 + e ^{-2Y f(x)})

De la formule précédente, nous voyons que,

E_{Y|x} [-l(Y,f(x))] = E_{Y|x} [e ^{-Y f(x)}]

\bullet Application informatique:

Procédure SAS: ND.

Package et fonction Rhttps://www.rdocumentation.org/packages/JOUSBoost/versions/2.1.0/topics/adaboost

\bullet Bibliographie:

– The Elements of Statistical Learning de Trevor Hastie, Robert Tibshirani et Jerome Friedman.

– The top ten algorithms in data mining de Xindong Wu et Vipin Kumar.

– Probabilité, analyse des données et Statistique de Gilbert Saporta.

– Data mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry.

Le modèle additif généralisé

add.png

\bullet Présentation:

Le modèle additif généralisé, que nous pouvons retrouvons sous l’acronyme GAM, a été élaboré par Trevor Hastie et Rob Tibshirani en 1990.  Le modèle GAM se base sur la somme (doù le terme d’additif) de fonctions f_1, \cdots, f_P de transformation des différentes variables explicatives \mathbf{X} = (X ^1, \cdots, X^P).

La variable à expliquer Y peut être de tout format et les variables explicatives \mathbf{X} = (X ^1, \cdots, X ^P) doivent êtres continues.

Le modèle GAM nécessite un jeu d’apprentissage pour sa construction et un jeu de test pour sa validation car il est sujet à un possible fort sur-apprentissage.  En dépit de sa puissance avérée pour modéliser un phénomène, il reste peu conseillé si nous disposons d’un nombre P de variables explicatives trop important du fait d’un coût de calcul très élevé.

\bullet Le modèle additif généralisé:

Hypothèse préliminaire: \mathbf{X} continue.

Le modèle:

La forme générale du modèle est,

E[Y | X ^1, \dots, X ^P] = \alpha + \sum_{p = 1} ^P f_p (X ^p)

Avec f_p, \forall p \in [1, P], fonction de transformation associée à la variable X ^p ou au uplet de variables explicatives. Deux principaux algorithmes d’estimation des paramètres sont utilisés: l’algorithme Backfitting et l’algorithme général local de scoring,

L’Algorithme backfitting (Friedman et Stuezle, 1981):

– Etape d’initialisation: poser f_0 = E[Y] = \frac{1}{n} \sum_{i = 1} ^n Y_i, et f_p ^0 = 0, \forall p \in[1, P]

– Etape itérative t: pour p \in [1,P], déterminer,

  • R_p = Y - f_0 - \sum_{k = 1} ^{p - 1} f_k ^t (X ^k) - \sum_{k = p + 1} ^P f_k ^{t - 1} (X ^k)
  • f_p ^t = E[R_p | X ^p]

Tant que,

\frac{1}{n} || Y - s_0 - \sum_{p = 1} ^P s_p ^t (X ^p) || ^2 décroît ou satisfait le critère de convergence

A noter que pour p = 1, \sum_{k = 1} ^{1 - 1} s_k ^t (X ^k) = \sum_{k = 1} ^0 s_k ^t (X ^k) = 0 et pour p = P, \sum_{k = P + 1} ^P s_k ^t (X ^k) = 0.

De plus, l’estimation des différentes fonctions de lissage à l’instant t, f_p ^t, se fait selon la fonction lien retenue (modèle linéaire, logistique, etc).

Les transformations:

Le modèle GAM se base donc sur la transformation de variables ou de combinaisons de variables afin d’optimiser le modèle prédictif construit. A ce titre, trois principales fonctions existent: La fonction Cubic Smoothing Spline, la fonction de régression locale (LOESS) et la fonction Thin-Plate Smoothing Spline.

– La fonction Cubic Smoothing Spline de paramètre \lambda \in [0, + \infty[:

RSS(f,\lambda) = \sum_{i = 1} ^n [y_i - f(x_i)] ^2 + \lambda \int (f '' (t)) ^2 dt

– La fonction LOESS de paramètre le noyau K:

min_{\alpha(x_0), \beta(x_0)} \sum_{i = 1} ^n K_{\lambda} (x_0,x_i) [y_i - \alpha(x_0) - \beta(x_0) x_i] ^2

– La fonction Thin-Plate Smooting Spline:

f(x) = \beta_0 + \beta ^t x + \sum_{i = 1} ^n \alpha_i h_i (x), h_i (x) = \theta(|| x - x_p||), \theta(z) = z ^2 log z ^2

\bullet Annexe théorique:

Cette partie de l’article présente une esquisse de la démonstration des fonctions à estimer pour déterminer les valeurs de \mathbf{X} selon la projection f = (f_1, f_2, \cdots).

– Nous avons vu que la fonction Cubic Smoothing Spline de paramètre \lambda \in [0, + \infty[ était définie ainsi:

RSS(f,\lambda) = \sum_{i = 1} ^n [y_i - f(x_i)] ^2 + \lambda \int (f '' (t)) ^2 dt

Lorsque \lambda = 0 alors f peut être n’importe quel fonction d’interpolation de X. Si \lambda = \infty, alors f est la fonction des moindres carrés partiels et aucune derivée seconde ne peut être obtenue.

Pour obtenir une version simplifiée de la fonction Cubic Smoothing Spline, nous posons D_j(x) un sous-ensemble de D fonctions basiques et \theta un vecteur de paramètres à estimer. La fonction d’origine peut alors se réécrire:

RSS(\theta,\lambda) = (y - D \theta) ^t (y - D \theta) + \lambda \theta ^t \Omega_N \theta

, avec \lbrace D \rbrace_{i,j} = D_j (x_i) et \lbrace \Omega_N \rbrace_{j,k} = \int D_j '' (t) D_k '' (t) dt. La solution est alors,

\hat{\theta} = (D ^t D + \lambda \Omega_D) ^{-1} D ^t y

, qui s’apparente à la régression ridge généralisée. Après développement, nous obtenons ainsi la forme simplifiée de f,

\hat{f}(x) = \sum_{j = 1} ^D D_j (x) \hat{\theta}_j

– Nous avons vu que la fonction LOESS de paramètre le noyau K était définie ainsi:

min_{\alpha(x_0), \beta(x_0)} \sum_{i = 1} ^n K_{\lambda} (x_0,x_i) [y_i - \alpha(x_0) - \beta(x_0) x_i] ^2

La fonction d’estimation est de la forme,

\hat{f} (x_0) = \hat{\alpha} (x_0) + \hat{\beta} (x_0) x_0

Nous définissons alors la fonction du vecteur de valeurs: b(x) ^t = (1,x), \mathbf{B} la matrice de régression de taille N \times 2 composée des b(x_i) ^t et \mathbf{W}(x_0) la matrice diagonale de taille N \times N et dont l’élément i est K_{\lambda} (x_0, x_i). Nous avons alors,

\hat{f} (x_0) = b(x_0) ^t \mathbf{B} ^t \mathbf{W} (x_0) \mathbf{B} ^{-1} \mathbf{B} ^t \mathbf{W} (x_0) y = \sum_{i = 1} ^N l_i (x_0) y_i

Ce qui nous donne une expression explicite pour l’estimation de la LOESS.

– Nous avons vu que la fonction Thin-Plate Smooting Spline était définie ainsi:

f(x) = \beta_0 + \beta ^t x + \sum_{i = 1} ^n \alpha_i h_i (x)

, avec h_i (x) = \theta(|| x - x_p||) et \theta(z) = z ^2 log z ^2.

Soit \mathbf{X} \in R ^2 et les fonctions de base de la forme h_{1,k} (X ^1), \forall k \in 1, \cdots, M_1 des coordonnées de X ^1 et de même pour la fonction h_{2,k} (X ^2), \forall 1, \cdots, M_2. Nous définissons alors,

g_{j,k} (\mathbf{X}) = h_{1,j} (X ^1) h_{2,k} (X ^2), j = 1, \cdots, M_1 et k = 1, \cdots, M_2

, que nous pouvons généraliser avec la forme suivante,

g(\mathbf{X}) = \sum_{j = 1} ^{M_1} \sum_{k = 1} ^{M_2} \theta_{j,k} g_{j,k} (\mathbf{X})

Pour estimer cette fonction, l’idée est de résoudre le problème suivant,

min_J \sum_{i = 1} ^N \lbrace y_i - f(x_i) \rbrace ^2 + \lambda J[f]

, avec J fonction de pénalisation visant à stabiliser f.

De plus, si le paramètre \lambda \rightarrow 0 alors la solution s’approche d’une fonction d’interpolation et si \lambda \rightarrow \infty alors elle s’approche d’un plan des moindres carrés. Pour les valeurs intermédiaires de \lambda, la solution peut être représentée comme une fonction linéaire dont les coefficients sont obtenus par régression ridge.

La solution est alors de la forme,

f(x) = \beta_0 + \beta^t x + \sum_{j = 1} ^N \alpha_j h_j (x)

, où h_j(x) = \eta(||x - x_j||) et \eta(z) = z ^2 log z ^2.

\bullet Application informatique:

Procédure SAS: https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#statug_gam_sect004.htm

Package et fonction R: https://stat.ethz.ch/R-manual/R-devel/library/mgcv/html/gam.html

\bullet Bibliographie:

– The Elements of Statistical Learning de Trevor Hastie, Robert Tibshirani et Jerome Friedman.

– Data Mining et statistique décisionnelle. L’Intelligence des données de Stéphane Tufféry.

https://www.math.univ-toulouse.fr/~besse/pub/Appren_stat.pdf