CLR

Klassifikation und Vorhersage mit AdaBoost

James McCaffrey

Bei der Klassifikation handelt es sich um eine Technik für maschinelles Lernen, mit der anhand von Trainingsdaten ein Modell generiert wird (normalerweise eine einzelne komplexe Regel oder eine mathematische Gleichung), das einer von mehreren unterschiedlichen Kategorien Datenelemente zuweist. Das Modell kann dann für Vorhersagen zu neuen Datenelementen mit unbekannter Kategorie herangezogen werden. Zu den Beispielen gehören: eine Vorhersage auf der Grundlage verschiedener medizinischer Testdaten, ob ein Patient an Krebs erkrankt ist (ja, nein), oder eine Vorhersage der Risikokategorie (niedrig, mittelmäßig, hoch) eines Darlehensantrags auf der Grundlage des finanziellen Hintergrunds eines Antragstellers.

Es gibt viele unterschiedliche Klassifikationsalgorithmen und -techniken, einschließlich Naive Bayes, neuronaler Netzwerke und der logistischen Regression. In diesem Artikel erläutere ich eine faszinierende Technik: mithilfe der AdaBoost-Klassifikation werden anstatt einer einzelnen und komplexen Regel für Vorhersagen Trainingsdaten zum Generieren einer umfassenden Auflistung sehr einfacher Faustregeln verwendet. Anschließend wird für jede Faustregel ein Gewicht berechnet. Eine Vorhersage zu neuen Eingaben wird durch die Kombination der Faustregeln erstellt. Dabei wird das Gewicht jeder einfachen Regel berücksichtigt, und es wird ein erwartetes Ergebnis erzielt. Der Begriff „Boost“ ist darauf zurückzuführen, dass die Qualität der Vorhersage der einfachen Regeln durch die Kombination „geboostet“ (verbessert) wird.

AdaBoost ist eine Metaheuristik. Damit meine ich, dass AdaBoost aus einem Satz an Richtlinien besteht, der zum Erstellen eines bestimmten Klassifikationsalgorithmus verwendet werden kann. Es gibt bereits viele Varianten von AdaBoost-Algorithmen sowie viele eigenständige Tools, die eine Art von AdaBoost implementieren. Warum sollten wir dann noch eine AdaBoost-Klassifikation von Grund auf codieren? Das Anpassen vorhandener AdaBoost-Klassifikationstools kann sich als schwierig oder sogar unmöglich erweisen. Die Tools sind zudem vielleicht nur schwierig in ein Softwaresystem zu integrieren. Darüber hinaus bestehen möglicherweise Probleme im Zusammenhang mit den Urheberrechten oder dem geistigen Eigentum. 

An einem konkreten Beispiel lässt sich das Konzept am besten erklären. Sehen Sie sich Abbildung 1 an. Das Hauptproblem des Demoprogramms besteht in der Vorhersage, ob eine Mannschaft aus Seattle in einem anstehenden Spiel gegen eine Mannschaft aus Detroit gewinnen oder verlieren wird. Die Voraussetzungen sind, dass Seattle im eigenen Stadion spielt („Home“ unter „Field“) und die Schätzung (der „Spread“) ist, dass Seattle einen kleinen Vorteil („small“) hat. Im oberen Teil in Abbildung 1 werden 10 hypothetische Trainingsdatenelemente mit bekannten Ergebnissen angezeigt. Das erste Trainingstupel (Detroit, Home, Large, Win) bedeutet, dass Seattle eines der vorherigen Spiele gegen Detroit gewonnen hat, als Seattle im eigenen Stadion gespielt hat und der Punktespread groß war.

Abbildung 1: AdaBoost für Klassifikation und Vorhersage

