Balancing exploration and exploitation (multi armed bandit) in information retrieval systems

01.03.2015 -

Abgeschlossen
TU Berlin & SAP SE

Name des Teilnehmers: Weijia Shao

Beschreibung des IT-Forschungsprojekts: Viele Internet-Dienstleister müssen große Mengen von Objekten verwalten. Zum Beispiel Nachrichtenartikel, Werbungen, oder Geräte, die mit dem Internet-der-Dinge verbunden sind. Diese Objekte verändern sich häufig und dynamisch. Dadurch ist es schwierig, die Präferenzen der Nutzer ausschließlich mit Informationen zum Inhalt zu modellieren. Allerdings basieren die Geschäftsmodelle der Dienstleister stark auf der korrekten Vorhersage der Präferenzen. In der Praxis sammeln die Internet-Dienstleister deswegen zusätzlich das Feedback von ihren Kunden um die Präferenzen von den Kunden zu lernen (Exploration). Diese Erkenntnisse verwerten (Exploitation) sie, um Einkommen zu maximieren, woraus folgendes Problem entsteht:

  • Falls die Internet-Dienstleister ihre Aufmerksamkeit auf das Sammeln des Feedbacks richten, kann ein kurzfristiger Einkommensverlust auftreten, wegen der hohen Wahrscheinlichkeit, den Kunden viele unerwartete Objekte anzubieten.
  • Ein langfristiger Einkommensverlust kann auftreten, wenn die Internet-Dienstleister ihre Aufmerksamkeit auf das Maximieren des Einkommens (ohne weiteres Lernen der Präferenzen der Benutzer) richten und so den Kunden immer suboptimale Objekte anbieten.
  • Das Exploration-Exploitation-Problem (Multi-Armed-Bandit-Problem) wurde im Jahr 1930 das erste mal beschrieben, und spielt seitdem eine immer wichtigere Rolle für moderne Retrieval- und Empfehlungssysteme.

Die vorhandenen Algorithmen haben drei Nachteile:

  • Die vorhandenen Algorithmen basieren auf unrealistischen Annahmen.
  • Die Komplexität der vorhandenen Algorithmen hängt von der Anzahl der Objekte ab. Deshalb sind sie ineffektiv für Systeme mit einer großen Menge von Objekten.
  • Die vorhandenen Algorithmen sind schwer zu verwenden, da die manuellen Einstellungen des Eingabeparameters benötigt werden.

Außerdem sind die vorhandenen Computerprogramme, die Bandit-Algorithmen anbieten, domain-spezifisch, obwohl das Exploration-Exploitation-Problem domainunabhängig ist.

In diesem Projekt werden Algorithmen für das Exploration-Exploitation-Problem entwickelt, analysiert, und in ein von Data-Analytik-Anwendungen aufrufbares Framework eingebaut. Dieses Framework können Firmen aus allen industriellen Sektoren nutzen, die vor dem Multi-Arm-Bandit-Problem stehen, und damit durch die Algorithmen des Frameworks unterstützt werden.

Software Campus-Partner: TU BerlinSAP SE

Umsetzungszeitraum: 01.04.2015 - 31.03.2017