벡터 공간 모형에서의 효과적인 질의 평가 방법 - WAND를 활용한 2단계 검색

정보 검색 모형 중 벡터 공간 모형(질의와 문헌을 벡터 공간 상의 좌표로 표현하고, 검색 시 질의와 문헌 좌표 간의 코사인 유사도를 계산하여 정렬하는 모형)은 안정적이면서 뛰어난 성능 덕분에 현재 다양한 검색 엔진에 널리 쓰이고 있습니다. 문제는 두 좌표 상의 코사인 유사도를 계산하는 것이 생각보다 비싼 연산이라는 것입니다. 벡터 공간의 dimension이 V일 경우, 총 V번의 곱셈과 덧셈이 필요하죠. 이게 모든 쿼리-문헌에 대해 계산되어야 전체 문헌에 대한 순위화가 가능하므로, 문헌이 총 D개라고 할 경우 최소 D*V 번의 곱셈이 필요합니다. 문헌 갯수 D가 커질수록 덩달아 V도 커질테니, 사실상 그 전체 연산 비용은 어마어마하게 늘어날 것이라고 예상할 수 있겠습니다.

이는 대량의 정보를 처리해야하는 웹 검색에서 치명적인 한계가 되는데요, 이를 극복하기 위한 기법 중 하나로 WAND를 이용한 2단계 검색 방법이 제안된 바 있습니다.^[각주:1] 이번 포스팅에서는 이 방법을 통해 어떻게 벡터 공간 모형의 검색 속도를 향상시킬 수 있는지 살펴보도록 하겠습니다.

Weakly AND(Weighted AND) 연산

본 방법의 가장 중요한 키워드는 WAND입니다. 이는 Weakly AND 또는 Weighted AND의 약자로써, 다음과 같은 연산을 의미합니다.

WAND연산자는 x_1, w_1, x_2, w_2, ... x_n, w_n까지의 내적한 값이 k 이상이면 참, 그렇지 않으면 거짓이 되도록 정의되었습니다. 여기에서 x_i가 문헌 내 각 용어의 존재 유무(0 혹은 1), 가중치 w_i는 전부 1로 둘 경우 AND와 OR연산은 다음과 같이 바꿔 쓸수있습니다.

매우 자명한 사실이죠. threshold인 k값이 1~n사이의 값을 가질 경우 AND와 OR의 중간쯤의 연산결과를 내는것도 가능합니다. 따라서 WAND는 불리언 검색 모형의 AND와 OR 연산의 일반화 버전이라고 할 수 있습니다.

벡터 간의 코사인 유사도와 WAND의 관계

두 벡터 Q와 D의 코사인 유사도는 다음과 같이 계산됩니다.

두 벡터의 코사인 유사도는 두 벡터 간의 내적 값을 두 벡터의 크기로 나눈 값입니다. 혹은 두 벡터의 크기로 나누는 작업을 먼저 수행할 경우(단위 벡터로 정규화), 분모 부분을 생략할 수도 있습니다.

즉, 라고 할 경우

로 적을수도 있겠습니다.

이때 정규화된 벡터의 각 요소의 크기는 최대 1입니다. 그리고 Q와 D가 질의와 문헌으로부터 생성된 벡터이므로 모두 0 이상이라고 가정할 수 있구요. 따라서 모든 i에 대해  입니다.

따라서 각각의 용어 i는 전체 유사도 Score에 항상 0~1 사이의 값을 증가시키는 기여를 합니다. 그 기여치는 어떠한 질의 Q에 대해서도를 넘지 못합니다. 이 기여치를 모든 문헌에 대해서 계산하여 상한값을 계산하여 다음과 같이 정의합시다.

최종적으로, 질의에 독립적으로 용어 i가 전체 코사인 유사도 스코어에 기여할수 있는 상한값 UB_i를 알고 있다면, 코사인 유사도를 계산하기에 앞서 특정 질의와 문헌 사이의 유사도의 상한값을 구할 수 있습니다.

한 발 더 나아가, 이 상한값이 특정한 threshold k보다 큰 지 작은 지를 따지는 것은 WAND 연산으로 표현할 수 있구요.

모든 결과를 순위화할 필요는 없다

우리 검색 엔진에게 바라는 것은 질의와 잘 맞는 상위 문헌 N개를 찾아주는 것입니다. 보통 N은 10~20개 정도지요. 전체 수백 만개의 문헌을 모두 정렬해주기를 바라지는 않습니다. 즉 상위 N개만 정확하게 찾아주면 됩니다. 나머지는 어떻게 되든 큰 상관이 없어요. 만약 N번째 문헌의 질의와의 코사인 유사도가 k라고 하면, score(Q, D) < k인 문헌 D는 굳이 코사인 유사도를 계산해볼 필요도 없습니다. 어차피 상위 N개에 들어가지 않을테니까요.

WAND(x1, UB1, ...,  k)가 참이 아닌 경우는 당연히 score(Q, D) < k이므로 문헌 D를 과감하게 무시할 수 있습니다. 약간의 문제가 있긴 합니다. 상위 N번째 문헌의 유사도 k를 정렬해보기 전에 알아내는 건 불가능합니다. 하지만 굳이 정확한 k값을 알지 않더라도 충분히 상위권에 들 희망 없는 문헌들을 필터링하는게 가능한데, 이에 대해서는 뒤에서 더 다루도록 하겠습니다.

