행렬 완성

1. 개요[편집]

행렬 완성 Matrix completion
문제	일부 성분 $\{M_{ij}\}_{(i,j)\in\Omega}$ 만 보고 전체를 복원
구조 가정	저계수 — 자유도 $r(m+n-r)$
볼록 완화	rank → 핵노름 $\lVert X\rVert_* = \sum_i \sigma_i$
표본 복잡도	$O(\mu n r \log^2 n)$ (균일 표본 + 결맞음 조건)
대표 알고리즘	SVT · ALS · 비볼록 인수분해
대표 사례	넷플릭스 프라이즈 (관측률 약 1.2%)

1억 개를 보고 85억 개를 채운다. 정신 나간 소리처럼 들리는데, 저계수라는 가정 하나가 이걸 정당화한다.

행렬 완성(matrix completion)은 행렬 $M \in \mathbb{R}^{m\times n}$ 의 극히 일부 성분 $\Omega$ 만 관측한 상태에서, 저계수라는 구조 가정만으로 나머지 전부를 복원하는 문제다. 아무 가정 없이는 당연히 불가능하다 — 관측 안 된 자리에 아무 숫자나 넣어도 데이터와 모순이 없기 때문이다. 그런데 $\mathrm{rank}(M) = r$ 이면 자유도가 $mn$ 이 아니라 $r(m+n-r)$ 로 줄고, $r \ll \min(m,n)$ 이면 이 수가 $mn$ 보다 자릿수로 작다. 미지수보다 방정식이 많아지는 순간 복원이 원리적으로 가능해진다.

가능성과 알고리즘은 다른 이야기다. 이 문서는 그 사이를 잇는 세 가지 — 볼록 완화가 왜 통하는가, 몇 개를 봐야 하는가, 그리고 그 이론이 실무에서 어디서 깨지는가 — 를 다룬다. 관측이 완전한 경우의 저계수 근사(에카르트-영-미르스키, SVD 절단)는 저랭크 근사에, 압축센싱과의 관계는 그쪽 문서에 있으니 여기서는 반복하지 않는다.

2. 계수 최소화와 그 볼록 완화[편집]

가장 정직한 정식화는

$$\min_X \ \mathrm{rank}(X) \quad \text{s.t.} \quad X_{ij} = M_{ij},\ (i,j)\in\Omega$$

인데, $\mathrm{rank}$ 는 비볼록이고 이 문제는 NP-난해다. 벡터의 희소성 문제에서 $\ell_0$ 를 $\ell_1$ 로 바꾸듯, 여기서는 핵노름(nuclear norm, 대각합 노름)

$$\lVert X\rVert_* = \sum_i \sigma_i(X)$$

으로 바꾼다. 정당화는 정확한 진술이 있다 — 핵노름은 스펙트럼 노름 단위공 $\{X : \lVert X\rVert_2 \le 1\}$ 위에서 $\mathrm{rank}$ 함수의 볼록 포락선이다. $\ell_1$ 이 $\ell_\infty$ 공 위에서 $\ell_0$ 의 볼록 포락선인 것과 정확히 대응한다. 계수는 특이값 벡터의 $\ell_0$ 이고 핵노름은 그 $\ell_1$ 이니, 행렬 완성은 특이값 좌표계에서 본 희소 복원인 셈이다.

바뀐 문제

$$\min_X \ \lVert X\rVert_* \quad \text{s.t.} \quad \mathcal{P}_\Omega(X) = \mathcal{P}_\Omega(M)$$

는 볼록이고, 실제로 반정부호 계획법으로 표현된다.

$$\lVert X\rVert_* = \min_{W_1,W_2}\ \tfrac{1}{2}\left(\mathrm{tr}\,W_1 + \mathrm{tr}\,W_2\right) \quad \text{s.t.}\quad \begin{bmatrix} W_1 & X \\ X^\top & W_2\end{bmatrix} \succeq 0$$

(이 등가성 자체가 슈어 보수 보조정리의 응용이다.) 다만 내점법 SDP는 변수 수가 $O((m+n)^2)$ 라 수백 차원에서 이미 힘들어진다. 실무 알고리즘이 따로 발달한 이유다.

3. 언제 되는가 — 결맞음과 표본 복잡도[편집]

저계수만으로는 부족하다. 반례가 한 줄로 나온다.

$$M = e_1 e_1^\top$$

