Spectral bandits for smooth graph functions with applications in recommender systems

Technische Samenvatting: Spectrale Bandieten voor Gladde Graffuncties

Probleemformulering
Dit artikel behandelt een multi-armed bandit-probleem waarbij de armen corresponderen met de knopen van een bekende graaf $G=(V, E)$, en de verwachte opbrengst van het trekken van een arm wordt bepaald door een gladde functie die op de graaf is gedefinieerd. In deze setting wordt de beloningsfunctie $f$ verondersteld een lineaire combinatie te zijn van de eigenvectoren van de graf-Laplaciaan $L$. Specifiek, als $Q$ de eigenvectoren van $L$ bevat als kolommen, is de beloning voor knoop $v$ gelijk aan $f_\alpha(v) = \langle x_v, \alpha^* \rangle$, waarbij $x_v$ de $v$-de rij van $Q$ is en $\alpha^*$ een onbekend gewichtsvector is.

De kernuitdaging doet zich voor wanneer het aantal knopen $N$ (en dus de dimensie van de kenmerkruimte $D=N$) zeer groot is, mogelijk groter dan de tijds horizon $T$ van het leerproces ($T < N$). Standaard lineaire bandit-algoritmen, die doorgaans hun regret schalen met de omgevende dimensie $D$ of het aantal armen $K$, zouden in dit regime slecht presteren. Het artikel veronderstelt dat de ware functie "glad" is, wat betekent dat de coëfficiënten $\alpha^*$ die corresponderen met eigenvectoren van grote eigenwaarden klein zijn, terwijl die die corresponderen met kleine eigenwaarden groter zijn.

Methodologie
De auteurs stellen twee algoritmen voor die gebruikmaken van de spectrale eigenschappen van de graaf om regretgrenzen te bereiken die schalen met een "effectieve dimensie" $d$ in plaats van de volledige dimensie $N$.

1. Effectieve Dimensie ($d$): Het artikel introduceert een formele definitie van effectieve dimensie $d$ gebaseerd op de groei van de eigenwaarden van de geregulariseerde Laplaciaan $\Lambda = \Lambda_L + \lambda I$. $d$ wordt gedefinieerd als het grootste gehele getal zodat $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. Deze metriek vangt het aantal "relevante" dimensies in het probleem, wat in real-world grafen doorgaans veel kleiner is dan $N$.

2. SpectralUCB: Dit algoritme is een modificatie van het LinUCB-algoritme. Het maakt gebruik van een geregulariseerde kleinste-kwadraten-schatter voor $\alpha^*$ met behulp van de spectrale basis. Cruciaal is dat het betrouwbaarheidsintervallen bouwt voor de voorspelde beloningen met behulp van de effectieve dimensie $d$ in plaats van de omgevende dimensie $D$. Het algoritme selecteert de knoop die de bovengrens van het betrouwbaarheidsinterval maximaliseert: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$, waarbij $c_t$ afhankelijk is van $d$.

3. Spectrale Thompson Sampling (SpectralTS): Dit algoritme maakt gebruik van een Bayesiaanse aanpak. Het onderhoudt een posterior-verdeling over $\alpha^*$, gemodelleerd als een Gaussische verdeling $N(\hat{\alpha}_t, v^2 V_t^{-1})$. De prior-covariantie wordt ingesteld op de geregulariseerde Laplaciaan $\Lambda$, wat de veronderstelling codeert dat gladde functies (componenten met lage eigenwaarden) waarschijnlijker zijn. Bij elke stap wordt een steekproef $\tilde{\alpha}$ getrokken uit de posterior, en wordt de knoop geselecteerd die $x_v^T \tilde{\alpha}$ maximaliseert.

Belangrijkste Bijdragen en Theoretische Resultaten

• Nieuw Kader: Dit is het eerste werk dat bandit-problemen formaliseert waarbij opbrengsten gladde functies zijn op een graaf, en dat manifold learning/semi-supervised learning overbrugt met online learning.
• Regretgrenzen: Het artikel bewijst dat zowel SpectralUCB als SpectralTS cumulatieve regretgrenzen bereiken die schalen met de effectieve dimensie $d$:
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    Deze grenzen zijn significant omdat $d$ vaak veel kleiner is dan $N$, waardoor de algoritmen goed kunnen presteren zelfs wanneer $T < N$.
• Berekeningsefficiëntie: De auteurs benadrukken een computationeel voordeel voor SpectralTS. Waar SpectralUCB het berekenen van betrouwbaarheidsintervallen voor alle $N$ armen vereist (wat leidt tot een complexiteit van $O(N^3)$ per stap in het slechtste geval waar $D=N$), vereist SpectralTS alleen het trekken van een parameter-vector en het vinden van het maximum, wat efficiënter kan worden gedaan ($O(N^2)$ per stap).

Experimentele Resultaten
De auteurs evalueerden de algoritmen op zowel synthetische als real-world datasets:

• Synthetische Data: Met gebruik van Barabási-Albert-grafen ($N=250$) waarbij de ware beloningsfunctie een lineaire combinatie was van de eerste 3 gladste eigenvectoren. In het regime $T < N$ presteerden zowel SpectralUCB als SpectralTS aanzienlijk beter dan hun lineaire tegenhangers (LinUCB en LinearTS) in termen van cumulatieve regret. SpectralTS toonde ook een snellere rekentijd.
• Real-World Data: Experimenten werden uitgevoerd op de MovieLens-dataset ($N=2019$ films), waarbij gebruikersvoorkeuren werden gemodelleerd als een gladde functie op een similariteitsgraaf die was geconstrueerd uit filmbeoordelingen. De resultaten weerspiegelden de synthetische bevindingen: de spectrale algoritmen bereikten een lagere cumulatieve regret dan lineaire bandit-baselines. Het artikel merkt op dat een goede schatter van gebruikersvoorkeuren voor duizenden items kan worden geleerd vanuit slechts tientallen knoop-evaluaties.

Betekenis en Beweringen
Het artikel beweert dat door het exploiteren van de gladheid van functies op grafen via spectrale decompositie, het mogelijk is om online learning-problemen op te lossen met een groot aantal armen zonder dat de regret slecht schaalt met het aantal knopen. De introductie van de effectieve dimensie $d$ stelt de algoritmen in staat zich aan te passen aan de intrinsieke complexiteit van de graafstructuur. Het werk wordt gemotiveerd door toepassingen in content-gebaseerde aanbeveling en gerichte reclame in sociale netwerken, waarbij gebruikersvoorkeuren of interesses de neiging hebben om soepel te veranderen over verbonden knopen. De auteurs benadrukken dat hun aanpak bijzonder relevant is voor scenario's waarbij het aantal beschikbare interacties ($T$) klein is in vergelijking met het aantal beschikbare items ($N$).