- 글 작성에는 추천팀 sasha.k와 marv.20가 함께해 주셨습니다.

머신러닝에 대한 기초 지식이 있고, 추천 알고리즘에 관심이 있는 분들에게 카카오 추천팀이 개인화 추천 기술을 활용하는 방법에 대해 공유합니다.

우리의 일상 속에는 수많은 추천이 함께합니다. 카카오 추천팀은 카카오가 제공하는 서비스들에서 여러분들이 더 좋은 추천을 경험하실 수 있도록 매일 노력하고 있는데요, 오늘은 수없이 많은 정보 가운데 여러분 한 분 한 분에게 도움이 될만한 콘텐츠를 콕 집어 추천해 주는 개인화 추천 기술에 대해 함께 알아보려고 합니다.

위와 같은 기사에 대해서 한번 생각해 볼게요, 이 기사에 대해 평균적으로 기대할 수 있는 클릭률을 N%라고 계산했을 때 이는 모든 사람에게 동일하게 기대할 수 있는 값은 아닙니다. 한국 야구에도 관심이 많고 추신수 선수에게도 관심이 많은 어떤 사람은 이 콘텐츠를 보자마자 클릭을 할 수도 있고, 야구에는 별로 관심이 없고 해외 축구에만 관심이 많은 사람은 이 콘텐츠를 보더라도 제목만 보고 클릭은 하지 않을 수도 있습니다.

이처럼 개인마다 각 콘텐츠에 기대할 수 있는 클릭률을 계산하고 클릭할 확률이 가장 높은 콘텐츠들을 각 사용자에게 맞춤형으로 제시해 주는 것이 개인화 추천 기술이라고 할 수 있겠습니다.

각 서비스마다 조금씩 다른 방법으로 개인화 추천이 이루어지고 있지만 오늘은 토픽 모델링과 실시간 최적화(Multi-Armed Bandit(MAB) 방식의 실시간 최적화)를 함께 활용한 개인화 추천 프레임워크 기술에 대해 소개하고자 합니다. 실제로 카카오 추천팀에서 많이 사용하고 있는 방법 중 하나이기도 합니다.

우선 토픽 모델링과 MAB에 대해 각각 설명한 후, 이 둘을 함께 활용해서 어떻게 개인화된 추천 결과를 생성할 수 있는지에 대해 소개하겠습니다.

토픽 모델링이란?

토픽 모델링은 기존에 자연어 처리 분야에서 사용되고 있었던 기법[1]입니다. 하나의 문서 안에 다양한 주제가 있다고 가정할 때, 문서별로 속한 단어들을 가지고 문서가 각 주제에 대해 얼마나 속해 있는지를 계산하는 것이죠. 비교적 오래된 기법의 하나지만, 따로 정답이 있는 데이터가 없어도 문서별로 속한 단어만 알고 있으면 학습할 수 있기 때문에 지금까지도 많이 사용되고 있습니다.

개인화 추천에서도 사용자들과 콘텐츠들의 특징을 추출하기 위해 토픽 모델링을 먼저 진행하게 됩니다.

한 문서 안의 단어들을 바탕으로 함축되어 있는 여러 개의 주제를 찾을 수 있는 것처럼, 아이템을 바탕으로 찾으면 한 명의 사용자 또는 콘텐츠 안에 내포되어 있는 주제가 여러 개 있다고 볼 수 있기 때문에, 토픽 모델링 기법을 개인화 추천에 적용할 수 있는 것입니다.

자연어 처리 분야에서는 문서별로 속한 단어들을 가지고 토픽 모델링을 수행했었는데, 여기서 '문서’를 '사용자’로, '단어’를 '아이템’으로 바꾸게 되면, 서비스 내의 클릭 로그를 가지고 토픽 모델링을 수행할 수 있게 됩니다. 그 결과, 위 그림처럼 각 사용자에 대한 주제 벡터를 구할 수 있습니다. 이때, 벡터의 크기 k는 주제(토픽)의 개수이며 각각의 값은 주제에 속할 확률을 의미하게 됩니다.

카카오 추천팀에서는 개인화 추천을 위해 사전에 토픽 모델링을 수행하여 각 사용자와 아이템이 어떤 주제에 속하는지를 판단합니다. 이제 각각의 토픽에 대해 실시간 최적화를 수행하는 방법에 대해 알아보겠습니다.

실시간 최적화에 대한 고찰

MAB(Multi-Armed Bandit)이란 무엇인가

