Post

[RAG] 검색 성능을 높이기 위한 알고리즘 분석

Posted
By chanho 52 min read

RAG에 대해 헤딩하면서 검색을 조금 더 정확하고 효율적으로 하기위해 검색 및 랭킹 알고리즘에 대해 알아보게 되었고, 이를 정리하고 기록하고자 한다.

RAG와 검색/랭킹 알고리즘의 역할

RAG는 사용자의 질문이나 프롬프트에 대해 관련성 높은 정보를 먼저 검색하고, 이 정보를 바탕으로 언어 모델이 답변을 생성하는 방식이다. 여기서 검색 및 랭킹 알고리즘은 RAG의 ‘Retrieval’ 단계에서 핵심적인 역할을 수행한다. 즉, 방대한 문서 데이터베이스에서 사용자의 질문과 가장 관련성이 높은 문서를 효율적으로 찾아내고, 그 관련성에 따라 순위를 매기는(Ranking) 기술이다.

랭킹 알고리즘 분류

크게 키워드 기반 희소(Sparse) 검색 알고리즘과 학습 기반(Learning-to-Rank, LTR) 알고리즘으로 나눌 수 있다.

1. 키워드 기반 희소 검색 알고리즘

텍스트 내 단어의 빈도, 분포 등 통계적 정보를 활용하여 문서와 질의(Query) 간의 관련성을 계산한다. 대표적으로 TF-IDF와 BM25가 있다.

가. TF-IDF (Term Frequency-Inverse Document Frequency)

TF-IDF는 문서 내 특정 단어의 중요도를 계산하여, 문서와 질의간의 관련성을 점수화하기 위해 사용한다. 해당 알고리즘의 핵심은 특정 문서 내에서 특정 탄어가 얼마나 자주 등장하는지를 보고 많이 등장할 수록 중요하게 생각하는 TF(단어 빈도)와 특정 단어가 전체 문서 집합 중 얼마나 많은 문서에서 등장하며 여러 문장에 흔하게 등장할수록 중요도를 감소하는 IDF(역 문서 빈도)이다.

TF-IDF의 특징

  • 직관적이고 구현이 비교적 간단하다.
  • 문서 내 특정 단어의 중요도를 효과적으로 반영한다.
  • ‘the’, ‘a’ 와 같은 불용어(stop words)처럼 여러 문서에 자주 나오는 단어의 가중치는 낮아진다.
TF-IDF의 한계

TF-IDF는 단어의 등장 빈도만 고려하므로, 문서의 길이와 단어 빈도의 포화(saturation) 등 이러한 부분을 고려하지 못하므로 이러한 부분에 대한 손실을 가질 수 있다.

수식

1

