비전공자도 이해할 수 있는 AI지식22 -검색엔진이 우리가 원하는 문서만 보게 만들어주는 비결-

1. 읽지 않아도 두 문서가 비슷하다는 것을 알 수 있는 방법

 

최신 문서도, 품질이 좋은 문서도 쿼리와 상관없이 판별할 수 있어서, 페이지 랭크는 품질 지표를 사용자의 검색 여부와 상관없이 주기적으로 계산하고 미리 저장해두기도 합니다.

 

그러면 매번 계산하지 않아도 되기 때문에 검색 속도를 높일 수 있죠.

 

이제 살펴볼 유사도 점수는 쿼리와 직접 관련이 있습니다. 쿼리에 따라 실시간으로 점수를 계산해야하기 때문에 미리 계산해두기도 어렵습니다.

 

그렇지만 매우 중요합니다. 특히 쿼리와 그에 따른 문서가 얼마나 유사한지는 사실상 검색엔진의 핵심이라고 할 수 있죠.

 

누구나 내가 입력한 쿼리에 딱 맞는 결과를 원하니까요. 그렇다면 어떻게 쿼리에 딱 맞는 문서를 불러올 수 있을까요?

 

먼저 사용자가 입력한 쿼리가 문서 어디쯤에 위치하느냐가 중요합니다.

 

제목에 위치하는지 또는 본문에 위치하는지, 아무래도 제목히 훨씬 더 중요하므로 제목에 위치하는 경우 더 높은 점수를 줍니다.

 

또한 순서대로 매칭되었는지도 중요합니다. 쿼리가 "갤럭시 노트 신제품"인 경우,문서에 이들 단어가 차례대로 표시되어 있다면, 유사한 문서라고 할 수 있겠죠.

 

검색 분야에서는 이를 근접도(proximity)라고 하며, 단어와 단어 사이의 간격이 좁을수록 더 유사한 문서라고 판단하고 높은 점수를 줍니다.

 

예를 들어 다음과 같은 두 문서가 있습니다.

 

- 얼마 전 삼성전자에서 갤럭시 노트의 신제품을 출시했습니다. 새로운 기능에 대한 고객들의 기대가 큽니다.

 

- 신제품이 나온 지 벌써 1년여가 지났지만 노트에 글을 쓰는 느낌을 주는 갤럭시는 아직 등장하지 않고 있습니다.

 

이 경우 쿼리와 매칭하는 단어가 가까이 있는 첫번째 문서가 훨씬 더 높은 점수를 받을 수 있습니다.

 

두 번째 문서는 매칭하는 단어들의 근접도가 매우 떨어집니다. 실제로 쿼리 "갤럭시 노트 신제품"가 의도하는 바와 관련성이 적은 내용이기도 합니다.

 

두번째 문서는 사실상 쿼리와 유사한 문서라고 보기는 어렵습니다.

 

이처럼 컴퓨터가 문서의 내용을 실제로 이해하지는 못하더라도, 단어의 근접도만으로 더 유서한 문서를 찾아낼 수 있습니다.

 

 

2. TF-IDF 알고리즘, 정보 검색 분야의 가장 중요한 발명품

 

근접도만으로 유사한 문서를 판별할 수 있지만, 훨씬 더 훌륭한 유사도 알고리즘이 있습니다.

 

TF-IDF라는 알고리즘은 정보 검색 분야에서는 가장 중요한 발명품으로 꼽습니다. 

 

2015년 추천 시스템을 조사한 한 연구에 따르면, 무려 83%의 시스템이 TF-IDF를 사용하고 있을 정도로 TF-IDF는 검색엔진과 추천 시스템을 대표하는 알고리즘입니다.

 

그렇다면 과연 TF-IDF는 어떤 알고리즘이고, TF-IDF 점수는 무엇일까요?

 

여기서 TF는 Term Frequency로 '단어 출현 빈도'를 의미하며, IDF는 'Inverse Document Frequency'로 '문서 출현 빈도의 역수'를 의미합니다.

 

