In unserem CV Management Tool GravityCV können sich Nutzer bei Bedarf passende und relevante Jobs aus allen großen deutschen Jobportalen anzeigen lassen. Die Herausforderung ist wie „Relevanz“ definiert wird. In dem AI und ML Zeitalter gibt es viele gute Ansätze. In einigen der nächsten Posts wollen wir Ansätze aus Natural Language Processing, Text Retrieval, Machine Learning, Graphen Theorie bis hin zu Deep Learning beleuchten mit dem Ziel am Ende eine möglichst akkurate Matching Pipeline zu implementieren.
Alle Suchalgorithmen basieren auf einen invertierten Index. Tools wie Solr oder Elasticsearch sind hier keine Ausnahmen und nutzen beide das Java Projekt Lucene als Basisframework. Der invertierte Index ist vereinfacht ausgedrückt wie ein Index in einem Buch zu verstehen.
Alle Wörter werden jeweils mit der Position Ihres Vorkommens, bzw. in welchem Dokument sie vorkommen gespeichert. Man schlägt das Wort dann in diesem Index nach und findet das Dokument oder die Dokumente. Ferner ist es möglich Suchbegriffe mit boolschen Ausdrücken miteinander zu kombinieren, z.B. :
Java AND Hibernate
Java OR Hibernate
Nachdem die Suchengine entsprechende Dokumente gefunden hat, die der boolschen Operation genügen wird diese Liste der Dokumente sortiert und zurückgegeben, um sie z.B. auf einer Webseite anzuzeigen. Die Boolsche Suche mit AND / OR ist nicht sehr ergiebig. Je mehr Terme in der Anfrage vorhanden sind, um so offensichtlicher wird das Problem:
Query: Java Hibernate Spring MVC Oracle
Wenn man eine AND Verknüpfung wählt, dann wird das Suchfenster recht strikt. Alle Wörter müssen vorkommen. Wenn eines der Wörter nicht vorkommt wird der Kandidat nicht gematched. Wenn man OR als Verknüpfung hat wird die Suchergebnisliste zu groß und irrelevant. Ferner sind Kombinationen von Operatoren möglich wie:
Query (Java AND Hibernate) OR (Spring AND Oracle)
Schnell wird es unübersichtlich eine passende Query zu formulieren. Die Lösung ist „Ranked Retrieval“. Dabei muss der User keine komplexen boolschen Ausdrücke beherrschen. Er gibt einfach die Query wie in natürlicher Sprache ein und ein Verfahren sorgt dafür, dass Dokumente gefunden werden, die der Query am ähnlichsten sind. Dabei werden die „ähnlichsten“ Dokumente ganz obern in der Liste erscheinen. Es gibt diverse Verfahren, die die „Ähnlichkeit“ von Dokumenten zu einer gegebenen Query feststellen können. Der gängigste ist TF-IDF. TF-IDF basiert auf dem Vector Space Model (VSM) aus der Welt der linearen Algebra. In allen Machine Learning oder auch Deep Learning Workflows ist einer der wichtigsten ersten Schritte das Enkodieren von Text in Zahlen. Erst dann ist es möglich mathematische Algorithmen zu nutzen. Die Frage, die sich also stellt, ist wie können wir unsere Dokumente und unsere Queries in Zahlen ausdrücken, um eben diese Algorithmen anzuwenden.
TF-IDF heisst Term Frequency – Inverse Document Frequency. Wenden wir uns dem ersten Teil dem TF zu. Term Frequency ist einfach ausgedrückt wie häufig ein Wort in den verschiedenen Dokumenten vorkommt. Dazu wird aus allen Dokumenten eine Wortliste erstellt und pro Dokument ein Vector erstellt, welches einfach die Häufigkeit beinhaltet wie oft das Wort in dem Dokument vorkommt. Die Idee ist, dass je mehr ein Term in dem Dokument vorkommt, umso relevanter scheint er für das Dokument zu sein. Beispiel:
Da Dokumente unterschiedliche Längen haben können und längere Dokumente, die wahrscheinlich den Suchterm häufiger enthalten nicht zu viel Gewicht bekommen bei der späteren Berechnung, wird die Anzahl der Terme noch durch die Länger aller Wörter im Dokument geteilt. Daher der Begriff „Frequency“, sonst könnte es auch einfach Term Count heißen. Das nennt man auch Normalisieren.
[latex]\quicklatex{size=25}\frac{\text{Haufigkeit des Wortes}}{\text{Alle Woerter im Dokument}}[/latex]
So, nun hätten wir schon mal pro Dokument einen Vector. Jetzt wird das gleiche mit der Query gemacht:
[latex]\quicklatex{size=25}Doc_{query}=\text{1 0 0 1 1 0 ….}[/latex]
Dabei entspricht die Zahl in dem Query Vector genau wie bei den Dokumenten auch der Anzahl der Vorkommen des Wortes (natürlich dann noch geteilt durch die Anzahl aller Wörter in der Query). D.h. Oracle:1, Ipsum:0, was:0, Java:1 usw. Jetzt haben wir für alles einen Vektor. Vektoren sind prädestiniert, um sie in einen n-dimensionalen Raum zu projiizieren. Jede Spalte in einem Vector entspricht dabei einer Dimension. Hätte unser gesamtes Vokabular 3000 Wörter, dann hätten wir einen 3000-dimensionalen Vector. Mehr als 3 Dimensionen kann sich der Mensch leider schwer vorstellen. Für einen Computer ist das kein Problem. Um dem Beispiel besser folgen zu können nehmen wir mal nur 3 Dimensionen:
Jeder Dokumenten Vektor wird dabei in den Raum projiziert. Inkl. dem Query Vector. Der Ursprung liegt bei allen im 0-Punkt. In der linearen Algebra sind zwei Vektoren umso ähnlicher je kleiner der Kosinus Winkel zwischen ihnen ist. D.h. wir vergleichen unseren Query Vektor mit jedem Dokumenten Vektor und suchen uns diejenigen aus mit dem kleinsten Kosinus Winkel zum Query Vektor. Diese sind dann die relevantesten Dokumente zu unserer Query. Doch es gibt einen Haken mit der reinen TF. Wie verhält es sich denn mit Wörtern, die in vielen Dokumenten vorkommen? In unserem Beispiel kommt das Wort „Bla“ in vielen Dokumenten relativ häufig vor. In dem Dokumenten Vektor hätte solch ein Wort relativ großen Einfluss auf die Ausrichtung des Vektors. Wir brauchen also eine Gewichtung, die folgendes berücksichtigt:
Kommt der Term häufig in einem Dokument vor, dann trägt es zur Relevanz bei.
Kommt ein Term in allen Dokumenten häufig vor, dann hat es eher weniger Relevanz und darf weniger beim Ranking eine Rolle spielen.
Den ersten Teil kriegen wir mit TF hin. Den zweiten Teil mit der Inverse Document Frequency : IDF. Die Formel für TF-IDF lautet:
[latex]\quicklatex{size=25}\mbox{tf-idf}_{t,d} = (1 +\log \mbox{tf}_{t,d}) \cdot \log \frac{N}{\mbox{df}_t}[/latex]
TF-IDF erzeugt einen Wert zwischen 0 und 1. Unsere neuen Vektoren beinhalten also nicht mehr die reine TF, sondern eben die TF-IDF Werte. Neben TF-IDF existieren noch andere Scoring Algorithmen, die ähnlich gute oder gar bessere Ergebnisse liefern wie z.B. Okapi BM25. Die eigentlich Berechnung der „Ähnlichkeit“ zwischen zwei gegebenen Dokument Vektoren ist einfach das Skalarprodukt dieser beider Vektoren. Ist das Ergebnis = 0, dann liegen die beiden Vektoren orthogonal zueinander und haben keine Ähnlichkeit. Bei kleiner werdendem eingeschlossenen Winkel wird die Ähnlichkeit größer, s. Kosinus-Ähnlichkeit.
Soweit so gut, aber dem Namen „Deep“ kommt dieser Ansatz noch nicht nahe. Was wir erreichen wollen ist eine noch bessere Relevanz. Was wenn z.B. unser Algorithmus die Beziehung zwischen Wörtern kennen Würde. Dass z.B. Hibernate irgendwie auch mit Java zu tun hat, oder ORM ein Framework für Datenbank Zugriffsabstraktion ist und Hibernate ein ORM Framework ist. Oder das TDD Test Driven Development heißt oder 8 Einträge im CV von 2014-2018 die sich mit Java relevanten Technologien befassen (und nicht unbedingt java als keyword vorkommt) gleichbedeutend ist mit 4 Jahre Java Erfahrung, UND UND UND.
In unserem Tool GravityCV.com möchten wir Nutzern – neben dem Management des CVs – weitere intelligente Tools an die Hand geben. Es wird möglich sein Markdaten zu analysieren, Trends in Technologie erkennen, was fordert der Markt, mit Machine Learning sehr passende Jobs finden usw. Wir befinden uns gerade am Anfang der Reise und haben sehr viel spannendes vor. Einige der Technologien, die wir nutzen und über die wir in weiteren Posts berichten werden:
- NLP (Natural Language Processing) und NER (Named Entity Recognition)
- Deep Learning (CNN) / Word Embeddings
- Topic Modeling, LDA
- Ontology Based Information Retrieval
- Semantic Search
- Query/Synonym Expansion
