[PYTHON] Ich habe versucht, es sorgfältig zu verstehen, während ich den Algorithmus Adaboost beim maschinellen Lernen implementiert habe (+ ich habe mein Verständnis der Array-Berechnung vertieft)

Einführung

Hier ist eine Zusammenfassung des ursprünglichen Boostings wie XGBoost, das häufig in Kaggle verwendet wird. Ich möchte Adaboost verstehen, während ich es unter den Boosting-Algorithmen implementiere. 　 Ich habe diesen Artikel von @amber_kshz verwendet und implementiert.

PRML implementiert Kapitel 14 Bagging und Ada Boost in Python https://qiita.com/amber_kshz/items/8869d8ef7f9743b16d8d

** Insbesondere konnte ich lernen, wie man mit einem Array effizient und schnell berechnet. ** Ich möchte zusammenfassen, wie das geht.

Die Hauptpunkte sind wie folgt.

• Boost verstehen
• Verstehen Sie den Adaboost-Algorithmus
• Vertiefen Sie Ihr Verständnis, indem Sie Adaboost implementieren
• Entscheidungsstumpf verstehen
• Probieren Sie es aus + Bewerten Sie den Unterschied aufgrund der Anzahl der Versuche

Boost verstehen

Die Methode zum Kombinieren von Lernenden, die als schwache Lernende bezeichnet werden, wird als ** Ensemble-Lernen ** bezeichnet. Typisches Ensemble-Lernen kann grob in vier Teile unterteilt werden.

1. Absacken (Unterscheidung von Trainingsdaten mit mehreren schwachen Lernenden und Durchschnitt (Stichprobe ** mit Duplizierung **))
2. Stimulation (Unterscheidung von Trainingsdaten mit mehreren schwachen Lernenden und Durchschnitt (Stichprobe ** keine Verdoppelung **))
3. Stapeln (Mittelwertbildung unter Berücksichtigung der Bedeutung schwacher Lernender)
4. ** (diesmal) Boosting (Verbesserung der Genauigkeit schwacher Lernender, um starke Lernende zu machen) **

Beim Lernen des Ensembles wird der Algorithmus, der den schwachen Lernenden kontinuierlich trainiert und modifiziert, um die Genauigkeit zu verbessern, als ** Boosting ** bezeichnet. Wir möchten einen genaueren Lernenden finden, indem wir auf die falsche (= falsch klassifizierte) Stichprobe achten und das nächste Lernen durchführen.

Die folgende Abbildung zeigt den Durchfluss. $ M $ ist die Anzahl der Versuche, und die Anzahl der Versuche steigt von links oben nach rechts unten. Ich würde gerne blaue und rote Kreise klassifizieren, aber die falsch klassifizierten Proben sind größtenteils ** eingekreist **. Sie können sehen, dass sich die grüne Klassifizierungslinie bewegt, um die falsch klassifizierte Stichprobe irgendwie zu trennen.

Ein ähnlicher Lernender ist ** Bagging **. Beim Absacken werden die Ergebnisse des unabhängigen Lernens gemittelt. Während jeder dieser Lernenden unabhängig ist, besteht der Unterschied darin, dass im Falle einer Steigerung die früher erlernten Ergebnisse für das spätere Lernen verwendet werden.

Verstehen Sie den Adaboost-Algorithmus

Lassen Sie uns nun den Adaboost-Algorithmus verstehen. Adaboost ist eine Abkürzung für Adaptive Boosting. Dies ist ein 1997 angekündigter Algorithmus. Adaboost wendet die Idee an, den neuen Prädiktor zu verwenden, um Korrekturen vorzunehmen, bei denen den Teilen, die vom vorherigen Prädiktor falsch eingeschätzt wurden, besondere Aufmerksamkeit geschenkt wird.

A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting https://www.sciencedirect.com/science/article/pii/S002200009791504X

Der spezifische Algorithmus ist wie folgt.

** Annahme **

• $ N \ in \ mathbb {N} $: Anzahl der Beispieldaten
• $ X = (x_0, x_1, \ dots, x_ {N-1}) $: Beispieldatenpunkte. Sagen wir $ x_n \ in \ mathbb {R} ^ D $.

Algorithmus

