확률 모델

확률 모델은 검색 결과를 어떤 순서로 보여 줄지 정하는 한 가지 방법입니다. 문서마다 사용자가 찾던 문서일 확률을 어림합니다. 그 확률이 높은 문서부터 위에 올립니다. 통계와 머신러닝에서는 불확실한 일을 확률로 나타내는 모델을 두루 이 이름으로 부릅니다.

상세

이 절은 확률 모델이 검색의 순서 문제를 확률 문제로 바꾸는 데서 시작합니다. 그다음 가장 단순한 형태인 이진 독립 모델로 낱말의 무게를 직접 계산합니다. 끝에서는 이 모델이 BM25(Best Matching 25)로 이어진 길과, 순서를 매기는 다른 방식과의 차이를 다룹니다. 예는 문서 1,000개짜리 작은 쇼핑몰 검색입니다.

단골 서점에 가서 「비 오는 날 읽을 만한 책」을 달라고 해 봅시다. 주인은 내 마음을 다 알 수 없습니다. 그래도 「이게 제일 마음에 드실 것 같고, 그다음은 이것」 하고 차례로 책을 내밀어 줍니다.

쇼핑몰 검색이 놓인 처지도 이 주인과 같습니다. 사용자가 어떤 문서를 원하는지 확실히 모릅니다. 그래도 원할 것 같은 정도를 어림해 그 순서로 내밉니다. 확률 모델은 이 「원할 것 같은 정도」를 확률로 셉니다.

관련 있음과 없음

검색이 해야 하는 일은 사용자가 찾던 문서를 위에 올리는 것입니다. 문서가 사용자가 찾던 것에 맞는 정도가 관련도입니다. 확률 모델은 관련도를 두 값으로만 봅니다. 문서는 관련이 있거나 없습니다.

문제는 관련이 있는지가 사용자 머릿속에 있다는 점입니다. 「이어폰」을 친 사람이 무선을 원하는지 유선을 원하는지 시스템은 모릅니다. 같은 검색어를 친 두 사람이 서로 다른 문서를 원하기도 합니다.

그래서 확률 모델은 관련 여부를 확실하게 정하지 않습니다. 대신 「이 검색어를 친 사람에게 이 문서가 관련 있을 확률」을 어림합니다. 확실히 모르는 것을 숫자로 다루려고 확률을 꺼냅니다.

확률 순위 원리

확률을 어림했으면 줄 세우는 방법은 하나입니다. 관련 있을 확률이 높은 문서부터 늘어놓습니다. 이 규칙을 확률 순위 원리(Probability Ranking Principle)라고 부릅니다.

이 순서가 관련 문서를 가장 많이 위로 올린다는 보장에는 조건이 붙습니다. 사용자가 결과를 위에서부터 차례로 읽는다고 가정합니다. 문서마다 관련 여부가 다른 문서와 상관없이 정해진다고도 가정합니다. 이 두 가정 아래에서는 확률 순서로 늘어놓을 때 위쪽 몇 건 안에 관련 문서가 평균적으로 가장 많이 들어옵니다.

이 원리가 정하는 것은 순서뿐입니다. 그래서 확률 값 자체를 정확하게 알 필요가 없습니다. 확률이 커질 때 같이 커지는 값이면 무엇이든 같은 순서를 냅니다. 확률 모델의 공식들은 이 점을 이용해 계산하기 쉬운 값으로 바꿔 씁니다.

이진 독립 모델

확률을 어림하려면 문서를 숫자로 나타내야 합니다. 가장 단순한 방법이 이진 독립 모델(Binary Independence Model)입니다. 이름의 두 낱말이 이 모델이 세우는 가정 둘을 가리킵니다.

「이진」은 문서를 낱말이 있나 없나로만 본다는 뜻입니다. 「이어폰」이 한 번 나오든 열 번 나오든 똑같이 「있음」입니다. 낱말의 순서도 보지 않습니다.

「독립」은 낱말끼리 서로 영향을 주지 않는다고 본다는 뜻입니다. 「무선」이 든 문서에 「이어폰」이 함께 들 확률이 다른 문서와 같다고 보는 셈입니다. 실제 글에서는 맞지 않는 가정입니다. 그래도 이렇게 가정하면 문서 하나의 값을 낱말마다 따로 계산한 값의 곱으로 나눌 수 있습니다.

곱보다 더하기가 다루기 쉬워서 이 곱에 log 를 씌웁니다. log 는 곱을 더하기로 바꿉니다. 값이 커지면 log 도 커지므로 줄 세우는 순서는 그대로입니다.

이렇게 나온 점수는 확률 자체가 아닙니다. 앞 절의 원리대로 확률과 같은 순서를 내면 충분합니다. 계산은 단순해집니다. 검색어의 낱말 가운데 문서에 든 것을 찾고, 그 낱말들의 무게를 더하면 점수입니다.