TF-IDF(t, d, D) = TF(t, d) * IDF(t, D)
  • t: 단어 (Term)
  • d: 특정 문서 (Document)
  • D: 전체 문서 집합 (Document set)
  • 구성 요소 해석
    1. TF(t, d): 단어 빈도 (Term Frequency)
      • 의미: 특정 문서 d 안에서 단어 t가 얼마나 자주 등장하는가?
      • 계산 예시 (단순 빈도): 문서 d 내 단어 t의 등장 횟수. (다양한 정규화 방법 존재: 불린 빈도, 로그 스케일 빈도, 증가 빈도 등)
      • 해석: 한 문서 내에서 특정 단어가 많이 나올수록 그 단어는 해당 문서를 설명할 가능성이 높다고 보고 가중치를 부여한다.
    2. IDF(t, D): 역 문서 빈도 (Inverse Document Frequency)
      • 의미: 전체 문서 D 중에서 단어 t가 얼마나 희귀하게 등장하는가? (즉, 얼마나 많은 문서에 걸쳐 등장하는가?)
      • 계산: log(N / (df(t) + 1))
        • N: 전체 문서의 수 (|D|)
        • df(t): 단어 t를 포함하고 있는 문서의 수 (Document Frequency)
        • +1: df(t)가 0일 때 분모가 0이 되는 것을 방지 (Smoothing)
        • log: 값이 너무 커지는 것을 방지하고 분포를 부드럽게 만든다.
      • 해석: ‘the’, ‘a’ 처럼 여러 문서에 흔하게 등장하는 단어는 구별 능력이 낮다고 판단하여 낮은 가중치(낮은 IDF 값)를 부여하고, 특정 주제의 문서에만 집중적으로 등장하는 단어는 중요하다고 판단하여 높은 가중치(높은 IDF 값)를 부여한다.
  • 최종 점수 해석
    • 어떤 단어가 특정 문서에 자주 등장하고(높은 TF), 전체 문서에서는 드물게 등장할수록(높은 IDF) 그 단어의 TF-IDF 점수는 높아진다. 이 점수는 해당 단어가 그 문서를 대표하는 중요한 키워드일 가능성이 높다는 것을 의미한다.

    ### 나. BM25 (Best Match 25)

    BM25는 TF-IDF의 한계점(문서 길이 미고려, 단어 빈도 영향력의 단순 증가)을 개선하여 문서와 질의 간의 관련성을 더 정교하게 점수화하기 위해 개발된 확률론적 랭킹 함수이다. 현재 많은 검색 엔진 및 정보 검색 시스템에서 표준적인 알고리즘으로 널리 사용되고 있다.

    BM25의 핵심 아이디어 및 개선점

    • 단어 빈도 포화 (Term Frequency Saturation): 문서 내 특정 단어의 빈도(TF)가 높아질수록 관련성 점수도 증가하지만, 일정 수준 이상이 되면 그 증가폭이 점차 둔화되도록 설계되었다. 이는 특정 단어가 비정상적으로 많이 등장했을 때 점수에 과도한 영향을 미치는 것을 방지할 수 있다. (TF-IDF는 TF가 증가하면 점수도 선형적으로 계속 증가하는 경향이 있다.)
    • 문서 길이 정규화 (Document Length Normalization): 문서의 길이를 고려하여 점수를 보정한다. 일반적으로 긴 문서일수록 특정 단어가 등장할 확률 자체가 높기 때문에, 단순히 단어 빈도만 비교하면 긴 문서가 유리해질 수 있다. BM25는 문서 길이를 평균 문서 길이와 비교하여, 평균보다 짧은 문서에서 단어가 등장하면 가중치를 더 부여하고, 긴 문서에서는 덜 부여하여 공정한 비교를 가능하게 한다.

    BM25의 특징

    • TF-IDF에 비해 일반적으로 더 높은 검색 정확도를 제공한다.
    • k1 (TF 포화도 조절)과 b (문서 길이 정규화 강도 조절)라는 파라미터를 제공하여, 사용하는 데이터셋의 특성이나 특정 검색 요구사항에 맞게 알고리즘의 성능을 미세 조정할 수 있는 유연성을 갖는다.
    • 이론적 기반이 탄탄하고 실제 성능이 우수하여 다양한 상용 및 오픈소스 검색 엔진에서 핵심 랭킹 알고리즘으로 채택되어 활용되고 있다.

    BM25의 한계

    • TF-IDF와 마찬가지로 단어의 표면적인 등장 빈도와 분포에 기반한 키워드 매칭 방식이므로, 단어의 의미론적 관계나 문맥(예: 동의어, 다의어, 문장의 전체적인 의미)을 파악하지는 못한다.
    • 최적의 성능을 내기 위해 데이터셋에 맞춰 파라미터 k1과 b를 튜닝하는 과정이 필요할 수 있다.

    수식 (질의 Q와 문서 d 간의 점수)

    1

      Score(Q, d) = Σ [ IDF(qi) * ( f(qi, d) * (k1 + 1) ) / ( f(qi, d) + K ) ]

    변수 설명:

    • Q: 사용자 질의 (Query), 하나 이상의 단어 qi로 구성됨
    • qi: 질의 Q에 포함된 개별 단어
    • d: 관련성을 평가할 대상 문서 (Document)
    • f(qi, d): 문서 d 내에서 단어 qi가 등장한 빈도 (Term Frequency, TF)
    • IDF(qi): 단어 qi의 역 문서 빈도 (Inverse Document Frequency). 전체 문서 집합에서 단어 qi가 얼마나 희귀한지를 나타내는 값입니다. (계산 방식은 TF-IDF와 유사하나 약간의 변형이 있을 수 있다.)
      • 예시: log( (N - n(qi) + 0.5) / (n(qi) + 0.5) + 1 )
      • N: 전체 문서의 총 개수
      • n(qi): 단어 qi를 포함하고 있는 문서의 개수
    • k1: 단어 빈도(TF)의 영향력 및 포화도를 조절하는 파라미터 (양수, 일반적으로 1.2 ~ 2.0 사이 값 사용). k1이 클수록 TF 값의 영향력이 커지고 포화는 더 늦게 일어난다.
    • b: 문서 길이에 따른 점수 정규화 강도를 조절하는 파라미터 (0과 1 사이 값, 일반적으로 0.75 사용). b=0이면 문서 길이 정규화를 사용하지 않고, b=1이면 정규화 효과를 최대로 적용한다.
    • |d|: 문서 d의 길이 (보통 문서 내 총 단어 수)
    • avgdl: 전체 문서 집합의 평균 문서 길이
    • K: 문서 길이(|d|)와 파라미터(k1, b)를 이용하여 계산되는 값으로, TF 점수 조절에 사용된다.
      • K = k1 * (1 - b + b * |d| / avgdl)

    구성 요소 해석

    1. IDF(qi): 역 문서 빈도
      • 의미: 질의 단어 qi가 전체 문서 집합에서 얼마나 희귀하게 등장하는지를 측정한다.
      • 역할: 정보 검색에서 중요도가 낮은 흔한 단어(예: 조사, 관사 등 불용어)의 영향력은 줄이고, 특정 주제를 나타내는 희귀하고 중요한 키워드의 영향력은 높여준다. 점수 계산 시 각 단어의 중요도 가중치 역할을 한다.
    2. TF 관련 부분: ( f(qi, d) * (k1 + 1) ) / ( f(qi, d) + K )
      • 의미: 문서 내 단어 빈도 f(qi, d)를 기반으로 하되, 단어 빈도 포화와 문서 길이 정규화 효과를 함께 적용하여 최종 TF 관련 가중치를 계산한다.
      • 단어 빈도 포화: f(qi, d) 값이 증가하면 이 부분의 값도 증가하지만, 분모에도 f(qi, d)가 포함되어 있어 증가율이 점차 감소하며 특정 값(k1+1에 가까움)으로 수렴(포화)한다. 즉, 단어가 아주 많이 등장해도 점수가 끝없이 비례하여 증가하지 않도록 제어한다. k1 파라미터가 이 포화되는 정도를 조절한다.
      • 문서 길이 정규화 (K 값의 역할):
        • K = k1 * (1 - b + b * |d| / avgdl) 수식을 보면, K 값은 문서 길이 |d|에 따라 변한다.
        • 문서 d가 평균보다 길면 (|d| > avgdl): |d| / avgdl 값이 1보다 커지고, b가 양수이므로 K 값이 커진다. K가 커지면 TF 관련 부분의 분모가 커져서 전체 점수가 낮아진다. (긴 문서에 대한 일종의 페널티 부여)
        • 문서 d가 평균보다 짧으면 (|d| < avgdl): |d| / avgdl 값이 1보다 작아지고, K 값이 작아진다. K가 작아지면 TF 관련 부분의 분모가 작아져서 전체 점수가 높아지게 된다. (짧은 문서에 대한 일종의 보너스 부여)
        • b 파라미터는 이러한 문서 길이에 따른 정규화 효과의 강도를 조절한다.

    최종 점수 해석

    • BM25 점수는 질의 Q에 포함된 각 단어(qi)가 문서 d의 관련성에 얼마나 기여하는지를 (1) 단어의 전체적인 희귀성(IDF), (2) 문서 내에서의 빈도(TF, 단 포화 고려), 그리고 (3) 문서의 상대적인 길이(정규화)를 모두 종합적으로 고려하여 계산한다.
    • 이렇게 각 질의 단어별로 계산된 기여도를 모두 합산(Σ)하여 문서 d와 질의 Q 간의 최종 관련성 점수를 얻는다. 이 점수가 높을수록 해당 문서가 사용자의 질의와 더 관련성이 높다고 판단하여 랭킹 상위에 노출시킨다.

