Klassifikation und logistische Regression in Java

Problem

Betrug oder nicht

Der Kunde drückt auf „Bezahlen“. Der Shop hat ein paar Millisekunden, um zu entscheiden: Lässt er die Zahlung durch oder sperrt er sie für eine Prüfung? Lässt er einen Betrug durch, verliert er die Ware und zahlt eine Gebühr für die zurückgebuchte Zahlung. Sperrt er einen ehrlichen Kunden, ärgert sich der Kunde und kauft woanders.

Hier ist die Antwort keine Zahl wie die Lieferzeit, sondern „Betrug“ oder „nicht“. Wir haben 20 vergangene Zahlungen. Das Merkmal ist der Betrag im Vergleich zum üblichen des Kunden: 3,0 bedeutet „dreimal so viel wie üblich“. Das Label ist 1 für Betrug und 0 für eine ehrliche Zahlung:

// der Betrag im Vergleich zum üblichen des Kunden: 3.0 ist dreimal so viel
double[] ratios = {0.4, 0.6, 0.7, 0.9, 1.0, 1.1, 1.2, 1.3, 1.5, 2.0, 2.6, 3.2,
        0.8, 3.6, 4.1, 5.0, 6.0, 7.5, 8.2, 9.0};
// 1 = Betrug, 0 = ehrliche Zahlung
int[] fraud = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1};

Die erste Idee ist die Gerade aus der linearen Regression: Die Labels sind 0 und 1, und über 0,5 sperren wir. Gelernt mit demselben Abstieg:

double[] line = trainLine(ratios, fraud, 0.01, 5000);
System.out.printf("Gerade, Zahlung 0.4×: %.2f%n", line[0] * 0.4 + line[1]);
System.out.printf("Gerade, Zahlung 9.0×: %.2f%n", line[0] * 9.0 + line[1]);
// ein kleiner Schritt: 40× ist eine große Zahl
double[] ratios2 = Arrays.copyOf(ratios, ratios.length + 1);
ratios2[ratios.length] = 40.0;
int[] fraud2 = Arrays.copyOf(fraud, fraud.length + 1);
fraud2[fraud.length] = 1;
double[] moved = trainLine(ratios2, fraud2, 0.01, 5000);
report("Gerade", line, ratios2, fraud2);
report("Gerade mit der 40×-Zahlung", moved, ratios2, fraud2);

Gerade, Zahlung 0.4×: 0.03
Gerade, Zahlung 9.0×: 1.24
Gerade: 0.5 bei 3.75×, übersehene Betrugsfälle: 2 von 9
Gerade mit der 40×-Zahlung: 0.5 bei 7.31×, übersehene Betrugsfälle: 5 von 9

Die Gerade sagt 1,24 für eine Zahlung von 9×. Das ist keine Wahrscheinlichkeit: „124 % Betrug“ bedeutet nichts. Das Schlimmere kommt jetzt. Ein Betrug kommt mit dem 40-Fachen des üblichen Betrags. Er ist offensichtlich, und doch kippt er die Gerade so stark, dass ihre Grenze von 3,75× auf 7,31× wandert. Jetzt übersieht die Gerade 5 von 9 Betrugsfällen statt 2. Ein klarer Betrug hat das Modell für alle anderen schlechter gemacht.

Die Idee

Die Antwort ist eine Klasse

Wenn das Modell zwischen ein paar Antworten wählt („Betrug“ oder „ehrlich“, eine „schlechte“ oder „gute“ Bewertung), heißt die Aufgabe Klassifikation, und die Antworten sind Klassen. In der linearen Regression war die Antwort eine Zahl auf einer Geraden. Hier wollen wir etwas anderes: eine Zahl zwischen 0 und 1, die sagt, wie wahrscheinlich der Betrug ist. Damit entscheiden wir dann.

Wir brauchen zwei Dinge:

eine Funktion, die jede Zahl zwischen 0 und 1 quetscht, ohne sie abzuschneiden;
eine Grenze, über der wir die Zahlung sperren.

Die Idee

Die Sigmoid-Funktion

