Nachdem wir in Teil 2 unserer Blogserie zu Empfehlungssystemen bereits nicht personalisierte Recommender vorgestellt und die entsprechenden Algorithmen dahinter erklärt haben, legen wir in diesem Beitrag das Augenmerk auf personalisierte Recommender Systeme und fortgeschrittenere Machine-Learning-Methoden. Außerdem soll das wesentliche Thema der Evaluierung genauer betrachtet werden.

Empfehlungssysteme sind ein ganz neues Feld für Sie? Dann starten sie gerne mit Teil 1 unserer Blogreihe und lernen Sie, für wen ein Recommendation System relevant ist, welche grundsätzlichen Varianten es gibt und wie aufwändig deren Implementierung ist.

Algorithmen für personalisierte Empfehlungen

Nicht immer hinterlassen Nutzer ausreichend personalisierte Informationen entlang ihrer Customer Journey. Beispielsweise können neue Nutzer hinzukommen oder bestehende Kunden beim Surfen von Online-Angeboten nicht angemeldet sein. Nicht personalisierte Empfehlungssysteme, wie der Vorschlag häufig gemeinsam gekaufter Produkte, bieten Unternehmen in diesem Fall trotzdem Möglichkeiten für Empfehlungen. Je individueller diese jedoch auf den Kunden zugeschnitten werden, desto besser. Deshalb werden im Folgenden Verfahren vorgestellt, die deutlich stärker personalisiert sind und die Präferenzen der Kunden erlernen. Zum Verständnis dieser Methoden ist es hilfreich, sich das Problem als dünnbesetzte Matrix vorzustellen. Die Zeilen repräsentieren die User, die Spalten die Items. Immer dann, wenn eine Aktion eines Users für ein Item stattfindet, wird ein Eintrag in der Matrix verzeichnet. Ansonsten sind die Werte fehlend und müssen nicht explizit gespeichert werden. Am besten lässt sich dies anhand der folgenden Grafik veranschaulichen:

Die Zeilen der Grafik stellen unterschiedliche Nutzer dar, die ihre Präferenzen für diverse Produkte als Like oder Dislike ausgedrückt haben. Viele dieser Interessen sind in der Praxis allerdings unbekannt (in der Grafik symbolisiert durch das Fragezeichen). Genau diese Fragezeichen will man mithilfe von Empfehlungssystemen vorhersagen, also die Präferenzen für noch unbekannte Items ermitteln. Die folgenden Algorithmen zielen mitunter darauf ab.

1. Kollaboratives Filtern
   Klassische Methoden, um die Präferenzen von Usern zu erkennen, sind User-User und Item-Item kollaboratives Filtern. Beim User-User kollaborativen Filtern wird für jeden User ein Vektor gebildet, in dem jede Komponente einem Item entspricht. Hat ein User ein Item bewertet, steht in dem Eintrag die entsprechende Bewertung, alle restlichen Einträge fehlen. Gibt es keine oder nicht genügend Bewertungen, können implizites Feedback, wie zum Beispiel Käufe oder andere Aktionen herangezogen werden und als Wert für eine Aktion z. B. eine 1 eingetragen werden. Da ein User üblicherweise nur mit einer geringen Anzahl an Items auf einer Seite interagiert hat, fehlt der Großteil der Werte (bzw. ist 0 für implizites Feedback). Mit Hilfe eines Ähnlichkeitsmaßes, wie der Cosine Similarity, können nun Ähnlichkeiten zwischen den Vektoren von Usern ermittelt werden. Führt man dies paarweise für alle User durch, ergibt sich eine User-User Ähnlichkeitsmatrix. Anhand dieser Matrix kann man für einen gegebenen Nutzer ähnliche User finden und wiederum deren bevorzugte Items als Empfehlungen für den gegebenen Nutzer einsetzen, wenn sie diesem noch unbekannt sind.
   
   In der untenstehenden Grafik sehen wir beispielsweise, dass die Präferenzen des Jungen (Nr. 1) mit denen des Mädchens (Nr. 3) sehr ähnlich zu sein scheinen. Deshalb liegt die Vermutung nahe, dass dem Mädchen die zweite Kamera (Nr. 5 der Produkte) auch gefallen könnte.
   Diese traditionelle Methode ist ein Nearest-Neighbor-Verfahren, wobei die Nachbarn die ähnlichen User sind. Item-Item kollaboratives Filtern ist vergleichbar, basiert aber auf Ähnlichkeiten zwischen Items. In der Praxis ist es normalerweise aber deutlich weniger rechen- und speicherintensiv, da es bei den meisten Anwendungen mehr User als Items gibt. Darüber hinaus wurden auch analoge Verfahren für andere Anwendungsfälle entwickelt, beispielsweise auf Session-Ebene. Die Bezeichnung „kollaboratives Filtern“ beschreibt genauer gesagt das allgemeine Konzept, dass auf Basis mehrerer interagierender User relevante Informationen gefiltert werden und dies trifft auch auf die folgenden, neueren Verfahren zu.
    

    