WAND 연산이 참이 되는 문헌만 골라내는 알고리즘을 그림으로 설명하면 다음과 같습니다.

검색에 사용한 질의가 grape, orange, water melon, fruit juice 였다고 가정해봅시다. 총 6개의 용어가 포함된 질의네요. 그리고 threshold 값으로 사용할 k = 0.5라고 합시다. 각 질의에 대한 역문헌색인이 다음과 같이 표현할 수 있을거에요.

그리고 각 용어별로 사전에 계산해둔 UB값이 위와 같구요. 제일 첫번째 단계는 현재 각 용어별로 가리키는 포인터(파란 화살표)가 가리키는 문헌 번호가 오름차순이 되도록 용어들을 정렬하는 것입니다. 그리고 나서 각 UB의 합이 0.5 이상이 되는 위치까지 용어들을 선택합니다.

grape, orange, juice까지 선택해야 0.2 + 0.1 + 0.5 = 0.8로 0.5 이상이 됩니다. 그리고 이 때 마지막으로 선택된 juice의 포인터가 가리키는 문헌번호는 7. 문헌번호가 7보다 작은 문헌 중에서는 UB합이 0.5 이상인 경우가 없다는 것은 자명합니다. 따라서 grape와 orange의 포인터가 7이상인 문헌번호를 가리키도록 포인터를 이동시켜 줍니다.

포인터를 이동시켜보고 나니 문헌 7을 가진 녀석은 juice밖에 없었네요. 그러나 다행히도 juice의 UB만 합하여도 0.5 이상이기 때문에, 문헌 7은 UB 0.5이상으로 참이 되므로 이 녀석을 후보 문헌에 넣어줍니다.

그리고 검색은 계속됩니다. 다시 포인터가 가리키는 문헌번호가 오름차순이 되도록 용어들을 정렬해줍니다. 그리고 아까와 마찬가지로 위에서부터 UB의 합이 0.5 이상이 되는곳까지 용어를 선택합니다. 이번에는 melon, water까지 선택하면 0.9으로 0.5를 넘겠네요.

마찬가지로 water가 가리키는 문헌 9 보다 작은쪽에는 UB합이 0.5 이상인 문헌이 없을 겁니다. 따라서 melon의 포인터를 9 이상인 값으로 옮기구요. 9번 문헌에는 water와 fruit이 모두 있어서 UB 합 1.0으로 0.5 이상이 되었습니다. 문헌 9도 후보 목록에 포함시킵시다.

이를 계속 반복하여 첫번째 용어의 포인터가 null에 도달할때까지 후보 목록을 찾아내면 UB합이 0.5 이상인 모든 문헌이 추출되게 됩니다.

얼핏보면 매번 정렬을 실시해서 비효율적이지 않을까 싶을수도 있는데, 실제 질의에 포함되는 용어의 갯수는 그리 많지 않다는 걸 생각해볼때(검색엔진에 20~30단어의 질의어를 넣어보신적 있으신가요? 길어야 5~6단어 정도죠), 정렬은 정말 금방 끝납니다. 그리고 검사가 불필요한 문헌들을 성큼성큼 건너뛰면서 탐색을 진행하기 때문에 효율적으로 필터링이 가능합니다.

k값은 어떻게 정해야하나

WAND를 통한 필터링이 성공적이려면 k값을 잘 정해야합니다. 공격적으로 k값을 아주 높게 정하면, 상위 N개에 포함될법한 문헌도 버려질수 있으니까요. 좋은 방법은 지속적으로 k값을 조정해 나가는 것입니다. 처음에는 k값을 0으로 시작합니다. 즉 별도의 필터링 없이 코사인 각 문헌마다 유사도를 계산해, 후보에 넣는거죠. 그리고 후보 목록에 N개의 문헌이 채워졌다면, 이제 k값을 N번째 문헌의 코사인 유사도 값으로 설정합니다. 그러면 자연히 코사인 유사도가 이를 넘을 희망이 안보이는 문헌들은 1차로 WAND 필터링 예선에서 탈락하게 됩니다. 예선을 통과한 문헌들에 대해서만 코사인 유사도를 계산하고, 이 값이 상위 N개 안에 들어올 경우 후보 목록에 끼워주고(이 경우 꼴찌는 후보 리스트에서 탈락하게 되겠죠) 다시 k값을 업데이트합니다.

논문에 따르면 연산 속도 향상은 놀랍습니다. 유사도 계산 부분의 연산량이 90% 이상 줄었다고 합니다. 거의 1/10로 줄인거죠. 그렇지만 당연하게도 상위 N개의 결과에는 변함이 없구요. 이러한 최적화 덕분에 다양한 검색엔진들이 빠른 검색 속도를 보장할 수 있나 봅니다.

1. Broder, A. Z., Carmel, D., Herscovici, M., Soffer, A., & Zien, J. (2003, November). Efficient query evaluation using a two-level retrieval process. In Proceedings of the twelfth international conference on Information and knowledge management (pp. 426-434). ACM. [본문으로]