DEVOCEAN

개요

• 주제: 정보 검색 및 질의 응답 시스템에서 사용되는 BM25(Best Match 25) 알고리즘의 사용법과 원리 소개

• 개념: BM25는 TF-IDF(단어 빈도-역문서 빈도) 모델을 기반으로 한 정보 검색 알고리즘으로, 문서와 질의 간 유사도를 계산하여 가장 관련성 높은 문서를 찾는 데 사용된다.

• 주요 내용:

1. BM25 개념

2. BM25 수식에 대한 이해

3. Hands-On

1. BM25 개념

BM25(Best Match 25)은 정보 검색 및 문서 검색에서 널리 사용되는 가중치 기반의 랭킹 함수 중 하나로, 특정 쿼리와 문서 간의 관련도를 평가하는 데 사용됩니다.

TF-IDF는 단어의 빈도(Term Frequency)와 역 문서 빈도(Inverse Document Frequency)를 이용해 단어마다 중요도를 계산하는 방법입니다.

기본 개념

먼저 TF-IDF 개념을 이해하는 것이 중요합니다. TF-IDF는 단어의 빈도(Term Frequency)와 역 문서 빈도(Inverse Document Frequency)를 이용해 단어마다 중요도를 계산하는 방법입니다.

따라서 단어의 TF-IDF가 높다는 것은 특정 문서에서 그 단어가 많이 사용되고 있고, 다른 문서들에서는 그 단어가 잘 나타나지 않는다는 의미입니다.

• TF (Term Frequency)

특정 용어가 문서 내에서 등장하는 횟수를 나타냅니다. 일반적으로 문서 내에서 용어가 자주 등장할수록 해당 문서가 쿼리와 관련이 있다고 판단합니다.

• DF(Document Frequency)

문서 집합 내에서 각 단어가 등장한 문서의 수 입니다.

• IDF (Inverse Document Frequency)

DF에 반비례 하는 값입니다. 즉 해당 용어가 전체 문서 집합에서 얼마나 드문지를 측정합니다. 특정 용어가 적게 등장할수록 가중치가 높아집니다. 이는 흔히 자주 등장하는 용어보다 드문 용어에 더 높은 중요성을 부여하는 방법입니다.

• TF-IDF(Term Frequency - Inverse Document Frequency)

  특정 단어가 해당 문서에서 얼마나 unique 한가를 나타내기 위한 방식입니다. TF-IDF가 높을수록 해당 단어가 다른 문서에서는 적게 사용된다는 것을 의미한다 (=해당 문서에서 uniqueness가 높다)

BM25 수식에 대한 이해

BM25 (Best Matching 25) 수식은 정보 검색 및 자연어 처리에서 문서와 질의 간의 유사도를 평가하기 위해 사용되는 통계적 모델입니다.

BM25는 확률적 검색 모델 중 하나인 Okapi BM25의 일부분으로, 주로 역문헌빈도(Inverse Document Frequency, IDF)를 기반으로

한 가중치를 통해 용어 빈도(Term Frequency, TF)를 적절히 조정하여 문서와 질의 간의 매칭 점수를 계산합니다.

먼저 IDF(q_i)는, 쿼리의 키워드 q_i에 대한 IDF(Inverse Document Frequency)입니다. 위에 TF-IDF 정의에서 살펴봤던 IDF와 크게 다르지 않습니다.

해당 키워드가 전체 문서 집단에서 자주 등장한다면 가중치를 적게 주고, 자주 등장하지 않는다면 큰 가중치 부여합니다.

• N: 총 문서의 개수

• n(q_i): 해당 키워드를 포함하는 문서의 개수

IDF(q_i) 수식을 이용한 BM25 랭킹 스코어 수식의 기본 형태는 다음과 같습니다.

여기서 각 수식의 기호를 정리하면 다음과 같습니다.

• Q: 질의를 구성하는 용어들의 집합. (q_1, q_2, ..., q_n)

• IDF(q_i): 쿼리의 키워드 q_i에 대한 IDF(Inverse Document Frequency) 입니다.  해당 키워드가 전체 문서 집단에서 자주 등장한다면 가중치를 적게 주고, 자주 등장하지 않는다면 큰 가중치를 부여합니다.

• TF(q_i,D): 문서 D에서 키워드 q_i가 얼마나 자주 나타나는가를 의미합니다. 문서에 해당 키워드가 자주 나타나면 점수가 높아집니다.

