Apprentissage automatique: supervisé - AdaBoost

Cible

Comprenez la formule adaboost et essayez-la avec scikit-learn.

On suppose que vous avez déjà appris l'intégration différentielle.

théorie

Adaboost est un type d'apprentissage d'ensemble appelé boosting qui apprend pas à pas plusieurs classificateurs faibles.

Booster

Boosting apprend plusieurs classificateurs faibles et le classificateur faible suivant en fonction des résultats d'apprentissage du classificateur faible précédent. Cela permet au discriminateur faible suivant de se concentrer sur des données que le discriminateur faible précédent n'a pas bien formé.

Alors que l'ensachage entraîne plusieurs classificateurs faibles indépendamment en parallèle, le boosting entraîne plusieurs discriminateurs faibles en série.

Classification par Adaboost

Un algorithme de boosting typique est l'Adaptive Boosting (AdaBoost). Les pondérations Adaboost ont correctement identifié les données d'entraînement avec une petite valeur et les données d'entraînement mal identifiées avec une grande valeur, de sorte que les classificateurs faibles de la seconde moitié se concentrent sur les données d'entraînement sujettes aux erreurs. Pour pouvoir apprendre.

Dérivation de l'adaboost

Ici, le nombre de données d'apprentissage est $ N $, le nombre de classificateurs faibles est $ M $, les données d'apprentissage sont $ x = (x_1, ..., x_n) $, et les données de réponse correctes sont $ t = (t_1, .. .., t_n) $ Cependant, $ t \ in \ {-1, 1 \} $, le poids des données d'entraînement est $ w ^ m_i (i = 1, ..., N, m = 1, .. Soit., M) $, et le classificateur faible sera $ y_m (x) = \ {-1, 1 \} $.

Adaboost minimise séquentiellement la fonction d'erreur exponentielle $ E $ dans la formule ci-dessous de $ m = 1 $ à $ M $.

E = \sum^N_{i=1} \exp \left( -t_i f_m(x_i) \right)

Où $ f_m (x) $ est défini dans la formule ci-dessous comme une combinaison linéaire du coefficient de couplage linéaire $ \ alpha_m $ et du classificateur faible $ y_m (x) $.

f_m(x) = \sum^m_{j=1} \alpha_j y_j(x)

Le but de l'entraînement Adaboost est de trouver le coefficient $ \ alpha_m $ qui minimise la fonction d'erreur exponentielle $ E $ et le poids $ w ^ m_i $ des données d'entraînement.

Où $ m-1 $ e coefficient $ \ alpha_1, ..., \ alpha_ {m-1} $ et classificateur faible $ y_1 (x), ..., y_ {m-1} (x) ) Étant donné que $ est recherché, considérons le coefficient $ m $ ème et le classificateur faible.

\begin{align}
E &= \sum^N_{i=1} \exp \left( -t_i f_{m-1}(x_i) - t_i f_m(x_i) \right) \\
&= \sum^N_{i=1} \exp \left( -t_i f_{m-1}(x_i) - t_i \alpha_m y_m(x_i) \right) \\
&= \sum^N_{i=1} w^m_i \exp \left( - t_i \alpha_m y_m(x_i) \right)
\end{align}

Sera. Ici, $ w ^ m_i = \ exp \ left (-t_i f_ {m-1} (x_i) \ right) $, et lorsqu'il est traité comme une constante en optimisation séquentielle, le classificateur faible $ y_m (x) $ $ Y_m (x_i) = t_i $ de $ y_m (x_i) t_i = 1 $ si correctement identifié, $ y_m (x_i) \ neq t_i $ de $ y_m (x_i) t_i = -1 Parce que c'est $

\begin{align}
E &= \sum_{y_m(x_i) = t_i} w^m_i \exp(-\alpha_m) + \sum_{y_m(x_i) \neq t_i} w^m_i \exp(\alpha_m) \\
&= \sum^N_{i=1} w^m_i \exp (-\alpha_m) + \sum_{y_m(x_i) \neq t_i} w^m_i \left\{ \exp(\alpha_m) - \exp(-\alpha_m) \right\} \
\end{align}

Si $ A = \ sum_ {y_m (x_i) \ neq t_i} w ^ m_i, B = \ sum ^ N_ {i = 1} w ^ m_i $

E = \left\{ \exp(\alpha_m) - \exp(-\alpha_m) \right\} A + \exp(-\alpha_m) B

Ce sera. Dans la minimisation du coefficient $ \ alpha_m $ que vous voulez trouver, si vous différenciez pour $ \ alpha_m $ et résolvez 0,

\frac{\partial E}{\partial \alpha_m} = \left\{ \exp(\alpha_m) + \exp(-\alpha_m) \right\} A - \exp(-\alpha_m) B = 0

