Month Year

Volume # Number #

Testlauf - Probit-Klassifizierung mit C#

James McCaffrey | Oktober 2014

Laden Sie die Codebeispiele herunter

Probit-Klassifizierung (von Probability Unit, deutsch: Wahrscheinlichkeitseinheit) ist eine maschinelle Lerntechnik (ML), die in Situationen verwendet werden kann, wo die vorherzusagende Variable binär ist, d.h. einen von nur zwei möglichen Werten einnehmen kann. Die Probit-Klassifizierung wird auch Probit-Regression und Probit-Modellierung genannt.

Die Probit-Klassifizierung ist der Klassifizierung durch logistische Regression (LR) sehr ähnlich. Die beiden Techniken sorgen für dieselbe Art von Problemen und ergeben eher ähnliche Ergebnisse, und die Wahl, ob Probit-Klassifizierung oder LR-Klassifizierung verwendet wird, hängt normalerweise von der Disziplin ab, in der Sie tätig sind. Probit wird oft in den Wirtschaftswissenschaften und dem Finanzsektor verwendet, während LR in anderen Feldern verbreiteter ist.

Um zu verstehen, was Probit-Klassifizierung ist, sollten Sie einen Blick in das Demoprogramm in Abbildung 1 werfen.

Abbildung 1 Probit-Klassifizierung in Aktion

Diese Demo verwendet Probit-Klassifizierung, um ein Modell zu erstellen, das auf Grundlage von Alter, Geschlecht und den Ergebnissen eines Nierentests vorhersagt, ob ein Krankenhauspatient sterben wird. Die Daten sind frei erfunden. Das erste Rohdatenelement ist:

Verstehen der Probit-Klassifizierung

Eine einfache Möglichkeit, den Tod in Abhängigkeit von Alter, Geschlecht und Nierenergebnis vorherzusagen, bestände darin, eine lineare Kombination zu bilden für die Zeilen:

died = b0 + (b1)(age) + (b2)(sex) + (b3)(kidney)

wobei b0, b1, b2, b3 Gewichtungen sind, die bestimmt werden müssen, sodass die berechneten Ergebniswerte der Trainingsdaten den bekannten abhängigen Variablenwerten genau entsprechen. Logistische Regression erweitert diese Idee mit einer komplizierteren Vorhersagefunktion:

z = b0 + (b1)(age) + (b2)(sex) + (b3)(kidney)
died = 1.0 / (1.0 + e-z)

Die Mathematik dahinter ist kompliziert, aber die Vorhersagefunktion (logistische Sigmoidfunktion genannt) gibt immer einen Wert zwischen 0,0 und 1,0 zurück, der als Wahrscheinlichkeit interpretiert werden kann. Die Probit-Klassifizierung verwendet eine andere Vorhersagefunktion:

z = b0 + (b1)(age) + (b2)(sex) + (b3)(kidney)
died = Phi(z)

Die Phi(z)-Funktion wird als kumulative Standardnormaldichtefunktion bezeichnet (normalerweise als CDF, Cumulative Density Function, abgekürzt), und gibt immer einen Wert zwischen 0,0 und 1,0 zurück. Die CDF ist etwas komplizierter, da es dafür keine einfache Gleichung gibt. Der CDF für einen Wert z ist der Bereich unter der berühmten glockenförmigen Kurvenfunktion (die Gaußsche Funktion) von negativer Unendlichkeit bis z.

Dies sieht komplizierter aus, als es in Wahrheit ist. Betrachten Sie den Graph in Abbildung 2. Der Graph zeigt die nebeneinander eingezeichnete logistische Sigmoidfunktion und die CDF-Funktion. Wichtig ist, dass beide Funktionen für jeden Wert z einen Wert zwischen 0,0 und 1,0 zurückgeben, selbst wenn die zugrundeliegenden Funktionen ganz unterschiedlich sind, der als Wahrscheinlichkeit interpretiert werden kann.

Abbildung 2 Der Graph der kumulativen Dichtefunktion

Aus Entwicklersicht besteht die erste Herausforderung darin, eine Funktion zu verfassen, welche die CDF für einen Wert z berechnet. Es gibt keine einfache Gleichung für die Berechnung der CDF, aber zahlreiche exotisch anmutende Annäherungen. Eine der gebräuchlichsten Möglichkeiten, sich der CDF-Funktion anzunähern, ist, etwas zu berechnen, das erf-Funktion genannt wird, kurz für Error Function (Fehlerfunktion). Dafür wird eine Gleichung namens A&S 7.1.26 verwendet und anschließend erf genutzt, um CDF zu bestimmen. Der Code für die CDF-Funktion wird in Abbildung 3 dargestellt.

Abbildung 3 Die CDF-Funktion in C#