Die Sigmoid-Funktion ist sigmoid(z) = 1 / (1 + e^−z). Ein großes z macht sie fast 1, ein großes negatives z macht sie fast 0, und z = 0 ergibt genau 0,5:

static double sigmoid(double z) {
    return 1 / (1 + Math.exp(-z));
}

for (int z = -4; z <= 4; z += 2) {
    System.out.printf("z = %d: %.2f%n", z, sigmoid(z));
}

z = -4: 0.02
z = -2: 0.12
z = 0: 0.50
z = 2: 0.88
z = 4: 0.98

Egal wie groß z ist, das Ergebnis geht nie über 1. Deshalb kann die Zahlung von 40× die Kurve nicht so „ziehen“ wie die Gerade: Für sie sagt die Sigmoid-Funktion schon fast 1, und es gibt nichts mehr zu korrigieren.

Sieh es dir an

Logistische Regression

Das Modell ist dieselbe Gerade, nur durch die Sigmoid-Funktion geschickt. Zuerst berechnet es einen Score: w · x + b, wie in der linearen Regression. Dann macht die Sigmoid-Funktion daraus eine Wahrscheinlichkeit p. Zum Schluss entscheidet der Schwellenwert: p ≥ 0,5 heißt „sperren“.

static double sigmoid(double z) {
    return 1 / (1 + Math.exp(-z));
}

static boolean block(double ratio, double w, double b,
                     double threshold) {
    double score = w * ratio + b;
    double p = sigmoid(score);
    return p >= threshold;
}

Das ist die logistische Regression. Der Name führt in die Irre: Sie sagt keine Zahl voraus, sondern eine Klasse. „Regression“ heißt sie wegen der Geraden im Inneren.

Mit den gelernten w und b (wie, steht auf der nächsten Karte) für drei neue Zahlungen:

double[] m = trainLogistic(ratios, fraud, 0.1, 3000);
double w = m[0], b = m[1];
for (double ratio : new double[] {1.0, 3.0, 5.0}) {
    double p = sigmoid(w * ratio + b);
    String verdict = block(ratio, w, b, 0.5) ? "sperren" : "durchlassen";
    System.out.printf("%.1f×: Betrugswahrscheinlichkeit %.2f → %s%n", ratio, p, verdict);
}

1.0×: Betrugswahrscheinlichkeit 0.06 → durchlassen
3.0×: Betrugswahrscheinlichkeit 0.46 → durchlassen
5.0×: Betrugswahrscheinlichkeit 0.91 → sperren

Eine Zahlung von 3× ergibt 0,46: verdächtig, aber unter dem Schwellenwert. Die Zahl zwischen 0 und 1 ist auch für sich nützlich. Der Shop kann 0,46 ohne Fragen durchlassen, bei 0,6 die Bank um eine Bestätigung bitten (3-D Secure) und 0,95 sperren.

Sieh es dir an

Gelernt mit demselben Abstieg

Wie werden w und b gefunden? Genau wie in der Lektion über den Gradientenabstieg: Wir starten bei null, berechnen für jede Zahlung, wie falsch das Modell liegt, und bewegen die Gewichte ein Stück gegen die Steigung. Hier ist das Training der Geraden aus dem Problem und daneben das der logistischen:

static double[] trainLine(double[] xs, int[] ys, double rate, int epochs) {
    double w = 0, b = 0;
    int n = xs.length;
    for (int epoch = 0; epoch < epochs; epoch++) {
        double gw = 0, gb = 0;
        for (int i = 0; i < n; i++) {
            double p = w * xs[i] + b;
            gw += (p - ys[i]) * xs[i];
            gb += p - ys[i];
        }
        w -= rate * gw / n;
        b -= rate * gb / n;
    }
    return new double[] {w, b};
}

static double[] trainLogistic(double[] xs, int[] ys, double rate, int epochs) {
    double w = 0, b = 0;
    int n = xs.length;
    for (int epoch = 0; epoch < epochs; epoch++) {
        double gw = 0, gb = 0;
        for (int i = 0; i < n; i++) {
            double p = sigmoid(w * xs[i] + b); // die einzige Zeile, die abweicht
            gw += (p - ys[i]) * xs[i];
            gb += p - ys[i];
        }
        w -= rate * gw / n;
        b -= rate * gb / n;
    }
    return new double[] {w, b};
}