Der nächste Teil des Demoprogramms zeigt, dass die 10 Trainingsdatenelemente zur effizienteren Verarbeitung aus Zeichenfolgedaten in ein nullbasiertes Ganzzahlformat konvertiert wurden. Anschließend wurden sie als Matrix im Arbeitsspeicher des Computers gespeichert. Zum Beispiel wird (Detroit, Home, Large, Win) als (3, 0, 2, 1) gespeichert. Beachten Sie, dass das vorherzusagende Ergebnis in diesem Beispiel nur zwei Werte hat: „Win“ (gewinnen) oder „Lose“ (verlieren). Dies wird als binäres Klassifikationsproblem bezeichnet. AdaBoost kann auch in Situationen verwendet werden, in denen die abhängige Variable aus drei oder mehr Werten besteht (multinomiale Klassifikation). Die meisten binären Klassifikationstechniken codieren die abhängige vorherzusagende Variable mit einem (0, 1)-Schema. AdaBoost verwendet jedoch fast immer ein (-1, +1)-Schema, da durch die Codierung ein Teil der Algorithmusimplementierung etwas vereinfacht wird. Beachten Sie, dass alle unabhängigen Prädiktorwerte für Variablen kategorisch („Home“, „Medium“ usw.) und nicht numerisch sind. Wie ich weiter unten erläutere, kann AdaBoost auch verwendet werden, wenn die Trainingsdaten aus numerischen Werten bestehen.

Im dritten Abschnitt von Abbildung 1 wird gezeigt, dass 8 Faustregeln aus den Trainingsdaten erzeugt wurden. Faustregeln werden in der AdaBoost-Terminologie häufig auch als „schwache Lerner“ oder „schwache Klassifikatoren“ bezeichnet. Der erste schwache Lerner lautet in benutzerfreundlicher Form „IF Opponent IS Buffalo THEN Result IS Win“ (Wenn der Gegner „Buffalo“ ist, dann lautet das Ergebnis „Gewinnen“) mit einer raw error-Rate (Rohfehlerrate) von „0.00“. Der zweite schwache Lerner lautet in anschaulicherer Form „IF Opponent IS Chicago THEN Result IS Lose“ (Wenn der Gegner „Chicago“ ist, dann lautet das Ergebnis „Verlieren“) mit einer Fehlerrate von „0.33“. Woher kommt dieser schwache Lerner? Sie stellen beim Betrachten der Trainingsdaten fest, dass „Chicago“ in drei Instanzen der Gegner ist. In zwei der Trainingsinstanzen lautete das Ergebnis „Lose“. Folglich ist der schwache Lerner in zwei von drei Fällen korrekt (0.67) und in einem Fall von drei Fällen falsch (0.33).

Beachten Sie, dass nicht alle Prädiktorwerte für Trainingselemente einen schwachen Lerner erzeugten: Es gibt keine Regel für Situationen, in denen der Gegner „Atlanta“ ist. Da zwei Trainingstupel vorhanden sind, in denen der Gegner „Atlanta“ ist und ein Ergebnis „Win“ und das andere „Lose“ lautet, wäre die Fehlerrate für den Lerner „0.50“, was keine nützlichen Informationen bereitstellt. In der in diesem Artikel besprochenen AdaBoost-Klassifikation wird davon ausgegangen, dass alle schwachen Lerner eine Rohfehlerrate von unter „0.50“ aufweisen.

Der nächste Abschnitt in Abbildung 1 weist darauf hin, dass der AdaBoost-Algorithmus die schwachen Lerner im Hintergrund verarbeitet, um für jeden Lerner ein Gewicht zu suchen. Diese Gewichte messen die Bedeutung jedes schwachen Klassifikators und werden in der AdaBoost-Terminologie als „Alphawerte“ bezeichnet. Der zentrale Bestandteil von AdaBoost besteht im Festlegen der Alphawerte. Das Klassifikationsmodell setzt sich aus dem Satz schwacher Lerner und ihren Alphagewichten zusammen.

Im letzten Teil des Demoprogramms wird das Klassifikationsmodell gezeigt, das für die Vorhersage für die Mannschaft „Seattle“ verwendet wird, wenn der „Opponent“ „Detroit“ ist, „Field“ auf „Home“ gesetzt ist und der Wert für den Punktespread „Small“ lautet. Wenn Sie den Satz generierter schwacher Lerner betrachten, stellen Sie fest, dass drei Lerner angewendet werden können: „[2] IF Opponent IS Detroit THEN Result IS Win (+1)“, „[3] IF Field IS Home THEN Result IS Win (+1)“ und „[5] IF Spread IS Small THEN Result IS Lose (-1)“. Die berechneten Alphawerte für die schwachen Lerner 2, 3 und 5 lauten „0.63“, „3.15“ bzw. „4.49“. Die Vorhersage anhand der Erwartungen „= (0.63)(+1) + (3.15)(+1) + (4.49)(-1) = -0.72“ (gerundet) bedeutet daher „Lose“, weil der Wert negativ ist. Auch wenn zwei der drei schwachen Lerner (2 und 3) „Win“ vorhersagen, hat der große Alphawert des schwachen Lerners 5 ein größeres Gewicht als diese Win-Vorhersagen, sodass sich insgesamt eine Vorhersage von „Lose“ ergibt.