static double CumDensity(double z)
{
  double p = 0.3275911;
  double a1 = 0.254829592;
  double a2 = -0.284496736;
  double a3 = 1.421413741;
  double a4 = -1.453152027;
  double a5 = 1.061405429;
  int sign;
  if (z < 0.0)
    sign = -1;
  else
    sign = 1;
  double x = Math.Abs(z) / Math.Sqrt(2.0);
  double t = 1.0 / (1.0 + p * x);
  double erf = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) *
    t * Math.Exp(-x * x);
  return 0.5 * (1.0 + (sign * erf));
}

Die zweite Herausforderung beim Erstellen von Code für die Probit-Klassifizierung ist, die Werte für die Gewichtungen zu bestimmen, sodass die berechneten Ausgabewerte bei Verwendung der Trainingsdaten den bekannten Ergebniswerten eng entsprechen. Eine andere Möglichkeit der Problembetrachtung ist, dass das Ziel darin besteht, den Fehler zwischen berechneten und bekannten Ausgabewerten zu minimieren. Dies wird Training des Modells durch numerische Optimierung genannt.

Es gibt keine einfache Möglichkeit, die meisten ML-Klassifikatoren zu trainieren, so auch bei Probit-Klassifikatoren. Es gibt circa ein Dutzend Haupttechniken, die Sie verwenden können, und jede Technik hat Dutzende von Variationen. Häufig verwendete Trainingstechniken sind das Gradientenverfahren, Backpropagation, Newton-Raphson, Partikelschwarmoptimierung, evolutionäre Optimierung und L-BFGS. Das Demoprogramm verwendet eine der ältesten und einfachsten Trainingstechniken: Simplex-Optimierung.

Verstehen der Simplex-Optimierung

Vage ausgedrückt ist ein Simplex ein Dreieck. Die Idee hinter der Simplex-Optimierung ist, mit drei möglichen Lösungen zu beginnen (daher „Simplex“). Eine Lösung wird am besten sein (den kleinsten Fehler haben), eine wird am schlechtesten sein (größter Fehler), und die dritte wird „andere“ genannt. Als Nächstes erstellt die Simplex-Optimierung drei neue mögliche Lösungen namens „erweitert“, „reflektiert“ und „zusammengezogen“. Jede dieser Lösungen wird mit der aktuell schlechtesten Lösung verglichen, und wenn einer der neuen Kandidaten besser ist (kleinerer Fehler), wird die schlechteste Lösung ersetzt.

Die Simplex-Optimierung wird in Abbildung 4 dargestellt. In einem einfachen Fall, in dem die Lösung aus zwei Werten besteht, wie etwa (1,23, 4,56), können Sie sich eine Lösung als Punkt auf der (x, y)-Ebene vorstellen. Die linke Seite von Abbildung 4 zeigt, wie die drei neuen Kandidatenlösungen aus der aktuell besten, schlechtesten und der anderen Lösung generiert werden.

Abbildung 4 Simplex-Optimierung

Zuerst wird ein Schwerpunkt berechnet. Der Schwerpunkt ist der Durchschnitt der besten und der anderen Lösung. Bei zwei Dimensionen ist dies ein Punkt auf halber Strecke zwischen dem besten und dem anderen Punkt. Als Nächstes wird eine imaginäre Linie erstellt, die beim schlechtesten Punkt beginnt und durch den Schwerpunkt gezogen wird. Der „zusammengezogen“-Kandidat liegt zwischen dem schlechtesten Punkt und dem Schwerpunkt. Der reflektierte Kandidat befindet sich auf der imaginären Linie hinter dem Schwerpunkt. Und der „erweitert“-Kandidat liegt hinter dem reflektierten Punkt.

Bei jeder Iteration der Simplex-Optimierung wird der schlechteste Kandidat durch einen anderen Kandidat ersetzt, wenn der erweiterte, reflektierte oder zusammengezogene Kandidat besser als die aktuell schlechteste Lösung ist. Wenn keiner der drei generierten Kandidaten besser als die schlechteste Lösung ist, werden die aktuell schlechteste und die andere Lösung in Richtung der besten Lösung verschoben, zu Punkten zwischen deren aktueller Position und der besten Lösung, wie in der rechten Seite von Abbildung 4 gezeigt.

Nach jeder Iteration wird ein neues virtuelles „bestes-anderes-schlechtestes“-Dreieck gebildet, wodurch eine stetige Annäherung an eine optimale Lösung erfolgt. Wenn eine Momentaufnahme jedes Dreiecks erfolgt und man sich diese sequenziellen Dreiecke ansieht, ähneln die in der Ebene verschobenen Dreiecke einem spitzen Klecks, der wie eine einzellige Amöbe aussieht. Aus diesem Grund wird die Simplex-Optimierung manchmal als Optimierung nach Amoeba-Methode bezeichnet.