참고 :
Multi-Armed Bandit(MAB)은 슬롯머신의 손잡이(Arm)를 지칭하던 말에서 유래한 알고리즘 모델로, 슬롯머신 투자를 최적화하기 위해 시작된 알고리즘이라고 합니다. 각 슬롯머신의 승률이 다르다는 경험적인 사실을 바탕으로, 각 슬롯머신마다 다른 보상(Reward) 중 어떤 슬롯을 어떤 순서로 당겨야 가장 많은 보상을 확보할 수 있는가의 문제를 MAB라고 부르기 시작했습니다. 슬롯머신 문제로 보면, 탐색(Exploration)은 각 슬롯머신의 승률을 확인하는 과정이며, 활용(Exploitaion)은 가장 높은 승률이 예상되는 슬롯머신을 선택해 본격적으로 손잡이(Arm)를 당기는 과정입니다. 이 탐색과 활용의 비율을 어떻게 조정하느냐에 따라 입실론-그리디(Epsilon-Greedy), 소프트맥스(Softmax), UCB(Upper Confidence Bound), 톰슨 샘플링(Thompson-Sampling) 등 다양한 알고리즘이 있습니다.

실시간 최적화를 위해서는 MAB[2] 모델을 사용할 수 있습니다. MAB는 강화 학습[3] 문제의 일종으로, 보상(Reward)를 알 수 없는 K개의 선택지가 존재할 때 탐색(Exploration)과 활용(Exploitation)을 적절히 조절하여 최종 보상(Reward)의 총합을 최대화하는 문제라고 볼 수 있습니다.

사용자에게 어떤 콘텐츠를 추천하면 좋을지 탐색하기 위하여 새로운 콘텐츠를 추천해 주고 피드백을 수집하는 것이 탐색(Exploration), 수집된 피드백을 바탕으로 사용자가 가장 좋아할 것으로 예상되는 콘텐츠를 추천해 주는 것이 활용(Exploitation)의 예라고 할 수 있습니다.

여기에서는 저희 추천 서비스에 MAB를 사용하는 이유, 그리고 대표적 MAB 알고리즘 중 하나인 톰슨 샘플링(Thompson-Sampling)에 대해 살펴보겠습니다.

MAB를 사용하는 이유

기존 서비스에 새로운 추천 시스템을 만들고자 한다고 가정해보겠습니다. 활용할 수 있는 알고리즘 기법에는 어떠한 것들이 있을까요?

대표적으로 전통적인 협업 필터링(Collaborative Filtering, 이하 CF) 기법이 있을 것입니다. Netflix Prize1 이후 모델 기반(Model-based) CF 추천 알고리즘에 대한 활발한 연구가 이루어졌습니다. 요즘도 학계에서는 여기에서 시작된 전통 CF 프레임워크 구조를 바탕으로 SOTA(State-of-the-art) 성능을 자랑하는 모델들에 대한 많은 연구들이 이루어지고 있습니다.

즉, 굳이 실시간으로 사용자의 피드백에 대해 MAB 학습을 하지 않아도 과거 데이터와 다양한 머신러닝 모델 등을 통하여 추천을 할 수 있는 다양한 방식들이 있습니다.

그렇다면 실제 개인화 추천 서비스에서 강화 학습 기반의 MAB 알고리즘들을 사용하는 것은 어떠한 장점들이 있기 때문에 사용하는 것일까요? 예를 들어 전통 CF 프레임워크 하에서 학습된 모델과 한번 비교해보겠습니다.

다양한 장점들이 있을 수 있겠지만 크게 3가지를 소개하고자 합니다. 첫 번째는 ‘실제 환경에서 목표(Objective)를 학습’할 수 있다는 것, 두 번째는 장기적인 보상(Reward)를 최적화 시켜주는 ‘탐색(Exploration)’, 그리고 세 번째는 ‘실시간성’입니다.

1넷플릭스 사용자들의 영화 별점 데이터를 바탕으로 2006년 10월~2009년 7월의 약 3년간에 걸쳐 이어진 영화 평가 데이터 예측 대회로, 본 대회를 통해 협업 필터링(Collaborative Filtering) 기법이 발전 및 공유되었습니다.

대리 목표(Surrogate Objective) vs 실제 목표(Real Objective) : 실제 환경을 바탕으로 학습 가능

전통적인 CF 프레임워크에서는 유저와 아이템의 상호작용(Interaction)에 대한 과거 데이터 X를 바탕으로 어떤 유저 u의 어떤 아이템 i에 대한 선호도 y_u, i를 예측할 수 있는 모델 f(y_u,i|X)를 주로 지도학습(Supervised Learning)[4]을 통해 학습합니다. 이때 y_u, i가 유저의 아이템에 대한 선호도를 나타낼 수 있는 목표(Objective)이며, 평점, 클릭 여부, 체류 시간 등이 될 수 있습니다. 지도학습을 위해서는 학습에 사용될 입력 데이터 X와 레이블(Label)에 해당하는 Y가 사전에 주어져야 합니다.

