달고나 57. Product Quantization
Algorithm: Product Quantization
오랜만에 알고리즘을 소개하는 글을 적는다. 몇 달 전에 Product Quantization (PQ)를 접하고 재미있어서 — 간단하지만 효과있는 — 간단한 소개글을 적으려 했으나, 페이스북에서 이걸 제안한 논문 (Optimized Product Quantization for Approximate Nearest Neoghbor Search)이 나온지도 벌써 10년이 지났고 FAISS: a library for efficient similarity search라는 오픈소스도 공개돼있어서 굳이 추가로 글을 적어야 할까?를 오래 고민했지만, 최근에 너무 가벼운 글들만 적었고 또 이 글을 통해서 PQ라는 알고리즘을 처음 접할 이들도 있을 것 같아 그냥 적기로 했다. 알고리즘 자체는 매우 간단해서 여러 블로그 포스팅을 참조해서 원 논문을 읽어보면 쉽게 이해할 수 있다. 대신 처음 PQ를 접하고 떠올랐던 생각을 위주로 글을 적는다.
나도 논문을 몇 편 적었지만 공돌이들의 가장 큰 취약점 중에 하나는 자신의 독창적인 생각을 다른 일반 대중들이 쉽게 이해하도록 적절히 표현하지 못한다는 점이다. 그냥 천재들이나 그 분야에 오랫동안 연구한 사람들을 대상으로 한다면 적당히 수식 한 두 개만 적거나 말로 썰을 조금만 풀어도 자신의 의도를 전달할 수 있지만, 지식과 경험의 차이가 큰 사람들이 이해하는 데는 부족한 점이 많다. 주목을 받는 어떤 논문들을 직접 찾아서 읽어봐도 처음부터 쉽게 이해되는 경우가 흔하지 않다. 하지만 대중 커뮤니케이션에 능한 분들이 그 논문의 핵심 아이디어를 다시 대중의 언어로 풀어 설명해줘서 그때서야 제대로 이해하게 되는 경우가 흔하다. PQ 논문도 그냥 읽으면 약간 감을 잡기 어려운데, 쉽게 소개한 다른 글들을 통해서 제대로 이해할 수 있었다. 아래의 그림도 논문의 개념을 잘 도식화한 블로그 글에서 가져왔다. 알고리즘을 제대로 이해하기 원하는 분은 이 블로그의 그림과 글을 먼저 보고 논문을 읽어보기 바란다.
출처: https://mccormickml.com/2017/10/13/product-quantizer-tutorial-part-1/
PQ를 간략히 설명하면, 긴 원본 데이터 (그림에선 4096차원 float 벡터)를 균등하게 몇 개의 서브벡터 (그림에서 8개)들로 쪼갠다. 쪼갠 각각의 서브벡터/데이터를 k-means 알고리즘을 이용해서 클러스터링 하고 각 서브 샘플들을 클러스터의 centroid index로 매핑한다. 그러면 하나의 샘플은 (그림에선) 정수형 인덱스를 갖는 8차원 정수 벡터가 생성된다. 위의 k-mean 클러스터링을 할 때, k값을 256으로 설정해서 색인의 범위가 0에서 255가 되어서 1바이트 (8비트), 즉 정수 값으로 표현한다. (256은 고정값이 아님) 각 서브벡터를 각각 클러스터링 하고 각 서브 샘플을 [0, 255] 값을 갖게 만든다. 애초에 4096차원의 float형 벡터가 최종 8차원의 정수형 벡터로 변환되어 메모리 사용량이 급격히 줄어들고, 이런 approximation을 통해서 연산 속도가 향상된다. 물론 approximation이므로 정확도는 다소 손실된다 (information loss).
애초 글을 적으려 했을 때는 PQ에 사용된 개념들을 우선 소개하고 알고리즘을 설명하려 했으나 어쩌다 보니 블로그/그림을 먼저 소개하게 됐다. 보통의 경우 차원 축소 dimensionality reduction은 큰 데이터를 눈으로 확인하기 어렵기 때문에 적당히 2~3차원으로 축소한 후 시각화해서 데이터의 특성을 파악하기 위함 (e.g., t-SNE)이나 데이터의 latent/intrisic 축으로 샘플들을 프로젝션함으로써 노이즈를 제거하여 더 robust 한 결과를 얻기 위함 (e.g.. PCA)이나 차원의 저주 (curse of dimensionality)를 해소하여 연산의 효율을 높이기 위함이다. PQ는 특히 3번째 목적이 강하다. 원래 페이스북에서 수많은 이미지 데이터를 빠르게 색인하고 검색하기 위해서 개발됐다.
두 번째로 알면 좋은 개념으로 Voronoi diagram인데, 이는 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 그림 (위키피디아)이다. 이미 초등학교 (중학교?)에서 배운 개념이니 넘어가자. ML의 용어로 그냥 데이터를 k-means 클러스터링으로 해서 가장 가까운 centroid로 색인한 것으로 이해하면 된다. 위의 그림에서 8개의 서브데이터를 각각 k-means 해서 각각의 서브 샘플을 각 k-means의 중심값으로 매핑한 거다.
마지막으로 hemming distnace (또는 hemming space)가 있다. 앞선 설명에서 PQ는 이미지 검색을 빠르게 하기 위함이라고 했다. 이때 필요한 것이 이미지 간의 유사도 (또는 거리)를 계산해야 하는데, 축소된 PQ 벡터 간의 거리를 계산하는 방식에 헤밍 디스턴스가 사용된다. 여느 차원 축소 알고리즘이라면 축소된 값을 바로 이용해서 유클리디언 디스턴스, 코사인 유사도나 상관계수를 구하면 된다. 하지만 PQ의 축소된 값은 centroid의 색인으로 이뤄졌다는 점에서 차이가 있다. 색인을 어떻게 잘 0에서 255까지 나열해서 ordinal 하게 만들 수 있다면 기존의 방식을 그대로 차용하면 되는데, 경우에 따라서 — 예를 들어 — 색인 0과 1보다 색인 0과 125가 더 가까울 수가 있다. 그래서 edit distance의 일종의 hemming distance를 사용한다. Edit distane는 어떤 한 단어 (예, word)를 다른 단어 (예, world)로 변환할 때 몇 번의 연산 (추가, 삭제, 치환)이 필요한지를 계산하는 거다. 앞의 예에서는 ‘l’을 r과 d 사이에 1회 추가하면 되기 때문에 ED = 1이 되다. Word와 work 간의 거리는 d를 k로 1회 치환하면 되기 때문에 역시 ED = 1이 된다. 그런데 헤밍 디스턴스는 길이가 같은 단어들 간의 edit distance이다. 즉, word와 work 사이에는 HD = 1인데, word와 world 사이에는 HD가 정의될 수 없다. PQ로 돌아와서, 위의 그림에서 모든 샘플들은 8차원의 정수 벡터로 표현되는데, 두 샘플 간의 approximated 거리는 8개의 정수 중에 몇 개가 틀리느냐를 계산한 값이다. 즉, 8개의 element 모두 다르면 거리가 8이 되고 모두 같으면 당연히 0이 된다.
그래서 정리하면 PQ는 차원 축소의 한 방법인데, 그림과 같이 원 데이터를 n개의 등차원으로 배분하고, 각 서브 데이터에서 보로노이 영역 (k-means)으로 분할하고, 축소된 데이터는 헤밍 디스턴스를 통해서 유사성을 판별한다.
원래 알고리즘은 이미지 데이터의 빠른 색인과 검색을 위해서 개발되었지만, 나는 오랫동안 다른 서비스, 특히 사용자 데이터를 오랫동안 고민했던 사람으로서 이 알고리즘이 어떤 특징이 있고 또 어떻게 적용/개선하면 좋을지를 조금 고민했다. 이미지 데이터는 순서가 명확하고 균등하다. 예를 들어, 이미지를 가로세로 3 분할하면 총 9개의 서브 영역으로 나뉜다. 보통 사진 중앙에 중요한 사물을 놓기는 하지만 그냥 순서대로 0부터 8까지 균등하게 9등분 해도 별 문제가 없다. 그런데 다른 데이터는 수집하고 concat 하는 순서에 따라서 알고리즘 성능에 영향을 주지 않을까?라는 의문이 들었다. (물론 큰 문제는 없을 거다.) 어쨌든 임의로 데이터를 분할해서 클러스터링을 함으로써 correlated 된 변수들이 분리돼서 알고리즘의 성능을 향상할 것도 같지만, 역으로 인터렉션이 있는 변수들이 다른 서브 데이터로 분할됨으로써 원 데이터를 제대로 반영하지 못하는 부작용이 발생할 수도 있겠다는 생각이 들었다. 그렇지만 다른 많은 알고리즘들이 그렇듯이 — 어떤 측면에선 그냥 운에 맡기듯이 — 랜덤 파티셔닝은 대체로 잘 동작할 거로 본다. 사용자 데이터는 출처가 다양하다. 그래서 한편으로는 순서대로 또는 랜덤 파티셔닝이 아니라, 데이터 출처별로 파티셔닝, 클러스터링, 색인하는 것도 문제에 따라서 효과가 있을 것 같다. 더 나아가 Random Forest (또는 Bagging)처럼 임의로 선택된 변수들의 서브 데이터로 PQ를 진행해도 재미있는 결과가 나올 것 같다. 물론 도미넌트 한 변수가 포함되느냐 빠지느냐에 따라서 결과가 뒤죽박죽 될 가능성도 배제할 수 없다. 특히 나뉜 서브 데이터/스페이스의 클러스터링 결과가 거의 유사하다면 이렇게 나뉜 효과가 반감될 우려도 있다. 그리고 k-means는 등거리로 구분하기 때문에 클러스터별로 속한 샘플수의 편차가 크다. 즉, 검색에서 쿼리에 따른 결과의 양이 천차만별일 수 있다.
1년 전으로 시간을 돌리면 (이미 이직이 결정된 시기라 좀 더 앞으로 ㅎㅎ) PQ 알고리즘을 사용해서 광고 타게팅에 활용했을 것 같다. 사용자와 광고 소재가 많아지면 연산량이 많아지는데 PQ의 approximation 능력을 이용하면 매우 연관성이 높지만 충분히 작은 규모의 유저-광고소재 후보군을 추려내고 그들 간의 정밀한 관계만 계산하면 된다. 특히 요즘처럼 계산이 버거운 DNN이 대세가 되면서 PQ를 닮은 candidate generation은 좋은 대안이 될 수 있어 보인다.