IDF는 다른 문서에 많이 출현할수록 작은 값이 된다는 얘기죠.

 

원래 IDF 점수는 로그로 계산하지만 여기서는 쉽게 설명하기 위해 단순히 출현 빈도만 이용해 1/(문서 출현 빈도) 형태의 간단한 분수로 나타내겠습니다.

 

이렇게 하면 해당 문서에 많이 출현할수록, 다른 문서에는 적게 출현할수록 TF-IDF 점수가 커집니다.

 

간단한 예를 들어보겠습니다. '갤럭시 노트 신제품'이라는 쿼리에 대해 다음 5개 문서의 TF-IDF 유사도 점수는 각각 몇점일까요?

 

A - 갤럭시 노트 신제품 출시

 

B - 갤럭시 노트 신제품 출시 새로운 노트 만나보세요

 

C - 갤럭시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까

 

D - 갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인

 

E - 삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출

 

먼저 쿼리를 단어 단위로 구분하여 각각의 점수를 구한 뒤 합산합니다.

 

'갤럭시 노트 신제품'이라는 쿼리의 점수를 구하려면, '갤럭시'의 점수, '노트'의 점수, '신제품'의 점수를 각각 구해서 합산해야겠죠

 

그렇다면 하나씩 계산해보겠습니다.

 

먼저 '갤럭시'는 별로 높은 점수를 얻지 못합니다. 왜냐하면 문서 E를 제외한 모든 문서에 '갤럭시'라는 단어가 포함되어 있기 때문이죠

 

희소성이 없습니다. 이 말은 IDF 점수가 낮다는 걸 의미합니다. 

 

TF-IDF 점수는 단어 출현 빈도와 1/(문서 출현 빈도)의 곱이므로, 해당 단어가 많은 문서에 포함되어 있을수록 IDF점수는 낮습니다.

 

문서 A에서 '갤럭시'는 1번 나왔으므로, TF점수는 1점, 4개의 문서에서 출현해 '갤럭시'의 IDF점수는 1/4점입니다.

 

그래서 '갤럭시'에 대한 문서 A의 TF-IDF 점수는 둘을 곱한 1/4점입니다.

 

같은 방식으로 계산하면 문서 B,C,D는 모두 1/4점입니다. E에는 '갤럭시'단어가 등장하지 않으므로 0/4점, 0점입니다.

 

정리해보면 다음과 같습니다

 

문서	내용	'갤럭시' TF-IDF 점수
A	갤럭시 노트 신제품 출시	0.25
B	갤럭시 노트 신제품 출시 새로운 노트 만나보세요	0.25
C	갤럭시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까	0.25
D	갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인	0.25
E	삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출	0

 

 

같은 방식으로 '노트'의 TF-IDF 점수를 구해봅시다.

 

'노트'는 3개 문서에서 등장하므로 IDF 점수는 1/3점입니다. 그런데 문서 C는 '노트'라는 단어가 무려 3번이나 등장합니다.

 

따라서 문서 C의 '노트'에 대한 TF-IDF 점수는 3/3점이므로, 1점이나 됩니다.

 

마지막 단어의 점수도 구해보죠. 단어 '신제품'을 포함한 문서들은 점수를 제법 많이 가져갈 수 있을 것 같습니다.

 

희소성이 높은 단어이기 때문입니다.

 

'신제품'은 문서 A와 B에서만 출현합니다. 문서에 1번만 등장해도 바로 1/2점을 얻습니다.

 

모든 점수를 계산해보면 다음과 같습니다.

 

문서	내용	'갤럭시'	'노트'	'신제품'	'갤럭시 노트 신제품'
A	갤럭시 노트 신제품 출시	0.25	0.33	0.5	1.08
B	갤럭시 노트 신제품 출시 새로운 노트 만나보세요	0.25	0.66	0.5	1.41
C	갤럭시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까	0.25	1	0	1.25
D	갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인	0.25	0	0	0.25
E	삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출	0	0	0	0

 

'갤럭시', '노트', '신제품'에 대한 점수를 각각 계산해봤습니다. 그렇다면 '갤럭시 노트 신제품'이라는 전체 쿼리의 TF-IDF 점수는 어떻게 될까요?

 

