🤖 machine learning

Constrained user-item allocation for e-commerce marketing campaigns

Diese Arbeit befasst sich mit der Herausforderung der gemeinsamen Auswahl von Nutzern und Artikeln für E-Commerce-Marketingkampagnen, indem sie das Problem als Auto-Targeting formalisiert und eine hybride Lösung vorschlägt, die beschränktes spektrales Biclustering, gierige lokale Suche und Multi-Armed-Bandit-Exploration kombiniert, um hochwertige, skalierbare Kampagnengruppierungen zu erreichen.

Ursprüngliche Autoren: Maja Lindström, Natalija Glisovic, Jan von Pichowski, Tommy Löfstedt, Martin Rosvall

Veröffentlicht 2026-06-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maja Lindström, Natalija Glisovic, Jan von Pichowski, Tommy Löfstedt, Martin Rosvall

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie leiten eine riesige Partyplanung für einen gigantischen Online-Shop. Ihr Job ist es, hunderte verschiedene „Mini-Partys“ (Marketingkampagnen) zu organisieren. Jede Mini-Party benötigt zwei Dinge: eine bestimmte Gruppe von Gästen (Nutzern) und ein spezifisches Set an Snacks und Spielen (Produkten/Artikeln).

Das Ziel ist einfach: Sicherzustellen, dass jeder Gast Snacks bekommt, die er wirklich liebt, und dass jeder Snack zu einem Gast geht, der ihn auch genießen wird. Aber es gibt strenge Regeln:

Kein Doppel-Dippen: Ein Gast kann nur auf einer Party sein, und ein spezifischer Snack kann nur auf einer Party serviert werden.
Größenbeschränkungen: Jede Party muss exakt die gleiche Anzahl an Snacks haben, aber die Anzahl der Gäste kann leicht variieren (innerhalb eines festgelegten Bereichs).
Der Twist: Sie wissen im Voraus nicht, welche Snacks zu welchen Gästen passen. Sie müssen die perfekten Paarungen gleichzeitig herausfinden.

Das Problem mit alten Methoden

Die meisten Unternehmen machen dies in zwei separaten Schritten. Zuerst wählen sie eine Liste von Snacks aus (z. B. „Lass uns Saxofone bewerben“). Dann versuchen sie, Menschen zu finden, die Saxofone lieben.
Das Paper argumentiert, dass dies so ist, als würde man versuchen, ein Schloss zu einem Schlüssel zu passen, indem man zuerst nach dem Schloss schaut, dann nach einem Schlüssel sucht, ohne jemals zu prüfen, ob sie tatsächlich zusammenpassen. Die besten Gäste für eine Kampagne hängen von den Artikeln ab, und die besten Artikel hängen von den Gästen ab. Man muss das Puzzle alles auf einmal lösen.

Die Autoren nennen diesen neuen Ansatz „Auto-Targeting“. Es ist wie ein automatischer Partnervermittler, der die Partys von Grund auf neu erstellt, baselt darauf, wer sich natürlich mit wem versteht.

Die drei neuen Strategien

Um dieses riesige Puzzle zu lösen, haben die Autoren drei verschiedene „Matchmaking“-Strategien getestet:

1. Der „Mustererkennner“ (Constrained Spectral Biclustering)
Stellen Sie sich eine riesige Tabelle vor, die zeigt, wie sehr jede Person jedes Item mag. Diese Methode sucht nach „dichten Blöcken“ hoher Zahlen – Bereichen, in denen eine bestimmte Gruppe von Menschen und eine bestimmte Gruppe von Artikeln sich alle wirklich gerne mögen.

Wie es funktioniert: Es findet diese natürlichen Cluster und beschneidet sie dann, um sie an die Partygrößen-Regeln anzupassen (wie das Schneiden eines großen Kuchens, um ihn auf einen bestimmten Teller zu passen).
Das Ergebnis: Dies war der Sieger. Es fand konsistent die kohärenteren Gruppen und schuf Partys, bei denen alle wirklich glücklich mit ihren Snacks waren. Es funktioniert hervorragend bei kleinen bis mittelgroßen Datenmengen, aber wenn die Tabelle riesig wird, dauert es sehr lange, die Zahlen zu berechnen.

2. Das „Tauziehen“ (Greedy Local Search)
Diese Methode ist wie ein Spiel mit Stühlen. Sie beginnt damit, Gäste zufällig Gruppen zuzuweisen. Dann schaut sie sich zwei Gäste in verschiedenen Gruppen an und fragt: „Wenn wir sie tauschen würden, würde das gesamte Glück steigen?“ Wenn ja, tauschen sie. Es führt dies Schritt für Schritt fort und verfeinert die Gruppen.