계수 1의 완벽한 저계수 행렬인데, $(1,1)$ 성분을 뽑지 못하면 관측한 것이 전부 0이라 $M = 0$ 과 구별할 방법이 없다. 정보가 한 칸에 몰려 있으면 무작위 표본이 그 칸을 놓친다.

그래서 특이벡터가 좌표축에 정렬되어 있지 않다는 조건이 붙는다. $M = U\Sigma V^\top$ 의 특이벡터 공간에 대해 결맞음(coherence)을

$$\mu(U) = \frac{n}{r}\max_i \lVert P_U e_i\rVert^2$$

로 정의하면 $\mu \in [1, n/r]$ 이고, 값이 작을수록 에너지가 좌표 전체에 고르게 퍼져 있다는 뜻이다. 위 반례는 $\mu$ 가 최대인 경우다.

이 조건 아래 캉데스와 렉트(2009)가 보인 것이 정확 복원 정리다. 관측 위치를 균일 무작위로 뽑았을 때

$$|\Omega| \;\ge\; C\,\mu\, n r \log^2 n$$

개면 높은 확률로 핵노름 최소화의 해가 $M$ 과 정확히 일치한다. 이후 캉데스-타오와 렉트가 상수와 로그 지수를 다듬어 오늘날 표준으로 인용되는 형태가 됐다. 자유도가 $\Theta(nr)$ 이므로 로그 인자 두 개만 더 내면 된다는 뜻이고, 이건 정보이론적으로 거의 최적이다.¹

증명 구조는 압축센싱의 이중 증명서(dual certificate) 논법을 행렬로 옮긴 것이며, 실제로 두 이론은 같은 시기 같은 사람들이 만들었다. 차이는 측정 연산자다 — 압축센싱은 무작위 가우스 행렬처럼 “잘 섞는” 측정을 설계할 수 있지만, 행렬 완성의 측정은 좌표 하나 뽑기로 고정돼 있어 결맞음 조건이 추가로 필요하다.

잡음이 있으면 등식 제약을 완화한다.

$$\min_X \ \tfrac{1}{2}\lVert \mathcal{P}_\Omega(X - M)\rVert_F^2 + \lambda \lVert X\rVert_*$$

이 되고, 오차가 잡음 수준에 비례하는 안정 복원 결과가 붙는다.

4. 알고리즘[편집]

4.1. 특이값 임계화 (SVT)[편집]

핵노름의 근접 연산자가 닫힌 형태로 나온다는 것이 결정적이다. $Y = U\Sigma V^\top$ 일 때

$$\mathrm{prox}_{\tau\lVert\cdot\rVert_*}(Y) = U\,\mathcal{S}_\tau(\Sigma)\,V^\top, \qquad \mathcal{S}_\tau(\sigma) = \max(\sigma - \tau,\, 0)$$

즉 SVD를 하고 특이값을 연화 임계화한 뒤 되조립한다. 벡터의 $\ell_1$ 근접 연산자가 성분별 연화 임계화인 것의 행렬판이다. 이걸 근접 경사법에 꽂으면 SVT(Cai·Candès·Shen, 2010) 알고리즘이 되고, 교대방향 승수법에 꽂아도 된다.

비용은 반복마다 SVD 한 번이라 만만치 않은데, 두 가지가 구해 준다. 첫째, 임계화 뒤에 살아남는 특이값이 몇 개뿐이므로 부분 SVD(란초스 알고리즘이나 랜덤화 SVD)면 충분하다. 둘째, 반복 중 반복자가 저계수 + 희소 구조를 유지해서 행렬-벡터 곱이 싸다.

4.2. 교대최소제곱과 비볼록 인수분해[편집]

볼록 완화를 아예 포기하고 $X = UV^\top$ ($U \in \mathbb{R}^{m\times r}$, $V\in\mathbb{R}^{n\times r}$)로 매개화한 뒤

$$\min_{U,V}\ \sum_{(i,j)\in\Omega}\left(u_i^\top v_j - M_{ij}\right)^2 + \lambda\left(\lVert U\rVert_F^2 + \lVert V\rVert_F^2\right)$$

를 푸는 쪽이 실무의 주류다. 목적함수는 비볼록이지만 **한쪽을 고정하면 다른 쪽에 대해 최소자승법**이라, $U$ 와 $V$ 를 번갈아 정확히 푸는 교대최소제곱(ALS)이 성립한다. 각 행/열이 독립이므로 완전 병렬이고, 메모리는 $O((m+n)r)$ 뿐이다. 관측을 통째로 훑는 대신 표본 하나씩 갱신하는 확률적 경사하강법 변형도 널리 쓰인다.