Nur eine Zeile ist anders: Die Vorhersage geht durch die Sigmoid-Funktion. Der Schritt (p − y) · x ist derselbe. Bekam ein Betrug 0,9, ist der Fehler klein, und die Gewichte bewegen sich kaum. Bekam er 0,1, ist der Fehler groß und der Schritt auch.

Um zu sehen, dass ein Modell lernt, messen wir seinen Fehler. Für „ja“ und „nein“ ist das Maß der Log-Loss: wie überrascht das Modell von der richtigen Antwort ist. Warum nicht der mittlere quadratische Fehler, steht unter „Mehr“ am Ende.

static double logLoss(double[] xs, int[] ys, double w, double b) {
    double sum = 0;
    for (int i = 0; i < xs.length; i++) {
        double p = sigmoid(w * xs[i] + b);
        sum -= ys[i] == 1 ? Math.log(p) : Math.log(1 - p);
    }
    return sum / xs.length;
}

for (int epochs : new int[] {10, 100, 1000, 3000}) {
    double[] m = trainLogistic(ratios, fraud, 0.1, epochs);
    System.out.printf("Epoche %d: Verlust %.4f, w = %.4f, b = %.4f%n",
            epochs, logLoss(ratios, fraud, m[0], m[1]), m[0], m[1]);
}

Epoche 10: Verlust 0.5895, w = 0.2139, b = -0.1837
Epoche 100: Verlust 0.3899, w = 0.5246, b = -1.4580
Epoche 1000: Verlust 0.2906, w = 1.1696, b = -3.6490
Epoche 3000: Verlust 0.2897, w = 1.2624, b = -3.9459

Der Verlust sinkt und bleibt bei etwa 0,29 stehen. Die Gewichte erreichen w = 1,26 und b = −3,95. Die Sigmoid-Funktion überschreitet 0,5, wo der Score 0 ist, also bei x = −b / w ≈ 3,13×. Und die Zahlung von 40× aus dem Problem?

double[] ratios2 = Arrays.copyOf(ratios, ratios.length + 1);
ratios2[ratios.length] = 40.0;
int[] fraud2 = Arrays.copyOf(fraud, fraud.length + 1);
fraud2[fraud.length] = 1;
report("Sigmoid", trainLogistic(ratios, fraud, 0.1, 3000), ratios2, fraud2);
report("Sigmoid mit der 40×-Zahlung", trainLogistic(ratios2, fraud2, 0.1, 3000), ratios2, fraud2);

Sigmoid: 0.5 bei 3.13×, übersehene Betrugsfälle: 1 von 9
Sigmoid mit der 40×-Zahlung: 0.5 bei 3.13×, übersehene Betrugsfälle: 1 von 9

Die Grenze wandert nicht. Der einzige übersehene Betrug ist weiterhin der bei 0,8×: eine kleine Zahlung, mit der der Dieb prüft, ob die Karte funktioniert. Nach dem Betrag sieht sie aus wie die ehrlichen, und kein Schwellenwert auf diesem Betrag fängt sie. Dafür braucht es ein anderes Merkmal (ein neues Land, ein neues Gerät, die Nachtzeit).

Sieh es dir an

Die Sigmoid-Funktion und der Schwellenwert

static double sigmoid(double z) {
    return 1 / (1 + Math.exp(-z));
}

static boolean block(double ratio, double w, double b,
                     double threshold) {
    double score = w * ratio + b;
    double p = sigmoid(score);
    return p >= threshold;
}

Schritt für Schritt, in Worten

