BM25

BM25 는 검색어와 문서가 얼마나 잘 맞는지 점수를 매겨 줍니다. 검색 엔진은 이 점수가 높은 문서부터 결과 맨 위에 올립니다. 드문 낱말이 여러 번 나오는 짧은 문서일수록 점수가 높습니다.

상세

BM25(Best Matching 25)는 검색어 하나와 문서 하나를 받아 점수 하나를 돌려주는 계산 절차입니다. 검색 엔진은 후보 문서마다 이 점수를 구하고 큰 순서로 줄 세웁니다. 이렇게 결과의 순서를 정하는 일을 랭킹이라고 부릅니다. 이름의 BM 은 가장 잘 맞춤(Best Matching)이라는 뜻입니다. 25 는 여러 번 고쳐 온 계산식 가운데 이 판에 붙은 번호입니다.

이 절은 점수를 움직이는 세 신호에서 출발합니다. 이어서 앞선 방식이 남긴 문제를 봅니다. 그다음 BM25 의 식을 한 줄씩 뜯어 봅니다.

식을 본 뒤에는 문서 셋에 같은 검색어를 넣어 점수가 어떻게 갈리는지 직접 계산합니다. 끝으로 색인에 미리 적어 두는 값, 글자가 같은 낱말만 잡는 한계, 쓰이는 곳을 차례로 봅니다.

점수를 움직이는 세 신호

검색어의 낱말이 문서에 들었는지만 보면 후보를 고를 수는 있어도 순서를 못 정합니다. 순서를 정하려면 문서가 검색어와 얼마나 잘 맞는지를 숫자로 나타내야 합니다. 이 숫자를 관련도라고 부릅니다.

관련도를 움직이는 신호는 셋입니다.

첫째 신호를 TF(Term Frequency, 낱말 빈도)라고 부릅니다. 한 문서 안에서 그 낱말이 몇 번 나왔는지입니다. 아래에서는 소문자 tf 로 적습니다.

둘째 신호는 IDF(Inverse Document Frequency, 역문서 빈도)입니다. 그 낱말이 든 문서가 적을수록 커지는 값입니다. 문서 수와 거꾸로 움직여서 이름에 「역」이 붙었습니다.

TF-IDF 가 남긴 두 문제

BM25 앞에는 TF-IDF(Term Frequency-Inverse Document Frequency)가 있었습니다. TF-IDF 는 앞의 두 신호를 곱해 점수로 삼습니다. 드문 낱말이 여러 번 나올수록 점수가 올라갑니다.

첫째 문제는 횟수에 비례해 점수가 끝없이 오른다는 것입니다. 「이어폰」이 스무 번 나온 글이 열 번 나온 글보다 두 배 높은 점수를 받습니다. 그런데 스무 번 적었다고 두 배 더 이어폰 이야기인 것은 아닙니다. 그래서 같은 낱말을 일부러 잔뜩 적어 넣은 글이 위로 올라옵니다.

둘째 문제는 문서 길이를 안 본다는 것입니다. 긴 글은 낱말이 많으니 검색어 낱말도 더 자주 나옵니다. 그 글이 검색어를 더 다뤄서가 아니라 그냥 길어서 점수를 더 받습니다.

BM25 는 이 둘을 고치려고 두 장치를 더합니다. 하나는 횟수 점수에 윗한도를 두는 것입니다. 다른 하나는 문서 길이로 횟수를 보정하는 것입니다.

두 장치의 세기는 사람이 미리 정해 넣는 값 둘로 조절합니다. 이런 값이 파라미터입니다. k1 은 윗한도를 맡습니다. b 는 길이 보정을 맡습니다.

한 낱말의 점수를 내는 식

BM25 는 검색어의 낱말마다 점수를 따로 구합니다. 한 낱말의 점수는 아래 세 줄로 나옵니다.

낱말 점수 = IDF × 횟수 몫
횟수 몫   = tf × (k1 + 1) ÷ (tf + k1 × 길이 보정)
길이 보정 = 1 − b + b × (문서 길이 ÷ 평균 문서 길이)

첫 줄은 드문 정도와 횟수를 곱한다는 뜻입니다. 여기까지는 TF-IDF 와 같은 꼴입니다. 다른 것은 둘째 줄입니다. tf 를 바로 곱하지 않습니다. 횟수 몫이라는 값으로 한 번 바꿔서 곱합니다.