2. Machine-Learning-basierte Faktorisierungsmodelle
   Neuere Methoden des maschinellen Lernens und der künstlichen Intelligenz knüpfen an das klassische, ähnlichkeitsbasierte kollaborative Filtern an und versuchen dieses zu verbessern. Im Rahmen des „Netflix Prize“, eines 1-Million-Dollar-Wettbewerbs, hat sich vor allem Matrix Factorization als Verfahren bewährt. Die Grundidee dieser Methode ist es, „latente Präferenzen“ von Usern und „latente Eigenschaften“ von Items zu lernen. Im Falle von Musik könnte dies beispielsweise die Präferenz eines Users für ein bestimmtes Genre sein; die zugehörige Eigenschaft des Songs beschreibt, wie stark er diesem Genre zuzurechnen ist. Präferenzen oder Eigenschaften basieren dabei aber nicht auf Annahmen, sondern werden vom Algorithmus automatisch anhand der Daten erlernt. Für eine spezifische Anzahl an latenten Präferenzen hat man niedrigdimensionale Vektoren von Usern und Items, deren Übereinstimmung durch das zugehörige Innenprodukt berechnet werden kann. Hohe Übereinstimmungen zwischen einem User und einem neuen Item sprechen dafür, dass das Item dem User gefallen wird und sich somit als Empfehlung eignet. Für Matrix Factorization gibt es sehr effiziente Algorithmen auf der Basis von Stochastic Gradient Descent, die das Lernen performant machen. Außerdem zeichnet sich Matrix Factorization durch seine Robustheit bei wenigen verfügbaren Daten aus, was an der niedrigdimensionalen Repräsentierung der Ausgangsdaten liegt. Eine Erweiterung von Matrix Factorization sind Factorization Machines, die den Vorteil eines erweiterten Feature Engineering bieten. Zusätzliche Variablen, wie Kontextinformationen, User- und Produktstammdaten sowie zeitabhängige Informationen, können durch eine entsprechende Codierung einfach in das Modell integriert werden.
    
3. Künstliche Neuronale Netze
   In jüngster Zeit wurden einige Ansätze für Empfehlungen entwickelt, die auf künstlichen neuronalen Netzwerken basieren. Dazu gehört der Einsatz von Embeddings, welche ursprünglich für Textdaten entwickelt wurden und ähnlich wie die oben beschriebenen Faktorisierungsmodelle eine latente Repräsentierung erzeugen. Diese können in andere neuronale Netze integriert werden und eignen sich auch, um gewisse Verhaltenseigenschaften von Kunden abzubilden, sind aber oftmals aufwändiger zu trainieren. Ebenso gibt es weitere Methoden basierend auf Deep Learning, wie beispielsweise RNN Ansätze mit Gated Recurrent Units. Ein häufiger Anwendungsfall dieser Art von Methoden sind Session-basierte Recommendations. Diese zielen darauf ab, die Sequenzeigenschaften zu modellieren, wie zum Beispiel die zeitlich aufeinanderfolgenden Views auf einer Website in einer Session, um damit die nächsten Klicks vorherzusagen. Solche Ansätze unterscheiden sich oftmals in der Art der Objective von klassischen RNN Anwendungen. Hier kommen in der Regel Ranking-basierte Loss-Funktionen zum Einsatz (oftmals mit einem paarweisen Loss wie Bayesian Personalized Ranking), da es das Ziel ist, eine möglichst gut sortierte Liste von Empfehlungen zu generieren. Auch unterscheidet sich die Form der batchweisen Input-Trainingsdaten.