0. Eingabe: Die Trainingsdaten sind $ (X, T) $, der Basisklassifikator ist $ y $ und die Anzahl der Klassifikatoren ist $ M $.
1. Initialisieren Sie das Trainingsdatengewicht $ (w_0, w_1, \ dots, w_ {N-1}) $ auf $ w ^ {(0)} _ {n} = 1 / N $.
2. Wiederholen Sie Folgendes für $ m = 0,1, .... M-1 $. (a) Richten Sie den Klassifikator $ y_m (x) $ an den Testdaten aus, um die unten dargestellte Fehlerfunktion $ J_m $ zu minimieren. $ \begin{align} J_m = \sum_{n=0}^{N-1} w^{(m)}\_{n} I \left[ y(x_n, \theta_m) \neq t_n \right] \end{align} $

⇒ Zu diesem Zeitpunkt ist $ I \ left [y (x_n, \ theta_m) \ neq t_n \ right] $ ** 0 (= richtige Antwort), wenn die Testdaten und der vorhergesagte Wert übereinstimmen, und 1, wenn sie falsch sind. Ich werde. Wenn daher die Anzahl der richtigen Antworten groß ist, ist $ J_m $ klein ** (= es spielt die Rolle einer Fehlerfunktion und ist in Ordnung).

(b) Berechnen Sie $ \ epsilon_m und \ alpha_m $ aus dem Fehler des Basisklassifikators. $ \ Epsilon_m $ repräsentiert die Fehlerrate und $ \ alpha_m $ ist der Koeffizient, der im Gewichtsparameter widergespiegelt werden soll. $ \begin{align} \varepsilon_m &:= \frac{\sum_{n=0}^{N-1} w^{(m)}\_{n} I \left[ y(x_n, \theta_m) \neq t_n \right]}{\sum_{n=0}^{N-1} w^{(m)}\_{n}} \\\ \alpha_m &:= \log \left(\frac{1 - \varepsilon_m}{\varepsilon_m} \right) \end{align} $

(c) Verwenden Sie das im vorherigen Schritt gefundene $ \ alpha_m $, um das Gewicht $ w $ festzulegen $ \begin{align} \tilde{w}^{(m+1)}\_{n} &= w^{(m)}\_{n} \exp\left\\{ \alpha_m I \left[ y(x_n, \theta_m) \neq t_n \right] \right\\} \\\ \end{align} $ Update wie.

⇒ Wenn zu diesem Zeitpunkt der vorhergesagte Wert und die Testdaten übereinstimmen, gibt $ I $ $ 0 $ an. Im Gegenteil, wenn es falsch ist, beträgt es $ 1 $, sodass die Gewichtung zusammen mit dem vorherigen $ \ alpha $ aktualisiert wird.

Vertiefen Sie Ihr Verständnis, indem Sie Adaboost implementieren

Jetzt möchte ich tatsächlich mit der Implementierung fortfahren.

Entscheidungsstumpf verstehen

Diesmal verwendet der schwache Lernende die ermittelte Belastung. Ein entscheidender Bestand besteht darin, eine der Eingabevariablen ** bestimmter Daten auszuwählen, einen Schwellenwert entsprechend dem Wert festzulegen und zu klassifizieren. ** Kurz gesagt, ich verstehe, dass es sich um einen Entscheidungsbaum der Tiefe 1 handelt. Das folgende Programm definiert nun die ermittelte Aktienklasse.

adaboost.ipynb

    def fit_onedim(self, X, y, sample_weight, axis):

        N = len(X)

        # Here we sort everything according the axis-th coordinate of X
        sort_ind = np.argsort(X[:, axis])
        sorted_label = y[sort_ind]
        sorted_input = X[sort_ind]
        sorted_sample_weight = sample_weight[sort_ind]

        pred = -2*np.tri(N-1, N, k=0, dtype='int') + 1 
        mistakes = (pred != sorted_label ).astype('int')

        # The (weighted) error is calculated for each classifier
        errs = np.zeros((2, N-1))
        errs[0] = mistakes @ sorted_sample_weight
        errs[1] = (1 - mistakes) @ sorted_sample_weight

        # Here, we select the best threshold and sign
        ind = np.unravel_index(np.argmin(errs, axis=None), errs.shape)
        sign = -2*ind[0] + 1
        threshold = ( sorted_input[ind[1], axis] + sorted_input[ind[1] + 1, axis] ) / 2
        err = errs[ind]
        return sign, threshold, err

Erfahren Sie mehr über Berechnungen

