유튜브 추천시스템 논문 리뷰 Part 2 - Deep Neural Networks for YouTube Recommendations (RecSys 2016)

유튜브 추천시스템 논문 리뷰 Part 1에서는 전통적인 데이터 마이닝을 기반으로 만들어진 2010년 버전의 유튜브 추천시스템을 소개했었습니다. 디버깅이 용이하고 알고리즘 구성도 간단해서 실무적으로 유용할 것 같은 시스템이었죠.

하지만 2010년대 들어서 딥러닝(Deep Learning)이 본격적으로 주목받게 되면서, 유튜브 추천시스템도 딥러닝 기반으로 전환하게 되었습니다. 오늘 리뷰할 논문은 2016년에 RecSys에 제출된 Deep Neural Networks for YouTube Recommendations라는 논문인데, 구글에서 딥러닝을 사용해서 어떻게 유튜브 추천시스템을 구성했는지를 담고 있습니다.

System Overview

[그림 1] 유튜브 추천시스템의 전체적인 구성

이 논문에서 소개하는 딥러닝 기반 추천시스템도 기본 구조는 이전에 Part 1에서 소개되었던 candidate generation -> ranking의 2단계 구조를 따릅니다. Part 1을 안보신 분들을 위해 간략하게 설명드리자면, candidate generation은 유저의 유튜브 활동 정보(이전에 시청했던 영상들의 ID, 검색 기록, 성별/연령/지역 등)를 collaborative filtering으로 분석해서 엄청나게 많은 유튜브 영상들 중에서 해당 유저가 좋아할 것 같은 영상들만 high-precision으로, 대략적으로만 선별해내는 작업을 말합니다. ranking 단계에서는 candidate generation 단계에서 대충 좁혀놓은 비디오들과 유저의 정보들을 좀 더 자세히 들여다보면서 유저의 선호도 점수를 추정하고 선호도 순으로 추천을 하게 되구요.

candidate generation 단계를 따로 두는 이유는 ranking의 scalability를 개선하기 위해서입니다. ranking에 사용될 후보 영상들의 개수를 확 줄이지 않으면, 유튜브 정도로 추천 가능한 상품(영상)들이 많은 시스템에서는 계산량이 감당이 안될테니까요. High-precision을 추구하는 이유는 유저들이 자기가 좋아하는 영상을 몇개 빠뜨리는 것에는 관대하지만, 싫어하는 걸 추천하는 것에는 민감하게 반응하기 때문이구요.

그 외에도 candidate generation -> ranking의 2단계 구조는 아래와 같은 장점이 있습니다.
  • Candidate generation / Ranking 각 단계별로 시스템을 분해해서 디버깅하기 좋다. (*Part 1의 내용)
  • 다른 candidate generation 알고리즘(예: Part 1에서 소개한 기존 유튜브 추천 시스템)에서 생성된 후보 비디오셋들을 손쉽게 합칠 수 있다. ([그림 1]에서 other candidate sources라고 써있는 부분)

Candidate Generation

이번 절부터는 candidate generation과 ranking을 어떻게 딥러닝으로 구현했는지를 구체적으로 살펴보겠습니다. 먼저 candidate generation 단계에서는 이전 버전과 유사하게 ranking에 쓸 후보 비디오 숫자를 수백개 수준으로 좁혀서 scalability를 확보합니다. 그런데 여기서 흥미로운 부분은 candidate generation 문제를 특정 시점에 유저가 시청할 것 같은 하나의 영상을 맞추는 extreme multiclass classification 문제로 formulate했다는 점입니다. 구체적으로는 아래와 같습니다.
$$
P(w_t=i|U,C)=\frac{e^{v_i^T u}}{\sum_{j\in V}{e^{v_j^T u}}}
$$
여기서 $u$는 유저 정보 $U$와 컨텍스트 정보 $C$를 조합해서 만든 유저 임베딩이고, $i$는 비디오 ID를, $v_i, v_j$는 비디오 임베딩을 나타냅니다. $w_t=i$ 는 비디오 $i$가 시간 $t$에 시청되었다는 것을 나타내는데, 유저가 비디오를 전부 시청했으면 유저가 positive implicit feedback을 준 것으로 간주합니다. 즉, 유저 정보와 컨텍스트 정보를 input으로 하고 유저의 watch 여부를 label로 해서 $P(w_t=i|U,C)$가 최대값이 되는 $i$를 알아내는 multi-class classification 문제가 되는 것입니다.

Model Training