In den folgenden Abschnitten werde ich die Funktionsweise des Demoprogramms ausführlich erklären, damit Sie einem .NET-System oder einer .NET-Anwendung Features zur Vorhersage hinzufügen können. Dieser Artikel setzt fortgeschrittene Programmierkenntnisse in einer C-Sprache voraus. Es wird nicht davon ausgegangen, dass Sie sich mit der AdaBoost-Klassifikation auskennen. Ich habe die Demo mit C# codiert. Die aufgeführten Erklärungen sollten jedoch ausreichen, um den Code in anderen Programmiersprachen umzugestalten wie Visual Basic .NET oder Python. Der Code für das Demoprogramm kann nicht vollständig in diesem Artikel aufgeführt werden, da er zu lang ist. Sie können den vollständigen Quellcode aber unter archive.msdn.microsoft.com/mag201304AdaptiveBoost herunterladen.

Der AdaBoost-Algorithmus

Im Zentrum der AdaBoost-Klassifikation liegt eine Routine, die jeden schwachen Lerner untersucht und ihm ein Alphagewicht zuweist. Der Algorithmus ist relativ komplex und kann am besten an einem konkreten Beispiel erklärt werden. Nehmen wir an, es gibt 10 Trainingstupel und 8 schwache Lerner, wie in Abbildung 1 gezeigt. Jedem Trainingstupel wird ein Gewicht zugewiesen, das in der AdaBoost-Literatur normalerweise die Bezeichnung „D“ erhält. Die Summe der D-Gewichte ergibt „1.0“, wodurch die D-Werte einer Verteilung genügen. Anfänglich werden allen Trainingsdatenelementen gleiche D-Gewichte zugewiesen, in diesem Fall „0.10“, weil 10 Elemente vorhanden sind:

[0] (D = 0.10) Detroit   Home   Large    Win
[1] (D = 0.10) Detroit   Away   Medium   Win
[2] (D = 0.10) Buffalo   Home   Small    Win
[3] (D = 0.10) Buffalo   Home   Medium   Win
[4] (D = 0.10) Atlanta   Away   Large    Win
[5] (D = 0.10) Chicago   Home   Medium   Win
[6] (D = 0.10) Chicago   Away   Small    Lose
[7] (D = 0.10) Chicago   Home   Small    Lose
[8] (D = 0.10) Atlanta   Away   Medium   Lose
[9] (D = 0.10) Detroit   Away   Large    Lose

Jeder Lerner hat einen Epsilon- und einen Alphawert. Epsilonwerte sind gewichtet Fehlerraten, mit denen Alphawerte berechnet werden. Am Anfang haben alle Lerner unbekannte Alphawerte (also „a = 0.00“) und unbekannte Epsilonwerte (also „e = -1.0“):

[0] (a = 0.00) (e = -1.0) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = -1.0) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = -1.0) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = -1.0) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = -1.0) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = -1.0) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = -1.0) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = -1.0) IF Spread IS Large THEN Result IS Win

In Pseudocode lautet der Algorithmus zum Suchen des Alphagewichts für jeden Lerner folgendermaßen:

set t=0
while not done loop
  update all learners' epsilons (weighted errors)
  find best (smallest epsilon) unused learner
  compute and save the alpha of best learner using its epsilon
  update the D weights for each training item using the best learner
  normalize the D weights so they sum to 1.0
  ++t
end loop

Die Hauptverarbeitungsschleife wird in folgenden Fällen beendet: wenn alle schwachen Lerner verarbeitet wurden und ihnen ein Alphagewicht zugewiesen wurde, wenn die Schleifenzählervariable „t“ einen Höchstwert überschreitet oder wenn die gewichtete Fehlerrate Epsilon für den besten nicht verwendeten schwachen Lerner einen Wert aufweist, wie „0.45“ oder „0.49“, und damit darauf hinweist, dass keine relativ guten nicht verwendeten Lerner zur Verarbeitung übrig sind.

