기술 요약: 불확실성 인지형 검색을 위한 분포적 근사 최근접 이웃 탐색 (dinosaur)

1. 문제 정의

현대의 대규모 추천 시스템은 수백만 개의 아이템을 랭킹을 위한 관리 가능한 집합으로 필터링하는 후보 생성 단계에서 근사 최근접 이웃(Approximate Nearest Neighbour, ANN) 탐색에 의존합니다. 표준 구현 방식은 공유된 잠재 공간 내에서 사용자 및 아이템 표현을 결정론적 점 추정치(단일 벡터)로 취급합니다.

본 논문은 이러한 패러다임의 근본적인 결함을 지적합니다:

• 내재적 불확실성: 상호작용 데이터가 희소한 임베딩은 본질적으로 불확실합니다. 이 불확실성은 두 가지 형태를 띱니다:
  • 인식론적 불확실성(Epistemic): 상호작용 데이터 부족으로 인한 롱테일 아이템의 높은 분산.
  • 알레아토리적 불확실성(Aleatoric): 저차원 잠재 요인 모델에 내재된 정보 손실.
• 체계적 편향: 결정론적 ANN 검색은 경직된 기하학적 경계를 생성합니다. 실제 관련성이 높을 수 있지만 점 추정치의 평균값이 약간 어긋나 있는 불확실성이 높은 아이템(주로 니치하거나 롱테일인 콘텐츠)은 상위-$k$ 후보군에서 영구적으로 제외됩니다.
• 결과: 이는 **인기 편향(popularity bias)**과 헤드 아이템이 노출을 독점하고 롱테일 크리에이터와 다양한 콘텐츠는 체계적으로 노출 기회를 박탈당하는 "부익부 빈익빈" 피드백 루프를 초래합니다. 기존의 해결책(예: 사후 재순위화 또는 다양성 목적 함수)은 종종 휴리스틱에 의존하며, 검색 단계의 근본 원인과는 단절되어 있습니다.

2. 방법론: dinosaur 프레임워크

저자들은 기존의 ANN 인프라나 스코어링 모델을 변경하지 않고도 임베딩 불확실성을 후보 생성 과정에 직접 통합하는 dinosaur(Distributional Approximate Nearrest Neighbour Search for Uncertainty-Aware Retrieval) 프레임워크를 제안합니다.

핵심 메커니즘

각 아이템 $i$에 대해 단일 점 추정치 $\mu_i$를 인덱싱하는 대신, dinosaur는 아이템을 분포 $P(v_i)$(평균 $\mu_i$와 공분산 $\Sigma_i$로 특징지어짐)로 취급합니다.

1. 인덱스 구축 (오프라인): 각 아이템 $i$에 대해, 시스템은 임베딩 분포 $P(v_i)$로부터 $S_i$개의 독립적인 샘플 $v_i^{(j)} \sim P(v_i)$를 추출합니다. ANN 인덱스는 이 확장된 벡터 집합을 기반으로 구축됩니다.
2. 쿼리 실행 (온라인): 서빙 시점에, 사용자 임베딩 $v_u$는 사용자 분포 $P(v_u)$로부터 샘플링됩니다. ANN 인덱스는 이 샘플링된 벡터에 대한 최근접 이웃을 찾기 위해 쿼리됩니다.
3. 중복 제거: 검색된 벡터들은 원래의 아이템 식별자로 매핑되며, 정확히 $k$개의 고유한 아이템이 반환될 때까지 중복을 제거합니다.

주요 특성

• 인프라 호환성: 이 방법은 ANN 인덱스 알고리즘(예: FAISS, HNSW, ScaNN)이나 스코어링 모델의 변경을 요구하지 않습니다. 단지 더 많은 수의 벡터를 처리할 수 있는 인덱스만 필요합니다.
• 양방향 vs 단방향: 프레임워크는 사용자와 아이템 모두에 대한 샘플링을 지원하지만, 본 논문은 탐색(exploration)을 유도하기 위해 아이템 측 불확실성에 집중합니다. 이는 실시간 사용자 샘플링이 지연 시간 제약을 위반할 수 있는 동적인 마켓플레이스 환경에서 특히 유용합니다.
• 적응형 샘플링: 메모리 비용(인덱스 비대화)을 관리하기 위해, 본 논문은 샘플 예산 $S_i$가 아이템의 불확실성에 따라 결정되는 **적응형 샘플링(Adaptive Sampling)**을 제안합니다. 신뢰도가 높은 헤드 아이템은 $S_i=1$을 받고, 불확실성이 높은 롱테일 아이템은 $S_i > 1$을 받습니다.

이론적 토대

논문은 프레임워크에 대한 이론적 보증을 제공합니다:

