확률적 검색 엔진 구축하기: 베이지안 BM25와 하이브리드 검색

현대 검색 시스템은 근본적인 과제에 직면해 있습니다. 어휘 매칭(정확한 키워드 검색)과 의미적 이해(의미 기반 유사도)를 어떻게 결합할 것인가? 이 글에서는 Cognica Database에서 기존 BM25 점수를 보정된 확률로 변환하여 텍스트 검색과 벡터 검색 결과의 근본적인 결합을 가능하게 하는 확률적 랭킹 프레임워크를 어떻게 구축했는지 살펴봅니다.

표준 BM25 점수의 문제점

BM25(Best Matching 25)는 텍스트 검색 랭킹의 사실상 표준입니다. 그러나 이 알고리즘은 중대한 한계가 있습니다. 바로 점수가 해석 가능하지 않고 상대적인 크기 비교에만 사용할 수 있다는 점입니다.

다음 검색 결과를 살펴보겠습니다:

12.34라는 점수는 실제 관련성에 대해 아무것도 말해주지 않습니다. 이 문서가 관련 있을 확률이 90%인가요? 50%인가요? 점수는 다음 요소에 따라 달라집니다:

• 쿼리 길이: 더 많은 용어가 더 높은 점수를 생성
• 컬렉션 통계: IDF는 말뭉치 크기에 따라 변동
• 문서 길이: 정규화 계수에 영향

이는 여러 신호를 결합하는 하이브리드 검색 시스템을 구축할 때 심각한 문제가 됩니다.

다중 신호 결합의 과제

현대 검색 엔진은 여러 랭킹 신호를 결합합니다:

$$\text{FinalScore} = f(\text{text\_relevance}, \text{semantic\_similarity}, \text{freshness}, \text{popularity}, \ldots)$$

신호들의 스케일과 분포가 다르면 단순한 결합은 실패합니다:

단순 덧셈 (BM25가 절대적):

$$\text{final} = \underbrace{12.34}_{\text{BM25}} + \underbrace{0.85}_{\text{vector}} + \underbrace{0.92}_{\text{fresh}} = 14.11$$

단순 곱셈 (여전히 절대적):

$$\text{final} = 12.34 \times 0.85 \times 0.92 = 9.65$$

BM25 점수가 다른 정규화된 신호들을 압도합니다. 보다 근본적인 해결 방법이 필요합니다.

Reciprocal Rank Fusion(RRF)을 쓰지 않는 이유

하이브리드 검색에 대한 일반적인 접근 방식은 점수가 아닌 순위를 결합하는 Reciprocal Rank Fusion (RRF)입니다:

$$\text{RRF}(d) = \sum_{r \in R} \frac{1}{k + \text{rank}_r(d)}$$

여기서 $k$는 Smoothing 상수입니다 (일반적으로 60).

RRF는 단순하고 견고하지만 중요한 한계가 있습니다:

1. 점수 크기를 버림: 점수 0.99로 1위인 문서와 점수 0.51로 1위인 문서가 동일하게 취급됩니다. 신뢰도 정보가 손실됩니다.

2. 별도의 검색 단계 필요: 각 시스템에서 독립적으로 top-k를 검색한 다음 병합해야 합니다. 이는 공동 최적화를 방해합니다.

3. WAND/BMW 최적화 활용 불가: WAND, BMW 같은 점수 기반 가지치기 알고리즘이 순위 기반 융합에서는 작동하지 않습니다.

4. k 파라미터에 민감: Smoothing 상수 $k$가 결과에 크게 영향을 미치지만 원칙적인 튜닝 방법이 없습니다.

5. 확률적 해석 불가: 결합된 점수는 아무런 의미도 없습니다. 단지 휴리스틱한 숫자 연산의 결과일 뿐입니다.

우리의 확률적 접근 방식은 점수를 확률 이론을 사용해 결합할 수 있는 보정된 확률로 변환함으로써 이러한 한계를 해결합니다.

해결책: 베이지안 BM25

우리는 베이지안 추론을 사용하여 BM25 점수를 보정된 확률로 변환합니다. 핵심 통찰은 관련성을 잠재 변수로 취급하고 관찰된 BM25 점수가 주어졌을 때 관련성의 사후 확률을 계산하는 것입니다.

