[NLP] 유사도 검색 알고리즘 TF-IDF 및 BM25 파이썬과 정리

RAG를 공부하다보면 DPR을 공부하게 되는데, DPR에서 기존 SOTA로 언급한 메소드가 있으니 바로 BM25이다.

DPR 논문 Abstarct에서의 BM25 언급부분

 

그래서 이번 포스팅에선 TF-IDF와 BM25를 간단하게 정리하려고 한다.

 

TF-IDF

TF-IDF는 텍스트마이닝 공부를 하다보면 초반에 배우게 되는 알고리즘이다. 문서를 어떻게 벡터, 즉 숫자로 바꿀 것이냐에 대한 알고리즘인데, 방식이 쉽고 간단한 점이 장점이다. 또한 문서 내에서 단어가 얼마나 중요한지를 나타낼 수 있는 통계적 지표로도 활용 가능하여 처음 제시된 것이 1972년이니 얼마나 이 분야에서 잘 활용되었는지 알 수 있다. 공식을 살펴보면

$\text{TF-IDF}(t,d) = \text{TF}(t,d) \times \text{IDF}(t)$

 

$\text{TF}(t,d) = \frac{f(t,d)}{\sum_{t' \in d} f(t',d)}$  , $\text{IDF}(t) = \log \frac{N}{|\{d \in D : t \in d\}|}$

 

$t$ : 단어, $d$ : 문서, $N$ : 전체 문서 수

 

로 나타낼 수 있게 된다. 즉 TF-IDF는 단순히 TF라는 값과 IDF라는 값을 곱한 것이다.

 

TF와 IDF의 식은 워낙 유명해서 간단히만 정리하고 넘어가면, TF는 용어 빈도이다. 즉 특정 단어가 해당 문서에서 몇 번이나 나왔나를 카운트하는 것이다. (전체 문서 아님 주의) IDF는 한국어로 하면 역문서 빈도이다. 즉 문서 빈도에 역수를 취한 값인데, 문서 빈도란 전체 문서 중 해당 단어를 포함하는 문서가 몇 개냐를 말한다. 그리고 역수값이 너무 커질 수가 있기 때문에 log를 씌워준다. 그런데 해당 단어를 아예 포함하지 않는 경우가 있을 수 있다. 그럴 때를 방지하기 위해

 

$\text{IDF}(t) = \log \frac{N}{1 + |\{d \in D : t \in d\}|}$

 

위와 같은 식으로 대체해서 쓰기도 한다.

 

BM25

TF-IDF가 문서 내 단어의 언급 빈도(TF), 단어가 언급된 문서 빈도(DF)로 단어 및 문장, 문서를 표현하려고 했듯, BM25 또한 접근하는 방식은 비슷하다. 사실 TF-IDF를 개선시킨 알고리즘이라고 한다. 

 

https://wikidocs.net/250433

BM25

참고자료는 위키독스의 AI&ML 사전 및 영문 위키피디아의 BM25 문서 및 레퍼런스로 걸려있는 문서들이다.

 

BM25의 BM은 Best Match, 25는 뭔가 특별한 의미가 있는 줄 알았지만 그런 것 같진 않다.

BM25의 수식은 아래와 같다.

 

$\text{BM25}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t,d) \cdot (k_1 + 1)}{f(t,d) + k_1 \cdot (1 - b + b \cdot \frac{|d|}{\text{avgdl}})}$

 

$q$는 쿼리를 의미하는데, BM25와 TF-IDF가 문서 유사도 검색에 많이 사용됐다보니 아예 쿼리를 가져온 것 같다. 단어 하나만 갖고 설명했던 TF-IDF와 다를 건 없으니 그냥 그렇구나 하고 넘기면 될 것 같다.

 

우선 IDF 를 사용하는 건 똑같은데, TF 부분이 다른 것을 알 수 있다. 상기했듯 BM25는 TF-IDF의 개량 버전이라는 것이 이런 이유에서다. 우선 BM25를 제대로 이해하려면 그 이전 버전인 BM11, BM15를 살펴봐야 할 것 같다.

 