참고로 위 정칙항이 우연이 아니다. $\lVert X\rVert_* = \min_{UV^\top = X} \tfrac{1}{2}(\lVert U\rVert_F^2 + \lVert V\rVert_F^2)$ 이므로, $r$ 을 충분히 크게 잡으면 이 비볼록 문제의 전역해가 핵노름 정식화의 해와 같다. 두 접근은 겉보기만큼 멀지 않다(뷔러-몬테이로 관점).

비볼록인데 왜 되는가에 대한 이론도 2015년 이후 상당히 정리됐다. 결맞음 조건과 적절한 초기화(관측 행렬의 스펙트럼 초기화) 아래 가짜 국소최소가 없고, 모든 안장점이 탈출 가능한 엄격 안장점이라는 결과들이다. 즉 경사하강이 전역해로 간다. 계수 $r$ 을 고정한 매개화는 리만 다양체 위의 최적화로도 볼 수 있고, 고정계수 다양체 위의 리만 경사법·그라스만 다양체 위의 부분공간 추적(GROUSE)이 같은 계열이다.

5. 이론이 깨지는 곳 — 결측은 무작위가 아니다[편집]

정리의 전제는 관측 위치가 균일 무작위라는 것이다. 현실 데이터는 거의 항상 이걸 어긴다.

• 자기선택. 사용자는 아무 영화나 보고 평점을 남기지 않는다. 보고 싶은 걸 골라 보고, 그중에서도 감정이 움직인 것에만 평점을 남긴다. 결측이 관측되지 않은 값 자체에 의존하는 MNAR(missing not at random) 구조다. “평점이 없다”가 “안 봤다”이면서 동시에 “재미없어 보였다”라는 정보를 담고 있다.
• 인기 편중. 관측 밀도가 행·열마다 자릿수로 다르다. 인기 영화 한 편의 평점 수가 비인기작 만 편을 합친 것보다 많다.
• 구조적 결측. 센서가 죽으면 그 행 전체가, 실험 조건이 빠지면 그 열 전체가 통째로 비는데, 한 행이 통째로 비면 어떤 알고리즘도 그 행을 복원할 수 없다.

첫 번째가 특히 고약하다. MNAR에서는 관측된 값들만으로 학습한 모형이 체계적으로 편향된다 — 평점 평균이 실제 선호보다 높게 나오는 것이 대표 증상이다. 대응은 두 갈래다. 결측 메커니즘 자체를 모형화해 함께 추정하거나, 관측 성향(propensity)을 추정해 역확률 가중을 걸어 균일 표본인 것처럼 보정하는 것. 후자는 인과추론의 표준 도구를 그대로 빌려 온 것이고, 성향 추정이 틀리면 분산이 폭발한다는 대가도 같이 딸려 온다.

그래서 실무는 이론적 보증 없이 정칙화 ALS를 돌린다. 표본 복잡도 정리는 “이 문제가 원리적으로 풀린다”는 존재 증명으로서의 가치가 크고, 현장 시스템의 성능 보증서는 아니다. 성능은 결국 교차검증으로 재는 수밖에 없으며, 과적합을 막는 것은 $\lambda$ 와 $r$ 두 손잡이다.

6. 응용[편집]

• 추천 시스템. 사용자×아이템 평점 행렬. 저계수 가정의 의미는 “취향을 결정하는 잠재 요인이 몇십 개뿐”이라는 것이고, $U$ 의 행이 사용자 취향 벡터, $V$ 의 행이 아이템 특성 벡터가 된다. 넷플릭스 프라이즈(2006–2009)가 이 분야를 통째로 만들었다.²
• 센서망 위치추정. 노드 간 거리를 일부만 측정했을 때 좌표를 복원하는 문제는 유클리드 거리 행렬(EDM) 완성이며, EDM은 좌표 차원 $d$ 에 대해 계수가 $d+2$ 이하로 묶인다. 이중 중심화하면 그람 행렬 완성이 되고, SDP + 저계수 문제로 떨어진다. 다차원 척도법의 결측 버전이라고 봐도 된다.
• 시스템 식별. 입출력 데이터로 만든 한켈 행렬의 계수가 곧 상태공간 모형의 차수다. 데이터가 비거나 잡음이 있을 때 “저계수 한켈 행렬 완성”으로 정식화하면 차수 결정과 식별이 한 문제가 된다. 구조 진동 계측에서 채널이 빠진 경우의 모드 해석도 같은 틀에 들어간다.
• 결측 스냅숏 복원. 시뮬레이션·PIV 스냅숏 행렬은 물리적으로 저계수인 경우가 많다. 적합직교분해 기반 축소모형에서 센서 몇 개로 전체 유동장을 재구성하는 갭피 POD가 이 계열이고, 압축센싱류 센서 배치 문제와 붙는다.
• 강건 변형. 관측에 희소한 이상치가 섞이면 $M = L + S$ (저계수 + 희소)로 분해하는 강건 주성분 분석으로 넘어간다. 배경/전경 분리가 교과서 예제다.