Das Ergebnis: Es ist ordentlich, bleibt aber oft bei einer „gut genug“-Lösung stecken und kann nicht die perfekte Lösung finden, weil es zu sehr auf kleine, unmittelbare Wechsel fokussiert ist.

3. Der „Neugierige Entdecker“ (Multi-Armed Bandit)
Stellen Sie sich vor, Sie sind ein Spieler in einem Casino mit vielen Spielautomaten (Kampagnen). Sie wollen den Hebel ziehen, der am meisten auszahlt, aber Sie wollen auch die anderen Maschinen ausprobieren, falls diese besser sein könnten. Diese Methode balanciert Exploitation (Menschen in die besten bekannten Gruppen zu stecken) mit Exploration (neue, seltsame Kombinationen auszuprobieren, um zu sehen, ob sie besser funktionieren).

Das Ergebnis: Dies ist der Sprinter. Es findet nicht immer die absolut perfekte Party, aber es findet sehr schnell eine sehr gute Party, selbst wenn die Gästeliste massiv ist. Es ist die beste Wahl, wenn Sie zu viele Daten für den „Mustererkennner“ haben, um in einer angemessenen Zeit zu arbeiten.

Die „Simulated Annealing“-Baseline

Die Autoren haben auch eine klassische Methode namens „Simulated Annealing“ (ähnlich wie das langsame Abkühlen von Metall, um es stark zu machen) getestet. Sie fanden heraus, dass diese Methode langsam war und nicht besonders gut funktionierte. Es war, als würde man versuchen, einen Rubik's Cube zu lösen, indem man zufällig eine einzelne Fläche nach dem anderen dreht; es dauerte einfach zu lange, um eine Lösung zu finden.

Was sie herausgefunden haben

Qualität gewinnt: Der „Mustererkennner“ (Biclustering) erstellte die qualitativ hochwertigeren Kampagnen. Die Gruppen waren „kohärenter“, was bedeutet, dass die Menschen und Produkte perfekt zusammenpassten.
Fairness: Der Mustererkennner war auch besser darin, das „Glück“ (Affinität) gleichmäßig unter allen Gästen zu verteilen, anstatt nur ein paar superglückliche Gäste zu haben, während andere mit langweiligen Snacks zurückgelassen wurden.
Der Trade-off: Wenn Sie einen kleinen Datensatz haben, nutzen Sie den Mustererkennner für die besten Ergebnisse. Wenn Sie einen massiven Datensatz haben (wie eine riesige E-Commerce-Seite), nutzen Sie den „Neugierigen Entdecker“ (Bandit), da er viel schneller skaliert.

Das große Ganze

Das Paper beweist, dass man die besten Marketingkampagnen erhält, wenn man aufhört, „Menschen“ und „Produkte“ als separate Listen zu behandeln. Stattdessen müssen Sie das Gesamtbild betrachten. Indem Sie die natürlichen „Cluster“ finden, zu denen Menschen und Produkte bereits gehören, können Sie Kampagnen erstellen, die sich persönlich und relevant anfühlen, anstatt nur zu raten.

Kurz gesagt: Wählen Sie nicht erst die Snacks und suchen dann die Gäste. Betrachten Sie den ganzen Raum, finden Sie die natürlichen Gruppen und bauen Sie die Partys um sie herum auf.

Technisches Resümee: Beschränkte Nutzer–Artikel-Allokation für E-Commerce-Marketingkampagnen

Problemdefinition: Auto-Targeting

Die Arbeit befasst sich mit einem kombinatorischen Zuweisungsproblem im E-Commerce-Marketing, bekannt als Auto-Targeting. Im Gegensatz zu herkömmlichen Ansätzen, die die Artikelauswahl von der Nutzerzuweisung entkoppeln oder eine vordefinierte Kampagnenstruktur voraussetzen, formalisiert diese Arbeit das Problem als eine gemeinsame Optimierungsaufgabe (Joint Optimization). Das Ziel besteht darin, gleichzeitig eine Menge von Nutzern und eine Menge von Artikeln in $K$ disjunkte Kampagnen (Gruppen) zu unterteilen, sodass:

Kohäsion: Jede Kampagne die gesamte innerhalb der Gruppe liegende Affinität zwischen den zugewiesenen Nutzern und Artikeln maximiert.
Disjunktheit: Jeder Nutzer und jeder Artikel in höchstens einer Kampagne erscheint.
Beschränkungen: Jede Kampagne muss eine feste Anzahl von Artikeln ( $I$ ) und eine Anzahl von Nutzern innerhalb eines spezifischen Bereichs ( $\tau_{min} \le |U_k| \le \tau_{max}$ ) enthalten.

