• Moritz Abdank

Von Nachbarn und deren Merkmalen zur Klassifizierung von Buchstaben

Auf dieser Plattform haben Sie bereits einige Methoden und Modelle kennengelernt, welche versuchen, die menschliche Fähigkeit der Wahrnehmung nachzuahmen. Sie haben gesehen, dass sich diese Fähigkeit nicht so einfach in Form eines Programms implementieren lässt – besonders kausale Zusammenhänge und die Interpretation von Zahlenwerten bereiten Maschinen nämlich große Probleme. Auf der Wissensdrehscheibe haben wir bereits einige typische Anwendungsfälle von AI gezeigt. Ein solcher Anwendungsfall ist der Einsatz von maschinellem Lernen zur Objekterkennung. Objekterkennung ist sowohl für das industrielle Umfeld als auch für alltägliche Anwendungen interessant. Zwei Beispiele von klassischen Anwendungen sind hier die Qualitätssicherung und Fahrassistenzsysteme.


Wir beschäftigen und in diesem Use Case mit einer der ersten praktischen Anwendungen vom maschinellen Lernen: dem Erkennen von handgeschriebenen Ziffern. Dabei Um diese Funktionalität als Programm umsetzen zu können, müssen wir uns mehreren Problematiken annehmen. Wie können wir ein Programm schreiben, das geschriebene Buchstaben richtig erkennt? Wie können wir handgeschriebene und eingescannte Dokumente so verarbeiten, dass anschließend aus der immensen Menge von Pixel Buchstaben, ganze Wörter, Sätze oder der komplette Inhalt in eine verständliche Sprache hervorgehen? Konkret beschäftigen wir uns in diesem Use Case mit zwei sich darauf beziehenden Problemen: Was sind die relevanten visuellen Merkmale handgeschriebener Buchstaben und wie kann man aus diesen Merkmalen erkennen, welcher Buchstabe es tatsächlich ist.


Warum kein CNN?

In diesem Use Case zeigen wir einerseits die Berechnung von visuellen Merkmalen mittels Hauptkomponentenanalyse (PCA, siehe AIAV Video Principal Component Analysis) und beschäftigen uns andererseits mit der der Formulierung von Klassifizierungsfunktionen. PCA haben wir uns dabei in einem anderen Use Case bereits im Kontext von mobilen Robotern angesehen (siehe AIAV Use Case Andocken Autonomer Mobiler Roboter). Anders als bei alternativen Use Cases (siehe Logistic Regression oder Support Vector Machines) nutzen wir hier aber keine mathematische Funktion zur Beschreibung des Klassifikators, sondern greifen auf eine Methode zurück, die ähnlich wie ein Mensch klassifiziert. Wir werden sehen, dass mit „Ähnlichkeiten“ und der Beschreibung dieser Ähnlichkeiten Klassifizierung durchgeführt werden kann.


Typischerweise werden heute Convolutional Neural Networks (CNN, siehe AIAV Video CNN Classifier) für solche Bildverarbeitungsprobleme eingesetzt. Während CNN's gute Leistungsmerkmale für Bildverarbeitungsprobleme aufweisen, resultieren sie auch in einigen Herausforderungen bezüglich der Nachvollziehbarkeit der von ihnen erreichten Ergebnisse. Analog dazu nutzen wir in diesem Use Case simple und erklärbare Methoden und nehmen eine eventuell schlechtere Leistung unserer Lösung in Kauf.


Aufbau des Use Cases

Wie bei anderen auf Lernen basierenden Use Cases benötigen wir einen annotierten Datensatz, welcher als Grundlage fürs Training der Klassifizierung verwendet wird. Es gibt bereits den EMNIST Datensatz, welcher Bilder von Handgeschriebenen Ziffern mit je 28 mal 28 Pixel Auflösung beinhaltet. Dieser Datensatz bildet die Grundlage für unsere Experimente.


Abbildung 1 zeigt dabei unser Vorgehen: Wir erklären zunächst, wie Bilder verarbeitet werden können. Anschließend nutzen wir PCA zur Berechnung von Merkmalen und formulieren basierend auf den Merkmalen die Klassifizierungsfunktion.

Abbildung 1: Vorgehen in diesem Use Case


Vorverarbeitung der Bilder

Bilder werden digital als Ansammlung an Zahlen repräsentiert. Diese sind tabellenartig neben- und übereinander angeordnet. Dabei stellen bei einem Farbbild drei Zahlen (Rot, Grün, Blau) einen Bildpunkt, also einen Pixel, dar. Ein CNN kann diese tabellenartige Struktur direkt nutzen. Die hier vorgestellte Methode macht dies nicht. Wir bauen hier auf Modelle und Methoden der klassischen Statistik und des maschinellen Lernens auf. Diese nutzen einen sogenannten „Vektor“ als Struktur um alle relevanten Zahlen bezüglich eines Beispiels zu beschreiben. Sie können sich einen Vektor als eine Tabelle vorstellen, die nur eine Spalte hat. Um nun unseren EMNIST Bilddatensatz zu verarbeiten, müssen wir für jedes Bild einen Vektor zur Verfügung stellen. Wir tricksen hier, indem wir jedes Bild zerschneiden und die Enden zusammenkleben. Damit haben wir eine Tabelle, welche nur mehr eine Spalte hat. Diese Art der Vorverarbeitung ist in Abbildung 2 dargestellt.

