기술 요약: 적은 양으로도 잘하기! 경험적 쌍별 손실 추정/최소화를 위한 샘플링 기법에 대하여

문제 정의

유사성 학습(similarity learning), 순위 학습(ranking), 클러스터링, 대조적 표현 학습(contrastive representation learning)을 포함한 많은 근본적인 머신러학습 과제들은 경험적 쌍별 손실 함수(empirical pairwise loss functions)를 최소화하는 데 의존한다. 이러한 목적 함수들은 차수가 2인 U-통계량(U-statistics)으로 정식화되며, 이는 $O(N^2)$개의 관측치 쌍을 평가해야 함을 의미한다. 고차원 데이터(예: 이미지 또는 텍text 임베딩)를 다룰 때, 가능한 모든 쌍에 대해 손실을 계산하는 것은 계산상의 주요 병목 현상이 되어, 대규모 환경에서 전체 쌍을 평가하는 것을 불가능하게 만든다.

이러한 비용을 완화하기 위한 일반적인 휴리스틱은 개별 관측치를 서브샘플링하고 그 결과로 얻은 부분 집합으로부터 쌍을 형성하는 것이다. 그러나 본 논문은 그러한 전략이 최적이 아니라고 주장한다. 핵심 과제는 통계적 효율성을 유지하고 선택 편향(selection bias)을 교정하면서, 추정하거나 최소화할 수 있는 작고 정보가 풍부한 비율의 쌍을 선택하는 샘플링 스킴을 설계하는 것이다.

방법론

저자들은 조사 샘플링 이론(survey sampling theory)을 개별 관측치가 아닌 '쌍(pairs)'의 모집단에 직접 적용할 것을 제안한다. 이 방법론은 관측된 값들을 그들의 포함 확률(inclusion probabilities)의 역수로 가중치를 두어 모집단의 총합(또는 평균)에 대한 불편 추정량(unbiased estimate)을 제공하는 호르비츠-톰슨(Horvitz-Thompson, HT) 추정량에 근거한다.

핵심 프레임워크

1. 모집단 정의: 방법론은 관측치의 집합 $I = \{1, \dots, N\}$에서 샘플링하는 대신, 쌍의 집합 $J = \{(i, j) : 1 \le i < j \le N\}$에서 샘플링한다.
2. 보조 정보(Auxiliary Information): 샘플링 설계는 쌍별 손실 $\ell(Z_i, Z_j)$와 상관관계가 있는 프록시(proxy)인 $\rho(W_i, W_j)$라는 보조 정보를 활용한다. 이 정보는 관측치 수준의 특징(예: 메타데이터, 저차원 투영)이나 쌍 수준의 특징(예: 그래프 엣지 가중치)으로부터 도출될 수 있다.
3. 포함 확률: 쌍은 보조 프록시에 비례하는 확률 $\bar{\pi}_{i,j} \propto \rho(W_i, W_j)$에 따라 선택된다. 이는 "정보가 풍부한" 쌍(손실에 크게 기여할 가능성이 높은 쌍)이 더 빈번하게 샘플링되도록 보장한다.
4. 추정량:
   • 직접 쌍 샘플링(Direct Pair Sampling): 쌍은 $J$로부터 설계 $\bar{D}_{\bar{N}}$(예: 포아송 또는 리젝티브 샘플링)를 사용하여 직접 샘플링된다. 추정량은 $\bar{U}_{\bar{D}_{\bar{N}}} = \frac{2}{N(N-1)} \sum_{(i,j) \in \bar{S}} \frac{\ell(Z_i, Z_j)}{\bar{\pi}_{i,j}}$이다.
   • 관측치 샘플링(Observation Sampling, 베이스라인): 관측치가 $I$에서 샘플링되고, 그 부분 집합으로부터 쌍이 형성된다. 추정량은 $\tilde{U}_{D_N} = \frac{2}{N(N-1)} \sum_{i<j \in S} \frac{\ell(Z_i, Z_j)}{\pi_{i,j}}$이다.

이론적 분석

논문은 조사 샘플링된 쌍들로 훈련된 예측 모델의 초과 위험(excess risk)에 대한 비점근적 경계(non-asymptotic bounds)를 확립한다.

