Technische Samenvatting: Beperkte Gebruiker–Item Allocatie voor E-commerce Marketingcampagnes

Probleemdefinitie: Auto-Targeting

Het artikel behandelt een combinatorisch toewijzingsprobleem in e-commerce marketing dat bekend staat als auto-targeting. In tegenstelling tot traditionele benaderingen die de selectie van items loskoppelt van de gebruikerstoewijzing of een vooraf gedefinieerde campagnestructuur veronderstellen, formaliseert dit werk het probleem als een gezamenlijke optimalisatieopgave. Het doel is om gelijktijdig een verzameling gebruikers en een verzameling items te partitioneren in $K$ disjuncte campagnes (groepen), zodanig dat:

1. Cohesie: Elke campagne de totale binnen-groep affiniteit tussen de toegewezen gebruikers en items maximaliseert.
2. Disjunctheid: Elke gebruiker en elk item in maximaal één campagne voorkomt.
3. Restricties: Elke campagne moet een vast aantal items ($I$) bevatten en een aantal gebruikers binnen een specifieke reeks ($\tau_{min} \le |U_k| \le \tau_{max}$).

De affiniteit tussen gebruikers en items wordt afgeleid uit een gedeelde embedding-ruimte (geleerd uit historische interacties zoals klikken of aankopen), waarbij nabijheid duidt op wederzijds belang. De doelfunctie streeft naar het maximaliseren van de som van de affiteiten over alle campagnes:
$$\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)$$

Deze formulering is computationeel uitdagend vanwege de exponentiële zoekruimte en de gekoppelde restricties, waardoor exacte oplossingen onhaalbaar zijn voor grootschalige datasets.

Methodologie

De auteurs stellen drie complementaire heuristische strategieën voor om dit probleem op te lossen, naast Simulated Annealing (SA) als baseline:

1. Beperkte Spectrale Biclustering

Deze aanpak past spectrale co-clustering aan om dichte regio's in de gebruiker–item affiniteitsmatrix te identificeren.

• Oversampling: Het berekent initieel $k' = \alpha k$ biclusters (waarbij $\alpha \ge 2$) om een diverse kandidaat-pool te waarborgen.
• Pruning: Kandidaten worden gesnoeid om aan de grootte-restricties te voldoen. Items en gebruikers worden sequentieel verwijderd op basis van hun gemiddelde affiniteit binnen de bicluster totdat de maximale grootte is bereikt.
• Selectie: De resterende kandidaten worden gerangschikt op dichtheid (gemiddelde affiniteit), en de top $k$ niet-overlappende biclusters worden geselecteerd als de definitieve campagnes.

2. Multi-Armed Bandit (MAB) Optimalisatie

Deze methode behandelt campagnes als "armen" in een bandit-framework, waarbij een balans wordt gezocht tussen exploitatie (entiteiten toewijzen aan campagnes met een hoge affiniteit) en exploratie.

• Gekoppelde Beloningen: Beloningen zijn endogeen; de affiniteit van een entiteit voor een campagne hangt af van de huidige samenstelling van die campagne.
• Strategieën: De auteurs implementeren twee exploratie-bonussen:
  • UCB1: Voegt een betrouwbaarheidsinterval toe aan de affiniteitsscore.
  • Thompson Sampling: Perturbeert scores met Gaussische ruis die krimpt naarmate een campagne meer toewijzingen ontvangt.
• Mechanisme: Het algoritme wisselt af tussen fasen van gebruiker- en itemtoewijzing, waarbij gebruik wordt gemaakt van rolling-window statistieken met exponentiële decay om zich aan te passen aan veranderende campagne-composities.

3. Greedy Local Search

Deze strategie maakt gebruik van een hebzuchtige procedure met capaciteitsrestricties, gevolgd door verfijning.

• Greedy Toewijzing: Entiteiten worden aan campagnes toegewezen op basis van de maximale verbetering van de score, verwerkt in aflopende volgorde van potentieel gewin.
• Pairwise Swaps: Een lokale zoekstap evalueert het wisselen van entiteiten tussen verschillende campagnes om lokale optima te vermijden. Als een wissel de doelfunctie verbetert terwijl de haalbaarheid behouden blijft, wordt deze uitgevoerd.
• Iteratie: Het proces wisselt af tussen gebruiker- en itemupdates voor een vast aantal iteraties.

Baseline: Sequentiële Simulated Annealing

De auteurs gebruiken Simulated Annealing (SA) als baseline. Het globale probleem wordt gedecomposeerd in $K$ sequentiële subproblemen. Voor elke campagne voert SA een stochastische lokale zoektocht uit (met behulp van add-, remove- en swap-operaties) met een temperatuur-gecontroleerde acceptatiekans om de optimale bicluster te benaderen.