Abbildung 2: Umwandlung einer Bildermatrix in einen Vektor


Extrahieren von Merkmalen

Was ist ein Merkmal, und wozu brauchen wir diese? Diese Frage ist nicht so einfach und lässt sich auf unterschiedliche Arten, je nach Anwendungsfall, beantworten. In unserem Fall besteht jedes Bild aus 28 mal 28 Pixeln. Das heißt, selbst wenn wir nur ein Graustufenbild vorliegen haben, wird jedes unserer Bilder immer noch durch 784 Zahlen beschrieben. Brauchen wir alle Pixel für das Aufstellen einer Klassifizierungsfunktion? Was sind die Relevanten visuellen Anhaltspunkte im Datensatz?


Die Merkmalsextraktion versucht in diesem Fall beide dieser Fragen zu lösen, indem Merkmale (Features in der englischen Literatur) im Datensatz gesucht werden. Die hier angewandte PCA extrahiert visuelle Merkmale, wobei Nutzer*innen die Anzahl der ausgegebenen Merkmale einstellen können. Typischerweise reichen sehr wenige Merkmale aus, um gute Ergebnisse zu erzielen. Basierend auf der Merkmalsextraktion beschreiben wir die Bilder nicht mehr mit Pixel, sondern mittels der Ausprägung von gelernten Merkmalen. Wenden wir die PCA auf den Trainingsdatensatz an und sehen wir uns die Ergebnisse an. Bevor wir die Software starten und die Modelle trainieren – welches Ergebnis erwarten wir uns? Was könnten visuelle Merkmale, also visuelle Grundbausteine, sein?


Wahrscheinlich werden wir linienartige Merkmale erkennen – das ist bei geschriebenen Buchstaben naheliegend. Sehen wir uns das Ergebnis an:

Abbildung 3: Die zehn wichtigsten Merkmale des EMNIST Datensatzes. Die blau umrandeten Merkmale werden im weiteren Verlauf dieses Use Cases zur Erklärung genutzt.


Wie liest man nun solche Bilder? Sehen Sie sich die besonders hellen oder dunklen Bereiche an. An diesen Stellen erwartet sich die PCA eine hohe Variabilität – also dort ändern sich im Datensatz die Pixelwerte erheblich. Rund um die Bereiche, wo sich die geschriebenen Buchstaben befinden, erkennen Sie eine monotone graue Fläche – diese Fläche scheint für uns uninteressant zu sein. Nehmen Sie sich nun Zeit und betrachten Sie die hellen und dunklen Bereiche.


Diese Bereiche sehen wie Teile von Buchstaben aus. Interpretieren Sie diese Bilder folgendermaßen: Wenn Sie alle Merkmale (nicht nur die zehn dargestellten, sondern alle Extrahierten) mit einer bestimmten Gewichtung verstehen, können alle Bilder fast fehlerfrei rekonstruiert werden. Je wichtiger das Merkmal ist (das Maß dafür gibt uns die PCA), desto relevantere Bereiche im Bild werden dadurch dargestellt. Je unwichtiger das Merkmal ist, desto geringer sind die Details, welche durch das Merkmal rekonstruiert werden. Eine Darstellung der Trainingsbilder durch die Merkmale ist also eine alternative Darstellung, wo anstelle von Pixelwerten die Bedeutung des Merkmals im Bild genutzt wird. Basierend auf den zehn gezeigten Merkmalen wird also jedes Bild mit zehn Zahlen beschrieben. Visualisieren wir also diese Darstellung!


Für die Visualisierung müssen wir die dargestellten Daten ein wenig vereinfachen (Sie merken gleich – der menschliche Geist ist nicht für solche Visualisierungen gemacht). Nutzen wir nun nur die ersten beiden Merkmale aus Abbildung 3 (die blau eingerahmten Visualisierungen). Mittels dieser wird jedes Bild durch zwei Zahlen beschrieben. Das können wir gut visualisieren! Abbildung 4 stellt die „Gewichtungen“ dieser Zahlen für die Einträge zweier verschiedener Klassen (also z.B. Bilder, die ein „A“ zeigen und Bilder, die ein „B“ zeigen) exemplarisch dar.

Abbildung 4: Darstellung des Datensatzes. Es sind nur geschriebene „A“ (rote Kreise) und geschriebene „B“ (blaue Kreise) dargestellt. Die offene Frage ist dabei, was im Bild durch den grünen Kreis repräsentiert wird?