단순히 세 단어의 점수를 합산하면 됩니다. 위 표의 맨 우측에 그것을 표기했습니다.

 

점수는 문서 B가 1.41로 가장 높고, 따라서 검색 결과에 가장 먼저 등장하게 됩니다. 

 

그 다음은 문서 C,A순으로 노출이 되겠습니다. 반면, 문서 E는 0점으로 쿼리와 전혀 관련이 없습니다. 따라서 이 문서는 검색 결과에 노출되지 않죠

 

문서 D도 점수가 매우 낮기 때문에 한참 뒤에 나오거나 아예 결과에서 배제될 가능성이 높습니다.

 

어떤가요? 쿼리의 의도와 검색 결과로 나온 문서 내용이 좀 맞는것 같나요?

 

여기까지가 TF-IDF 점수의 기본적인 구조입니다. 검색과 추천 시스템의 83%가 사용한다는 TF-IDF 점수의 핵심이 바로 이러한 계산 방식이죠

 

물론 여기서는 이해를 돕기 위해 아주 단순한 형태로 표현했지만, 실제로는 이렇게까지 간단하지는 않습니다.

 

훨씬 더 복잡하죠. 그렇다면 실무에 실제로 쓰이는 좀 더 정교한 점수 계산 방식을 살펴보고 어떻게 결과가 다른지 알아볼까요?

 

 

3. BM25, 가장 성능이 좋다고 알려진 방식

 

TF-IDF를 기반으로 하는 점수 계산 방식 중 가장 성능이 좋다고 알려진 방식으로 BM25가 있습니다.

 

'Best Matching 25'의 약자로, 1990년대 런던 시티 대학교에서 여러 가중치 조합을 연구한 결과물을

 

Okapi라는 정보 검색 엔진에 적용해 논문을 발표했는데, 여기서 유래한 BM25 가중치 조합은 지금까지도 여러 검색엔진에서 널리 사용할 정도로 성능이 뛰어납니다.

 

구글은 물론이거니와 네이버와 다음 등 사실상 국내외 모든 검색엔진이 채택한 유사도 계산 방식이죠

 

그렇다면 과연 어떻게 구현한 수식이고, 어떤 특징이 있길래 대부분의 검색엔진이 채택해 쓰는 걸까요?

 

기본적으로 BM25는 TF-IDF의 방언 정도로 볼 수 있습니다.

 

TF-IDF의 원리를 다시 한번 떠올려보죠.

 

문서 내에서 해당 단어가 많이 나올수록(단어 출현 빈도), 다른 문서에는 해당 단어가 포함되어 있지 않을수록(문서 출현 빈도) 점수가 커지는 계산방식입니다.

 

BM25도 원리는 동일합니다. 다른 문서에 등장하지 않는 단어가 해당 문서에 많이 포함되어 있을수록 높은 점수를 얻게 되죠

 

그리고 여기에 몇가지 최적화를 덧붙여 훨씬 더 합리적인 점수를 유도합니다.

 

$$ BM25 = IDF \times \frac{TF \times (k_{1} + 1)}{TF + k_{1} \times (1-b+b \times \frac{문서 길이}{평균 길이})} $$

 

여기서 $k_{1}$, b는 hyperparameter

 

복잡해보이지만 단순히 수식이 어렵다고 좋은 성능이 나오는 것은 아닙니다.

 

어려워 보이는 수식 이면에는 성능을 높이기 위한 여러 장치가 숨어있죠

 

먼저 BM25에서는 TF점수가 무한대로 증가하지 않습니다. 수식에 특정 점수 이상을 넘지 않도록 하는 장치가 숨어있죠

 

또한 문서 길이를 살펴보는 장치가 수식에 포함되어 있습니다.

 

TF-IDF는 문서 길이는 평가하지 않기 때문에 긴 문서가 무조건 유리하지만,

 

