Lihong Li, Wei Chu, John Langford, Robert E. Schapire의 A Contextual-Bandit Approach to Personalized News Article Recommendation을 번역했습니다.


초록

개인화 웹 서비스는 컨텐츠 및 사용자 정보를 이용해서 개별 사용자마다 (광고, 뉴스 기사 등의) 맞춤 서비스를 제공하기 위해 노력한다. 최신 기술의 발전에도 불구하고 적어도 두 가지 이유로 난항을 여전히 겪고 있다. 먼저, 웹 서비스의 경우 기존 협업 필터링 방법을 적용하기 어려울만큼 동적으로 변하는 컨텐츠 풀을 특징으로 한다. 둘째, 실용적으로 자주 쓰이는 웹 서비스의 규모는 학습과 계산 모든 면에서 고속인 해법을 필요로 한다.

본 논문은 뉴스 기사 개인화 추천을 어떤 원리적 접근법, 컨텍스츄얼 밴딧 문제로 모형화한다. 컨텍스츄얼 밴딧은 사용자 클릭 수 총합을 최대로 만들기 위해 사용자 클릭 피드백을 바탕으로 기사 선택 전략을 점차 수정해 나가는 동시에 사용자와 기사에 관한 맥락 상 정보를 기반으로 사용자에게 제공할 기사를 순차적으로 선택하는 학습 알고리즘이다.

이 논문이 공헌하는 바는 세 가지이다. 첫째, 계산이 효율적이며 학습 이론에서 동기를 얻은, 새롭고 일반화 가능한 컨텍스츄얼 밴딧 알고리즘을 제안한다. 둘째, 이전에 기록된 무작위 트래픽을 이용하여 모든 밴딧 알고리즘을 오프라인에서 안정적으로 평가할 수 있는 방법을 이야기한다. 마지막으로 해당 오프라인 평가 방법을 통해 3,300만 건이 넘는 이벤트가 포함된 Yahoo! Front Page Today 데이터셋에 새 알고리즘을 성공적으로 적용했다. 결과에 따르면 기존의 맥락 무관한 밴딧 알고리즘과 비교했을 때 클릭 수준을 12.5 % 넘게 끌어올렸고 이러한 이점은 데이터가 부족할수록 더욱 커진다.

1. 서론

본 논문은 각 사용자 별로 가장 적절한 웹 기반 컨텐츠를 가장 적절한 시기에 선별해내는 문제를 해결한다. 대부분의 서비스 공급 업체는 예를 들어 뉴스 기사를 필터링하거나 광고를 띄우기 위해 저장소에 다량의 컨텐츠를 확보하고 유지 관리한다. 또한 그러한 웹 서비스 저장소의 컨텐츠는 빈번한 추가 및 삭제를 거치면서 동적으로 변한다. 이러한 환경에서 사용자가 흥미를 가질 컨텐츠를 신속히 선정해내는게 중요하다. 예를 들자면 뉴스 필터는 인기있는 속보를 즉시 판별해내는 동시에 시간이 흐른, 기존 뉴스 기사의 가치는 감가시켜야한다.

컨텐츠 정보 만으로 인기와 시간에 따른 변화를 모형화하는건 일반적으로 어렵다. 보통 실무에서는 신규 컨텐츠의 인기를 평가하기 위해 소비자 피드백을 실시간으로 수집해 미지의 것을 탐색해봄과 함께 기존 가치의 변화를 추적, 관찰해나간다. 예를 들어 트래픽 일부를 그러한 탐색을 위해 배정할 수 있다. 무작위로 고른 컨텐츠에 대한 트래픽 일부의 사용자 응답(예: 클릭)을 기반으로 가장 애용되는 컨텐츠를 판별해서 이를 나머지 트래픽에 활용해볼 수 있다. 트래픽 중 \(\epsilon\)만큼의 부분은 무작위로 탐색하고 나머지에 대해 탐욕적 활용을 수행하는 해당 전략을 \(\epsilon\)-탐욕이라고 부른다. EXP3이나 UCB1과 같이 진보한 탐색 접근법도 사용해볼 수 있다. 직관적으로 신규 컨텐츠의 경우 더 많은 트래픽을 배정해서 가치를 빨리 학습해야하고 기존 컨텐츠의 경우 추이를 파악하기 위한 사용자 수는 점차 줄여 나가야한다.

최근 개인화 추천은 웹 사이트가 개별 사용자 요구에 맞게 컨텐츠 표현을 조정하여 사용자 만족도를 향상시키는 용도로써 훌륭히 잘 쓰이고 있다. 개인화는 사용자 속성을 수집, 저장하고 컨텐츠 자산을 관리하며 현재와 과거 사용자 행동을 분석하여 가장 적합한 컨텐츠를 현 사용자에게 개별적으로 제공하는 절차를 포함한다.

사용자와 컨텐츠는 흔히 변수의 집합으로 표현된다. 사용자 변수에는 기입된 인구 통계 정보뿐만 아니라 활동 기록을 집계한 걸 포함시킬 수 있다. 컨텐츠 변수에는 설명 정보와 범주를 포함시킬 수 있다. 지금 다루는 시나리오의 경우 똑같은 컨텐츠에 대해 사용자마다 관점이 상당히 다를 수 있기 때문에 탐색과 활용이 개별적으로 수행되어야한다. 매우 많은 숫자의 선택지 또는 동작이 존재할 수 있으므로 컨텐츠 품목 간의 공통점을 인지하여 컨텐츠 풀로 해당 지식을 전달할 수 있는지도 중요하다.

