SVD & PCA

Everafter·2022년 11월 27일

ML Study 2022

목록 보기

10/10

SVD(Singular Value Decomposition)

SVD의 종류

전체 SVD (Full SVD)

특이값 분해(SVD; Singular Value Decomposition)

실수 항들을 갖는 $n \times d$ 행렬 $D$ 는 항상 다음의 3개의 행렬로 분해될 수 있다.

D = Q\Sigma P^T \\ Q:n\times n, \space \Sigma: n\times d, \space P:d\times d

$Q$ 와 $P$ 는 직교 행렬(Orthogonal), $\Sigma$ 는 ‘비음수’ ‘비정방형’ 대각행렬(Diagonal)이다.

더 자세한 구성은 다음과 같다.

$Q$ 를 구성하는 $n$ 개의 ‘좌 특이벡터’ 열은 $n \times n$ 행렬 $DD^T$ 의 $n$ 개의 고유벡터에 해당한다. $DD^T$ 가 대칭행렬이므로 고유벡터들은 모두 직교정규한다.
$P$ 를 구성하는 $d$ 개의 ‘우 특이벡터’ 열은 $d \times d$ 행렬 $D^TD$ 의 $d$ 개의 고유벡터에 해당한다. $D^TD$ 가 대칭행렬이므로 고유벡터들은 모두 직교정규한다.
$n \times d$ 비정방형 대각행렬 $\Sigma$ 의 대각 항들에는 $D^TD$ 또는 $DD^T$ 의 $\mathrm{min}\{n, d\}$ 개의 가장 큰 고윳값들의 제곱근인 특이값들이 들어간다.

존재성의 증명은 추후에 따로 다루겠다.

절약형 SVD (Thin SVD)

$n$ 과 $d$ 의 값이 다르면 $Q$ 와 $P$ 둘 중 $\left\vert n-d \right\vert$ 개의 ‘짝 없는’ 고유벡터가 남게 된다. 이는 실제 값에 영향을 주지 않으므로 ‘절약형 SVD’를 유도할 수 있다.

스펙트럼 분해 꼴의 ‘절약형 SVD’는 다음과 같다.

D = Q\Sigma P^T = \sum_{r=1}^{\mathrm{min}\{n, d\}} \sigma_{rr} \bar{q_r} \bar{p_r}^T \\ Q : n\times p, \Sigma : p \times p, P : d \times p \\ p = \mathrm{min}\{n, d\}

조밀 SVD (Compact SVD)

$\mathrm{min}\{n, d\}$ 개의 $\sigma_{rr}$ 중 0의 값이 존재한다는 가정 하에 분해의 크기를 더 줄일 수 있다. 특이값을 내림차순으로 정렬하여 $k$ 개의 양의 특이값이 존재한다고 할 때 위 분해는 다음과 같이 개선된다.

D = Q\Sigma P^T = \sum_{r=1}^{k} \sigma_{rr} \bar{q_r} \bar{p_r}^T \\ Q : n\times k, \Sigma : k \times k, P : d \times k

절삭 SVD (Truncated SVD)

$\sigma_{rr} = 0$ 인 성분 뿐만 아니라 $\sigma_{rr}$ 이 매우 작은 성분도 제거하여 $rank$ 가 $k$ 인 ‘근사’ 형태를 얻을 수 있다. (크기 순으로 상위 $k (< \mathrm{min}\{n, d\})$ 개의 특이값에 대응하는 성분만 유지)

D \approx D_k= Q_k\Sigma_k P_k^T = \sum_{r=1}^{k} \sigma_{rr} \bar{q_r} \bar{p_r}^T \\ Q_k : n\times k, \Sigma_k : k \times k, P_k : d \times k

절삭 SVD와 정확도 손실

절삭 SVD에서 $P_k$ 를 $k$ 개의 $d$ 차원 기저 벡터 집합, $Q_k\Sigma_k = U_k$ 를 $D_k$ 의 $P_k$ 의 기저벡터에 의한 $k$ 차원 표현 즉, $D$ 의 축소된 $k$ 차원 표현이라 볼 수 있다.

U_k = DP_k = Q_k\Sigma_k

