[Recommender System] - 결과 정렬에서의 Shuffle 알고리즘

 

 

 

본 포스팅은 필자가 쓴 DeliveryHero Korea 기술 블로그(링크)에 있는 추천 시스템의 Shuffle 알고리즘 활용법에 관한 내용을 발췌한 것이다. 회사 기술 블로그에 글을 쓰면서 흥미 위주의 글을 쓰게 되었는데, 여기에 조금 더 내용적인 살을 붙여 글을 재구성하였다. 당연히 비즈니스와 관련이 없는 선에서 세간에 알려진 알고리즘 내용만을 서술하였다.

 

 

---

 

 

1. Spotify의 Music Shuffle 알고리즘

 

 

추천시스템, 그중에서도 콘텐츠 Shuffle이 필요한 영역에서 가장 대표적인 예시는 Spotify의 Shuffle 알고리즘이다.

 

Music Shuffle 에서는 컨텐츠를 완전한 랜덤으로 추천하지 않는다. 하지만 흔히 알고있기로, 사용자들은 음악 앱에서 셔플 기능을 사용할 때 동작하는 방식을 완전한 랜덤으로 인식하고 있다. Shuffle 추천은 어떻게 이루어지는 것일까? 이와 관련해 Mattias Petter Johansson 이라는 spotify의 개발자는 이런 글을 올린 적이 있다.

“The problem is that to humans, truly random does not feel random”.

 

이는 소위 말하는 도박사의 오류 문제로 비유될 수 있다.

도박사의 오류(賭博師─誤謬)는 서로 독립적으로 일어나는 확률적 사건이 서로 확률에 영향을 미친다는 착각에서 기인한 논리적 오류로, 도박사들이 성격의 특성상 앞에서 일어난 사건과 그 뒤에 일어날 사건이 서로 독립되어 있다는 확률 이론의 가정을 받아들이지 않기 때문에 ‘도박사의 오류’라고 한다

 

하나의 상황을 가정해보자, 만약 어떤 유저가 멜론 앱의 셔플 기능을 통해 음악감상을 하고 있다. 첫 번째는 아이유의 <라일락>이 나왔고, 두 번 째 음악으로는 아이유의 <팔레트>가 재생되었다. 정말 순수하게 랜덤한 셔플 기능을 제공했다면, 얼마든지 일어날 수 있는 상황이지만 유저가 느끼기엔 비슷한 노래가 연속으로 재생되었기 때문에 랜덤한 셔플 기능이라는 생각이 들지 않을 것이다. 바로 이러한 상황을 도박사의 오류 문제, 그리고 추천시스템에서의 Shuffle 문제라고 할 수 있다.

 

그렇다면 Spotify는 이 문제를 어떻게 해결하려고 했을까? (자세한 내용은 Spotify의 블로그를 읽는 것을 추천하며, 본 포스팅에서는 아이디어만 요약하였다) 이러한 문제를 인식하기 이전에는 Fisher-Yates Shuffle 이라는 완전한 랜덤 알고리즘을 사용했다고 한다. 하지만 이러한 도박사의 오류 문제를 인식한 뒤로, 몇 가지 아이디어를 추가한 것으로 보인다.

 

 

 

 

 

2. Floyd–Steinberg dithering

 

 

메인 아이디어는 디더링 알고리즘에서 고안했다고 한다. 본문에서 언급한 알고리즘은 Floyd–Steinberg dithering 알고리즘인데, 위키피디아나 여러 블로그에 좋은 내용이 잘 정리되어있지만, 아래의 이미지를 보는 것이 가장 직관적으로 이해하기 좋다.

 

 

이와 같이 디더링이라는 것은 픽셀정보를 간략화 할 때 생겨나는 뭉탱이 흩뿌리기(?), 멋진 말로는 양자화 오류를 풀어주는 알고리즘이라고 보면 된다. 그리고 Floyd–Steinberg 알고리즘은 아래와 같은 Filter Map으로 픽셀을 Convolution 하면서 해당 픽셀의 양자화 오류를 주위 픽셀로 퍼뜨려주는 식으로 동작한다. 

 

 

알고리즘의 수도코드는 다음과 같다. (위키피디아 발췌)

for each y
   for each x
      oldpixel := pixel[x][y]
      newpixel := find_closest_palette_color(oldpixel)
      pixel[x][y] := newpixel
      quant_error := oldpixel - newpixel
      pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
      pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
      pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
      pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

 

그리고 Spotify의 원문에서는 이 알고리즘을 설명하면서, 픽셀을 순수한 Random Shuffle로 처리했을 때와 디더링을 적용했을 때의 픽셀 분포를 비교하는 예를 든다.

 

왼쪽이 Random Shuffle, 오른쪽이 디더링 적용

 

그리고 이 알고리즘을 통해 아래의 그림과 같이 Music Shuffle 수행을 완성했다고 한다.

 

 

 

 

 

 

3. The art of shuffling music

 

 

원문에서는 메인 알고리즘인 Floyd–Steinberg dithering 이외에도 한 가지를 더 언급하였는데, 바로 The art of shuffling music 이라는 제목을 가진 블로그 글이다. 다만 이 알고리즘은 예외적인 케이스를 처리하는 것에 약점이 있으며, 속도 또한 그리 빠르지 않다는 단점을 가지고 있어 Spotify 에서는 아이디어만을 차용하고, 알고리즘을 적극 사용하지는 않았다고 한다.

 

필자가 서두에 언급한 테크 블로그의 글에서는 이 알고리즘을 조금 더 중점적으로 설명하였는데, 이는 디더링 알고리즘보다는 이 블로그 글의 알고리즘이 조금 더 도메인 특징, 컨텐츠 특징이나 자료구조에 잘 맞았기 때문이다(실제 서비스도 후자의 알고리즘에 더 가깝다). 

 

여하간에 이 알고리즘의 아이디어만을 간단하게 설명하자면 다음과 같다.

 

 

1) 셔플 대상인 아이템을 카테고리로 분류하여 Logical Block을 형성 (Music 컨텐츠의 경우, 카테고리는 아티스트나 앨범이 될 수 있음)

2) 가장 많은 카테고리의 수만큼 빈 공간을 포함한 리스트 생성

3) 같은 색깔의 블록끼리 Shuffle!

4) 블록의 세로 영역을 기준으로 정렬

 

5) 경우에 따라 추가적인 디더링 및 스코어링 로직 적용 (with 알고리즘의 복잡도 개선)