2. 학습 기반 랭킹 알고리즘 (Learning-to-Rank, LTR)

Learning-to-Rank는 기계 학습(Machine Learning)을 사용하여 랭킹 모델 자체를 학습하는 방법이다. 단순히 키워드 매칭 점수뿐만 아니라, 문서의 최신성, 출처의 신뢰도, 사용자 클릭 로그 등 다양한 특징(feature)들을 종합적으로 고려하여 최적의 랭킹 순서를 학습한다.

랭킹 알고리즘 vs LTR:

  • 랭킹 알고리즘: TF-IDF, BM25처럼 특정 규칙이나 공식에 따라 점수를 매기고 순위를 결정하는 개별 알고리즘을 지칭할 수 있다.
  • LTR: 이러한 개별 알고리즘의 점수를 포함한 여러 특징들을 입력으로 받아, 어떤 순서가 “좋은 순서”인지를 데이터로부터 학습하는 방법론 또는 프레임워크이다. RankNet, LambdaRank, LambdaMART는 LTR 방법론에 속하는 구체적인 알고리즘들이다.

가. RankNet

RankNet은 개별 문서의 절대적인 관련성 점수를 예측하는 대신, 두 문서 간의 상대적인 순서(어떤 문서가 다른 문서보다 더 관련성이 높은지)가 올바른지를 확률적으로 모델링하고 학습하는 LTR(Learning-to-Rank) 알고리즘이다. 이는 LTR 방법론 중 Pairwise 접근 방식의 대표적인 예시이다.

RankNet의 핵심 아이디어

  • 주어진 질의(Query)에 대해 관련된 두 문서 쌍(i, j)을 입력받아, “문서 i가 문서 j보다 더 관련성이 높을 확률”을 예측하는 모델을 구축하는 것.
  • 실제 정답 순서(Ground Truth)와 모델의 예측 확률을 비교하여, 모델이 올바른 상대적 순서를 예측하도록 학습시키는 데 초점을 맞춰 절대적인 점수보다는 올바른 랭킹을 만드는 것을 목표로 한다.
RankNet의 학습 목표