Es gibt viele Varianten der Simplex-Optimierung, die sich dadurch unterscheiden, wie weit sich die zusammengezogenen, reflektierten und erweiterten Kandidatenlösungen vom aktuellen Schwerpunkt entfernt befinden, sowie durch die Reihenfolge, in der die Kandidatenlösungen überprüft werden, um herauszufinden, ob sie besser als die aktuell schlechteste Lösung sind. Die häufigste Form der Simplex-Optimierung wird Nelder-Mead-Algorithmus genannt. Das Demoprogramm verwendet eine einfachere Variation, die keinen eigenen Namen hat.

Für die Probit-Klassifizierung ist jede mögliche Lösung ein Satz an Gewichtungswerten. Abbildung 5 zeigt in Pseudocode die Variation der Simplex-Optimierung, die im Demoprogramm verwendet wird.

Abbildung 5 Pseudocode für die Simplex-Optimierung, die im Demoprogramm verwendet wird

randomly initialize best, worst other solutions
loop maxEpochs times
  create centroid from worst and other
  create expanded
  if expanded is better than worst, replace worst with expanded,
    continue loop
  create reflected
  if reflected  is better than worst, replace worst with reflected,
    continue loop
  create contracted
  if contracted  is better than worst, replace worst with contracted,
    continue loop
  create a random solution
  if  random solution is better than worst, replace worst,
    continue loop
  shrink worst and other toward best
end loop
return best solution found

Die Simplex-Optimierung bietet wie alle ML-Optimierungsalgorithmen Vor- und Nachteile. Sie ist jedoch (relativ) einfach zu implementieren und funktioniert normalerweise – jedoch nicht immer – gut in der Praxis.

Das Demoprogramm

Um das Demoprogramm zu erstellen, habe ich Visual Studio gestartet, die Vorlage für das C#-Konsolenanwendungsprogramm ausgewählt und diese ProbitClassification genannt. Die Demo hat keine signifikanten Microsoft .NET Framework-Versionsabhängigkeiten, jede halbwegs aktuelle Version von Visual Studio sollte also funktionieren. Nachdem der Vorlagencode im Solution Explorer-Fenster geladen wurde, habe ich die Datei Program.cs in ProbitProgram.cs umbenannt. Visual Studio hat daraufhin automatisch die Programmklasse umbenannt.

Abbildung 6 Beginn des Democode