근사에 의한 정확도 손실을 정량화 하는 방법으로 원본 $D$ 와 근사 $D_k$ 의 ‘프로베니우스 노옴 제곱’ 값을 비교한다.

\lVert D \rVert_F^2 \approx \lVert D_k \rVert_F^2 = \lVert \sum_{r=1}^k \sigma_{rr}\bar{q_r}\bar{p_r}^T \rVert_F^2 = \sum_{r=1}^k \sigma_{rr}^2\lVert\bar{q_r}\bar{p_r}^T\rVert_F^2 = \sum_{r=1}^k \sigma_{rr}^2

보통의 경우 특이값은 어떤 임계치에서 급격히 값이 감소하는 경향을 보이므로, $k$ 가 매우 작은 ‘저 순위 근사’임에도 높은 근사율을 갖게 된다.

기하학적 의미

$D^TD$ 는 $D$ 의 산포도 행렬인데, 이 행렬의 최상위 $k$ 개의 고유벡터는 가장 큰 산포도를 갖는 방향을 유지하게 된다. (단, SVD는 데이터를 평균중심화하지 않는다. PCA는 데이터를 평균중심화한다.)

이는 SVD가 다음의 무제약 최적화 문제의 해답이기도 한 것과도 연관된다.

\mathrm{Minimize}_{U, V} J = \lVert D-UV^T\rVert_F^2 \\ U:n \times k, V : k \times d

PCA (Principal Component Analysis)

SVD와의 관계

주성분 분석(PCA; Principal Component Analysis) 는 SVD와 밀접한 관련이 있다.

SVD는 $k$ 차원 부분공간에 투영된 데이터의 ‘원점과의 거리 제곱’이 최대화 되지만, PCA는 ‘데이터 평균’과의 거리 제곱이 최대화된다. 데이터 평균과의 거리 제곱은 ‘분산’으로 포착된다. 즉,

PCA는 평균중심 데이터 세트 $D$ 에서 SVD와 정확히 동일한 차원 축소를 수행한다

PCA의 성질

PCA에서는 $D$ 의 각 행에 $d$ 차원 평균 벡터를 빼서 평균 중심화를 먼저 진행한다.

M = D - \bar{1}\bar{\mu}

이후 공분산 행렬 $C$ 를 얻는다.

C = {M^TM \over n}

$C$ 는 양의 준정부호 행렬이므로 $rank = k$ 에서 다음과 같이 근사 대각화될 수 있다.

C \approx V\Delta V^T \\ V : d \times k, \Delta : k\times k

$V$ 의 열은 $C$ 의 상위 $k$ 개의 고유 벡터로, PCA의 주성분이 된다.

이때 $\Delta$ 의 $(r, r)$ 번째 성분 $\lambda_r^2$ (PCA의 고윳값)과 SVD의 $r$ 번째 특이값 $\sigma_{rr}$ 의 관계는 다음과 같다.

\lambda_r^2 = {\sigma_{rr}^2 \over n}

$M$ 의 $n$ 개 행들을 $V$ 의 열 벡터에 투영하여 얻어진 $k$ 차원 표현은 $n \times k$ 행렬 $U$ 로 구해진다.

U = MV

이때 $U$ 에서도 평균중심 성질은 유지되며, $U$ 에서 유지되는 분산은 $\sum_{i=1}^k \lambda_i^2$ 로 주어진다.

{U^TU\over n} = V^T{M^TM \over n} V = V^T(CV) = [v_1 ... v_k]^T[\lambda_1^2v_1 ... \lambda_k^2v_k] = \Delta

위 결과 처럼 $U$ 의 공분산 행렬이 $\Delta$ 가 되기 때문이다.

원본 데이터 세트의 복구는 다음과 같이 이루어진다.

D \approx D_{pca} = UV^T + \bar{1}\bar{\mu}

PCA와 SVD의 비교

정보 손실률은 PCA가 SVD가 우수하다. 절삭 SVD와 PCA를 이용한 $D$ 의 $k$ 차원 근사가 $D_{svd}, D_{pca}$ 일 때, 다음이 성립한다.

\lVert D-D_{pca}\rVert_F^2 \le \lVert D-D_{svd} \rVert_F^2