학습 데이터에서 잘못된 순서쌍(Inversion Pair), 즉 실제로는 관련성이 더 높은 문서가 모델에 의해 더 낮은 순위로 예측되는 경우를 최소화하는 것을 목표로 한다. 이는 모델이 예측한 순서 확률과 실제 정답 순서 간의 차이(오류)를 줄이는 방향으로 학습이 진행됨을 의미한다.

RankNet의 접근 방식 및 특징

주로 신경망(Neural Network)을 사용하여 각 문서의 특징(Feature)을 입력받아 관련성 점수(s_i)를 출력하는 함수를 모델링한다. 이 점수는 직접적인 랭킹 점수라기보다는 상대적 순서 확률을 계산하기 위한 중간 값이다. 두 문서의 점수 차이(s_i - s_j)를 시그모이드(Sigmoid) 함수에 통과시켜 문서 i가 j보다 관련성이 높을 확률(P_ij)을 계산하며, 크로스 엔트로피(Cross-Entropy) 비용 함수를 사용하여 모델의 예측 확률(P_ij)과 실제 정답 레이블(P̄_ij) 간의 불일치 정도를 측정하고, 이 비용을 최소화하도록 확률적 경사 하강법(SGD) 등의 최적화 알고리즘으로 신경망 모델의 파라미터를 업데이트한다.

  • Pairwise 접근 방식은 Pointwise(개별 문서 점수 예측)나 Listwise(전체 랭킹 리스트 최적화) 방식과 구별되는 LTR의 한 축을 형성한다.
RankNet의 한계

비용 함수가 개별 문서 쌍의 순서 정확도를 최적화할 뿐, NDCG나 MAP과 같은 실제 정보 검색 평가 지표(Ranking Metric)를 직접적으로 최적화하지는 않는다. 따라서 쌍별 정확도가 높아져도 전체 랭킹 리스트의 품질 향상으로 반드시 이어지지 않을 수 있다. 또한 관련된 모든 문서 쌍을 고려해야 하므로 학습 데이터의 크기가 커지고 계산 비용이 높을 수 있다.

핵심 수식 (비용 함수 - Cross Entropy)

1

C_ij = - P̄_ij * log(P_ij) - (1 - P̄_ij) * log(1 - P_ij)
  • C_ij: 단일 문서 쌍 (i, j)에 대한 비용(손실) 값이다. 전체 비용은 모든 관련 쌍에 대한 C_ij의 합 또는 평균이다.

변수 설명

  • i, j: 순서를 비교할 두 개의 문서
  • s_i, s_j: 모델(예: 신경망)이 문서 i와 j의 특징 벡터를 입력받아 출력한 잠재적인 관련성 점수(score). 이 점수 자체가 최종 랭킹 점수는 아니며, 상대 순서 확률 계산에 사용된다. (모델 학습을 통해 이 점수를 출력하는 방식이 업데이트)
  • P_ij: 모델이 예측한 문서 i가 문서 j보다 더 관련성이 높을 확률
    • P_ij = σ(s_i - s_j) = 1 / (1 + exp(-(s_i - s_j)))
    • σ는 시그모이드 함수로, 입력값(점수 차이)을 0과 1 사이의 확률값으로 변환한다.
  • P̄_ij (P bar ij): 문서 쌍 (i, j)에 대한 실제 정답 레이블 (Ground Truth).
    • 일반적으로, 문서 i가 문서 j보다 실제로 더 관련성이 높으면 P̄_ij = 1
    • 문서 j가 문서 i보다 관련성이 높거나 같으면 P̄_ij = 0
  • C_ij: 문서 쌍 (i, j)에 대한 크로스 엔트로피 비용(손실). 모델 예측(P_ij)이 실제 정답(P̄_ij)과 얼마나 다른지를 측정하며, 이 값을 최소화하는 것이 학습 목표이다.