• |D| / avgdl: 말뭉치 내 문서들의 평균 길이 입니다. 해당 문서 D가 평균적인 문서 길이에 비해 얼마나 긴 문서인지를 고려합니다. 평균 대비 문서의 길이가 길다면 점수를 낮추는 역할을 합니다. 매우 긴 문서에서 키워드가 한 번 등장하는 것과 매우 짧은 문서에서 한 번 등장하는 것 중 후자가 더 중요도가 높다고 판단하는 방식입니다.

• k1(알고리즘의 파라미터): 키워드의 빈도를 통해 점수에 주는 영향을 제한합니다. 키워드의 TF가 k1보다 작다면 점수가 빠르게 증가하지만, k1보다 커지는 경우 패널티를 받아 키워드가 많이 등장해도 스코어에 주는 영향이 크지 않도록 제한합니다. 일반적으로 k1의 값은 1.2 ~ 2.0 사이의 값이 많이 사용됩니다. 특히, k1 = 1.5가 많이 사용되는 기본값입니다.

• b(알고리즘의 파라미터): 문서의 길이에 대한 중요도를 제한하는 역할을 합니다. b가 커지면 평균 대비 문서의 길이에 대한 항의 중요도가 커져 문서가 길수록 패널티를 부여합니다. 반대로 b가 작을수록 문서의 길이를 무시합니다. 일반적으로 b는 0.75를 사용한다고 합니다.

k1, b 2개의 파라미터를 통해 TF항이 정규화(Normalized) 함으로써, 아래 그래프에서 확인할 수 있듯이 BM25의 Term Frequency는 TF-IDF와 다르게 특정 값 이상을 넘지 않습니다.

Hands-On

말뭉치 (샘플 문서 집합)을 생성합니다.

from rank_bm25 import BM25Okapi

import numpy as np

  

# 샘플 문서 집합

corpus = [

"파이썬은 프로그래밍 언어입니다",

"자바는 객체 지향 프로그래밍 언어입니다",

"파이썬과 자바는 모두 인기 있는 언어입니다",

"프로그래밍을 배우는 것은 재미있습니다",

"인공지능은 파이썬으로 많이 개발됩니다",

"C++은 고성능 애플리케이션 개발에 사용됩니다",

"JavaScript는 웹 개발에 필수적인 언어입니다",

"Ruby on Rails는 웹 애플리케이션 프레임워크입니다",

"PHP는 서버 사이드 스크립팅 언어로 널리 사용됩니다",

"Go 언어는 동시성 프로그래밍을 지원합니다",

"Swift는 iOS 앱 개발에 주로 사용되는 언어입니다",

"R은 통계 분석과 데이터 시각화에 특화된 언어입니다",

"Kotlin은 안드로이드 앱 개발에 인기가 있습니다",

"TypeScript는 정적 타입을 지원하는 JavaScript의 상위 집합입니다",

"Rust는 메모리 안전성을 강조하는 시스템 프로그래밍 언어입니다",

"SQL은 데이터베이스 관리에 사용되는 쿼리 언어입니다",

"Scala는 함수형 프로그래밍과 객체 지향 프로그래밍을 결합한 언어입니다",

"MATLAB은 수치 계산과 알고리즘 개발에 사용되는 언어입니다",

"Perl은 텍스트 처리에 강점이 있는 스크립트 언어입니다",

"Haskell은 순수 함수형 프로그래밍 언어입니다"

]

말뭉치의 각 문장을 빈칸(blank) 기준으로 분리하는 간단한 토크나이저를 사용합니다.

# 토큰화

from pprint import pprint

  

tokenized_corpus = [doc.split() for doc in corpus]

pprint(tokenized_corpus)