Darüber hinaus gibt es noch weitere Arten, wie hybride Empfehlungssysteme, welche eine Kombination mehrerer Ansätze darstellen sowie wissensbasierte Recommender, welche zum Beispiel auf kodiertem Wissen aufsetzen und dem User regelbasiert schrittweise zu einer Entscheidung verhelfen.

Evaluation

Um den Erfolg eines Recommenders zu beurteilen, ist eine Live Evaluation und gegebenenfalls eine Nutzerbefragung am effektivsten. Jedoch ist es sehr hilfreich, ein Empfehlungssystem vor dem Deployment offline zu evaluieren. Das beste Maß für diese Evaluierung hängt dabei vom jeweiligen Anwendungsfall ab. Häufig ist die Genauigkeit der resultierenden Empfehlungsliste von Interesse. Zu den wichtigsten Maßen hierfür gehören Precision und Recall. Precision gibt den Anteil der für den User relevanten empfohlenen Items an (Beispiel: Anteil der Produkte, die nach einer Empfehlung gekauft wurden), gemittelt über alle User. Recall gibt an, wie viele der für den User relevanten Items ausgewählt wurden. Beide Maße können für unterschiedliche Thresholds (Grenzen) ermittelt werden. Ein relativ hoher Precision-Wert lässt sich durch die Empfehlung der insgesamt populärsten Items erzielen. Jedoch könnte dies außer Acht lassen, dass es für konkrete User wesentlich mehr relevante Items gibt, die von ihren speziellen Interessen abhängen. Ein hoher Recall-Wert versucht dies zu beschreiben.

Eine weitere wichtige Metrik ist die AUC, welche die Fläche unter der Kurve von False Positive Rate – True Positive Rate oder der Kurve von Recall - Precision beschreibt. Dies kann als Kombination der Konzepte von Recall und Precision innerhalb einer Metrik verstanden werden.

Für Anwendungsfälle, in denen die Empfehlungen nicht nebeneinander, sondern als absteigend sortierte Liste ausgegeben werden, bieten sich ferner Ranking-Maße wie der Mean Reciprocal Rank oder der normalized Discounted Cumulative Gain an. Die Idee ist hierbei, dass die obersten ausgegebenen Items stärker gewichtet werden müssen, weil sie von Usern eher wahrgenommen werden.

Customization

Neben den genannten Metriken ist es oftmals sinnvoll, eine auf die Problemstellung zugeschnittene Evaluierungsfunktion und, nach Möglichkeit, ebenfalls eine Zielfunktion zu definieren, nach welcher optimiert wird. Auf diese Weise können die Anforderungen für den jeweiligen Anwendungsfall besser einbezogen werden, sodass beispielsweise Gewinn- und Umsatzziele des Unternehmens in den Empfehlungen unmittelbar berücksichtigt werden.

Recommended Reading

Sie möchten mehr Details wissen? Als Einführung in die Grundlagen und Konzepte von Empfehlungssystemen eignet sich das Buch „Recommender Systems: An Introduction“ von Jannach, Zanker, Felfernig und Friedrich. Genaue Beschreibungen der Algorithmen und jüngsten Entwicklungen findet man in Fachpublikationen. So zum Beispiel die Veröffentlichungen in der jährlichen RecSys Konferenz, die sich spezifisch mit Forschung zu Recommender Methoden und deren Anwendungen befasst: https://recsys.acm.org/.

Fazit

Dieser Blogbeitrag diente als Überblick über die verschiedenen Methodiken, die in Empfehlungssystemen zum Einsatz kommen. Es empfiehlt sich, zuerst in einem kürzeren Projekt ein einfaches Verfahren zu implementieren. Dies kann in der Praxis bereits gute Ergebnisse liefern und ermöglicht ein besseres Verständnis. Je nach Resultat können anschließend fortgeschrittene Machine-Learning-Methoden zum Einsatz kommen.