반면 MAB는 강화 학습 기반의 프레임워크로써, 에이전트가 실제 환경에서 직접 상호작용을 하며 피드백을 학습합니다. 즉, 추천 모델이 유저 u에게 아이템 i를 추천해 주고 그에 대한 실제 피드백을 관찰하며 모델을 업데이트합니다. 최적화하고자 하는 목표(Objective)가 클릭이라고 가정해보겠습니다. 이 경우 피드백으로 받게 되는 보상(Reward) r_u, i는 ‘유저 u에게 아이템 i를 추천해 줬을 때 그 추천 결과를 클릭하였는지’로 정의할 수 있습니다.

과거 데이터를 바탕으로 지도학습 CF 모델을 학습할 경우에는 목적 함수(Objective Function)를 어떻게 설정하여야 할까요? 모델의 추천 결과를 사람에게 보여주고 이에 대한 반응(피드백)을 살펴볼 수 없기 때문에 ‘추천해 줬을 때 클릭을 하는지’를 직접적으로 최적화할 수는 없습니다. 그렇기 때문에 실제 목표도 잘 맞출 수 있도록 유도하는 대리 목표(Surrogate Objective)를 설정하게 됩니다.

즉, 클릭을 많이 받는 추천 시스템을 만들고자 했을 때, 기존에 축적된 서비스 로그를 통해 y_u, i를 ‘유저 u가 아이템 i를 클릭한 적 있는지’와 같이 정의합니다. 그러면 모델 f(y_u,i|X)는 어떤 사용자가 해당 아이템을 소비했을 확률을 예측하고 소비하지 않은 아이템 중 확률 값이 높은 아이템을 추천합니다. 다시 말해, 대리 목표(Surrogate Objective)를 최적화함으로써 간접적으로 실제 목표(Real Objective) 또한 잘 맞추도록 학습되길 기대하는 것입니다. 이처럼 과거 데이터를 기반으로 한 CF 모델과 강화 학습 기반의 MAB 모델은 학습하는 목표(Objective)가 분명히 다릅니다.

MAB의 경우 구현된 현실 추천 시스템에서 사용자에게 모델이 직접 추천을 하고 그에 대한 반응으로서의 피드백을 학습합니다. 반면, CF 모델의 경우 전체 서비스의 방대한 과거 데이터를 사용할 수 있다는 장점이 있지만, 개별 추천 행동(Action) 과는 무관하게 사용자의 이력(History)으로부터 선호도를 추출하고자 합니다.

하지만 사용자는 예를 들면, 콘텐츠를 직접 찾아 소비할 때보다 추천 시스템을 사용할 때는 익숙한 콘텐츠보다는 새로운 콘텐츠를 찾고자 할 수도 있습니다. 또한, 현실의 추천 시스템은 UX 등 다양한 요인에 따라 그 시스템 내에서 클릭률이 높은 아이템의 특성이 달라질 수도 있습니다.

결국 실제 시스템에서 행동(Action)에 대한 피드백을 취한 게 아닌, 과거 데이터로부터 정의한 대리 목표(Surrogate Objective)를 정답으로 학습한 모델의 경우, 실제 현업에서 해당 추천 시스템의 클릭률/구매율 등의 KPI를 최적화하고자 할 때에는 실제 목표(Real Objective)와 간극이 발생할 수밖에 없습니다.

더 자세한 내용은 CF 모델과 실제 현업에서의 실제 목표 사이의 간극에 대해 논의한 논문[5]을 참고하시기 바랍니다.

탐색(Exploration): 장기적 보상(Reward) 최적화

MAB는 T 번의 타임 스텝(Time Step) 동안 행동(Action)을 취하는 일종의 MDP(Markov Decision Process, 마르코프 결정 과정)[6] 하에서 누적 보상(Reward)를 최대화할 수 있도록 설계된 알고리즘입니다.

그렇기 때문에 당장 현재 스텝(Step)에서 기대 보상(Reward)이 높지 않더라도 이후 미래의 보상을 높여줄 수 있다면 해당 행동을 선택합니다. 이를 탐색(Exploration)이라고 합니다. 탐색(Exploration)을 통해 사용자가 익숙하지 않지만 좋아할 수도 있는 새로운 아이템을 추천하기도 하죠. 반면, 전통적인 CF 프레임워크에서는 과거 데이터를 바탕으로 현재 가장 선호할 아이템만을 추천합니다. 고정된 하나의 타임 프레임(Time Frame)을 가정하기 때문에 미래의 보상과 같은 개념은 없습니다. 활용(Exploitation)만 하게 되는 것이죠.