• 수렴성: 임베딩 분산이 사라짐에 따라($\sigma^2 \to 0$), dinosaur는 표준 결정론적 점 추정치 검색으로 수렴합니다.
• 단조적 커버리지 확장: 결정론적 top-$k$ 밖에 있는 임의의 아이템에 대해, 검색 확률은 해당 아이템의 임베딩 분산에 따라 엄격하게 증가합니다. 이는 수학적으로 불확실한 아이템이 무작위 노이즈 주입 없이도 "검색 단계의 탐색 보너스"를 받도록 하여 구조적으로 롱테일 콘텐츠를 우대함을 보장합니다.
• Thompson Sampling과의 연결: 이 메커니즘은 샘플링을 통해 사후 분포로부터 샘와링하여 탐색과 활용의 균형을 맞추는 Thompson Sampling과 공식적으로 연결됩니다.

3. 실험 설정

저자들은 MovieLens-32M 데이터셋(3,200만 건의 상호작용, 약 20만 명의 사용자, 약 8.4만 개의 아이템)을 사용하여 dinosaur를 평가했습니다.

• 베이스라인: Exact Inner Product Search (Flat) 및 Approximate Search (IVFFlat).
• 불확실성 프록시: 기본 모델(iALS)은 결정론적이므로, 저자들은 표준 편차 $\sigma_i$가 아이템 상호작용 횟수 $n_i$에 반비례하는 합성 에피스테믹 사후 분포를 구축했습니다: $\sigma_i = \alpha / (1 + n_i)^\gamma$.
• 지표:
  • Recall@K: 표준 오프라인 효용 지표.
  • Catalogue Coverage@K: 적어도 하나의 사용자 top-$K$ 리스트에 등장하는 전체 아이템 카탈로그의 비율.
  • 계층적 커버리지 (Stratified Coverage): 인기 분위수(B0 = 가장 인기 있음, B4 = 가장 인기 없음)별 분석.

4. 주요 결과

• 압도적인 커버리지 이득: 샘플 예산을 $S=1$(베이스라인)에서 $S=5$로 늘렸을 때, 글로벌 카탈로그 커버리지가 거의 3배 증가했습니다 ($K=1000$에서 23.52%에서 62.97%로).
• 미미한 Recall 손실: 이러한 커버리지 확장은 오프라인 Recall의 최소한의 비용, 즉 0.0041의 감소만으로 이루어졌습니다.
• 롱테일 노출:
  • 표준 IVFFlat은 가장 인기 없는 아이템(Bucket B4)에 대해 **0.00%**의 커버리지를 달ável 했습니다.
  • dinosaur ($S=5$)는 Bucket B4에 대해 **81.88%**의 커버리지를 달성하여, 13% 이상의 사용자가 가장 희귀한 아이템으로부터 추천을 받을 수 있도록 보장했습니다.
• 파레토 우위: $\epsilon$-greedy 휴리스틱과 비교했을 때, dinosaur는 다양한 검색 깊이($K \in \{100, 500, 1000\}$)에서 동일한 비율의 탐색적 추천에 대해 더 높은 Recall을 달성하며 베이스라인을 엄격히 압도했습니다.

5. 의의 및 주장

본 논문은 dinosaur가 검색 단계에서의 탐색-활용(exploration-exploitation) 트레이드오프에 대한 원칙적이고 인프라 호환 가능한 솔루션을 제공한다고 주장합니다.

• 패러다임의 전환: 불확실성을 처리하는 부담을 사후 재순위화나 휴리스틱 다양화에서 검색 단계 자체로 이동시킵니다.
• 피드백 루프 타파: 불확실한 아이템이 후보 집합에 진입할 수 있게 함으로써, 결정론적 정책이 롱테일 아이템의 노출을 막고 학습을 방해하는 알고리즘적 피드백 루프를 끊어냅니다.
• 실용성: 이 방법은 샘플 수 외에 새로운 하이퍼파라미터를 요구하지 않으며, 기존의 프로덕션급 ANN 라이브러리와 함께 작동합니다.
• 한계 인정: 저자들은 자신들의 불확실성 프록시가 학습된 분포가 아닌 상호작용 횟수에 기반했다는 점과, 오프라인 지표(Recall)가 MNAR(Missing Not At Random) 데이터에 의해 편향될 수 있음을 언급했습니다. 이들은 향후 연구에서 참된 마켓플레이스 임팩트를 측정하기 위해 성향 점수 기반(propensity-aware) 오프라인 평가와 온라인 A/B 테스트를 결합해야 한다고 제안합니다.

요약하자면, dinosaur는 임베딩을 점이 아닌 분포로 취급하는 것이 표준적인 검색 효용의 저하 없이 카탈로그 다양성과 롱테일 노출을 크게 개선할 수 있음을 입증합니다.