BM25 전체 텍스트 검색 알고리듬 이해

 (emschwartz.me)
1P by GN⁺ | ★ favorite | 댓글 1개
  • BM25는 정확한 키워드 매칭이 필요한 전체 텍스트 검색에서 여전히 널리 쓰이며, 벡터 유사도 검색을 보완하는 하이브리드 검색의 한 축이 됨
  • 확률을 직접 계산하지 않고도 문서 순위를 정하기 위해, BM25는 쿼리 항별 가중치를 더해 관련성이 높아 보이는 문서를 앞에 배치함
  • 점수는 IDF, 문서 내 용어 빈도, 문서 길이 정규화로 나뉘며, 드문 단어는 더 크게 반영하고 반복 등장은 점차 덜 보상함
  • k1은 반복 등장 보상의 체감 속도를, b는 문서 길이 정규화 강도를 조절하며 보통 k1=1.2~2, b=0.75가 쓰임
  • BM25 점수는 실제 관련 확률이 아니므로 범용 비교값처럼 쓰기 어렵고, 같은 문서 컬렉션 안에서 비교할 때 의미가 있음

BM25가 풀려는 검색 문제

  • BM25 또는 Best Match 25는 전체 텍스트 검색에서 널리 쓰이는 알고리듬임
    • Lucene/Elasticsearch와 SQLite 등에서 기본값으로 사용됨
    • 최근에는 전체 텍스트 검색과 벡터 유사도 검색을 결합한 하이브리드 검색이 흔해짐
  • 개인화 콘텐츠 피드에서는 벡터 유사도 검색만으로 정확한 키워드 처리가 부족할 수 있음
    • 관심사가 Solid.js인 경우, 벡터 유사도 검색만 사용하면 Solid보다 React 관련 콘텐츠가 더 많이 나올 수 있음
  • 핵심 질문은 한 문서의 BM25 점수를 여러 쿼리 사이에서 비교해, 그 문서가 어떤 쿼리에 가장 잘 맞는지 판단할 수 있는지임

확률 랭킹 원리와 BM25의 접근

  • 전체 텍스트 검색의 목표는 쿼리를 기준으로 가능한 문서 집합에서 가장 관련 있는 문서를 찾는 것임
  • 실제 관련성을 확실히 알 수 없기 때문에, 검색은 문서가 쿼리에 관련 있을 확률을 기준으로 정렬하려고 함
    • 이 아이디어는 Probability Ranking Principle로 불림
  • BM25 같은 어휘 기반 검색은 쿼리와 문서 컬렉션 안의 문서 특성만 사용함
    • 벡터 유사도 검색은 외부 텍스트 말뭉치로 학습된 임베딩 모델을 사용해 쿼리와 문서의 의미를 표현할 수 있음

BM25 점수를 이루는 요소

  • BM25는 쿼리와 문서 컬렉션의 여러 신호를 조합해 점수를 계산함

  • 쿼리 항

    • 검색 쿼리가 여러 용어로 구성되면, 각 용어별 점수를 계산한 뒤 합산함

  • 역문서 빈도(IDF)

    • 특정 검색어가 전체 문서 컬렉션에서 얼마나 드문지를 나타냄
    • the, and 같은 흔한 단어는 정보량이 낮다고 보고, 드문 단어의 중요도를 높임

  • 문서 내 용어 빈도

    • 검색어가 특정 문서에 몇 번 등장하는지를 반영함
    • 같은 용어가 더 많이 반복되면 관련 가능성이 커진다고 보지만, BM25는 반복 등장에 체감 효과를 적용함

  • 문서 길이

    • 긴 문서는 길다는 이유만으로 검색어가 더 많이 등장할 수 있음
    • BM25는 문서 길이를 평균 문서 길이와 비교해, 긴 문서가 부당하게 높은 점수를 받지 않도록 정규화함