7. 실무 체크리스트[편집]

• 관측률과 자유도를 먼저 세라. $|\Omega| < r(m+n-r)$ 이면 어떤 알고리즘도 못 한다. 이 부등식을 확인하지 않고 튜닝부터 하는 것이 가장 흔한 시간 낭비다.
• 행·열 관측 수의 히스토그램을 그려라. 관측이 0인 행/열이 있으면 그건 완성 문제가 아니라 콜드 스타트 문제이고, 부가 정보(메타데이터) 없이는 해결되지 않는다.
• $r$ 을 크게 잡고 정칙화로 눌러라. $r$ 을 정확히 맞히려 애쓰는 것보다, 넉넉히 잡고 $\lambda$ 로 실질 계수를 통제하는 쪽이 안정적이다. 관측이 촘촘한 부분행렬을 떼어 특이값 스펙트럼을 그려 보면 대략의 감이 잡힌다.³
• 전체 행렬을 조립하지 마라. 답은 $U, V$ 인수 형태로 들고 다닌다. $UV^\top$ 을 명시적으로 만드는 순간 $O(mn)$ 메모리가 돌아와 저계수의 이득이 사라진다.
• 평가는 관측 분포와 같은 분포에서 하지 마라. 랜덤하게 뗀 검증 집합의 RMSE는 MNAR 편향을 그대로 물려받는다. 가능하면 무작위 노출 실험 데이터를 따로 확보하는 것이 정석이다.

8. 관련 문서[편집]

• 저랭크 근사 · 특이값 분해 · 주성분 분석 · 랜덤화 SVD
• 압축센싱 · 기저 추구 · 볼록 최적화 · 반정부호 계획법
• 근접 경사법 · 교대방향 승수법 · 확률적 경사하강법 · 약볼록 함수
• 리만 다양체 · 그라스만 다양체 · 란초스 알고리즘
• 추천 시스템 · 시스템 식별 · 적합직교분해 · 모드 해석
• 슈어 보수 · 행렬 곱셈 · 교차검증 · 과적합

9. Footnotes[편집]

1. $nr\log^2 n$ 의 로그 두 개가 꼭 필요한지는 오래 논쟁거리였다. 하나로 줄일 수 있다는 결과들이 있고, 정보이론적 하한은 $\Theta(nr\log n)$ 쪽이라 상수와 로그 하나 정도의 간격이 남아 있다고 보면 된다. 실무 감각으로는 “자유도의 몇 배”만 기억하면 되고, 그 몇 배가 로그다. ↩

2. 넷플릭스는 480,189명 × 17,770편에서 약 1억 개의 평점을 공개했다. 밀도로 치면 1.2%, 즉 98.8%가 구멍이었다. 우승팀 BellKor’s Pragmatic Chaos가 RMSE 10.06% 개선으로 100만 달러를 받았지만, 정작 그 앙상블은 운영 비용이 감당이 안 돼 실서비스에 들어가지 못했다. 대회가 남긴 진짜 유산은 알고리즘이 아니라 “잠재요인 모형 + 정칙화 + 편향항”이라는 표준 레시피와, 익명화된 데이터가 외부 데이터와 결합하면 재식별된다는 교훈(그래서 2편 대회가 취소됐다)이다. ↩

3. 그럼에도 저계수 가정 자체는 놀랍도록 잘 버틴다. 평점 행렬의 특이값 스펙트럼을 로그축에 찍어 보면 수십 번째부터 완만해지는 경우가 흔하고, 그게 “취향은 몇십 개 축으로 대충 설명된다”는 다소 서글픈 경험적 사실이다. 사람이 생각보다 예측 가능하다는 발견 위에 이 산업 전체가 서 있다. ↩