Zum Inhalt
wannacode

Die Ziffern auf dem Kassenbon

Kurz gesagt: Die Ziffernerkennung mit einem neuronalen Netz macht aus dem Bild Pixel als Merkmale, und ein Netz mit einem Neuron pro Ziffer lernt zu sagen, welche Ziffer es ist.

Problem

Die Summe aus einem Foto

Für eine Rückgabe schickt der Kunde ein Foto des Kassenbons, und das System muss die Summe lesen. Die Kasse druckt die Ziffern in einer Schrift, also sieht es einfach aus: Vergleiche die Pixel mit der Schrift, fertig.

Aber Papier knittert, Tinte verblasst, und auf dem Foto sind Flecken. Hier ist die 7 aus der Schrift und drei Siebenen von echten Kassenbons:

printSide([show(pixels(DIGITS[7])), show(trainX[7]), show(trainX[17]), show(trainX[27])]);
Ausgabe
#####   #####   #####   #####
....#   ....#   ....#   ....#
...#.   ...##   .....   ...#.
..#..   ..#..   #.#..   ..##.
..#..   ..#..   ..#..   #.##.

Der dritten 7 fehlt ein Pixel in der mittleren Zeile, die vierte hat unten zusätzliche Tinte. Eine Regel „es ist eine 7, wenn diese 9 Pixel Tinte sind“ bricht beim ersten Fleck. Und du kannst nicht für jeden möglichen Fleck eine Regel schreiben.

Die Idee

Die Pixel sind Merkmale

Ein 5 × 5 großes Bild sind 25 Pixel. Reihe sie Zeile für Zeile auf, und du hast 25 Zahlen: 1 für Tinte, 0 für leer. Das sind Merkmale, genau wie die Entfernung und das Gewicht einer Bestellung. Ein Bild zu erkennen ist Klassifikation mit 25 Merkmalen und 10 Klassen, den Ziffern 0 bis 9. Das ist Bildklassifikation.

Das Netz ist eine Schicht aus 10 Neuronen, eines pro Ziffer. Jedes Neuron hat für jedes Pixel ein Gewicht: Seine Summe ist groß, wenn die Tinte dort ist, wo seine Ziffer Tinte hat.

Die zehn Summen werden mit Softmax zu Wahrscheinlichkeiten: Jede Summe wird zu eˢ, dann wird jede Zahl durch die Summe aller geteilt. Die Zahlen sind positiv und ergeben zusammen 1. Die größte ist die Antwort, und ihre Größe sagt, wie sicher das Netz ist.

Das Training ist die Schleife aus der vorigen Lektion: Epochen, Mischen, Batches, ein Schritt. Der Fehler für ein Bild ist −ln(p) der richtigen Ziffer: 0, wenn das Netz die richtige Antwort zu 100 % gibt, und groß, wenn es ihr wenig gibt.

Die Daten: 60 Ziffern zum Training (6 von jeder) und 30 für den Test (3 von jeder), alle aus der Schrift mit Flecken. Jedes Pixel kippt mit einer Wahrscheinlichkeit von 8 %, im Durchschnitt zwei Pixel pro Ziffer.

Sieh es dir an

Die Daten und das Netz

Die Schrift steht im Code als Text, # ist Tinte:

// die Ziffern der Kassenschrift: 5 × 5 Pixel, # ist Tinte
const DIGITS = [
  [".###.", "#...#", "#...#", "#...#", ".###."],
  ["..#..", ".##..", "..#..", "..#..", ".###."],
  [".###.", "#...#", "..##.", ".#...", "#####"],
  ["####.", "....#", ".###.", "....#", "####."],
  ["#..#.", "#..#.", "#####", "...#.", "...#."],
  ["#####", "#....", "####.", "....#", "####."],
  [".###.", "#....", "####.", "#...#", ".###."],
  ["#####", "....#", "...#.", "..#..", "..#.."],
  [".###.", "#...#", ".###.", "#...#", ".###."],
  [".###.", "#...#", ".####", "....#", ".###."],
];

Ein Bild wird zu Merkmalen, die Flecken kommen vom Generator, und die Merkmale werden wieder zu einem Bild, damit wir sie ausgeben können:

// das Bild als 25 Merkmale: Zeile für Zeile, 1 für Tinte, 0 für leer
function pixels(rows) {
  const x = [];
  for (let r = 0; r < 5; r++)
    for (let c = 0; c < 5; c++) x.push(rows[r][c] === "#" ? 1 : 0);
  return x;
}


// ein Fleck oder verblasste Tinte: Jedes Pixel kippt mit einer Wahrscheinlichkeit von 8 %
const smudge = (x, rng) => x.map((v) => (rng.next() < 0.08 ? 1 - v : v));


// die Merkmale zurück als Bild
const show = (x) =>
  [0, 1, 2, 3, 4].map((r) => x.slice(r * 5, r * 5 + 5).map((v) => (v > 0.5 ? "#" : ".")).join(""));


// mehrere Bilder nebeneinander
function printSide(pics) {
  for (let r = 0; r < 5; r++) console.log(pics.map((pic) => pic[r]).join("   "));
}

Der Generator ist der aus der vorigen Lektion, mit Seed 7. Zuerst kommen die 60 Trainingsziffern, dann die 30 Testziffern:

class Rng {
  constructor(seed) {
    this.state = seed;
  }


  // die nächste Zahl zwischen 0 und 1; ein Seed liefert immer dieselben Zahlen
  next() {
    this.state = (this.state * 48271) % 2147483647;
    return this.state / 2147483647;
  }
}
const rng = new Rng(7);
const trainY = Array.from({ length: 60 }, (_, n) => n % 10);
const trainX = trainY.map((d) => smudge(pixels(DIGITS[d]), rng));
const testY = Array.from({ length: 30 }, (_, n) => n % 10);
const testX = testY.map((d) => smudge(pixels(DIGITS[d]), rng));

Das Netz: 10 × 25 Gewichte und 10 Biases. predict berechnet die zehn Summen und macht daraus Wahrscheinlichkeiten. Vor exp wird von jeder Summe die größte abgezogen: Das Ergebnis ist dasselbe, aber exp läuft bei großen Summen nicht über. In step ist die Steigung von Neuron k nach seiner Summe p[k] − 1 für die richtige Ziffer und p[k] für die anderen: Das richtige Neuron wird nach oben gedrückt und die anderen nach unten, um so viel, wie sie falsch lagen.

class Net {
  // kleine zufällige Gewichte; die Biases bleiben 0
  constructor(rng) {
    this.w = Array.from({ length: 10 }, () =>
      Array.from({ length: 25 }, () => (rng.next() * 2 - 1) * 0.1)); // ein Gewicht für jedes Pixel bei jedem der 10 Neuronen
    this.b = new Array(10).fill(0);
  }


  // die zehn Wahrscheinlichkeiten (Softmax): Sie ergeben zusammen 1
  predict(x) {
    const p = [];
    for (let k = 0; k < 10; k++) {
      let s = this.b[k];
      for (let i = 0; i < 25; i++) s += this.w[k][i] * x[i];
      p.push(s);
    }
    const top = Math.max(...p);
    let total = 0;
    for (let k = 0; k < 10; k++) {
      p[k] = Math.exp(p[k] - top);
      total += p[k];
    }
    for (let k = 0; k < 10; k++) p[k] /= total;
    return p;
  }


  // der Fehler: der Mittelwert von −ln(p) der richtigen Antwort
  loss(xs, ys) {
    let total = 0;
    for (let n = 0; n < xs.length; n++) total -= Math.log(this.predict(xs[n])[ys[n]]);
    return total / xs.length;
  }


  // ein Schritt pro Batch: die Steigung von Neuron k ist p[k] − 1 für die richtige Ziffer, p[k] für die anderen
  step(xs, ys, batch, rate) {
    const gw = Array.from({ length: 10 }, () => new Array(25).fill(0));
    const gb = new Array(10).fill(0);
    for (const n of batch) {
      const p = this.predict(xs[n]);
      for (let k = 0; k < 10; k++) {
        const d = p[k] - (k === ys[n] ? 1 : 0);
        gb[k] += d;
        for (let i = 0; i < 25; i++) gw[k][i] += d * xs[n][i];
      }
    }
    for (let k = 0; k < 10; k++) {
      this.b[k] -= (rate * gb[k]) / batch.length;
      for (let i = 0; i < 25; i++) this.w[k][i] -= (rate * gw[k][i]) / batch.length;
    }
  }
}

