Retrieval이란 사전에 준비 된 데이터 내부에서 가장 적절한 것을 찾는 것을 의미합니다. 접근 방식 중 하나는 쿼리 정보를 벡터화하여 사전에 벡터화 되어 있는 데이터들 중 쿼리 벡터와의 내적(inner product)값이 가장 큰 것을 찾아주는 것 입니다. 해당 방식으로 sorting을 할 경우 임베딩 모델 학습 시 쿼리 벡터와 그에 상응하는 답의 내적은 크고, 그에 상응하지 않는 답의 내적은 작도록 학습을 해야합니다.
답 후보군이 많다면 검색하는데 시간이 걸릴 것이고, 가장 기본적으로는 쿼리 벡터와 답 벡터의 내적을 모두 다 비교해서 그 중 값이 가장 큰 답을 찾는 방법이 있습니다. 답 후보의 갯수를 n개라고 하면, O(n) complexity의 exact search를 베이스로, 그보다 개선된 sub-linear-time approximate search 소개해 보도록 하겠습니다.
About
Sub-linear-time의 알고리즘들을 소개하기 앞서 조금 더 구체적으로 Maximum Inner Product Search(MIPS)가 어떤 문제인지, 그리고 Nearest Neighbor Search(NNS)와 Maximum Cosine Similarity Search(MCSS)와는 어떻게 다른지 소개합니다.
쿼리 벡터를 q, 답변 후보군을 V라고 하겠습니다. 우리는 결국 V에 속해 있는 각 답변 벡터들 v_i 중에서 q와의 ‘상성이 가장 좋은’ 것을 찾아야합니다. 그 좋은 상성의 기준이 q와 v_i와의 내적이 큰 것이면 MIPS, q와 v_i의 유클리디안 거리(Euclidean Distance)가 작은 것이면 NNS, q와 v_i의 코사인유사도(Cosine Similarity)가 큰 것이면 MCSS가 됩니다. 이것을 수식으로 풀면,
MIPS의 objective는
NNS의 objective는
MCSS의 objective는
가 됩니다. 여기서 주목해야할 부분은 세 경우 모두 q와 v_i의 내적이 클 수록 좋다는 공통점이 있지만, NNS와 MCSS와는 v_i의 norm이 작아야한다는 추가 제약이 있는 방면 MIPS의 경우에는 그렇지 않다는 점입니다. 그래서 모든 v_i 벡터들의 norm이 같다면 MCSS, NNS는 결국 MIPS와 같은 문제가 됩니다. 하지만 norm이 같지 않은경우, MCSS와 NNS의 알고리즘들을 직접적으로 MIPS에 적용시킬 수가 없습니다.
하지만 MIPS를 효율적으로 풀려는 몇 가지의 시도가 있고, 몇가지 방법으로 MIPS를 NNS, 혹은 MCSS 문제로 변환하여 NNS와 MCSS 알고리즘들을 적용하는 접근을 합니다. 이어서 MIPS 문제를 효율적으로 푸는 세가지 알고리즘에 대해서 소개하도록 하겠습니다.
MIPS에서 NNS, MCSS로
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS), CLUSTERING IS EFFICIENT FOR APPROXIMATE MAXIMUM INNER PRODUCT SEARCH 논문에서 소개된 방법으로, MIPS문제를 NNS 혹은 MCSS 문제를 풀 듯 풀 수 있는 방법입니다.
우선 답 V의 벡터들 중 norm이 가장 큰 벡터의 norm 만큼 V의 모든 벡터들을 나눠준 후 q, v를 변형시켜 차원을 m만큼 늘릴 것입니다. 쿼리 벡터 q, 답변 벡터 v를 변환하는 함수 P(ㆍ), Q(ㆍ)를 다음과 같이 정의합니다.
여기서 주목해야하는 부분은 P(v)의 norm입니다. P(v)의 norm의 제곱을 구하면 다음과 같습니다.
v의 norm이 0과 1사이이기 때문에 m 무한히 커짐에 따라 ||v||의 2^(m+1) 승은 0에 수렴하게 되기 때문에 모든 v_i들에 대해 P(v_i)들은 norm의 크기가 동일하게 됩니다. m이 충분히 큰 값을 가진다면 모든 P(v_i) 벡터들의 norm들은 거의 비슷한 크기를 가지게 되겠죠. 그 말은 곧 Q(q), P(v_i)의 MIPS 문제를 푸는 것은 Q(q), P(v_i)의 NNS, MCSS 문제를 푸는 것과 비슷하다는 것이죠!
MIPS에서 NNS로, 그리고 Asymmetric Locality Sensitive Hashing
위에서 설명한 P(ㆍ), Q(ㆍ)의 과정을 거치면 다음과 같이 됨을 알 수 있습니다.
이제 우리는 Q(q), P(v_i)에 대해서 NNS를 하면 되는 것입니다! 다양한 NNS 알고리즘중에 해당 논문²(Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS))에서 제시하는 Asymmetric Locality Sensitive Hashing(ALSH)를 소개하도록 하겠습니다. Locality Sensitive Hashing이란 ‘비슷한 위치’에 존재하는 벡터 값들의 hash 값들이 충돌할 확률은 높고, 서로 멀리 떨어져 있는 벡터 값들의 hash 값들이 충돌할 확률은 낮은 hashing을 말합니다. ‘비슷한 위치’의 기준이 내적의 크기라면 LSH를 사용할 수 없습니다. 어떠한 점이든 자기 자신과의 위치가 가장 가까운 것이어야 하는데, 그 기준이 내적이라면 자기 자신한테 가장 가까운 것은 자기 자신이 아닌 경우가 있을 수 있기 때문이죠. 다시 말하자면, 모든 벡터 x, y에 대하여 다음 부등식이 성립하지는 않습니다.
여기서 우리는 MIPS를 NNS로 바꾸는 트릭을 이용할 수 있습니다.
유클리디안 거리를 distance metric으로 하는 여러가지 LSH 함수가 있지만 논문²에서 사용하는 LSH 함수는 다음과 같습니다.
여기서 a는 ~N(0,1)의 i.i.d 표준정규분포에서 랜덤하게 뽑은 숫자들을 성분으로 하는 벡터입니다. “i.i.d” 란 independently and identically distributed의 줄임말로서 a는 다음의 확률분포에서 하나씩 독립적으로 랜덤하게 뽑은 숫자라고 생각할 수 있습니다.
b는 0과 r사이의 uniform distribution에서 랜덤하게 고른 스칼라 값입니다 (r 또한 지정해줘야하는 임의의 변수입니다). “└ ┘” 표시는 내림을 뜻합니다. 그러니까 h의 결과값은 항상 정수가 되겠죠?
이런 식으로 L개(이 또한 우리가 지정해주어야하는 변수입니다. L이 클수록 정확한 대신 search의 시간이 늘어나겠죠?)의 hash 함수들을 만듭니다. 그리고 V 벡터들로 L개의 hash table을 구성해놓습니다. 까먹지 말아야할 것은 hashing을 할 때 바로 h(v_i)를 하는 것이 아니라 h(P(v_i))를 해야한다는 것이죠. 그렇게 hash table이 L개 만들어졌으면 쿼리 벡터 q가 들어왔을 때 L개의 h(Q(q))로 q를 hashing하여 그 결과값들이 가장 많이 충돌하는, 그러니까 L개의 hash function에 대해서 q와 해시충돌이 가장 많이 일어난 v_i를 추천해주면 됩니다! (q와 v_i의 hashing이 Q(), P()로 인해 동일하지 않기 때문에 알고리즘 이름 앞에 ‘Asymmetric’이 붙어 있는 것은 살짝 TMI)
MIPS에서 MCSS로, 그리고 Spherical K-means Clustering
마찬가지로, P(ㆍ), Q(ㆍ)의 과정을 거치면 다음과 같이 됨을 알 수 있습니다.
이제 MIPS를 MCSS처럼 풀 모든 준비가 되었습니다. 어떻게? 바로 CLUSTERING IS EFFICIENT FOR APPROXIMATE MAXIMUM INNER PRODUCT SEARCH 논문에서 소개하는 Spherical K-means Clustering을 이용하는 방법을 통해서 말이죠!
K-means clustering을 위한 Lloyd’s Algorithm과 거의 같습니다만 metric이 코사인 유사도라는 것이 가장 큰 차이점입니다. 이렇게 Spherical K-means Clustering으로 K개의 클러스터를 형성한 후, 각 클러스터의 centroid c_i 값들 중 Q(q)ㆍc_i의 값이 가장 큰 centroid를 찾아 해당 centroid와 같은 클러스터에 속해있는 벡터들 중에서만 exact search를 하면 됩니다! 다만 명심해야할 부분은, K-means clustering의 특성상 클러스터의 변두리 쪽에 위치해 있는 점들을 놓칠 수 있는 가능성이 다분하기 때문에 정확성을 위해 top-N search를 해야합니다. 즉, exact search의 대상이 될 클러스터를 하나만 선정하는 것이 아니라 N개를 선정한다는 말입니다.
그리고 당연히 그 centroid들을 다시 Spherical K-means clustering 해서, 또 그 클러스들의 centroid들을 다시 클러스터링해서 ‘search tree’의 높이를 키울 수 있습니다.
Vector Quantization
다음은 Quantization based Fast Inner Product Search 논문에서 소개된 vector quantization을 통해 빠르게 MIPS를 하는 방법에 대해서 알아보도록 하겠습니다.
Vector Quantization이란 벡터를 압축시키는 것이라고도 생각할 수 있습니다. 먼저 벡터들을 K개의 조각으로 ‘분할’해줄 것입니다.
다만 각 조각들은 서로 길이가 같아야합니다. 예컨대 q¹ 과 v¹의 차원이 같아야 하고 q²와 v²의 차원이 같아야 합니다. 모두 분할이 됐다면 우리는 내적을 다음과 같이 계산할 수 있습니다.
그 다음 부분이 핵심적인 부분인데, 이렇게 쪼개 놓은 V의 벡터들의 각 1, 2, 3, … K 번째의 조각들로 각각 공간을 이루어 K개의 공간을 이룹니다. 예컨대 v¹_1, v²_1, v³_1 … 들로 하나의 공간을 이룹니다. 그리고 그렇게 만들어진 각 K개의 공간에서 Mahalanobis Distance를 metric으로 K-means Clustering을 합니다. Mahalanobis Distance란 어떠한 분포와의 거리를 표준편차를 기준으로 나타냅니다.
등장하는 변수들에 대해 설명하겠습니다.
input으로 들어가는 대문자 X는 모든 벡터 v_i들입니다. (k)는 위에서 설명했듯이 각 벡터들을 분할했을 때 k번째 조각이라는 의미입니다. 클러스터링은 같은 순번의 조각들 사이에서 실행이 되어지므로 모두 같은 k를 공유합니다. 그 말은 즉 다음과 같은 클러스터링을 총 k번 해야겠다는 뜻 입니다.
c_x는 하나의 벡터 x가 속해있는 클러스터를 얘기합니다.
S_c는 c번째 클러스터에 속해있는 벡터들의 집합이며, |S_c|는 그 집합의 크기를 얘기합니다.
U_c^(k)는 k번째 조각들의 클러스터들 중 c번째 클러스터의 centroid입니다.
U^(k)는 centroid들을 행으로 갖는 매트릭스입니다. 클러스터가 N+1개, 벡터들의 k번째 조각들의 길이가 M이라고 하면 이는 (N+1) x M 매트릭스입니다.
α는 assignment vector라고 하는데, 하나의 1과 0들로만 이루어진 one-hot vector입니다. 즉 α_i^k 는 v_i의 k번째 조각이 그 공간의 여러 클러스터들(U^k) 중 몇 번째 클러스터에 속해있는지를 명시해주는 벡터라고 생각하면 됩니다. 예를 들어 x 의 k번째 조각이 해당 조각들의 클러스터들 중 0번째 클러스터에 속해있다면 α_x^(k) = [1, 0, …, 0]입니다. 곧 U_c^(k)가 주여졌을 때 x^(k)가 c번째 클러스터에 속해있다면 다음과 같이 x의 k번째 조각을 근사할 수 있습니다.
클러스터링은 Lloyd 알고리즘을 조금 변형해서 사용합니다. 구체적인 알고리즘은 다음과 같습니다.
위의 알고리즘에서 추가적으로 알아야하는 것이 바로 Mahalanobis distance라는 것인데, 수식은 다음과 같습니다.
여기서 Σ_X는 X의 covariance matrix입니다. covariance matrix는 분포의 mean들의 outer product입니다. N+1개의 클러스터로 클러스터링을 한다고 했을 때 이를 수식으로 표현하면 다음과 같습니다.
이렇게 클러스터링을 통해서 구해진 U^k들을 codebook이라고 합니다. 클러스터 centroid 값들로 이루어진 매트릭스라고 할 수 있죠. 우리는 v_i를 다음과 같이 근사할 것입니다.
q와의 내적도 다음과 같이 근사할 수 있죠.
참으로 근사하죠?
사전에 이렇게 U와 α를 구해놓고 각 답변 벡터들을 α들로 나타내는 look-up table을 준비해놓읍시다. 예를 들어 어떠한 v_i에 대해 α¹_i= [0, 1, 0, …], a²_i = [0, 0, 1, …], … 라고 하면 [1, 2, ….] -> v_i로 매핑이 되는 look-up table을 준비하면 됩니다.
이제 쿼리 벡터 q가 들어오면 q를 K개로 쪼개어 각 K개의 codebook U에서 q^k와의 내적이 큰 centroid들을 찾아주기만 하면 됩니다. 그 후 사전에 준비해놓은 look-up table에서 답변 v를 가져오면 끝!
References