현실의 추천 시스템은 근본적으로 사용자와 시스템이 상호작용하며 동적으로 변화합니다. MAB의 설정이 현실에 더 적합한 부분이 있는 것이죠. 같은 아이템만을 계속 추천해 주면 사용자가 더 이상 좋아하지 않을 것이고, 탐색 없이 활용(Exploitation)만 한다면 새롭게 추가되는 아이템들은 추천에서 배제될 것입니다. 이처럼 미래의 보상(Reward)도 고려한 탐색(Exploration)은 추천 시스템의 장기적인 성능에 많은 도움이 됩니다.

실시간성

MAB 알고리즘의 또 다른 장점은, 사용자의 피드백이 실시간으로 모델에 적용되어 추천 결과에 나타난다는 것입니다. 이러한 실시간 업데이트는 사용자의 경험에 긍정적으로 작용하는 정성적 효과뿐만 아니라 실제 클릭률 지표에도 수치적으로 영향을 미칩니다.

추천 결과를 보여주고 그에 대한 사용자의 피드백이 모델에 반영되어 다시 추천 결과에 나타나는 한 번의 루프(Loop)에 드는 시간이 얼마나 짧은지에 따라 실제 클릭률이 유의미하게 달라지며, 실험 결과 이러한 업데이트 소요 시간이 짧으면 짧을수록 클릭률도 올라갔습니다.

오프라인(Offline) 모델(정적 모델로, 모델을 한 번만 학습시키고 일정 기간 사용하는 방식) 중에도 데이터가 생성될 때마다 점증적(Incremental)으로 계산하여 빠르게 업데이트할 수 있는 경우도 있긴 합니다.

하지만 앞서 얘기한 실제 목표를 학습하고 탐색도 함께 한다는 장점 등과 함께, 애초에 실시간으로 업데이트하는 구조를 가정하고 설계된 MAB 알고리즘이 실시간 최적화를 달성하기에 더 유리하겠죠? 이 장점들은 사실 MAB만의 장점이라기보다는 강화 학습 프레임워크의 장점이라고 볼 수도 있습니다.

대표적인 MAB 알고리즘, 톰슨 샘플링(Thompson Sampling)

참고:
톰슨 샘플링은 기댓값(보상)의 분포를 추정한 후 샘플링한 값을 기준으로 보상을 계산하는 확률적 알고리즘으로, 피드백을 수용해 기댓값의 분포를 업데이트 가능한 장점이 있습니다.
이해를 돕기 위해 대표적인 MAB 알고리즘 중 하나인 톰슨 샘플링[7]을 예시로 구체적인 작동 방식을 알아보겠습니다.

pseudo code ref: [8]

K개의 Arm이 존재하는 톰슨 샘플링 수도 코드를 살펴보겠습니다. 추천 시스템의 경우, 각 Arm은 하나의 콘텐츠, Success는 클릭을 의미하며, 어떤 Arm을 선택하는 행동은 해당 콘텐츠를 추천하는 것이 됩니다.

톰슨 샘플링은 베이지안 통계를 기반으로 하여 각 K개 Arm(콘텐츠)들의 성공(클릭) 확률을 베타 분포[9]를 따르는 확률변수로 보고, 처음에는 동일한 파라미터를 가지는 베타 분포로 전부 초기화합니다. 그리고 매 타임 스텝 t마다 각 Arm의 확률분포로부터 예상 클릭률 theta_i를 샘플링한 후 값이 가장 높은 Arm을 선택하고, 그에 대한 Reward를 바탕으로 베타 분포가 계속 업데이트되는 형식입니다. t가 커질수록 각 Arm의 베타 분포는 수렴하여 분산이 작아질 것이고, 초기(모든 Arm의 분산 값이 높아서 탐색이 활발했을 때)에 비해 점점 기댓값이 높은 Arm 위주로 활용(Exploitation)이 이루어지게 됩니다.

개인화 추천 과정

지금까지 개인화 추천 방식을 이해하기 위해 그 구성요소인 토픽 모델링과 MAB에 대해 간단히 알아보았습니다.

개인화 추천은 사용자 각각의 취향에 부합하면서도 현재 상황에 가장 적절한 콘텐츠를 추천해 주어야 하는데요, 토픽 모델링을 통해 사용자의 취향과 아이템의 주제를 알아내는 역할을 진행하고, 이 정보를 바탕으로 MAB를 통한 실시간 최적화를 진행하여 현재 상황에 가장 적절한 콘텐츠를 추천해 주고 있습니다.

