Computer VisionData-MiningDeep LearningTutorial

Die Mustererkennung-Pipeline

Mustererkennung-Pipeline

Dieser Post fasst die Ideen hinter dem Thema Mustererkennung zusammen und erklärt ein paar Vokabeln, die sehr oft im Mustererkennung-Bereich verwendet werden.

Konkret lernen wir heute kennen:

  • Was ist Mustererkennung überhaupt und wo findet sie Verwendung?
  • Machine Learning: Wie können Computer lernen?
  • Trainingsset und Testset: Warum wir zwei verschiedene Datensätze brauchen,
  • Das Preprocessing: Die Kunst der Datensäuberung,
  • Die Feature Extraction: Geschickte Datenreduzierung auf das Wichtigste,
  • Den Classifier: Das Herz einer jeden Mustererkennungssoftware,

Wir werden uns hier auf sehr abstrakte Konzepte beschränken und kaum konkrete Implementierungen oder gar Pseudo-Code anschauen. Dieser Post soll lediglich dazu dienen einmal ein Gefühl für Mustererkennung zu bekommen.


Muster… Was?

“Mustererkennung ist die Fähigkeit, in einer Menge von Daten Regelmäßigkeiten, Wiederholungen, Ähnlichkeiten oder Gesetzmäßigkeiten zu erkennen.”, so Wikipedia1. Bei der Mustererkennung suchen wir also in einer gegebenen Menge von Daten nach Regeln, um mit Hilfe dieser Regeln neue Informationen zu erlangen.
Stellen wir uns ganz konkret vor, dass wir einen Auftrag von der Deutschen Post bekommen, der wie folgt lautet: “Wir brauchen ein Stück Software, welches die Adressen auf den Paketen automatisch einliest und die Pakete je nach Empfängeradresse wo anders hinschickt.”
Unsere Aufgabe ist es jetzt eine Texterkennungssoftware zu schreiben, was für uns als Anfänger im Gebiet der Mustererkennung natürlich nicht einfach ist. Texterkennungssoftware ist eines der gängigen Beispiele im Bereich Mustererkennung. Genau so gehören aber auch folgende Gebiete zur Musterkennung:

  • Stimmerkennung (Was hat der Benutzer gesagt?)
  • Objekterkennung (Was ist auf dem Bild sichtbar? Hunde? Katzen? Autos?)
  • Wettervorhersage (Wie wird das Wetter morgen? Regnet es?)
  • Aktienkursvorhersage (Wie verhält sich der Kurs? Wird er demnächst steigen? Wann sollte ich (ver-)kaufen?)
  • Produktionsüberwachung (Wann geht mein Produkt kaputt? Welche Schritte müssen wie ablaufen, damit es kaputt geht? Ist das bereits bei der Produktion erkennbar?)
  • Übersetzungsprogramme (Übersetzen von Texten in eine andere Sprache, z.B. Englisch <-> Deutsch)
  • Antivirensysteme (Ist die Datei ein Virus? Wenn ja wie bedrohlich? Kenne ich diese Art von Virus schon?)
  • Vieles mehr

Mustererkennung findet man also praktisch überall und in jedem Teil der Informatik. Mit Sicherheit hat auch jeder schon einmal selbst eine ganz einfache Variante von Mustererkennungssoftware geschrieben.

Aber nun zurück zu unsere Texterkennungssoftware. Die erste Idee, die uns wohl in den Sinn kommt, ist feste Regeln zu definieren, wie eine Zahl/ein Buchstaben aus zu sehen hat. Wir fangen mit den Zahlen an und blenden die Buchstaben fürs Erste komplett aus. Stellen wir doch einfach einmal unsere erste Regel auf: ”Eine Null ist immer ein geschlossener Kreis”.
Das klingt logisch und auf den ersten Blick auch sinnvoll. Wenn unser Programm also eine Ziffer bekommt und sagen soll, was das für eine Ziffer ist, dann erkennen wir die 0 daran, dass alle Pixel, die auf dem Bild sind mit einander verbunden sind und zusammen in einem Kreis liegen.
Um zu erkennen, ob die Pixel in einem Kreis angeordnet sind, gibt es genug Algorithmen, die mehr oder weniger komplex sind. Dieselbe Art von Regeln definieren wir für die anderen Zahlen, so könnte eine 1 immer “ein Strich mit einem Haken” sein. Wir haben jetzt also für jede unserer Ziffern eine andere Regel aufgestellt und nach ersten Tests sieht das alles auch gut aus. Voller Stolz übergeben wir also unsere erste Mustererkennungssoftware der Deutschen Post und freuen uns schon über unsere Prämie.