셋째 줄의 길이 보정은 이 문서가 평균보다 얼마나 긴지를 나타냅니다. 평균 길이인 문서에서는 1 입니다. 길수록 1 보다 커집니다. 이 값이 둘째 줄의 분모로 들어가서 긴 문서의 횟수 몫을 깎습니다.

식에 드는 값은 두 곳에서 옵니다. 한쪽은 문서 모음 전체의 통계입니다. 다른 쪽은 점수를 매길 이 문서의 값입니다.

전체 통계는 색인에 적어 둡니다. 색인은 검색 엔진이 문서를 넣을 때 미리 만들어 두는 찾아보기입니다. 검색할 때마다 문서를 처음부터 다시 훑지 않으려고 만듭니다. 값이 어디서 오는지 모으면 아래와 같습니다.

flowchart TD
    subgraph 색인["색인 전체의 통계"]
        N["전체 문서 수"]
        DF["낱말이 든 문서 수"]
        AVG["평균 문서 길이"]
    end
    subgraph 문서["이 문서의 값"]
        TF["tf · 낱말이 나온 횟수"]
        L["문서 길이"]
    end
    N --> IDF["IDF"]
    DF --> IDF
    AVG --> NORM["길이 보정"]
    L --> NORM
    TF --> TFP["횟수 몫"]
    NORM --> TFP
    IDF --> S["낱말 점수"]
    TFP --> S
    S --> SUM["검색어의 낱말 점수를 모두 더한 문서 점수"]

위쪽 묶음의 전체 문서 수·낱말이 든 문서 수·평균 문서 길이는 문서 모음 전체에서 한 번 구해 두면 됩니다. 아래쪽 묶음의 tf 와 문서 길이는 문서마다 다릅니다.

둘을 모아 낱말 점수를 냅니다. 검색어에 든 낱말들의 점수를 더하면 문서 점수가 됩니다.

나온 횟수의 포화와 k1

횟수 몫은 tf 가 커져도 k1 + 1 을 넘지 못합니다. 이렇게 더 넣어도 더는 늘지 않는 상태가 포화입니다. 처음 몇 번은 크게 오릅니다. 그 뒤로는 거의 제자리입니다.

아래 표는 k1 을 1.2 로 두고 평균 길이인 문서에서 잰 값입니다. 평균 길이라서 길이 보정은 1 입니다.

TF-IDF 쪽은 스무 번이면 스무 배입니다. BM25 쪽은 스무 번이어도 두 배를 조금 넘을 뿐입니다. 값은 윗한도 2.2 에 다가갑니다. 그래서 같은 낱말을 잔뜩 적어 넣어도 점수가 크게 오르지 않습니다.

k1 은 포화가 얼마나 빨리 오는지를 정합니다. k1 이 0 이면 횟수 몫이 언제나 1 이 됩니다. 낱말이 들었는지만 보는 셈입니다. k1 이 아주 크면 한도가 멀어져서 tf 를 바로 쓰는 것에 가까워집니다.

아래 그림은 tf 를 1 부터 10 까지 늘리며 횟수 몫을 그렸습니다. 아래 선이 k1 1.2, 위 선이 k1 2 입니다.

xychart-beta
    title "tf 에 따른 횟수 몫 · k1 1.2 와 2"
    x-axis "tf" ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10"]
    y-axis "횟수 몫" 0 --> 3
    line [1.00, 1.38, 1.57, 1.69, 1.77, 1.83, 1.88, 1.91, 1.94, 1.96]
    line [1.00, 1.50, 1.80, 2.00, 2.14, 2.25, 2.33, 2.40, 2.45, 2.50]

두 선 모두 처음 몇 칸에서 가파르게 오르다 눕습니다. k1 이 2 인 선은 더 오래 오릅니다. 눕는 높이도 윗한도 3 쪽으로 더 높습니다.

문서 길이 보정과 b

같은 횟수라도 짧은 문서에서 나왔다면 그 낱말의 비중이 더 큽니다. 길이 보정은 이 차이를 점수에 넣습니다.

아래 표는 「이어폰」이 세 번 나온 문서 셋을 견줍니다. k1 은 1.2, b 는 0.75, 평균 문서 길이는 100 낱말로 두었습니다.

같은 세 번이어도 50 낱말짜리 문서가 200 낱말짜리보다 횟수 몫이 한참 큽니다. 긴 문서는 길이 보정이 커집니다. 그만큼 분모가 커져 점수가 깎입니다.