Probier es aus

Sag die Ausgabe voraus

Was gibt das Programm aus? x[r * 5 + 2] ist das Pixel in Zeile r und Spalte 2 (von 0 gezählt).

const x = pixels(DIGITS[7]);
console.log([0, 1, 2, 3, 4].map((r) => x[r * 5 + 2]).join(" "));
Antwort

Sieh es dir an

Das Training, und eine Ziffer aus der Nähe

60 Epochen, Batches von 10, Rate 0,5. Alle 10 Epochen gibt das Programm den Fehler aus und wie viele Ziffern auf dem Trainings- und auf dem Testsatz richtig sind:

const net = new Net(rng);
const order = [...trainX.keys()];
console.log("Epoche  Fehler  Training  Test");
for (let epoch = 1; epoch <= 60; epoch++) {
  shuffle(order, rng);
  for (let start = 0; start < order.length; start += 10)
    net.step(trainX, trainY, order.slice(start, start + 10), 0.5);
  if (epoch % 10 === 0) {
    const right = `${correct(net, trainX, trainY)}/${trainX.length}`;
    const test = `${correct(net, testX, testY)}/${testX.length}`;
    const loss = net.loss(trainX, trainY).toFixed(3);
    console.log(String(epoch).padStart(6) + loss.padStart(8) + right.padStart(10) + test.padStart(6));
  }
}
Ausgabe
Epoche  Fehler  Training  Test
    10   0.268     59/60 28/30
    20   0.128     60/60 29/30
    30   0.084     60/60 29/30
    40   0.063     60/60 29/30
    50   0.050     60/60 29/30
    60   0.042     60/60 29/30

Nach 20 Epochen trifft das Netz alle 60 Trainingsziffern und 29 von 30 auf dem Testsatz. Der Fehler fällt weiter, weil das Netz sicherer wird, aber die Testziffer, die es verfehlt, bleibt dieselbe.

Hier siehst du, was mit einer Ziffer passiert. Die Pixel gehen hinein, jedes Neuron addiert seine Gewichte über sie, und Softmax macht aus den Summen Wahrscheinlichkeiten:

// die zehn Wahrscheinlichkeiten (Softmax): Sie ergeben zusammen 1
predict(x) {
  const p = [];
  for (let k = 0; k < 10; k++) {
    let s = this.b[k];
    for (let i = 0; i < 25; i++) s += this.w[k][i] * x[i];
    p.push(s);
  }
  const top = Math.max(...p);
  let total = 0;
  for (let k = 0; k < 10; k++) {
    p[k] = Math.exp(p[k] - top);
    total += p[k];
  }
  for (let k = 0; k < 10; k++) p[k] /= total;
  return p;
}


const net = train(trainX, trainY, rng);
const shifted = pixels(shift(DIGITS[1]));
for (const x of [testX[17], shifted]) {
  printSide([show(x)]);
  const p = net.predict(x);
  for (let k = 0; k < 10; k++) {
    const bar = "█".repeat(Math.round(p[k] * 20));
    const pct = (p[k] * 100).toFixed(1).padStart(5);
    console.log(`${k} ${bar.padEnd(20)} ${pct}%`);
  }
  console.log(`→ ${best(p)}`);
}
Schritt für Schritt, in Worten
  1. Eine 7 aus dem Testsatz, mit einem Fleck unten links. Für das Netz sind das 25 Zahlen: 1 für Tinte, 0 für leer.
  2. Jedes der 10 Neuronen addiert seine Gewichte über den Tintenpixeln. Das Neuron für die 7 hat die größte Summe: 6,68.
  3. Softmax: e hoch jede Summe, geteilt durch die Gesamtsumme. Die zehn Balken ergeben zusammen 100 %.
  4. Der größte Balken ist die Antwort: 7 mit 98,4 %. Der Fleck hat nicht gestört.
  5. Die 1 aus der Schrift, ohne Fleck, ein Pixel nach rechts gedruckt. Ihre Tinte steht in der vierten Spalte.
  6. Das Netz sagt 4 mit 57,1 %, und die 1 bekommt nur 4,4 %. Die Gewichte der 4 warten genau in dieser Spalte auf Tinte.
  7. Jedes Gewicht hängt an einem Pixel. Flecken hat das Netz zu ignorieren gelernt; eine Verschiebung um ein Pixel hat es nie gesehen.
