기술 요약: 행렬 완성을 위한 양방향 최근접 이웃 (Two-Sided Nearest Neighbors)

문제 정의

본 논문은 잠재 요인 모델(latent factor models)의 맥락 내에서 행렬 완성 문제를 다루며, 특히 기저의 참값 행렬 $\Theta$가 알려지지 않은 행 및 열 잠재 요인에 작용하는 비선형 잠재 함수 $f$에 의해 생성되는 상황에 초점을 맞춥니다. 모델은 다음과 같이 정의됩니다:
$$\theta_{i,j} = f(u_i, v_j)$$
여기서 $u_i \in \mathbb{R}^{d_1}$와 $v_j \in \mathbb{R}^{d_2}$는 잠재 요인이며, $f$는 매끄러움 파라미터 $\lambda \in (0, 1]$를 갖는 Hölder 함수 클래스에 속합니다. 이 설정은 표준 쌍선형 모델(bilinear models, $f(u,v) = \langle u, v \rangle$인 경우)을 비매개적(non-parametric)이고 잠재적으로 덜 매끄러운(Lipschitz보다 덜 매끄러운) 함수로 일반화합니다.

해결하고자 하는 핵심 과제는 MNAR (Missing Not At Random) 환경입니다. 관측 여부가 데이터와 독립적인 MCAR(Missing Completely At Random)과 달리, MNAR은 관측 여부가 관측되지 않은 잠재 요인에 의존한다고 가정합니다. 또한, 저자들은 특정 구성에서 엔트리가 **결정론적으로 누락(deterministically missing)**될 수 있는 시나리오(즉, 특정 구성에 대해 누락 확률이 0인 경우)를 고려합니다. 이는 추천 엔진과 같이 사용자 선호도가 가시성을 결정하는 실제 시스템에서 흔히 발생하는 현상입니다.

목표는 행 및 열의 잠재 요인이나 함수 $f$에 대한 사전 지식 없이, 미니맥스 최적률(minimax optimal rates)을 달성하면서 참값 $\theta_{i,j}$를 추정하는 것입니다.

방법론: 양방향 최근접 이웃 (TS-NN)

저자들은 양방향 최근접 이웃 (Two-Sided Nearest Neighbor, TS-NN) 알고리즘을 제안합니다. 핵심 직관은 관측된 데이터를 사용하여 행과 열 사이의 잠재적 거리를 근사한 다음, 결과적인 이웃 범위 내에서 결과값들을 평균하는 것입니다.

1. 거리 추정: 잠재 함수 $f$를 알 수 없으므로, 알고리즘은 행(row) 및 열(column) 요인 간의 제곱 $L_2$ 거리에 대한 데이터 기반 대리물(proxies)을 구축합니다.

   • 알고리즘은 공통 열에 걸친 관측된 엔트리들의 제곱 차이를 노이즈 분산($2\sigma^2$)에 대해 보정한 후 평균하여 행 $i$와 $i'$ 사이의 거리를 추정합니다.
   • 열 거리는 공통 행을 사용하여 유사하게 추정됩니다.
   • 형식적으로, 추정된 행 거리는 다음과 같습니다:
     $$\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$$
     (열에 대해서도 대칭적인 공식이 적용됩니다).

2. 이웃 구축: 튜닝 파라미터 $\eta_{row}$와 $\eta_{col}$을 사용하여 이웃을 정의합니다:

   • $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
   • $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$

3. 추정: $\hat{\theta}_{i,j}$는 $i' \in N_{row}(i)$ 이고 $j' \in N_{col}(j)$ 인 모든 관측된 엔트리 $X_{i',j'}$의 평균입니다.

주요 기여 및 이론적 결과

1. 매끄러움에 대한 적응성 및 미니맥스 최적성

주요 이론적 발견은 TS-NN이 잠재 함수 $f$의 매끄러움 $\lambda$에 적응한다는 것입니다.

• MCAR 환경: 표준 MCAR 가정 하에서, 저자들은 적절한 튜닝($\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$)을 통해 평균 제곱 오차(MSE)가 비매개적 미니맥스 최적률을 달성함을 증명합니다:
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  이 비율은 참값 잠재 요인 $U$와 $V$에 접근할 수 있는 "오라클(oracle)" 알고리즘의 비율과 일치합니다.
• MNAR 환경: 저자들은 규제 조건(Assumption 6)이 충족된다면 이 최적성이 MNAR 조건에서도 유지됨을 입증합니다. 이 조건은 행 및 열 이웃의 교집합 내 관측된 엔트리의 수가 이웃 크기의 곱에 비해 충분히 커야 함을 요구하며, 이는 일부 엔트리가 결정론적으로 누락된 경우에도 마찬가지입니다.

