차원이 검색 모델의 장벽인가?

일반적으로 $d ext{ } ext{약} ext{ } ext{1000}$인 표현(representation)의 낮은 차원이 현대의 임베딩 기반 검색(embedding-based retrieval) 모델이 수십억 개, 심지어 수조 개의 데이터 포인트로 확장하는 것을 왜 방해하지 않을까요? 이 질문에 답하기 위해, 우리는 통신 복잡도(communication complexity) [PS86]에서 고전적으로 연구되었고 최근 임베딩 기반 검색 [WBNL26]에서 더 활발히 연구되고 있는 다음 검색 모델에서의 최대 마진(maximal-margin) 임베딩을 연구합니다. $A ext{ } ext{∈} ext{ } ext{{0,1}}^{N imes n}$를 $N$개의 쿼리 각각이 $n$개의 문서 각각과 관련이 있는지 여부를 나타내는 행렬이라고 합시다. 우리는 다음과 같은 성질을 가진 쿼리와 문서의 단위 노름(unit norm) 임베딩 $ ext{{U_j}{j = 1}^N, {V_i}{i = 1}^n}$이 존재하는 가장 큰 마진 $m>0$을 $ ext{\mathsf{m}^{\mathsf{rd}}(d, A)}$로 표기하여 관심을 가집니다. 이 성질은 $A_{ji} = 1$일 때 $ ext{\langle U_j, V_i\rangle ext{ } ext{ extgeq} ext{ } ext{m}$이고, 그렇지 않으면 $ ext{\langle U_j, V_i\rangle ext{ } ext{ extleq} ext{ } ext{-m}$인 것입니다. 큰 마진은 표현 품질(representation quality)을 나타내는 핵심적인 대리 지표입니다. 이는 섭동(perturbation)에 대한 강건성(robustness)과 쿼리 전반에 걸친 구성적 일반화(compositional generalization)를 모두 제어합니다. 우리의 주요 정리는 차원에 대한 제한이 없을 때 가능한 최선의 마진인 $ ext{\mathsf{m}^{\mathsf{rd}}(+\infty, A)}$가 차원 $d = O( ext{\mathsf{m}^{\mathsf{rd}}(+\infty, A)^{-2} ext{\log n})$에서 거의 달성될 수 있음을 입증하며, 이는 [BDES02]의 정리를 개선한 것입니다. 정리 1.5의 일치하는 하한(lower bound)과 함께, 우리는 $A ext{ ext } ext{∈} ext{ ext } ext{{0,1}}^{ ext{\binom{n}{k}} imes n}$이 가능한 모든 $k$-희소(k-sparse) 행을 한 번씩 포함하는 행렬일 때, 이 설정에서 가능한 최대 마진 $ ext{\mathsf{m}^{\mathsf{rd}}(+\infty, A) = ext{\Theta}(k^{-1/2})$를 위해 차원 $d = O(k ext{\log }(n/k))$가 필요충분조건임을 결론짓습니다. 이는 [WBNL26]의 설정을 완전히 해결합니다. 우리는 또한 $d = o(k ext{\log }(n/k))$일 때 큰 마진을 얻기 위한 여러 가지 구성법(constructions)을 제시합니다. 마지막으로, 우리는 큰 마진 임베딩을 생성하기 위해 InfoNCE 및 sigmoid 손실(loss)을 경험적으로 테스트하고, sigmoid 손실의 명확한 이점을 입증합니다.