넷플릭스에서는 영상 이미지, 즉 artwork를 어떤 것을 선택할지에 대해 추천 로직을 적용하고 있다.이미지는 대표성과 정보성, 매력, 차별성을 지녀야 하는데 이 모든 것이 개인적인 성향에 영향을 받을 수밖에 없다.사람들은 대개 장르 또는 캐스팅에 대한 선호도를 가지는데, 이 선호가 이미지에 반영될 수 있다.행과 열로 구성된 바둑판 화면을 inventory라고 하면, 각 계좌에 배치할 오더링과 계좌에 넣을 광고 이미지 중 어느 것을 선택해야 하는가?이들은 모두 추천 알고리즘으로 돌아간다.
전통적인 추천 방식은 단연 Collaborative Filtering이다. 하지만 이래서는 부족하다.CF는 현재 운영 중인 상품 풀 내에서만 유사한 상품 추천이 가능해 새롭게 탐색할 수 있는 방법이 없다.새로운 상품이 유입되면 cold-start 문제로 적절히 추천할 수 없다.또한 사람들의 선호는 실시간으로 바뀌고 반응할 경우 rating을 붙이지만 모델 입장에서는 rating으로 인해 특정 사용자가 반드시 그 영화를 선호/좋아하지 않았다고 단언할 수 없다.(implicitfeedback) A, B, C가 노출되었을 때 A를 선택하였다고 하더라도 반드시 A를 선호한다고 단정할 수 없고, 기타 영화를 비선호한다고 할 수 없다.
이러한 맥락에서 추천 문제를 MAB에 접목하였다.학습자는 지속적으로 action하고 그에 대한 reward를 받는다. 이때 학습자는 누적 보상치를 극대화하는 방향으로 행동해 나간다.넷플릭스도 똑같이 작동하지만 사람들은 홈페이지에서 마음에 드는 artwork를 선택하고 알고리즘은 매칭률을 높이는 방향으로 업데이트한다.
Bandit는 각 action에 대한 optimial 보상과 선택된 보상의 간격을 줄이는 것을 목표로 한다.메탈릭은 반응수/노출수로 하게 되는데, 예를 들어 영화 A에 대해 4명의 사용자에게 보여주고, 2명이 반응했다면 2/4을 관측치로 사용한다.이렇게 전체 영화에 대해 관측치를 계산하면 두 전략 사이에 고민이 발생한다.1) 현재 경험상 가장 베스트 선택지를 고른다 2) 아직 경험하지 못한 선택지를 선택하여 경험을 쌓는다 1)를 Maximization/Exploitation 전략, 2)을 Exploreration 전략이라 부른다.2)는 장기적으로 가장 좋은 선택을 할 수 있도록 정보를 쌓는다는 장점이 있다.데이터를 모으는 것이 궁극적으로는 초기에 탐험에 소요된 시간과 비용을 보상하는 것이라고 생각한다.
얼마나 탐색하고 얼마나 수확하면 좋을까? 내가 탐색을 통해 찾은 전략이 optimal이라고 할 수 있을까.이러한 상황에서 취할 수 있는 전략은 다음과 같다.A. 단순히 Exploreration을 지속한다(Naive Exploreration) B. 불확실하지만 Optimize 해 나간다(Optimism) C. 확률 분포에 의한 유추(Probabilstic)
A를 취하는 알고리즘으로서 e(입실론)-greedy가 있다. 입실론 확률만 exploration 하는 것이다.초기에는 탐색을 진행하고 일정 시간 후에 분기를 정해 입실론만큼 탐색하고 기타 서브옵티말 액션에 대해 수확한다.알고리즘이 간단하다는 장점이 있지만 오차가 무한정 있을 수 있다는 단점이 있다.가장 좋은 보상이라고 생각하는 게 사실상 옵티멀이 아닐 수 있기 때문이다.
B를 취하는 알고리즘으로는 UCB(Upper Confidence Bound)가 있다.지금까지 관측된 결과를 토대로 예측된 보상의 신뢰도를 계산한 후 신뢰도 UpperBound가 가장 높은 action을 취한다.해당 액션에 대한 결과를 재업데이트하여 신뢰도를 재계산한다.이 알고리즘은 지금까지 탐색한 action에 대한 보상뿐만 아니라 해당 보상이 얼마나 불확실성을 가지고 있는지까지 추정하게 된다.즉, action별 최고 성과에 대한 기록과 각 보상을 얻기까지 얼마나 많은 탐색을 거쳤는지(=즉 얼마나 불확실성을 갖는지)도 따지게 된다.장점은 이론적으로는 오차를 optimize해 나간다는 것이지만 단점은 관측된 값을 빠르게 업데이트해야 한다는 것이다.
예를 들어 아래 그림에서 왼쪽일 경우 2번 action이 가장 높은 UCB를 갖는다. 그래서 2번을 선택하여 얻은 결과로 신뢰도를 update 한다.그러나 대부분의 경우 불확실성이 가장 큰 action이 UCB를 가질 것이다. 따라서 오른쪽 그림과 같이 1번이 action으로 선택되고, 이 1번은 일정 정도의 exploration을 통해 UCB가 현재에 비해 줄어들 것이다. 이 과정이 바로 불확실한 보상에 대해 더 많은 탐색을 진행하게 되는 과정이다.
출처 : http://jyoondev.tistory.com/137 만약 각 artwork에 대한 베타 분포를 이용하여 UCB 알고리즘을 적용해보면 아래와 같이 a, b, c 세 영화에 대해 각각 관측된 반응값에 따라 베타 분포를 만들어준다. 베르누이 분포의 p값을 클릭/반응으로 잡아보면 사전 확률 분포는 p의 분포와 같다. (0<=p<=1)
데이터를 어느 정도 수집했으므로 사후 확률 분포를 그릴 수 있는데, a, b, c에 대해 클릭 이력을 input하여 베타 확률 분포를 그린다.베타 확률 분포는 일반적으로 비율을 설명할 때 사용되며 파라미터로는 알파와 베타를 받는다. B(x;a, b) 구조이지만 x를 반응률로 하면 특정 a, b 값에 따라 반응률이 x1~x2 구간 사이에 위치할 확률을 구할 수 있다.위 그림에서는 a는 영화별 클릭수, b는 총 클릭수로 하고 x는 반응률/클릭률로 한 것이다.그래프를 그렸으므로 신뢰도를 정한 후(ex.95%), 각 신뢰 구간을 찾아 가장 높은 UCB를 가진 분포도의 영화를 선택하는 것이다.
C를 취하는 알고리즘은 오늘날 가장 많은 곳에서 사용되는 Thompson Sampling이다.각 action이 최선이라는 확률에 따라 action을 취하는 것이다.즉, 각 action에 대해 확률 분포를 그린 후 샘플을 각 분포에 넣어 예측된 보상값을 비교한다.이 보상값을 선택해 행동을 취한 뒤 얻은 결과로 다시 분포를 업데이트해 나가는 것이다.
이하의 예를 보면, a, b, c의 섹션에 대해 각각 관측된 결과에 따른 확률 분포를 plotting하고, sampling에 의해 얻어진 결과를 바탕으로 각 분포를 수정해 나가는 것을 확인할 수 있다.결과적으로 1000회 시행 이후 각 action에 대한 실제 보상과 유사한 확률 분포를 그릴 수 있다는 것이다.
출처 : https://towardsdatas cience.com/thompson-sampling-fc28817eacb8
UCB와 달리 확률 분포를 바탕으로 랜덤 sample을 추출하게 돼 더 확률적으로 가장 큰 보상을 찾을 수 있다는 접근법이다.예를 들어 UCB는 관측된 결과 중 가장 높은 영화를 먼저 선택하게 되고 그 그래프를 업데이트해 나가는 방향인데, Thompson sampling은 그와 별도로 샘플링에 의해 랜덤으로 추출되므로 관측된 결과 중 가장 최악의 선택을 먼저 추천해 줄 수도 있다.Contextual Bandit
넷플릭스는 artwork 추천에 Bandit를 적용해 보면 아래와 같은 장애물을 접할 수 있다.1)선택에 따른 보상가격이 실시간으로 달라진다2) 보상이 어떻게 생성됐는지에 대한 설명이 안 되는 3)action이 무한하다, 각 action도 시간에 따라 달라진다 즉 Bandit는 여러 action을 취할 수 있도록 했지만 개인화된 추천을 하지 않은 것이다.개인화된 추천이라는 영화 장르에 대한 호감도나 영화 등정 배우에 대한 선호 등 개인의 context 정보가 없는 것이다.
이에 따라 Contextual Bandit을 생각하기 시작했다.앞서 본 밴디트 모델에 context라는 새로운 feature가 생긴 것이다. Context는 사용자의 디바이스, 사용자 성별 등이 해당될 수 있다.
앞서 본 세 알고리즘을 다시 contextual bandit에 적용해 보자.각 영화별로 이미 관측된 행동과 context를 feature를 사용하여 보상 확률 분포를 예측하는 모델들을 세우게 되어 A-epsilon greedy: 엡실론 확률만큼 이미지를 랜덤하게 뿌리고(exploration), 기타 확률로 개인화된 이미지를 보여준다.(exploitation) B-UCB: LinUCB 알고리즘 즉, 각 이미지별로 보상을 예측하는 선형(linear) 모델을 세워 특정 percentile 나의 상위값을 가진 모델을 선택한다. C-Thompson Sampling: 베이스 회귀분석과 같은 모델을 세워 확률분포를 예측한 후 각분포에서 샘플링하여 최선의 선택을 한다.밴디트 모델에 서비스를 서빙하게 되면 고려해야 할 사항이 있다.우선 처음에는 모델을 서빙하지 말고 데이터를 수집해야 한다.사용자가 제공하는 보상을 저장하고 어느 정도 데이터가 축적되면 모델을 학습해 추론된 결과로 추천해야 한다.
또 실시간으로 추천해 줄지, 아니면 온라인으로 저장된 데이터로 추천해 줄지 선택해야 한다.물론 실시간으로 추천해주면 신선함이 반영되지만 response가 제때 도착해야 하고 scalability가 보장돼야 한다.반면 대량의 데이터를 캐싱해 저장된 데이터로 추천하면 큰 데이터를 handling할 수 있지만 신선도는 떨어질 수 있다.
아키텍처 구성도 중요하며 취향 변화에 따른 로직 구성도 잘 짜여져 있어야 한다.예를 들어 개인화된 추천에 대한 반응이 좋지 않았다면 개인화를 제외한 추천(degraded)을 하고, 그래도 반응이 좋지 않으면 default 이미지를 제공하는 등의 논리가 준비되어 있어야 한다. 최상의 선택지를 제공하기 위해서다.
본고에서는 추천 시스템 알고리즘 중 Bandit 계열 알고리즘을 간단히 살펴보고 넷플릭스에서는 어떻게 활용하고 있는지를 확인할 수 있었다.다음 기사부터는 각 알고리즘에 대한 상세 로직과 contextual bandit에 대해 좀 더 살펴본다.참고자료 http://netflixtechblog.com/artwork-personalization-c589f074ad76Artworkisthefirstinstanceofpersonalizingnotjustwerecommendbutalsohowwerecommend.netflixtechblog.com
베타 분포 http://norman3.github.io/prml/docs/chapter02/1.html1.BinaryVariables 먼저 가장 간단한 형식부터 논의를 시작한다. 랜덤 변수 x가 x{{0,1}인 상황(즉, 취할 수 있는 값이 단 2개)에서의 확률 분포를 조사한다. 가장 쉬운 경우가 동전 던지기 예인데 동전을 던지고 앞면이 나오면 x=1, 뒷면이 나오면 x=0이다. 이때 이 동전의 앞·뒷면이 나올 확률이 서로 동일하지 않다면, 앞면이 나올 확률은 다음과 같이 정의할 수 있다. p(x=1|μ)=μ(2.1) 여기서 01μp1이다.(이…norman3.github.iohttps://www.real-statistics.com/binomial-and-related-distributions/beta-distribution/Beta Distribution Definition 1:For the binomial distribution the number of successes x is a random variable and the number of trials n and the probability of success p on any single trial are parameters(i.e. constants). Instead, we would now like to view the probability of success on any singlet…www.real-statistics.com