Innovating Faster on Personalization Algorithms at Netflix Using Interleaving 에 관한 정리

이번 포스팅은 2017년 11월 30일 Juliette Aurisset, Michael Ramm, Joshua Parks이 작성한 Innovating Faster on Personalization Algorithms at Netflix Using Interleaving 에 관한 내용을 정리한것입니다.

Fig. 1 : An example of a personalized Netflix hompage

넷플릭스에서는 목적에따라 다양한 알고리즘을 사용하고있습니다.

Fig. 1에서 첫번째 row인 top pick은 joshua에 맞춤설정된 추천알고리즘을 사용하였고, 두번째 row는 trending now로 최근 인기트렌드인 아이템들을 보여주는 알고리즘을 사용합니다. 이러한 다양한 알고리즘들은 1억명이 넘는 회원들에게 각 개인에 맞춤화된 홈페이지를 구성해주기위해 사용됩니다.

Faster algorithm innovation with interleaving

추천시스템이 중요한 이유는 사용자가 아이템(=Netflix 사에서는 Contents)을 추천받아 시청을 하였는데 별로이거나, 추천 리스트가 마음에 들지 않는 경우 더이상 Netflix를 찾지 않을 수도 있기 때문입니다. 따라서 Netflix에서는 알고리즘을 지속적으로 향상시켜 각 사용자에게 더 적합한 추천을 해주기 위한 노력을 하고 있습니다.

일반적으로 새로운 랭킹알고리즘을 만들고, Off-line test로 자사 내부의 데이터로 성능을 평가한 다음에 A/B test를 활용해 회원만족도를 극대화하기위해 On-line test를 시행합니다.

Fig. 2(a) : Tranditional A/B Test

On-line test에서는 최적화를 위해 여러가지 알고리즘으로 A/B test를 시행합니다. 이 때, 신속하게 test를 해야하는데 Fig. 2(a)에서보면 Sampling하는 기간, 샘플링한 대상들에게 테스트하는 기간과 같이 최적의 알고리즘을 찾기 위해서 시간과 비용이 많이 소요됩니다.

Fig. 2(b) : Proposed Two Stage Experimental Process

그렇기 때문에 속도를 가속화시키기 위해서 고안되어진 방법이 Fig. 2(b)에 나타난 Two Stage Online Experimental Process입니다.

새롭게 고안된 방식은 아래와 같은 두가지 속성을 만족시켜야합니다.

• 샘플의 사이즈를 감소시켜야 한다.
• 전통적인 A/B Test를 거쳐서 나온 최적의 알고리즘과 Interleaving 방식을 거쳐서 나온 최적의 알고리즘이 동일해야한다.

Interleaving at Netflix

Interleaving 방식이 무엇인지 알아보기위해 A/B Test와 Interleaving 방식에 좀 더 자세히 설명하면

Fig. 3 : A/B Testing vs. Interleaving

A/B Test는 모집단을 두개의 그룹으로 나누어서 하나의 집단은 A 알고리즘에 노출시키고, 다른 하나의 집단은 B 알고리즘을 사용합니다. 이때의 평가 방식은 월단위 구독유지(Retention)와 스트리밍 시간(Streaming)으로 어느 알고리즘이 더 좋은지 두 그룹을 비교합니다.

Interleaving 방식은 한 그룹의 멤버들에게 A와 B가 섞인 알고리즘을 사용해서 A와 B의 알고리즘의 비디오 시청시간 점유율(User Preferences)을 비교하여 사용자 선호도를 측정합니다.

그런데, Netflix에서는 사용자에게 추천해주는 list를 사용자가 가장 좋아할 것 같은 item을 왼쪽에서부터 노출시키기 때문에 사용자가 비디오를 재생하는 확률이 왼쪽에서 오른쪽으로 갈수록 줄어듭니다. 따라서 Interleaving 방식을 사용할 때 편향을 고려해야 합니다. 이때 사용되는 방식이 스포츠에서 많이 사용하는 Team draft 방식을 사용합니다. Team draft 방식을 사용하여 아래 Fig. 4(a)처럼 A와 B의 각각의 비디오 세트 리스트를 만듭니다. 그런 다음 Fig. 4(b)와같이 A 알고리즘을 먼저 적용할건지 B 알고리즘을 먼저 적용할 것인지는 동전던지기처럼 랜덤으로 정합니다.

Fig. 4(a) : interleaving videos from two ranking algorithms using team draft

Fig. 4(b) : interleaving videos from two ranking algorithms using team draft

Comparing the sensitivity of interleaving to traditional A/B testing

A/B Test와 새롭게 제안된 Two Stage Online Experimental Process의 Interleaving 방식을 비교하기 위해서 이 단계에서는 작은 샘플 크기로 더 우수한 알고리즘을 식별해야 하는데 평가하기 위해 이를 상대적 품질문제로 변경해서 평가합니다.

Fig. 5 : Sensitivity of interleaving vs. tranditional A/B metrics for two rankers of known relative quality

A/B Test와 Interleaving을 비교하기 위해서 Bootstrap Subsampling을 사용해다양한 샘플크기로 적용시켰더니 Fig. 5 와 같은 분석결과가 나옵니다. x 축을 샘플의 크기, y 축을 진짜 선호도에 불일치하는 확률이라고 했을때, A 알고리즘과 B 알고리즘 중 어떤 알고리즘이 좋은지 찍어도 50%의 확률값을 갖기때문에 Random guessing 이 50%가 나오는데, 찍은것 보다는 좋아야하고 Netflix사에서 진짜 선호도에 일치하는 정도가 95%정도는 되야된다고 한다면 불일치하는 정도는 5%인데 이때의 Interleaving 일때의 샘플크기는 10^3 이고, A/B Test의 평가지표인 Algo Engagement 경우는 10^5로 Interleaving 방식이 A/B Test 에비해 100배 이상의 적은 샘플을 사용할 수 있다는 것을 볼 수 있습니다.

Correlation of interleaving metrics with A/B metrics

A/B Test를 거쳐서 나온 최적의 알고리즘과 Two Stage Online Experimental Process를 거쳐서 나온 최적의 알고리즘이 일치해야 새롭게 고안한 Test 방식이 의미가있는데, 이를 보기위해 A/B Test 와 Interleaving을 상관분석을 해보면 Fig. 6 과같이 나타납니다.

Fig. 6 : Correlation of the interleaving measurement with the most sensitive A/B metric

A/B Test와 Interleaving 의 상관계수는 0.969로나타나는데 강한 상관관계의 모습을 보여줍니다.

Conclusion

Interleaving은 알고리즘의 혁신 속도를 높일 수 있는 강력한 기술이지만, 한계가 존재하는데 Interleaving framework를 구현하는 것이 어렵다는 엔지니어링 측면의 문제점과 랭킹 알고리즘에 대한 비디오 시청시간 점유율과 같은 사용자 선호도(User preference)의 상대적인 측정값이라는 제한이 있다는 점에서 Retention와 같은 직접적인 측정은 불가능하다는 점이 있습니다.