Soweit so gut… Oder?

Nach kurzer Zeit wird uns die Post mailen und in etwa folgendes schreiben:
“Die Software erkennt praktisch kaum Buchstaben und Nummern, von 100 Buchstaben/Zahlen werden nur rund 2 korrekt erkannt! Totaler Schrott!” Völlig empört und ungläubig nehmen wir also den langen Weg auf uns und fahren direkt in die Zentrale der Poststelle. Nach einigen Hundert falschen Beispielen, glauben wir dann doch dem Auftraggeber und setzen uns zurück ans Reißbrett:

“Aber was war passiert?”

Offensichtlich ist unser Problem zweigeteilt. Zuerst einmal haben wir nicht erkannt, dass unsere Regeln nicht immer funktionieren.Wir haben unsere Software immer nur für Ziffern/Buchstaben getestet, die wir selbst geschrieben haben. Das heißt für unsere 0en war diese Regel vielleicht sogar perfekt und ausreichend. Aber leider muss die Software ja mit jeder beliebigen Handschrift zurecht kommen.

Unser zweites Problem ist aber noch viel schlimmer als das Erste:
Offensichtlich sind unsere definierten Regeln nicht gut genug gewesen. Wir erkennen schnell, dass eine 0 nicht immer ein Kreis ist und erst recht nicht immer geschlossen sein muss. Wenn wir noch etwas darüber nachdenken, fällt auch auf, dass die 0 genau so gut einen Strich durch die Mitte haben könnte, dass die 0 sogar eher eckig sein kann als oval und uns fallen noch viel mehr Spezialfälle ein, die wir nicht bedacht haben. Aber für jeden Fall eine Regel aufzustellen, wäre ein riesiger Haufen Arbeit. Vor allem aber können wir uns nie sicher sein alle Regeln abgedeckt zu haben. Es ist also ziemlich schwer konkrete Regeln, die für alle Fälle funktionieren aufzustellen. Und genau hier kommt Machine Learning zum Zug.


Was ist Machine Learning?

Anstatt genaue Regeln aufzustellen, zeigen wir dem Computer tausende manchmal sogar Millionen Beispiele von einem Objekt in verschiedensten Situationen/Belichtungen/Größen/usw. und hoffen darauf, dass der Algorithmus schlau genug ist, das gemeinsame Muster in den Daten zu erkennen.
Wir bringen dem Computer also Wissen bei, indem wir ihm Beispiele zeigen (und sagen was es ist), ähnlich wie wir ein Kleinkind unterrichten würden. Der Computer soll demnach selbst Regeln aufstellen wie zum Beispiel “0er sind meistens oval” und diese so kombinieren, dass er die verschiedenen Ziffern gut unterscheiden kann. Da wir persönlich jetzt keine bzw. nur noch sehr wenig Regeln per Hand aufstellen müssen, sondern der Computer die Regeln selbstständig findet, können wir natürlich auch pro Ziffer hundert verschiedene Regeln aufstellen lassen, die dann für 99% der Fälle funktionieren. Eventuell kann das Finden so vieler Regeln auch enorm viel Zeit fressen, aber den Computer stört das nicht, dann lassen wir ihn halt einmal ein paar Tage rechnen. Das Finden der Regeln passiert ja im Normalfall nur ein einziges Mal.

Unsere Lösungen sind jetzt also wie folgt:

  1. Wir sammeln mehr Beispiele von verschiedenen Personen und Schrifttypen, damit unser Computer Regeln für alle möglichen Arten findet. Damit wir einen weiteren Ausrutscher vermeiden können und um herauszufinden wie gut die gefundenen Regeln wirklich sind, unterteilen wir unsere Daten in ein Trainingsset und ein Testset.
  2. Wir werfen Machine Learning auf unsere Datensätze und hoffen auf gut Ergebnisse.

