행렬 근사(Matrix approximation)는 추천 시스템, 텍스트 마이닝 및 컴퓨터 비전에 사용되고 있다. 행렬 근사는 일반적으로 부분 관찰된 행렬이 낮은 순위라 가정한다. 본 논문은 로컬 행렬 근사(local matrix approximation)를 구성하기 위해 병렬(parallel)과 전역(global)이라는 두가지 절차를 제안하고자 한다. 두가지 접근 방식은 관찰된 행렬을 하위 행렬(low-rank)의 가중치 합으로 근사화한다. 이러한 행렬은 관찰된 행렬의 로컬 영역(local region)으로 제한된다. 본 연구는 추천 시스템 작업에 대한 기존의 접근 방식보다 제안하는 로컬 하위 모델링의 예측 정확도가 개선되었음을 보여준다.
행렬 근사 및 완성은 기계 학습에서 널리 사용되는 기법이다. 관찰된 행렬(M)에서의 관찰되지 않은 항목들에 대하여 근사한 행렬(M’)을 구성하므로 써 행렬 완성을 할 수 있도록 한다. 행렬 근사는 추천 시스템, 텍스트 처리, 컴퓨터 비전 및 생물 정보학과 등 여러 곳에 사용되고 있다. 추천 시스템에서는 행렬 M에 대하여 사용자(행)에 대한 아이템(열)의 평점(rating)으로 구성되어 있다. 이 경우 행렬 근사는 관찰된 몇가지 평가를 기반으로 모든 항목에 대한 모든 사용자의 평가를 예측하는 것으로 진행된다. 많은 산업 환경 케이스들에서 행렬 근사는 최신 모델로 여겨지고 있다.
일반적으로, 관찰된 몇가지 항목(entry)들을 기반으로 하였을 때 행렬 완성에는 문제점이 존재한다. 관찰된 행렬(M)의 항목(entry)과 완벽하게 일치하는 행렬의 수는 무한하다. 따라서 추가적인 가정 없이 완성 행렬을 선택하는 것은 부족함(under-specified)이 있으며 잘못 정의된다. 일반적인 가정은 행렬(M)이 low-rank행렬이라는 것으로 이는 완성 행렬이 낮은 rank를 갖는다고 가정하는 것이 합리적이라는 것을 의미한다.
$$ M \in \mathbb{R}^{n_1 \times n_2} \\ \hat{M}=UV^T, where\;U\in\mathbb{R}^{n_1 \times r}, V \in \mathbb{R}^{n_2\times r},\;r<< min(n_1, n_2) $$
많은 실제 데이터셋에서 low-rank 가정이 현실적(realistic)이며, low-rank 근사는 종종 관찰되지 않은 항목(entry)으로 잘 일반화되는 행렬을 생성한다.
본 논문에서 우리는 low-rank 가정을 완화하는 방식으로 기존의 아이디어를 확장하고자 하였다. M이 low-rank 행렬에 의해 전체적으로 근사화될 수 있다고 가정하는 대신 M이 특정 행-열 조합에서 low-rank 행렬로 동작한다고 가정한다. 따라서 본 논문은 행렬의 특정 영역에서 각각 정확한 행렬(M)의 하위 근사치를 구성할 수 있도록 하였다. 이는 추정량을 low-rank 행렬의 평활화된 convex 조합으로 표현되었으며 각 행렬은 로컬 영역에서 M에 근사되어 있다.
지역적 low-rank 가정은 다음과 같은 의미를 가질 수 있다. 많은 설정에는 사용자가 아이템을 원하는지 여부를 결정하는 몇가지 주요 잠재 요소가 포함되어 있다. 영화에서는 이러한 요소들로 배우, 감독, 개봉 연도, 장르 등이 포함될 수 있있다. 그러나 잠재 변수의 수는 일반적으로 20개 이하로 제한되며 이러한 요소는 장르나 배우와 같은 정보를 사용할 수 있다고 가정하지 않기 때문에 암묵적으로 학습되고 자동으로 구성된다. 예를 들어 rank가 5인 경우, 사용자가 아이템에 부여한 평점은항목 특성을 설명하는 길이 5의 벡터와 사용자 선호도를 설명하는 길이 5의 벡터의 내적이다(두 벡터는 각각 U와 V의 행). 잠재 요인의 기초가 되는 선형 기준(linear basis)이 사용자 그룹과 아이템 유형에 따라 변경 될 수 있다는 점을 제외하고 로컬 low-rank의 경우에도 동일한 가정이 유지된다.
위 논문은 두 가지 목표를 달성하기 위해 비모수적 커널 평활화 기법(non-parametric kernel smoothing)을 사용한다. 첫 번째 목표는 공식적으로 로컬 low-rank 근사 개념을 개발하는 것이고, 두 번째 목표는 여러 로컬 모델들을 통합 행렬 근사로 집계하는 것이다. 표준 low-rank 행렬의 근사화 기법은 행렬 M이 낮은 순위라고 가정할 때 대용량 데이터의 한계에서 일관성을 달성한다(데이터 생성 프로세스 수렴). 본 논문의 로컬 방법은 low-rank 가정 없이 일관성을 달성한다. 그 대신 점점 더 작아지는 이웃에서 충분한 수의 샘플을 사용할 수 있어야 한다. 본 연구는 주로 연속 공간을 위해 개발된 비모수적 커널 평활화 이론을 반영하며 잘 알려진 압축 감지 결과를 설정에 맞게 조정하고 일반화 한다. 본 연구는 추천 시스템의 맥락에서 지역의 낮은 순위 모델링이 글로벌 low-rank 모델링보다 훨씬 더 정확하다는 것을 보여준다.
로컬 low-rank 행렬 근사를 용이하게 하기 위해 $[n_1] \times [n_2]$에 대한 메트릭 구조가 있다고 가정해야 한다. 거리 $d$($(a,b), (a', b'))$는 행 $a$$, a'$와 열 $b, b'$ 사이의 유사성을 반영한다. 거리 함수는 관찰된 평점 $P_{\Omega}(M)$ 또는 이용 가능한 경우 사용자에 대한 아이템-아이템 유사성 또는 부가 정보와 같은 추가 정보, 두 행(사용자) 사이 또는 두 열(아이템) 사이의 거리는 해당 행이나 열의 인텍스와 무관하다. 두 행 또는 열의 순서를 교환할 때 유사성은 여전히 동일하게 유지된다.
전역 행렬 분해(global matrix factorization)의 경우, 본 논문은 행렬$M($$M \in \mathbb{R}^{n_1 \times n_2})$이 low-rank구조라고 가정한다. 그러나 국소(local)적인 경우, 모델이 여러개의 low-rank $n_1 \times n_2$ 행렬을 특징으로 한다고 가정한다. 특히, 본 연구는 각 행-열 조합 $[n_1] \times [n_2]$와 관련된 매핑(mapping) $\tau : [n_1] \times [n_2] \rightarrow \mathbb{R}^{n_1 \times n _2}$를 이웃에 있는 $M$의 항목을 설명하는 low-rank 행렬(특히 관찰된 항목 $\Omega$에 적용된)을 가정한다.
$$ \tau : [n_1] \times [n_2] \rightarrow \mathbb{R}^{n_1 \times n_2} \;\;where\;\; \tau_{a,b}(a,b) = M_{a,b} $$
추가적인 가정 없이 $m<n_1n_2$ 관측 세트에서 매핑(mapping) $\tau$를 추정하는 것을 불가능하다. 본 논문에서는 비모수 통계에서 자주 수행되는 것처럼 매핑 $\tau$가 천천히 변한다고 가정했다. $\tau$의 영역은 이산적이기 때문에 연속성 또는 미분성에 대한 고전적인 정의는 본 연구의 설정에 적용시킬 수 없으며, 따라서 그 대신 $\tau$가 횔더 연속(Hölder continuous)이라 가정했다.