Die Darstellung in Abbildung 4 zeigt eine klare Trennung zwischen den zwei wichtigsten Merkmalen von „A“ und „B“ - ob dieser Sachverhalt gegeben ist, werden wir in den Ergebnissen evaluieren. Unter der Annahme, dass die Merkmale trennbar sind, bleibt noch eine Frage offen: wie unterscheiden wir nun tatsächlich zwischen „A“ und „B“? Betrachten Sie den grün markierten Eintrag in Abbildung 4. Wie würden Sie diesen einordnen? Eher in Klass „A“ oder eher in „B“? Diese Frage wird durch Klassifizierungsmodelle formal geklärt.

Vorweg: Die Idee in diesem Use Case ist simpel: wir sehen uns an, wie ähnlich das Beispiel (grüner Punkt) den Trainingsdaten der Klasse „A“ oder „B“ ist.


Das Klassifizierungsmodell

Ein neues Beispiel, also ein neues und unbekanntes Bild, muss zunächst mit der trainierten PCA reduziert werden. Die Schritte sind den oben beschriebenen Schritten identisch: Das Bild wird von als Vektor formatiert und mit der trainierten PCA reduziert. Wenn wir, wie in Abbildung 3, von der Nutzung von zwei Merkmalen ausgehen, ergibt sich ein ähnliches Bild wie in Abbildung 4 – der grüne Punkt ist das neue Beispiel.


Die k-Nearest Neigbor Klassifizierung (kNN) verfolgt dabei einen simplen Ansatz: Das Modell klassifiziert einen neuen Dateneintrag basierend auf den Klassen der am nächsten gelegenen Datenpunkte im beschrifteten Datensatz (den Nachbarn). Der von Nutzer*innen festgelegte k-Wert gibt dabei an, wie viele Nachbarn berücksichtigt werden. Ein k von drei heißt z.B. also, dass mittels der Klassen der drei nächsten Nachbarn abgestimmt wird, zu welcher Klasse der neue Eintrag gehört. Wenn unter diesen k Beispielen mehr Elemente von „A“ vorkommen, dann ist das neue Beispiel auch ein „A“ – und umgekehrt. Abbildung 5 stellt diese Abstimmung dar.

Abbildung 5: Visualisierung für k=3. In diesem Fall wird das neue Beispiel (grüner Punkt) als „B“ klassifiziert.


Implementierung in Software

Wir wollen nun die gelernte Theorie hinter PCA und kNN anwenden und die Ziffernerkennung implementieren. Für unsere Implementierung werden wir rund 4.800 Bilder pro Buchstaben verwenden. Das sind fast 124.800 Bilder, die wir für das Trainieren, Testen und Evaluieren verwenden können. Mit 28 mal 28 Pixeln pro Bild entsteht dadurch eine große Datenmenge, welche wir nach dem Einlesen und Umwandeln in einen Vektor mithilfe von PCA verringern. Wir können somit einen Bildvektor von 784 Einträgen (je 28 mal 28 Pixel) auf nur 15 Einträge reduzieren. Obwohl beim Reduzieren der Dimensionalität Information verloren geht, können wir trotzdem eine akzeptable Genauigkeit erreichen, während wir nur noch mit 1.9% der ursprünglichen Datenmenge arbeiten.

Anschließend wird mittels der scikit-learn Bibliothek das kNN Modell implementiert. Scikit-learn implementiert bereits viele Datenverarbeitungsmethoden, wie PCA und kNN und erlaubt es uns, einfach auf fertige Modelle zuzugreifen ohne sie selbst programmieren zu müssen. Beim Erstellen des Modells ist vor allem der k-Parameter für uns sehr interessant. Wir können dem Modell vorgeben, wie viele seiner Nachbarn für eine zukünftige Entscheidung berücksichtigt werden sollen. In unserem Fall betrachten wir die 3 umliegenden Datenpunkte, wie auch in Abbildung 5 vereinfacht dargestellt ist.


Ergebnisse

Mit unserem Trainingsdatensatz erzielen wir eine Genauigkeit (Accuracy in englischer Fachliteratur) von rund 84%. Wie schon angesprochen, müssen wir bei der Verwendung eines kNNs leider schlechteres Verhalten in Kauf nehmen, da es ein einfacheres (aber auch erklärbares) Modell ist. Die Beschreibung dieses Use Cases hat rund 10.000 Zeichen (als Vereinfachung vernachlässigen wir Zahlen und Sonderzeichen). Stellen wir uns vor, sie wurde nicht am Computer, sondern per Handschrift verfasst und wir wollen den Text von unserer Implementierung digitalisieren lassen. Dann müssen wir leider mit rund 1600 Fehlern rechnen. In der Praxis muss man pro Applikation entscheiden, ob solche Fehler im Einzelfall vertretbar sind oder nicht. Falls die Genauigkeit nicht ausreichen sollte, muss ein komplexeres Modell, wie z.B. ein CNN gewählt werden.




53 Ansichten

Aktuelle Beiträge

Alle ansehen