Im ersten Schritt in der Schleife werden alle Epsilonwerte aktualisiert. Ein Epsilonwert ist die Summe der D-Gewichte inkorrekt klassifizierter Trainingstupel. Für den Lerner [0] (IF Opponent IS Buffalo THEN Result IS Win) gibt es zwei anwendbare Trainingstupel, [2] und [3], und die Regel ist in beiden Instanzen korrekt, somit ist Epsilon „0.00“. Für Lerner [1] (IF Opponent IS Chicago THEN Result IS Lose) gibt es drei anwendbare Trainingstupel, [5], [6] und [7]. Von diesen ist Tupel [5] nicht korrekt. Folglich ist Epsilon nur das D-Gewicht für Tupel [5] = „0.10“.

Auch wenn es nicht sofort offensichtlich ist, werden Sie bei einer genauen Untersuchung der Berechnung der Epsilonwerte feststellen, dass sie immer zwischen „0.0“ und „0.5“ sind. Nach allen Aktualisierungen lauten die Epsilonwerte für die Lerner folgendermaßen:

[0] (a = 0.00) (e = 0.00) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = 0.10) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = 0.10) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = 0.10) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = 0.20) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = 0.10) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = 0.10) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = 0.10) IF Spread IS Large THEN Result IS Win

Jetzt wird der beste Lerner ausgewählt. Es handelt sich dabei um Lerner [0], da der Epsilonwert mit „0.00“ am kleinsten ist. Der zugehörige Alphawert wird so berechnet:

alpha = 0.5 * log((1.0 - epsilon) / epsilon)

Dies ist in erster Linie eine magische Gleichung aus der AdaBoost-Theorie. Hier ist „log“ der natürliche Logarithmus (zur Basis e). Wie Sie wissen, ist der Alphawert ein Gewicht, das einem Lerner Bedeutung zuweist. Die vorherige Gleichung wurde so entworfen, dass kleinere Epsilonwerte (Lernerfehler) zu größeren Alphawerten (Lernerbedeutung) führen.

In dieser bestimmten Situation ist das problematisch, weil Epsilon „0“ ist und ein Fehler aufgrund einer Division durch Null auftritt. Das Demoprogramm konvertiert allerdings willkürlich jeden Epsilonwert von „0“ in „0.000001“, um dies zu vermeiden. Folglich wird der Alphawert für Lerner [0] mittels „0.5 * log(0.999999 / 0.000001) = 6.91“ berechnet. Dieser Wert wird Lerner [0] zugewiesen, und Lerner [0] wird als abgeschlossen gekennzeichnet.

Im nächsten Schritt in der Algorithmusschleife werden die D-Trainingstupelgewichte auf Grundlage des soeben berechneten besten Lerners aktualisiert. Es wird angestrebt, die D-Gewichte für die Trainingstupel zu erhöhen, die inkorrekt als bester Lerner klassifiziert wurden, und die D-Gewichte für Trainingstupel zu reduzieren, die korrekt als bester Lerner klassifiziert wurden. Die D-Aktualisierungsgleichung erscheint auf den ersten Blick etwas kompliziert:

D(new) = D(old) * exp(-alpha * actualY * predictedY)

Der beste Lerner war Lerner [0] (IF Opponent IS Buffalo THEN Result IS Win) mit einem Alphawert von „6.91“. Von den 10 Trainingstupeln gehört Lerner [0] zu den Tupeln [2] und [3]. Folglich werden diese D-Werte aktualisiert. Für Trainingstupel [2]:

D(new) = 0.10 * exp(-6.91 * (+1) * (+1))
       = 0.10 * exp(-6.91)
       = 0.0000997758

Der neue D-Wert für Trainingstupel [3] besitzt die gleiche Berechnung und den gleichen Wert wie Tupel [2].

In diesem Fall erhalten wir ein neues D-Gewicht, das sehr klein ist, weil das Trainingstupel vom besten Lerner korrekt klassifiziert wurde. Wenn der tatsächliche Y-Wert und der vorhergesagte Y-Wert identisch sind („-1“ oder „+1“), ergibt die Multiplikation beider Werte „+1“, und das Argument für „exp“ ist eine negative Zahl (da -alpha immer negativ sein wird), wodurch ein Ergebnis von unter „1.0“ entsteht. Wenn sich der tatsächliche Y-Wert jedoch vom vorhergesagten Y-Wert unterscheidet, ist das Produkt „-1“, und das Argument für „exp“ ist positiv, wodurch sich eine (möglicherweise große) Zahl von über „1.0“ ergibt. Aufgrund dieser Aktualisierungstechnik für D verwendet die AdaBoost-Klassifikation für die abhängigen Variablenwerte in der Regel „-1“ und „+1“ anstelle von „0“ und „+1“.