• 분산 최소화: 저자들은 고정된 평가 쌍 예산에 대해, 직접 쌍 샘플링이 관측치 기반 샘플링보다 추정량 분산 측면에서 엄격하게 우월함을 증명한다. 이는 관측치 수준의 포함 확률이 $\pi_{i,j} = \pi_i \pi_j$로 인수분해되어야 한다는 제약 때문에, 쌍별 손실의 전체 기하학적 구조에 적응할 수 없기 때문이다.
• 일반화 경계: 독립(포아송) 및 음의 상관 관계(리젝티브) 변수에 대한 번스타인 부등식(Bernstein's inequality)을 사용하여, 논문은 균등 편차 경계를 도출한다. 이는 샘플링된 쌍의 수 $\bar{n}$이 $N$에 선형적으로 비례하는 경우(즉, $\bar{n} = cN$), 초과 위험이 표준적인 $O(1/\sqrt{N})$ 속도로 수렴함을 보여준다. 이는 평가된 쌍의 비율이 전체 가용 쌍에 비해 소멸함에도 불구하고, 학습률은 최적 상태를 유지함을 의미한다.

주요 기여

1. 직접 쌍 샘플링의 이론적 우월성: 본 논문은 직접 쌍 샘플링이 쌍별 손실 추정을 위해 이론적으로 최적임을 입증한다. 명제 1은 완벽한 보조 정보가 있더라도 어떤 관측치 기반 샘플링 계획도 직접 쌍 샘플링 계획만큼의 분산을 달성할 수 없음을 보여준다.
2. 최적의 포함 확률: 정리 1은 쌍별 포아송 스킴에서의 최적 연결 함수(link function)를 식별한다. 최적의 확률은 $\rho^*(W_i, W_j) = \sqrt{E[\ell^2(Z, Z') | W_i, W_j]}$에 비례한다. 또한 논문은 손실과 상관관계가 있는 프록시 $\rho$를 사용하는 것이 상관관계의 품질에 비례하여 분산을 감소시킨다는 것을 보여준다.
3. 비점근적 일반화 보장: 섹션 4는 조사 샘플링된 쌍들에 기반한 쌍별 학습에 대한 최초의 비점근적 초과 위험 경계를 제공한다. 이는 선형 비율의 쌍만 평가되더라도 $O(1/\sqrt{N})$의 수렴 속도가 유지됨을 확인해 준다.
4. 경험적 검증: 합성 데이터와 세 가지 실제 데이터셋(MovieLens, Cora, LFW)을 통해 검증되었다. 결과에 따르면, 정보 기반 쌍 샘플링은 손실의 이질성과 보조 프록시의 품질에 따라 균등 쌍 샘플링 및 관측치 샘플링에 비해 $2\times$에서 $100\times$ 이상의 분산 감소 효과를 보였다.

결과

• 분산 감소: 희소 신호(sparse signal) 작업에서, 정보 기반 쌍 샘플링은 균등 쌍 샘플링에 비해 $121\times$의 분산 감소를 달ach했다. 실제 데이터셋에서는 관측치 기반 샘플링과 비교하여 $1.2\times$에서 $76.8\times$ 사이의 감소를 보였으며, 이 이득은 손실의 제곱 변동 계수($CV^2(\ell)$)에 따라 규모가 결정되었다.
• 학습 성능: 노드 분류(Cora) 및 얼굴 인식(LFW) 실험은 조사 샘플링된 쌍으로 훈련된 모델이 전체 쌍 훈련(오라클)의 성능에 수렴함을 입증했다.
  • 편향 교정: 선택 편향을 유발하는 "하드 네거티브 마이닝(hard negative mining)"이나 기타 휴리스틱 선택 방법과 달리, HT 가중치 조사 샘플링 방식은 편향되지 않는다. 논문은 하드 샘플링이 교정되지 않은 편향으로 인해 정체되는 반면, 포아송 및 리젝티브 샘플링은 전체 쌍 손실을 향해 계속 수렴한다는 점을 보여준다.
  • 강건성: 약한 보조 정보(예: 상관관계 $\approx 0.16$인 LFW)를 사용하더라도, 정보 기반 샘플링이 균등 샘플링보다 성능이 낮았던 적은 없다. 강력한 프록시(예: 사전 계산된 대조 손실)를 사용했을 때 성능은 오라클과 매우 유사했다.

의의 및 주장

본 논문은 쌍별 학습 문제에 있어 계산 비용과 추정 정확도 사이의 원칙적이고 이론적으로 근거가 있는 트레이드오프를 제공한다고 주장한다.

• 패러다임 전환: 쌍별 작업을 수행할 때 관측치를 서브샘플링하는 표준 관행에 도전하며, 이 문제들의 자연스러운 샘플링 영역은 쌍 그 자체임을 주장한다.
• 검소함(Frugality): 이 방법론은 전체 쌍의 극히 적은 비율($O(N^2)$ 대신 $O(N)$)만을 평가하면서도 전체 쌍 학습의 통계적 보장을 유지함으로써, 실무자들이 "적은 양으로도 잘할 수 있게" 해준다.
• 범용적 적용 가능성: 이 프레임워크는 적절한 보조 정보가 있다면 순위 학습, 메트릭 학습, 대조적 학습을 포함하여 2차 U-통계량으로 정식화되는 모든 과제에 적용 가능하다.

저자들은 분산 감소를 고려한 더 정교한 학습률 경계에 대한 연구가 향가적인 과제로 남아있지만, 본 연구가 조사 샘플링 이론에 근거한 적절한 데이터 선택 체계를 통해 더 검소한 쌍별 학습 방법을 위한 길을 열었다고 결론짓는다.