[LLM] 희소 검색(Sparse Retrieval) vs. 밀집 검색(Dense Retrieval)

1. 검색 알고리즘의 두 가지 접근 방식

검색 알고리즘은 크게 두 가지 방식으로 나뉩니다.

1️⃣ 희소 검색(Sparse Retrieval): 단어 기반(Term-Based) 검색

2️⃣ 밀집 검색(Dense Retrieval): 임베딩(Embedding) 기반 검색

이 블로그에서는 "용어 기반(Term-Based) 검색"을 중심으로 다루고 있지만, 실제로 검색 알고리즘을 분류할 때는 희소 vs. 밀집 검색 기준이 자주 사용됩니다.

---

2. 희소 검색(Sparse Retrieval)

희소 검색은 단어(Term) 자체를 벡터로 변환하여 검색하는 방식입니다.

• 전통적인 TF-IDF(Term Frequency-Inverse Document Frequency), BM25 등의 검색 기법이 포함됨
• 문서의 단어를 0과 1이 포함된 벡터 형태로 변환하여 저장
• 단어가 해당 문서에 존재하면 1, 없으면 0

📌 예제: 원-핫 인코딩(One-Hot Encoding) 방식

단어 사전(Dictionary): ["food", "banana", "slug"]
"food" → [1, 0, 0]
"banana" → [0, 1, 0]
"slug" → [0, 0, 

• 단어가 문서에 존재하면 1, 없으면 0
• 단어의 순서를 고려하지 않음
• 문서에서 단어가 여러 번 등장하더라도 단순히 횟수만 반영됨

✅ 희소 검색의 특징

• 간단하고 빠른 검색 가능
• 의미적인 유사성을 고려하지 않음
• 단어가 정확히 일치해야 검색 가능(예: "AI 연구"와 "인공지능 연구"는 다르게 인식됨)

---

3. 밀집 검색(Dense Retrieval)

밀집 검색은 단어를 벡터 공간에 매핑하여 의미적으로 유사한 문서를 검색하는 방식입니다.

• 딥러닝 기반 임베딩(Embedding) 모델을 활용
• 단어 간의 의미적 관계를 고려하여 벡터로 변환
• 검색 시, 단순한 키워드 일치가 아니라 의미적으로 유사한 문서까지 검색 가능

📌 예제: 임베딩 벡터 변환

"food" → [0.21, 0.78, 0.12, ...]
"banana" → [0.45, 0.67, 0.33, ...]
"slug" → [0.98, 0.12, 0.08, ...]

✅ 밀집 검색의 특징

• 의미적으로 유사한 단어까지 검색 가능(예: "AI 연구"와 "인공지능 연구"를 비슷하게 인식)
• 검색 정확도가 높음
• 하지만 사전 학습이 필요하고 계산 비용이 높음

📌 SPALDE(Sparse Latent and Expansion, Forman et al., 2021)

• 최근에는 희소 검색과 밀집 검색을 결합한 방법도 연구됨
• SPALDE는 희소 검색 방식으로 임베딩을 생성하고, BERT 기반 모델을 활용해 임베딩 벡터를 최적화
• 이렇게 하면 밀집 검색처럼 의미를 고려하면서도, 희소 검색보다 빠르게 검색 가능

---

4. 용어 기반 검색(Term-Based Retrieval)

용어 기반 검색은 검색어에 포함된 키워드를 바탕으로 관련 문서를 찾는 가장 단순한 방법입니다.

• "AI engineering"이라는 검색어가 주어지면, 검색 시스템은 "AI"와 "engineering"을 포함한 문서를 반환합니다.

📌 용어 기반 검색의 문제점

1️⃣ 검색 결과에 너무 많은 문서가 포함될 수 있음

2️⃣ 문서가 길 경우, 중요한 키워드를 포함했더라도 문서 전체 내용을 고려하기 어려움

이를 해결하기 위해 사용되는 방법이 TF-IDF(Term Frequency-Inverse Document Frequency)입니다.

---

5. TF-IDF 알고리즘: 용어 기반 검색의 핵심

TF-IDF는 단순한 단어 빈도(TF, Term Frequency)뿐만 아니라, 해당 단어가 얼마나 중요한지(IDF, Inverse Document Frequency)를 함께 고려하는 방식입니다.

📌 수식 정리

• TF(t, D) = 특정 문서 D에서 단어 t의 등장 횟수
• IDF(t) = 전체 문서에서 해당 단어가 얼마나 희귀한지를 나타내는 값 IDF(t)=logC(t)N
  • N: 전체 문서 수
  • C(t): 단어 t가 등장하는 문서의 수
• IDF(t)=log⁡NC(t)IDF(t) = \log \frac{N}{C(t)}

📌 TF-IDF 점수 공식

Score(D,Q)=∑t∈QIDF(t)×TF(t,D)Score(D, Q) = \sum_{t \in Q} IDF(t) \times TF(t, D)

Score(D,Q)=t∈Q∑IDF(t)×TF(t,D)

• 검색어 Q에 포함된 모든 단어 t에 대해 TF-IDF 값을 합산하여 문서 D의 점수를 계산

---

6. 역색인(Inverted Index)

검색 속도를 높이기 위해 검색 시스템에서는 역색인(Inverted Index)을 활용합니다.

• 문서 내의 단어와 해당 단어가 포함된 문서 ID를 매핑하여 저장
• 이를 통해 빠른 검색 가능

📌 예제: 역색인 테이블

Term	Document Count	Document Index, Term Frequency
banana	3	(10,3), (5,2), (7,1)
food	4	(1,5), (10,2), (8,9), (42,5)
learning	5	(1,5), (38,7), (42,5)

• "banana"라는 단어가 등장하는 문서: 10, 5, 7번 문서
• "food"라는 단어가 등장하는 문서: 1, 10, 8, 42번 문서
• 검색 시, 해당 단어가 포함된 문서를 빠르게 찾을 수 있음

---

7. Okapi BM25: 현대적인 용어 기반 검색 알고리즘

BM25는 TF-IDF의 발전형 모델로, 가중치를 조정하여 검색 결과의 정확도를 높이는 알고리즘입니다.

• TF-IDF보다 문서 길이에 대한 보정 기능이 추가됨
• 특정 단어가 여러 번 등장해도 무조건 높은 점수를 주지 않도록 설계됨

📌 Okapi BM25의 특징

✅ TF-IDF보다 더 정교한 검색 결과 제공

✅ 문서 길이를 고려하여 가중치를 조정

✅ 검색 정확도를 향상시키는 핵심 알고리즘

---

8. 결론: 희소 검색 vs. 밀집 검색, 그리고 미래 방향

✅ 희소 검색(Sparse Retrieval)

• 단순하고 빠른 검색 가능
• 의미적 유사성을 고려하지 않음
• 예: TF-IDF, BM25

✅ 밀집 검색(Dense Retrieval)

• 의미적으로 유사한 문서까지 검색 가능
• 검색 정확도는 높지만, 계산 비용이 큼
• 예: BERT 기반 임베딩 검색

📌 최신 트렌드: 하이브리드 검색

• SPALDE와 같은 기술을 통해 희소 검색과 밀집 검색을 결합하는 연구가 진행 중
• 이렇게 하면 빠른 검색 속도와 높은 정확도를 동시에 확보 가능

AI 기반 검색 기술은 단순한 키워드 매칭을 넘어, 의미를 이해하는 방향으로 발전하고 있다!