Jetzt lauten die vorläufigen Annäherungs-D-Werte (gerundet):

[0] (D = 0.1000) Detroit   Home   Large    Win
[1] (D = 0.1000) Detroit   Away   Medium   Win
[2] (D = 0.0001) Buffalo   Home   Small    Win
[3] (D = 0.0001) Buffalo   Home   Medium   Win
[4] (D = 0.1000) Atlanta   Away   Large    Win
[5] (D = 0.1000) Chicago   Home   Medium   Win
[6] (D = 0.1000) Chicago   Away   Small    Lose
[7] (D = 0.1000) Chicago   Home   Small    Lose
[8] (D = 0.1000) Atlanta   Away   Medium   Lose
[9] (D = 0.1000) Detroit   Away   Large    Lose

Der nächste Schritt in der Hauptalgorithmusschleife besteht im Normalisieren der D-Werte, sodass sie sich auf „1.0“ summieren, indem jeder vorläufige D-Wert durch die Summe der D-Werte geteilt wird. Die Summe der 10 D-Werte liegt bei etwa „0.8002“. Folglich ist der normalisierte D-Wert für das Trainingstupel [0] etwa „0.1000 / 0.8002 = 0.1249“. Die endgültigen aktualisierten D-Werte lauten:

[0] (D = 0.1249) Detroit   Home   Large    Win
[1] (D = 0.1249) Detroit   Away   Medium   Win
[2] (D = 0.0001) Buffalo   Home   Small    Win
[3] (D = 0.0001) Buffalo   Home   Medium   Win
[4] (D = 0.1249) Atlanta   Away   Large    Win
[5] (D = 0.1249) Chicago   Home   Medium   Win
[6] (D = 0.1249) Chicago   Away   Small    Lose
[7] (D = 0.1249) Chicago   Home   Small    Lose
[8] (D = 0.1249) Atlanta   Away   Medium   Lose
[9] (D = 0.1249) Detroit   Away   Large    Lose

Es wird hier angestrebt, dass der Fokus des Algorithmus auf anderen Trainingstupeln als [2] und [3] liegt, da diese Tupel von Lerner [0] berücksichtigt wurden. Hier springt der Algorithmus zum Anfang der Schleife zurück und aktualisiert die Epsilonwerte aller Lerner auf der Grundlage der neu berechneten D-Werte, bestimmt den besten nicht verwendeten Lerner ([5]), berechnet den Alphawert für den besten Lerner (4.49), aktualisiert die D-Werte für die entsprechenden Trainingstupel ([2], [6] und [7]) und berechnet normalisierte D-Werte für alle Trainingstupel.

In diesem Beispiel wird der Prozess fortgesetzt, bis die Alphawerte für alle 8 schwachen Lerner berechnet wurden. Im Allgemeinen schneiden nicht alle schwachen Lerner zwangsläufig als gute Lerner ab und erhalten einen Alphawert.

Allgemeine Programmstruktur

Das in Abbildung 1 gezeigte Demoprogramm ist eine einzelne C#-Konsolenanwendung. Ich habe Visual Studio 2010 verwendet, aber jede beliebige Version, die Microsoft .NET Framework 2.0 oder höher unterstützt, funktioniert. Ich habe ein neues Projekt mit dem Namen „AdaptiveBoosting“ erstellt und anschließend im Fenster „Projektmappen-Explorer“ „Program.cs“ in den aussagekräftigeren Namen „AdaptiveBoostingProgram.cs“ geändert, wodurch auch die Klasse „Program“ automatisch umbenannt wurde. Alle von der Vorlage generierten Using-Anweisungen am Anfang des Quellcodes habe ich gelöscht, außer den Verweisen auf die Namespaces „System“ und „Collections.Generic“. Die Main-Methode ist in Abbildung 2 aufgeführt. Es wurden einige WriteLine-Anweisungen entfernt, ein paar weitere Änderungen vorgenommen, und es wurde und eine zentrale programmdefinierte Klasse zur Definition schwacher Lernerobjekte hinzugefügt.

Abbildung 2: Allgemeine Programmstruktur

