최대 내적 검색(Maximum Inner Product Search, MIPS)은 주어진 쿼리 벡터와 데이터베이스 내의 수많은 데이터 벡터들 사이에서, 내적(inner product) 값이 가장 큰 벡터를 찾는 문제를 의미합니다. 이 기술은 단순한 유사도 측정을 넘어 추천 시스템, 자연어 처리(NLP), 컴퓨터 비전 등 다양한 분야에서 중요한 역할을 합니다.
MIPS의 중요성
벡터의 내적은 두 벡터의 크기(norm)와 이들이 이루는 각도의 코사인 값을 곱한 형태로 계산됩니다. 즉, 두 벡터가 얼마나 유사한지(방향)와 각 벡터의 크기를 모두 반영하는 척도입니다. 예를 들어 추천 시스템에서는 사용자 벡터와 아이템 벡터의 내적이 곧 사용자의 선호도와 아이템의 인기까지 종합적으로 고려한 점수가 됩니다. 따라서 내적 값이 클수록 사용자가 해당 아이템을 선호할 가능성이 높다고 해석할 수 있습니다.
또한 최근에는 검색 증강 생성(Retrieval-Augmented Generation, RAG)과 같은 모델에서도 MIPS가 핵심적인 역할을 합니다. RAG는 대규모 언어 모델(LLM)이 답변을 생성할 때, 외부 지식 데이터베이스에서 관련성 높은 정보를 검색하여 이를 기반으로 보다 정확하고 풍부한 답변을 생성하는 기술입니다. RAG에서는 사용자의 질문과 가장 관련성이 높은 문서를 외부 데이터베이스에서 찾아내기 위해 MIPS를 활용합니다.
A.1.1) MIPS Vs NNS Vs MCSS
MIPS는 최근접 이웃 검색(Nearest Neighbor Search, NNS), 최대 코사인 유사도 검색(Maximum Cosine Similarity Search, MCSS)와 자주 비교됩니다.
- NNS: 질의 벡터와 데이터 벡터 사이의 유클리드 거리(Euclidean distance)를 기준으로 가장 가까운 항목을 찾습니다.
- MCSS: 두 벡터 간의 코사인 유사도(), 즉 방향만 고려해 가장 유사한 항목을 찾습니다.
- MIPS: 내적() 값을 최대로 하는 항목을 찾으며, 여기서는 방향뿐 아니라 크기도 중요한 요소로 작용합니다.
즉, NNS나 MCSS는 보통 크기에 영향을 받지 않거나 정규화해서 사용하는 반면, MIPS는 크기를 그대로 반영하여 계산합니다. 만약 모든 데이터 벡터들의 크기가 동일하다면 세 문제는 본질적으로 동일해집니다.
A.1.2) 주요 응용 분야
- 추천 시스템: 행렬 분해 기반 추천 모델에서 사용자 및 아이템 임베딩 간 내적 계산에 활용됩니다.
- 자연어 처리(NLP): 대형 언어 모델에서 단어나 문장 임베딩 간 최대 관련 정보를 찾기 위해 MIPS가 사용됩니다.
- 컴퓨터 비전: 이미지 특징이나 객체 인식 등에서 특징 임베딩 간 유사도를 비교하는 데 쓰입니다.
- 다중 클래스/레이블 분류: 입력 데이터와 여러 클래스 중 가장 연관성 높은 레이블 판별에 활용할 수 있습니다.
A.1.3) 효율적인 MIPS 알고리즘
데이터셋 규모가 커질수록 모든 데이터와 직접적으로 내적을 계산하는 것은 매우 비효율적입니다. 이를 극복하기 위해 다양한 근사(approximate) 알고리즘이 개발되었습니다.
A.1.3.1) NNS로 변환
대표적인 방법 중 하나는 MIPS 문제를 NNS 문제로 변환하여 기존 고속 NNS 알고리즘(k-d 트리, 볼 트리 등)을 활용하는 것입니다. 데이터 벡터와 질의 벡터를 더 높은 차원의 공간으로 변환해, 원래 공간에서 내적이 큰 쌍일수록 새로운 공간에서도 거리가 가깝도록 설계합니다. 이러한 방식은 HNSW 같은 그래프 기반 알고리즘에도 적용 가능합니다.
A.1.3.2) 지역 민감 해싱(Locality Sensitive Hashing, LSH)
LSH는 서로 비슷한(유사도가 높은) 벡터들이 동일 해시 버킷에 저장될 확률이 높아지도록 설계된 해싱 기법입니다. 특히 비대칭 LSH(Asymmetric LSH), Norm-Ranging LSH 등은 데이터 벡터의 norm 분포가 긴꼬리를 가질 때도 성능 저하를 줄이도록 고안되었습니다.
A.1.3.3) 양자화(Quantization)
고차원 임베딩 데이터를 더 적은 비트로 압축하여 저장하고 빠르게 근사 내적값을 계산하도록 돕습니다. Product Quantization(PQ)은 하나의 고차원 벡터를 여러 하위 벡터로 나누고 각각 독립적으로 양자화합니다. 이런 방식으로 메모리를 절약하면서 빠른 근사 검색이 가능합니다. ScaNN 같은 라이브러리는 파티셔닝 및 이방성 양자화(Anisotropic Quantization)를 결합하여 대규모 환경에서도 효율적인 성능을 보장합니다.
이외에도 트리 기반 또는 그래프 기반 알고리즘 등 다양한 접근 방식들이 연구되고 있습니다. 오늘날 MIPS는 머신러닝과 정보검색 분야에서 필수 기술로 자리 잡았으며, 보다 빠르고 정확한 검색 방법 개발이 지속되고 있습니다. 이처럼 MIPS는 현대 데이터 과학과 머신러닝 분야에서 필수적인 기술로 자리 잡았으며, 더 빠르고 정확한 검색을 위한 알고리즘 연구는 계속해서 발전하고 있습니다