candidate generation을 이렇게 classification 문제로 formulate했을 때의 장점은 기존에 word2vec이나 machine translation 등의 application에서 extreme multiclass classification 문제를 풀기 위해 사용되었던 negative sampling 테크닉을 모델 학습 시에 사용해서 학습 속도를 획기적으로 개선할 수 있다는 점입니다.(여기서는 "candidate sampling"이라 표현) 논문에 따르면 수천개의 negative class들을 뽑은 뒤에  Large-scale NMT에서 사용했던 접근법을 모방해서 importance weighting으로 보정을 한다고 하는데, 보정을 구체적으로 어떻게 했는지는 언급되지 않아 아쉬운 부분이 있습니다. 사실 RecSys 2016에서 논문 발표하는 비디오(8:23~8:54)를 보면, negative class를 충분히 많이 뽑으면 보정은 안해도 크게 상관없다고 하네요.

Model Serving

서비스할 때는 유튜브에 올라와있는 수많은 비디오 중에서 top K개만 수십 ms 안에 뽑아내야 되는 시간 제약이 걸리기 때문에, 정확도를 좀 희생하고 적당한 솔루션을 빠르게 뽑아내는 접근법을 사용합니다. Multiclass classification 문제로 formulate한 것이 여기서 다시 한번 장점을 발휘하는데, Multiclass classification에서 top K개의 클래스를 뽑아내는 문제는 output vector space상에서 k-nearest neighbor search를 하는 것과 문제와 동일하기 때문입니다. 따라서 적당히 좋은 top K개의 후보를 빠르게 뽑아내고 싶으면 그냥 output space에 approximate k-nearest neighbor search 알고리즘을 돌리면 끝입니다. 유튜브에서는 여러 버전의 approximate kNN search 알고리즘들을 구현해서 A/B testing해보았는데, 어느 버전을 사용하든 사용자들이 체감할만한 차이는 없었다고 합니다.

Model Architecture

[그림 2] 딥러닝을 이용한 Candidate generation network

1. Input Structure

각 유저들은 1) 시청했던 비디오 목록, 그리고 2) 검색했던 키워드, 3) Demographic feature (나이, 성별, 나이, 위치, 사용 기기, 로그인 상태...)를 통해서 위와 같이 fixed-length vector로 embedding됩니다. 시청했던 비디오들은 위 그림과 같이 각 비디오들의 embedding을 averaging해서 watch vector로 aggregate되고, search token들도 unigram/bigram 단위로 각각 embedding된 후에 search vector라는 fixed-length vector로 합쳐집니다.

사실 search token들을 순서를 무시하고 averaging해서 넣는데는 특별한 이유가 있습니다. 유저가 다음에 볼 비디오를 맞추라고 문제를 정의한 상황에서 search token sequence를 input으로 집어넣게 되면, 모델이 손쉽게 정답을 맞추기 위해 이전 검색어들을 싹 무시하고 마지막 검색어의 결과만 단순암기하는 상황이 발생하기 쉽기 때문입니다. 예를 들어 사용자가 "강식당"이라는 검색어를 입력한 다음 바로 검색 결과에서 강식당 동영상을 시청했다면, 모델 입장에서는 그냥 이전 검색어들을 싹 무시하고 마지막 검색어와 거기에 대응되는 검색 결과를 외워두는게 가장 합리적인 솔루션이 됩니다. 하지만 매번 새로운 동영상이 추천되기를 원하는 사용자 입장에서는 마지막에 같은 검색어를 치더라도 직전에 검색했던 키워드들의 맥락에 따라서 추천 리스트가 조금씩 달라지기를 원하겠죠. 이런 문제를 방지하기 위해 일부러 search token들의 순서를 뭉개버리는 averaging 연산을 하는 것입니다. 논문에 직접 언급되지는 않았지만, watched video를 averaging하는 것도 비슷한 이유 때문일 것 같네요.

[그림 2]를 보면 Demographic feature도 여럿 들어가는걸 볼 수 있는데, video watches와 search tokens이 얼마 없는 light user들을 모델링할때 유용합니다. 이때 input distribution을 비슷하게 맞추고 싶었는지 binary categorical feature는 0 or 1 그대로 넣고 continuous feature는 [0,1] 범위로 scaling해서 넣었다고 합니다.

또 과거의 데이터 위주로 모델이 편향되어 학습되는 경향(e.g. 최근에 viral하기 시작한 것보다 과거에 viral했던 비디오 선호)을 보정해주기 위해 Example Age라는 feature를 넣어서, 각 training example (user watch log)이 학습 시점으로부터 얼마나 오래됬는지를 모델에 명시해줍니다. testing할때는 example age=0으로 세팅하구요. 이렇게 example age를 넣어서 모델을 만들면, 아래와 같이 실제로 유저들이 시간이 지남에 따라 특정 비디오를 점점 덜 보게 되는 경향을 보다 잘 예측할 수 있었다고 합니다.(해당 비디오 URL이 논문에 첨부되었지만 현재는 삭제됨)
[그림 3] 샘플 비디오의 시청 확률에 대한 모델별 예측치 & 실제 결과
파란 선: example age 없이 예측한 watch probability.
Training 기간 전체의 평균 watch probability를 예측하려는 경향이 나타난다고 함.
빨간 선: example age를 넣어서 예측한 watch probability
초록 선: 실제 watch probability

