🤖 machine learning

Constrained user-item allocation for e-commerce marketing campaigns

Questo articolo affronta la sfida della selezione congiunta di utenti e articoli per campagne di marketing e-commerce formalizzando il problema come auto-targeting e proponendo una soluzione ibrida che combina il biclustering spettrale vincolato, la ricerca locale greedy e l'esplorazione multi-armed bandit per ottenere raggruppamenti di campagne scalabili e di alta qualità.

Autori originali: Maja Lindström, Natalija Glisovic, Jan von Pichowski, Tommy Löfstedt, Martin Rosvall

Pubblicato 2026-06-09

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Maja Lindström, Natalija Glisovic, Jan von Pichowski, Tommy Löfstedt, Martin Rosvall

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di gestire un enorme organizzatore di feste per un gigantesco negozio online. Il tuo compito è organizzare centinaia di diverse "mini-feste" (campagne di marketing). Ogni mini-festa ha bisogno di due cose: un gruppo specifico di ospiti (utenti) e un set specifico di snack e giochi (prodotti/articoli).

L'obiettivo è semplice: assicurarsi che ogni ospite riceva gli snack che ama davvero, e che ogni snack venga servito a un ospite che lo apprezzerà. Ma ci sono regole ferree:

Niente doppi passaggi: Un ospite può partecipare a una sola festa, e uno snack specifico può essere servito in una sola festa.
Limiti di dimensione: Ogni festa deve avere esattamente lo stesso numero di snack, ma il numero di ospiti può variare leggermente (entro un intervallo prestabilito).
Il colpo di scena: Non sai in anticipo quali snack vadano con quali ospiti. Devi scoprire le combinazioni perfette simultaneamente.

Il problema con i vecchi metodi

La maggior parte delle aziende fa questo in due fasi separate. Prima scelgono una lista di snack (ad esempio, "Promoviamo i sassofoni"). Poi cercano di trovare persone che amino i sassofoni.
L'articolo sostiene che questo sia come cercare di abbinare una serratura a una chiave guardando prima la serratura e poi cercando una chiave, senza mai controllare se si incastrino effettivamente. I migliori ospiti per una campagna dipendono dagli articoli, e i migliori articoli dipendono dagli ospiti. Devi risolvere il puzzle tutto in una volta.

Gli autori chiamano questo nuovo approccio "Auto-Targeting". È come un matchmaker automatico che costruisce le feste partendo da zero, basandosi su chi si sente naturalmente in sintonia con chi.

Le tre nuove strategie

Per risolvere questo enorme puzzle, gli autori hanno testato tre diverse strategie di "matchmaking":

1. Il "Rilevatore di Schemi" (Biclustering Spettrale Vincolato)
Immagina di avere un enorme foglio di calcolo che mostra quanto ogni persona ama ogni articolo. Questo metodo cerca "blocchi densi" di numeri elevati: aree dove un gruppo specifico di persone e un gruppo specifico di articoli si amano davvero a vicenda.

Come funziona: Trova questi cluster naturali, poi li ritaglia per adattarli alle regole della dimensione della festa (come tagliare una grande torta per farla stare in un piatto specifico).
Il risultato: È stato il campione. Ha trovato costantemente i gruppi più coesi, creando feste dove tutti erano genuinamente felici con i loro snack. Funziona incredibilmente bene su dati di piccole o medie dimensioni, ma se il foglio di calcolo diventa enorme, richiede molto tempo per elaborare i numeri.

2. Il "Tiro alla Fune" (Ricerca Locale Greedy)
Questo metodo è come un gioco di sedie musicali. Inizia assegnando casualmente gli ospiti alle feste. Poi guarda due ospiti in feste diverse e chiede: "Se li scambiassimo, l'entità totale della felicità aumenterebbe?". Se sì, avviene lo scambio. Continua a farlo, perfezionando i gruppi passo dopo passo.

Il risultato: È discreto, ma spesso si blocca in una soluzione "abbastanza buona" e non riesce a trovare quella perfetta perché è troppo concentrato su piccoli scambi immediati.

3. L' "Esploratore Curioso" (Multi-Armed Bandit)
Immagina di essere uno scommettitore in un casinò con molte slot machine (campagne). Vuoi tirare la leva che paga di più, ma vuoi anche provare le altre macchine nel caso siano migliori. Questo metodo bilancia l'exploitation (mettere le persone nei gruppi noti come migliori) con l'exploration (provare nuove, strane combinazioni per vedere se funzionano meglio).

Il risultato: È il velocista. Non sempre trova la festa assolutamente perfetta, ma trova una festa molto buona molto rapidamente, anche quando la lista degli ospiti è enorme. È la scelta migliore quando hai troppi dati perché il "Rilevatore di Schemi" possa gestirli in un tempo ragionevole.

La Baseline del "Simulated Annealing"

