유튜브 추천시스템 논문 리뷰 Part 1 - The Youtube Video Recommendation System (RecSys 2010)

요즘 트렌드를 알고 싶다고 하면 유튜브를 빼놓고는 말하기 어렵습니다. VOD 시장에서 전통적으로 인기있었던 먹방, 겜방, 뷰티 방송이나 연예인 뮤비, 공연 영상 등은 기본이고, 최근에는 정치인들이 유튜브에 채널을 직접 개설하는 일도 늘어나고 있죠. 유튜브에 올라오는 영상들의 양과 종류에는 그야말로 한계가 없습니다.

대도서관이 운영하는 겜방

그렇다면 이렇게 다양한 종류의 콘텐츠가 끊임없이 올라오는 유튜브에서 발생하는 트래픽은 실제로 얼마나 될까요? 앱 분석업체인 WISEAPP에서 분석한 국내 2018년 11월 앱별 사용시간 통계를 한번 살펴보겠습니다.

2018년 11월 안드로이드 앱 총 사용시간 (출처: https://platum.kr/archives/112749)

유튜브의 사용시간은 317억 시간으로 소위 국민 앱이라는 카카오톡과 네이버를 압도합니다. 한국 국민 1명 당 하루 평균 대략 21분 정도 유튜브를 사용하고 있는 셈이죠. 유튜브 천하라는 말이 정말 피부로 와닿네요.

그런데 사람들이 유튜브를 이렇게 많이 쓰는 것은 단순히 유튜브에 재밌는 영상이 많이 올라오기 때문이 아니고, 이 영상들의 홍수 속에서 사용자들의 취향에 딱 맞는 영상을 골라내주기 때문입니다.

필자가 자기계발이나 재테크. 패션 관련 컨텐츠를 좋아해서 그런지 관련 영상이 많이 추천된다. 

그렇다면 유튜브는 어떤 방식으로 이 어마어마한 영상들 중에서 사용자가 원하는 영상을 골라내는 걸까요? 심플하게는 Matrix Factorization을 이용한 Collaborative Filtering을 쓸 수 있겠지만, 비디오와 유저 수가 수백만을 가볍게 넘기는 유튜브 정도의 스케일이 되면 다음과 같은 문제들을 풀어야 하기 때문에 그것조차도 간단하지는 않습니다.

• Distributed Training
  • 하나의 서버에 비디오/유저의 latent vector를 모두 올릴 경우 속도 저하나 메모리 부족 문제가 발생하므로 여러 서버에 추천 모델을 분산해서 학습합니다.
  • 실시간으로 업데이트되는 비디오 컨텐츠들을 바로바로 추천할 수 있도록 추천 모델을 자주 업데이트해줘야 합니다.
• Fast Inference: 실서비스에서 사용자에게 추천 목록을 제공할 때 latency가 낮아야 합니다.

이 중에서 Distributed Training의 경우 필자가 지금 글을 쓰고 있는 2019년 중반 시점에서는 엔지니어링적으로 해결할 수 있는 방법이 많이 나와있습니다. Spark MLLib의 ALS 패키지를 쓰거나, Tensorflow/PyTorch로 직접 모델을 구현한 후에 각 라이브러리의 분산 트레이닝 기능을 쓰면 됩니다. Yahoo에서 공개한 TensorflowOnSpark나 Uber의 Horovod를 이용한 Spark + Tensorflow/Pytorch 조합이나,  Kubernetes를 이용한 조합도 가능합니다.(분산 트레이닝에 관해서는 기회가 되면 다른 포스트에서 다뤄보도록 하겠습니다)

하지만 Inference 속도 자체를 향상시키는 문제는 좀 더 고민이 필요합니다. 가장 기본적인 matrix factorization 알고리즘을 쓴다 하더라도 랭킹 과정에서 수백/수천만개의 item latent vector들과 user latent vector의 inner product를 매번 계산해야 되기 때문이죠. 유튜브에 접속했는데 추천 목록이 뜨기까지 5초가 걸린다고 상상해겠습니다. 콘텐츠가 아무리 좋다 한들, 유튜브에 그대로 머무르는 유저들이 과연 얼마나 될까요?

더군다나 Distributed Training을 한다고 쳐도, 유튜브의 경우 특정 컨텐츠가 순식간에 떴다가(go viral) 사라지는 식의 높은 컨텐츠 회전율이 문제가 됩니다. 이런 경우 추천 모델을 굉장히 자주 업데이트해줘야 하기 때문에 기본적으로 시스템의 scalability가 굉장히 좋아야 하는 문제가 있죠. 더군다나 추천 모델이 Neural Network 처럼 무거운 편이라면...

이런 문제들을 풀기 위해서는 알고리즘과 시스템적인 측면에서 모두 고민이 필요합니다. 이번 시리즈에서는 유튜브에서 내놓은 논문 2개를 리뷰하면서 유튜브에서 이런 문제를 어떻게 다루고 있는지를 살펴보겠습니다.

• The Youtube Video Recommendation System(RecSys 2010)
• Deep Neural Networks for Youtube Recommendations(RecSys 2016)

The Youtube Video Recommendation System(RecSys 2010)

1. 시스템의 지향점

논문에 따르면, 사용자들이 유투브에 들어오는 이유는 크게 3가지라고 합니다.

• 직접 탐색(Direct navigation): 다른 곳에서 찾은 영상을 유투브에서 보는 경우입니다. 다른 사이트에서 유투브의 영상을 링크하는 경우를 말하는 것으로 보입니다.
• 검색(Search): 자기가 찾는 검색 의도와 관련된 영상들을 찾는 경우입니다. "XX하는 법", 혹은 "XX가 연주한 음악" 등이 해당합니다..
• 의도 없음(Unarticulated want): 그냥 재밌는 영상을 보면서 시간을 때우는 경우입니다.

이 논문에서 다루는 시스템의 목표는 특별한 의도 없이 타임킬링하려는 유저들에게 개인화된(personalized) 영상을 추천해서 유튜브에서 즐거운 시간을 보내고 계속 머무르도록 하는 것입니다. 이 목표를 달성하기 위해 구글에서 설정한 시스템 요구사항은 다음과 같습니다.

• 추천되는 비디오 목록이 주기적으로 업데이트되는 것
• 유저가 최근에 보여준 행동 기록을 참고해서 비디오를 추천해줄 것
• 사용자에게 다양한 스펙트럼의 비디오들을 추천해주는 것

그런데 위에서도 언급했지만, Youtube의 경우 다음과 같은 심각한 scalability 문제 때문에 위의 요구사항을 만족하는 시스템을 만들어내기가 그리 쉽지 않습니다.

• 비디오 숫자와 유저 숫자가 엄청나게 많고, 대부분의 영상이 10분 이내의 짧은 영상이다.
• 순간적으로 인기를 타는(go viral) 비디오들이 워낙 많아서 추천 목록을 짧은 주기로 갱신해주어야 한다.

이렇게 스팟성 컨텐츠가 많고 컨텐츠들의 업데이트가 잦은 상황에서 추천 목록을 자주 업데이트해주지 못하면, 유저들이 느끼는 서비스의 질은 하락하게 됩니다. 이 논문에서 제안된 시스템이 지향하는 바가 이런 잦은 업데이트를 지원하기 위해 랭킹의 scalability를 개선하는 것입니다. 구체적으로 어떻게 하는지는 다음 절에서 살펴보겠습니다.

2. Scalable 2-step ranking

이 논문의 핵심은 Candidate Generation → Ranking의 2-step 접근법으로 랭킹 단계에서의 computation cost를 확 줄이는 것입니다.(원래 논문의 Section 2.1~2.4에 해당) 구체적으로 어떻게 하는지를 한번 차례차례 살펴보겠습니다.

2-1. Candidate Generation

Candidate Generation 단계의 시각화

Candidate generation 단계에서는 사용자가 관심을 보였던 비디오들과 연관되어 있지 않을 것 같은 비디오들을 빠르게 쳐내서 랭킹 후보셋의 크기를 줄입니다. 이 논문에서는 전통적인 association rule mining을 이용해서 이 문제에 접근했는데, 구체적인 방법은 다음과 같습니다.

1. Seed video set 생성

• 유저가 반응을 보였던(시청, 좋아요, 플레이리스트에 추가, ...) 비디오들을 모아서 seed video set $S$ 를 만든다.

2. Seed video set의 각 비디오와 관련된 Related Videos 생성

• 특정한 기간 내에(보통 24시간) $S$ 에 포함된 각 비디오 $v_i$ 와 같은 세션에서 시청(co-watch)되었던 다른 비디오 $v_j$ 들만 쭉 뽑아서, $v_i$와의 relatedness score $r(v_i,v_j)$ 가 가장 높은 top $N$ 개의 비디오 $v_j$ 들을 비디오 $v_i$ 의 Related Videos $R_i$ 로 정의한다. (*너무 $r(v_i, v_j)$ 값이 낮은 경우는 top $N$ 에 포함되더라도 제외)
• relatedness score는 $r(v_i, v_j) = \frac{c_{ij}}{f(v_i, v_j)}$ 로 계산한다. $c_{ij}$ 는 하나의 유저 세션 내에서 $v_i$ 와 $v_j$ 가 같이 시청된 횟수이고, $f(v_i, v_j)$ 는 seed video $v_i$ 와 candidate video $v_j$ 의 global popularity를 고려해서 $c_{ij}$ 를 normalize하는 역할을 한다. 가장 간단하게는 $f(v_i, v_j) = c_i c_j$ 로 계산할 수 있다.

3. 초기 후보셋 생성
   $$C_1(S)=\cup_{v_i\in S}R_i$$

• $S$ 에 포함된 모든 비디오 $v_i$ 에 대해 $R_i$ 를 계산해서 하나의 후보셋 $C_1(S)$ 로 합친다.

4. 확장된 후보셋 생성
   $$C_n(S)=\cup_{v_i\in C_{n-1}}R_i$$

• 후보셋이 너무 좁아지지 않도록 $S$ 에서 $n$ 번의 Related Videos 연산으로 도달 가능한 모든 비디오들까지 포함해서 확장된 후보셋 $C_n(S)$ 를 만든다. $n$ 값은 생성되는 최종 후보셋의 diversity를 보고서 결정한다.

5. 최종 후보셋 생성
   $$C_{final}=\left(\cup_{i=0}^N{C_i}\right) \setminus S$$

• 유저가 이미 봤던 비디오셋 $S$ 를 최종 후보셋에서 제외한다.

2-2. Ranking

위와 같이 후보셋을 뽑아내고 나면, 일반적인 추천 시스템에서 하는 것처럼 후보셋의 비디오들에 대해서 랭킹 알고리즘을 적용합니다. 구체적인 랭킹 알고리즘이 공개되지는 않았지만, 논문을 쓸 당시에 유투브에서 랭킹에 반영하는 요소는 다음 3가지였다고 합니다.

1. Video quality: 유저에 상관없이 비디오의 절대적인 품질을 측정하는 점수. 비디오의 총 시청 횟수나 rating, 혹은 공유된 횟수 등이 해당한다.
2. User specificity: 유저 활동 로그를 기반으로 개인화된 추천 점수. 후보셋 생성 단계의 seed set S를 사용해서 추출한다.
3. Diversification: 같은 채널이나 비슷한 비디오가 너무 많이 추천되지 않게 후보 셋을 조정한다.

기본적으로는 Video quality와 User specificity feature들의 linear combination으로 비디오들의 랭킹 점수를 매겨서 추천 리스트를 생성한 뒤에, 생성된 리스트를 post-processing해서 diversity를 일부 조정하는 방식을 썼다고 하네요.

3. 엔지니어링

엔지니어링적인 측면은 논문에 간략하게만 언급되었지만, 실제로 서비스할때 중요할 것 같은 내용을 꽤 많이 담고 있습니다.

• 추천셋 업데이트 방식
  • Batch 방식: 유저별 추천 리스트를 미리 계산해뒀다가 실제 서비스할 때는 유저별로 저장해둔 리스트를 바로 불러와서 서빙한다.
  • 잦은 업데이트: 하루에도 몇번씩 업데이트를 해준다.
• 유저별 로그 저장 방식
  • 유저 단위로 구글의 분산 NoSQL DB인 Bigtable에 저장한다. (*Bigtable의 오픈소스 버전이 HBase이다)
  • 유저 ID를 primary key로 해서 유저 활동 기록을 계속 업데이트/저장해나가는 듯 하다.
• 유저별 추천셋 저장 방식
  • Read-only 스타일로 단순화된 Bigtable 서버에 저장한다고 한다. Random access를 통해 low latency 확보에 유리한 Bigtable의  장점을 살린 것 같다.

4. 성능 평가

이렇게 개인화 추천 시스템을 만든 후에는 시스템 성능을 평가해야겠죠? 구글에서는 과거 데이터에 시스템을 맞춰보는 데서 끝내지 않고, 실제 Youtube 서비스에 논문에서 언급한 시스템을 일정 기간동안 테스트해본 후에 다음의 measure들을 측정했다고 합니다.

• CTR(Click Through Rate): 사용자가 추천된 컨텐츠를 클릭한 비율
• Long CTR: 사용자가 추천된 컨텐츠를 장시간 시청한 비율
• 개별 유저 세션 길이
• 유저가 접속한 후 첫번째 장시간 시청을 시작하기까지의 소요 시간
• 추천 coverage: 개인화된 추천셋을 실제로 받아보게 되는 유저 수. 아마 candidate generation 단계에서의 $n$ 값을 설정하기 위해 보는 것 같다.

하지만 measure값들이 너무 많다고 생각했는지, 실제로 논문에서는 3주간 측정한 평균 CTR 값만 보고하였습니다.(아니면 어른의 사정이 있었을 수도^^;;)

단순히 인기도 기반으로 추천하던 기존 추천 방식들에 비해 CTR이 무려 2배가 높은 것을 볼 수가 있습다. 그야말로 경이로운 수준이네요. 유튜브 레전드의 시작

5. 분석

제가 생각하기에 이런 2단계 시스템의 가장 큰 장점은 랭킹과 후보 생성 기능이 완전히 분리되어 있어서 모듈 단위로 관리가 가능하다는 것입니다. 사실 자동화라는 측면에서는 이런 구조가 end-to-end 시스템에 비해 불리할 수 있지만, 유튜브 정도 되는 대규모 시스템에서는 시스템 관리자가 모듈 단위로 손쉽게 테스팅과 디버깅이 가능한 구조가 더 매력적이 될 수 있죠.

그래서인지 후속 논문인 Deep Neural Networks for Youtube Recommendations(RecSys 2016)를 보면, 랭킹과 후보 생성 기능을 분리한 2단계 구조를 그대로 유지하고 있는 걸 볼 수가 있습니다. 해당 후속 논문에 대해서는 Part 2에서 다루도록 하겠습니다.