b 는 길이를 얼마나 세게 볼지 정합니다. b 가 0 이면 길이 보정이 늘 1 이라 길이를 안 봅니다. b 가 1 이면 문서 길이에 비례해 온전히 깎습니다. 그 사이 값은 두 극단을 섞습니다.

k1 과 b 는 데이터에 맞춰 고르는 값입니다. 정답이 표시된 검색 결과가 있으면 그걸로 여러 값을 시험해 고릅니다. 그런 자료가 없을 때 흔히 쓰는 값은 k1 을 1.2 에서 2 사이, b 를 0.75 로 두는 것입니다.

드문 낱말의 무게 IDF

IDF 는 그 낱말이 문서를 얼마나 잘 가려 주는지를 나타냅니다. BM25 에서 흔히 쓰는 꼴은 아래와 같습니다. log 는 자연로그입니다.

IDF = log( (전체 문서 수 − 낱말이 든 문서 수 + 0.5) ÷ (낱말이 든 문서 수 + 0.5) )

분수의 위는 낱말이 없는 문서 수입니다. 아래는 낱말이 든 문서 수입니다. 든 문서가 적을수록 분수가 커집니다. 분수가 크면 IDF 도 큽니다. 양쪽에 더한 0.5 는 위나 아래가 0 이 되어 계산이 깨지는 것을 막습니다.

문서 1000 개짜리 상품 목록을 예로 들면 이렇게 나옵니다.

「이어폰」은 열 문서에만 있어서 이 낱말이 맞으면 후보가 크게 좁혀집니다. 그래서 무게가 큽니다. 「무선」은 문서 셋 중 하나꼴로 있어서 무게가 작습니다.

「상품」처럼 문서 절반 넘게 든 낱말은 IDF 가 0 아래로 떨어집니다. 분수의 위가 아래보다 작아지기 때문입니다. 그러면 그 낱말이 맞은 문서가 오히려 점수를 잃습니다.

Lucene 은 식을 고쳐 이 문제를 막습니다. Lucene 은 문서를 색인하고 검색하는 자바 라이브러리입니다. 고친 식은 log 안에 1 을 더합니다.

IDF = log( 1 + (전체 문서 수 − 낱말이 든 문서 수 + 0.5) ÷ (낱말이 든 문서 수 + 0.5) )

더한 1 덕분에 log 안의 값이 1 보다 커집니다. 그러면 IDF 는 늘 0 보다 큽니다. 이 식에서 「상품」의 IDF 는 0.11 입니다. 식을 고치지 않고 음수를 0 으로 잘라 쓰는 방법도 있습니다.

문서 셋으로 따라가는 계산

이 소절은 포화·길이 보정·IDF 를 한 번에 돌려 봅니다. 문서 1000 개 가운데 문서 셋을 골라 「무선 이어폰」으로 점수를 구합니다. k1 은 1.2, b 는 0.75, 평균 문서 길이는 100 낱말입니다.

A 는 짧은 이어폰 상품 설명입니다. B 는 무선 기기 여럿을 길게 소개하다 이어폰을 한 번 언급한 글입니다. C 는 「무선」만 여덟 번 적은 무선 충전기 설명입니다.

같은 계산을 파이썬으로 옮기면 아래와 같습니다. 앞 소절의 IDF 식과 세 줄짜리 식을 옮겼습니다. 코드의 norm 은 길이 보정, tfp 는 횟수 몫입니다. DF(Document Frequency, 문서 빈도)는 낱말이 든 문서 수입니다.

import math

N, AVG = 1000, 100  # 문서 수, 평균 길이
DF = [300, 10]      # 무선, 이어폰
K1, B = 1.2, 0.75

def bm25(tfs, length):
    norm = 1 - B + B * length / AVG
    score = 0.0
    for tf, df in zip(tfs, DF):
        idf = math.log(
            (N - df + 0.5) / (df + 0.5))
        tfp = tf * (K1 + 1) / (tf + K1 * norm)
        score += idf * tfp
    return score

bm25([1, 2], 50)    # 8.34  문서 A
bm25([6, 1], 300)   # 3.74  문서 B
bm25([8, 0], 80)    # 1.65  문서 C

A 가 가장 높습니다. 낱말이 모두 세 번 나왔을 뿐인데도 그렇습니다. 점수를 낱말별로 나눠 보면 까닭이 보입니다.

