Im zweiten Teil der Serie, die Ihnen einen Einblick hinter die Kulissen bei snapADDY gibt, geht es um den Einsatz von maschinellem Lernen in den snapADDY Produkten. Im Blogbeitrag erläutern wir daher die grundlegende Arbeitsweise unseres Parsers für die Adresserkennung aus einem unstrukturierten Text und wie wir hierfür Deep Learning mit einem regelbasierten System für ein bestmögliches Resultat kombinieren.
Grundlegendes Problem: Kontaktinformationen aus unstrukturiertem Text erkennen
Das Hauptproblem, mit dem wir uns bei der snapADDY GmbH beschäftigen, ist das der Adresserkennung. Am Anfang steht ein unstrukturierter Text, den wir als formatierten Kontakt mit zugehöriger Adresse speichern wollen, wie er beispielsweise auf Visitenkarten oder auf einer Impressums- bzw. Kontaktseite (siehe Abbildung) zu finden ist.
Der Mensch nutzt zur Erkennung seinen Verstand. In dem gegebenen Beispiel erkennt er sofort, dass die Musterfirma GmbH einen Unternehmensnamen abbildet. Wie kommt das? Der Mensch folgert einerseits aus der Position und dem Kontext der Wörter, andererseits kann hier die Musterfirma aber auch einfach direkt durch den Zusatz der Rechtsform erkannt werden.
Beim Computer ist die Vorgehensweise nicht komplett anders. Durch ähnliche Regeln, wie sie der Mensch benutzt, muss die Software am Ende die jeweiligen Wörter erkennen und den richtigen Feldern zuordnen. Deswegen verwenden wir bei snapADDY als ersten Schritt zur Adresserkennung ein regelbasiertes System, grundsätzlich ähnlich wie es der Mensch verwendet.
Lösung, 1. Teil: Regelbasiertes Vorgehen
Wenn unser Parser weiß, dass die Zeichen vor der Rechtsform in der Regel dem Firmennamen entsprechen, dann haben wir hier bereits eine Regel zur Erkennung identifiziert. Eine Vielzahl von Regeln sorgt dafür, dass in diesem Beispiel möglichst alle Unternehmensnamen erkannt werden. Die Regeln werden dabei für jedes Feld definiert, wenn dieses in sich geschlossen strukturiert ist. Dies ist zum Beispiel bei der Telefonnummer, der Postleitzahl, E-Mail-Adresse und Webseite der Fall. E-Mail-Adressen sind beispielsweise an sich standardisiert, damit diese von Email-Clients als Email Adresse erkannt werden. Das machen wir uns an dieser Stelle zu nutze.
Beispiel: E-Mail-Adressen erkennen mit RegEx
Die dargestellte Grafik zeigt beispielhaft einen sogenannten regulären Ausdruck zum Filtern einer E-Mail-Adresse aus einer Zeichenfolge. Der Ausdruck sieht auf den ersten Blick kompliziert aus, folgt aber einer einfachen Logik. Das System geht den Text von links nach rechts durch und überprüft dabei, ob die Regeln aus dem Regulären Ausdruck eingehalten werden. Erfüllt eine Zeichenfolge alle Regeln des Ausdrucks, können wir davon ausgehen, dass diese Zeichenfolge eine E-Mail-Adresse darstellt. Der Mensch erkennt diese an dem @-Zeichen, der Computer macht eigentlich genau dasselbe (siehe Abbildung).
Listen als Hilfe bei der Erkennung
Zusätzlich zu den Regulären Ausdrücken, verwenden wir Listen, um weitere Begriffe im Text zu finden. Mit dieser Strategie können wir auch Inhalte identifizieren, die nicht standardisiert sind. Anhand einer Liste von vielen verschiedenen Vornamen, Nachnamen, Titeln, Postleitzahlen oder Positionen können Textinhalte einfacher klassifiziert werden. In der Abbildung sehen wir ein Beispiel hierfür.
In diesem Fall werden alle möglichen Postleitzahlen der Visitenkarte mit regulären Ausdrücken erkannt und danach diese mit den vorhandenen Listen abgeglichen. Dadurch weiß der Parser, dass in diesem Beispiel nur Baltimore und Würzburg zu den gefundenen Postleitzahlen gehören können und sucht jeweils nach diesen Städtenamen auf der Visitenkarte. Wenn eine valide Kombination aus einem Städtenamen und zugehöriger Postleitzahl gefunden wurde, dann hat der Parser eine Übereinstimmung finden können. Auf diesem Match aufbauend kann der Parser dann weitergehend das Bundesland und Land erkennen, das in der Liste dem Städtenamen und der Postleitzahl zugeordnet ist. Die Liste der Postleitzahlen alleine ist bei uns übrigens rund 400.000 Einträge lang.
Ein weiterer Ansatz ist die Gewichtung der einzelnen Faktoren. Für alle Werte in den Listen ist ein Gewicht hinterlegt, mit dem die Wahrscheinlichkeit beziffert wird, dass eine Buchstabenfolge zu einer bestimmten Kategorie gehört. Das Beispiel des Ausdrucks Schneider verdeutlicht die Problemstellung. Denn Schneider kann im klassischen Sinn einer Position (Berufsbezeichnung) entsprechen, gleichzeitig ist Schneider aber auch ein weitverbreiteter Nachname in Deutschland. Genau hier kommt die Gewichtung ins Spiel. Nach statistischen Kriterien evaluiert, haben wir eine Gewichtungs-Datenbank aufgebaut, die die Gewichtung für einen bestimmten Kontext festlegt. Demnach gewichtet unsere Datenbank den Begriff Schneider beispielsweise mit einem Wert von 4 als Nachnamen und nur mit 3 Punkten als Position. Also wird am Ende Schneider als Nachname eingeordnet – durch die höhere Gewichtung.
Regelbasiertes Vorgehen ist begrenzt
Bis hierhin hat uns der regelbasierte Ansatz zu guten Ergebnissen gebracht. Inwieweit kann uns Machine Learning in diesem Fall trotzdem weiterhelfen oder wird überhaupt benötigt? Dazu möchte ich zwei Beispiele geben.
In Deutschland ist das Adressformat einheitlich, also immer genau gleich aufgebaut. Das hilft natürlich ungemein, wenn man versucht alle Möglichkeiten durch Regeln abzudecken. Natürlich ist aber auch nicht nur das deutsche Adressformat, sondern auch internationale Adressformate für snapADDY Nutzer relevant – hier beginnen die Probleme. In anderen Ländern gibt es beispielsweise viele verschiedene Adressformate (besonders im arabischen Raum) oder die Adressformate sind schwierig in Regeln auszudrücken. Ein Albtraum für unseren Parser, wenn dieser nur mit definierten Regeln arbeiten würde.
Das Problem wird direkt ersichtlich: Wenn allgemein für jeden Ausnahmefall eine neue Regel definiert werden muss, dann wird das ganze irgendwann nicht irgendwann unübersichtlich und nicht mehr erweiterbar. Daneben kann es auch Überschneidungen in den Listen geben. Nehmen wir einmal die reine Zeichenfolge „York“. Diese kann einerseits einem Nachnamen in Deutschland oder den USA, andererseits aber auch einen österreichischen Vornamen entsprechen. Genau hier liegen die Limitationen des regelbasierten Vorgehens. Zu viele Regeln blähen das System auf und machen es irgendwann nicht mehr beherrschbar. Zudem kann es immer passieren, dass es zum sogenannten Schmetterlingseffekt kommt, also eine kleine Veränderung im System große Auswirkungen auf die gesamte Leistung hat und so die Ergebnisse nicht mehr aussagekräftig sind.
Lösung, Teil 2: Deep Learning Ansatz als zusätzliche Hilfe integrieren
Da wir mit dem beschriebenen, regelbasierten System mit bereits sehr guten Ergebnissen gestartet sind, ist dies die Basis unseres Parsers. Das bedeutet, dass wir die regelbasierte Erkennung immer noch im ersten Schritt nutzen, um z.B. die Adresse über die Postleitzahl zu validieren (wie vorher beschrieben).
In der aktuellen Version nutzen wir Deep Learning genau dann, wenn die Regeln nicht mehr vernünftig greifen. Am wichtigsten ist dabei die Gewichtung, die wir bei der regelbasierten Vorgehensweise zwar auch nach statistischen Kriterien errechnet haben, allerdings kann uns hier Deep Learning entscheidend weiterhelfen. Die Abbildung zeigt die Gewichtung durch den Parser mittels Deep Learning. Roland-Frank-Straße 7 ist natürlich eine Straße, an sich ist im Namen der Straße aber auch ein Personenname versteckt (Roland Frank) und auch ein Teil eines Firmennamens könnte sich dahinter verbergen. Die mit Deep Learning errechneten Gewichte sagen hier auch zu 65% einen Straßennamen voraus. Dieses wird dann auch letztlich so übernommen und Roland-Frank-Straße 7 als Straße eingetragen. Das so von uns genutzte Verfahren kombiniert also beide erläuterten Techniken und ist damit ein hybrides Modell.
Gestiegene Adresserkennung durch den hybriden Parser
Mit der aktuellen Parser-Version, die das regelbasierte Vorgehen mit den Gewichtungsmöglichkeiten des Machine Learnings kombiniert, werden in unseren Test durchgehend bessere Resultate erzielt – im Gegensatz zur rein regelbasierten Methodik. Die größten Veränderungen sind in dem Diagramm dargestellt und zeigen jeweils pro Feld die Veränderung bei der Erkennungsrate in Prozent vom alten regelbasierten zum neuen hybriden Parser. Es ist ersichtlich, dass Machine Learning einen großen Teil hin zu einer verbesserten Datenqualität der Ergebnisse beigetragen hat. Auch in Zukunft werden wir daher weiterhin versuchen unsere Erkennungsqualität und den hybriden Parser durch das Testen verschiedener Parameter weiter zu verbessern!