const net = train(trainX, trainY, rng);
const shifted = pixels(shift(DIGITS[1]));
for (const x of [testX[17], shifted]) {
  printSide([show(x)]);
  const p = net.predict(x);
  for (let k = 0; k < 10; k++) {
    const bar = "█".repeat(Math.round(p[k] * 20));
    const pct = (p[k] * 100).toFixed(1).padStart(5);
    console.log(`${k} ${bar.padEnd(20)} ${pct}%`);
  }
  console.log(`→ ${best(p)}`);
}
Ausgabe
#####
....#
...#.
..#..
#.#..
0                        0.1%
1                        0.0%
2                        0.2%
3                        0.4%
4                        0.0%
5                        0.7%
6                        0.0%
7 ████████████████████  98.4%
8                        0.1%
9                        0.1%
→ 7
...#.
..##.
...#.
...#.
..###
0                        0.2%
1 █                      4.4%
2 ███                   15.4%
3                        2.3%
4 ███████████           57.1%
5                        0.6%
6 █                      5.0%
7 █                      7.1%
8 █                      2.9%
9 █                      5.0%
→ 4

Die 7 aus dem Testsatz hat unten links einen Fleck, und das Netz sagt trotzdem 7 mit 98,4 %. Das zweite Bild ist die 1 aus der Schrift, ein Pixel nach rechts gedruckt. Kein einziger Fleck, und das Netz sagt 4 mit 57,1 %. Darauf kommen wir zurück.

Die Idee

Worauf jedes Neuron schaut

Jedes Neuron hat 25 Gewichte, eines pro Pixel, also sind seine Gewichte auch ein 5 × 5 großes Bild. Ein großes positives Gewicht bedeutet „Tinte hier spricht für mich“, ein großes negatives „Tinte hier spricht gegen mich“:

// # starkes „ja“, + „ja“, . egal, - „nein“, = starkes „nein“
function symbol(v) {
  if (v > 0.8) return "#";
  if (v > 0.25) return "+";
  if (v < -0.8) return "=";
  if (v < -0.25) return "-";
  return ".";
}


const weightMap = (weights) =>
  [0, 1, 2, 3, 4].map((r) => weights.slice(r * 5, r * 5 + 5).map(symbol).join(""));
const net = train(trainX, trainY, rng);
console.log("  0       1       7  ");
printSide([0, 1, 7].map((d) => weightMap(net.w[d])));
Ausgabe
  0       1       7
.+.--   .-+=.   #+++#
+.-.#   -##.-   -.--+
#===#   --+=-   -==+.
#--.+   -+#.-   ..#.-
.+.--   -+.+-   -=+-.