$ \text{BM11}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t, d) \cdot (k_1 + 1)}{f(t, d) + k_1 \cdot \frac{|d|}{\text{avgdl}}}$

 

위키피디아는 BM25에서 b=1인 경우가 BM11이라고 설명하고 있다. 위 수식을 TF-IDF 수식과 비교해보면 TF 부분이 다르다. Term Frequency, 즉 단어 빈도를 사용하긴 하는데 Rate로 사용하는 느낌이 강한 TF-IDF와는 달리 BM11에선 단순히 그 횟수로 사용한다. 특이한건 여기에 $k_1$ 이라는 상수가 분모에, 분자엔 $k_1 + 1$이 들어온다는 것. 이 $k_1$은 하이퍼파라미터로, 일반적으로 좋은 성능의 값은 [1.2, 2.0] 의 값이라고는 하지만 본 연구에선 1로 사용하기도 했다고 한다. 이 $k_1$이 다소 갑자기 등장해서 어려운데, 고전적인 확률론적 가중치 부여 방식의 가장 일반적인 형태에서 유래한 것이다. 내가 다루기는 힘들 것 같아서 여기선 설명하지 않고 링크로 대체하겠다.

 

https://xapian.org/docs/bm25.html

The BM25 Weighting Scheme

 

그리고 $ \frac{|d|}{\text{avgdl}}$ 이 또 새로 등장하는데, 이건 해당 문서의 길이를 전체 문서의 평균 길이로 나눈 값이다. 이걸 문서 길이에 대한 정규화, 보정이라고 부른다. 해당 문서가 길어진다는 것은 단어를 많이 포함하고 있다는 것이고, 단어를 많이 포함한다는 것은 쿼리에 대한 단어를 포함할 확률도 높아진다는 것이다. 따라서 이를 보정해주는 것이다.

 

$\text{BM25}_{b=0}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t, d) \cdot (k_1 + 1)}{f(t, d) + k_1}$

 

위키피디아는 BM25에서 b=0인 경우가 BM10이라고 설명하고 있다. 여기선 문서 길이에 대한 정규화가 사라지고 $k_1$만 남게 된다.

 

이제 다시 BM25로 돌아가면, 

 

$\text{BM25}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t,d) \cdot (k_1 + 1)}{f(t,d) + k_1 \cdot (1 - b + b \cdot \frac{|d|}{\text{avgdl}})}$

 

문서 길이에 대한 정규화항 $(1 - b + b \cdot \frac{|d|}{\text{avgdl}})$ 과 하이퍼파라미터 $k_1$으로 이루어진 TF에 IDF를 곱한 것이라고 해석할 수 있다.

 

이제 파이썬으로 TF-IDF와 BM25의 차이를 확인해보자.

파이썬

import math
from collections import Counter
import pandas as pd

class TFIDF:
    def __init__(self, documents):
        self.documents = documents
        self.doc_count = len(documents)
        self.df = self._compute_df()  # 문서 빈도수 계산
        self.idf = self._compute_idf()  # IDF 계산

    def _compute_df(self):
        """ 문서 빈도수(DF) 계산 """
        df = {}
        for doc in self.documents:
            for word in set(doc):  # 각 문서에서 중복 제거된 단어 집합 사용
                df[word] = df.get(word, 0) + 1
        return df

    def _compute_idf(self):
        """ IDF(Inverse Document Frequency) 계산 """
        idf = {}
        for word, freq in self.df.items():
            idf[word] = math.log((self.doc_count + 1) / (freq + 1)) + 1  # Smoothing 적용
        return idf

    def compute_tf(self, document):
        """ TF(Term Frequency) 계산 """
        tf = Counter(document)
        doc_len = len(document)
        return {word: count / doc_len for word, count in tf.items()}

    def compute_tfidf(self, query, document):
        """ 특정 문서에 대한 TF-IDF 점수 계산 """
        tf = self.compute_tf(document)
        score = 0
        for word in query:
            if word in self.idf:
                score += tf.get(word, 0) * self.idf[word]
        return score

    def rank_documents(self, query):
        """ 질의(query)에 대해 문서별 TF-IDF 점수 계산 """
        query = query.split()
        scores = []
        for i, doc in enumerate(self.documents):
            score = self.compute_tfidf(query, doc)
            scores.append((i, score))
        return sorted(scores, key=lambda x: x[1], reverse=True)