Dieses Mal verwenden wir, wie unten gezeigt, den Makemoons-Datensatz. Stellen Sie sich den Fall vor, in dem die Anzahl der Beispieldaten 100 US-Dollar beträgt (siehe Abbildung unten), die Daten mit dem Label $ 1 $ $ 50 $ und die Daten mit dem Label $ -1 $ $ 50 $.

Dieser Datensatz wird in $ X = (x_1, x_2) $ gespeichert. Verwenden Sie der Einfachheit halber das folgende np.argsort, um den Index zu definieren, bevor Sie ihn in aufsteigender Reihenfolge anordnen.

Führen Sie als nächstes die Methode "np.tri" (Erzeugung der oberen und unteren Dreiecksmatrix) als Matrix "pred" aus, die einen vorläufigen vorhergesagten Wert ergibt.

Definieren Sie dann dieses "pred" -y "als" Fehler "-Matrix. Als Ergebnis wurden 99 Sätze von Korrektheitstabellen erstellt.

Zum Schluss multiplizieren Sie diese Korrektheitstabelle und das Gewicht, um die Verlustfunktion zu ermitteln.

Die Grenzlinie ist der Durchschnittswert von $ x_1 ^ m, x_1 ^ {m + 1} $, der die Grenze ist, wenn der Minimalwert dieser Verlustfunktion genommen wird. Im Fall von Adaboost gibt es hier auch einen Prozess zum Aktualisieren des Gewichts für das falsche Etikett.

(Ergänzung) Stellen Sie fest, ob sie übereinstimmen

Hier sind einige der Dinge, von denen ich dachte, dass sie ein guter Weg sind, dies zu tun. Ob der vorhergesagte Wert korrekt ist oder nicht, wird durch den Wahrheitswert (Bool-Typ) bestimmt. Im Inhalt der Fehlerfunktion zuvor war es $ 0 $, wenn es getroffen wurde, und $ 1 $, wenn es nicht war, also werde ich es so arbeiten.

sample.ipynb

a = np.array([[1,1,1,1],[1,1,1,1],[1,1,0,1]])
b = np.array([1,1,1,0])
c1 = (a != b )
c2 = (a != b ).astype('int')

print(c1)
print(c2)

[[False False False  True]
 [False False False  True]
 [False False  True  True]]
[[0 0 0 1]
 [0 0 0 1]
 [0 0 1 1]]

Hier ist ein einfaches Beispiel. Sei $ a $ der vorhergesagte Wert und $ b $ die richtige Bezeichnung. Sie können sehen, dass das Programm diesmal $ 0 $ für "False" und $ 1 $ für "True" zurückgibt, wenn es deaktiviert ist.

Bewegen Sie sich tatsächlich + bewerten Sie den Unterschied aufgrund der Anzahl der Versuche

Bewegen wir es tatsächlich. Versuchen Sie, die Anzahl der Versuche von 1 USD auf 9 USD zu erhöhen.

adaboost.ipynb

num_clf_list = [1, 2, 3, 4, 5, 6,7,8,9]
clfs = [AdaBoost(DecisionStump, num_clfs=M) for M in num_clf_list]

fig, axes = plt.subplots(3, 3, figsize=(15,15))

for i in range(len(clfs)):
    clfs[i].fit(X, y)
    plot_result(ax=np.ravel(axes)[i], clf=clfs[i], xx=xx, yy=yy, X=X, y=y)
    np.ravel(axes)[i].set_title(f'M = {num_clf_list[i]}')

Sie können sehen, dass die zu klassifizierenden Zeilen allmählich getrennt werden und es wahrscheinlich zu einem genauen Klassifizierer wird. Wie Sie der Definition entnehmen können, ist es bei einem bestimmten Bestand schwierig, mit einer nichtlinearen Kurve zu klassifizieren, da versucht wird, mit einer geraden Linie zu klassifizieren.

Am Ende

Dieses Mal habe ich mein Verständnis von Adaboost durch die Implementierung vertieft. Obwohl der Algorithmus selbst leicht zu verstehen ist, stellte ich bei der Implementierung fest, dass ich ohne ein gutes Verständnis von Matrixberechnungen wie "numpy" nicht fortfahren konnte. Von hier aus möchte ich meine analytischen Fähigkeiten verbessern, indem ich die in Kaggle häufig verwendeten Algorithmen wie XG Boost verstehe.

Das vollständige Programm finden Sie hier. https://github.com/Fumio-eisan/adaboost_20200427