9. 주성분과 최적의 낮은 랭크 행렬
강의 내용
Lecture 7: Eckart-Young: The Closest Rank k Matrix to A | Matrix Methods in Data Analysis, Signal Processing, and Machine Learn
Description In this lecture, Professor Strang reviews Principal Component Analysis (PCA), which is a major tool in understanding a matrix of data. In particular, he focuses on the Eckart-Young low rank approximation theorem. Summary \(A_k = \sigma_1 u_1 v^
ocw.mit.edu
에카트 영 Eckart-Young 정리
$A = \sigma_1 u_1 v_1^T + \cdots + \sigma_r u_r v_r^T $
$A_k = \sigma_1 u_1 v_1^T + \cdots + \sigma_k u_k v_k^T $
행렬 $A_k$ 는 rank $k$ 인 행렬 $B$ 에 대해서 아래를 만족한다.
$ ||A - B || \geq || A - A_k $
이는 에카트 영 Eckart-Young 정리이다.
여기서 $ || A || $ 는 무엇을 의미할까?
norm 이라고 부르는 || || 은 행렬 $A$ 가 얼마나 큰지를 의미한다. 이를 계산하는 법은 다양하다.
벡터의 norm ?
L2 Norm : $ || v ||_2 = \sqrt{ |v_1|^2 + \cdots + |v_n|^2 } $
L1 Norm : $ ||v||_1 = |v_1| + \cdots + |v_n| $
L$\infty$ Norm : $ ||v||_{\infty} = \max |v_i| $
Norm 에 상수곱 : $||cv|| = |c| ||v||$
합의 Norm : $||v+w|| \leq ||v|| + ||w||$
행렬의 norm?
합의 Norm : $|| A + B || \leq ||A|| + ||B||$, 행렬합의 첫 특이값은 각 행렬 첫특이값의 합보다 작거나 같다.
L2 Norm : $|| A ||_2 = \sigma_1 $
L Frobenius Norm : 각 행렬의 원소를 제곱합후 제곱근 취한값 $ ||A||_F = \sqrt{|a_{11}^2| + \cdots + |a_{1n}^2| + \cdots + |a_{m1}^2| + \cdots + |a_{mn}^2| } $
L Nuclear Norm : 행렬의 모든 특이값의 합 $||A||_N = \sigma_1 + \cdots + \sigma_r $
Nuclear Norm 은
Netflix Competition 에서 단지 사용자의 영화 선호정보만으로, 아직 보지않은 영화들의 랭킹을 가지는 행렬을 만들고 이를 정확히하기 위해 이용되고,
MRI 에서 장치안에 충분히 오래머물면 완벽한 정보를 얻어 깨끗한 이미지를 얻겠지만, 그럴수없기 때문에 곳곳에 missing 된 데이터들이 존재한다. 이 부족한 이미지 행렬을 채우기위해 Nuclear Norm 을 사용한다.
3가지 Norm 을 다루는 이유는 위의 에카트 영 정리를 만족하는 Norm 측정방식이기 때문이다.
에가트 영 정리에 대한 예시를 보자.
$ \Sigma = \begin{bmatrix} 4 & & & \\ & 3 & & \\ & & 2 & \\ & & & 1 \\ \end{bmatrix} $
$ \Sigma_2 = \begin{bmatrix} 4 & & & \\ & 3 & & \\ & & 0 & \\ & & & 0 \\ \end{bmatrix} $
$\Sigma$ 와 비슷할거같은 rank 2 행렬 $B$ 를 만들어보자.
$ B = \begin{bmatrix} 3.5 & 3.5 & & \\ 3.5 & 3.5 & & \\ & & 1.5 & 1.5 \\ & & 1.5 & 1.5 \\ \end{bmatrix} $
여기서 $B$ 의 랭크를 2로 만들기 위한 대각성분이 아닌값들에 의해 $\Sigma_2$ 가 더 가까워지겠지만, 이 행렬들중 뭐가 더 가까운지는 명확하지는 않다.
각 Norm 에 대한 에카트 영 정리 증명은 아래서 진행할 예정이다.
벡터의 L2 Norm 에 대해서 직교행렬 $Q$ 를 곱한 벡터의 Norm 은 변하지 않는다.
$||Qv|| = (Qv)^T(Qv) = v^Tv = ||v|| $
행렬 $A =U \Sigma V^T$ 에 대해서, 직교행렬 $Q$ 를 곱하면, $QA = QU \Sigma V^T$
$QU$ 는 직교행렬간의 곱으로 크기는 변하지않는다. 따라서 $QA$ 의 크기또한 변하지 않을것이다.
주성분 분석 Principal Compoment Analysis
나이와 키에 대한 정보를 가지는 2 x N 행렬 $A$ 에 대해서 생각해보자.
이 속성들에 대한 관계를 어떻게 찾을 수 있을까?
먼저, 통계학에서 데이터들의 평균을 0 으로 만든다. 각 속성에 대한 평균을 구하고, 각 속성의 평균을 0 으로 맞춘다.
그러면 모든 데이터는 평균 0 을 갖게된다. 각 속성의 평균이 0 이기때문이다.
이 2차원 평면에 있는 데이터들에 대한 가장 알맞는 직선의 기울기는 무엇일까?
least square 과 동일하게 계산하면 되지않냐? $ || b - Ax||^2 $ 를 최소화 ?
PCA 에서는 직선에 수직인 값을 측정하기 때문에 least square 과는 다르다! 따라서 다른 값을 도출한다.
least square 은 $\min || b- Ax||^2$ 식을 풀고 이를 편미분하면 $ A^TA \hat{x} = A^Tb$ 이라는 Normal Equation 을 도출한다.
즉 PCA 와는 다른 문제이다.
그럼 PCA 는 어떻게 풀수있을까?
데이터의 평균을 0 으로 만든상태에서, 각 속성들의 분산과 각 속성끼리의 공분산을 구해야한다.
각 분산은 각 속성끼리 얼마나 차이가 있는가 이고, 공분산 행렬은 각 속성끼리 어떻게 연관되어있는가 이다.
근데 여기서 구한 분산과 공분산 행렬은 데이터에서 찾은것으로 표본공분산행렬 Sample Covariance Matrix 라고 부른다.
그 행렬은 $\frac{AA^T}{N-1}$ 으로 구할수 있다. 여기서 $N-1$ 으로 Normalize 하는 이유는 평균을 0 으로 만들때 자유도를 사용했기 때문이다.
책 내용
행렬 $A$ 의 주성분은 $A$ 의 특이벡터이자 직교행렬 $U$, $V$ 의 열벡터 $u_j$, $v_j$ 이다.
주성분 분석은 주어진 행렬 $A$ 에서 가장 중요한 부분 $A_k$ 를 추출한다.
$$ A_k = \sigma_1 u_1 v_1^T + \cdots + \sigma_k u_k v_k^T $$
$A$ 에 가장 가까운랭크 $k$ 행렬은 $A_k$ 이다. 통계학에서는 최대 분산으로 $A$의 부분을 식별하는데, 이 작업이 SVD 를 데이터 과학의 핵심으로 만들었다.
데이터과학의 PCA 는 비지도학습인데, 그 방향을 선형대수학 SVD 의 특이값이 제시한다.
PCA 는 $A_k$ 에 의한 행렬 근사에 기초하고, 이 행렬 근사는 에카트-영이 행렬에 대한 증명을 하여 랭크 $k$ 행렬 $A_k = \sigma_1 u_1 v_1^T + \cdots | \sigma_k u_k v_k^T $ 에 대해서
에카트-영 Eckart-Young 정리 : 랭크 $k$ 인 행렬 $B$ 에 대해 $||A - B || \geq || A - A_k||$ 를 만족한다.
행렬 Norm 을 계산하는 중요한 3가지 방법
- 스펙트럼 Norm : $||A||_2 = \max \frac{||Ax||}{||x||} = \sigma_1$
- 프로베니우스 Frobenius Norm : $||A||_F = \sqrt{ \sigma_1^2 + \cdots + \sigma_r^2 }
- 핵 Nuclear Norm : $||A||_N = \sigma_1 + \cdots + \sigma_r$
n x n 직교행렬 $Q$ 에 대해 세가지 Norm 은 다른 값을 가진다.
- $||Q||_2 = 1$
- $||Q||_F = \sqrt{n}$
- $||Q||_N = n$
또한 행렬 $A$ 의 양변에 직교행렬 $Q$ 를 곱해도 세 Norm 의 값은 변하지 않는다.
세 Norm 은 특이값에 대한 연산이고, 행렬 $A$ 와 $QA$ 의 특이값은 동일하기 때문이다.
$$ ||Q_1 A Q_2^T|| = ||A|| $$
에가트-영 정리 : $A_k$ 에 의한 최적 근사
스펙트럼 Norm 에서의 증명
위 강의에 사용했던 4x4 특이값 대각행렬에 가장 가까운 랭크 2 행렬은 $A_2$ 라고했었다.
이 정리를 $L^2$ Norm 에서 증명해보자.
$L^2$ Norm : $rank(B) \leq k$ 이면, $|| A - B || = \max \frac{||(A-B)x||}{||x||} \geq \sigma_{k+1}$
일단 $||A - A_k|| = \sigma_{k+1}$ ( L2 Norm 은 가장 큰 특이값 ) 임을 알고있고, $||A-B|| \geq \sigma_{k+1}$ 을 증명하기위해,
$Bx \neq 0$ 과, $x = \sum_1^{k+1}c_iv_i $ 가 성립하는 영이아닌 벡터 $x$ 를 선택하자.
$B$ 의 영공간 차원은 $n-k$ 이상이고, $v_1$ 부터 $v_{k+1}$ 까지의 결합은 $k+1$ 차원의 부분공간을 만들고, 이 공간과 $B$ 의 영공간은 반드시 교차한다. 적어도 한 직선을 공유한다.
그러면 $(A-B)x$ 를 통해 아래식을 도출할 수 있다. $Bx = 0$, $Av_i = \sigma_i u_i$
$$ ||(A-B)x||^2 = ||Ax||^2 = || \sum c_i \sigma_i u_i ||^2 = \sum_1^{k+1} c_i^2 \sigma_i^2 \\
= \sum_1^{k+1} c_i^2 \sigma_i^2 \geq \sum_1^{k+1} c_i^2 \sigma_{k+1}^2 =||x||^2 \sigma_{k+1}^2 \\
||(A-B)x|| \geq \sigma_{k+1}||x|| $$
벡터 $x$ 는 $||A-B||$ 의 하한을 준다. 즉 아래식이 성립한다.
$\frac{||(A-B)x||}{||x||} \geq \sigma_{k+1} $ 이므로, $ || A- B|| \geq \sigma_{k+1} = || A - A_k|| $ 이다.
프로베니우스 Frobenius Norm
프로제니우스 Norm 을 구하는 방식에 세가지가 있다.
- 행렬 $A$ 를 하나의 긴 벡터로 보고 L2 Norm 을 취하는 것
- 행렬 $A^TA$ 의 대각성분의 L2 Norm 을 취하는것
- 행렬 $A$ 의 특이값 $\sigma_k$ 의 L2 Norm 을 취하는 것
$||A||_F^2 = |a_{11}|^2 + \cdots + |a_{mn}|^2 $
$||A||_F^2 = A^TA$ 의 대각합 $= (A^TA)_{11} + \cdots + (A^TA)_{nn} $
$||A||_F^2 = \sigma_1^2 + \cdots + \sigma_r^2 $
프로베니우스 Norm 에서 에카트-영 정리
$||A-B||_F$ 에 대하여 피트 스튜어트 Pete Stewart 의 증명을 보자.
랭크가 $k$ 이하인 행렬 $B$ 가 행렬 $A$ 에 가장 가깝다고 가정하자. 우리는 $B=A_k$ 임을 증명하고 싶다.
행렬 $B$ 를 특이값분해 하면, k x k 대각행렬 $D$ 에 대해서 아래를 만족한다.
$$ B = U\begin{bmatrix}
D & 0 \\
0 & 0 \\
\end{bmatrix} V^T $$
$B$ 의 $U$, $V$ 가 $A$ 를 대각화하는 것은 아니므로 아래와 같이 쓸수있다. ( 왜인진 잘모르겠는데, 암튼 쓸수있음 -> $U$, $V$ 로 분해한 행렬 $A$의 나머지 행렬을 부분적으로 나타낸것인듯, 순하삼각행렬 + 대각행렬 + 순상삼각행렬은 온전한 행렬이됨. )
$$ A = U\begin{bmatrix}
L+E+R & F \\
G & H \\
\end{bmatrix} V^T $$
$L$ 의 처음 $k$ 개 행은 순하삼각행렬, $E$ 는 대각행렬, $R$ 은 순상삼각행렬이다. (순삼각행렬은 대각성분이 0 이다.)
$$ C = U\begin{bmatrix}
L+D+R & F \\
0 & 0 \\
\end{bmatrix} V^T $$
명백히 랭크 $k$ 이하인 인 행렬 $C$ ( 행렬의 row 중 k 개를 제외한 나머지 row는 0 이기때문에, 랭크가 최대 $k$ 이다. ) 를 도입해 $L$, $R$, $F$ 모두 영행렬임을 보일것이다.
직교행렬은 Norm 에 영향을 주지않고, $||A-B||_F^2$값을 구하기 위해 각 모든 원소를 제곱합하려는데 $C$ 를 통해 아래 식으로 분리해 구할수 있다.
$$ || A - B ||_F^2 = || A - C ||_F^2 + ||L||_F^2 + ||R||_F^2 + ||F||_F^2 $$
$||A - B||_F^2$의 최소값을 찾기위해서 $L$ $R$ $F$ 는 전부 영행렬이고, $G$ 도 영행렬이다. 각 원소가 모두 0 이여야 최소값임.
그 결과 아래식이 나온다.
$$ U^TAV = \begin{bmatrix}
E & 0 \\
0 & H \\
\end{bmatrix}, U^TBV = \begin{bmatrix}
D & 0 \\
0 & 0 \\
\end{bmatrix} $$
기본적으로 $||U^TAV||_F = ||A||_F $, $||U^TBV||_F = ||B||$ 이다.
여기서 $B$ 가 $A$ 에 가장 가깝다면, $U^TBA$ 이 $U^TAV$ 에 가장 가깝다. 이유는?
행렬 $B$ 가 $A$ 에 가장가깝다면, $B= A_k$ 이라면,
1. 행렬 $D$ 는 $E = diag(\sigma_1, \cdots, \sigma_k)$ 이어야 한다.
2. 행렬 $H$ 의 특이값은 행렬 $A$ 의 가장 작은 $n-k$ 개의 특이값이어야한다. ( $ ||U^TAV||_F = ||A|| $ 이기 위해서 )
3. 가장작은 오차 $||A-B||_F$ 는 $||A-A_k||_F = ||H||_F = \sqrt{ \sigma_{k+1}^2 + \cdots + \sigma_r^2 }$ 이어야 한다.
- 이 증명과정에 대해서 이해가 잘가진않는데 일단넘어감.
프로베니우스 거리 $||A-B||_F^2$ 의 최소화
에카트-영을 더 직접적으로 증명해보자. $||A-B||_F^2$ 의 도함수가 0 인 부분을 찾아보자.
랭크가 $k$ 인 행렬 $B$ 를 $B = CR = $ ( m x k ) ( k x n ) 행렬로 분해, 표현하자. 이것을 SVD 에 연결시켜 $C = U_k\Sigma_k$, $R = V_k^T$ 에 연결시켜본다.
우리가 구하는 것은 $E = ||A- CR||_F^2$ 를 최소화하는 $C$, $R$ 이다. 양변에 편미분을 취하면, 아래식이 나온다.
$$ \frac{\partial E}{\partial C} = 2(CR-A)R^T = 0 \\
(\frac{\partial E}{\partial R})^T = 2(R^TC^T - A^T)C = 0 $$
위 식을통해 $AR^T = CRR^T = C$ ( $R = V^T$ ) 와, $R^TD = A^TC = A^TAR^T $ ( $D = C^TC = \Sigma_k U^T U = \Sigma_k $ )
첫번째식 $AR^T = C$, 두번째식 $R^TD = A^TAR^T$ 을 얻는다.
두번째식을 변형하면 $A^TA = R^TDR$ 을 얻고, $D$ 는 대각행렬이고 $R^T$ 열은 정규직교하므로, $R^T$ 의 열들는 $A^TA$ 의 고유벡터 행렬이다.
식 $AA^TC$ 을 변형해보자. $AA^TC = AA^T(AR^T) = A(A^TAR^T) = AR^TD = (AR^T)D = CD$ 이고, 위와동일하게 $C$ 의 열들은 $AA^T$ 의 고유벡터이다. 이때 정규직교하지는 않음, 직교함.
$R^T$ 의 열은 $A$ 의 우특이벡터 $v_j$ 이고, $C$ 의 열은 $A$ 의 좌특이벡터 $u_j$ 를 포함한다. 같지는 않음.
$E = ||A-CR||_F^2$ 는 $C$ 와 $R$ 에 포함되지않은 $\sigma^2$ 의 합이다. 오차 $E$ 를 최소화하기위해 $B = CR$ 은 가장 큰 특이값행렬 $A_k$ 가 되어야하고, 그로인해 $E$ 는 가장 작은 $\sigma$들을 포함한다. 즉 $B = CR = A_k$ 일때 $E$ 는 최소이다.
주성분 분석
SVD를 통해 주성분 분석을 해보자. $n$ 개의 표본과, 각 $m$ 개의 변수로 이루어진 m x n 데이터 행렬 $A_0$ 이 있다.
먼저 $A_0$ 의 행 row ( 변수들 )을 따라 평균(표본평균)을 구해 뺀다. 그러면 중심화된 행렬 $A$ 각 행의 합은 0 이고 모든 요소의 합도 0 이다.
$m=2$ 인 행렬 $A$ 에 대해서, 모든 표본들에 가장가까운( 수직거리 ) 0 을 지나는 직선의 기울기는 $A$ 의 첫번째 특이벡터 $u_1$ 의 방향이다. 과연?
PCA 이면의 통계학
확률과 통계에서 가장 중요한 수는 평균과 분산이다. 데이터 행렬 $A_0$ 에서 $A$ 으로 변환해서 평균은 0 이고, 분산은 $A$ 의 각행을 따라 평균에서 떨어진 거리 제곱의 합이다. 여기서 평균이 0 이므로 분산은 $AA^T$ 의 대각성분이다.
각 변수들의 상관관계는 어떨까? 이를 나타내는 공분산은 $AA^T$ 의 대각성분(분산)을 제외한 성분들이다.
내적 ($A$ 의 $i$행)$\cdot$($A$ 의 $j$행) 인 공분산이 크면, 나이가 많을수록 키는 커진다. 대칭행렬이므로 키가 클수록 나이는 많다.
공분산이 작으면, 반대의 상관관계를 가진다. 표본수에 맞는 정확한 척도를 얻기위해 $n-1$로 나눈다.
표본 공분산행렬 Sample Covariance Matrix : $S = \frac{AA^T}{n-1}$
평균 0 으로 취하는데 하나의 자유도를 사용해서 $n-1$ 로 나눈다.
EX) $ A = \begin{bmatrix} 3 & -4 & 7 & 7 & -4 & -3 \\ 7 & -6 & 8 & -1 & 1 & -7 \\ \end{bmatrix} $ 인 평균을 0 으로만든 6명의 나이와 키 행렬이다.
표본 공분산행렬 $S$ 는 아래와 같다.
$$S = \frac{1}{6-1}AA^T = \begin{bmatrix} 20 & 25 \\ 25 & 40 \\ \end{bmatrix} $$
여기서 $AA^T$ 의 고유벡터는 $A$ 의 좌특이벡터 $u_j$ 와 같다는걸 이미알고있고,
$S$ 의 고유벡터 $u_1$, $u_2$ 에서 벡터 $u_1$ 은 데이터에 가장 가까운 직선의 방향을 의미한다.
벡터 $u_2$ 는 이 가장 가까운 선에 수직이다.
요악
PCA 는 대칭행렬 $S = \frac{AA^T}{n-1}$ 또는 직사각행렬 $A$ 로 나타낸다. $S$ 가 좋은 행렬임은 분명하지만, 이를 계산하고 대각화하는 것보다 $A$ 그 자체를 직접 특이값분해하는것이 더 빠르고 정확할 수 있다.
위 예시에서 $S$ 의 고유값은 57, 3 에 가깝고, 행렬 $A$ 의 첫번째 특이값은 두번째 특이값보다 훨씬크다. 또한 첫 좌특이벡터 $u_1 \approx (0.6, 0.8) $ 는 데이터 산점도에 가장가까운 직선의 기울기가 $\frac{8}{6}$ 임을 의미한다.
PCA 이면의 기하학
일반적인 최소제곱 least square 으로 이 문제를 푸는방식 $Ax=b$ 의 최소제곱해와는 다르다. 이는 $||Ax-b||^2$ 를 최소화하는것이고, 이는 최적직선의 위아래 거리를 측정한다. 이는 $A^TA \hat{x} = A^Tb$ 인 $\hat{x}$ 를 찾는다.
PCA 에서는 최적직선과 수직거리를 측정한다. 이 문제는 고유값 $\sigma^2$ 과 특이벡터 $u_i$ 으로 이어진다.
데이터 점에서 직선 $u_1$ 까지 거리의 제곱의 합이 최소값이다.
위의 명제가 참일까? $A$ 의 각 열 $a_j$ 를 특이벡터 $u_1$, $u_2$ 에 대한 식으로 분리하자.
$\sum_1^n ||a_j||^2 = \sum_1^n |a_j^T u_1|^2 + \sum_1^n |a_j^T u_2|^2$
데이터 행렬은 좌변을 고정하고 우변의 첫번째 항인 $|a_j^Tu_1|^2 = u_1^Ta_j a_j^T u_1$ 들의 합은 $u_1^T(AA^T)u_1$ 이 된다.
여기서 $u_1$ 을 $AA^T$ 의 첫 고유값으로 선택할때, $u_1^T (AA^T)u_1$ 은 최대가되고, $u_2^T(AA^T)u_2$ 는 최소가된다.
이 두번째항 $u_2^T(AA^T)u_2$ 가 의미하는것이 바로 첫번째 고유벡터 $u_1$ 의 방향에 해당하는 최적직선과 데이터들의 수직거리의 합이다. 이 값은 벡터 $u$ 가 고유벡터일 때 최소가된다.
PCA 이면의 선형대수학
주성분 분석은 $m$ 차원 공간의 $n$ 개의 표본 데이터들을 이해하는 한가지 방법이다. PCA 와 선형대수학을 연결하는 것이 특이값 $\sigma_i$ 와 특이벡터 $u_i$ 이다.
이들은 표본 공분산행렬 $S = \frac{AA^T}{n-1}$ 의 고유값 $\lambda_i = \sigma_i^2$ 에서 얻는다.
데이터의 평균은 0 으로맞춰져있고, 데이터들의 전체 분산은 각 데이터 성분의 제곱합이다. 전체분산 $T$
$$ T = \frac{1}{n-1} ||A||_F^2 = \frac{1}{n-1}(||a_1||^2 + \cdots + ||a_n||^2) $$
이는 $S$ 의 대각합이다. ( 기존 행렬들 $A$ 에 $n-1$ 을 나눈것과 동일 )
선형대수학은 대각합(전체분산)이 표본 공분산행렬 $S$ 의 고유값 $\frac{\sigma_i^2}{n-1}$ 의 합과 같다는 것을 알려준다.
전체분산 $T = \frac{1}{n-1} (\sigma_1^2 + \cdots + \sigma_r^2) $ 을 만족한다.
첫번째 주성분 $u_1$ 이 전체 분산의 제일 큰 분수 $\frac{\sigma_1^2}{T}$ 를 설명한다. 그 다음 주성분 $u_2$ 는 그다음 제일 큰 분수 $\frac{\sigma_2^2}{T}$ 를 설명한다.
에카트-영 정리의 핵심은 $k$ 개의 특이벡터가 다른 어떤 $k$ 개의 벡터보다 데이터를 잘설명한다는 점이다. 그래서 $n$ 개의 데이터 점에 가장 가까운 $k$ 차원 부분공간의 기저로 $u_1, \cdots, $u_k$ 를 선택해야 했다.
우리가 데이터에 대해 어떠한 $k$ 값을 선택해야할까? 행렬 $A$, $S$ 의 유효 랭크는 데이터에서 노이즈가 진짜 신호를 삼키는 지점위의 특이값 개수와 같다. 어떤 특이값 $\sigma_i$ 에서 급격하게 작아지는 지점을 스크리 플롯 scree plot 이라 한다.
나쁘게 조건화된 힐베르트 행렬 Hilbert matrix 에서 이러한 현상이 발견된다.