등호는 $D$ 가 평균 중심 데이터일 때 성립한다.

Latent Dimension의 결정

Reconstruction error

PCA에 의해 $L$ 차원으로 근사된 데이터셋 $D$ 의 reconstruction error은 다음과 같다.

\mathcal{L}_L = {1\over \left\vert D \right\vert} \sum_{n \in D} \lVert x_n - \hat{x}_n \rVert^2

Scree plots

\mathcal L_L = \sum_{j = L+1}^D \lambda_j

F_L = {{\sum_{j = 1}^{L} \lambda_j}\over {{\sum_{j' = 1}^{L_{max}} \lambda_{j'}}}}

Profile likelihood

기본 아이디어 : 특정한 $L^*$ 이 가정하여 $\lambda_1\ge \lambda_2 \ge ... \ge \lambda_{L^* -1}$ 의 분포와 $\lambda_{L^*} \ge ... \ge \lambda_{L_{max}}$ 의 분포가 가장 명확히 차이나게 되는 임계값 $L^*$ 를 찾는다.

이때 $\lambda$ 의 확률 분포는 $\mathcal{N}$ 을 가정한다. 즉,

\lambda_k \sim \mathcal{N}(\mu_1, \sigma^2) \ \ if \ k\le L \\ \lambda_k \sim \mathcal{N}(\mu_2, \sigma^2) \ \ if \ k\gt L

을 가정하고, 이 가정에 가장 잘 따르게 되는 $L^*$ 을 likelihood를 이용해 찾는다.

\mu_1(L) = {{\sum_{k \le L} \lambda_k} \over L} \\ \mu_2(L) = {{\sum_{k \gt L} \lambda_k} \over {L_{max} - L}} \\ \sigma^2(L) = {{\sum_{k\le L}(\lambda_k - \mu_1(L))^2 + \sum_{k \gt L}(\lambda_k - \mu_2(L))^2} \over {L_{max}}}

Profile log likelihood는 다음과 같다.

l(L) = \sum_{k=1}^L \mathrm{log} \ \mathcal N (\lambda_k \vert \mu_1(L), \sigma^2(L)) + \sum_{k=L+1}^{L_{max}} \mathrm{log} \ \mathcal N (\lambda_k \vert \mu_2(L), \sigma^2(L))

이후 likelihood가 최대가 되는 $L^*$ 을 선택하면 된다.

SVD, PCA의 활용

차원 축소

SVD와 PCA의 가장 큰 활용은 차원 축소이다. $d\times k$ 의 기저 행렬 $V$ 가 주어지면, $n \times d$ 데이터 행렬 $D$ 를 $n \times k$ 데이터 행렬 $D_k = DV$ 로 변환한다.

SVD에 더 적합한 데이터의 예는 ‘텍스트 데이터’다. 평균 중심화를 거치면 데이터 희소성이 망가지기 때문에 SVD를 텍스트 데이터에 이용하며, 이를 잠재 의미 분석(LSA; latent semantic analysis)라 한다.

이미지 압축에도 활용된다. 적절한 $rank$ 의 SVD, PCA를 활용하여 정보 손실을 최대화 하며 노이즈 제거 효과도 얻을 수 있다.

노이즈 제거

예로, 이미지 데이터에 소량의 노이즈가 포함된 경우 SVD를 진행하게 되면 하위 특이값 성분들에게서 노이즈가 나타나게 된다. 따라서 하위 성분을 절삭하게 되면 노이즈 제거 효과를 얻는다.

텍스트 데이터의 경우 언어들에 본질적으로 따르는 노이즈와 모호성 효과(동의어, 다의성)를 줄여준다. SVD의 상위 성분은 단어의 상관관계에 초점을 맞추는 경향이 있어 문맥을 고려한다.

특징 전처리와 백색화

데이터의 차원을 PCA로 축소한 다음, 변환된 특징들을 정규화 하여 각 특징 벡터 방향에 따른 데이터 분산이 동일하도록 특징 전처리가 가능하다. $U_k = DV_k$ 로 변환한 뒤, 각 열을 표준편차로 나누어 주어 정규화 하는 식이다. 이를 백색화(whitening)이라 한다.