2. 결정론적 누락에 대한 강건성

본 논문의 중요한 기여 중 하나는 상당 부분의 행렬이 결정론적으로 누락되어 있음에도 불구하고(예: 특정 사용자-아이템 쌍에 대해 50%의 엔트리가 누락됨) TS-NN이 유의미한 오차율을 낸다는 것을 보여준 점입니다. 이론적 경계는 이웃 내의 "유효한" 누락 확률이 0에서 멀리 떨어져 있는 한 미니맥스 비율이 보존됨을 보여줍니다.

3. 점별 보장 및 점근적 정규성

• 점별 경계 (Pointwise Bounds): 논문은 개별 엔트리 $\hat{\theta}_{i,j}$에 대한 비점근적 점별 오차 경계를 제공합니다. 이러한 경계는 튜닝 파라参数 및 행렬 차원에 따른 "차원의 저주"를 나타내지만, 집단 수준으로 평균화될 때 이는 사라집니다(MSE).
• 점근적 정규성: 이웃 크기에 대한 특정 조건 하에서, 저자들은 점별 추정량이 점근적으로 정규 분포를 따름을 증명합니다:
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  이 결과는 반사실적 추정(counterfactual estimates)을 위한 유효한 신뢰 구간 구축을 가능하게 합니다.

실증적 결과

저자들은 다음을 통해 이론적 발견을 검증합니다:

1. 합성 시뮬레이션:

   • 실험은 Row-NN, Col-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT), SoftImpute를 포함한 베이스라인과 TS-NN을 비교합니다.
   • 결리: TS-NN은 일관되게 가장 좋은 MSE 감소율을 달성하며, MCAR 설정에서 오라클-TS-NN(잠재 요인을 알고 있는 모델)과 일치하는 성능을 보입니다. 결정적으로, TS-NN은 DR-NN과 같은 다른 방법들이 크게 성능이 저하되는 MNAR 설정에서도 견고한 성능을 유지합니다.
   • 매끄러움 적응성: TS-NN의 경험적 감소율은 매끄러움 파라미터 $\lambda$가 변함에 따라 이론적 예측과 일치합니다.
   • 신뢰 구간: 구축된 신뢰 구간은 적절한 표본 크기에서 근사적 명목 피복률(95%)을 달성하여 점근적 정규성 결과를 검증합니다.

2. 실제 사례 연구 (HeartSteps):

   • 방법론을 37명의 사용자와 6주간의 결정 지점을 포함하는 미세 무작위 시험인 HeartSteps 모바일 헬스 데이터셋에 적용합니다.
   • 이 데이터셋은 MN-AR 특성을 보입니다 (사용자는 약 20%의 시간 동안 부재 중이며, 알림은 사용 가능한 경우에만 전송됨).
   • 결과: 5-겹 교차 검증 설정에서, TS-NN은 단방향 NN 변형(Row-NN, Col-NN) 및 "All-Row-NN"과 같은 베이스라인보다 우수한 성능을 보이며, 반사실적 걸음 수(step counts)를 추정하는 데 있어 결정론적 누락을 처리하는 양방향 접근 방식의 실용적 유용성을 입증했습니다.

의의 및 주장

본 논문은 비매개적 행렬 완성과 MNAR 결측 데이터 분석이라는 두 가지 별개의 연구 영역을 통합한다고 주장합니다.

• 최초의 분석: 저자들은 이것이 알려지지 않은 행 및 열 잠재 요인, 비선형 Hölder 연속 함수($\lambda < 1$), 그리고 MNAR 결측을 동시에 다루는 최초의 이론적 분석이라고 밝힙니다.
• 오라클 등가성: 본 연구는 잠재 요인에 대한 지식의 부재가 수렴 속도에 불이익을 주지 않음을 보여줍니다. 즉, TS-NN은 중간 단계의 레짐(intermediate regime)에서 $U$와 $V$에 대한 완전한 지식을 가진 오라클만큼 잘 수행됩니다.
• 강건성: 본 방법론은 표준 행렬 완성 문헌에서는 종종 간과되지만 추천 시스템과 같은 실제 응용 분야에서 매우 중요한 특징인 결정론적 누락 패턴에 대해 강건함을 보여줍니다.

저자들은 결론적으로 TS-NN이 복잡하고 덜 매끄러우며 비무작위적인 결측 환경에 대해 이론적으로 근거가 있고, 적응적이며, 강건한 솔루션을 제공한다고 설명합니다.