협업 필터링, 컨텐츠 기반 필터링 또는 혼합 접근법을 포함하여 기존 추천 시스템은 과거 활동을 통해 판별한 사용자 관심사를 이용하여 개인 수준에서 의미있는 추천을 제공한다. 사용자 간 소비 이력이 상당히 겹치고 컨텐츠 전체 목록이 잘 변하지 않는 시나리오라면 협업 필터링이 사용자 소비 이력을 기반으로 유사도를 계산하여 좋은 추천안을 제공할 수 있다. 컨텐츠 기반 필터링의 경우 기존 사용자의 소비 프로필과 잘 부합하는 신규 품목을 식별하는데 용이하지만 추천한 품목이 사용자가 이전에 취해온 품목들과 굉장히 유사할 수 밖에 없다. 혼합 접근법은 추천 기법을 두 가지 이상 결합하여 개발한다. 예를 들어 협업 필터링은 신규 품목을 추천할 수 없는데 보통 컨텐츠 기반 필터링과 결합하여 이 약점을 보완한다.

그러나 위에서 언급했듯이 대부분의 웹 기반 시나리오에서 컨텐츠 전체 목록은 자주 변경되며 시간이 경과함에 따라 컨텐츠의 인기는 변한다. 또한 방문자의 상당수는 과거 소비 기록이 전혀 없는 신규 사용자들인데 이는 보통 콜드 스타트 상황으로 불리운다. 앞서 언급한 문제들은 과거 사례 연구에서 볼 수 있듯이 추천 시스템의 전통적인 접근법을 적용하기 어렵게 만든다. 따라서 사용자와 컨텐츠 중 한쪽 또는 양쪽 모두 새로 등장한 것이라면 서로 잘 부합하는 지 학습하는 과정이 필수이다. 그러나 해당 정보를 수집하는 건 비용이 많이 들고 사용자 만족도를 단기적으로 저하시킬 수 있다. 그러므로 장기적인 사용자 만족도를 최대화하고 사용자의 관심사와 컨텐츠가 잘 부합하는지 정보를 수집하는, 상충하는 두 가지 목표 간에 최적 균형점을 찾는 문제로 이어진다.

윗 문제는 사실 변수 기반의 탐색 / 활용 문제로 알려져있다. 본 논문은 이를 어떤 원리적 접근법, 컨텍스츄얼 밴딧 문제로 수식화한다. 컨텍스츄얼 밴딧은 사용자 클릭 수 총합을 장기적으로 최대로 만들기 위해 사용자 클릭 피드백을 바탕으로 기사 선택 전략을 점차 수정해 나가는 동시에 사용자와 기사에 관한 맥락 상 정보를 기반으로 사용자에게 제공할 기사를 순차적으로 선택하는 학습 알고리즘이다. 2장에서는 다중 슬롯머신 실험 문제를 정의하고 기존의 접근법을 검토한다. 그리고 3장에서 새로운 알고리즘 LinUCB를 제안한다. 해당 알고리즘의 경우 적은 계산량으로 최적 선형 예측기에 견주기 위해 가장 잘 알려진 알고리즘 기준으로 유사 리그릿 분석을 수행한다. 또 4장은 오프라인 평가 방법론을 다루면서 각 상호 작용이 독립이고 분포가 동일하다면(i.i.d.) 모든 탐색 / 활용 전략에 해당 전략을 적용할 수 있음을 증명한다. 서로 다른 사용자를 고려할 때 이는 합리적인 가정일 수 있다. 마지막으로 5장은 해당 오프라인 평가 전략을 사용하여 새 알고리즘과 기존 알고리즘을 실험한다.

2. 수식화와 연관 작업

이 장은 \(K\)개의 슬롯 손잡이를 갖는 컨텍스츄얼 밴딧 문제를 수식으로 정의하고 이것을 뉴스 기사 개인화 추천 문제에 어떻게 적용할 수 있는지 보인다. 그런 다음 기존 방법과 그 한계점을 논한다.

2.1 다중 슬롯머신 실험 문제 수식화

뉴스 기사 개인화 추천 문제는 자연스럽게 맥락 상의 정보가 있는 다중 슬롯머신 문제로 모형화할 수 있다. 이전 연구에 따라 이를 컨텍스츄얼 밴딧1이라고 부를 것이다. 수식화해보자면 컨텍스츄얼 밴딧 알고리즘 \(\mathsf{A}\)는 개별 시도 \(t = 1, 2, 3, \ldots \)에 따라 수행된다. \(t\)번째 시도에 대하여,