using System;
namespace ProbitClassification
{
  class ProbitProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin Probit Binary Classification demo");
      Console.WriteLine("Goal is to predict death (0 = false, 1 = true)");
      double[][] data = new double[30][];
      data[0] = new double[] { 48, +1, 4.40, 0 };
      data[1] = new double[] { 60, -1, 7.89, 1 };
      // Etc.
      data[29] = new double[] { 68, -1, 8.38, 1 };
...

Der Beginn des Democode ist in Abbildung 6 dargestellt. Die Dummydaten werden im Programm hartcodiert. In einem Nicht-Demoszenario würden Ihre Daten in einer Textdatei gespeichert und Sie müssten eine Dienstprogrammmethode schreiben, um die Daten in den Speicher zu laden. Als Nächstes werden die Ursprungsdaten mit der programmdefinierten Methode ShowData angezeigt:

Console.WriteLine("\nRaw data: \n");
Console.WriteLine("       Age       Sex      Kidney   Died");
Console.WriteLine("=======================================");
ShowData(data, 5, 2, true);

Dann werden die Spalten 0 und 2 der Ursprungsdaten normalisiert:

Console.WriteLine("Normalizing age and kidney data");
int[] columns = new int[] { 0, 2 };
double[][] means = Normalize(data, columns); // Normalize, save means & stdDevs
Console.WriteLine("Done");
Console.WriteLine("\nNormalized data: \n");
ShowData(data, 5, 2, true);

Die Normalisierungsmethode speichert die Durchschnittswerte und Standardabweichungen aller Spalten und gibt diese zurück, sodass bei neuen Daten diese mit denselben Parametern normalisiert werden können, die zum Training des Modells verwendet wurden. Dann werden die normalisierten Daten in einen Trainingssatz (80 Prozent) und einen Testsatz (20 Prozent) aufgeteilt:

Console.WriteLine("Creating train (80%) and test (20%) matrices");
double[][] trainData;
double[][] testData;
MakeTrainTest(data, 0, out trainData, out testData);
Console.WriteLine("Done");
Console.WriteLine("\nNormalized training data: \n");
ShowData(trainData, 3, 2, true);

Sie können die Methode MakeTrainTest parametrisieren, um den Prozentwert der Elemente zu akzeptieren, die im Trainingssatz landen sollen. Dann wird ein programmdefiniertes Probit-Klassifikatorobjekt instantiiert:

int numFeatures = 3; // Age, sex, kidney
Console.WriteLine("Creating probit binary classifier");
ProbitClassifier pc = new ProbitClassifier(numFeatures);

Schließlich wird der Probit-Klassifikator trainiert, wobei die Simplex-Optimierung verwendet wird, um Werte für die Gewichtungen zu finden, sodass die berechneten Ausgabewerte den bekannten Ausgabewerten eng entsprechen.

int maxEpochs = 100; // 100 gives a representative demo
Console.WriteLine("Setting maxEpochs = " + maxEpochs);
Console.WriteLine("Starting training");
double[] bestWeights = pc.Train(trainData, maxEpochs, 0);
Console.WriteLine("Training complete");
Console.WriteLine("\nBest weights found:");
ShowVector(bestWeights, 4, true);

Das Demoprogramm berechnet abschließend die Klassifizierungsgenauigkeit des Modells auf den Trainingsdaten und auf den Testdaten:

...
  double testAccuracy = pc.Accuracy(testData, bestWeights);
  Console.WriteLine("Prediction accuracy on test data = 
    " + testAccuracy.ToString("F4"));
  Console.WriteLine("\nEnd probit binary classification demo\n");
  Console.ReadLine();
} // Main

Die Demo trifft keine Vorhersage für zuvor ungesehene Daten. Eine Vorhersage zu machen könnte so aussehen:

// Slightly older, male, higher kidney score
double[] unknownNormalized = new double[] { 0.25, -1.0, 0.50 };
int died = pc.ComputeDependent(unknownNormalized, bestWeights);
if (died == 0)
  Console.WriteLine("Predict survive");
else if (died == 1)
  Console.WriteLine("Predict die");

Dieser Code geht davon aus, dass die unanhängigen x-Variablen – Alter, Geschlecht und Nierenergebnis – mit den Durchschnittswerten und Standardabweichungen aus dem Trainingsdaten-Normalisierungsprozess normalisiert wurden.

Die ProbitClassifier-Klasse

Die allgemeine Struktur der ProbitClassifier-Klasse sehen Sie in Abbildung 7. Die ProbitClassifier-Definition enthält eine verschachtelte Klasse namens Solution. Die Unterklasse stammt von der IComparable-Schnittstelle ab, sodass ein Array von drei Solution-Objekten automatisch sortiert werden kann, um die beste, andere und schlechteste Lösung anzugeben. Normalerweise bin ich kein Freund von Codierungstechniken, aber in diesem Fall überwiegen die Vorteile angesichts der zusätzlichen Komplexität.

Abbildung 7 Die ProbitClassifier-Klasse

public class ProbitClassifier
{
  private int numFeatures; // Number of independent variables
  private double[] weights; // b0 = constant
  private Random rnd;
  public ProbitClassifier(int numFeatures) { . . }
  public double[] Train(double[][] trainData, int maxEpochs, int seed) { . . }
  private double[] Expanded(double[] centroid, double[] worst) { . . }
  private double[] Contracted(double[] centroid, double[] worst) { . . }
  private double[] RandomSolution() { . . }
  private double Error(double[][] trainData, double[] weights) { . . }
  public void SetWeights(double[] weights) { . . }
  public double[] GetWeights() { . . }
  public double ComputeOutput(double[] dataItem, double[] weights) { . . }
  private static double CumDensity(double z) { . . }
  public int ComputeDependent(double[] dataItem, double[] weights) { . . }
  public double Accuracy(double[][] trainData, double[] weights) { . . }
  private class Solution : IComparable<Solution>
  {
    // Defined here
  }
}

ProbitClassifier hat zwei Ausgabemethoden. Die Methode Compute­Output gibt einen Wert zwischen 0,0 und 1,0 zurück und wird während des Trainings verwendet, um einen Fehlerwert zu berechnen. Die Methode ComputeDependent ist ein Wrapper um ComputeOutput und gibt 0 zurück, wenn die Ausgabe weniger oder gleich 0,5 ist, oder 1, wenn die Ausgabe größer als 0,5 ist. Diese Rückgabewerte werden verwendet, um die Genauigkeit zu berechnen.

Zusammenfassung

Die Probit-Klassifizierung ist eine der ältesten ML-Techniken. Da die Probit-Klassifizierung der logistischen Regression-Klassifikation ähnelt, sollte entweder die eine oder die andere Technik verwendet werden. Da LR etwas leichter zu implementieren ist als Probit, wird die Probit-Klassifizierung seltener verwendet und ist im Laufe der Zeit zu einem ML-Bürger zweiter Klasse geworden. Die Probit-Klassifizierung ist jedoch sehr effektiv und kann eine wertvolle Ergänzung Ihres ML-Toolkits sein.

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Wash. Er arbeitet an verschiedenen Microsoft-Produkten wie Internet Explorer und Bing. Sie erreichen Dr. McCaffrey unterjammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft Research für die Durchsicht dieses Artikels: Nathan Brown und Kirk Olynyk.