[['파이썬은', '프로그래밍', '언어입니다'],

['자바는', '객체', '지향', '프로그래밍', '언어입니다'],

['파이썬과', '자바는', '모두', '인기', '있는', '언어입니다'],

['프로그래밍을', '배우는', '것은', '재미있습니다'],

['인공지능은', '파이썬으로', '많이', '개발됩니다'],

['C++은', '고성능', '애플리케이션', '개발에', '사용됩니다'],

['JavaScript는', '웹', '개발에', '필수적인', '언어입니다'],

['Ruby', 'on', 'Rails는', '웹', '애플리케이션', '프레임워크입니다'],

['PHP는', '서버', '사이드', '스크립팅', '언어로', '널리', '사용됩니다'],

['Go', '언어는', '동시성', '프로그래밍을', '지원합니다'],

['Swift는', 'iOS', '앱', '개발에', '주로', '사용되는', '언어입니다'],

['R은', '통계', '분석과', '데이터', '시각화에', '특화된', '언어입니다'],

['Kotlin은', '안드로이드', '앱', '개발에', '인기가', '있습니다'],

['TypeScript는', '정적', '타입을', '지원하는', 'JavaScript의', '상위', '집합입니다'],

['Rust는', '메모리', '안전성을', '강조하는', '시스템', '프로그래밍', '언어입니다'],

['SQL은', '데이터베이스', '관리에', '사용되는', '쿼리', '언어입니다'],

['Scala는', '함수형', '프로그래밍과', '객체', '지향', '프로그래밍을', '결합한', '언어입니다'],

['MATLAB은', '수치', '계산과', '알고리즘', '개발에', '사용되는', '언어입니다'],

['Perl은', '텍스트', '처리에', '강점이', '있는', '스크립트', '언어입니다'],

['Haskell은', '순수', '함수형', '프로그래밍', '언어입니다']]

토크나이징된 단어(keyword)를 이용해서 BM25 모델을 생성합니다.

# BM25 모델 생성

bm25 = BM25Okapi(tokenized_corpus)

BM쿼리를 위해 사용자 쿼리 (파이썬 프로그래밍)에 동일하게 토크나이징 합니다.

# 검색 쿼리

query = "파이썬 프로그래밍"

tokenized_query = query.split()

이미 생성한 말뭉치에 대한 BM25 모듈에 대해 토크나이징된 쿼리를 넣어서 keyword-based search (TF-IDF) 수행하여 스코어링 합니다.

# BM25 점수 계산

doc_scores = bm25.get_scores(tokenized_query)

최종적으로 사용자 쿼리 ("파이썬 프로그래밍")에 대한 각 문서와의 관련성을 점수(score)로 표현하여 가져올 수 있습니다.

이것은 우리가 일상 생활에서 사용하는 구글 검색 과정과 매우 유사합니다.

구글 검색 결과의 첫 상위 페이지에 보여주는 문서가 스코어 점수가 가장 높은 순서대로 보여주는 방법이 대표적인 BM25 와 같은 keyword-based search 과정으로 이해할 수 있습니다.

# 결과 출력

for i in np.argsort(doc_scores)[::-1]:

print(f"문서 {i+1}: {corpus[i]}")

print(f"점수: {doc_scores[i]:.4f}")

print()

문서 1: 파이썬은 프로그래밍 언어입니다

점수: 1.6641

문서 20: Haskell은 순수 함수형 프로그래밍 언어입니다

점수: 1.3902

문서 2: 자바는 객체 지향 프로그래밍 언어입니다

점수: 1.3902

문서 15: Rust는 메모리 안전성을 강조하는 시스템 프로그래밍 언어입니다

점수: 1.1937

문서 17: Scala는 함수형 프로그래밍과 객체 지향 프로그래밍을 결합한 언어입니다

점수: 0.0000

문서 18: MATLAB은 수치 계산과 알고리즘 개발에 사용되는 언어입니다

점수: 0.0000

문서 19: Perl은 텍스트 처리에 강점이 있는 스크립트 언어입니다

점수: 0.0000

문서 16: SQL은 데이터베이스 관리에 사용되는 쿼리 언어입니다

점수: 0.0000

문서 12: R은 통계 분석과 데이터 시각화에 특화된 언어입니다

점수: 0.0000

문서 11: Swift는 iOS 앱 개발에 주로 사용되는 언어입니다

점수: 0.0000

문서 14: TypeScript는 정적 타입을 지원하는 JavaScript의 상위 집합입니다

점수: 0.0000

문서 13: Kotlin은 안드로이드 앱 개발에 인기가 있습니다

점수: 0.0000

문서 9: PHP는 서버 사이드 스크립팅 언어로 널리 사용됩니다

점수: 0.0000

문서 10: Go 언어는 동시성 프로그래밍을 지원합니다

점수: 0.0000

문서 8: Ruby on Rails는 웹 애플리케이션 프레임워크입니다

점수: 0.0000

문서 7: JavaScript는 웹 개발에 필수적인 언어입니다

점수: 0.0000

문서 5: 인공지능은 파이썬으로 많이 개발됩니다

점수: 0.0000

문서 6: C++은 고성능 애플리케이션 개발에 사용됩니다

점수: 0.0000

문서 3: 파이썬과 자바는 모두 인기 있는 언어입니다

점수: 0.0000

문서 4: 프로그래밍을 배우는 것은 재미있습니다

점수: 0.0000