1.알고리즘은 현재 사용자 \(u_t\)와 슬롯 손잡이 또는 행동의 집합 \(\mathcal{A}_t\)와 함께 \(a_t \in \mathcal{A}\)일 때의 변수 벡터 \(\mathbf{x}_{t, a}\)를 관측한다. 벡터 \(\mathbf{x}_{t, a}\)는 사용자 \(u_t\)와 슬롯 손잡이 \(a\)의 정보를 모두 축약하며 이를 맥락이라고 지칭한다.
2.이전 시도들에서 관측한 손익에 기초하여 \(\mathsf{A}\)는 슬롯 손잡이 \(a_t \in \mathcal{A}\)를 선택하고 손익 \(r_{t, a_t}\)를 받는다. 해당 손익의 기대값은 사용자 \(u_t\)와 슬롯 손잡이 \(a_t\) 양쪽에 의존한다.
3.알고리즘은 새로운 관측치 \((\mathbf{x}_{t, a}, a_t, r_{t, a_t})\)를 이용하여 슬롯 손잡이 선택 전략을 개선한다. 여기에서 중요한 것은 선택하지 않은 슬롯 손잡이 \(a \ne a_t\)에 대해서 관측되는 피드백(즉, 손익 \(r_{t, a}\)) 또한 없다는 점이다. 이 사실로부터 이어지는 결론은 다음 절에서 좀 더 자세히 논의할 것이다.

상술한 과정에서 \(\mathsf{A}\)의 총 \(T\)번의 시도에 따른 손익을 \(\sum_{t = 1}^T r_{t, a}\)로 정의한다. 이와 비슷하게 총 \(T\)번의 시도에 따른 최적 손익의 기대값을 \(\mathbf{E}[\sum_{t = 1}^T r_{t, a_t^*}]\)으로 정의한다. 여기서 \(a_t^*\)는 \(t\)번째 시도에서 손익의 기대값이 최대인 슬롯 손잡이이다. 목표는 \(\mathsf{A}\)를 잘 설계하여 위의 총 손익 기대값을 최대로 만드는 것이다. 이와 동치로써, 최적의 슬롯 손잡이 선택 전략 대비 리그릿을 최소로 만드는 알고리즘을 찾는 것이다. 여기서 알고리즘 \(\mathsf{A}\)의 총 \(T\)번 시도에 따른 리그릿 \(R_{\mathsf{A}}(T)\)는 다음과 같은 수식으로 정의된다.

일반적인 컨텍스츄얼 밴딧 문제에서 특별히 중요한 경우는 (ⅰ) 슬롯 손잡이 집합 \(\mathcal{A}_t\)가 변하지 않으며 모든 \(t\)마다 슬롯 손잡이가 \(K\)개인 (ⅱ) 사용자 \(u_t\)(또는 이와 동치로 맥락 \((\mathbf{x}_{t, 1}, \cdots ,\mathbf{x}_{t, K})\))가 모든 \(t\)마다 동일한 문제이다. 즉, 잘 알려진 \(K\)개의 슬롯 손잡이를 갖는 다중 슬롯머신 실험이다. 슬롯 손잡이 집합과 맥락이 모든 시도마다 동일하므로 다중 슬롯머신 실험 알고리즘과 아무런 차이가 없으며 해당 유형을 맥락 무관한 다중 슬롯머신 실험이라고 부른다.

기사 추천의 관점에서 컨텐츠 풀에 속하는 기사를 하나의 슬롯 손잡이로 볼 수 있다. 제공한 기사를 클릭하면 손익은 1이고 그렇지 않으면 0이라고 하자. 이 손익 정의에 따라 어떤 기사의 손익 기대값은 정확히 클릭률(CTR)이며 CTR이 최대인 기사를 선택하는 것과 사용자의 클릭 수 기대값을 최대로 만드는 건 동일한 얘기다. 또한 다중 슬롯머신 실험 수식에서 손익의 기대값을 최대로 만드는 것과 같다.

또한 웹 서비스는 사용자 관심사를 유추하고 가장 관심을 보일 만한 뉴스 기사를 선택하는데 이용 가능한 사용자 정보를 보통 갖고 있다. 예를 들자면 10대 남성은 은퇴 계획보다는 iPod 제품 기사에 관심을 가질 가능성이 훨씬 크다. 따라서 사용자와 기사의 경우 그것을 간략히 표현해내는 유용한 정보의 변수 집합으로 “축약”할 수 있다. 이렇게하면 다중 슬롯머신 실험 알고리즘은 특정 기사 / 사용자의 CTR 정보를 일반화할 수 있고 특히 신규 사용자와 기사에 대해 적합한 기사를 더 빨리 선택할 수 있다.

2.2 기존의 다중 슬롯머신 실험 알고리즘

다중 슬롯머신 실험의 경우 핵심 과제는 탐색과 활용 간의 균형점을 찾는 일이다. 수식 (1)의 리그릿을 최소로 만들고자 알고리즘 \(\mathsf{A}\)는 최적으로 보이는 슬롯 손잡이 선택에 과거의 경험을 활용한다. 허나 \(\mathsf{A}\)가 갖고 있는 지식이 부정확해서 최적으로 보이는 슬롯 손잡이가 실은 최선책이 아닐 수 있다. 이 원치않는 상황을 피하고자 \(\mathsf{A}\)는 차선으로 보이는 슬롯 손잡이들을 실제로 선택해가며 정보를 더 많이 수집하는 식으로 탐색을 한다(예를 들자면 이전 절에서 정의한 다중 슬롯머신 실험 3 단계). 최적이 아닌 슬롯 손잡이가 선택될 수 있기에 탐색은 단기 리그릿을 증가시킨다. 그러나 슬롯 손잡이의 평균 손익에 관한 정보를 얻어서(즉, 탐색으로) 슬롯 손잡이들에 대한 \(\mathsf{A}\)의 추정치를 갱신해 나갈 수 있으므로 장기 리그릿을 결과적으로 감소시킨다. 온전히 탐색만 하거나 활용만 하는 알고리즘은 일반적으로 잘 작동하지 않으며 적당한 절충안이 필요하다.