BM25 수식의 각 부분

  • BM25의 전체 점수는 문서 D와 쿼리 Q에 대해 각 쿼리 항 q_i의 점수를 더하는 방식임
    • D: 대상 문서
    • Q: 전체 쿼리
    • n: 쿼리 항 개수
    • q_i: 각 쿼리 항

  • IDF: 컬렉션 안에서 희귀한 단어를 더 크게 반영

    • IDF 항은 쿼리 항이 전체 문서 컬렉션에서 얼마나 드문지 계산함
    • N: 컬렉션의 전체 문서 수
    • n(q_i): 쿼리 항을 포함한 문서 수
    • N - n(q_i): 쿼리 항을 포함하지 않은 문서 수
    • 흔한 용어는 많은 문서에 등장하므로 점수에 미치는 영향이 작아짐
    • 드문 용어는 적은 문서에만 등장하므로 점수에 더 크게 반영됨
    • 수식의 0.5와 1은 용어가 매우 드물거나 매우 흔할 때 결과가 크게 흔들리지 않도록 완화하는 역할을 함

  • 용어 빈도: 반복은 반영하되 무한히 보상하지 않음

    • 문서 내 용어 빈도는 특정 쿼리 항이 특정 문서에 얼마나 자주 등장하는지를 반영함
    • f(q_i, D): 쿼리 항 q_i가 문서 D에 등장한 빈도
    • k1: 보통 1.2에서 2 사이로 설정되는 튜닝 매개변수
    • BM25는 용어 반복을 점수에 반영하지만, 반복이 늘수록 추가 점수 상승폭은 줄어듦
    • k1은 용어 반복 보상이 얼마나 빨리 줄어드는지를 제어함

  • 문서 길이 정규화: 긴 문서의 유리함을 조정

    • 문서 길이 정규화는 대상 문서 길이를 컬렉션의 평균 문서 길이와 비교함
    • |D|: 대상 문서의 길이
    • avgdl: 컬렉션의 평균 문서 길이
    • b: 문서 길이 정규화 강도를 제어하는 튜닝 매개변수
    • 평균보다 긴 문서는 검색어가 더 자주 등장할 가능성이 있으므로, 최종 수식의 분모에서 불이익을 받음
    • b=0이면 문서 길이 정규화가 꺼지고, b=1이면 완전히 적용됨
    • b는 보통 0.75로 설정됨

BM25의 핵심 아이디어

  • BM25는 Probability Ranking Principle에 기반하지만, 문서 관련성의 진짜 확률을 계산하기는 거의 불가능함
  • 검색에서 중요한 것은 정확한 확률값보다 문서의 순서이므로, 순서에 영향을 주지 않는 항을 수식에서 제거해 계산을 실용화함
  • 이 때문에 BM25는 확률 자체가 아니라 가중치를 계산함
  • Robertson/Sparck Jones Weight는 관련 문서 수와 쿼리 항 포함 문서 수를 사용해 확률을 추정하는 방식임
    • r: 쿼리 항을 포함한 관련 문서 수
    • N: 컬렉션의 전체 문서 수
    • R: 컬렉션의 관련 문서 수
    • n: 쿼리 항을 포함한 문서 수
  • 이 방식은 먼저 어떤 문서가 관련 있는지 알아야 한다는 점이 큰 한계임

“대부분 문서는 관련 없다”는 가정

  • BM25 개발자는 임의의 쿼리에 대해 대부분의 문서가 관련 없다고 가정함
  • 관련 문서 수가 무시할 만큼 작다고 보면 R = r = 0으로 둘 수 있음
  • 이 값을 Robertson/Sparck Jones Weight 수식에 대입하면 BM25에서 쓰는 IDF 항과 거의 같은 형태가 나옴
  • 관련성 정보를 미리 요구하지 않으면서도 같은 이론적 기반을 유지했기 때문에 BM25가 훨씬 실용적이 됨
  • Victor Lavrenko는 이를 "very impressive leap of faith"라고 표현함

BM25 점수 비교의 범위

  • BM25 점수는 일반적으로 직접 비교하기 어려움
    • 0에서 1 사이의 확률 점수를 만들지 않음
    • 문서가 관련 있을 실제 확률을 추정하려는 알고리듬도 아님
    • 특정 컬렉션 안에서 쿼리에 대한 관련 가능성 순서를 근사하는 데 초점을 둠
  • 더 높은 BM25 점수는 문서가 더 관련 있을 가능성이 크다는 신호지만, 실제 관련 확률은 아님
  • 같은 문서 컬렉션 안의 같은 문서에 대해서는 여러 쿼리의 BM25 점수를 비교할 수 있음
    • BM25가 각 쿼리 항 점수를 합산하므로, 두 쿼리 항의 점수 비교와 두 전체 쿼리의 점수 비교 사이에 의미상 차이가 없다고 볼 수 있음
  • 중요한 제약은 같은 문서, 같은 컬렉션임
    • BM25는 컬렉션 안의 IDF와 평균 문서 길이를 사용함
    • 컬렉션이 변경되면 점수가 달라질 수 있어 시간에 걸친 점수 비교는 보장되지 않음
  • 개인화 콘텐츠 피드에서는 각 사용자 관심사별로 전체 텍스트 검색을 실행하고 BM25 점수를 비교해, 어떤 콘텐츠가 어떤 관심사에 더 잘 맞는지 판단하는 데 사용할 수 있음

