Spectral bandits for smooth graph functions with applications in recommender systems

기술적 요약: 매끄러운 그래프 함수를 위한 스펙트럼 밴딧

문제 공식화
본 논문은 팔들이 알려진 그래프 $G=(V, E)$의 노드에 대응하고, 팔을 당기는 기대 보상이 그래프 위에 정의된 매끄러운 함수에 의해 결정되는 다중 팔 밴딧 문제를 다룹니다. 이 설정에서 보상 함수 $f$는 그래프 라플라시안 $L$의 고유벡터들의 선형 결합으로 가정됩니다. 구체적으로, $Q$가 $L$의 고유벡터들을 열로 포함한다면, 노드 $v$에 대한 보상은 $f_\alpha(v) = \langle x_v, \alpha^* \rangle$이며, 여기서 $x_v$는 $Q$의 $v$번째 행이고 $\alpha^*$는 알려지지 않은 가중치 벡터입니다.

핵심적인 도전 과제는 노드의 수 $N$(따라서 특징 공간의 차원 $D=N$) 이 매우 커서 학습 과정의 시간 범위 $T$를 초과할 수 있는 ($T < N$) 상황에서 발생합니다. 일반적으로 후회 (regret) 를 주변 차원 $D$나 팔의 수 $K$에 비례하여 확장하는 표준 선형 밴딧 알고리즘은 이러한 영역에서 성능이 저하됩니다. 논문은 실제 함수가 "매끄럽다"고 가정하는데, 이는 큰 고유값에 대응하는 고유벡터와 관련된 계수 $\alpha^*$는 작고, 작은 고유값에 관련된 계수는 더 크다는 것을 의미합니다.

방법론
저자들은 그래프의 스펙트럼 특성을 활용하여 전체 차원 $N$ 대신 "유효 차원" $d$에 비례하는 후회 상한을 달성하는 두 가지 알고리즘을 제안합니다.

1. 유효 차원 ($d$): 논문은 정규화된 라플라시안 $\Lambda = \Lambda_L + \lambda I$의 고유값 성장에 기반한 유효 차원 $d$의 공식적 정의를 도입합니다. $d$는 $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$를 만족하는 가장 큰 정수로 정의됩니다. 이 지표는 문제의 "관련" 차원의 수를 포착하며, 실제 세계의 그래프에서는 일반적으로 $N$보다 훨씬 작습니다.

2. SpectralUCB: 이 알고리즘은 LinUCB 알고리즘의 변형입니다. 스펙트럼 기저를 사용하여 $\alpha^*$에 대한 정규화된 최소제곱 추정기를 사용합니다. 핵심적으로, 이 알고리즘은 주변 차원 $D$ 대신 유효 차원 $d$를 사용하여 예측 보상에 대한 신뢰 구간을 구성합니다. 알고리즘은 상한 신뢰 구간을 최대화하는 노드를 선택합니다: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$. 여기서 $c_t$는 $d$에 의존합니다.

3. Spectral Thompson Sampling (SpectralTS): 이 알고리즘은 베이지안 접근법을 활용합니다. $\alpha^*$에 대한 사후 분포를 가우시안 $N(\hat{\alpha}_t, v^2 V_t^{-1})$으로 모델링하여 유지합니다. 사전 공분산은 정규화된 라플라시안 $\Lambda$로 설정되어, 매끄러운 함수 (낮은 고유값 성분) 가 더 가능성이 높다는 가정을 인코딩합니다. 각 단계에서 사후 분포에서 $\tilde{\alpha}$를 샘플링하고, $x_v^T \tilde{\alpha}$를 최대화하는 노드를 선택합니다.

주요 기여 및 이론적 결과

• 새로운 프레임워크: 이는 보상이 그래프 위의 매끄러운 함수인 밴딧 문제를 공식화하여 매니폴드 학습/반지도 학습과 온라인 학습을 연결하는 첫 번째 작업입니다.
• 후회 상한: 논문은 SpectralUCB 와 SpectralTS 모두 유효 차원 $d$에 비례하는 누적 후회 상한을 달성함을 증명합니다.
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    이러한 상한은 $d$가 종종 $N$보다 훨씬 작기 때문에 중요하며, 알고리즘이 $T < N$일 때에도 잘 수행되도록 합니다.
• 계산 효율성: 저자들은 SpectralTS 에 대한 계산적 이점을 강조합니다. SpectralUCB 는 모든 $N$개의 팔에 대한 신뢰 구간을 계산해야 하여 (최악의 경우 $D=N$인 경우 단계당 $O(N^3)$의 복잡도) 반면, SpectralTS 는 매개변수 벡터를 샘플링하고 최댓값을 찾는 것만 필요하므로 더 효율적으로 수행할 수 있습니다 (단계당 $O(N^2)$).

실험 결과
저자들은 합성 및 실제 세계 데이터셋 모두에서 알고리즘을 평가했습니다.

• 합성 데이터: 첫 번째 3 개의 가장 매끄러운 고유벡터의 선형 결합인 실제 보상 함수를 가진 Barabási-Albert 그래프 ($N=250$) 를 사용했습니다. $T < N$ 영역에서 SpectralUCB 와 SpectralTS 모두 누적 후회 측면에서 선형 대응물 (LinUCB 및 LinearTS) 보다 훨씬 우수한 성능을 보였습니다. SpectralTS 는 또한 더 빠른 계산 시간을 보여주었습니다.
• 실제 세계 데이터: 영화 평점으로부터 구축된 유사성 그래프 위의 매끄러운 함수로 사용자 선호도를 모델링한 MovieLens 데이터셋 ($N=2019$개 영화) 에서 실험을 수행했습니다. 결과는 합성 데이터의 발견을 반영했습니다: 스펙트럼 알고리즘은 선형 밴딧 기준선보다 더 낮은 누적 후회를 달성했습니다. 논문은 수천 개의 항목에 대한 사용자 선호도의 좋은 추정기가 단几十 개의 노드 평가로부터 학습될 수 있음을 지적합니다.

의의 및 주장
본 논문은 스펙트럼 분해를 통해 그래프 위의 함수의 매끄러움을 활용함으로써, 노드의 수에 따라 후회가 나쁘게 확장되지 않고 많은 수의 팔을 가진 온라인 학습 문제를 해결할 수 있다고 주장합니다. 유효 차원 $d$의 도입은 알고리즘이 그래프 구조의 내재적 복잡성에 적응할 수 있게 합니다. 이 작업은 사용자 선호도나 관심이 연결된 노드 간에 매끄럽게 변화하는 소셜 네트워크의 콘텐츠 기반 추천 및 타겟 광고 응용 분야에서 동기부여를 받았습니다. 저자들은 그들의 접근 방식이 사용 가능한 상호작용 수 ($T$) 가 사용 가능한 항목 수 ($N$) 에 비해 작은 시나리오에서 특히 관련이 있음을 강조합니다.