A 와 B 를 가른 것은 드문 낱말 「이어폰」입니다. 둘 다 이어폰이 들었습니다. A 는 두 번 나온 데다 짧아서 횟수 몫이 1.60 입니다. B 는 한 번뿐인 데다 길어서 0.55 로 깎였습니다.

C 는 「무선」을 여덟 번이나 적었지만 그 점수가 1.65 에서 멈춥니다. 흔한 낱말이라 IDF 가 작습니다. 게다가 횟수가 포화합니다. 이어폰이 없으니 그 낱말 몫은 0 입니다.

색인에 미리 적어 두는 값과 계산 비용

BM25 는 검색할 때 문서 본문을 다시 읽지 않습니다. 필요한 값을 문서를 넣을 때 미리 적어 두기 때문입니다. 적어 두는 곳은 역색인입니다.

역색인은 낱말마다 그 낱말이 든 문서 번호를 모아 둔 목록입니다. 책 뒤의 찾아보기가 같은 구조입니다.

역색인의 한 줄에는 문서 번호와 함께 그 문서에서의 tf 를 적습니다. 그러면 한 줄의 길이가 곧 「낱말이 든 문서 수」가 됩니다. 문서마다 길이도 따로 적어 둡니다. 전체 문서 수와 평균 길이도 색인이 들고 있습니다.

앞 소절의 문서 A·B·C 로 그리면 아래와 같습니다.

flowchart TD
    Q["검색어 「무선 이어폰」"]
    subgraph 역색인["역색인 · 낱말마다 한 줄"]
        W["「무선」 줄"] --> W1["문서 A · tf 1"] --> W2["문서 B · tf 6"] --> W3["문서 C · tf 8"] --> W4["나머지 297개"]
        E["「이어폰」 줄"] --> E1["문서 A · tf 2"] --> E2["문서 B · tf 1"] --> E3["나머지 8개"]
        P["「상품」 줄 · 문서 900개 · 검색어에 없어 안 읽는다"]
    end
    subgraph 길이["문서마다 적어 둔 길이"]
        LA["문서 A · 50"]
        LB["문서 B · 300"]
        LC["문서 C · 80"]
    end
    subgraph 전체["색인 전체의 값"]
        NN["전체 문서 수 · 1000"]
        AV["평균 문서 길이 · 100"]
    end
    Q --> W
    Q --> E

「무선」 줄은 모두 300 칸, 「이어폰」 줄은 10 칸입니다. IDF 표의 「낱말이 든 문서 수」와 같은 값입니다.

검색어가 오면 검색어 낱말의 역색인 줄만 읽습니다. 그림의 「상품」 줄은 검색어에 없어 건드리지 않습니다. 줄에 적힌 문서마다 그 낱말의 점수를 구해 문서별 합계에 더합니다.

그래서 드는 시간은 읽은 줄들의 길이를 모두 더한 값에 비례합니다. 「무선 이어폰」이면 310 칸만 읽습니다. 전체 문서 수와는 무관합니다.

점수를 다 더한 뒤에는 위에서 몇 개만 골라 돌려줍니다. 합계가 붙은 문서 수를 P, 돌려줄 개수를 m 이라고 합시다.

고르는 데는 힙을 씁니다. 힙은 가장 작은 값을 늘 꼭대기에 두는 트리입니다. 그래서 가장 작은 값을 바로 꺼내 버릴 수 있습니다.

힙의 크기를 m 으로 묶어 두고 문서를 하나씩 넣습니다. m 개를 넘으면 꼭대기의 가장 작은 것을 버립니다. 끝까지 넣고 나면 점수가 큰 m 개만 남습니다.

검색할 때의 순서를 모으면 아래와 같습니다.

flowchart TD
    A["검색어를 낱말로 나누기"] --> B["그 낱말의 역색인 줄 읽기"]
    B --> C["줄의 문서마다 낱말 점수 구하기"]
    C --> D["문서별 합계에 더하기"]
    D --> E{"낱말이 남았나"}
    E -->|남았다| B
    E -->|없다| F["크기 m 힙으로 위에서 m 개 고르기"]

힙에 한 번 넣고 버리는 데는 트리 높이만큼 걸립니다. 원소가 m 개인 힙의 높이는 log m 쯤입니다. 문서 P 개를 한 번씩 넣으니 고르는 일은 P × log m 에 비례합니다.

입력이 커질 때 시간이 어떤 꼴로 느는지를 O(…) 로 적습니다. 이 표기로 고르는 일은 O(P log m) 입니다. 공간은 문서별 합계를 담을 만큼, 곧 O(P) 가 더 듭니다.