맥락 무관한, \(K\)개의 슬롯 손잡이를 갖는 다중 슬롯머신 실험 문제는 통계학자들이 오랫동안 연구해왔다. 가장 단순하고 직관적인 알고리즘 중의 하나는 \(\epsilon\)-탐욕이다. 먼저 각 시도 \(t\)마다 해당 알고리즘은 모든 슬롯 손잡이 \(a\)의 평균 손익 \(\hat{\mu_{t, a}}\)를 추정해 나간다. 그런 다음 \(1 - \epsilon\)의 확률로 탐욕적 슬롯 손잡이(즉, 가장 높은 손익 추정치를 갖는 슬롯 손잡이)을 선택하며 \(\epsilon\) 확률로 슬롯 손잡이를 무작위 선택한다. 극한을 취한다면 모든 슬롯 손잡이를 무한히 자주 시도할 것이다. 그래서 손익 추정치 \(\hat{\mu_{t, a}}\)는 1의 확률로 참값 \(\mu_a\)에 수렴한다. 더욱이 탐색 확률을 적절히 감소시키면 매 단계 당 리그릿, 즉 \(R_{\mathsf{A}}(T) / T\)는 1의 확률로 0에 수렴한다.

\(\epsilon\)-탐욕이 사용하는, 유도하지 않는 성향의 탐색 전략과 다르게 보통 신뢰 상한 알고리즘이라고 불리우는 또 다른 범주의 알고리즘은 탐색과 활용 간 균형점을 찾기위해 더 영리한 방법을 사용한다. 구체적으로 이 알고리즘은 각 슬롯 손잡이 \(a\)의 평균 손익 \(\hat{\mu_{t, a}}\)에 상응하는 신뢰 구간 \(c_{t, a}\)를 \(|\hat{\mu_{t, a}} - \mu_a | < c_{t, a}\) 식이 높은 확률을 갖는 조건 하에 추정해낸다. 그런 다음 가장 높은 신뢰 상한(줄여서 UCB)을 갖는 슬롯 손잡이를 선택한다. 즉, \(a_t = argmax_a (\hat{\mu_{t, a}} + c_{t, a})\)이다. 적절히 정의한 신뢰 구간을 사용하면 해당 알고리즘은 총 시도 횟수 \(T\)에 대해 단지 로그 수준으로 증가한다. 이는 최적으로 증명된 수준으로써 총 \(T\)번 시도에 대해 매우 작은 리그릿을 갖는다.

맥락 무관한, \(K\)개의 슬롯 손잡이를 갖는 다중 슬롯머신 실험의 경우 광범위하게 연구되면서 이해가 깊어졌지만 보다 일반적인 컨텍스츄얼 밴딧 문제는 여전히 난제이다. EXP4 알고리즘은 \(\tilde{O}(\sqrt{T})\)의 리그릿2을 달성하기 위해 지수 가중 기법을 이용하지만 변수 개수가 늘어남에 따라 계산 복잡도가 지수적으로 증가한다. 일반적인 컨텍스츄얼 밴딧 알고리즘 중 하나는 \(\epsilon\)을 축소시켜 나가는 \(\epsilon\)-탐욕과 유사한 유형인 에폭 탐욕 알고리즘이다. 해당 알고리즘은 신탁적 옵티마이저가 주어진다는 가정 하에 계산량이 효율적이지만 보장하는 리그릿은 \(\tilde{O}(T^{2 \over 3})\) 수준으로 약한 편이다.

다중 슬롯머신 실험에 대한 다양한 모형화 가정 아래 리그릿을 좀 더 강력히 보장하는 알고리즘을 설계할 수 있다. Auer는 슬롯 손잡이의 손익 기대값이 변수에 선형적이라고 가정하고 본질적으로 UCB 유형의 접근법인 LinRel 알고리즘을 소개한다. 그 변형 중 하나는 이전 알고리즘을 상당히 개선하여 \(\tilde{O}(\sqrt{T})\)의 리그릿을 갖는다.

마지막으로 기틴스 지수 방법처럼 베이즈 법칙에 기반한, 또 다른 종류의 다중 슬롯머신 알고리즘이 존재한다. 베이즈 접근법은 정의한 사전 분포이 적절한 경우 좋은 성능을 발휘한다. 이 방법은 적합한 사전 모형을 얻기 위해 오프라인 엔지니어링이 광범위하게 필요하며 근사 기법을 결합시키지 않으면 계산이 불가능하다.

3. 알고리즘