Die Affinität zwischen Nutzern und Artikeln wird aus einem gemeinsamen Embedding-Raum abgeleitet (der aus historischen Interaktionen wie Klicks oder Käufen gelernt wurde), wobei die Nähe auf ein gegenseitiges Interesse hindeutet. Die Zielfunktion zielt darauf ab, die Summe der Affinitäten über alle Kampagnen hinweg zu maximieren:
$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$

Diese Formulierung ist aufgrund des exponentiellen Suchraums und der Kopplung der Beschränkungen rechentechnisch anspruchsvoll, was exakte Lösungen für große Datensätze unmöglich macht.

Methodik

Die Autoren schlagen drei komplementäre heuristische Strategien vor, um dieses Problem zu lösen, neben Simulated Annealing (SA) als Baseline:

1. Beschränktes Spektrales Biclustering

Dieser Ansatz passt das spektrale Co-Clustering an, um dichte Regionen in der Nutzer–Artikel-Affinitätsmatrix zu identifizieren.

Oversampling: Er berechnet zunächst $k' = \alpha k$ Bicluster (wobei $\alpha \ge 2$ ), um einen vielfältigen Kandidatenpool sicherzustellen.
Pruning (Beschneidung): Kandidaten werden beschnitten, um die Größenbeschränkungen zu erfüllen. Artikel und Nutzer werden sequenziell basierend auf ihrer durchschnittlichen Affinität innerhalb des Biclusters entfernt, bis die maximale Größe erreicht ist.
Selektion: Die verbleibenden Kandidaten werden nach Dichte (durchschnittliche Affinität) geordnet, und die obersten $k$ nicht-überlappenden Bicluster werden als endgültige Kampagnen ausgewählt.

2. Multi-Armed Bandit (MAB) Optimierung

Diese Methode behandelt Kampagnen als „Arme“ in einem Bandit-Framework, wobei ein Gleichgewicht zwischen Exploitation (Zuweisung von Entitäten zu hoch-affinen Kampagnen) und Exploration gewahrt wird.

Gekoppelte Belohnungen: Die Belohnungen sind endogen; die Affinität einer Entität zu einer Kampagne hängt von der aktuellen Zusammensetzung dieser Kampagne ab.
Strategien: Die Autoren implementieren zwei Exploration-Bonuses:
- UCB1: Fügt eine Konfidenzgrenze zum Affinitätsscore hinzu.
- Thompson Sampling: Perturbiert die Scores mit Gaußschem Rauschen, das kleiner wird, je mehr Zuweisungen eine Kampagne erhält.
Mechanismus: Der Algorithmus wechselt zwischen Phasen der Nutzer- und Artikelzuweisung unter Verwendung von Rolling-Window-Statistiken mit exponentiellem Zerfall, um sich an die sich ändernden Kampagnenzusammensetzungen anzupassen.

3. Greedy Local Search

Diese Strategie verwendet ein Greedy-Verfahren mit Kapazitätsbeschränkungen, gefolgt von einer Verfeinerung.

Greedy-Zuweisung: Entitäten werden basierend auf der maximalen Score-Verbesserung zugewiesen, wobei sie in absteigender Reihenfolge des potenziellen Gewinns verarbeitet werden.
Paarweise Swaps: Ein Local-Search-Schritt evaluiert das Vertauschen von Entitäten zwischen verschiedenen Kampagnen, um lokale Optima zu verlassen. Wenn ein Swap die Zielfunktion verbessert und gleichzeitig die Durchführbarkeit beibehält, wird er ausgeführt.
Iteration: Der Prozess wechselt zwischen Nutzer- und Artikel-Updates für eine feste Anzahl von Iterationen.

Baseline: Sequentielles Simulated Annealing

Die Autoren verwenden Simulated Annealing (SA) als Baseline. Das globale Problem wird in $K$ sequentielle Teilprobleme zerlegt. Für jede Kampagne führt SA eine stochastische lokale Suche (unter Verwendung von Add-, Remove- und Swap-Operationen) mit einer temperaturgesteuerten Akzeptanzwahrscheinlichkeit durch, um einen optimalen Bicluster zu approximieren.

Wichtigste Beiträge