Gli autori hanno anche testato un metodo più vecchio chiamato "Simulated Annealing" (come raffreddare lentamente il metallo per renderlo resistente). Hanno scoperto che questo metodo era lento e non faceva un buon lavoro. Era come cercare di risolvere un cubo di Rubik ruotando casualmente un quadratino alla volta; richiedeva semplicemente troppo tempo per trovare una soluzione.

Cosa hanno scoperto

La qualità vince: Il "Rilevatore di Schemi" (Biclustering) ha creato le campagne di più alta qualità. I gruppi erano più "coesivi", il che significa che le persone e i prodotti si abbinavano perfettamente.
Equità: Il Rilevatore di Schemi ha anche fatto un lavoro migliore nel distribuire la "felicità" (affinità) equamente tra tutti gli ospiti, invece di creare solo pochi ospiti super felici mentre altri restavano con snack noiosi.
Il compromesso: Se hai un dataset piccolo, usa il Rilevatore di Schemi per i migliori risultati. Se hai un dataset massiccio (come un enorme sito di e-commerce), usa l' "Esploratore Curioso" (Bandit) perché scala molto più velocemente.

Il quadro generale

L'articolo dimostra che ottieni le migliori campagne di marketing quando smetti di trattare "persone" e "prodotti" come liste separate. Inveve, devi guardare l'immagine completa contemporaneamente. Trovando i "cluster" naturali dove persone e prodotti appartengono già insieme, puoi costruire campagne che sembrano personali e rilevanti, invece di limitarti a tirare a indovinare.

In breve: Non scegliere prima gli snack, poi trova gli ospiti. Guarda l'intera stanza, trova i gruppi naturali e costruisci le feste attorno a loro.

Riepilogo Tecnico: Allocazione Vincolata Utente-Articolo per Campagne di Marketing E-commerce

Definizione del Problema: Auto-Targeting

Il documento affronta un problema di assegnazione combinatoria nel marketing e-commerce noto come auto-targeting. A differenza degli approcci tradizionali che scindono la selezione degli articoli dall'assegnazione degli utenti o assumono una struttura di campagna predefinita, questo lavoro formalizza il problema come un compito di ottimizzazione congiunta. L'obiettivo è partizionare simultaneamente un insieme di utenti e un insieme di articoli in $K$ campagne disgiunte (gruppi) tali che:

Coesione: Ogni campagna massimizzi l'affinità totale all'interno del gruppo tra gli utenti e gli articoli assegnati.
Disgiunzione: Ogni utente e ogni articolo compaia al massimo in una sola campagna.
Vincoli: Ogni campagna deve contenere un numero fisso di articoli ( $I$ ) e un numero di utenti entro un intervallo specifico ( $\tau_{min} \le |U_k| \le \tau_{max}$ ).

L'affinità tra utenti e articoli è derivata da uno spazio di embedding condiviso (appreso da interazioni storiche come click o acquisti), dove la prossimità indica un interesse reciproco. La funzione obiettivo cerca di massimizzare la somma delle affinità attraverso tutte le campagne:
$\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)$

Questa formulazione è computazionalmente impegnativa a causa dello spazio di ricerca esponenziale e dell'accoppiamento dei vincoli, rendendo impraticabili le soluzioni esatte per dataset su larga scala.

Metodologia

Gli autori propongono tre strategie euristiche complementari per risolvere questo problema, insieme al Simulated Annealing (SA) come baseline:

1. Biclustering Spettrale Vincolato

Questo approccio adatta il co-clustering spettrale per identificare regioni dense nella matrice di affinità utente-articolo.

Oversampling: Calcola inizialmente $k' = \alpha k$ bicluster (dove $\alpha \ge 2$ ) per garantire un pool di candidati diversificato.
Pruning (Potatura): I candidati vengono potati per soddisfare i vincoli di dimensione. Articoli e utenti vengono rimossi sequenzialmente in base alla loro affinità media all'interno del bicluster fino al raggiungimento della dimensione massima.
Selezione: I candidati rimanenti sono classificati per densità (affinità media) e i primi $k$ bicluster non sovrapposti sono selezionati come campagne finali.

2. Ottimizzazione Multi-Armed Bandit (MAB)

Questo metodo tratta le campagne come "braccia" (arms) in un framework di bandit, bilanciando sfruttamento (assegnazione di entità a campagne ad alta affinità) ed esplorazione.

Ricompense Accoppiate: Le ricompense sono endogene; l'affinità di un'entità verso una campagna dipende dalla composizione attuale di quella campagna.
Strategie: Gli autori implementano due bonus di esplorazione:
- UCB1: Aggiunge un limite di confidenza al punteggio di affinità.
- Thompson Sampling: Perturba i punteggi con rumore gaussiano che si restringe man mano che una campagna riceve più assegnazioni.
Meccanismo: L'algoritmo alterna fasi di assegnazione di utenti e articoli, utilizzando statistiche a finestra mobile con decadimento esponenziale per adattarsi alle mutevoli composizioni delle campagne.

3. Ricerca Locale Greedy

Questa strategia impiega una procedura greedy con vincoli di capacità seguita da un raffinamento.