맥락 무관한 다중 슬롯머신 알고리즘에 대한 UCB 방법의 점근적 최적성, 그리고 강력한 리그릿 수준을 감안할 때 컨텍스츄얼 밴딧 문제에 대해서도 유사한 알고리즘을 고려해볼 만하다. 손익 함수가 모수적 형태로 주어진다면 슬롯 손잡이 추정 손익의 UCB 계산을 위해 모수 신뢰 구간을 데이터로부터 추정해내는 수많은 방법이 존재한다. 그러나 이러한 접근법은 보통 계산 비용이 매우 높다.

본 연구는 손익 모형이 선형일 때 신뢰 구간을 닫힌 해를 통해 효율적으로 계산해낼 수 있음을 보인다. 그리고 해당 알고리즘을 LinUCB라고 부를 것이다. 편의를 위해 배타 선형 모형이라는 단순 형태를 먼저 설명하고 3.2절에서 혼합 모형이라는 더 일반적인 형태를 고려한다. LinUCB는 뉴스 기사 개인화 추천 이외의 응용 프로그램에 적용 가능한, 일반적인 컨텍스츄얼 밴딧 알고리즘이다.

3.1 배타 선형 모형을 이용한 LinUCB

2.1절의 표기법을 그대로 사용하겠다. 모든 \(t\)에 대하여 슬롯 손잡이 \(a\)의 손익 기대값은 \(d\)-차원 변수 \(\mathbf{x}_t\)에 선형이며 미지의 계수 벡터 \(\boldsymbol{\theta}^*_a\)를 갖는다고 가정한다.

파라미터를 다른 슬롯 손잡이와 공유하지 않기 때문에 본 모형은 배타적이다. \(\mathbf{D}_a\)를 \(t\)번째 시도에서의 \(m \times d\) 차원인 설계 행렬이라고 정의하자. 행은 \(m\) 개의 훈련 입력값(예: 기사 \(a\)에 대해 이전 관찰한 맥락 정보)에 해당하며 \(\mathbf{c}_a \in \mathbb{R}^m\)를 그에 상응하는 응답 벡터(예: 상응하는 \(m\) 개의 클릭 여부 사용자 피드백)라고 하자. 훈련 데이터 \((\mathbf{D}_a, \mathbf{c}_a)\)에 릿지 회귀 분석을 적용하면 계수 추정값을 얻을 수 있다.

여기서 \(\mathbf{I}_d\)는 \(d \times d\) 차원인 항등 행렬이다. \(\mathbf{c}_a\)의 성분들이 \(\mathbf{D}_a\)의 상응하는 행에 대해 조건부 독립일 때, 임의의 \(\delta > 0\)와 \(\mathbf{x}_{t, a} \in \mathbb{R}^d\)에 대해 적어도 \(1 - \delta\)의 확률로

이다. 여기서 \(\alpha = 1 + \sqrt{\ln{(2/\delta)}/2}\)은 상수이다. 다시 말해서 위 부등식은 슬롯 손잡이 \(a\)의 손익 기대값에 대해 엄격한 UCB를 합리적으로 제공하며 이로부터 UCB 유형의 슬롯 손잡이 선택 전략이 파생될 수 있다. 각 \(t\)번째 시도에서

을 고른다. 식 (4)에서의 신뢰구간은 다른 원리를 적용해 계산해낼 수 있다. 예를 들자면 릿지 회귀는 베이즈 식의 점 추정으로 해석할 수 있는데 여기서 계수 벡터의 사후 분포 즉, \(p(\boldsymbol{\theta}_a)\)는 평균 \(\hat{\boldsymbol{\theta}}_a\)와 공분산 \(\mathbf{A}^{-1}_a\)를 갖는 정규분포이다. 모형이 주어졌을때 손익 기대값 \(\mathbf{x}^{\mathsf{T}}_{t, a}\boldsymbol{\theta}^*_a\)의 예측 분산은 \(\mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{x}_{t, a}\)으로, 표준편차는 \(\sqrt{\mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{x}_{t, a}}\)로 계산된다. 또한 정보 이론에서 \(p(\boldsymbol{\theta}_a)\)의 미분 엔트로피는 \(-{1 \over 2} \ln((2\pi)^d\det \mathbf{A}_a)\)로 정의된다. 점 \(\mathbf{x}_{t, a}\)이 새로 포함되어 갱신이 발생할 경우 \(p(\boldsymbol{\theta}_a)\)의 엔트로피는 \(-{1 \over 2} \ln((2\pi)^d\det (\mathbf{A}_a + \mathbf{x}_{t, a}\mathbf{x}^{\mathsf{T}}_{t, a}))\)가 된다. 사후분포 모형의 엔트로피 감소분은 \(-{1 \over 2}\ln(1 + \mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{x}_{t, a})\)이다. \(\mathbf{x}_{t, a}\)이 모형을 개선하는데 기여한 정도를 계산할 때 이 양을 종종 사용한다. 따라서 식 (5)에서 슬롯 손잡이 선택 기준은 손익 추정과 모형 분산 감소 사이의 추가분에 관한 트레이드 오프로 생각할 수있다.

알고리즘 1은 입력 파라미터가 오직 \(\alpha\)인 LinUCB 알고리즘 전반에 대하여 자세하게 설명한다. 식 (4)에 표시된 \(\alpha\)를 보라. 일부 응용 프로그램에서 보수적으로 큰 값을 취할 수 있으므로 해당 파라미터를 최적화하면 전체 손익을 높일 수 있다. 모든 UCB 방법과 마찬가지로 LinUCB는 UCB가 가장 높은 슬롯 손잡이를 항상 선택한다(식 (5)와 같다).