2. (Label, Input) pair 생성

Candidate generation network를 정의했으니 이제 모델을 학습하기 위해
  1. 유저가 watch했는지 여부를 표시하는 label
  2. 그 label에 대응하는 context, 즉 candidate generation network에 넣을 input
을 준비하면 끝입니다.

먼저 watch label의 경우 유저가 유튜브에서 직접 봤든 다른 웹사이트에서 임베딩된 유튜브 비디오를 봤든 상관없이 유저의 watch 기록을 전부 끌어모읍니다. 다른 웹사이트에서의 시청 기록까지 사용하는 이유는 학습되는 모델이 현재의 유튜브 추천 시스템에 overfitting되는걸 막기 위해서입니다. 이 때 주의할 점은 사용자의 모든 watch 로그를 label로 그대로 사용하는게 아니고, 모든 사용자에게서 동일한 양의 label만 랜덤으로 샘플링해서 사용자간의 밸런스를 맞춘 상태로 모델에 넣는다는 점입니다. 이렇게 하면 training 기간 동안에 유달리 활동이 많았던 소수의 헤비 유저에게 모델이 편향되는걸 막을 수가 있죠.

[그림 4] (input, label) pair 구성 방법

다음으로는 각 watch label에 대응하는 유저 로그들을 input으로 뽑아서 training set으로 사용할 (input, label)를 최종적으로 뽑아냅니다. label은 위에서 언급했듯이 사용자별로 동일한 수의 watch label을 랜덤하게 골라내면 끝이고, input으로는 각 watch label이 발생한 시점을 기준으로 과거에 발생한 사용자 로그들을 최대 50개까지 골라서 집어넣게 됩니다.

3. 세부 네트워크 구조

신경쓸 것이 굉장히 많은 input/output 구조에 비해, 네트워크 구조는 전형적인 타워형 구조를 지니고 있어서 매우 심플합니다. 마지막 레이어는 흔히 볼 수 있는 softmax output layer로 256차원이고, 한 층씩 밑단으로 내려갈때마다 차원이 2배가 되는 구조를 지니고 있습니다. 층 개수를 늘리고 input 종류를 늘릴수록 성능이 더 좋아지는 경향을 보였다고 하네요.
[그림 5] feature와 network depth가 늘어남에 따른 성능 증가 추이


Ranking

Feature Engineering

[그림 6] Ranking network 구조

랭킹 단계에서는 candidate generation 단계에서 줄여놓은 후보 비디오들의 feature들을 훨씬 자세하게 들여다보면서 1등부터 꼴등까지 순위를 쫙 매기는 neural network를 사용합니다.([그림 6] 참조) 이 때 네트워크의 input으로 집어넣기 위해 수백개(!)에 달하는 feature들을 생성해내는 엄청난 feature engineering이 들어가구요,

programmer crunching에 대한 이미지 검색결과
※ 위 설명과 무관한 이미지입니다.
이 때 feature들은 다음과 같이 분류해서 적절한 엔지니어링을 거친뒤 모델에 입력으로 들어가게 됩니다.
  • 데이터 형태에 따른 분류
    • continuous/ordinal features
    • categorical features
      • univalent: 값을 딱 하나만 가지는 feature. 예) scoring하는 비디오의 ID
      • multivalent: 값을 여러개 가지는 feature. 예) 지금까지 봤던 비디오들의 ID 목록
  • 데이터 의미에 따른 분류
    • Query features: 유저/컨텍스트 feature들
    • Impression features: 비디오 자체에 대한 feature들

1. Categorical features

categorical feature들은 dense embedding으로 변환되어 네트워크에 input으로 들어갑니다. 가질 수 있는 값이 지나치게 많은 categorical feature들의 경우(e.g. 비디오 ID나 search query term)에는 출현한 frequency를 기준으로 top $\log{N(\text{unique_features})}$ 개 정도만 사용하고, 나머지는 Out-Of-Vocabulary 샘플로 취급하여 zero vector로 변환합니다. 값을 여러개 가질 수 있는 multivalent categorical feature들은 candidate generation에서처럼 averaging한 뒤에 집어넣구요.

2. Continuous features

연속형 값들은 quantile로 변환해서 [0, 1) 사이의 값 $\tilde{x}$ 로 매핑합니다. 모델이 복잡한 feature들간의 관계를 보다 쉽게 배울 수 있도록 $\sqrt{\tilde{x}}, \tilde{x}^2$ 도 직접 모델에 feature로 집어넣습니다.

