A Contextual-Bandit Approach to Personalized News Article Recommendation 를 참고하자.
LinUCB 의 한계
A.1) 가정 위반
LinUCB 는 ridge regression 을 기반으로 하지만, 이 과정에서 몇 가지 중요한 가정이 지켜지지 않습니다.
A.1.1) 독립성 가정
LinUCB 에서 사용하는 ridge regression 은 다음과 같은 가정을 전제로 합니다:
-
샘플 들이 서로 독립적일 때, ridge regression 을 통해 의 closed-form 추정치를 얻을 수 있습니다:
\hat{\theta}{t}=\left(D{t}^{\top}D_{t}+\lambda\mathrm{I}{d}\right)^{-1}D{t}
그러나 LinUCB 알고리즘은 이전 라운드에서 수집된 샘플들을 사용하여 $\theta^*$를 추정하고, 이를 바탕으로 현재 라운드의 샘플을 선택합니다. 따라서 샘플들이 서로 독립적이지 않다는 문제가 발생합니다. ### 2. 대안적인 접근 Abbasi-Yadkori et al.(2011)에 따르면, martingale 기법을 통해 예측 변수에 대한 집중 결과(concentration results)를 직접적으로 도출할 수 있으며, 이는 독립적인 랜덤 변수들의 선형 결합이라는 가정을 필요로 하지 않습니다. # 핵심 학습 방식 [[ridge regression]]의 해석적 해 (Closed-form Solution) 표준 LinUCB 알고리즘은 사실 **그래디언트를 직접 계산하여 조금씩 이동하는 방식을 사용하지 않습니다.** 대신, 매 시점마다 업데이트된 데이터를 기반으로 **릿지 회귀(Ridge Regression)의 최적 파라미터를 해석적으로(analytically) 계산**합니다. 이 방식이 더 효율적이고 안정적이기 때문입니다. 과정은 다음과 같습니다. 1. **가정**: 각 팔(arm) $a$의 기대 보상 $E[r]$은 컨텍스트 벡터 $x$와 알려지지 않은 계수 벡터 $θ_a$의 선형 결합이라고 가정합니다. $$E[r_t | x_t,a] = x_t,a^T * θ_a$$ 2. **학습 목표**: 관측된 보상과 예측 보상 간의 차이를 최소화하는 $θ_a$를 찾는 것입니다. (L2 정규화 포함) 3. **업데이트 공식**: 새로운 데이터 $(x_t, r_t)$가 들어왔을 때, 선택된 팔 $a$ 에 대해 다음 두 행렬을 업데이트합니다. - $A_a$: $(D_a^T * D_a + I)$에 해당하는 행렬입니다. $D_a$는 지금까지 팔 $a$에 대해 관측된 컨텍스트 벡터들을 쌓은 행렬이고, $I$는 정규화(regularization)를 위한 항등 행렬입니다. - **업데이트**: $A_a ← A_a + x_t * x_t^T$ - $b_a$: $D_a^T * c_a$에 해당하는 벡터입니다. $c_a$ 는 팔 $a$ 에 대해 관측된 보상들을 모은 벡터입니다. - **업데이트**: $b_a ← b_a + r_t * x_t$ 4. **계수 θ_a 계산**: 업데이트된 A_a와 b_a를 사용하여 언제든지 $θ_a$를 다시 계산할 수 있습니다. - $θ_a = {A_a}^{-1} * b_a$ 이 방식은 매번 역행렬(A_a⁻¹)을 계산해야 하지만, 그래디언트 기반 방식처럼 학습률(learning rate)을 튜닝할 필요가 없고, 더 빠르고 안정적으로 최적의 계수를 찾아냅니다. **이것이 LinUCB의 표준 학습 방식입니다.** ## LinUCB의 온라인 업데이트 공식유도 매 시점마다 릿지 회귀의 해석적 해를 계산하기 위한 구성 요소(A_a, b_a)를 점진적(incrementally)이고 효율적으로 만들기 위한 수학적 트릭입니다. ### 1. 기본: 배치(Batch) 릿지 회귀의 해석적 해 먼저, 모든 데이터를 한 번에 사용하여 학습하는 일반적인 릿지 회귀를 보겠습니다. - **데이터**: 특정 팔(arm) a에 대해 지금까지 관측된 모든 컨텍스트 벡터를 쌓은 행렬 $D_a$와, 해당하는 보상들을 모은 벡터 $c_a$가 있다고 가정합니다. - $D_a$: m x d 행렬 (관측 횟수 m, 피처 차원 d) - $c_a$: m x 1 벡터 (관측된 보상 m개) - **목표**: $||D_a * θ_a - c_a||² + λ||θ_a||²$를 최소화하는 계수 벡터 $θ_a$를 찾는 것입니다. - **해석적 해(Analytical Solution)**: 이 목표를 달성하는 $θ_a$는 미분을 통해 유도할 수 있으며, 그 결과는 다음과 같습니다. $$θ_a = (D_a^T D_a + λI)^{-1} D_a^T c_a$$ 여기서, - $D_a$는 행동 a에 대해 관측된 feature 벡터들의 행렬입니다. - $c_a$는 행동 a에 대해 얻은 보상 값들의 벡터입니다. - $λ$는 정규화 파라미터이며, - $I$는 항등 행렬입니다. 이것이 우리가 출발할 표준 공식입니다. (LinUCB 논문에서는 편의상 정규화 계수 $λ$를 1로 가정하므로, $λ*I$는 그냥 $I$가 됩니다) 이제 LinUCB의 업데이트 구성 요소를 위 공식에 대입해 보겠습니다. $A_a$는 $(D_a^T D_a + I)$로 정의됩니다. $b_a$는 $(D_a^T c_a)$로 정의됩니다. 이러한 정의를 표준 릿지 회귀 공식에 그대로 대입하면 다음과 같습니다. $$\theta_a = A_a^{-1} b_a$$ 이는 LinUCB에서 $\theta_a$를 계산하는 공식과 정확히 일치합니다. 즉, **LinUCB는 매 시점마다 관측된 데이터를 바탕으로 릿지 회귀 해를 새롭게 계산하는 것**과 같습니다. ### A.1.3) 핵심: 점진적 업데이트의 마법 (The Magic of Incremental Updates) 왜 매번 $D_a$와 $c_a$를 처음부터 다시 만들어 $A_a$와 $b_a$를 계산하지 않고, 아래와 같이 단순한 덧셈으로만 업데이트할까요?A_a \leftarrow A_a + x_t x_t
b_a \leftarrow b_a + r_t x_t
**여기에 바로 효율성의 비밀이 숨어 있습니다.** 시점 $t-1$까지의 데이터를 사용해 만든 $A_a(t-1)$과 $b_a(t-1)$이 있다고 가정합시다. 이제 시점 $t$에 새로운 데이터 $(x_t, r_t)$가 들어옵니다. #### A.1.3.1) $A_a$의 점진적 업데이트 증명 새로운 데이터 행렬 $D_a(t)$는 이전 행렬 $D_a(t-1)$ 아래에 $x_t^T$ 한 행이 추가된 형태입니다. 정의에 따라, $$A_a(t) = D_a(t)^T D_a(t) + I$$ 입니다. 여기서, $$D_a(t)^T D_a(t) = D_a(t-1)^T D_a(t-1) + x_t x_t^T$$ 가 됩니다. 따라서, $$A_a(t) = [D_a(t-1)^T D_a(t-1) + I] + x_t x_t^T = A_a(t-1) + x_t x_t^T$$ 가 성립합니다. #### A.1.3.2) $b_a$의 점진적 업데이트 증명 * 새로운 보상 벡터 $c_a(t)$는 이전 벡터 $c_a(t-1)$ 아래에 $r_t$가 추가된 구조입니다. 정의에 따라, $$b_a(t) = D_a(t)^T c_a(t)$$ 입니다. 이는 $$b_a(t) = D_a(t-1)^T c_a(t-1) + x_t r_t$$ 로 쓸 수 있습니다. 결국, $$b_a(t) = b_a(t-1) + r_t x_t$$ 가 됩니다. --- ### A.1.4) 결론: 왜 이 방식이 중요한가? 이 점진적(인크리멘털) 업데이트 덕분에 LinUCB는 스트리밍 환경에서 매우 효율적으로 작동할 수 있습니다. 1. **메모리 효율성** 과거의 모든 데이터($D_a$, $c_{a}$)를 메모리에 저장할 필요 없이, 오직 $d \times d$ 크기의 행렬 $A_{a}$와 $d \times 1$ 크기의 벡터 $b_{a}$만 유지하면 됩니다. 여기서 $d$는 피처 차원 수로, 전체 데이터량과 무관하게 일정하게 유지됩니다. 2. **계산 효율성** 새로운 데이터가 들어올 때마다 대형 행렬 곱을 처음부터 다시 계산할 필요 없이, 단순히 벡터 외적($x_{t}x_{t}^{T}$), 벡터 덧셈만으로 빠르게 갱신 가능합니다. 즉, **LinUCB의 업데이트 공식은 릿지 회귀 해석적 해를 스트리밍(온라인/실시간 학습)에 맞게 변형해 낸 결과**라고 할 수 있습니다. 이러한 수학적 유도로 인해 LinUCB는 온라인 환경에서도 빠르고 효율적으로 동작합니다. ## A.2) 대안: 확률적 경사 하강법 (Stochastic Gradient Descent, SGD) 만약 "그래디언트를 계산해서 학습한다"는 관점을 굳이 적용한다면, 이는 확률적 경사 하강법(SGD)으로 LinUCB를 구현하는 방식에 해당합니다. 1. **손실 함수(Loss Function)** 각 데이터 포인트 $(x_t, r_t)$에 대해 손실 함수는 예측 오차의 제곱으로 정의할 수 있습니다.\text{Loss} = (r_t - x_t^\top \theta_a)
2. **그래디언트 계산** 이 손실 함수를 $\theta_a$에 대해 미분하여 그래디언트(기울기)를 계산합니다.\nabla_{\theta_a} \text{Loss} = \frac{\partial,\text{Loss}}{\partial,\theta_a} = -2 (r_t - x_t^\top \theta_a), x_t
3. **파라미터 업데이트** 계산된 그래디언트의 반대 방향으로 $\theta_a$를 아주 조금 업데이트합니다. 여기서 $\eta$는 학습률(learning rate)입니다.\theta_a \leftarrow \theta_a - \eta,\nabla_{\theta_a},\text{Loss}
\theta_a \leftarrow \theta_a + 2,\eta, (r_t - x_t^\top \theta_a), x_t
SGD 방식을 사용하면 구현이 더 직관적일 수 있습니다. 그러나 적절한 학습률 $\eta$를 선택해야 하며, 표준 방식과 비교해 수렴이 불안정할 수 있다는 단점이 있습니다. ### A.2.1) 비교 요약 | | | | | ----------- | ---------------------------------------- | ------------------------------------- | | 항목 | 표준 LinUCB (Ridge Regression) | 대안 (SGD 방식) | | **계산 방식** | 해석적 해 (Closed-form Solution) | 반복적 최적화 (Iterative Optimization) | | **그래디언트** | 직접 계산하지 않음 | 매 스텝마다 **명시적으로 계산** | | **학습률 (η)** | 필요 없음 | **반드시 필요하며 튜닝해야 함** | | **업데이트** | $A_a$, $b_a$ 행렬/벡터를 누적하고, θ_a는 공식을 통해 계산 | θ_a를 그래디언트 방향으로 직접 업데이트 | | **안정성/속도** | 더 안정적이고 빠름 | 학습률에 따라 불안정할 수 있음 | | **일반적인 사용** | **LinUCB 논문과 대부분의 구현체에서 사용** | 개념적으로 가능하며, 특정 라이브러리에서는 구현이 더 쉬울 수 있음 | **결론적으로, LinUCB는 선형 모델을 기반으로 하지만, 학습 시 그래디언트를 반복적으로 계산하는 대신 릿지 회귀의 해석적 해를 온라인으로 업데이트하는 방식을 사용하여 효율성과 안정성을 높인 알고리즘입니다.**