Spectral bandits for smooth graph functions with applications in recommender systems

Riepilogo Tecnico: Banditi Spettrali per Funzioni Lisce su Grafi

Formulazione del Problema
Questo articolo affronta un problema di bandito multi-braccio in cui i bracci corrispondono ai nodi di un grafo noto $G=(V, E)$, e il payoff atteso della selezione di un braccio è determinato da una funzione liscia definita sul grafo. In questo contesto, si assume che la funzione di ricompensa $f$ sia una combinazione lineare dei vettori propri del Laplaciano del grafo $L$. Nello specifico, se $Q$ contiene i vettori propri di $L$ come colonne, la ricompensa per il nodo $v$ è $f_\alpha(v) = \langle x_v, \alpha^* \rangle$, dove $x_v$ è la $v$-esima riga di $Q$ e $\alpha^*$ è un vettore di pesi sconosciuto.

La sfida principale sorge quando il numero di nodi $N$ (e quindi la dimensione dello spazio delle caratteristiche $D=N$) è molto grande, potenzialmente superiore all'orizzonte temporale $T$ del processo di apprendimento ($T < N$). Gli algoritmi standard per banditi lineari, che tipicamente scalano il loro rimpianto con la dimensione ambientale $D$ o con il numero di bracci $K$, avrebbero prestazioni scarse in questo regime. L'articolo assume che la funzione vera sia "liscia", il che significa che i coefficienti $\alpha^*$ associati ai vettori propri corrispondenti a grandi autovalori sono piccoli, mentre quelli associati a piccoli autovalori sono più grandi.

Metodologia
Gli autori propongono due algoritmi che sfruttano le proprietà spettrali del grafo per ottenere limiti di rimpianto che scalano con una "dimensione effettiva" $d$ anziché con l'intera dimensione $N$.

1. Dimensione Effettiva ($d$): L'articolo introduce una definizione formale della dimensione effettiva $d$ basata sulla crescita degli autovalori del Laplaciano regolarizzato $\Lambda = \Lambda_L + \lambda I$. $d$ è definita come il più grande intero tale che $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. Questa metrica cattura il numero di dimensioni "rilevanti" nel problema, che è tipicamente molto inferiore a $N$ nei grafi reali.

2. SpectralUCB: Questo algoritmo è una modifica dell'algoritmo LinUCB. Impiega un stimatore dei minimi quadrati regolarizzato per $\alpha^*$ utilizzando la base spettrale. Crucialmente, costruisce limiti di confidenza per le ricompense previste utilizzando la dimensione effettiva $d$ anziché la dimensione ambientale $D$. L'algoritmo seleziona il nodo che massimizza il limite superiore di confidenza: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$, dove $c_t$ dipende da $d$.

3. Campionamento Thompson Spettrale (SpectralTS): Questo algoritmo utilizza un approccio bayesiano. Mantiene una distribuzione a posteriori su $\alpha^*$, modellata come una Gaussiana $N(\hat{\alpha}_t, v^2 V_t^{-1})$. La covarianza a priori è impostata sul Laplaciano regolarizzato $\Lambda$, codificando l'assunzione che le funzioni lisce (componenti a basso autovalore) siano più probabili. Ad ogni passo, viene estratto un campione $\tilde{\alpha}$ dalla distribuzione a posteriori e viene selezionato il nodo che massimizza $x_v^T \tilde{\alpha}$.

Contributi Chiave e Risultati Teorici

• Nuovo Framework: Questo è il primo lavoro a formalizzare problemi di bandito in cui i payoff sono funzioni lisce su un grafo, colmando il divario tra apprendimento su varietà/apprendimento semi-supervisionato e apprendimento online.
• Limiti di Rimpianto: L'articolo dimostra che sia SpectralUCB che SpectralTS raggiungono limiti di rimpianto cumulativo che scalano con la dimensione effettiva $d$:
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    Questi limiti sono significativi perché $d$ è spesso molto più piccolo di $N$, permettendo agli algoritmi di performare bene anche quando $T < N$.
• Efficienza Computazionale: Gli autori evidenziano un vantaggio computazionale per SpectralTS. Mentre SpectralUCB richiede il calcolo dei limiti di confidenza per tutti i $N$ bracci (portando a una complessità di $O(N^3)$ per passo nel caso peggiore in cui $D=N$), SpectralTS richiede solo l'estrazione di un vettore di parametri e la ricerca del massimo, operazioni che possono essere eseguite in modo più efficiente ($O(N^2)$ per passo).

Risultati Sperimentali
Gli autori hanno valutato gli algoritmi su dataset sintetici e reali:

• Dati Sintetici: Utilizzando grafi Barabási-Albert ($N=250$) in cui la vera funzione di ricompensa era una combinazione lineare dei primi 3 vettori propri più lisci. Nel regime $T < N$, sia SpectralUCB che SpectralTS hanno superato significativamente le loro controparti lineari (LinUCB e LinearTS) in termini di rimpianto cumulativo. SpectralTS ha inoltre dimostrato tempi di calcolo più rapidi.
• Dati Reali: Gli esperimenti sono stati condotti sul dataset MovieLens ($N=2019$ film), modellando le preferenze degli utenti come una funzione liscia su un grafo di similarità costruito dalle valutazioni dei film. I risultati hanno rispecchiato le scoperte sintetiche: gli algoritmi spettrali hanno raggiunto un rimpianto cumulativo inferiore rispetto alle linee di base dei banditi lineari. L'articolo nota che un buon estimatore delle preferenze degli utenti per migliaia di articoli potrebbe essere appreso da sole decine di valutazioni di nodi.

Significato e Affermazioni
L'articolo afferma che, sfruttando la liscietà delle funzioni sui grafi tramite decomposizione spettrale, è possibile risolvere problemi di apprendimento online con un gran numero di bracci senza che il rimpianto peggiori in modo significativo con il numero di nodi. L'introduzione della dimensione effettiva $d$ permette agli algoritmi di adattarsi alla complessità intrinseca della struttura del grafo. Il lavoro è motivato da applicazioni nel raccomandazione basata sui contenuti e nella pubblicità mirata nelle reti sociali, dove le preferenze o gli interessi degli utenti tendono a variare in modo liscio attraverso nodi connessi. Gli autori sottolineano che il loro approccio è particolarmente rilevante per scenari in cui il numero di interazioni disponibili ($T$) è piccolo rispetto al numero di articoli disponibili ($N$).