질문과 관련있는 지문을 찾는 Maximum Inner Product Search

1. Motivation

 

dense embedding을 이용한 retrieve의 원리는 굉장히 간단한데

 

passage를 미리 embedding해놓고 question이 들어오면 embedding을 한 뒤

 

미리 embedding한 passage들과 similarity score를 전부 계산한 다음 가장 높은 score를 가진 passage를 출력

 

similarity score는 nearest neighbor에서 distance가 가까울수록 높은 점수를 부여하는 방식을 생각해볼 수 있고

 

inner product가 높을수록 높은 점수를 부여하는 방식을 생각해볼 수 있다.

 

사람이 이해하기에 nearest search가 위치 거리측면에서 생각하면서 이해하기 쉽다

 

근데 학습이나 효율성측면에서는 nearest neighbor같은 L2 distance보다

 

2개 벡터의 dot product를 구해 maximum 값을 찾는 것이 더 좋을 수 있다.

 

이런 방식으로 inner product의 maximum을 찾아 가장 유사한 두 벡터로 판단하는 것이 Maximum inner product search

 

 

2. formal

 

주어진 질문 벡터 q에 대하여 가지고 있는 passage vector vi , i=1,2,3,...

 

각각 inner product를 구해 최댓값인 벡터 vi를 찾는 문제

 

 

 

 

MIPS는 질문 벡터와 인덱싱된 passage 벡터들을 가지고와서 inner product한 뒤 상위 k개의 passage 벡터를 찾는 과정이다.

 

참고로 인덱싱이라는 말이 나와있는데 방대한 양의 passage 벡터를 저장하는 방식을 indexing이라고 부르나보다.. 기억하고 있는게 좋다

 

 

 

indexing은 방대한 passage 벡터를 공간에 미리 저장해두는 방식이다.

 

질문이 들어오면 indexing된 벡터를 빼내서 score를 계산해서 높은 score가진 passage를 가져옴

 

 

3. problem

 

앞에서는 주어진 질문 q에 대하여 모든 vi , i=1,2,3,... 와 각각 inner product를 해서 최고 점수를 찾았는데

 

이 방식을 brute-force search라고 부르지만 현실적으로 문제점이 많다

 

일단 벡터 차원이 클수록 dot product 계산이 부담이 될 수 있음(근데 이건 큰 문제는 아님.. dense vector의 차원이 그렇게 크지 않다)

 

passage 수가 많아질수록 비효율적이라는 것이 문제임

 

요즘같은 시대에 위키피디아는 500만개라고? 문서단위로 하면 작아보이지만 passage단위로 자르면 수십억, 수십조단위까지 넘어감

 

근데 brute force로하면 수십조 passage 전부 dot product를 해봐야하는데 언제 다 해봄

 

유저가 질문을 던지면 답을 주는데 걸리는 시간은 상당히 짧아야하는데 수십조개 다 해보면 1주일 넘어서 나올텐데 무슨 의미가 있음

 

현실에서 방대한 문서들을 아주 짧은 real time안에 살펴보고 질문에 가장 가까운 passage를 찾아낸 뒤 답을 주는 알고리즘이 중요해졌다.

 

어떻게 하면 이것이 가능할까

 

 

4. tradeoff of similarity search

 

4-1) search speed

 

query당 유사한 벡터를 k개 찾는데 얼마나 걸리는지?

 

당연한데 가지고 있는 passage 벡터가 많을수록 더 오래걸리고 검색 속도도 느려짐

 

 

4-2) memory usage

 

passage 벡터를 indexing하여 저장해놓을 때 어디에 저장하고 필요할 때 사용할지?

 

RAM에 모두 올려둘 수 있으면 편하고 빠르게 사용할 수 있지만, 많은 RAM 용량을 요구한다

 

그렇다고 디스크에 저장하면 계속 불러와야돼서 너무 느려

 

 

4-3) accuracy

 

brute-force 검색 결과와 얼마나 비슷한가?

 

brute-force 자체가 모든 경우를 검사하므로 정확도는 제일 높아야 맞겠지

 

그런데 속도를 높이고 싶으면 덜 검사하면서 결국 정확성을 조금 희생해야겠지

 

 

5. method

 

exhaustive search를 하면 모든 경우를 다 검사하므로 정확성을 최대로 얻을 수 있다.

 

그러나 memory를 많이 쓰고 Search Speed가 그만큼 낮아짐

 

compression을 통해 어떻게 하면 더 적은 용량으로 저장할 수 있을지 고민하여 memory를 효율적으로 사용

 

inference time에 pruning 기법을 통해 정확성을 조금 잃더라도 필요한 속도를 확보하는 것이 중요하다.

 

 

 

 

검색에 오랜시간을 들일수록 재현율이 상승함

 

속도가 느릴수록, 검색시간이 오래걸릴수록, 정확한 검색을 할 가능성이 높다는 것이지

 

search time이 늘어날수록 재현율 recall이 증가함

 

 

 

6. large search space by bigger corpus

 

corpus가 커질수록 사실 많은 문제점들이 생겨남

 

탐색공간이 커지면서 검색시간이 늘어나 어려워짐

 

저장할 memory space도 많이 요구됨

 

sparse embedding이 이런 문제가 심각하지만 compressed format으로 어느정도 극복은 가능함

 

dense embedding도 아무리 차원을 줄여 압축적으로 표현했다고 하더라도

 

마찬가지로 corpus가 커지면 저장할 memory 공간이 많이 요구되는 것은 당연하다

 

 

 

corpus의 벡터 수에 따른 메모리 저장공간

 

현실적으로도 대회에서도 1m(백만)~1g(10억?)까지 갈수있다고는함