Das Neuron für die 0 will Tinte in den beiden äußeren Spalten und ist stark gegen Tinte in der Mitte der dritten Zeile: Dort ist die 0 leer, während 8, 3 und 2 Tinte haben. Das Neuron für die 7 will die ganze obere Zeile und die dritte Spalte unten. Das Neuron für die 1 will die zwei Pixel oben in der Mitte (.##.) und ist gegen die untere linke Ecke, wo 2 und 5 Tinte haben.

Niemand hat dem Netz gesagt, wo der Strich der 7 ist. Die Gewichte wurden allein aus den Beispielen gefunden. Sie sind keine Kopie der Ziffer: Ein Neuron schaut auch darauf, wo sich seine Ziffer von den anderen unterscheidet.

Probier es aus

Ergänze

Die letzten Zeilen von Softmax. Wodurch wird jede Zahl geteilt, damit die zehn zusammen 1 ergeben?

for (let k = 0; k < 10; k++) p[k] /= ;

Die Idee

Ein Pixel zur Seite

Die Kasse druckt eine Ziffer manchmal ein wenig zur Seite, und das Foto wird schräg aufgenommen. Hier sind drei Ziffern aus der Schrift, ohne Flecken, um ein Pixel nach rechts verschoben:

// dieselbe Ziffer, ein Pixel nach rechts gedruckt
const shift = (rows) => rows.map((row) => "." + row.slice(0, 4));
const net = train(trainX, trainY, rng);
const digits = [1, 3, 7];
printSide(digits.map((d) => shift(DIGITS[d])));
for (const d of digits) {
  const p = net.predict(pixels(shift(DIGITS[d])));
  console.log(`${d} → ${best(p)} (${(p[best(p)] * 100).toFixed(1)}%)`);
}
Ausgabe
...#.   .####   .####
..##.   .....   .....
...#.   ..###   ....#
...#.   .....   ...#.
..###   .####   ...#.
1 → 4 (57.1%)
3 → 9 (77.7%)
7 → 9 (39.0%)

Das Netz, das 29 von 30 verfleckten Ziffern trifft, liegt bei allen dreien falsch. Von allen zehn verschobenen Ziffern kommt nur die 9 richtig heraus, und mit 53,8 %.

Der Grund liegt in den Gewichten. Jedes Gewicht hängt an einem Pixel an einer Stelle. Das Neuron für die 1 erwartet Tinte in der mittleren Spalte. Die verschobene 1 steht in der vierten Spalte, und Tinte dort erwartet das Neuron für die 4. Für das Netz ist dieselbe Form an anderer Stelle ein anderes Bild: Es weiß nicht, dass es „einen Strich“ gesehen hat, es weiß nur, welche Pixel Tinte sind.

Deshalb müssen die Trainingsdaten wie die echten Daten aussehen. Wenn sich Ziffern auf den Fotos verschieben, müssen sich auch die Trainingsbeispiele verschieben. Oder das Netz muss von anderer Art sein, eines, das die Form überall sucht (siehe „Mehr“).

Probier es aus

Finde den Fehler

Ein Kollege schreibt einen Bericht über die Genauigkeit des Netzes und sagt „100 %“. Auf den Kassenbons der Kunden macht das Netz Fehler. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann es schadet

  • Sicher falsch. Der einzige Fehler auf dem Testsatz ist eine 3 mit einem Fleck in der Mitte, die das Netz als 9 mit 91,2 % liest. Die Wahrscheinlichkeit sagt, wie sicher das Netz ist, nicht wie recht es hat. Wenn ein Fehler Geld kostet, wird der Schwellenwert für „sicher“ an einem Testsatz geprüft, und ein Mensch schaut sich die zweifelhaften Ziffern an.
  • Alles, was es nicht gesehen hat. Eine Verschiebung, eine andere Schrift, ein schräges Foto, eine handgeschriebene Ziffer: Das Netz hat nur die Schrift mit Flecken gesehen und weiß nichts anderes. Für das Netz ist jedes Bild eine der zehn Ziffern, auch ein leeres Quadrat oder ein Buchstabe.
  • Wenige Daten. 60 Bilder reichen, weil es eine Schrift gibt und die Ziffern 5 × 5 groß sind. Das Foto eines echten Kassenbons braucht Tausende von Beispielen und ein größeres Netz.
  • Kein Netz nötig. Wenn die Kasse die Summe auch als Text sendet oder einen QR-Code auf den Bon druckt, lies den. Die Erkennung ist für die Fälle, in denen es keinen anderen Weg gibt.
Genauer, für Neugierige

Softmax als Formel. Die Summen der zehn Neuronen sind s₀ … s₉. Die Wahrscheinlichkeit der Ziffer k ist:

p[k] = e^(s[k]) / (e^(s₀) + e^(s₁) + … + e^(s₉))

In Worten: Mache jede Summe mit e hoch der Summe positiv, dann teile durch die Gesamtsumme. Bei zwei Ziffern ist das die Sigmoid-Funktion aus der logistischen Regression: Softmax ist ihre Erweiterung auf mehr Klassen. Die größte Summe abzuziehen ändert das Ergebnis nicht, denn e^(s − m) = e^s / e^m, und e^m kürzt sich weg.

Warum die Steigung p[k] − 1 ist. Der Fehler für ein Bild ist L = −ln(p[y]), wobei y die richtige Ziffer ist (Kreuzentropie). Seine Steigung nach der Summe von Neuron k ist sehr einfach: p[k] − 1 für k = y und p[k] für die anderen. Wenn das Netz die richtige Antwort zu 98 % gibt, ist der Druck nur −0,02. Gibt es sie zu 10 %, ist er −0,9. Von dort geht Backprop wie in den früheren Lektionen weiter zu den Gewichten: Die Steigung nach Gewicht i ist die Steigung nach der Summe mal Pixel i.

Warum es keine verborgene Schicht gibt. Bei 10 Neuronen direkt von den Pixeln gehört jedes Gewicht zu einem Pixel und einer Ziffer, sodass sich die Gewichtskarte lesen lässt. Mit einer verborgenen Schicht trifft das Netz mehr, aber die Karten der verborgenen Neuronen sind eine Mischung aus Teilen mehrerer Ziffern und schwer zu lesen. Probiere es in den Aufgaben aus.

Netze für Bilder. Echte Netze für Bilder sind Convolutional Networks (CNN): Ein kleines Fenster aus Gewichten, sagen wir 3 × 3, gleitet über das ganze Bild und sucht überall dieselbe Form. Ein Strich ist links und rechts ein Strich, deshalb stört eine Verschiebung sie kaum. Das klassische Beispiel ist MNIST: 70.000 handgeschriebene Ziffern, 28 × 28 Pixel. In PyTorch ist das Fenster nn.Conv2d.

Dieselben Zahlen in vier Sprachen. Die Programme geben die Wahrscheinlichkeiten mit einer Nachkommastelle aus, und die Balken sind auf 20 Teile gerundet. Die Lektion prüft, dass kein Balken und kein Gewicht genau auf einer Rundungsgrenze liegt, damit die Ausgabe in Java, C#, Python und JavaScript gleich ist.

Übung

Die Summe auf dem Kassenbon

Löse es in deinem Editor.

Die Summe auf dem Kassenbon ist 12,90 €: die Ziffern 1, 2, 9 und 0. Die Kasse hat die letzte Ziffer ein Pixel nach rechts gedruckt, und das Foto hat Flecken. Mache die vier Bilder (das letzte verschoben, alle mit demselben Generator verfleckt, nach dem Training), erkenne jedes und gib die Ziffer und ihre Wahrscheinlichkeit aus. Liegt die Wahrscheinlichkeit unter 90 %, markiere die Ziffer zur Prüfung von Hand und setze in der Summe ein ? an ihre Stelle.

Ausgabe
Ziffer 1: 1 (97.0%)
Ziffer 2: 2 (94.4%)
Ziffer 3: 9 (90.5%)
Ziffer 4: 7 (37.4%) → von Hand prüfen
Summe: 12,9? € → von Hand prüfen

Die verschobene 0 wird zu einer 7, aber nur mit 37,4 %, und der Schwellenwert fängt sie. Die 9 kommt mit 90,5 % durch, knapp über dem Schwellenwert. Der Schwellenwert macht das Netz nicht klüger, er sagt dir, wann du ihm nicht trauen sollst. Ein Kassenbon mit einem ? geht an einen Menschen, nicht in die Buchhaltung.

Weitere Aufgaben

  • Verschobene Beispiele. Füge den Trainingsdaten jede Ziffer der Schrift um ein Pixel nach links und nach rechts verschoben hinzu und trainiere neu. Wie viele der zehn verschobenen Ziffern trifft es jetzt? Und wie viele auf dem Testsatz?
  • Eine verborgene Schicht. Setze eine verborgene Schicht aus 16 Neuronen mit einer Sigmoid-Funktion zwischen die Pixel und Softmax. Gib die Gewichte von zwei verborgenen Neuronen als Bild aus. Sieht eines von ihnen wie eine Ziffer aus?

Test

Teste dich

1. Wie sieht das Netz ein 5 × 5 großes Bild?
2. Das Netz gibt für die 7 98,4 % und für die anderen Ziffern kleine Zahlen. Wozu summieren sich die zehn Wahrscheinlichkeiten?
3. Die 1 ist ein Pixel nach rechts gedruckt, und das Netz sagt 4 mit 57,1 %. Warum?
4. Ein Kollege meldet 100 % Genauigkeit, gemessen an den 60 Ziffern, aus denen das Netz gelernt hat. Was sagt das über neue Kassenbons?
5. Das Netz liest eine 3 aus dem Testsatz als 9 mit 91,2 %. Was folgt daraus?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·