글자가 같은 낱말만 잡는 한계

BM25 는 낱말의 글자가 같은지만 봅니다. 「자동차」로 찾으면 「차량」이라고만 적힌 문서는 두 낱말이 겹치지 않아 0점입니다. 뜻이 같아도 글자가 다르면 못 잡습니다. 이 틈은 동의어 사전을 따로 붙여 메웁니다.

점수는 글을 낱말로 어떻게 쪼갰느냐에도 달려 있습니다. 글을 낱말로 쪼개는 이 일이 토큰화입니다. BM25 의 tf 도 이렇게 쪼갠 낱말을 단위로 셉니다.

한국어는 「이어폰을」·「이어폰이」처럼 낱말에 조사가 붙습니다. 이걸 두고 쪼개면 서로 다른 낱말로 셉니다. 그래서 색인하기 전에 형태소 분석을 합니다. 낱말을 뜻을 가진 가장 작은 조각으로 나눠 「이어폰」과 「을」을 떼어 내는 일입니다.

낱말의 순서도 보지 않습니다. 조사를 떼고 나면 「개가 사람을 물었다」와 「사람이 개를 물었다」는 둘 다 「개 · 사람 · 물다」가 되어 같은 점수를 받습니다. 문서를 순서 없는 낱말 모음으로만 보는 이런 방식을 단어 주머니 모델이라고 부릅니다.

점수의 크기에도 절대 기준이 없습니다. 한 검색어 안에서 문서끼리 순서를 가리는 값일 뿐입니다. 다른 검색어의 점수와 견주거나 「8점이면 잘 맞는다」처럼 읽을 수는 없습니다.

쓰이는 곳과 짝을 이루는 방식

BM25 는 Okapi 라는 연구용 검색 시스템에서 처음 구현됐습니다. 그래서 Okapi BM25 라고도 합니다.

뿌리는 확률 모델입니다. 문서가 검색어에 맞을 확률을 어림해 점수로 삼는 모델입니다. 앞에서 본 IDF 식의 분수도 이 모델에서 나왔습니다.

지금은 전문 검색의 기본 점수로 널리 쓰입니다. 전문 검색은 긴 글의 본문 전체를 대상으로 낱말을 찾는 검색입니다. 앞에서 본 Lucene 도 기본 점수 계산으로 BM25 를 씁니다. Lucene 을 안에 넣어 만든 검색 서버 Elasticsearch도 마찬가지입니다.

에러 코드·상품 모델명·사람 이름처럼 글자가 딱 맞아야 하는 검색에 잘 맞습니다. 뜻으로 찾아야 하는 검색에는 벡터 검색을 씁니다. 벡터 검색은 글을 뜻을 담은 숫자 목록으로 바꾼 뒤 가까운 것을 찾습니다.

두 방식은 서로 못 잡는 것을 잡습니다. 그래서 둘의 결과를 합쳐 순위를 매기기도 합니다. 이렇게 합치는 방식이 하이브리드 검색입니다.

제목과 본문처럼 필드가 여럿인 문서를 위해 필드마다 무게를 달리 주는 변형 BM25F도 있습니다.

관련 항목

BM25 가 속하는 상위 분류

랭킹 · 관련도 · 순위 모델 · 정보 검색 · 확률 모델 · 확률적 관련성 모델

BM25 식을 이루는 값

TF-IDF · 낱말 빈도 · 역문서 빈도 · 문서 빈도 · 문서 길이 · 길이 정규화 · 포화 함수

BM25 를 고친 변형

BM25F · BM25+ · BM25L · Okapi · 이진 독립 모델

BM25 와 겨루거나 함께 쓰는 검색 방식

불리언 검색 · 벡터 공간 모델 · 벡터 검색 · 임베딩 · 하이브리드 검색 · 재순위화 · 상호 순위 융합 · 학습 기반 랭킹 · SPLADE

BM25 가 기대는 색인과 전처리

역색인 · 포스팅 리스트 · 분석기 · 토큰화 · 형태소 분석 · 불용어 · 어간 추출 · 동의어 · 단어 주머니 모델

BM25 로 점수를 매기는 검색 엔진

검색 엔진 · 전문 검색 · Apache Lucene · Elasticsearch · OpenSearch · Apache Solr

BM25 의 결과를 재는 지표

정밀도 · 재현율 · nDCG · MRR · 평균 정밀도