[PYTHON] Maschinelles Lernen: Betreut --AdaBoost

Ziel

Verstehe die Adaboost-Formel und probiere sie mit Scikit-Learn aus.

Es wird davon ausgegangen, dass Sie die differentielle Integration bereits gelernt haben.

Theorie

Adaboost ist eine Art von Ensemble-Lernen namens Boosting, bei dem mehrere schwache Klassifikatoren Schritt für Schritt gelernt werden.

Erhöhen

Durch Boosting werden mehrere schwache Klassifikatoren und der nächste schwache Klassifikator basierend auf den Lernergebnissen des vorherigen schwachen Klassifikators gelernt. Dies ermöglicht es dem nächsten schwachen Diskriminator, sich auf Daten zu konzentrieren, die der vorherige schwache Diskriminator nicht gut trainiert hat.

Beim Absacken werden mehrere schwache Klassifikatoren unabhängig voneinander parallel trainiert, während beim Boosten mehrere schwache Klassifikatoren in Reihe trainiert werden.

Klassifizierung nach Adaboost

Ein typischer Boosting-Algorithmus ist Adaptive Boosting (AdaBoost). Adaboost gewichtet korrekt identifizierte Trainingsdaten mit einem kleinen Wert und falsch identifizierte Trainingsdaten mit einem großen Wert, so dass sich die schwachen Klassifikatoren in der zweiten Hälfte auf fehleranfällige Trainingsdaten konzentrieren. Lernen können.

Ableitung von Adaboost

Hier beträgt die Anzahl der Trainingsdaten $ N $, die Anzahl der schwachen Klassifikatoren $ M $, die Anzahl der Trainingsdaten $ x = (x_1, ..., x_n) $ und die korrekten Antwortdaten $ t = (t_1, .. .., t_n) $ Jedoch ist $ t \ in \ {-1, 1 \} $ das Gewicht der Trainingsdaten $ w ^ m_i (i = 1, ..., N, m = 1, .. Sei., M) $ und der schwache Klassifikator $ y_m (x) = \ {-1, 1 \} $.

Adaboost minimiert sequentiell die Exponentialfehlerfunktion $ E $ in der folgenden Formel von $ m = 1 $ auf $ M $.

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

Wobei $ f_m (x) $ in der folgenden Formel als lineare Kombination des linearen Kopplungskoeffizienten $ \ alpha_m $ und des schwachen Klassifikators $ y_m (x) $ definiert ist.

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

Der Zweck des Adaboost-Trainings besteht darin, den Koeffizienten $ \ alpha_m $ zu finden, der die Exponentialfehlerfunktion $ E $ und das Gewicht $ w ^ m_i $ der Trainingsdaten minimiert.

Wobei $ m-1 $ der Koeffizient $ \ alpha_1, ..., \ alpha_ {m-1} $ und der schwache Klassifikator $ y_1 (x), ..., y_ {m-1} (x) ) Wenn $ gesucht wird, berücksichtigen Sie den $ m $ -ten Koeffizienten und den schwachen Klassifikator.

\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}

Wird sein. Hier ist $ w ^ m_i = \ exp \ left (-t_i f_ {m-1} (x_i) \ right) $, und wenn es bei der sequentiellen Optimierung als Konstante behandelt wird, der schwache Klassifikator $ y_m (x) $ $ Y_m (x_i) = t_i $ von $ y_m (x_i) t_i = 1 $ bei korrekter Identifizierung, $ y_m (x_i) \ neq t_i $ von $ y_m (x_i) t_i = -1 Weil es $ ist

\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}

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

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

Es wird sein. Wenn Sie in der Minimierung für den Koeffizienten $ \ alpha_m $ suchen, wenn Sie nach $ \ alpha_m $ differenzieren und 0 lösen,

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

Deshalb,

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

Deshalb,

\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}

Es wird sein. Jedoch,

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

Und $ \ epsilon_m $ wird als gewichtete Fehlerfunktion bezeichnet.

Andererseits wird die folgende Formel verwendet, um das Gewicht der $ i $ -ten Trainingsdaten zu aktualisieren.

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

Wenn die Funktion, die bei korrekter Identifizierung 0 und bei falscher Identifizierung 1 wird, $ I (y_m (x_i) \ neq t_i) $ ist,

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

Damit

\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}

Und da $ \ exp (- \ alpha_m) $ allen Daten gemeinsam ist, ist der Aktualisierungsausdruck des Trainingsdatengewichts $ w ^ m_i $, wenn wir ihn durch Normalisierung ignorieren

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

Es wird sein.

Adaboost lernen

Der Lernalgorithmus von Adaboost ist wie folgt.

Initialisieren Sie zunächst das Trainingsdatengewicht $ w ^ 1_i $ wie folgt.

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

Wiederholen Sie dann die folgenden Schritte von der Anzahl der schwachen Klassifikatoren $ m = 1 $ bis $ M $.

1. Lernen Sie den schwachen Klassifikator $ y_m $ anhand des Trainingsdatengewichts $ w ^ m_i $.
2. Suchen Sie die gewichtete Fehlerfunktion $ \ epsilon_m $ aus dem schwachen Klassifikator $ y_m $.
3. Ermitteln Sie den linearen Kopplungskoeffizienten $ \ alpha_m $.
4. Aktualisieren Sie das Trainingsdatengewicht $ w ^ m_i $.

Verwenden Sie zum Identifizieren der neuen Daten $ x $ die Codefunktion $ {\ rm sign} $ und verwenden Sie die folgende Formel, um sie zu identifizieren.

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

Da Adaboost ursprünglich ein binäres Klassifizierungsmodell ist, müssen $ K-1 $ -Klassifizierer für die Klassifizierung mehrerer Klassen vorbereitet werden.

Implementierung

Ausführungsumgebung

Hardware-

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

Software

・ Windows 10 Pro 1909 ・ Python 3.6.6 ・ Matplotlib 3.3.1 ・ Numpy 1.19.2 ・ Scikit-Learn 0.23.2

Programm zum Ausführen

Das implementierte Programm wird auf [GitHub] veröffentlicht (https://github.com/sho-watari/MachineLearning/blob/master/Supervised).

adaboost.py

Ergebnis

Klassifizierung nach Adaboost

Hier ist das Ergebnis der Anwendung von Adaboost auf den Brustkrebs-Datensatz wie zuvor.

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%

Die folgende Abbildung zeigt die Diskriminanzgrenzen bei der Durchführung einer Mehrfachklassifizierung für einen Iris-Datensatz.

Rückkehr mit Adaboost

Für die Daten des Regressionsproblems wurde der Sinuswelle eine Zufallszahl hinzugefügt.

Referenz

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. "Erste Mustererkennung", Morikita Publishing, 2012.