그럼 이제 단계별로 어떻게 개인화 추천이 제공되는지를 알아보겠습니다.

추천이 나가기 전

먼저 추천이 제공되기 전에 사전에 쌓아놓았던 사용자와 아이템 간의 클릭 로그를 기반으로 토픽 모델링을 진행해, 사용자와 아이템 각각에 대한 주제 벡터를 계산해놓습니다. 이때, 사용자의 주제 벡터는 사용자가 각 주제를 얼마나 선호하는지를 의미하고, 아이템의 주제 벡터는 아이템이 각 주제에 얼마나 속하는지를 의미하게 되겠죠. 그런 다음, 각 주제별로 MAB를 하나씩 할당합니다.

위 그림을 예로 들면, 사전에 진행한 토픽 모델링을 통해 사용자와 아이템이 [‘패스트푸드’, ‘제과’, ‘육류’]라는 주제에 얼마나 속하고 있는지를 계산합니다. 사용자의 주제 벡터가 [0.06, 0.10, 0.84]로 이루어져 있다는 것은 사용자가 ‘육류’라는 주제에 관심이 많다는 것을 의미합니다. 그와 동시에 각 주제에 해당하는 MAB에서는 모든 아이템에 대해 각 주제에 맞는 추천 점수를 가지고 있습니다.

추천 요청이 들어올 때

사용자에 대한 추천 요청이 들어올 경우, 주제별 MAB들의 추천 점수들을 사용자의 주제 벡터에 맞게 가중평균하여 계산합니다. 토픽 모델링에서 구한 사용자의 취향이 '육류’에 치우쳐져 있다면, 추천 결과 또한 ‘육류’ MAB의 추천 결과에 가중하여 전달하는 것이죠.

피드백을 통한 실시간 최적화

그런 다음 어떤 사용자의 추천 결과에 대한 피드백을 받게 되면, 피드백 또한 추천이 나갈 때처럼 주제별로 속할 확률을 바탕으로 각 MAB에 피드백을 나누어서 전달하게 됩니다. 이 피드백에 해당하는 추천이 ‘패스트푸드’라는 주제에 집중했었던 추천이었다면, 해당 추천의 피드백 또한 ‘패스트푸드’의 MAB에 집중되어 전달되게 됩니다.

마치며

지금까지 카카오 추천팀에서 토픽 모델링과 MAB 알고리즘을 통해 개인화 추천을 제공하는 방법에 대해 알아보았습니다. 이 방법은 학습이나 추천에 필요한 연산량이 적고 모델 크기가 작으면서도 많은 사용자에게 개인화된 추천을 제공할 수 있다는 점에서 자주 사용되고 있습니다.

카카오 추천팀 내에서는 이 외에도 컨텍스트 밴딧(Contextual Bandit)이나 딥러닝을 통한 개인화 추천도 제공하고 있는데요, 각 서비스의 특성과 모델의 장단점을 고려하여 서비스에 맞는 방법론이 선택되고 있습니다.

다음 편에서는 Content-Based Filtering과 Collaborative Filtering에 대해 자세히 알아보도록 하겠습니다. 감사합니다.

참고문헌

[1] Probabilistic Latent Semantic Indexing Wiki (https://en.wikipedia.org/wiki/Probabilistic_latent_semantic_analysis)
[2] Multi-Armed Bandit Wiki (https://en.wikipedia.org/wiki/Multi-armed_bandit)
[3] Reinforcement Learning Wiki (https://en.wikipedia.org/wiki/Reinforcement_learning)
[4] Supervised Learning Wiki (https://en.wikipedia.org/wiki/Supervised_learning)
[5] Rethinking Collaborative Filtering, RecSys ‘17 (https://dl.acm.org/doi/10.1145/3109859.3109919)
[6] Markov Decision Process Wiki (https://en.wikipedia.org/wiki/Markov_decision_process)
[7] Thompson Sampling Wiki (https://en.wikipedia.org/wiki/Thompson_sampling)
[8] An Empirical Evaluation of Thompson Sampling, NIPS’ 11 (https://papers.nips.cc/paper/2011/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf)
[9] Beta Distribution Wiki (https://en.wikipedia.org/wiki/Beta_distribution)

함께 하면 좋은 글

추천 기술과 관련된 더 다양한 자료는 추천팀 소개 페이지에서 확인하실 수 있습니다.

카카오 AI추천 : 토픽 모델링과 MAB를 이용한 카카오 개인화 추천