Assegnazione Greedy: Le entità vengono assegnate alle campagne in base al massimo miglioramento del punteggio, elaborate in ordine decrescente di potenziale guadagno.
Scambi a Coppie (Pairwise Swaps): Una fase di ricerca locale valuta lo scambio di entità tra diverse campagne per uscire dagli ottimi locali. Se uno scambio migliora l'obiettivo mantenendo la fattibilità, viene eseguito.
Iterazione: Il processo alterna aggiornamenti di utenti e articoli per un numero fissato di iterazioni.

Baseline: Simulated Annealing Sequenziale

Gli autori utilizzano il Simulated Annealing (SA) come baseline. Il problema globale viene scomposto in $K$ sottoproblemi sequenziali. Per ogni campagna, il SA esegue una ricerca locale stocastica (usando operazioni di aggiunta, rimozione e scambio) con una probabilità di accettazione controllata dalla temperatura per approssimare il bicluster ottimale.

Contributi Chiave

Formalizzazione dell'Auto-Targeting: Il documento definisce un nuovo problema di ottimizzazione congiunta che inferisce sia la struttura della campagna che le assegnazioni utente-articolo simultaneamente, affrontando una lacuna in cui i metodi esistenti tipicamente fissano un lato dell'assegnazione.
Adattamento Algoritmico: Gli autori adattano tre approcci distinti (biclustering spettrale vincolato, ricerca locale greedy e bandit multi-braccio) per gestire i vincoli specifici di copertura disgiunta e limiti di capacità in un contesto accoppiato.
Valutazione Completa: I metodi sono valutati su tre fonti di dati distinte:
- Dati Sintetici: Ambienti controllati con strutture di ground-truth note.
- Benchmark Pubblici: Dataset Amazon Reviews (Baby Products, Musical Instruments).
- Dati Proprietari: Dataset commerciali su larga scala (IKEA, Interior Design).

Risultati e Prestazioni

La valutazione utilizza metriche tra cui Utility (affinità totale), Quality (affinità media), Lift (miglioramento rispetto all'assegnazione casuale) e il Coefficiente di Gini (distribuzione dell'utility tra gli utenti).

Qualità della Soluzione: Il Biclustering Spettrale Vincolato raggiunge costantemente i punteggi più alti in Lift, Quality e fairness (coefficienti di Gini più bassi) in tutti i dataset. È particolarmente efficace nel recuperare regioni coerenti ad alta affinità, anche quando la struttura sottostante è rumorosa o sovrapposta.
Trade-off tra Scalabilità e Qualità:
- Il Biclustering è altamente efficiente su dataset più piccoli ma diventa computazionalmente costoso man mano che la matrice di affinità cresce (ad esempio, il tempo di esecuzione è passato da 1,2 minuti su IKEA a 66,2 minuti su Interior Design).
- I metodi basati su Bandit (UCB1 e Thompson Sampling) offrono un'alternativa scalabile per grandi dataset, mantenendo prestazioni competitive con un tempo di esecuzione significativamente inferiore rispetto ai metodi greedy o SA su scale molto grandi.
- La Ricerca Locale Greedy è generalmente più lenta dei metodi bandit a causa dei ripetuti passaggi di ricerca locale.
Prestazioni della Baseline: Il Simulated Annealing performa sostanzialmente peggio dei metodi proposti in termini di qualità della soluzione e comporta il costo computazionale più elevato (spesso richiedendo ore). Gli autori attribuiscono ciò alla difficoltà di compiere progressi significativi in spazi combinatori ad alta dimensionalità utilizzando spostamenti di singola entità.

Significato e Rivendicazioni

Il documento sostiene che modellare esplicitamente la struttura congiunta utente-articolo è critico per un design efficace delle campagne. I risultati suggeriscono che:

L'Ottimizzazione Congiunta è Superiore: Scindere la selezione degli articoli dall'assegnazione degli utenti fa perdere raggruppamenti che emergono solo dall'ottimizzazione congiunta.
Il Biclustering Cattura l'Intento Latente: L'analisi qualitativa (ad esempio, sul dataset Musical Instruments) mostra che il biclustering recupera campagne allineate con l'intento latente dell'utente (ad esempio, raggruppando articoli per la manutenzione del sassofono) piuttosto che tassonomie superficiali.
Robustezza al Rumore: Il biclustering è robusto all'aumento della varianza del cluster e del rumore, superando i metodi che si affidano a segnali di singole entità quando il segnale di affinità è concentrato globalmente in una piccola frazione di coppie ma diffuso per singolo utente.
Trade-off Pratici: Sebbene il biclustering offra la qualità più elevata, i metodi basati su bandit forniscono un'alternativa scalabile e valida per implementazioni commerciali su scala molto vasta dove il tempo di esecuzione è un vincolo primario.

Gli autori concludono che, sebbene il loro framework migliori la rilevanza del targeting e l'efficienza, esso si basa su embedding appresi da dati comportamentali, rendendo necessarie considerazioni di trasparenza e correttezza per evitare di rafforzare le disparità esistenti nel targeting degli utenti.