네트워크 이론 – 인스타그램의 알고리즘
Criteo라는 리타게팅 광고회사 (유저별 행동에 맞춰 쇼핑몰 노출 상품을 골라주는 광고 상품)에서 Senior Data Scientist로 재직하던 시절, 외부 접촉이 있을 때마다 항상 위에서 “절대로 회사 알고리즘을 상세하게 공개하면 안 된다”는 경고를 받았다. 굳이 공개해야할 때는 Top-line info만 공개해라고 여러번 주의를 들었는데, 회사 그만둔지 1년이 지난 요즘도 여전히 그 모델을 제대로 따라가는 경쟁자가 별로 없는 것과, 모델을 보면서 느꼈던 내공의 깊이(?)를 봤을 때 top line 보다 더 공개해줘도 경쟁자들이 따라가기 쉽지 않을 것 같다(고 생각했었다).
회사 재직 중에 Google의 리마케팅 (매우 유사한 서비스)과 가끔 Head-to-head (H2H)로 맞상대한 적이 있었는데, 적어도 내 기억에는 한번도 H2H에서 져 본적이 없다. H2H는 글로벌 전체에 10명도 안 되는 Data Scientist들끼리 항상 예의주시하며 모니터링했던 업무였는데, 밀릴 것 같으면 꼼수(?)라도 써라고 농담을 들었지만, 맹세컨데 한번도 꼼수(?)를 써 본적이 없었다 ㅋㅋ (그만두고 나온 회사 홍보를 이렇게까지 하다니 ㅎㅎ)
덕분인지는 몰라도, 지난 1년간 이쪽 업계에서 Criteo 모델을 얼마나 알고 있냐고 묻는 헤드 헌터들의 연락이 꽤나 왔었다. 아마 “추천 알고리즘”이라는걸 만드는 회사들이 한계점에 봉착한 상태에서 자신들의 문제를 어떻게 뚫어야할지 내부적인 고민이 많았다는 뜻이겠지. 모르긴 몰라도 일반에 알려진 알고리즘을 카피하는 수준이었거나, 데이터 전처리 & 가공을 매우 조잡하게 하는 상태에서 모델링을 했기 때문일 것이다. 좀 더 냉정하게 이야기하면, 모델링이라는 개념없이, 데이터를 주먹구구식으로 쓰는 기초적인 단계를 못 벗어나고 있기 때문일 것이다고 할 수 있다. (이런게 바로 기술력의 차이다)
(Source: TechCrunch) – Instagram product lead, Julian Gutman
얼마전에 인스타그램이 어떤 기준으로 유저들에게 피드(Feed)를 노출하는지에 대해서 오픈 세미나를 진행했었는데, 내용을 들으면서 여기도 Top-line info만 공개해라는 주의를 많이 들었겠구나 싶더라. 그래도 설명을 들으면서 Criteo와는 다른 방식으로 유저 데이터를 쓰고 있겠다는 생각이 드는 부분이 몇 번 있었는데, 이번 포스팅에 필자 스타일로 수학적인 컨셉에 맞춰 정리해보고 싶다.
1. 인스타그램 알고리즘의 “Variable”
인스타그램의 서비스는 장기간 반복적으로 들어오는 유저들에게 새롭고, 재밌는 내용을 계속 보여줘서 그 유저가 장시간 인스타그램을 돌아다니도록 만드는데 있다. 그런데, 각각의 유저들이 서로 “Following”을 하면서 연관관계를 맺고 있고, 그 연관관계 덕분에, 단순히 컨텐츠만 맞춰주는 방식에서 벗어나 유저들로 구성된 네트워크를 만들었겠구나는 포인트가 눈에 보이더라. (Network Theory 또 등장한다 ㅋ)
- Interest: 유저의 컨텐츠별 흥미도
- Timeliness: 얼마나 최근 컨텐츠인가
- Relationship: 얼마나 친한 사람의 피드인가? Friends and family인가?
- Frequency: 얼마나 자주 인스타그램을 쓰는 유저인가?
- Following: 누구누구를 팔로잉하고 있는가?
- Usage: 얼마나 자주, 얼마나 오래 인스타그램을 쓰는 유저인인가?
인스타그램의 Product Lead를 맡고 있는 Julian Gutman이 발표에서 공개한 인스타그램의 피드 선정 기준들이다. 여기서 눈에 확 들어오는 포인트는 역시 3번 Relationship과 5번 Following이다. 쇼핑몰 광고주들에게 주력하는 타겟팅 광고 회사에 있을 때는 고려대상이 아니었던 포인트기 때문이다. 물론 “오~ 3번과 5번을 쓰는구나!”고 끝냈으면 Data Scientist 타이틀 달고 다니기 좀 쪽팔렸을 것이다.
한국와서 “추천 알고리즘” 만든다는 “개발자”들이 만들어놓은 결과물을 보고 필자가 한번도 칭찬을 하지 않았던 이유도 여기에 있다. 이 분들이 모델링을 한번도 해 본적이 없던 분이어서 그렇겠지만, 3번과 5번을 어떻게 활용해야하는지에 대한 “내공”을 거의 갖고 있지 않기 때문이다. (1,2,4,6번은 말할 것도 없다.) 보통 비슷한 사례를 한국에서 보면 얼마나 Feed를 자주 봤는지, 얼마나 Like를 많이 눌렀는지 등으로 단순 계산을해서 Relationship을 “추측”한다. 그리고 5번을 0/1의 Boolean 값으로 입력한다음, 3번에서 구한 값과 가중평균 곱셉을 한다. 굉장히 1차원적이다.
그럼 이걸 2차원, 3차원적으로 쓰려면 어떻게 해야하냐고?
2. 유저 네트워크의 구성 – complexity
(Source: ResearchGate)
위는 국가별 무역량을 간단한 네트워크로 표현한 그래프다. 인스타그램의 Follower들로 엮은 모델보다 훨씬 더 간단한 네트워크인데도 보면 좀 어지럽다. 그래서 이런 네트워크들을 간단한 행렬로 바꿔쓴다.
(Source: EMBL-EBI)
위와 같은 행렬로 표현하면 Complexity, Transivity, Centrality 등의 주요 정보들을 빠르고 효과적으로 계산할 수 있다. 참고로, 딥러닝이라고 불리는 (Deep) Neural network 모델의 계산 방식도, 비트코인 광풍을 불러왔던 블록체인 모델의 계산도, 모두 위와 같은 행렬로 변환되어서 처리된다.
저 위에 인스타그램에서 주요 변수로 삼는다는 Relationship과 Following 같은 정보가 위의 네트워크를 만들 수 있는 information set이 된다. 센스 있는 사람이라면 2번째의 Directed 같은 그래프가 following 용으로 쓰일 것이고, 3번째의 weighted가 relationship을 표현하는데 쓰인다는 것을 바로 이해할 것이다.
이렇게 그래프를 그려놓으면, (3번째 Network 기준) C, D, E와 G를 잇는 Walk은 3이어서 멀어보이지만, A와 F가 굉장히 친하기 때문에 (둘 사이의 두꺼운 Node) C의 피드가 A에게 노출되는 족족 바로 F에게 노출되고, 그 내용을 또 G가 쉽게 볼 수 있다는 것을 이해하게 된다. 같은 관점에서 B와 G는 Walk이 2 밖에 안 되지만, 정작 B의 피드가 G에게 노출될 확률이 훨씬 낮다는 것을 이해할 수 있다.
3. 유저 네트워크의 구성 – centrality
그럼 이 그래프에서 가장 중요한 사람은 누구일까?
3번째 네트워크에서 A가 사망 or 실종하게 되면 G – F (- B)를 잇는 짧은 네트워크 하나만 남는다. 말을 바꾸면 A가 이 네트워크의 핵심적인 존재다. 이걸 Centrality라고 하는데, walk이 1개인 값들만 모아서 계산하는 방식도 있고, walk을 무한대까지 다 고려한 계산 방식도 있다. (뒤의 경우를 직접 계산하려면 행렬을 무한대만큼 곱하면 된다. 단 convergence를 보장하기 위해서 0~1 사이의 가중치를 활용한다.)
무한대까지 고려하는 방식을 Eigenvalue centrality라고 하는데, 이게 (무식하게) 행렬을 무한번 곱해서 얻은 값을 쓰는게 아니라, 그 행렬의 벡터들이 만들어내는 벡터 공간 (Vector Space)이 행렬이 표현해낼 수 있는 모든 가능성이라는 관점에서 출발한다. (무한번 곱하면서 나온 모든 행렬을 합하면 전체 벡터 공간과 일치한다. “이거 다~ 선형대수학 교과서에 있는 내용인거 아시죠?”ㅋㅋㅋ)
Principal Component Analysis (PCA) 에서와 마찬가지로, 벡터 공간을 유지하면서 새롭게 만들어낸 Eigen-vector와 그에 대응하는 Eigen-value 값들이 새로운 축과 좌표값을 상징하고, 굉장히 복잡해 보이는 네트워크도 간략하게 추려서 볼 수 있다. Unsupervised learning이나 데이터 전처리에서 공부했던 그 PCA가 네트워크형 데이터 처리에서도 이렇게 쓰이는 것이다.
(P.S. 1: 이거 구글 검색시 페이지들이 노출되는 방식이기도 하다. 페이지 주소들을 network으로 묶은 다음, eigen centrality를 기준으로 한 index로 노출 순서를 정하는 것이다.)
(P.S. 2: 네트워크가 무한히 팽창한다고 해도 sum(walk)의 평균값은 크게 움직이지 않고, 그 때 walk의 값에 대한 Chernoff bounds라는 개념이 있다. Extended star network 또는 Scale free network를 만들어내려고 하는 블록체인 업그레이드 모델에서 네트워크의 복잡성을 컨트롤하는데 쓰이는 개념이기도 하다.)
3.1. Centrality for Group
이런 모델링 작업은 서로간 직간접적인 연결 고리만 따지는데, 사실 여러명이 동시에 어떤 행동을 취하는 경우들 (Synergy effect라고 부른다)을 무시할 수도 없다.
(Source: Wikipedia)
위의 V6, V7, V8이 결합해서 V1과 V2를 잇고 있는 걸 보자. 이중 V8은 아래 v11과 연결되어서 아래와 위를 연결해주는 연결 고리 역할을 하고 있으니 약간 다른 관점에서 볼 수 있지만, V6와 V7은 V8과 함께 팀을 이뤄서만 V1, V2와 연결 관계를 갖는다. 중복이 필요없다면 배제시켜야할 것인데, 반대로 항상 그룹으로만 움직여야한다면 어떻게 처리해야할까? 위의 PCA 작업을 하면 분명히 V6, V7의 Eigenvector는 V8에 포함되어 버리겠지만, 반드시 그룹으로 묶어야한다면 이야기가 달라진다.
쉬운 예제를 들면, 혼자서는 만날 수 없는 사람이지만 우리 팀 사람들 전체 모임과는 굉장히 친하게 지내는 높은 분과의 관계를 생각해보자. 그 분이 우리 팀과 친하게 지내는 이유가 팀의 결과물이 자신의 목표와 관계가 있어서일 뿐, 우리 팀원 각각과는 개인적인 관계를 갖고 싶지 않다면?
이런 네트워크에서 Centrality를 계산할 때는 게임이론에 기반한 Shapley Value를 활용한다. (물론 Shapley value 계산이 쉽지 않기 때문에 특정 network에 적합한 형태로 계산 법을 바꾸는 일이 많다.)
나가며 – Network theory를 배워야하는 이유
일전에 모교의 Computer Science 학부 고학년 수업 목록에서 Graph Theory라는 수업을 봤다. Graph가 다양하니 가르치는 주제는 교수들마다 조금씩 다르겠지만, 필자가 수학과에서 들었던 수업은 대부분 Tree model과 Network Theory 위주로 돌아갔었던걸 감안하면, 공대의 같은 수업도 크게 다르지 않을 것이다. 그러나 필자가 한국와서 만난 CS혹은 Math출신의 개발자 중에서 Graph Theory를 제대로 이해하고 있는 분은 (외람되지만) 단 한 분도 없었다.
설령 수업을 들었더라도 단순히 Complexity와 Centrality만 “들어봤다” 수준으로 직장생활을 시작했을 것이다. 요즘 좀 실제 데이터를 쓰면서 가르친다는 수업들 이야기를 들어봐도 기초적인 Network 그리기 연습만하고 끝나거나, Walk, Path, Diameter 같은 기본 개념을 살짝 응용하는정도에서 그치더라. 정작 이걸 Social Network Service에서 어떻게 활용할 수 있을지는 정말 무궁무진한데, 2차원, 3차원으로 쓸 수 있는 경험을 쌓게 해줘야할 수업이 제대로 돌아가질 않았거나, 아니면 아예 학생들이 제대로 배울 생각을 못했던 거겠지.
런던가서 고교 졸업반에 해당하는 학생들에게 경제학을 가르쳐주던 중, 높은 점수를 받았다는 답안지를 보고 충격을 먹었던 적이 있다. 수업에 나오는 개념들을 문제에 적용하면서 생기는 다양한 수학적 도전들을 모두 경제학으로, 실생활의 예제로 풀어서 써 놨더라. “내가 이런 교육을 어릴 때부터 받았었더라면 이렇게 고생하면서 석사공부하고 있지는 않았을텐데”라는 속쓰림을 오랫동안 지울 수 없었다.
추천 알고리즘을 만들겠다는 사용자는 “개발자”라는 사람에게 이걸 만들라고 시키고, 그 분들은 모델링이라는 관점은 거의 배제한채 기계적으로 코드만 갖다붙힌다. 추천 알고리즘을 가르친다는 교육기관에서도 코드 Copy & Paste하고 어떻게 수정하는지를 배우지, 정작 모델이 어떻게 구성되는지는 다루질 않는다. 한국 교육의 특징, 직장의 특징이다. 블록체인 기반의 SNS를 만들어서 컨텐츠를 퍼뜨리는 활동 모두에게 코인을 나눠준다는데, 정작 누구에게 얼마나 배분해주는 시스템을 짜야 시스템이 내부 붕괴하지 않고 돌아가는지 고민했냐고 물어보면 그건 “개발자”가 할 일이란다. 나 원 참~
위에 말했듯이 구글 검색의 노출 기준 중 하나는 Eigen-centrality다. 어떻게 쓰는지 궁금해서 Network Theory와 Network를 행렬로 만든 데이터를 Eigen Decomposition하는 작업과, 그 Eigen vector들로 여러 페이지 검색 데이터를 재구성하는 모델을 만들고 싶은가, 아니면 구글이 만들었다는 코드만 어떻게 좀 구해서 우리 회사 모델에 붙이고 싶은가?
참고로 앞의 작업을 R&D라고 하고, 뒤의 작업을 “도둑질”이라고 한다.
블록체인 시리즈