더 읽을 자료

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 일반 검색에는 https://typesense.org/를 쓰고 있는데, 이제 하이브리드 검색도 지원하니 써본 사람이 있는지 궁금함

    • 하이브리드 검색에 써봤고 꽤 잘 동작함
      Typesense가 여기서 언급되는 걸 보니 반갑고, 작은 규모의 RAG 프로젝트에는 잘 맞는 경우가 많을 텐데 이상하게 덜 알려진 편임
      배포가 쉽고, 기본값도 합리적이며, 문서도 좋고, 클러스터링도 쉬운 편인데, 더 깊게 파고들 필요가 있을 때도 충분히 성능 좋고 강력함
    • 우리도 쓰고 있고 대체로 만족함
      다만 임베딩 모델을 외부 제공자로 쓰면 지연 시간이 500ms+ 로 터무니없이 높아서, 클러스터 안에서 직접 호스팅하는 편이 좋음
      하이브리드 검색 품질은 좋지만 조정 옵션이 매우 제한적이고, 점수도 결과 집합 내부의 순위 매기기 외에는 꽤 불투명함

  • 최근 벡터 기반 의미 검색이 발전한 상황에서, 요즘 키워드 + 의미 검색 하이브리드에 쓰는 최신 검색 스택은 무엇인지 궁금함

    • 범용 검색 전략은 실제로 목표로 하는 작업에 따라 완전히 달라짐
      최근 자유 서술 필드가 10개씩 있는 설문 약 300만 건을 받아, 회사가 조치해야 할 만한 항목을 찾아야 했음
      작은 분류기 모델 몇 개를 쓰고, 처음 1만 건에서 드러난 노이즈를 보고 흔한 단어를 수동으로 제거한 뒤, 모델 응답에 가중치를 줬더니 거의 완벽하게 동작함
      이런 건 “프로그래밍”이라기보다 여러 도구의 블랙박스 출력을 테스트 케이스와 고객에게 좋아 보일 때까지 조정하는 일에 가까움
      참고로 작은 서버에서 Node.js로 여러 Hugging Face 소형 모델을 이어 붙여 처리했음
    • 상용 및 오픈소스 하이브리드 검색 제품 대부분은 BM25 + 임베딩 기반 벡터 유사도 검색을 쓰는 듯함
      결과는 보통 상호 순위 융합(RRF) 으로 합침
      RRF 논문은 놀라울 정도로 단순해서 인상적이고, 논문도 2쪽뿐임: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
    • 하나의 스택에만 집중하지 말고, 작업마다 가장 맞는 도구를 쓸 준비를 해야 함
      BM25류 작업에는 Elasticsearch, 단순하고 빠른 벡터 검색에는 Turbopuffer, 특정 질의 결과를 미리 계산하거나 가격처럼 자주 바뀌는 동적 속성에는 Redis도 쓸 수 있음
      이런 것들을 scatter/gather 방식으로 결합하는 게 좋다고 봄
      검색 스택 바깥에는 거의 항상 재순위를 위한 추론 서비스 계층이 있고, 이상적으로는 다른 머신러닝 인프라와 비슷한 단순한 서비스가 됨
      사용자 질의를 이해해서 “ID로 조회”는 한 시스템으로, “퍼지 의미 검색”은 다른 시스템으로 보내는 식의 라우팅도 거의 항상 필요함
      이들은 데이터 구조가 아주 다르고, 검색은 대체로 서로 다른 사용 사례를 넓게 포괄함
      모든 일을 한 시스템에 밀어 넣는 건 안티패턴이라고 봄
      각 시스템은 각기 다른 작업 부하에 맞고, 내장 추론 기능은 머신러닝 엔지니어들이 익숙한 일반 머신러닝 도구의 속도를 따라잡기 어렵다
      Elasticsearch Learning to Rank로 해봤지만 가망 없는 작업이었음
      그래도 넓은 사용 사례를 하나의 스택으로 풀려는 시도 중에는 Vespa가 아마 가장 나음
    • BM25를 다룬 훌륭한 글임
      txtai 작성자로서, txtai는 Python에서 arrays 패키지를 통해 성능 좋은 BM25 색인을 구현하고, 용어 빈도 벡터를 SQLite에 저장함
      txtai의 하이브리드 색인 방식은 BM25 점수가 정규화되어 있으면 볼록 결합을, 정규화되어 있지 않으면 상호 순위 융합(RRF) 을 지원함
      [1] https://github.com/neuml/txtai
      [2] https://neuml.hashnode.dev/building-an-efficient-sparse-keyw...
      [3] https://neuml.hashnode.dev/benefits-of-hybrid-search
      [4] https://github.com/neuml/txtai/blob/master/src/python/txtai/...
    • Langroid[1] LLM 라이브러리에는 DocChatAgent[2] 안에 깔끔하고 확장 가능한 RAG 구현이 있음
      어휘 기반 검색(bm25, 퍼지 검색), 의미 검색(임베딩), 재순위화(cross-encoder, 상호 순위 융합), 다양성 확보와 lost-in-the-middle 완화를 위한 재순위화까지 여러 검색 기법을 사용함
      [1] Langroid - CMU/UW-Madison 연구자들이 만든 멀티 에이전트 LLM 프레임워크 https://github.com/langroid/langroid
      [2] DocChatAgent 구현 -
      https://github.com/langroid/langroid/blob/main/langroid/agen...
      answer_from_docs 메서드에서 시작해서 따라가면 됨
      덧붙여 Kadoa 창업자라면, Kadoa-snack은 LLM 관련 HN 토론을 찾는 데 매일 즐겨 쓰는 도구 중 하나임

  • 좋은 글임
    좀 더 찾기 어려운 배경을 덧붙이면, BM25는 “Best Matching 25”의 약자이고, “best matching”은 질의의 용어와 문서의 용어를 맞춰 순위와 용어 가중치를 매기는 공식이라는 뜻임
    25는 단순한 일련번호로, 앞서 24개의 공식 변형이 있었고 이후 변형도 있었지만 25번이 가장 잘 동작해서 발표된 것임
    Stephen Robertson과 Karen Spärck Jones(IDF로 유명함)가 고안했고, Robertson의 OKAPI 정보 검색 연구 시스템에 처음 구현됨
    OKAPI 시스템은 미국 NIST의 연례 TREC(Text Retrieval Conference)에서 여러 해 동안 벤치마크되었고, 이는 검색 엔진 방법론의 국제적인 “세계 선수권”에 가까움
    다만 이 행사는 우승보다 비교와 상호 학습이 목적이며, 매년 11월 메릴랜드 Gaithersburg에서 열리는 추천할 만한 행사임
    “단어 주머니” 벡터 공간 모델(용어의 희소 벡터), BM25가 속한 확률 모델 외에도, 질의가 주어졌을 때 문서 집합의 순위를 매기는 이론적 틀은 놀랄 만큼 많고 계속 늘고 있음
    예를 들어 무작위성으로부터의 발산, 통계적 언어 모델링, Learning to Rank, 양자 정보 검색, 신경망 순위화 등이 있음
    ICTIR나 SIGIR 같은 학회에서는 지금도 가끔 완전히 새로운 검색 패러다임이 나옴
    여기서 “통계적 언어 모델링”은 요즘 유행하는 대규모 언어 모델을 뜻하지 않고, 그쪽은 “신경망 검색” 범주에 들어감
    또 “Quantum IR”을 검색하면 양자 정보 검색 튜토리얼이 아니라 적외선 분광법이나 같은 이름의 시멘트 회사를 보게 될 수 있음
    21세기에도 검색 기술은 이런 미묘함이 있음
    BM25와 대안을 직접 비교해보고 싶다면 University of Glasgow에서 개발한 오픈소스 검색 엔진이자 연구 플랫폼인 Terrier를 추천함
    BM25는 25년이 넘었지만 여전히 넘기 어려운 기준선으로 입증됐고, 새 방법을 비교할 때 기준점으로 자주 쓰임
    더 최근 변형인 BM24F는 제목, 본문, 하이퍼링크 같은 여러 필드와 하이퍼텍스트를 다룰 수 있음
    추천 논문은 Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36(6): 779–808 및 후속 Part 2임
    안타깝게도 오픈 액세스는 아님

    • 공교롭게도 US NIST TREC가 지금 열리고 있음
      18일에 시작해서 22일에 끝남
      자세한 내용: https://trec.nist.gov/
    • BM24F에 대한 자료가 더 있는지 궁금함
      Google과 Google Scholar로 찾아봐도 관련 내용을 찾지 못했음

  • 부끄럽지만 홍보함: https://github.com/jankovicsandras/plpgsql_bm25
    https://github.com/jankovicsandras/bm25opt

    • 취미 프로젝트를 부끄럼 없이 홍보하는 흐름이라면, SearchArray는 Google Colab에서 이것저것 만져볼 때 전체 텍스트(BM25) 검색을 위한 pandas 확장임
      https://github.com/softwaredoug/searcharray
      비슷한 목표로 매우 인기 있는 Xing Han Lu의 BM25S도 같이 홍보함
      https://github.com/xhluca/bm25s
    • 어제 작은 사이드 프로젝트에 BM25를 추가할 생각을 하고 있었는데 타이밍 좋은 홍보였음
      많은 텍스트와 PDF 문서를 관리하기 위한 순수 Python 래퍼 프로젝트가 있는지 궁금함
      Solr나 ElasticSearch를 생각했지만 지금 하려는 일에는 너무 무거워 보임
      SQLite가 BM25를 쓰니 pysqlite3와 PyPDF2를 함께 쓰는 방안을 고려 중임
      주제에서 조금 벗어나지만, 하이브리드 BM25 / 벡터 저장소 / LLM 애플리케이션을 만들 도구를 찾는 사람이 많을 것 같음

  • 문서 길이 정규화에서 말하는 평균 문서 길이가 중앙값인지 궁금함
    지나치게 긴 문서의 가중치를 제대로 낮추려면 중앙값이어야 할 것 같은데, 아니면 너무 긴 문서가 평균을 부당하게 끌어올리지 않나 싶음

    • Lucene 기준으로는 산술평균임
      중앙값을 쓰는 것도 흥미로운 실험이 될 듯함
      문서 길이 차이가 아주 큰 검색 데이터셋을 알고 있는지 궁금함
      예를 들어 MSMarco는 길이가 꽤 일정한 편임

  • 좋은 글임
    이런 문제를 수학적 형태로 생각하는 법과 이를 테스트하는 법을 진심으로 배우고 싶은데, 참고할 만한 자료가 있을까?

  • 하이브리드 검색은 검색 결과 관련성의 오래된 과제를 해결함
    키워드와 벡터 사이의 순위 융합을 쓰면 대부분의 상황에서 동작하는 하이브리드 검색을 만들 수 있음

  • BM25는 1970년대에 개발된 오래된 알고리즘임
    기본적으로 조악한 통계 모델이고, 요즘 통계학자들은 훨씬 더 잘할 수 있음
    검색은 학습 기반 방법에 엄격히 지배된다고 봄
    물론 학습은 검색을 입력으로 쓸 수 있음
    아직 이를 깨닫지 못했거나, 오래된 기술을 가능한 한 오래 유지할 유인이 있는 사람이 많지만, 시장 압력이 결국 바꿀 것임

    • 그 시장 압력이라는 게 Google이 잘 동작하던 오래된 검색 기술을 버리거나 용도 변경하고, 반짝이는 새 머신러닝 기반 검색으로 옮기게 만든 바로 그 압력인가?
      그 기술 때문에 적대적 SEO 전쟁을 피하려고 검색어마다 “+reddit”을 붙이게 된 것 아닌가?
      오래됐다고 나쁜 건 아님
      어떤 발명이나 발견, 기법의 나이보다 유용성을 봐야 하는데, 나이에 집착하는 이상한 기술주의적 태도가 걱정됨
    • BM25가 1970~80년대 초기 연구, 특히 확률적 순위 원리 위에서 나왔다는 점은 맞지만, 몇 가지가 궁금함
      실제 애플리케이션에서 BM25를 대체할 만큼 우월하다고 보는 구체적인 현대 통계적 접근은 무엇인가?
      특히 BM25가 명시적으로 다루려 했던 희귀 용어와 문서 길이 정규화 같은 경계 사례를 어떻게 처리하는지 궁금함
      학습 기반 접근이 인상적인 결과를 보인 데는 동의하지만, 검색이 학습 방법에 “엄격히 지배된다”는 말이 정확히 무엇을 뜻하는지도 더 듣고 싶음
      특정 벤치마크를 말하는 건지, 실제 운영 사례를 말하는 건지 궁금함
    • 꽤 매운 견해임
      많은 검색 전문가들은 동의하지 않을 것 같음
      David Tippet(전 OpenSearch, 현 Github)과 Nicolay Gerold의 훌륭한 팟캐스트 제목이 이렇다:
      “BM25 is the workhorse of search; vectors are its visionary cousin”
      https://www.youtube.com/watch?v=ENFW1uHsrLM
    • “새로운 것”을 팔려는 유인도 분명 있음
      검색 분야에는 내가 일해온 내내 수많은 유행과 AI 관련 기술이 있었음
      지금은 막대한 VC 투자를 받은 벡터 검색 회사들이 기술 에반젤리스트 군단을 앞세워 특정 관점을 밀고 있음
      반면 Google 같은 곳에서 “의미 검색”을 실제로 움직이는 수작업 큐레이션과 기본적이고 지루한 수작업 분류 체계의 양은 엄청남
      다만 그런 것들은 섹시하지 않아서 컨퍼런스에서 별로 이야기되지 않을 뿐임
답변달기