수식 해석

  1. 모델의 예측 점수 및 확률 계산 (s_i, s_j → P_ij)
    • 모델은 각 문서(i, j)의 특징을 바탕으로 점수(s_i, s_j)를 계산한다.
    • 두 점수의 차이(s_i - s_j)를 계산하여 문서 i가 j보다 얼마나 더 관련성이 높다고 모델이 판단하는지를 나타낸다.
    • 이 점수 차이를 시그모이드 함수(σ)에 넣어 0과 1 사이의 확률값 P_ij로 변환한다. s_i가 s_j보다 훨씬 크면 P_ij는 1에 가까워지고, s_j가 훨씬 크면 0에 가까워진다. 점수가 비슷하면 0.5에 가까워지게 된다.
  2. 크로스 엔트로피 비용 계산 (C_ij)
    • 이 비용 함수는 모델의 예측 확률(P_ij)이 실제 정답 레이블(P̄_ij)과 얼마나 다른지를 측정하여 벌점(Penalty)을 부여한다.
    • Case 1: 실제로는 i가 j보다 관련성이 높을 때 (P̄_ij = 1)
      • 모델이 올바르게 예측하여 P_ij가 1에 가까우면, 1 * log(P_ij)는 0에 가까워져 비용이 작다.
      • 모델이 잘못 예측하여 P_ij가 0에 가까우면, 1 * log(P_ij)는 매우 큰 양수 값이 되어 비용이 커진다. (두 번째 항은 (1-1) * ... = 0이 된다.)
    • Case 2: 실제로는 i가 j보다 관련성이 높지 않을 때 (P̄_ij = 0)
      • 모델이 올바르게 예측하여 P_ij가 0에 가까우면, (1-0) * log(1-P_ij)는 log(1)에 가까워져 0에 가까운 비용이 된다. (첫 번째 항은 0 * ... = 0이 된다.)
      • 모델이 잘못 예측하여 P_ij가 1에 가까우면, (1-0) * log(1-P_ij)는 log(매우 작은 양수)가 되어 매우 큰 양수 값의 비용이 발생한다.
    • 결론적으로, 모델의 예측(P_ij)이 실제 정답(P̄_ij)과 일치할수록 비용 C_ij는 0에 가까워지고, 불일치할수록 비용은 커진다.

학습 과정

  • 주어진 학습 데이터셋 내의 모든 (또는 샘플링된) 관련 문서 쌍 (i, j)에 대해 각각의 비용 C_ij를 계산
  • 이 개별 비용들의 총합 또는 평균을 전체 비용 함수로 정의
  • 경사 하강법(Gradient Descent) 또는 그 변형(예: SGD, Adam)을 사용하여 이 전체 비용을 최소화하는 방향으로 모델(신경망)의 내부 파라미터(가중치, 편향)를 반복적으로 업데이트

이 과정을 통해 모델은 점차적으로 실제 정답과 유사한 상대적 순서 확률(P_ij)을 예측하도록 학습되어, 결과적으로 더 나은 랭킹 순서를 생성하게 된다.

나. LambdaRank

LambdaRank는 RankNet의 아이디어를 기반으로 하면서도, 실제 정보 검색 평가 지표(예: NDCG, MAP, ERR 등)를 직접적으로 최적화하도록 학습 과정을 개선한 LTR(Learning-to-Rank) 알고리즘이다. 이는 비용 함수 자체보다는 비용 함수의 그래디언트(Gradient)에 랭킹 지표 정보를 영리하게 결합시킨 것이 특징이다.

LambdaRank의 핵심 아이디어 및 주요 개선점

  • RankNet의 한계 극복: RankNet은 개별 문서 쌍의 순서 정확도(Pairwise Accuracy)를 높이는 데 집중하지만, 이것이 반드시 NDCG와 같은 전체 랭킹 리스트의 품질 향상으로 이어지지는 않는다는 문제점을 인식했다. 예를 들어, 랭킹 상위권에서의 오류와 하위권에서의 오류는 실제 사용자 경험에 미치는 영향이 다른데, RankNet은 이를 구분하지 못할 수 있다.
  • 비용 함수 대신 그래디언트에 집중: LambdaRank 연구자들은 RankNet 학습 과정에서 실제 필요한 것은 비용 함수 자체가 아니라, 모델 파라미터를 업데이트하기 위한 그래디언트라는 점에 착안했다.
  • 랭킹 지표 기반 그래디언트 (“Lambda Gradient”): LambdaRank는 RankNet의 그래디언트 계산 방식에 “랭킹 지표의 변화량”이라는 정보를 추가하여 새로운 형태의 그래디언트, 즉 “Lambda 그래디언트”를 정의한다. 이 Lambda 그래디언트는 각 문서의 점수를 조정했을 때 최종 랭킹 지표가 얼마나 개선될지를 직접적으로 반영한다.

LambdaRank의 학습 목표

  • 개별 문서 쌍의 순서 정확도를 넘어, 전체 랭킹 리스트의 품질을 나타내는 특정 정보 검색 평가 지표(Z, 예: NDCG)를 최대화하는 방향으로 모델을 학습시키는 것을 목표로 한다.

LambdaRank의 접근 방식 및 특징

  • RankNet과 마찬가지로 Pairwise 접근 방식을 기반으로 하지만, 학습 과정에서 Listwise적인 정보(전체 랭킹 지표 변화량)를 활용한다.
  • 명시적인 비용 함수를 정의하고 미분하는 대신, 경험적으로 효과적인 Lambda 그래디언트를 직접 계산하여 모델 업데이트에 사용한다. 이는 마치 “가상의 비용 함수”가 있는 것처럼 동작하며, 이 가상의 비용 함수는 실제 랭킹 지표와 밀접하게 연관되어 있다.
  • Lambda 그래디언트는 잘못된 순서쌍(i, j)이 랭킹 지표에 미치는 영향력(|ΔZ_ij|)을 가중치로 사용하여, 중요한 오류(예: 랭킹 상위권에서의 오류)에 대해 더 큰 업데이트를 수행하도록 유도한다.

