Summary

2010년에 나온 유튜브의 첫 추천 알고리즘 관련 논문으로, 비디오별로 candidates을 생성하고 그것에 따라 ranking을 부여하며 이를 기반으로 추천을 진행한다.
비디오별 $v_i$와 다른 비디오 $v_j$ 간의 relatedness을 계산하는데 두 비디오가 같이 방문(co-visitation)되는 횟수에 따라 계산된다. 계산된 relatedness인 $r(v_i, v_j)$에 따라 상위 N개의 비디오 세트를 seed video $R_i$라고 정의한다.
$R_i$을 사용하여 candidates을 생성한다. 이때, 사용자에게 novelty을 주도록 구성한다.
비디오의 다양한 signals에 따라 비디오를 랭킹하고 정해진 갯수를 유저에게 추천한다.

Motivation

유튜브 추천 시스템을 소개하는 논문으로 딱히 어떤 방법을 개선한다는 등의 motivation은 없다.

Approach

시스템 디자인이나 입력 데이터보다는 추천을 어떤 식으로 진행했는지에 집중하여 논문을 살펴보자.

Video Relatedness

어떤 비디오 $v_i$가 주어졌을 때, 그 비디오를 시청한 유저가 다음에 시청할만한, 유사한 비디오를 정의해야한다. 이를 위해 유튜브에서는 association rule mining, 또는 co-visitation counts을 사용한다.

일정 기간 (주로 24시간) 비디오 $(v_i, v_j)$가 함께 시청되는 횟수를 $c_ij$라 하고 비디오 $v_i$을 기반으로 하는 다른 비디오 $v_j$에 대한 relatedness score는 아래와 같이 정의된다.

$f(v_i, v_j)$는 normalization function인데 일종의 global populairty 개념이다.
dot product인 $c_i \cdot c_j$가 사용되는데 다른 함수도 많이 있다.

Make related videos set

seed video인 $v_i$의 related videos의 세트 $R_i$은 $r(v_i, v_j)$가 가장 큰 상위 N개의 비디오로 구성한다.
이때, 비디오별로 최소 시청 기록의 제한을 둔다.
related videos는 비디오간에 directed graph을 만드는 것으로 볼 수 있다.
- 비디오 페어인 $(v_i,v_j)$는 iff $v_j \in R_i$라면, $v_i$에서 $v_j$로 가는 edge $e_{ij}$가 있다고 해석할 수 있다.
- 이때 weight는 $r(v_i, v_j)$이다.

Generating recommendation candidates

유저의 웹상 활동을 바탕으로 seed set을 구성한다. 이때 유저가 좋아요를 누르거나 별점을 평가하거나 플레이리스트에 추가한 비디오를 포함한다. 유저가 관심을 보인 비디오인 seet set $S$에 대해 candidate recommendations을 생성하기 위해 related videos의 edge을 이용한다. seed sets에 포함된 비디오인 $v_i$의 related video sets을 $R_i$라고 할 때, 이를 모두 모은 것을 아래와 같이 정의하자.

만약, 어떤 유저가 백종원이 카레를 만드는 영상 a에 좋아요를 누르고 일본 카레 맛집을 리뷰한 영상 b에 댓글을 남겼다. 그러면 영상 a, b와 related videos로 묶이는 영상들을 모두 모은 것이 $C_1(S)$이다.

논문에서는 $C_1(S)$로는 novelty을 주는 추천을 하기 힘들다고 한다. 그도 그럴 것이, 위 예시에서 계속 카레 관련된 영상만 추천될 것이기 때문이다. 추천의 범위를 넓히기 위해 related videos graph을 사용한다.

$C_n$을 seed set에 있는 어떤 비디오로부터 n의 거리로 갈 수 있는 비디오의 집합이라고 하자.

위 식은 $R_i$을 가져오는데 $C_{n-1}$을 사용하지만 recursive하게 생각해보면, 결국 n의 거리로 갈 수 있는 비디오의 집합임을 알 수 있다. 이를 이용한 최종 후보군은 아래와 같이 추출한다.

어떤 seed set에서 0의 거리로 갈 수 있는 비디오 집합, 1의 거리로 갈 수 있는 비디오 집합, ..., N의 거리로 갈 수 있는 비디오 집합을 모두 합한 것에서 seed set은 제외한다. 이미 유저가 반응한 비디오는 제외해야하기 때문이다. 결국 N에 따라서 얼마나 멀리 있는 비디오까지 branching factor을 넓힐지가 결정되는데, 논문에서는 작은 N으로도 다양한 종류의 비디오를 추천할 수 있다고 한다. 사실, 그도 그럴 것이 N에 따라서 몇다리를 건너서 연관되는 비디오가 추천될지 결정되는데 N=3이라고만 해도 건너 건너 건너 연관된 비디오가 추천되니.. 유저에게 novelty을 주는 비디오가 추천될 것 같다는 느낌이 들었다. 다만, 이 추천이 좋은 추천인지는 실험해봐야한다..

Ranking

후보 비디오를 생성하고 나서 다양한 signals을 사용하여 비디오의 랭킹을 매긴다.

video quality signals: 유저와 상관없이 비디오의 품질로 결정한다. 예를 들어, 비디오가 얼마나 시청됐는지, 평점을 몇점인지 등을 포함한다.
user specificity signals: 유저의 개별적인 취향이나 선호를 반영한다.
이 둘을 선형 결합하여 후보 비디오에서 랭킹 리스트를 생성한다. 정확히 어떻게 선형결합하는지는 안 나와 있다.

Results

논문에서 제안한 모델과 a) most viewed: 하루에 가장 많이 시청된 비디오 b) top favorited: 가장 많이 유저의 favorites에 추가된 비디오 c) top rated: 하루에 가장 많은 좋아요를 받은 비디오로 추천된 결과와 비교해본다.

유튜브의 추천 알고리즘이 가장 높은 CTR을 기록함을 확인할 수 있다.

Conclusion

유튜브에서 처음 발표한 추천 논문을 살펴보았다.
추천 후보군을 생성하는 부분에 novelty을 주기 위한 생각이 들어가 있어서 흥미로웠다. N에 따른 실험 결과도 같이 리포트 했으면 좋지 않았을까 싶다.
가장 중요한 ranking 관련된 부분이 좀 날림으로 쓰여졌다.. 그래서 signals을 어떻게 처리해서 선형 결합을 어떻게 하는지가 명확하게 나와있지 않아서 아쉽다.

[Recommender System / Paper review] #20 The YouTube Video Recommendation System