남은 일은 낱말 하나의 무게를 정하는 것입니다. 무게는 관련 있는 문서와 관련 없는 문서에서 그 낱말이 얼마나 다르게 나타나는지를 견줘서 정합니다.

무게 = log( [p / (1 − p)] × [(1 − u) / u] )

p   관련 있는 문서에 이 낱말이 들어 있을 확률
u   관련 없는 문서에 이 낱말이 들어 있을 확률

앞 괄호는 관련 있는 문서에서 이 낱말이 있을 쪽과 없을 쪽을 견줍니다. 뒤 괄호는 관련 없는 문서에서 없을 쪽과 있을 쪽을 견줍니다. 관련 문서에는 잘 들고 관련 없는 문서에는 잘 안 드는 낱말일수록 두 괄호가 함께 커집니다.

p 가 u 보다 크면 두 괄호를 곱한 값이 1 보다 커서 무게가 양수가 됩니다. 관련 문서에 유난히 자주 드는 낱말일수록 그 낱말이 든 문서를 위로 끌어올립니다.

관련 문서를 모를 때의 무게

처음 검색할 때는 어느 문서가 관련 있는지 아무도 모릅니다. p 와 u 를 셀 수가 없습니다. 이 모델은 두 값을 그럴듯하게 어림해서 이 문제를 넘깁니다.

먼저 u 입니다. 한 검색어에 관련 있는 문서는 전체 가운데 아주 적습니다. 그러니 관련 없는 문서는 전체 문서와 거의 같다고 봐도 됩니다. 전체 문서 수를 N, 이 낱말이 든 문서 수를 n 이라 하면 u 는 n/N 입니다.

이 n 이 그 낱말의 문서 빈도입니다. 흔한 낱말일수록 문서 빈도가 큽니다.

p 는 아는 것이 없으므로 반반, 곧 0.5 로 둡니다. 그러면 앞 괄호 p / (1 − p) 가 1 이 되어 식에서 사라집니다. 뒤 괄호에 u = n/N 을 넣으면 (N − n)/n 이 됩니다. 남는 식은 이렇습니다.

무게 = log( (N − n) / n )

문서 1,000개짜리 쇼핑몰에서 이 식으로 무게를 매기면 아래 표가 나옵니다. log 는 자연로그로 계산했습니다.

드문 낱말일수록 무게가 큽니다. 문서 열 개에만 든 「이어폰」은 문서 백 개에 든 「무선」보다 두 배 넘게 무겁습니다. 문서 절반에 든 「방법」은 점수에 아무것도 보태지 않습니다.

「무선 이어폰」을 검색하면 두 낱말이 다 든 문서는 4.6 + 2.2 = 6.8 점을 받습니다. 「이어폰」만 든 문서는 4.6 점이라 그 아래에 섭니다.

이 무게는 역문서 빈도와 같은 생각입니다. 역문서 빈도는 낱말이 든 문서가 드물수록 크게 치는 값입니다. 사람이 경험으로 쓰던 이 값이 확률 모델에서는 가정 몇 개로부터 계산되어 나옵니다.

표의 마지막 줄처럼 절반 넘는 문서에 든 낱말은 무게가 음수가 됩니다. 그런 낱말이 든 문서는 오히려 점수가 깎입니다. 구현에 따라서는 음수 무게를 0 으로 잘라 내기도 합니다.

관련 피드백

이진 독립 모델이 처음 노린 쓰임은 관련 문서를 알게 된 뒤에 있습니다. 사용자가 결과 몇 건을 보고 「이건 맞다」고 표시해 줬다고 해 봅시다. 그러면 p 를 0.5 로 어림하지 않고 셀 수 있습니다.

맞다고 표시한 문서가 다섯 건이라고 합시다. 그중 네 건에 「블루투스」가 들어 있으면 p 는 4/5 로 어림합니다. 이렇게 사용자의 판정을 받아 무게를 고치는 일을 관련 피드백이라 합니다.

「블루투스」처럼 검색어에 없던 낱말도 이 계산으로 무게를 얻습니다. 무게가 큰 낱말은 검색어에 더해 다시 검색합니다. 검색어에 낱말을 보태는 이 일을 질의 확장이라 합니다.

flowchart TD
    A["처음 무게로 검색한다 · p 는 0.5"] --> B["사용자가 맞는 문서를 표시한다"]
    B --> C["표시한 문서에서 낱말마다 p 를 다시 센다"]
    C --> D["무게가 큰 낱말을 검색어에 더해 다시 검색한다"]
    D --> B

사용자가 표시해 주지 않으면 위쪽 몇 건을 맞다고 치고 같은 계산을 돌리기도 합니다. 이 방식을 유사 관련 피드백이라고 부릅니다. 위쪽 결과가 빗나갔으면 무게가 빗나간 쪽으로 더 쏠립니다.

낱말 횟수와 문서 길이