using System;
using System.Collections.Generic;
namespace AdaptiveBoosting
{
  class Program
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin adaptive boosting classification demo\n");
        string[] features = new string[] { "Opponent", "Field", "Spread",
          "Result" };
        string[][] values = new string[4][];
        values[0] = new string[] { "Atlanta", "Buffalo", "Chicago",
          "Detroit" }; // opponent
        values[1] = new string[] { "Home", "Away" };  // Field
        values[2] = new string[] { "Small ", "Medium", "Large " }; 
        // Note: Spaces added
        values[3] = new string[] { "Lose", "Win" }; 
        // The dependent/predicted variable
        string[][] rawTrain = new string[10][];
        rawTrain[0] = new string[] { "Detroit", "Home", "Large ", "Win" };
        rawTrain[1] = new string[] { "Detroit", "Away", "Medium", "Win" };
        rawTrain[2] = new string[] { "Buffalo", "Home", "Small ", "Win" };
        rawTrain[3] = new string[] { "Buffalo", "Home", "Medium", "Win" };
        rawTrain[4] = new string[] { "Atlanta", "Away", "Large ", "Win" };
        rawTrain[5] = new string[] { "Chicago", "Home", "Medium", "Win" };
        rawTrain[6] = new string[] { "Chicago", "Away", "Small ", "Lose" };
        rawTrain[7] = new string[] { "Chicago", "Home", "Small ", "Lose" };
        rawTrain[8] = new string[] { "Atlanta", "Away", "Medium", "Lose" };
        rawTrain[9] = new string[] { "Detroit", "Away", "Large ", "Lose" };
        Console.WriteLine("Raw (string) training data for team seattle:\n");
        Console.WriteLine("Opponent Field  Spread   Result");
        Console.WriteLine("===============================");
        ShowMatrix(rawTrain);
        Console.WriteLine("\nConverting and storing training data");
        int[][] train = RawTrainToInt(rawTrain, values);
        Console.WriteLine("Training data in int form:\n");
        ShowMatrix(train, true);
        Console.WriteLine(
          "\nCreating weak categorical stump learners from training data");
        List<Learner> learners = MakeLearners(values, train);
        Console.WriteLine("Completed. Weak learners are:\n");
        for (int i = 0; i < learners.Count; ++i)
          Console.WriteLine("[" + i + "] " + Description(learners[i],
            features, values));
        Console.WriteLine("\nInitializing list of best learner indexes");
        List<int> bestLearners = new List<int>();  // Indexes of good weak learners
        Console.WriteLine(
          "\nUsing adaptive boosting to find best  learners and alphas");
        MakeModel(train, values, learners, bestLearners);
        Console.WriteLine("\nModel completed");
        int numGood = bestLearners.Count;
        Console.Write("Algorithm found " + numGood + " good learners ");
        Console.WriteLine("and associated alpha values");
        Console.WriteLine("\nThe good learners and their alpha value are:");
        for (int i = 0; i < bestLearners.Count; ++i)
        {
          int lrn = bestLearners[i];
          Console.Write("[" + lrn + "] " +
            learners[lrn].alpha.ToString("F2") + "  ");
        }
        Console.Write("\nPredicting outcome when Opponent = Detroit, ");
        Console.WriteLine("Field = Home, Spread = Small\n");
        int[] unknownTuple = new int[] { 3, 0, 0 }; // Detroit, Home, Small
        int Y = Classify(unknownTuple, learners, bestLearners);
        Console.Write("Predicted Y = " + Y + " => ");
        Console.WriteLine("seattle will " + YValueToString(Y, values));
        Console.WriteLine("\nEnd\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
    // (Many) static methods here
  } // Class Program
  public class Learner  // Weak learner
  {
    // Definition code here
  }
} // ns

Die Main-Methode beginnt mit der Festlegung hartcodierter Zeichenfolgen für „Opponent“, „Field“, „Spread“ und „Result“ für die Features. Dann legt der Code in „Main“ für jedes Feature hartcodierte Werte fest: „Atlanta“, „Buffalo“, „Chicago“, „Detroit“, „Home“, „Away“, „Small“, „Medium“, „Large“, „Lose“ und „Win“. Um die Ausgabe übersichtlicher zu machen, habe ich hinter „Small“ und „Large“ ein Leerzeichen eingefügt.