Belangrijkste Bijdragen

1. Formalisering van Auto-Targeting: Het artikel definieert een nieuw gezamenlijk optimalisatieprobleem dat zowel de campagnestructuur als de gebruiker–item toewijzingen gelijktijdig afleidt, waarmee een gat wordt gedicht waar bestaande methoden doorgaans één zijde van de toewijzing vastleggen.
2. Algoritmische Adaptatie: De auteurs passen drie verschillende benaderingen aan (beperkte spectrale biclustering, greedy local search en multi-armed bandits) om de specifie-ke restricties van disjuncte dekking en capaciteitslimieten in een gekoppelde setting te hanteren.
3. Uitgebreide Evaluatie: De methoden worden geëvalueerd op drie verschillende databronnen:
   • Synthetische Data: Gecontroleerde omgevingen met bekende grondwaarheid-structuren.
   • Publieke Benchmarks: Amazon Reviews datasets (Baby Products, Musical Instruments).
   • Propriëtaire Data: Grootschalige commerciële datasets (IKEA, Interior Design).

Resultaten en Prestaties

De evaluatie maakt gebruik van metrieken waaronder Utility (totale affiniteit), Quality (gemiddelde affiniteit), Lift (verbetering ten opzichte van willekeurige toewijzing) en de Gini-coëfficiënt (verdeling van utility over gebruikers).

• Oplossingskwaliteit: Beperkte Spectrale Biclustering behaalt consistent de hoogste scores in Lift, Quality en eerlijkheid (laagste Gini-coëfficiënten) over alle datasets. Het is bijzonder effectief in het terugvinden van coherente regio's met een hoge affiniteit, zelfs wanneer de onderliggende structuur ruisachtig of overlappend is.
• Trade-off tussen Schaalbaarheid en Kwaliteit:
  • Biclustering is zeer efficiënt op kleinere datasets, maar wordt computationeel duur naarmate de affiniteitsmatrix groeit (bijv. de runtime steeg van 1,2 minuten op IKEA naar 66,2 minuten op Interior Design).
  • Bandit-gebaseerde methoden (UCB1 en Thompson Sampling) bieden een schaalbare alternatief voor grote datasets, waarbij ze een concurrerende prestatie leveren met een aanzienlijk lagere runtime dan de greedy of SA-methoden op zeer grote schaal.
  • Greedy Local Search is over het algemeen trager dan de bandit-methoden vanwege herhaalde lokale zoekstappen.
• Baseline Prestaties: Simulated Annealing presteert aanzienlijk slechter dan de voorgestelde methoden wat betreft oplossingskwaliteit en brengt de hoogste computationele kosten met zich mee (vaakt uren werk vereisend). De auteurs wijten dit aan de moeilijkheid om betekenisvolle vooruitgang te boeken in hoogdimensionale combinatorische ruimtes met enkelvoudige entiteit-bewegingen.

Betekenis en Claims

Het artikel claimt dat het expliciet modelleren van de gezamenlijke gebruiker–item structuur cruciaal is voor effectief campagnedesign. De resultaten suggereren dat:

• Gezamenlijke Optimalisatie Superieur is: Het ontkoppelen van itemselectie van gebruikerstoewijzing mist groeperingen die alleen door gezamenlijke optimalisatie aan het licht komen.
• Biclustering Latente Intentie Vastlegt: Kwalitatieve analyse (bijv. op de Musical Instruments dataset) laat zien dat biclustering campagnes terugvindt die in lijn zijn met latente gebruikersintentie (bijv. het groeperen van items voor saxofoononderhoud) in plaats van oppervlakkige taxonomieën.
• Robuustheid tegen Ruis: Biclustering is robuust tegen toenemende cluster-variantie en ruis, waarbij het methoden overtreft die vertrouwen op individuele entiteit-signalen wanneer het affiniteitssignaal globaal geconcentreerd is in een klein deel van de paren maar diffuus per gebruiker.
• Praktische Trade-offs: Hoewel biclustering de hoogste kwaliteit levert, bieden bandit-gebaseerde methoden een levensvatbaar, schaalbaar alternatief voor zeer grootschalige commerciële implementaties waar runtime een primaire beperking is.

De auteurs concluderen dat hoewel hun framework de relevantie en efficiëntie van targeting verbetert, het rust op geleerde embeddings uit gedragsdata, wat transparantie en eerlijkheid vereist om bestaande ongelijkheden in gebruikersgerichtheid te voorkomen.