이진 독립 모델은 낱말이 있나 없나만 봅니다. 「이어폰」이 열 번 나온 상품 설명과 한 번 스친 공지 글이 같은 점수를 받습니다. 낱말이 몇 번 나왔는지가 낱말 빈도입니다. 이 모델은 낱말 빈도를 버립니다.

문서 길이도 보지 않습니다. 긴 문서는 낱말이 많아서 검색어의 낱말이 우연히 들어 있을 가능성이 큽니다. 그런데 이 모델은 긴 문서와 짧은 문서를 똑같이 대합니다.

이 두 빈틈을 메운 공식이 BM25입니다. BM25 는 이진 독립 모델의 무게를 뼈대로 둡니다. 거기에 낱말 빈도와 문서 길이를 넣었습니다. 오늘날 검색 엔진이 확률 모델을 쓴다고 할 때는 대개 이 BM25 를 가리킵니다.

다른 순위 모델과의 차이

검색 결과의 순서를 정하는 공식을 묶어 순위 모델이라고 부릅니다. 순위 모델마다 관련도를 무엇으로 보는지가 다릅니다. 아래 표는 확률 모델과 이웃한 셋을 같은 물음으로 견줍니다.

벡터 공간 모델은 「얼마나 닮았나」를 기하로 잽니다. 닮음을 재는 틀만 있어서 낱말 무게를 어떻게 줄지는 따로 정해야 합니다. 확률 모델은 무게가 가정에서 계산되어 나온다는 점이 다릅니다.

질의 우도 모델도 확률을 씁니다. 다만 묻는 방향이 반대입니다. 「이 문서가 관련 있을 확률」이 아니라 「이 문서에서 이 검색어가 나올 확률」을 봅니다. 곧 이 문서를 쓴 사람이 이 검색어를 쓸 확률입니다. 넓게 보면 이것도 확률 모델에 넣습니다.

쓰는 곳과 쓰지 않는 곳

확률 모델은 글자가 맞는 낱말을 찾는 검색에 맞습니다. 「무선 이어폰 미니 2」 같은 상품명이나 「NullPointerException」 같은 에러 이름처럼 검색어의 낱말이 문서에 그대로 나와야 하는 검색이 그렇습니다. 학습 데이터가 없어도 문서 빈도만 세면 바로 돌아갑니다.

뜻으로 찾아야 하는 검색에는 약합니다. 「자동차」를 찾는데 문서에 「차량」만 있으면 낱말이 안 겹쳐 점수가 0 입니다. 이럴 때는 글의 뜻을 숫자 묶음으로 바꿔 견주는 벡터 검색을 씁니다.

확률 순위 원리의 가정이 깨지는 경우도 있습니다. 거의 같은 문서 둘이 있으면 둘 다 확률이 높아 나란히 위에 옵니다. 첫 문서를 읽은 사용자에게 둘째는 쓸모가 없습니다.

문서마다 관련 여부가 따로 정해진다는 가정이 이 경우에 어긋납니다. 결과를 고르게 섞으려면 확률 순서 위에 다른 규칙을 얹어야 합니다.

통계와 머신러닝의 확률 모델

검색 밖에서 확률 모델은 더 넓은 뜻으로 쓰입니다. 일어날 수 있는 결과마다 확률을 매겨 주는 모델이면 모두 확률 모델입니다. 「내일 비가 올 확률」을 숫자로 내는 예보 모델이 그렇습니다.

메일이 스팸일 확률을 계산하는 나이브 베이즈 분류기도 이런 확률 모델입니다. 이 분류기도 낱말끼리 독립이라고 가정합니다. 문서를 「관련 있음」과 「관련 없음」 두 부류로 가르는 일로 보면 이진 독립 모델은 나이브 베이즈와 같은 가정 위에 서 있습니다.

관련 항목

확률 모델이 속하는 상위 분류

정보 검색 · 순위 모델 · 랭킹 · 검색 엔진 · 전문 검색

확률 모델이 순서를 정하는 데 쓰는 원리와 가정

확률 순위 원리 · 관련도 · 이진 독립 모델 · 확률적 관련성 모델 · 단어 주머니 모델 · 독립 가정

확률 모델의 무게를 이루는 값

문서 빈도 · 역문서 빈도 · 낱말 빈도 · 문서 길이 · TF-IDF

확률 모델에서 나온 공식과 기법

BM25 · BM25F · Okapi · 관련 피드백 · 유사 관련 피드백 · 질의 확장

확률 모델과 순서 매기는 방식을 겨루는 모델

불리언 검색 · 벡터 공간 모델 · 질의 우도 모델 · 언어 모델 검색 · 벡터 검색 · Learning to Rank

확률 모델이 기대는 확률 개념

확률 분포 · 조건부 확률 · 베이즈 정리 · 나이브 베이즈 · 통계 · 머신러닝

확률 모델로 매긴 순서를 재는 지표

정밀도 · 재현율 · 결과 다양성