수학적 프레임워크

베이즈 정리에서 시작합니다:

$$P(\text{relevant} \mid s) = \frac{P(s \mid \text{relevant}) \cdot P(\text{relevant})}{P(s)}$$

우도를 시그모이드 함수로 모델링합니다:

$$P(s \mid \text{relevant}) = \sigma(\alpha \cdot (s - \beta)) = \frac{1}{1 + e^{-\alpha(s - \beta)}}$$

여기서:

• $\alpha$: 시그모이드 기울기 제어 (점수 민감도)
• $\beta$: 시그모이드 중심점 제어 (관련성 임계값)

아키텍처 개요

복합 사전 확률 설계

균일 사전 확률 대신, 용어 빈도와 문서 길이를 모두 고려하는 복합 사전 확률을 통해 도메인 지식을 통합합니다:

용어 빈도 사전 확률 (가중치: 0.7):

$$P_{\text{tf}}(f) = 0.2 + 0.7 \cdot \min\left(1, \frac{f}{10}\right)$$

용어 빈도가 높은 문서는 관련성의 사전 확률이 높습니다.

필드 정규화 사전 확률 (가중치: 0.3):

$$P_{\text{norm}}(n) = 0.3 + 0.6 \cdot \left(1 - \min(1, |n - 0.5| \cdot 2)\right)$$

너무 짧지도 너무 길지도 않은 문서가 더 높은 사전 확률을 가집니다.

복합 사전 확률은 다음과 같습니다:

$$P_{\text{prior}} = 0.7 \cdot P_{\text{tf}} + 0.3 \cdot P_{\text{norm}}$$

극단적인 사전 확률이 사후 확률을 왜곡하는 것을 방지하기 위해 $[0.1, 0.9]$ 범위로 교정합니다.

사후 확률 계산

최종 사후 확률 공식은 베이즈 정리에서 유도됩니다. 다음을 정의합니다:

• $L = P(s \mid R) = \sigma(\alpha(s - \beta))$를 우도로
• $p = P(R)$를 사전 확률로

그러면:

$$P(R \mid s) = \frac{L \cdot p}{L \cdot p + (1 - L) \cdot (1 - p)}$$

구현:

float compute_posterior_probability_(float score, float prior) const {
  auto likelihood = 1.0f / (1.0f + std::exp(-alpha_ * (score - beta_)));
  auto joint_probability = likelihood * prior;
  auto complement_joint_probability = (1.0f - likelihood) * (1.0f - prior);
  return joint_probability / (joint_probability + complement_joint_probability);
}

이것은 모든 BM25 점수를 $[0, 1]$ 범위의 확률로 변환합니다.

수학적 속성:

1. 출력 범위: 항상 $(0, 1)$
2. 단조성: 더 높은 BM25 점수가 더 높은 사후 확률을 산출 ($\alpha > 0$일 때)
3. 사전 확률 영향: 사전 확률이 결정 경계를 이동
4. 보정: 적절한 $\alpha, \beta$로 출력이 실제 관련성 확률에 근사

표준 BM25 구현

베이지안 변환을 살펴보기 전에, 먼저 BM25 구현을 살펴 봅시다.

고전적인 BM25 공식