Trainingsets und Testsets

Nachdem wir einige tausend Bilder von Ziffern bekommen haben, könnten wir prinzipiell schon mit Machine Learning anfangen. Das Problem ist aber, wie bei unsere manuellen Regeln vorher auch, dass wir nicht wissen wie gut die Regeln funktionieren für “unbekannte” Schrifttypen.
Wir brauchen eine zuverlässige Möglichkeit zu messen, wie gut unsere Regeln für Schrifttypen funktionieren, die der Computer noch nie zuvor gesehen hat. Damit wir die Möglichkeit haben abschätzen zu können, wie viele Ziffern wirklich richtig erkannt werden. Denn man muss bedenken, dass man nicht den Schrifttyp eines jeden Menschen in Machine Learning trainieren kann. Das ist sowohl von der Zeit her als auch vom Aufwand her diese Ziffern von jedem Menschen zu bekommen, einfach nicht möglich. Stattdessen wollen wir herausfinden, ob sich unser Algorithmus für die Anwendung im realen Leben eignet. Um das Herauszufinden unterteilt man seine Beispiele, die man dem Computer zeigt in zwei Gruppen. Einmal das Trainingsset und das Testset.
Das Trainingsset enthält Beispiele, die dem Computer gezeigt werden sollen. Der Computer benutzt also das komplette Trainingsset für Machine Learning. Das Testset hingegen ist meist deutlich kleiner als das Trainingsset. Es enthält ausschließlich Beispiele, die nicht im Trainingsset sind und die der Computer daher noch nie zuvor genau so gesehen hat.

Um jetzt herauszufinden wie gut unsere Regeln in der Realität funktionieren, wenden wir nach dem Lernen der Regeln, diese Regeln auf unser Testset an. Da das Testset nur unbekannte Schrifttypen enthält, lässt sich damit sehr gut abschätzen wie gut der Fehler in der Realität sein wird.

Stellen wir uns vor wir bekommen von jeder Ziffer 100 verschiedene Beispiele von der Post. Das Trainingsset könnte jetzt aus 90 pro Ziffer zufällig ausgewählten Beispielen bestehen und das Testset aus dem Rest. Die Trefferrate für unser Trainingsset könnte bei ungefähr 99% liegen, weil die Regeln ja basierend auf diesem Set gefunden wurden. Das Testset hingegen könnte nur 80% aller Ziffern richtig vorhersagen.

Gehen wir also einmal davon aus, dass wir eine Trefferrate von 80% für das Testset haben trotz Machine Learning. Das heißt 20% aller Briefe werden an den falschen Empfänger gehen oder gar nicht zugestellt werden. Im Vergleich zu vorher haben wir uns deutlich verbessert, aber wir sind noch lange nicht am Ende angekommen, das muss noch besser gehen!


Preprocessing – Aufräumen hilft!

Jeder dürfte den Satz “Wenn du Ordnung hältst, dann findest du auch deine Sachen wieder” aus der Kindheit kennen. So genervt wir auch von dieser Aussage und dem damit verbundenem Aufräumen waren, wir wussten, dass sie stimmt. Auch für Mustererkennungssoftware gilt:

“Aufräumen ist die halbe Miete”

Das Aufräumen, auch Preprocessing genannt, entfernt Unregelmäßigkeiten und sich widersprechende Aussagen aus unseren Daten. Preprocessing bringt die Daten also in eine einheitliche Form. Sehen wir uns dazu einmal diese vier Bilder von ein und derselben Zahl an:

raw_0_1 raw_0_2 raw_0_3 raw_0_4

Offensichtlich ist das immer dieselbe Zahl mit demselben Schrifttyp und dennoch wird unser Machine Learning Algorithmus mindestens vier zusätzliche Regeln extrahieren.
Es ist auch eine 0, wenn das Zeichen die Eigenschaften von 0ern erfüllt und:

  • der Hintergrund die Farbe weiß hat und die 0 die Farbe rot.
  • der Hintergrund die Farbe grün hat und die 0 die Farbe rot.
  • der Hintergrund die Farbe grau hat und die 0 die Farbe rot.
  • der Hintergrund die Farbe grau hat und die 0 die Farbe grün.