Most important features?

모델링을 해보고 나서 성능에 가장 영향을 많이 미친건 Collaborative Filtering에 전통적으로 많이 사용되었던 정보들, 즉 impression video + similar videos와 유저 간의 interaction feature들이었다고 합니다. 예를 들어 특정 채널의 비디오들에 대한 유저 선호도가 굉장히 높았다면 해당 채널의 비슷한 비디오들을 유저가 또 볼 확률이 높다는, 추천시스템의 cliche가 여전히 성립하고 있다는 거죠.

또 유저에게 비디오가 노출된 이후로 시간이 얼마나 지났는지도 중요한 팩터였다고 합니다. 비디오가 최근에 노출되었지만 유저가 시청하지 않았다면, 해당 비디오는 유저가 선호하지 않는 비디오이므로 랭킹이 내려가야 한다는거죠. 그런데 놀랍게도 논문에 따르면 무려 초 단위로(!!) 모델이 노출 이후의 시간을 체크하면서 추천을 바꾸고 있다고 합니다. 실제로 글을 쓰는 2019년 9월 기준으로 유튜브에 접속해서 새로고침을 한번만 눌러보시면, 몇초 지나지 않았는데도 컨텐츠 순위가 일부 바뀌는 걸 보실수가 있습니다. 어떻게 이런 latency로 서빙을 하고 있는건지는 아쉽게도 논문에 공개되지 않았네요 ㅠㅠ 너무 궁금한데;;
[그림 7-1] 유튜브 접속 직후 추천된 컨텐츠

[그림 7-2] 13초 후에 새로고침을 눌렀을때 추천된 컨텐츠


Fighting abusing with watch-time-weighted cross entropy loss

feature engineering으로 생성된 feature들은 [그림 6]의 ranking network를 통과한 뒤에 주어진 impression video가 실제로 시청될 확률 $P(watch)\in[0,1]$로 매핑됩니다. 특정 상품의 시청 여부(yes/no)만을 알아맞히는 전통적인 CTR prediction 구조죠.

이 때 특이한 점이 하나 있는데, loss function을 단순하게 binary cross-entropy loss로 가져가는 대신 비디오들에 각각의 watch time으로 가중치를 준 weighted cross-entropy loss를 사용한다는 것입니다. 보통은 imbalanced dataset 문제를 해결하기 위해 주로 사용되는 weighted cross-entropy loss를 여기서 사용하는 이유는 Youtube 플랫폼에 낚시성/광고성 콘텐츠를 업로드하는 소위 어뷰징(abusing) 행위들을 걸러내기 위해서입니다. RecSys에서의 논문발표 16:55 ~ 18:06를 보면, CTR 기준으로 optimize하면 유저 클릭만 유도하고 알맹이는 없는 clickbait(낚시성 비디오)가 많이 걸리고, 그렇다고 watch time이 긴 녀석들만 기준으로 optimize하면 지나치게 긴 video들만 추천되어 밸런스를 잘 맞춰줘야 한다는 언급이 있습니다. 즉, 유저가 오래 본 비디오일수록 유저가 더 좋아하는 비디오라고 생각해서 학습시에 이런 비디오들을 상대적으로 더 많이 추천하도록 조정하는 거죠.

※ 논문 4.3절에 보면 이런 방식으로 Expected Watch Time을 모델링할 수 있다고 하는데, reference나 설명도 부족하고 논리에 납득이 안가는 부분이 많습니다. RecSys에서의 논문 발표 영상에서도 해당 부분이 생략된 걸 보면 중요도도 떨어지는 내용인듯 싶으니 무시하셔도 좋을 듯 싶습니다.

결론

전반적으로 논문을 살펴보면, 딥러닝 논문이기는 한데 feature engineering이 차지하는 비중이 굉장히 높다는 걸 아실 수가 있습니다. 아무리 구글이라고 하더라도 딥러닝을 production level까지 끌어올리려면 엔지니어들의 노력수명이 필요하다는 거죠. 특히 example age나 watch-time-weighted cross entropy loss처럼 도메인 지식이 들어간 tweak들을 보면, 추천 엔지니어들이 고객들과 시스템에 대해서 정말 고민을 많이 해야겠다는 생각이 드네요.

Comments

  1. candidate generation 에서 k nearest neighbor 을 돌린다고 하는데, user vector u 와 가장 가까운 video vector v를 k 개 찾는건가요??

    ReplyDelete
  2. 잘 정리해놓으신 글 잘 읽었습니다! :)

    ReplyDelete

Post a Comment

Popular posts from this blog

맥락 기반(Context-aware) 추천 시스템은 어떻게 만드는가?

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