Die 20 Zahlungen: Von links nach rechts steht der Betrag im Vergleich zum üblichen. Betrug ist oben (1), ehrliche Zahlungen unten (0).
Eine Gerade durch die Nullen und Einsen: Bei 9× sagt sie 1,24. Das ist keine Wahrscheinlichkeit.
Die Sigmoid-Funktion biegt die Gerade zwischen 0 und 1. Sie überschreitet 0,5, wo der Score 0 ist: bei 3,13×.
Jede Zahlung bekommt ihre Wahrscheinlichkeit und setzt sich auf die Kurve. Rote sind Betrug, grüne ehrlich.
Schwellenwert 0,5: Darüber sperren wir, darunter lassen wir durch. Übersehene Betrugsfälle: 1, gesperrte ehrliche Kunden: 1.
Schwellenwert 0,3 ist strenger: übersehene Betrugsfälle: 1, gesperrte ehrliche Kunden: 2.
Schwellenwert 0,7 ist weicher: übersehene Betrugsfälle: 2, gesperrte ehrliche Kunden: 0.
Das Modell liefert eine Wahrscheinlichkeit, und der Schwellenwert ist eine Entscheidung: Ein niedrigerer fängt mehr Betrug und sperrt mehr ehrliche Kunden.

Die Gerade geht über 1 und unter 0. Die Sigmoid-Funktion bleibt dazwischen, und die waagerechte Schwellenwert-Linie teilt die Zahlungen in „sperren“ und „durchlassen“. Sinkt der Schwellenwert, kommen weniger Betrugsfälle durch, aber es werden auch mehr ehrliche Kunden gesperrt.

Probier es aus

Ergänze

Welche einzelne Zeile macht aus dem Training der Geraden die logistische Regression?

for (int i = 0; i < n; i++) {
    double p = (w * xs[i] + b);
    gw += (p - ys[i]) * xs[i];
    gb += p - ys[i];
}

Probier es aus

Sage die Ausgabe voraus

Das Modell hat w = 1,26 und b = −3,95, und der Schwellenwert ist 0,5. Was gibt es für Zahlungen von 1,5×, 3,0× und 3,5× aus?

double w = 1.26, b = -3.95;
for (double ratio : new double[] {1.5, 3.0, 3.5}) {
    System.out.println(block(ratio, w, b, 0.5) ? "sperren" : "durchlassen");
}

Antwort

durchlassen / sperren / sperren

durchlassen / durchlassen / sperren

durchlassen / durchlassen / durchlassen

Die Idee

Der Schwellenwert ist eine Geschäftsentscheidung

Das Modell liefert eine Wahrscheinlichkeit. Was wir damit tun, entscheidet der Schwellenwert, und das Modell lernt ihn nicht. Hier sind dieselben 20 Zahlungen bei vier Schwellenwerten:

for (double threshold : new double[] {0.3, 0.5, 0.7, 0.9}) {
    int missed = 0, blocked = 0;
    for (int i = 0; i < ratios.length; i++) {
        boolean stop = block(ratios[i], w, b, threshold);
        if (fraud[i] == 1 && !stop) missed++;
        if (fraud[i] == 0 && stop) blocked++;
    }
    System.out.printf("Schwellenwert %.1f: übersehene Betrugsfälle %d, gesperrte ehrliche %d%n",
            threshold, missed, blocked);
}

Schwellenwert 0.3: übersehene Betrugsfälle 1, gesperrte ehrliche 2
Schwellenwert 0.5: übersehene Betrugsfälle 1, gesperrte ehrliche 1
Schwellenwert 0.7: übersehene Betrugsfälle 2, gesperrte ehrliche 0
Schwellenwert 0.9: übersehene Betrugsfälle 3, gesperrte ehrliche 0

Ein niedriger Schwellenwert ist streng: Bei 0,3 übersehen wir 1 Betrug, sperren aber 2 ehrliche Kunden. Ein hoher Schwellenwert ist weich: Bei 0,9 sperren wir keinen ehrlichen Kunden, übersehen aber 3 Betrugsfälle. Einen Schwellenwert ohne Fehler gibt es nicht, weil sich Betrug und ehrliche Zahlungen überlappen.

Welcher Schwellenwert ist der richtige? Das hängt davon ab, was jeder Fehler kostet. Ein übersehener Betrug über 300 € kostet 300 € plus die Gebühr. Ein gesperrter ehrlicher Kunde kostet einen verärgerten Menschen, einen Anruf beim Support und manchmal einen verlorenen Kunden. Wie man die beiden mit Zahlen vergleicht, wenn Betrug 1 von 100 ist, steht in der nächsten Lektion.

Probier es aus

Finde den Fehler