Formalisierung von Auto-Targeting: Das Paper definiert ein neuartiges gemeinsames Optimierungsproblem, das sowohl die Kampagnenstruktur als auch die Nutzer–Artikel-Zuweisungen simultan inferiert und damit eine Lücke schließt, in der bestehende Methoden typischerweise eine Seite der Zuweisung fixieren.
Algorithmische Anpassung: Die Autoren passen drei unterschiedliche Ansätze (beschränktes spektrales Biclustering, Greedy Local Search und Multi-Armed Bandits) an, um die spezifischen Beschränkungen der disjunkten Abdeckung und der Kapazitätsgrenzen in einem gekoppelten Setting zu handhaben.
Umfassende Evaluierung: Die Methoden werden auf drei unterschiedlichen Datenquellen evaluiert:
- Synthetische Daten: Kontrollierte Umgebungen mit bekannter Ground-Truth-Struktur.
- Öffentliche Benchmarks: Amazon Reviews Datensätze (Baby Produkte, Musikinstrumente).
- Proprietäre Daten: Große kommerzielle Datensätze (IKEA, Interior Design).

Ergebnisse und Leistung

Die Evaluierung nutzt Metriken wie Utility (Gesamtaffinität), Quality (durchschnittliche Affinität), Lift (Verbesserung gegenüber zufälliger Zuweisung) und den Gini-Koeffizienten (Verteilung der Utility über die Nutzer).

Lösungsqualität: Beschränktes Spektrales Biclustering erzielt konsistent die höchsten Werte in Lift, Quality und Fairness (niedrigste Gini-Koeffizienten) über alle Datensätze hinweg. Es ist besonders effektiv darin, kohärente High-Affinity-Regionen zu rekonstruieren, selbst wenn die zugrunde liegende Struktur verrauscht oder überlappend ist.
Skalierbarkeit vs. Qualitäts-Trade-off:
- Biclustering ist auf kleineren Datensätzen hocheffizient, wird aber rechenintensiv, wenn die Affinitätsmatrix wächst (z. B. stieg die Laufzeit von 1,2 Minuten bei IKEA auf 66,2 Minuten bei Interior Design).
- Bandit-basierte Methoden (UCB1 und Thompson Sampling) bieten eine skalierbare Alternative für große Datensätze und halten eine wettbewerbsfähige Leistung bei signifikant geringerer Laufzeit als Greedy- oder SA-Methoden auf sehr großen Skalen.
- Greedy Local Search ist im Allgemeinen langsamer als Bandit-Methoden aufgrund der wiederholten Local-Search-Schritte.
Baseline-Leistung: Simulated Annealing schneidet in Bezug auf die Lösungsqualität deutlich schlechter ab als die vorgeschlagenen Methoden und verursacht die höchsten Rechenkosten (oft mehrere Stunden). Die Autoren führen dies auf die Schwierigkeit zurück, in hochdimensionalen kombinatorischen Räumen durch Einzelentitäts-Bewegungen signifikante Fortschritte zu erzielen.

Bedeutung und Behauptungen

Das Paper behauptet, dass die explizite Modellierung der gemeinsamen Nutzer–Artikel-Struktur entscheidend für ein effektives Kampagnendesign ist. Die Ergebnisse legen nahe:

Gemeinsame Optimierung ist überlegen: Die Entkopplung der Artikelauswahl von der Nutzerzuweisung übersieht Gruppierungen, die sich erst aus der gemeinsamen Optimierung ergeben.
Biclustering erfasst latente Intentionen: Eine qualitative Analyse (z. B. am Musical Instruments Datensatz) zeigt, dass Biclustering Kampagnen rekonstruiert, die mit der latenten Nutzerintention (z. B. Gruppierung von Saxophon-Wartungsprodukten) übereinstimmen, statt nur oberflächliche Taxonomien abzubilden.
Robustheit gegenüber Rauschen: Biclustering ist robust gegenüber zunehmender Cluster-Varianz und Rauschen und übertrifft Methoden, die auf individuellen Entitäts-Signalen basieren, wenn das Affinitätssignal global in einem kleinen Bruchteil der Paare konzentriert, aber pro Nutzer diffus ist.
Praktische Trade-offs: Während Biclustering die höchste Qualität liefert, bieten Bandit-basierte Methoden eine praktikable, skalierbare Alternative für sehr große kommerzielle Implementierungen, bei denen die Laufzeit die primäre Beschränkung darstellt.

Die Autoren kommen zu dem Schluss, dass ihr Framework zwar die Targeting-Relevanz und Effizienz verbessert, es jedoch auf aus Verhaltensdaten gelernten Embeddings basiert, was Transparenz- und Fairness-Überlegungen erfordert, um die Verstärkung bestehender Disparitäten im Nutzer-Targeting zu vermeiden.