Seite 3: Lernziel

Inhaltsverzeichnis

Was genau soll gelernt werden?

Zunächst ist das Lernziel zu definieren. Es geht darum, einem Nutzer die Suchergebnisse zu zeigen, die zu seiner Anfrage und seinen Interessen passen. Die erste Aufgabe, die initiale Menge zu einer Suchanfrage passende Ergebnisse zu finden, übernimmt eine Suchmaschine. Stattdessen konzentrieren sich die Autoren auf die folgende Personalisierung der Suchergebnisse, wobei die Ergebnisliste so umsortiert wird, dass die Resultate, die der Suchintention des Nutzers entsprechen, am Anfang der Liste erscheinen.

Da es um einen Online-Shop (also einen Produktkatalog) geht, definieren die Autoren eine Suchintention als die Menge relevanter Produktattribute wie Kategorien von Produkten, ihre Marken, Preise, Farben usw. Damit haben sie auch die Fälle abgedeckt, dass sich die einen Kunden generell für die Technik interessieren, während andere nur für rote Kleidung oder laktosefreie Lebensmittel Interesse zeigen. Um die Erklärung des Algorithmus zu erleichtern, sei weiterhin von einer Suchintention gesprochen, die sich auf eine Produktkategorie beschränkt.

Als weitere Vereinfachung betrachtet der Algorithmus nur Nutzeraktivitäten der aktuellen Sitzung als Kontext. Später wird gezeigt, wie man das gelernte Modell für andere Komponenten des Kontexts erweitert, was die Autoren Nutzercluster nennen. Als mögliche Cluster-Dimensionen können zum Beispiel die Zeit, der Nutzerkanal, aber auch – falls verfügbar – Geo- und demographische Informationen dienen.

Für jeden Nutzercluster sind nun die populärsten Suchintentionen herauszufinden. Zusätzlich soll untersucht werden, wie stabil diese Suchintentionen innerhalb einer Sitzung sind. Besuchen Nutzer einen Online-Shop nur mit einer Intention? Oder gibt es mehrere Suchthemen innerhalb einer Sitzung? Die Autoren stellen ein Verfahren vor, das aus Logdaten lernt, welche Suchintentionen in einer Sitzung zusammen am häufigsten vorkommen und wie oft und in welcher Reihenfolge dazwischen gewechselt wird. Anhand dieses Wissens und des Echtzeitkontexts, der die Aktivitäten der aktuellen Sitzung umfasst, wird anschließend vorhergesagt, welche Intention die nächste Suche hat.

Sequenzen von Suchintentionen aus Logdaten lernen

Die Schlussfolgerung ist mithilfe eines statistischen Modells, eines sogenannten Hidden Markov Model (HMM), modelliert. Es betrachtet eine Sequenz von Suchintentionen innerhalb einer Sitzung als eine Markov-Kette von Zuständen. Ziel ist es, Wahrscheinlichkeiten der Übergänge zwischen Zuständen zu lernen, um anhand einer Kette von Beobachtungen den nächsten Zustand prognostizieren zu können.

Die Zustände sind "hidden" (verborgen), weil sie nicht direkt beobachtet, sondern von Nutzeraktivitäten abgeleitet werden. Wer also nach einer nicht eindeutigen Suche, zum Beispiel nach "Samsung", Produkte aus der Kategorie "Smartphones" anklickt, wird davon ausgehen, dass die Intention der Suche "Smartphones" und nicht "Fernseher" oder "Haushaltstechnik" ist. Wenn man aber für dieselbe Suchanfrage mehrere Klicks auf Produkte aus verschiedenen Kategorien beobachtet, heißt es, dass es mehrere Kandidaten für eine Intention dieser Suche gibt. Es ließen sich nicht nur Klicks, sondern auch andere Konversionen betrachten und unterschiedlich gewichten (beispielsweise führt ein Kauf eines Produkts, das einer bestimmten Intention entspricht, zu einer höheren Wahrscheinlichkeit, dass diese Intention die echte Intention der Nutzer ist).

Formal ausgedrückt definieren die Autoren den Kontext als (t – 1) Suchen und Klicks auf Suchergebnisse innerhalb einer Sitzung und möchten daraus vorhersagen, welche Suchintention die nächste Suche haben wird. Dazu können sie die A-posteriori-Wahrscheinlichkeiten für jede Intention eines bestimmten Nutzerclusters berechnen:

p (Intention i | aktuelle Sitzung , Modellparameter eines Nutzerclusters) = p (s_i|O,Θ_k)

und einen oder mehrere wahrscheinliche Intentionskandidaten bestimmen. Mit dem Expectation-Maximization-Algorithmus lernt man im Offline-Modus die folgenden Wahrscheinlichkeiten, die man zum Berechnen von p (s_i|O,Θ_k) braucht:

• p (s_i|Θ_k) – die Wahrscheinlichkeit, dass eine Suchintention s_i die erste in einer Sitzung ist
• p (s_i|S_m,Θ_k) – die Wahrscheinlichkeit, dass sich an Intentionssequenz S_m eine Suchintention s_i anschließt
• p (w|s_i,Θ_k) – die Wahrscheinlichkeit, dass ein Nutzer auf ein Produkt w klickt, wenn die Intention seiner Suche s_i ist

Da das Modell auf dem des genannten Artikels basiert, lassen sich weitere Details des Lernalgorithmus dort finden. Die Autoren schlagen vor, ein separates HMM für jeden Nutzercluster zu lernen. Ein Nutzer u wird in der Echtzeit zu jedem Cluster K mit einer Wahrscheinlichkeit p(u|K) zugeordnet. Anschließend lässt sich die wahrscheinlichste Intention der nächsten Suche aus dem HMM-Ensemble berechnen, wo die einzelnen Modelle proportional p (u|K) gewichtet sind:

Offline- und Online-Berechnungen

Das Offline-Lernen umfasst die Berechnungen von p(s_i | Θ_k), p(s_i|s_m,Θ_k) sowie p(w|s_i,Θ_k) für jeden Nutzercluster und kann mit den neuen Logdaten regelmäßig aktualisiert werden.

Die Echtzeitinformationen stammen aus dem Kontext. Er besteht aus verschiedenen Nutzercharakteristiken (den Dimensionen der Cluster entsprechend) und umfasst außerdem Bewegungen des jeweiligen Nutzers auf der Website. So wird im ersten Schritt die Wahrscheinlichkeit der Clusterzugehörigkeit des Nutzers berechnet. Danach werden für jede vom Nutzer initiierte Suche aus den Klicks der vorherigen Suchen mögliche Intentionen s₁,…,s_{t – 1} und Intentionssequenzen S_{t – 1} ermittelt. Damit ergibt sich die Möglichkeit, die wahrscheinlichste Intention der nächsten Suche zu berechnen.

Abbildung 13 zeigt ein Beispiel einer aus den Logdaten des Online-Shops gelernten Intentionssequenz. Die Suchintentionen werden durch verschiedene Produktkategorien repräsentiert.

Die oben gezeigten Sequenzen lassen sich gut interpretieren. So erhöht sich die Verweilwahrscheinlichkeit für den Bereich Smartphones mit jedem Produkt, das der Kunde in diesem Sortimentsbereich aufruft.

Komplexität der Berechnungen

Bei großen Logfiles spielt es eine bedeutende Rolle, wie skalierbar sich der Algorithmus zum Lernen umsetzen lässt, weil im Batch-Lauf zum Beispiel jede Nacht alle Daten bis zu einem Stichzeitpunkt mit zu betrachten sind. Wie die Abbildung 14 zeigt, wächst die Zeit für Batch-Berechnungen linear mit der Anzahl der Sitzungen. Weil man den EM-Algorithmus verteilt implementieren kann [1], ergibt sich ein linear skalierender verteilter Lernalgorithmus.

Berechnungszeit: p(s_t|S_t–1,Ɵ_k) für t ϵ [1,5] (Abb. 14)

Die Anzahl der vorberechneten p(s_t|S_{t – 1},Θ_k) kann theoretisch sehr schnell (exponentiell) wachsen, wenn die der möglichen Suchintentionen bei langen Sitzungen groß wird. Als Lösung kann man sich auf eine Submenge der Intentionssequenzen beschränken, die in vergangenen realen Sitzungen vorgekommen sind. Alternativ lässt sich die maximale Länge der betrachteten Sequenzen begrenzen.