LambdaRank의 한계

명시적인 비용 함수가 없기 때문에 이론적인 수렴 보장이 어려울 수 있다. 그럼에도 실제로는 좋은 성능을 보이는 경우가 많기도 하다. 어떤 랭킹 지표(NDCG, MAP 등)를 사용할지에 따라 |ΔZ_ij| 계산 방식이 달라지며, 이는 구현의 복잡성을 증가시킬 수 있다.

핵심 수식 (Lambda 그래디언트)

문서 i의 점수 s_i에 대한 Lambda 그래디언트 λ_i는 다음과 같이 계산된다. (문서 j는 문서 i와 쌍을 이루는 다른 문서를 의미)

1

λ_i = Σ_{j: (i,j)는 유효한 쌍} λ_ij

여기서 λ_ij (문서 쌍 (i, j)에 대한 그래디언트)는 종종 다음과 같이 정의된다.

1

λ_ij = - σ'(s_i - s_j) * |ΔZ_ij| = - [ P_ij * (1 - P_ij) ] * |ΔZ_ij|

또는 더 간단히 사용되는 형태로는

1
2

λ_ij = - σ(s_i - s_j) * |ΔZ_ij| = - [ 1 / (1 + exp(s_i - s_j)) ] * |ΔZ_ij|

변수 설명

  • λ_i: 문서 i의 점수 s_i를 업데이트하기 위한 최종 Lambda 그래디언트 값. 문서 i와 관련된 모든 다른 문서 j와의 쌍에서 계산된 λ_ij를 합산하여 구한다.
  • λ_ij: 문서 쌍 (i, j) 사이의 상대적 순서 오류가 랭킹 지표에 미치는 영향을 반영한 그래디언트.
  • s_i, s_j: 모델이 예측한 문서 i와 j의 관련성 점수.
  • σ'(s_i - s_j) 또는 P_ij * (1 - P_ij): RankNet 그래디언트의 일부로, 모델 예측 점수 차이에 따른 기울기 정보를 나타낸다. 예측이 확실할수록(점수 차이가 크면) 이 값은 작아지고, 예측이 모호할수록(점수 차이가 작으면) 커지는 경향이 있다.
  • σ(s_i - s_j) 또는 P_ij: 모델이 예측한 “문서 i가 j보다 관련성이 높을 확률”.
  • |ΔZ_ij|: LambdaRank의 핵심 요소! 만약 문서 i와 j의 현재 순서를 서로 바꾸었을 때, 목표로 하는 랭킹 평가 지표 Z(예: NDCG)의 값이 얼마나 변하는지의 절대값. 즉, 이 순서 변경이 전체 랭킹 품질에 미치는 영향의 크기를 나타낸다.