Ein Kollege schreibt die Sigmoid-Funktion direkt in block. Seine Tests benutzen Betrugsfälle und laufen durch. Am Freitag sperrt der Shop jede Zahlung, auch die ehrlichen. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann es wehtut

Die logistische Regression ist eine gute erste Lösung: Sie ist schnell, leicht zu erklären („wir haben gesperrt, weil der Betrag das Sechsfache des üblichen ist“) und liefert eine Wahrscheinlichkeit. Hier steht, wann sie nicht reicht oder schadet:

Es gibt eine einzige Grenze. Das Modell sperrt über einem Schwellenwert auf einer gewichteten Summe der Merkmale. Liegt das Gefährliche in der Mitte (weder sehr kleine noch sehr große Beträge), kann eine Grenze es nicht abtrennen. Du brauchst ein anderes Merkmal oder ein anderes Modell, zum Beispiel einen Baum oder ein neuronales Netz (das nächste Modul).
Die Wahrscheinlichkeit ist so wahr wie die Daten. Hier sind 8 von 20 Zahlungen Betrug, weil wir so etwas zum Lernen haben. Im echten Strom sind es etwa 1 von 100. Ein Modell, das mit 40 % Betrug trainiert wurde, sieht Betrug zu oft. Das ist die nächste Lektion.
Eine Regel, die Gesetz ist, wird nicht gelernt. „Wir nehmen keine Karten aus einem Land unter Sanktionen an“ ist ein if, kein Modell. Das Modell ist für das, was du nicht als Regel schreiben kannst.
Ein Merkmal, das es zum Zeitpunkt der Entscheidung nicht gibt. „Der Kunde hat die Zahlung angefochten“ ist ein großartiges Betrugsmerkmal, kommt aber Wochen nach der Zahlung. Steckt es in den Trainingsdaten, sieht das Modell ausgezeichnet aus und ist bei der Entscheidung blind.
Entscheidungen über Menschen. Kredit, Arbeit, Versicherung: Dort muss das Modell gegenüber Gruppen von Menschen fair und erklärbar sein. Das ist ein eigenes Thema und oft das Gesetz.

Genauer, für Neugierige

Warum Log-Loss und nicht MSE. Der Log-Loss für eine Zahlung ist −log(p), wenn sie Betrug ist, und −log(1 − p), wenn sie ehrlich ist. Sagt das Modell 0,01 für einen echten Betrug, ist der Fehler −log(0,01) ≈ 4,6. Beim MSE ist derselbe Fehler nur (1 − 0,01)² ≈ 0,98. Der Log-Loss bestraft eine selbstsichere falsche Antwort viel härter. Und die Steigung des Log-Loss nach w ist genau (p − y) · x, deshalb ist der Code so kurz. Mit Sigmoid-Funktion und MSE hat die Steigung einen zusätzlichen Faktor p · (1 − p), der fast 0 wird, wenn das Modell sicher und falsch liegt: Das Lernen stoppt genau dann, wenn es am schnellsten sein sollte.

Warum die Schritte verschieden sind. Die Gerade wird mit einem Schritt von 0,01 gelernt, die logistische Regression mit 0,1. Bei der Geraden wächst der Fehler mit x, und die Zahlung von 40× ergibt eine riesige Steigung: Mit einem Schritt von 0,1 explodiert die Gerade. Bei der Sigmoid-Funktion liegt p − y zwischen −1 und 1, also bringt auch ein großes x sie nicht so durcheinander.

Mehr Merkmale. Mit mehreren Merkmalen (Betrag, ob es Nacht ist, ob das Gerät neu ist) ist der Score w₁ · x₁ + w₂ · x₂ + w₃ · x₃ + b, und der Code ist derselbe mit Arrays von Gewichten. Die Grenze ist eine Gerade in der Ebene oder eine Ebene im Raum: weiterhin eine einzige.

Mehr als zwei Klassen. Für „gut / neutral / schlecht“ gibt es einen Score pro Klasse, und Softmax macht daraus Wahrscheinlichkeiten, die sich zu 1 addieren. Du triffst ihn bei Sprachmodellen wieder: Sie wählen das nächste Token genau so, unter Zehntausenden von Klassen.