BM25는 현재 문서 길이와 전체의 평균 길이를 비교하면서 가중치를 조절하는 장치를 포함하기 때문에 같은 조건에서는 오히려 짧은 문서가 좀 더 유리합니다.

 

이외에도 BM25 수식에는 정체를 알 수 없는 $k_{1}$과 b라는 값이 있는데요. 

 

이 두 값은 랭킹을 모델링하는 개발자가 임의로 정하는 값입니다. 매개변수라고 부르는데, 일종의 스위치 역할을 하죠

 

예를 들어 점수가 좀 더 가파르게 상승하도록 하려면 $k_{1}$을 크게 잡으면 됩니다.

 

이렇게하면 단어 출현 빈도에 따라 점수가 좀 더 가파르게 상승하죠. 스위치를 올리는 것과 비슷합니다.

 

이처럼 BM25에는 $k_{1}$과 b라는 개발자가 조절할 수 있는 2개의 값이 있습니다. 최종 점수 분포를 정하기 위해 임의로 설정하는 값이죠.

 

어려운 개념은 아니지만, 주로 통계학을 전공한 개발자들이 전체 문서의 특성과 점수 분포 등을 살펴보면서 어떤 값을 넣을지 결정합니다.

 

기본값으로는 $k_{1} = 1.5$와 b=0.75를 사용합니다.

 

기본값으로 설정하고 앞서 활용한 쿼리인 '갤럭시 노트 신제품'의 BM25 점수를 계산해보죠

 

먼저 각각의 IDF 점수부터 구해본다면..

 

단어	문서 출현 빈도	IDF 점수
갤럭시	5개중 4개	0.2343
노트	5개중 3개	0.2343
신제품	5개중 2개	0.3364

 

 

기존 TF-IDF 점수를 구했을 때의 IDF 점수와는 조금 다릅니다. 앞서 IDF 점수는 예시를 위해 매우 단순하게 계산했지만

 

실제로 IDF 점수를 정교하게 구하려면 몇가지 로그 계산을 거쳐야합니다.

 

이 계산은 조금 복잡하기 때문에 미리 계산해둔 값을 사용하겠습니다.

 

특이한 부분은 '갤럭시'와 '노트'의 출현 빈도가 다름에도 불구하고 IDF 점수가 같다는 점입니다. 

 

왜냐하면 두 단어 모두 출현 빈도가 빈번하기 때문입니다. 핵심은 빈도가 아니라 비율입니다.

 

횟수는 많지 않지만 전체 비율로 보면 각각 60%, 80%에 해당하죠. 전체 문서가 5개밖에 되지 않기 때문입니다.

 

만약 전체 문서가 5개가 아니라 1억 개라고 가정해보죠. 여기에 동일하게 비율이 80%라면, 무려 8000만개 문서에 해당 단어가 등장하는 겁니다.

 

이렇게 보면 매우 빈번하다고 할 수 있겠죠?

 

이처럼 과반수가 넘게 출현하는 단어는 계산식에 따르면 IDF 점수가 마이너스로 나올 수 있기 때문에 보정해주는 작업이 필요합니다.

 

각각 최솟값으로 보정해야하고, 여기서는 그 값이 0.2343입니다. 구체적인 값은 크게 중요하지 않습니다

 

하지만 어떤 경우에 큰 값이 나오고 어떤 경우에 작은 값이 나오는지는 정확하게 인지하고 있어야합니다.

 

다시 한번 얘기하지만 다른 문서에 등장한 적이 없는 희귀한 단어는 값이 높게 나오고 빈번하게 등장하는 단어는 값이 낮게 나옵니다.

 

'갤럭시'처럼 여러 문서에 걸쳐 자주 등장하는 단어는 IDF 값이 작고, '신제품'처럼 다른 문서에 등장하지 않는 희귀한 단어는 IDF 값이 큽니다.

 

BM25 수식을 살펴보면 IDF 점수를 곱하기 때문에 희귀한 단어일수록 더 높은 점수를 받을 수 있겠죠

 

이 부분만 잘 기억하면 됩니다. 먼저 단어 '갤럭시'에 대한 점수를 구하기 위해 IDF 점수 0.2343을 적용해봅시다.

 