수식 해석

  1. RankNet 그래디언트 요소 (σ' 또는 σ 부분)

: 이 부분은 RankNet과 유사하게, 모델이 예측한 두 문서의 점수 차이(s_i - s_j)를 기반으로 한다. 모델이 두 문서의 순서를 얼마나 확실하게(또는 불확실하게) 예측하는지에 대한 정보를 담고 있다.

  1. 랭킹 지표 변화량 가중치 (|ΔZ_ij|)

: 이것이 LambdaRank를 특별하게 만드는 부분이다. 각 문서 쌍 (i, j)의 순서가 현재 잘못 예측되었다고 가정하고, 이 둘의 순서를 강제로 바꾸었을 때 최종 랭킹 지표(예: NDCG)가 얼마나 좋아지거나 나빠지는지를 계산한다.

  • 예시
    • 만약, 관련성이 매우 높은 문서 i가 관련성이 낮은 문서 j보다 낮은 순위에 있다면, 이 둘의 순서를 바꾸면 NDCG 값이 크게 향상될 것이다 (|ΔZ_ij|가 큼). 따라서 이 오류는 중요하게 다뤄져야 하며, 해당 λ_ij 값도 커진다.
    • 만약, 관련성이 비슷한 두 문서 i, j의 순서가 약간 잘못되었거나, 이미 랭킹 하위권에 있는 두 문서의 순서가 잘못된 경우, 이 둘의 순서를 바꿔도 NDCG 값의 변화는 미미할 수 있다 (|ΔZ_ij|가 작음). 이 경우 해당 λ_ij 값도 작아져 덜 중요하게 취급된다.
    • 결과적으로 |ΔZ_ij|는 각 순서 오류가 실제 랭킹 품질에 미치는 영향력을 가중치로 부여하는 역할을 한다.
      1. 최종 Lambda 그래디언트 (λ_i)

: 각 문서 i에 대해, 관련된 모든 다른 문서 j와의 쌍으로부터 계산된 λ_ij 값들을 모두 합산한다. 이 최종 λ_i 값은 “문서 i의 점수 s_i를 현재 상태에서 얼마나, 어느 방향으로 조절해야 목표 랭킹 지표(Z)가 가장 효과적으로 개선될 것인가?” 를 나타내는 총체적인 업데이트 신호가 된다.

학습 과정

  • RankNet처럼 명시적인 비용 함수를 계산하고 미분하는 대신, 각 학습 반복(Iteration)마다 다음 과정을 수행한다.
    1. 현재 모델을 사용하여 각 문서(i)의 점수(s_i)를 예측
    2. 각 문서 i에 대해, 관련된 다른 모든 문서 j와의 쌍 (i, j)에 대해 Lambda 그래디언트 λ_ij를 계산 (여기서 |ΔZ_ij| 계산이 필요하다.)
    3. 각 문서 i에 대한 총 Lambda 그래디언트 λ_i를 계산 (λ_i = Σ λ_ij)
    4. 이 λ_i 값을 실제 그래디언트처럼 사용하여, 경사 하강법(또는 변형 알고리즘)을 통해 모델(점수 s_i를 출력하는 함수, 예: 신경망)의 파라미터를 업데이트

이 과정을 반복하면 모델은 점차적으로 Lambda 그래디언트가 작아지는 방향, 즉 실제 랭킹 평가 지표가 높은 상태로 수렴하게 된다.

다. LambdaMART

LambdaMART는 LambdaRank의 랭킹 지표 최적화 아이디어와 MART(Multiple Additive Regression Trees)라는 강력한 앙상블 학습 모델(Gradient Boosting Decision Tree의 일종)을 결합하여, 현재 LTR(Learning-to-Rank) 분야에서 가장 성공적이고 널리 사용되는 알고리즘 중 하나이다.

LambdaMART의 핵심 아이디어

  • 두 강점의 시너지: LambdaRank가 가진 실제 랭킹 지표(예: NDCG)를 직접 최적화하는 능력과, MART(GBDT)가 가진 높은 예측 성능, 복잡한 특징 관계 학습 능력을 효과적으로 융합했다.
  • Lambda 그래디언트를 활용한 부스팅: 일반적인 Gradient Boosting이 이전 모델의 예측 오류(잔차)를 다음 모델이 학습하는 방식이라면, LambdaMART는 예측 오류 대신 LambdaRank에서 정의된 “Lambda 그래디언트”를 다음 트리(약한 학습기)가 학습할 타겟(Pseudo-residual)으로 사용한다.

기반 모델: MART (Multiple Additive Regression Trees)

  • 정의: MART는 Gradient Boosting Decision Tree (GBDT) 알고리즘의 한 종류로, LambdaMART의 핵심 엔진 역할을 한다. LTR 알고리즘 자체라기보다는 LambdaMART를 구성하는 기계 학습 모델 구조이다.
  • 작동 원리: 여러 개의 작은 결정 트리(Weak Learner)를 순차적으로 만들어 나간다. 각 단계에서 새로 만들어지는 트리는 이전 단계까지 학습된 모든 트리들의 결합(앙상블) 모델이 가진 예측 오류를 보완하는 방향으로 학습되며 이렇게 점진적으로 오류를 줄여나가며 최종적으로 매우 강력하고 정확한 예측 모델을 구축한다.
  • 특징: 회귀(Regression) 및 분류(Classification) 문제에서 뛰어난 성능을 보여주며, 특히 테이블 형태의 정형 데이터 처리에 강점을 가진다.

LambdaMART의 특징 및 장점

  • 최고 수준의 랭킹 성능: 다수의 LTR 벤치마크 데이터셋에서 매우 우수한 성능(State-of-the-art)을 보여주며, 실제 검색 서비스 및 추천 시스템 등에서 널리 활용된다.
  • 랭킹 지표 직접 최적화: LambdaRank의 핵심 아이디어를 계승하여, NDCG, MAP 등 원하는 정보 검색 평가 지표를 직접적으로 최적화하는 학습이 가능하다.
  • 강력한 모델링 능력: GBDT 기반이므로 다양한 유형의 특징(수치형, 범주형 등)을 효과적으로 처리하고, 특징들 간의 복잡한 비선형 관계 및 상호작용(Interaction)을 잘 학습할 수 있다.
  • 구현 용이성 및 확장성: LightGBM, XGBoost 등 널리 사용되는 GBDT 라이브러리에 LambdaMART 목적 함수가 구현되어 있어 비교적 쉽게 활용할 수 있으며, 대규모 데이터셋 처리에도 효율적이다.

LambdaMART의 한계 및 고려사항

  • 모델 해석의 어려움: 다수의 트리가 복잡하게 결합된 앙상블 모델이므로, 특정 예측 결과가 왜 그렇게 나왔는지 직관적으로 해석하기 어려울 수 있다. (블랙박스 모델 경향)
  • 특징 공학(Feature Engineering)의 중요성: 모델 성능은 입력으로 사용되는 특징(Feature)의 품질에 크게 의존한다. 어떤 특징을 어떻게 설계하고 추출하여 모델에 제공하는지가 중요하다.
  • 파라미터 튜닝: GBDT 모델 자체의 파라미터(트리 개수, 깊이, 학습률 등)와 LambdaRank 관련 설정 등 튜닝해야 할 파라미터가 많아 최적의 성능을 내기 위한 노력이 필요할 수 있다.
  • 학습 시간: 모델 구조가 복잡하고 많은 트리를 학습해야 하므로, 단순한 모델에 비해 학습 시간이 더 오래 걸릴 수 있다.

LambdaMART의 작동 방식 및 학습 과정

  1. 초기화: 모든 문서에 대해 동일한 초기 예측값(보통 0 또는 평균 관련성 점수)을 갖는 간단한 모델로 시작
  2. 반복 학습 (Boosting): 지정된 횟수(트리의 개수)만큼 다음 과정을 반복
    • Lambda 그래디언트 계산: 현재까지 학습된 앙상블 모델의 예측 점수를 사용하여, 각 문서에 대한 Lambda 그래디언트(λ_i)를 계산한다. 이 그래디언트는 현재 모델에서 어떤 방향으로 점수를 조정해야 목표 랭킹 지표가 가장 효과적으로 개선될지를 나타낸다. (LambdaRank 방식 활용)
    • 새로운 트리 학습: 계산된 Lambda 그래디언트를 실제 타겟 값(Pseudo-residual)처럼 사용하여, 이 그래디언트를 가장 잘 예측하는 새로운 결정 트리(Decision Tree)를 학습시킨다. 즉, 이 트리는 랭킹 지표를 개선하는 방향으로 예측값을 조정하는 방법을 학습한다.
    • 앙상블 모델 업데이트: 새로 학습된 트리를 기존의 앙상블 모델에 추가합니다. 이때 보통 학습률(Learning Rate)을 적용하여 각 트리가 전체 모델에 미치는 영향을 조절한다.
  3. 최종 모델: 지정된 횟수만큼 트리가 추가되거나 더 이상 성능 개선이 없을 때 학습을 멈추고, 최종적으로 만들어진 모든 트리의 예측값을 합산하여 문서의 최종 관련성 점수를 예측하는 모델을 완성한다.

모든 알고리즘 비교 요약

특징TF-IDFBM25RankNetLambdaRankLambdaMART
유형키워드 기반 (Sparse)키워드 기반 (Sparse)LTR (학습 기반)LTR (학습 기반)LTR (학습 기반)
핵심 아이디어단어 빈도와 역 문서 빈도TF-IDF 개선 (단어 빈도 포화, 문서 길이 정규화)문서 쌍 비교, 오류 쌍(inversion) 최소화RankNet 개선 (랭킹 지표 그래디언트 직접 사용)LambdaRank 그래디언트 + MART(GBDT) 모델 결합
주요 입력텍스트 (단어)텍스트 (단어)문서 특징 벡터 쌍문서 특징 벡터 쌍문서 특징 벡터 쌍
학습 필요 여부XX (파라미터 튜닝은 가능)O (주로 신경망)O (주로 신경망)O (GBDT)
장점간단, 직관적TF-IDF보다 높은 정확도, 파라미터 튜닝 가능다양한 특징 활용 가능랭킹 지표 직접 최적화높은 랭킹 성능, 다양한 특징 처리 용이
RAG 활용초기 단계 검색, 간단한 시스템표준적인 키워드 기반 검색복잡한 특징 기반 랭킹 모델 학습복잡한 특징 기반 랭킹 모델 학습현재 가장 널리 쓰이는 LTR 알고리즘 중 하나
단점의미/문맥 파악 불가, 길이/포화 미고려의미/문맥 파악 불가랭킹 지표 직접 최적화 X, 학습 비용 발생구현 복잡도 증가학습 데이터/특징 설계 중요, 학습 비용 발생

위에 설명된 TF-IDF, BM25는 희소 벡터(Sparse Vector) 기반 검색이다. 최근 RAG에서는 밀집 벡터(Dense Vector) 기반 검색이 많이 사용된다. 밀집 벡터 검색은 단어 자체보다는 의미적 유사성을 더 잘 파악하는 장점이 있다. 실제 RAG 시스템을 서비스 하기 위해서는 BM25와 같은 희소 검색과 밀집 벡터 검색을 결합하는 하이브리드(Hybrid) 방식을 사용하여 각 방식의 장점을 취하는 것이 결과의 품질에 도움이 될 것으로 판단된다. 검색된 결과에 대해 LTR 모델을 적용하여 최종 순위를 결정하게 하는 방법도 고려 해볼만 할 것 같다.

AI, LargeLanguageModel
ai rag algorithm
This post is licensed under CC BY 4.0 by the author.