Donc,

\exp(2 \alpha_m) = \frac{B}{A} - 1

Donc,

\begin{align}
\alpha_m &= \frac{1}{2} \ln \left( \frac{B}{A} - 1 \right) = \frac{1}{2} \ln \frac{1 - A/B}{A/B} \\
&= \frac{1}{2} \ln \frac{1 - \epsilon_m}{\epsilon_m}
\end{align}

Ce sera. cependant,

\epsilon_m = \frac{A}{B} = \frac{\sum_{y_m(x_i) \neq t_i} w^m_i}{\sum^n_{i=1} w^m_i}

Et $ \ epsilon_m $ sera appelée la fonction d'erreur pondérée.

D'autre part, la formule suivante est utilisée pour mettre à jour le poids des données d'entraînement $ i $ th.

w^{m+1}_i = w^m_i \exp \left( - t_i \alpha_m y_m(x_i) \right)

Ici, si la fonction qui devient 0 lorsqu'elle est correctement identifiée et 1 lorsqu'elle est incorrectement identifiée est $ I (y_m (x_i) \ neq t_i) $,

t_i y_m(x_i) = 1 - I(y_m(x_i) \neq t_i)

Alors

\begin{align}
w^{m+1}_i &= w^m_i \exp \left( - \alpha_m + I(y_m(x_i) \neq t_i) \right) \\
&= w^m_i \exp(-\alpha_m) \exp \left( \alpha_m I( y_m(x_i) \neq t_i) \right)
\end{align}

Et comme $ \ exp (- \ alpha_m) $ est commun à toutes les données, si nous l'ignorons par normalisation, l'expression de mise à jour du poids des données d'entraînement $ w ^ m_i $ est

w^{m+1}_i = w^m_i \exp \left( I( y_m(x_i) \neq t_i) \right)

Ce sera.

Apprendre Adaboost

L'algorithme d'apprentissage d'Adaboost est le suivant.

Tout d'abord, initialisez le poids des données d'entraînement $ w ^ 1_i $ comme suit.

w^1_i = \frac{1}{N}

Puis répétez les étapes suivantes à partir du nombre de classificateurs faibles $ m = 1 $ à $ M $.

1. Apprenez le classificateur faible $ y_m $ en utilisant le poids des données d'entraînement $ w ^ m_i $.
2. Trouvez la fonction d'erreur pondérée $ \ epsilon_m $ à partir du classificateur faible $ y_m $.
3. Trouvez le coefficient de couplage linéaire $ \ alpha_m $.
4. Mettez à jour le poids des données d'entraînement $ w ^ m_i $.

Enfin, lors de l'identification des nouvelles données $ x $, utilisez la fonction de code $ {\ rm sign} $ et utilisez la formule suivante pour l'identifier.

\hat{t} = {\rm sign} \left( \sum^M_{m=1} \alpha_m y_m (x) \right)

Notez qu'Adaboost étant à l'origine un modèle de classification binaire, il est nécessaire de préparer des classificateurs $ K-1 $ pour une classification multi-classes.

la mise en oeuvre

Environnement d'exécution

Matériel

・ Processeur Intel (R) Core (TM) i7-6700K 4,00 GHz

Logiciel

・ Windows 10 Professionnel 1909 ・ Python 3.6.6 ・ Matplotlib 3.3.1 ・ Numpy 1.19.2 ・ Scikit-learn 0.23.2

Programme à exécuter

Le programme implémenté est publié sur GitHub.

adaboost.py

résultat

Classification par Adaboost

Voici le résultat de l'application d'Adaboost à l'ensemble de données sur le cancer du sein comme auparavant.

Accuracy 97.37%
Precision, Positive predictive value(PPV) 97.06%
Recall, Sensitivity, True positive rate(TPR) 98.51%
Specificity, True negative rate(TNR) 95.74%
Negative predictive value(NPV) 97.83%
F-Score 97.78%

La figure ci-dessous montre les limites discriminantes lors de l'exécution de la multiclassification sur un ensemble de données d'iris.

Retour par Adaboost

Pour les données du problème de régression, un nombre aléatoire a été ajouté à l'onde sinusoïdale.

référence

1.11.3. AdaBoost

1. Yoav Freund and Robert E. Schapire. "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting", Journal of computer and system sciences 55.1 (1997): pp. 119-139.
2. Ji Zhu, Hui Zou, Saharon Rosset, and Trevor Hastie. "Multi-class AdaBoost", Statistics and its Interface, 2(3), 2009, pp. 349-360.
3. Harris Drucker. "Improving Regressors using Boosting Techniques", ICML, 1997, pp. 107-115.
4. Yuzo Hirai. «Première reconnaissance de formes», Morikita Publishing, 2012.