이 알고리즘은 몇 가지 좋은 성질이 있다. 첫째, 계산 복잡도가 슬롯 손잡이 개수에 선형이며 변수 개수에 최대 세제곱이다. 계산량을 더 줄이기 위해 모든 단계(\(O(d^2)\) 시간이 걸리는)에서 \(\mathbf{A}_{a_t}\)를 실시간으로 업데이트하는 대신 주기적으로 \(\mathbf{Q}_a \overset{\underset{\mathrm{def}}{}}{=} \mathbf{A}^{-1}_{a_t}\) (모든 \(a\)에 대하여)를 계산하고 캐시할 수 있다. 둘째, 알고리즘은 동적인 슬롯 손잡이 집합에 대해 잘 작동하며 \(\mathcal{A}_t\)의 크기가 너무 크지 않은 한 효율적이다. 이는 많은 응용 프로그램에 해당하는 경우이다. 예를 들어 뉴스 기사 추천의 경우 편집자가 기사를 풀에 추가 / 제거하기 때문에 본질적으로 풀의 크기는 일정하다. 셋째, 본 논문의 초점은 아니지만 해당 논문3의 분석 결과를 다음과 같이 적용해볼 수 있다. 집합 \(\mathcal{A}_t\)가 고정되어 있고 슬롯 손잡이가 \(K\)개일 경우 데이터가 증가하면 신뢰 구간(즉, 식 (4)의 우항)이 충분히 빠르게 감소하며 강력한 리그릿 상한 \(\tilde{O}(\sqrt{KdT})\)을 갖는다. 이는 앞서 언급한 최신 논문 중 식 (2), 다중 슬롯머신 실험 결과에 부합한다. 본 이론적 결과는 알고리즘이 기본적으로 건전하며 효율적임을 나타낸다.


알고리즘 1 배타 선형 모형을 이용한 LinUCB


0: 입력: \(\alpha \in \Bbb{R}_+\)
1: for \(t = 1, 2, 3, \ldots , T\) do
2: \(\qquad\) 모든 슬롯 손잡이 \(a \in \mathcal{A}_t\)의 변수 \(\mathbf{x}_{t, a} \in \Bbb{R}_d\)를 관측함
3: \(\qquad\) for all \(a \in \mathcal{A}_t\) do
4: \(\qquad \qquad\) if \(a\)가 신규라면 then
5: \(\qquad \qquad \qquad \mathbf{A}_a \leftarrow \mathbf{I}_d\) (\(d\) 차원의 항등 행렬)
6: \( \qquad \qquad \qquad \mathbf{b}_a \leftarrow \mathbf{0}_{d \times 1}\) (\(d\) 차원의 영 벡터)
7: \(\qquad \qquad \) end if
8: \(\qquad \qquad \hat{\boldsymbol{\theta}}_a \leftarrow \mathbf{A}^{-1}_a\mathbf{b}_a \)
9: \(\qquad \qquad p_{t, a} \leftarrow \hat{\boldsymbol{\theta}}^{\mathsf{T}}_a\mathbf{x}_{t, a} + \alpha\sqrt{\mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{x}_{t, a}}\)
10: \(\qquad\) end for
11: \(\qquad\) 슬롯 손잡이 \(a_t = \arg\max_{a \in \mathcal{A}_t} p_{t, a}\)를 선택하되 동점인 경우 무작위로 정하고 실수값 손익 \(r_t\)를 관측함
12: \(\qquad \mathbf{A}_{a_t} \leftarrow \mathbf{A}_{a_t} + \mathbf{x}_{t, a_t}\mathbf{x}^{\mathsf{T}}_{t, a_t}\)
13: \(\qquad \mathbf{b}_{a_t} \leftarrow \mathbf{b}_{a_t} + r_t\mathbf{x}_{t, a_t}\)
14: end for

마지막으로 입력 변수 \(\mathbf{x}_{t, a}\)를 정규분포에서 i.i.d.로 추출한다는 가정 하에서(식 (2)의 모형화 가정에 덧붙여) Palidis 등은 UCB를 계산하기 위해 릿지 회귀의 해(식 (3)의 \(\hat{\boldsymbol{\theta}}_a\)) 대신 최소 자승 해 \(\tilde{\boldsymbol{\theta}}_a\)를 이용한 유사 알고리즘을 제안했다. 그러나 본 접근법(그리고 이론적 분석)이 보다 일반적이며 입력 변수가 정상(stationary) 상태가 아닐 경우에도 유효하다. 보다 중요하게 기본 알고리즘 1을 Pavlidis 등이 다루지 않은, 훨씬 더 흥미로운 경우로 확장하는 방식에 관해 다음 절에서 논할 것이다.

3.2 혼합 선형 모형을 이용한 LinUCB