Aus Gründen der Einfachheit sind die Trainingsdaten auch im Demoprogramm hartcodiert. In vielen Situationen werden Ihre Trainingsdaten in einer Textdatei oder SQL-Tabelle gespeichert. Dann können Sie die Trainingsdaten programmgesteuert überprüfen, um die Featurenamen (vermutlich aus der Headerzeile einer Textdatei oder aus SQL-Tabellenspaltennamen) und die Featurewerte zu bestimmen.

„Method RawTrainToInt“ konvertiert die Trainingsdaten im Zeichenfolgeformat in nullbasierte ganze Zahlen und speichert die ganzen Zahlen in einer int[][]-Matrix mit dem Namen „train“. „RawTrainToInt“ ruft ein Hilfsprogramm mit dem Namen „ValueToInt“ auf. In der letzten Spalte der train-Matrix sind die abhängigen Variablenwerte („Result“) gespeichert. Sie können abhängige Werte in einem separaten Spaltenarray speichern. In Situationen mit sehr großen Trainingsdatensätzen können Sie vielleicht nicht den gesamten Trainingsdatensatz im Speicher des Computers speichern. Dann müssen Sie durch den externen Datenspeicher anstelle einer internen Matrix streamen.

Das Demoprogramm bestimmt die schwachen Lerner mithilfe der MakeLearners-Methode und einer programmdefinierten Klasse „Learner“. Ich beschreibe die Methode und die Klasse im nächsten Abschnitt des Artikels ausführlicher. Nachdem die schwachen Lerner erstellt wurden, wird vom Demoprogramm die Methode „MakeModel“ aufgerufen. Wie im vorherigen Abschnitt beschrieben, bildet „MakeModel“ den Kern des AdaBoost-Algorithmus. Das Ergebnis ist eine sortierte Liste (namens „bestLearners“) der Indizes der Lerner, denen Alphawerte zugewiesen wurden.

Die Main-Methode wird abgeschlossen, indem das Ergebnis für Seattle für eine Reihe von Eingaben vorhergesagt wird. Hierbei wird mithilfe der Classify-Methode für „Opponent“ „Detroit“, für „Field“ „Home“ und für „Spread“ „Small“ festgelegt. In diesem Fall beträgt der Rückgabewert für „Classify“ „-0.72“, was als „Lose“ interpretiert wird.

Erstellen von schwachen Lernern

Die Implementierung eines bestimmten AdaBoost-Algorithmus hängt zu einem gewissen Grad von der spezifischen Definition eines schwachen Lerners ab. Die programmdefinierte Klasse „Learner“ besitzt sechs Felder:

public int feature;
public int value;
public int predicted;
public double error;
public double epsilon;
public double alpha;

Ich habe alle fünf Felder aus Gründen der Einfachheit mit öffentlichem Scope deklariert. Das Feld „feature“ enthält eine ganze Zahl, die darauf hinweist, welche unabhängige Variable für den Lerner entscheidend ist. Wenn beispielsweise „feature“ „0“ ist, basiert der schwache Lerner auf dem Wert eines Gegners. Das Feld „value“ enthält eine ganze Zahl, die den Wert des Features angibt. Wenn beispielsweise „value“ „3“ ist, basiert der schwache Lerner auf der Bedingung, dass der Gegner „Detroit“ ist. Das Feld „predicted“ ist „-1“ oder „+1“, je nachdem, ob die tatsächliche Kategorie für den Featurewert „Lose“ oder „Win“ ist.

Das Feld „error“ ist vom Typ „double“ und stellt die Rohfehlerrate dar, die mit dem schwachen Lerner in den Trainingsdaten verbunden ist. Wenn die Werte für einen schwachen Lerner beispielsweise „feature“ = „0“, „value“ = „3“ und „predicted“ = „+1“ lauten (was bedeutet, wenn „Opponent“ „Detroit“ ist, ist das Ergebnis „Win“), dann ist die Rohfehlerrate für die Trainingsdaten in Abbildung 1 „0.33“, da eines der drei Trainingsdatenelemente inkorrekt vorhergesagt wurde. Beachten Sie, dass „raw error“ jedes Trainingselement gleich behandelt. Es stellt sich heraus, dass der in diesem Artikel besprochene AdaBoost-Algorithmus das Feld „raw error“ nicht wirklich benötigt und das Feld hätte ausgelassen werden können. Ich finde diese Informationen jedoch nützlich.