Um also jegliche Farbkombination abzufangen, bräuchte man Millionen von Daten in allen möglichen Farbkombinationen, damit unser Computer all diese Farben lernt. Preprocessing hilft uns dieses Problem zu umgehen. Wir räumen die Daten etwas auf! Wenn wir die Bilder alle in schwarz/weiß Bilder umwandeln lassen (auch Binärisierung genannt), dann braucht unser Computer nicht mehr lernen welche Farben kombinierbar sind, sondern kann sich wieder auf die wichtigeren Eigenschaften konzentrieren. Wir nehmen dem Computer also die Arbeit ab und sagen von vornherein: “Die Farbe der Bilder ist egal”, indem wir alle Bilder bevor wir sie dem Computer zeigen in schwarz/weiß Bilder konvertieren lassen.

Schauen wir uns die entstandenen Bilder an:

bin_0_1 bin_0_2 bin_0_3 bin_0_4

Das sieht schon deutlich besser aus, aber irgendwie hat man das Gefühl, dass das noch nicht perfekt ist. Jetzt fällt erst richtig auf, dass die Bilder zusätzlich leicht gedreht sind. Das bedeutet natürlich wieder mehr Regeln, die der Computer lernen muss. Aber auch das lässt sich beheben, indem wir alle Bilder automatisch Drehen lassen, so dass sie immer “gleich gedreht” sind. Als nächsten Preprocessing-Schritt kann man die Ziffern alle auf dieselben Größe/Dicke/usw. bringen. Ihr seht es gibt etliche mögliche Preprocessing-Schritte und jeder Schritt kann die Trefferrate weiter verbessern.

Mittlerweile haben wir alle unsere Bilder auf eine ähnliche Form gebracht, sie sind jetzt alle ungefähr gleich groß, alle schwarz/weiß, alle gleich gedreht, und so weiter. Aber über 95% Trefferrate werden wir bei unserem Testset dennoch nicht hinaus kommen, was immer noch nicht gut genug ist.


Feature Extraction – Erste Hilfe für Computer

Um unsere Trefferrate noch weiter zu erhöhen, können wir dem Computer helfen Regeln zu finden.
Bisher hat der Computer immer das komplette Bild bekommen und musste basierend auf den Pixelwerten Regeln finden. Wenn wir dem Computer aber im Voraus sagen worauf er genauer achten soll, dann können wir unser menschliches Wissen mit dem Machine Learning kombinieren und bekommen hoffentlich Ergebnisse, die außergewöhnlich gut sind.
Sehen wir uns zur verdeutlichung einmal diese As an:

a_1 a_2 a_3 a_4

Da wir unsere Preprocessing-Steps darauf angewendet haben, sehen die As schon alle sehr ähnlich aus. Trotzdem unterscheiden sie sich in der Schriftart. Ein paar As sind etwas geschwungener, andere sind etwas kantiger und wieder andere sind zittrig. Wir als Menschen wissen natürlich, dass die Schriftart keinen Einfluss darauf hat welcher Buchstabe gezeigt wird, aber der Computer weiß das natürlich nicht. Indem wir den ganzen Buchstaben in “perfekte” Linien und Kreise zerlegen, sparen wir uns einen Haufen Regeln.

Wir sagen dem Computer dann nicht mehr: “An Position 0,0 ist ein weißer Pixel, an Position 1,0 ein schwarzer Pixel, …” und das für alle Pixel im Bild, sondern wir können uns darauf beschränken dem Computer zu sagen: “An Position 12,3 ist eine Linie, die bis 20,5 geht, an Position 2,2 ist ein Kreis mit Radius 5, …”
Damit fassen wir die Pixel zu größeren Objekten zusammen und helfen dem Computer Regeln zu finden. Die Feature Extraction bringt die Daten also in eine Form, die es dem Computer erleichtert Regeln zu finden. Preprocessing und Feature Extraction sind nicht immer eindeutig von einander abgrenzbar, oft genug überschneiden sich diese zwei Schritte auch.
Zusammenfassend kann man aber sagen: Preprocessing besteht aus Verfahren, die versuchen die Daten in eine einheitliche Form (selbe Farbe, selbe Position, usw.) zu bringen. Feature Extraction hingegen versucht menschliches Wissen mit einfließen zu lassen und versucht die Daten auf das Wichtigste zu reduzieren.