알고리즘 1(또는 해당 논문3과 유사한 알고리즘)은 행렬 \(\mathbf{D}^{\mathsf{T}}_a\mathbf{D}_a + \mathbf{I}_d\)(또는 \(\mathbf{D}^{\mathsf{T}}_a\mathbf{D}_a\))의 역행렬을 계산한다. 여기서 \(\mathbf{D}_a\)는 학습 데이터 변수에 해당하는 행을 갖는 설계 행렬이다. 슬롯 손잡이의 모든 행렬은 고정된 차원 \(d \times d\)를 가지며 업데이트를 점진적, 효율적으로 수행할 수 있다. 또한 알고리즘 1의 파라미터는 상호 배타적이기 때문에 역행렬을 쉽게 계산할 수 있다. 식 (3) 중 \(\hat{\boldsymbol{\theta}}_a\)는 다른 슬롯 손잡이에 대한 훈련 데이터의 영향을 받지 않으므로 별도 계산할 수 있다. 이제 혼합 모형이라는 더 재밌는 사례를 살펴보자.

응용 프로그램 다수의 경우 특정 슬롯 손잡이 변수에 더하여 모든 슬롯 손잡이가 공유하는 변수를 사용하는 편이 선호된다. 예를 들자면 어떤 사용자는 정치 기사만 선호할 수 있고 뉴스 기사 추천은 이에 대한 메커니즘을 제공할 수 있다. 따라서 공유 또는 비공유 구성 요소가 함께 있는 변수를 갖는 편이 좋다. 식 (2) 우항에 또 다른 선형 항을 추가한 다음의 혼합 모형을 채택하자.

여기서 \(\mathbf{z}_{t, a} \in \Bbb{R}^k\)는 특정 사용자 / 기사 조합의 변수이고 \(\boldsymbol{\beta}^*\)는 모든 슬롯 손잡이 공통의 알려지지 않은 계수 벡터이다. 계수 \(\boldsymbol{\beta}^*\) 중 일부는 모든 슬롯 손잡이에 의해 공유되는 반면 \(\boldsymbol{\theta}^*_a\)는 그렇지 않다는 점에서 본 모형은 혼합이다.

혼합 모형의 경우 슬롯 손잡이 다수의 신뢰 구간이 공유 변수로 인해 독립이 아니므로 알고리즘 1을 더 이상 사용할 수 없다. 다행히 이전 절의 추론을 동일하게 따라가며 UCB를 계산하는 효율적 방법이 있다. 식의 전개는 블록 행렬의 역을 구하는 기법에 크게 의존한다. 지면 상 제약으로 알고리즘 2에서는 의사 코드만 제시하겠다(5와 12행은 계수의 릿지 회귀 해를 계산하고 13행은 신뢰 구간을 계산함). 상세한 전개식은 정식 논문에 적어둔다. 알고리즘을 구성하는 블록들(\(\mathbf{A}_0, \mathbf{b}_0, \mathbf{A}_a, \mathbf{B}_a\)와 \(\mathbf{b}_a\))의 차원은 모두 고정된 크기이며 점진적 업데이트 수행 또한 가능하므로 본 알고리즘은 계산 효율적이다. 그리고 \(\mathcal{A}_t\)에서 제거된 슬롯 손잡이와 관련된 수치는 더 이상 계산에 사용되지 않는다. 마지막으로 모든 시행 대신 역행렬들(\(\mathbf{A}^{-1}_0\)와 \(\mathbf{A}^{-1}_a)\)을 주기적으로 계산하고 캐시하면 시행 당 계산 복잡도를 \(O(d^2 + k^2)\)로 줄일 수 있다.


알고리즘 2 혼합 선형 모형을 이용한 LinUCB