Im echten Code. In scikit-learn ist das LogisticRegression, in ML.NET SdcaLogisticRegression, in Tribuo (Java) LogisticRegressionTrainer. Darin steckt dieselbe Idee mit einem schlaueren Abstieg und mit Regularisierung, die du zwei Lektionen später siehst.

String.format und printf schreiben die Zahl nach der Standard-Locale. Mit einer deutschen siehst du 0,46.

Übung

Ist die Bewertung schlecht

Löse die Aufgabe in deinem Editor.

Unter jedem Produkt stehen Bewertungen. Der Shop will, dass die schlechten sofort beim Support landen. Das Merkmal ist, wie viele Wörter aus einer Liste („kaputt“, „zurückgeschickt“, „zu spät“ …) die Bewertung enthält. Du hast 18 Bewertungen: Die Zahl der schlechten Wörter ist 0, 0, 1, 0, 2, 0, 1, 0, 1, 3, 2, 3, 4, 1, 5, 3, 2, 4, und die Labels (1 = schlechte Bewertung) sind zehn Nullen, dann acht Einsen. Trainiere die logistische Regression mit einem Schritt von 0,5 über 2000 Epochen und gib die Wahrscheinlichkeit und die Entscheidung (Schwellenwert 0,5) für eine Bewertung mit 0 bis 5 schlechten Wörtern aus.

schlechte Wörter: 0 → 0.05, gut
schlechte Wörter: 1 → 0.20, gut
schlechte Wörter: 2 → 0.52, schlecht
schlechte Wörter: 3 → 0.83, schlecht
schlechte Wörter: 4 → 0.96, schlecht
schlechte Wörter: 5 → 0.99, schlecht

Eine Bewertung mit 2 schlechten Wörtern liegt auf der Kante: 0,52. Dort liegen auch die guten Bewertungen, die sagen „nicht kaputt, aber zu spät“.

Weitere Aufgaben

Ein anderer Schwellenwert. Der Support will alles Verdächtige sehen. Bei welchem Schwellenwert bekommt er auch die Bewertungen mit 1 schlechtem Wort?
Ein neues Merkmal. Füge die Sterne (1 bis 5) als zweites Merkmal hinzu: w₁ · Wörter + w₂ · Sterne + b. Wie stark ändert sich die Wahrscheinlichkeit bei 2 schlechten Wörtern und 5 Sternen?

Test

Teste dich

1. Warum ist eine Gerade, die auf den Labels 0 und 1 gelernt wurde, ein schlechtes Modell für Betrug?Eine Gerade sagt immer 0,5Eine Gerade lässt sich nicht mit dem Gradientenabstieg lernenSie liefert Zahlen unter 0 und über 1, und eine sehr große Zahlung kippt sie so, dass sie anfängt, Betrug zu übersehen

2. Was macht die Sigmoid-Funktion?Sie macht aus jeder Zahl einen Wert zwischen 0 und 1: Eine große wird fast 1, eine negative fast 0, und null ist 0,5Sie rundet die Zahl auf 0 oder 1Sie sortiert die Zahlungen nach dem Betrag

3. Was ist anders, wenn du statt der Geraden die logistische Regression trainierst?Alles: Man braucht einen ganz anderen AlgorithmusNur eine Zeile: Die Vorhersage geht durch die Sigmoid-Funktion. Der Schritt nach unten ist derselbeDie logistische Regression wird nicht gelernt, sie wird von Hand geschrieben

4. Die Bank senkt den Schwellenwert von 0,5 auf 0,3. Was passiert?Es werden mehr Zahlungen gesperrt: Mehr Betrug wird erwischt, aber auch mehr ehrliche Kunden werden gesperrtDas Modell wird für alle genauerNichts ändert sich, denn das Modell ist dasselbe

5. Wann ist die logistische Regression nicht das richtige Werkzeug?Wenn sich Betrug nicht mit einem Schwellenwert auf einer gewichteten Summe der Merkmale trennen lässt, zum Beispiel „verdächtig nur in der Mitte“Wenn die Daten in Euro sindWenn die Antwort „ja“ oder „nein“ ist

Klassifikation: Betrug oder nicht

Cookies