$$\text{score}(D, Q) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{f(t, D) \cdot (k_1 + 1)}{f(t, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}$$

여기서:

• $f(t, D)$: 문서 $D$에서 용어 $t$의 출현 빈도
• $|D|$: 문서 길이 (용어 수)
• $\text{avgdl}$: 컬렉션의 평균 문서 길이
• $k_1 = 1.2$: 용어 빈도 포화 파라미터
• $b = 0.75$: 문서 길이 정규화 파라미터

단조성 보존 구현

수학적으로 동등하지만 수치적으로 안정적인 형태를 사용합니다:

$$\text{score} = w - \frac{w}{1 + f \cdot \text{inv\_norm}}$$

여기서:

$$\text{inv\_norm} = \frac{1}{k_1 \cdot \left((1 - b) + b \cdot \frac{\text{norm}}{\text{avgdl}}\right)}$$

그리고 $w = \text{boost} \cdot \text{IDF}$입니다.

float score(float freq, float norm) const {
  // 단조성 보존 재작성:
  // freq / (freq + norm) = 1 - 1 / (1 + freq * (1 / norm))
  auto inv_norm = 1.f / (k1_ * ((1.f - b_) + (b_ * norm / avg_doc_size_)));
  return weight_ - weight_ / (1.f + freq * inv_norm);
}

이 재작성은 다음을 보장합니다:

• 용어 빈도에 대해 단조 증가: $f_1 > f_2 \implies \text{score}(f_1, n) \geq \text{score}(f_2, n)$
• 문서 길이에 대해 단조 감소: $n_1 > n_2 \implies \text{score}(f, n_1) \leq \text{score}(f, n_2)$

IDF 계산

Robertson-Sparck Jones IDF 공식을 사용합니다:

$$\text{IDF}(t) = \ln\left(\frac{N - \text{df}(t) + 0.5}{\text{df}(t) + 0.5} + 1\right)$$

여기서:

• $N$: 컬렉션의 전체 문서 수
• $\text{df}(t)$: 문서 빈도 (용어 $t$를 포함하는 문서 수)

float compute_idf(int64_t doc_freq, int64_t doc_count) const {
  auto idf = std::log((static_cast<float>(doc_count - doc_freq) + 0.5f)
                          / (static_cast<float>(doc_freq) + 0.5f)
                      + 1);
  return idf;
}

IDF 속성:

• 희귀 용어 (낮은 $\text{df}$)는 높은 IDF를 받음
• 흔한 용어 (높은 $\text{df}$)는 낮은 IDF를 받음
• $+1$ Smoothing이 IDF가 항상 양수임을 보장

문서 길이 정규화

정규화 계수는 스코어링 시점에 적용됩니다:

$$\text{norm\_factor} = k_1 \cdot \left((1 - b) + b \cdot \frac{|D|}{\text{avgdl}}\right)$$

WAND와 BMW 최적화

효율적인 top-k 검색을 위해 WAND (Weak AND)와 BMW (Block-Max WAND) 알고리즘을 모두 구현했습니다.

WAND 알고리즘

WAND는 용어 수준의 상한을 사용하여 결과 집합에 들어갈 수 없는 문서를 건너뜁니다:

상한 계산:

BM25의 경우, 용어 빈도의 무한대 극한이 상한이 됩니다:

$$\text{upper\_bound} = \lim_{f \to \infty} \text{score}(f, n) = w = \text{boost} \cdot \text{IDF}$$

WAND 가지치기 조건:

$$\sum_{i=0}^{\text{pivot}} \text{upper\_bound}_i < \theta \implies \text{다음 피벗으로 건너뛰기}$$

여기서 $\theta$는 현재 $k$번째로 높은 점수입니다.

BMW (Block-Max WAND) 알고리즘

BMW는 용어 수준 상한 대신 블록 단위 상한을 사용하여 WAND를 개선합니다. 포스팅 리스트는 128개 문서 블록으로 나뉘고, 각 블록 내의 최대 점수가 사전 계산됩니다.

WAND와의 주요 차이점:

자동 선택:

bool use_bmw = false;
if (avg_posting_size <= 250) {
  use_bmw = true;  // 작은 리스트에서 BMW가 항상 승리
} else if (avg_posting_size <= 1000) {
  use_bmw = true;  // BMW가 7-17% 빠름
} else if (avg_posting_size <= 5000) {
  use_bmw = (num_terms <= 3);  // 적은 용어에 BMW
} else {
  use_bmw = false;  // 매우 큰 리스트에는 WAND
}
if (k >= 100) {
  use_bmw = true;  // 큰 k에서 BMW가 37% 빠름
}

블록 인덱스 캐싱

BMW는 오버헤드를 최소화하기 위해 캐시 우선 블록 조회를 사용합니다:

void update_block_info(size_t term_index) {
  auto doc_id = states_[term_index].current_doc;

  // 1. 캐시된 블록 확인 (O(1) - 빠른 경로, ~99% 적중률)
  auto cached_idx = current_block_indices_[term_index];
  if (blocks_[term_index][cached_idx].contains(doc_id)) {
    return;  // 여전히 같은 블록에 있음
  }

  // 2. 다음 블록 확인 (O(1) - 순차 접근에서 일반적)
  if (blocks_[term_index][cached_idx + 1].contains(doc_id)) {
    current_block_indices_[term_index] = cached_idx + 1;
    return;
  }

  // 3. 캐시 미스 시에만 이진 탐색 (O(log B) - 드묾)
  auto block_idx = find_block_index(term_index, doc_id);
  current_block_indices_[term_index] = block_idx;
}

벡터 검색 통합

Cognica Database는 벡터 검색을 위해 HNSW (Hierarchical Navigable Small World)를 사용합니다.

거리에서 점수로 변환

벡터 검색은 거리를 반환하며, 이를 유사도 점수로 변환합니다:

$$\text{score} = 1 - \text{distance}$$

auto score() const -> std::optional<float> {
  auto index = disi_->index();
  auto dist = distances_.get()[index];
  return 1.f - dist;
}

코사인 거리 (범위 $[0, 2]$)의 경우:

하이브리드 검색: 모든 것을 하나로

이제 근본적인 점수 결합으로 텍스트 검색과 벡터 검색을 의미를 유지한 채 결합할 수 있습니다.

쿼리 처리 파이프라인

확률적 점수 결합

논리곱 (AND) - 독립 사건:

확률적 스코어러의 경우, 확률 곱셈 법칙을 사용합니다:

$$P(A \land B \land C) = P(A) \cdot P(B) \cdot P(C)$$

수치 안정성을 위해 로그 공간에서 계산합니다:

$$P(\text{AND}) = \exp\left(\sum_{i} \ln(p_i)\right)$$

auto score_prob_() const -> std::optional<float> {
  auto log_probability = 0.0f;
  for (const auto& scorer : scorers_) {
    auto score = scorer->score();
    if (!score.has_value()) {
      return std::nullopt;
    }
    auto prob = std::clamp(score.value(), 1e-10f, 1.0f - 1e-10f);
    log_probability += std::log(prob);
  }
  return std::exp(log_probability);
}

논리합 (OR) - 독립 사건:

$$P(A \lor B \lor C) = 1 - P(\neg A) \cdot P(\neg B) \cdot P(\neg C) = 1 - \prod_{i}(1 - p_i)$$

로그 공간에서 계산합니다:

$$P(\text{OR}) = 1 - \exp\left(\sum_{i} \ln(1 - p_i)\right)$$

auto score_prob_() const -> std::optional<float> {
  auto log_complement_sum = 0.f;
  auto has_valid_scorer = false;

  for (const auto& scorer : scorers_) {
    if (scorer->doc_id() == disi_->doc_id()) {
      auto score_opt = scorer->score();
      if (score_opt.has_value()) {
        auto prob = std::clamp(score_opt.value(), 1e-10f, 1.0f - 1e-10f);
        log_complement_sum += std::log(1.0f - prob);
        has_valid_scorer = true;
      }
    }
  }

  if (!has_valid_scorer) {
    return std::nullopt;
  }
  return 1.0f - std::exp(log_complement_sum);
}

모드 선택

프레임워크는 확률적 모드와 비확률적 모드를 모두 지원합니다:

점수 결합 예시

텍스트와 벡터 쿼리 모두에 매칭되는 문서를 고려해 봅시다:

논리곱 (MUST 용어):

$$P_{\text{must}} = 0.78 \times 0.72 = 0.56$$

논리합 (MUST + SHOULD):

$$P_{\text{final}} = 1 - (1 - 0.56)(1 - 0.85) = 1 - 0.44 \times 0.15 = 0.934$$

파라미터 학습

시그모이드 파라미터 ($\alpha$, $\beta$)는 교차 엔트로피 손실을 최소화하여 관련성 판단으로부터 학습할 수 있습니다:

$$\mathcal{L}(\alpha, \beta) = -\sum_{i=1}^{n} \left[ y_i \log(\hat{y}_i) + (1 - y_i) \log(1 - \hat{y}_i) \right]$$

여기서 $\hat{y}_i = \sigma(\alpha(s_i - \beta))$이고 $y_i$는 실제 관련성 레이블입니다.

그래디언트:

$$\frac{\partial \mathcal{L}}{\partial \alpha} = \sum_{i=1}^{n} (\hat{y}_i - y_i) \cdot (s_i - \beta) \cdot \hat{y}_i \cdot (1 - \hat{y}_i)$$ $$\frac{\partial \mathcal{L}}{\partial \beta} = -\sum_{i=1}^{n} (\hat{y}_i - y_i) \cdot \alpha \cdot \hat{y}_i \cdot (1 - \hat{y}_i)$$

void update_parameters(const std::vector<float>& scores,
                       const std::vector<float>& relevances) {
  auto num_iterations = 1000;
  auto learning_rate = 0.01f;

  auto alpha = 1.0f;
  auto beta = scores[scores.size() / 2];  // 중앙값 점수로 초기화

  for (auto i = 0; i < num_iterations; ++i) {
    auto alpha_gradient = 0.0f;
    auto beta_gradient = 0.0f;

    for (auto j = 0uz; j < scores.size(); ++j) {
      auto pred = 1.0f / (1.0f + std::exp(-alpha * (scores[j] - beta)));
      auto error = pred - relevances[j];

      alpha_gradient += error * (scores[j] - beta) * pred * (1 - pred);
      beta_gradient += -error * alpha * pred * (1 - pred);
    }

    alpha -= learning_rate * alpha_gradient / scores.size();
    beta -= learning_rate * beta_gradient / scores.size();
  }

  auto guard = std::scoped_lock {lock_};
  alpha_ = alpha;
  beta_ = beta;
}

성능 고려사항

계산 오버헤드

가지치기 효율성

WAND (다양한 리스트 크기):

• 500 docs, 2 terms: 50.5% 문서 건너뜀
• 500 docs, 5 terms: 79.9% 문서 건너뜀
• 1000 docs, 2 terms: 62.5% 문서 건너뜀

BMW (다양한 리스트 크기):

• 500 docs, 2 terms: 77.6% 문서 건너뜀
• 500 docs, 5 terms: 88.1% 문서 건너뜀
• 1000 docs, 2 terms: 84.1% 문서 건너뜀

BMW는 중소형 리스트에서 WAND보다 50-100% 더 나은 가지치기 효율성을 달성합니다.

사용 가능한 Similarity

결과 및 영향

베이지안 BM25와 BMW 최적화를 통해 다음을 달성했습니다:

1. 해석 가능한 점수: 출력이 $[0, 1]$ 범위의 실제 확률
2. 근본적인 결합: 텍스트와 벡터 점수가 확률 이론을 사용해 자연스럽게 결합
3. 순위 보존: BM25와 동일한 상대적 순서
4. WAND/BMW 호환성: 확률적 변환이 상한 유효성을 보존
5. 온라인 학습: 파라미터가 말뭉치 특성에 적응
6. 효율적인 가지치기: BMW가 77-88% 문서 건너뛰기율 달성

결론

관련성을 확률적 추론 문제로 취급함으로써, BM25를 무한대로 발산할 수 있는 스코어링 함수에서 보정된 확률 추정기로 변환했습니다. 이를 통해 기존 정보 검색 알고리즘의 WAND/BMW 등의 최적화를 그대로 유지하면서 벡터 검색 및 기타 랭킹 신호와의 근본적인 결합이 가능해졌습니다.

핵심 통찰:

• 시그모이드 변환이 비경계 점수를 $[0, 1]$로 매핑
• 복합 사전 확률이 외부 훈련 데이터 없이 도메인 지식을 통합
• 로그 공간 연산이 극단적인 확률에 대한 수치 안정성 보장
• BMW 최적화가 일반적인 워크로드에서 WAND 대비 20-43% 속도 향상 제공
• 확률적 결합이 점수 크기 정보를 보존하여 RRF보다 정확하고 해석 가능한 결과 제공

이 프레임워크는 Cognica Database의 하이브리드 검색 기능의 핵심 구성 요소이며, 프로덕션 워크로드에 필요한 효율성을 유지하면서 정교한 다중 신호 랭킹을 가능하게 합니다.

---

참고 문헌

• Robertson, S. E., & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond.
• Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.
• Broder, A. Z., et al. (2003). Efficient Query Evaluation using a Two-Level Retrieval Process.
• Ding, S., & Suel, T. (2011). Faster Block-Max WAND with Variable-sized Blocks.
• Cormack, G. V., et al. (2009). Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.