class BM25:
    def __init__(self, documents, k1=1.5, b=0.75):
        self.documents = documents
        self.k1 = k1
        self.b = b
        self.doc_count = len(documents)
        self.avgdl = sum(len(doc) for doc in documents) / self.doc_count  # 평균 문서 길이
        self.df = self._compute_df()  # 문서 빈도수 계산
        self.idf = self._compute_idf()  # IDF 계산

    def _compute_df(self):
        """ 문서 빈도수(DF) 계산 """
        df = {}
        for doc in self.documents:
            for word in set(doc):  # 각 문서에서 중복 제거된 단어 집합 사용
                df[word] = df.get(word, 0) + 1
        return df

    def _compute_idf(self):
        """ IDF(Inverse Document Frequency) 계산 """
        idf = {}
        for word, freq in self.df.items():
            idf[word] = math.log((self.doc_count - freq + 0.5) / (freq + 0.5) + 1)
        return idf

    def compute_bm25(self, query, document):
        """ 특정 문서에 대한 BM25 점수 계산 """
        score = 0
        doc_len = len(document)
        for word in query:
            if word not in self.idf:
                continue
            f = document.count(word)  # 단어 빈도(TF)
            numerator = self.idf[word] * f * (self.k1 + 1)
            denominator = f + self.k1 * (1 - self.b + self.b * (doc_len / self.avgdl))
            score += numerator / denominator
        return score

    def rank_documents(self, query):
        """ 질의(query)에 대해 문서별 BM25 점수 계산 """
        query = query.split()
        scores = []
        for i, doc in enumerate(self.documents):
            score = self.compute_bm25(query, doc)
            scores.append((i, score))
        return sorted(scores, key=lambda x: x[1], reverse=True)

# 테스트 데이터
documents = [
    "deepfake detection technology is improving".split(),
    "deepfake videos are becoming more realistic".split(),
    "the best way to detect deepfakes is AI".split()
]

# 모델 생성
tfidf = TFIDF(documents)
bm25 = BM25(documents)

# 질의 입력
query = "deepfake detection"

# 문서 순위 계산
tfidf_scores = tfidf.rank_documents(query)
bm25_scores = bm25.rank_documents(query)

# 결과 비교
df_results = pd.DataFrame({
    "Document": [" ".join(doc) for doc in documents],
    "TF-IDF Score": [score for _, score in tfidf_scores],
    "BM25 Score": [score for _, score in bm25_scores],
})

 

 

 

예제는 빠르게 ChatGPT로 생성했다. TF-IDF는 싸이킷런으로, BM25는 rank_bm25라는 패키지를 설치해서 사용할 수도 있다. 결과를 보면 TF-IDF로 계산한 유사도는 1보다 작지만, BM25같은 경우엔 1보다 큰값도 나올 수 있음을 알 수 있다. 본 예제는 토큰화 없이 진행했기 때문에 점수는 무조건 신뢰할 수는 없다. ElasticSearch라는 서치엔진이 이 BM25를 기반으로 문서 검색을 진행한다고 하니 추가로 참고하면 좋을 것 같다.

 

추가사항

ChatGPT에게 BM11에 대해서 물어보면 다음과 같이 답한다.

$\text{BM11}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t, d) \cdot (k_1 + 1)}{f(t, d) + k_1}$

 

문제가 되는 부분은 문서 길이에 대한 정규화가 없다고 답하는 부분이다. GPT의 의견과 위키피디아, 공식문서(Xapian)의 의견이  다르기 때문에 둘 중 뭘 채택해야하는지 고민을 많이 했는데, Xapian의 설명이 아주 논리적이고 또 관련 분야의 교수님, 특히 이 TF-IDF 분야에서 저명한 것으로 보이는 Stephen Robertson 의 글을 직접 인용했다고 설명하는 것으로 보아 GPT보단 이쪽을 선택하여 본문을 작성했다.