0: 입력: \(\alpha \in \Bbb{R}_+\)
1: \(\mathbf{A}_0 \leftarrow \mathbf{I}_k\) (\(k\)차원의 항등 행렬)
2: \(\mathbf{b}_0 \leftarrow \mathbf{0}_k\) (\(k\)차원의 영 벡터)
3: for \(t = 1, 2, 3, \ldots , T\) do
4: \(\qquad\) 모든 슬롯 손잡이 \(a \in \mathcal{A}_t\)의 변수 (\(\mathbf{z}_{t, a}, \mathbf{x}_{t, a} \in \Bbb{R}^{k + d}\))를 관측함
5: \(\qquad \hat{\boldsymbol{\beta}} \leftarrow \mathbf{A}^{-1}_0\mathbf{b}_0\)
6: \(\qquad \) for all \(a \in \mathcal{A}_t\) do
7: \(\qquad \qquad\) if \(a\)가 신규라면 then
8: \(\qquad \qquad \qquad \mathbf{A}_a \leftarrow \mathbf{I}_d\) (\(d\) 차원의 항등 행렬)
9: \(\qquad \qquad \qquad \mathbf{B}_a \leftarrow \mathbf{I}_{d \times k}\) (\(d \times k\) 차원의 영 행렬)
10: \( \qquad \qquad \qquad \mathbf{b}_a \leftarrow \mathbf{0}_{d \times 1}\) (\(d\) 차원의 영 벡터)
11: \(\qquad \qquad \) end if
12: \(\qquad \qquad \hat{\boldsymbol{\theta}}_a \leftarrow \mathbf{A}^{-1}_a\left(\mathbf{b}_a - \mathbf{B}_a\hat{\boldsymbol{\beta}}\right)\)
13: \(\qquad \qquad s_{t, a} \leftarrow \mathbf{z}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_0\mathbf{z}_{t, a} - 2\mathbf{z}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_0\mathbf{B}^{\mathsf{T}}_a\mathbf{A}^{-1}_a\mathbf{x}_{t, a} + \mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{x}_{t, a} + \mathbf{x}^{\mathsf{T}}_{t, a}\mathbf{A}^{-1}_a\mathbf{B}_a\mathbf{A}^{-1}_0\mathbf{B}^{\mathsf{T}}_a\mathbf{A}^{-1}_a\mathbf{x}_{t, a}\)
14: \(\qquad \qquad p_{t, a} \leftarrow \mathbf{z}^{\mathsf{T}}_{t, a}\hat{\boldsymbol{\beta}} + \mathbf{x}^{\mathsf{T}}_{t, a}\hat{\boldsymbol{\theta}}_a + \alpha\sqrt{s_{t, a}}\)
15: \(\qquad \) end for
16: \(\qquad\) 슬롯 손잡이 \(a_t = \arg\max_{a \in \mathcal{A}_t} p_{t, a}\)를 선택하되 동점인 경우 무작위로 정하고 실수값 손익 \(r_t\)를 관측함
17: \(\qquad \mathbf{A}_0 \leftarrow \mathbf{A}_0 + \mathbf{B}^{\mathsf{T}}_{a_t}\mathbf{A}^{-1}_{a_t}\mathbf{B}_{a_t} \)
18: \(\qquad \mathbf{b}_0 \leftarrow \mathbf{b}_0 + \mathbf{B}^{\mathsf{T}}_{a_t}\mathbf{A}^{-1}_{a_t}\mathbf{b}_{a_t} \)
19: \(\qquad \mathbf{A}_{a_t} \leftarrow \mathbf{A}_{a_t} + \mathbf{x}_{t, a_t}\mathbf{x}^{\mathsf{T}}_{t, a_t}\)
20: \(\qquad \mathbf{B}_{a_t} \leftarrow \mathbf{B}_{a_t} + \mathbf{x}_{t, a_t}\mathbf{z}^{\mathsf{T}}_{t, a_t}\)
21: \(\qquad \mathbf{b}_{a_t} \leftarrow \mathbf{b}_{a_t} + r_t\mathbf{x}_{t, a_t}\)
22: \(\qquad \mathbf{A}_0 \leftarrow \mathbf{A}_0 + \mathbf{z}_{t, a_t}\mathbf{z}^{\mathsf{T}}_{t, a_t} - \mathbf{B}^{\mathsf{T}}_{a_t}\mathbf{A}^{-1}_{a_t}\mathbf{B}_{a_t} \)
23: \(\qquad \mathbf{b}_0 \leftarrow \mathbf{b}_0 + r_t\mathbf{z}_{t, a_t} - \mathbf{B}^{\mathsf{T}}_{a_t}\mathbf{A}^{-1}_{a_t}\mathbf{b}_{a_t}\)
24: end for

4. 평가 방법론

보다 표준화된 지도 학습 환경에서 기계 학습과 비교할 때 컨텍스츄얼 밴딧 설정에서의 방법 평가는 좌절감을 느낍니다. 여기에서 우리의 목표는 적기 알고리즘 \(\pi\)의 성능, 즉 앞의 상호 작용 (예 : 위에 설명 된 알고리즘)을 기반으로 각 시간 단계에서 팔을 선택하는 규칙을 측정하는 것입니다. 대화 형 특성 때문에 문제는 “라이브”데이터에서 알고리즘을 실제로 실행하는 것입니다. 그러나 실제로이 접근법은 심각한 병참 문제로 인해 실행 불가능할 수 있습니다. 오히려 완전히 다른 로깅 정책을 사용하여 이전에 수집 된 오프라인 데이터 만 사용할 수 있습니다. 결과 값은 로깅 정책에 의해 선택된 팔에서만 관찰되기 때문에 평가되는 알고리즘 \(\pi\)에 의해 선택된 알고리즘과는 종종 다르기는하지만 그러한 로깅 된 데이터에만 기반하여 π를 평가하는 방법은 명확하지 않습니다. 이 평가 문제는 소위 “정책 외 평가”의 특별한 경우로 볼 수 있습니다 문제 “를 강조한다 (참조, c.f., [23]).

한 가지 해결책은 기록 된 데이터로부터 적기 프로세스를 모델링하기 위해 시뮬레이터를 구축 한 다음 시뮬레이터로 π를 평가하는 것입니다. 그러나 모델링 단계는 시뮬레이터에 바이어스를 도입 할 것이므로이 시뮬레이터 기반 평가 방법의 신뢰성을 정당화하는 것을 어렵게 만듭니다. 대조적으로, 우리는 구현하기 쉽고, 기록 된 데이터에 근거하고, 편견없는 접근법을 제안합니다.

(번역 중)

  1. 문헌에 따라 때론 컨텍스츄얼 밴딧은 공변량을 갖는, 부가적 정보가 있는, 또는 연관성 있는 다중 슬롯머신 실험 아니면 연관성 있는 강화 학습이라고 불리운다. 

  2. \(\tilde{O}(\cdot)\)의 경우 로그 인수가 표기에서 빠지는 점을 제외하면 \(O(\cdot)\)와 동일하다. 

  3. P. Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3:397–422, 2002.  2