Das Feld „epsilon“ ist ein gewichteter Fehlerterm. „epsilon“ ist für einen schwachen Lerner ein Fehlerterm, der die internen D-Gewichte berücksichtigt, die jedem Trainingselement zugewiesen werden. Die Epsilonwerte werden vom AdaBoost-Algorithmus zum Berechnen der Alphagewichte verwendet. Zusammenfassend lässt sich sagen, dass in der AdaBoost-Klassifikation zwei Gewichtssätze verwendet werden. Die Alphagewichte weisen jedem schwachen Lerner eine Bedeutung zu und werden zum Bestimmen einer Gesamtvorhersage verwendet. Ein Epsilonfehler ist ein interner Fehler, der einem schwachen Lerner zugeordnet und zum Berechnen der Alphagewichte herangezogen wird. Jedes Trainingstupel besitzt ein internes Gewicht (in der AdaBoost-Literatur als „D“ bezeichnet), das zum Berechnen der Epsilonfehler verwendet wird.

In Pseudocode funktioniert die MakeLearners-Methode so:

initialize an empty result list of learners
for each feature loop
  for each value of curr feature loop
    scan training data to determine most likely -1, +1 result
    if no most likely result, skip curr value
    create a new learner object with feature, value, predicted
    add learner object to result list
  end each value
end each feature
for each learner in result list
  for each training data item
    if learner isn't applicable to data, skip curr data item
    compute raw error rate
    store raw error into learner
  end each training data item
end each learner

Dies beruht auf folgender Vorstellung: Jeder Featurewert wie „Atlanta“ (Gegner) oder „Medium“ (Punktespread) generiert eine Regel für einen schwachen Lerner, die auf den Trainingsdaten beruht. Dies trifft nicht zu, wenn der Wert in den Trainingsdaten nicht enthalten ist (wie zum Beispiel ein Gegner von „New York“) oder der Wert kein sehr wahrscheinliches Ergebnis erzeugt, weil mit dem Wert eine identische Anzahl von gewonnenen und verlorenen Spielen verbunden ist (wenn zum Beispiel der Gegner in den Demodaten „Atlanta“ ist, mit einem gewonnenen und einem verlorenen Spiel).

Zusammenfassung

Eine wichtige Variante des in diesem Artikel besprochenen Algorithmus verwendet Daten mit numerischen Werten. Angenommen, die Werte für das Punktespreadfeature wären numerisch (wie „1.5“, „3.0“ und „9.5“) und nicht kategorisch („Small, „Medium“ und „Large“). Einer der Hauptvorteile der AdaBoost-Klassifikation im Vergleich zu anderen Klassifikationstechniken besteht darin, dass AdaBoost unkompliziert kategorische sowie numerische Daten direkt verarbeiten kann. Sie könnten eine dedizierte Lernerklasse mit einer benutzerfreundlichen Beschreibung erstellen wie „if Spread is less than or equal to 5.5 then Result is Lose“. Oder Sie könnten einen komplexeren Lerner erstellen, wie „if Spread is between 4.0 and 6.0 then Result is Win“.

Ich finde, dass die AdaBoost-Klassifikation am besten verwendet werden kann, wenn die abhängige vorherzusagende Variable nur zwei mögliche Werte aufweist. In fortgeschrittenen Formen von AdaBoost kann jedoch auch die multinomiale Klassifikation verwendet werden. Wenn Sie weitere Informationen hierzu oder zur Theorie von AdaBoost generell wünschen, empfehle ich Ihnen, nach Artikeln von den Experten R. Schapire und Y. Freund zu suchen.

In der Forschung für maschinelles Lernen wird davon ausgegangen, dass es keine einzige beste Technik zur Datenklassifikation oder Vorhersage gibt. Mit AdaBoost steht Ihnen jedoch eine äußerst leistungsstarke Methode zur Verfügung, die die Grundlage des Hinzufügens von Vorhersagefeatures zu einem .NET-Softwaresystem bilden kann.

Dr. James McCaffreyist für Volt Information Sciences Inc. tätig. Er leitet technische Schulungen für Softwareentwickler, die auf dem Campus von Microsoft in Redmond, Washington arbeiten. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. Dr. McCaffrey ist der Autor von ".NET Test Automation Recipes" (Rezepte für die .NET-Testautomatisierung, Apress 2006) und kann unter jammc@microsoft.com erreicht werden.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Darren Gehring (Microsoft)