Nachdem wir unserem Computer geholfen haben die Regeln zu extrahieren, können wir Trefferrate von 99,9% bekommen. Das ist nicht perfekt, aber endlich gut genug, um es in der Realität zu benutzen. Die restlichen 0.1% muss dann wohl oder übel dennoch ein Mitarbeiter der Post anschauen und entziffern.


Der Classifier – Das Herz

“Halt Stopp! Was ist denn jetzt ein Classifier?”, denkt ihr euch vielleicht.
Tatsächlich haben wir das Existieren von einem Classifier die ganze Zeit über vorausgesetzt ohne dabei zu wissen, dass es einer ist. Wir haben Machine Learning benutzt, damit der Computer selbstständig Regeln aufstellt. Machine Learning heißt aber lediglich der Prozess des Lernens, nicht jedoch das entstandene Programm. Ganz simpel ausgedrückt ist ein Classifier also das Programm, welches die Regeln verwaltet, Regeln findet, Regeln anwendet und uns am Ende sagt was für eine Ziffer das ist. Der Classifier ist also der letzte Schritt in unserer Mustererkennung-Pipeline. In ihm laufen alle Informationen, alle Regeln, einfach alles, zusammen und basierend auf Erfahrung und auf den gelernten Regeln liefert der Classifier dann ein Ergebnis. Es gibt zig verschiedene Classifier, etwa Künstliche Neuronale Netze, SVMs, k-Nearest-Neighbour Classifier, Expertensysteme und noch viele mehr. Jeder Classifier ist dabei für andere Anwendungsgebiete und Feature Extraction Methoden mehr oder weniger gut geeignet.


Überblick

In diesem Kapitel fassen wir das was wir heute gelernt haben in einer Grafik zusammen, um auch die Abhängigkeiten und den Ablauf besser zu verstehen (in den Klammern stehen jeweils Beispiele für die jeweilige Stufe der Pipeline).

Mustererkennung-Pipeline

Soweit zu den wirklich grundlegenden Konzepten hinter dem Gebiet der Mustererkennung.
Besonders faszinierend finde ich an diesem Themengebiet die enorme Abwechslung, die man in jedem Mustererkennung-Softwareprojekt findet. Es gibt zwar ein paar Methoden und Verfahren, die man immer anwenden kann und die eigentlich immer auch die Trefferrate verbessern, aber welche Verfahrenskombination wirklich DIE beste Trefferrate mit sich bringt, das kann man meistens nur abschätzen im Voraus, nicht jedoch eindeutig vorhersagen oder gar berechnen.
Das genau macht das Gebiet der Mustererkennung auch so umfangreich und komplex. Es gibt im Allgemeinen keine perfekten Lösungen für irgendein Problem aus diesem Gebiet.
In der Spielprogrammierung zum Beispiel weiß ich, den kürzesten Pfad zwischen A und B kann ich über Dijkstra bzw. A* finden und ich weiß der Algorithmus wird ein perfektes Ergebnis liefern, egal wie oft und auf welche Graphen ich diese Algorithmen anwende. Ein derartiges Allheilmittel gibt es in der Mustererkennung leider nicht, auch wenn schon viel von solcher “Intelligenz” geträumt wird.

Artikel zitieren:
Marcel Rupprecht, "Die Mustererkennung-Pipeline", in Neural Ocean, 2016, //neuralocean.de/index.php/de/2016/09/30/mustererkennung-pipeline/.

BibTex:
@misc{NeuOcPipe2016,
    title="Die Mustererkennung-Pipeline",
    url="\url{//neuralocean.de/index.php/de/2016/09/30/mustererkennung-pipeline/}",
    journal="Neural Ocean",
    author="Marcel Rupprecht",
    year="2016 (accessed März 30, 2020)"
}

 

1.
Mustererkennung – Wikipedia. de.wikipedia.org. //de.wikipedia.org/wiki/Mustererkennung. Published October 7, 2016. Accessed October 7, 2016.

Ein Gedanke zu „Die Mustererkennung-Pipeline

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.