문서 A의 내용은 '갤럭시 노트 신제품 출시'였습니다. 그렇다면 '갤럭시' 단어의 TF 점수는 얼마일까요?

 

문서 A에서 '갤럭시'는 1번밖에 등장하지 않았으므로 1입니다. $k_{1}$과 b는 각각 기본값인 1.5와 0.75를 그대로 사용합니다.

 

수식에서 남은 건 $\frac{문서 길이}{평균 길이}$입니다. 

 

TF-IDF 점수를 구할 때는 없었던 이 값이 무슨 역할을 할까요? BM25는 문서 길이로 점수의 가중치를 조절한다고 설명한 바 있었죠.

 

예를 들어 문서 A의 내용인 '갤럭시 노트 신제품 출시'라는 문장에 들어간 띄어쓰기로 구분한 단어 수는 4입니다

 

이렇게 현재 문서의 길이를 구한 값을 전체 문서의 평균 길이의 값으로 나누면 BM25 점수에 가중치를 부여할 수 있습니다.

 

띄어쓰기로 구분한 전체 문서의 평균 길이는 .. $\frac{4+8+9+10+11}{5}=8.4$입니다.

 

이제 문서 A의 $\frac{문서 길이}{평균 길이}$에 대입하면.. 4/(8.4) = 0.47이 나옵니다.

 

만약 문서 E라면 11/(8.4)이므로 1.3이 되겠죠

 

이처럼 해당 문서의 길이가 짧을수록 값이 작아집니다. 이 값은 분모에 위치하므로 값이 작을수록 BM25점수는 커지겠죠

 

문서 A에서는 0.47로 작은 값이 나왔기 때문에 BM25 점수는 비교적 크겠네요.

 

이제 필요한 모든 값을 구했으므로 마지막으로 수식에 대입하여 계산해보면

 

$$ BM25 = 0.2343 \times \frac{1 \times (1.5 + 1)}{1 + 1.5 \times (1-0.75+0.75 \times \frac{4}{8.4})} =0.3066 $$

 

문서 A의 '갤럭시'에 대한 BM25 점수는 0.3066입니다.

 

마찬가지로 다른 단어 점수도 각각 구해서 TF-IDF를 계산했을 때처럼 합산하기만 하면 전체 점수가 나옵니다.

 

문서	내용	TF-IDF	BM25
A	갤럭시 노트 신제품 출시	1.08	1.05
B	갤럭시 노트 신제품 출시 새로운 노트 만나보세요	1.41	0.92
C	갤럭시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까	1.25	0.61
D	갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인	0.25	0.21
E	삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출	0	0

 

 

어떤가요? BM25 점수는 앞서 계산했던 TF-IDF 점수와는 조금 다릅니다.

 

그래서 랭킹도 다릅니다. 문서 A가 1등이고 문서 B가 2등, 문서 C가 3등입니다.

 

어떤 점수가 좀 더 합리적으로 보이나요?

 

쿼리가 '갤럭시 노트 신제품'이라면 모든 단어가 문서에 포함되어 있고 문서의 길이가 가장 짧은 A가 1등이 맞지 않을까요?

 

그렇다면 BM25 점수가 좀 더 합리적이라고 할 수 있습니다.

 

마찬가지로 모든 단어가 문서에 포함되어 있지만, 문서의 길이가 조금 더 긴 B는 2등이 됩니다.

 

그리고 유사한 내용이지만 일부 쿼리가 포함되어 있지 않은 C는 3등이 됩니다.

 

TF-IDF 점수에서는 C가 2등이었지만, C는 '신제품'이라는 단어를 포함하지 않으므로 당연히 문서 A나 B보다는 밀리는게 맞는 것 같습니다.

 

BM25 점수는 최종적으로 A-B-C 순으로 우리가 기대하는 순서와 동일하게 나왔습니다.

 

정말 정교하고 성능이 좋은 방식이죠. 이제 왜 국내외 대부분의 검색엔진이 BM25를 채택하고 활용하는지 알수 있을 겁니다.