Eigenvalue, Eigenvector, PCA, SVD

Research/Machine Learning

Eigenvalue, Eigenvector, PCA, SVD

IMCOMKING 2014. 7. 18. 15:53

# 아이겐 벡터와 아이겐 벨류의 의미 : 3*3으로된 행렬에 일련의 값들이 들어있다고 하자. 이 값들은 3차원 공간상에 점들로 표현될 수 있다. 그런데 만약 이 점들에 전부 x,y위에만 존재한다면, 이는 사실 x,y 2개의 차원만으로 표현될 수 있는 데이터였던 것이다. 이러한 n*n행렬에서의 핵심 차원을 알아내는 것이 바로 아이겐 벡터와 아이겐 벨류이다.

# 정의 : 임의의 정방행렬(n*n) A에대해, AB=λB를 만족하는 (단, B는 0이 아닌 벡터) B를 eigenvector, 상수 λ를 eigenvalue 라고 한다.

- 직관적 해석 : A라는 행렬에 벡터 B를 곱하여 선형 변환(프로젝션)시켰을 때, B 벡터가 그리는 직선(상수 λ가 미지수이므로)위에 행렬 A가 놓여지는 것을 의미한다.

즉, 임의의 벡터 B를 통해 행렬 A를 프로젝션하고, 그 벡터가 그리는 직선상의 한 점으로 표현한 것을 의미한다.

(엄밀하게는 행렬 A의 컬럼 벡터들을, 벡터 B로 프로젝션 시킨다음, 각 컬럼벡터들을 다 더한 한개의 점 = 벡터 B 직선위에 존재하는 임의의 한 점이 되도록하는 식이다.)

(보통 행렬 A와 벡터x의 곱셈 Ax는 "행렬A로 벡터x를 선형변환 시켰다" 라고 해석된다. 그이유는 행렬이 하나의 연산자로써 적용되고 벡터x를 데이터로 해석하는 관점이 일반적이기 때문이다. 그런데 아이겐벡터에서는 행렬A가 데이터로써 주어지고, 벡터 B를 찾아서 계산하는 관점이기 때문에 행렬 A를 벡터로 선형변환한 관점에서 해석하였다.)

# eigenvalue, eigenvector 계산 : AB=λB, (단 B는 0이아님) 이라는 수식을 역행렬이 존재하지 않는다는 조건으로 풀어서 계산한다. 일단 AB-λB=0 꼴로 놓은뒤, 이를 벡터 B의 성분(a,b)에 대해서 묶으면

[1-λ 1] [a] = [0]
[1 2-λ] [b] [0]

과 같은 식이 나온다. 이 때 (a,b)는 0이 아니므로, 역행렬이 존재해서는 안된다.(역행렬이 존재하면 a,b는 무조건 0이 되어버리기 때문에)

따라서 ad-bc=0 이므로, 이를 이용해 λ를 계산한다. 이렇게 eigenvalue를 계산한 다음, 구해진 λ를 위에서 구한 판별식에 대입하면 a=2b 등과 같은 형태의 식을 얻을 수 있다. 그러면 결국 (a,b)의 벡터에 이를 대입하면 (2b,b) 가되고, λ는 임의의 실수를 뜻하기 때문에 b를 약분하여 (2,1)의 아이겐 벡터를 얻을 수 있다.

이렇게 구해진 아이겐 벡터는 서로 직교한다.(내적해서 0이된다.)

Eigenvector(고유 벡터) : 행렬 A를 가장 잘 표현하는 직선의 방향을 의미하는 벡터들이다.

Eigenvalue(고유 값) : 아이겐 벡터들의 계수를 의미한다. 그런데 이 값은 해당 벡터가 그리는 직선의 길이라고 생각을 할 수 있다. 즉, 해상도가 높은 벡터는 이 고유 값이 클 것이라고 해석할 수 있다.

그래서 PCA를 수행할 때, 이 아이겐 벨류의 weight(전체 고유값중에 몇퍼센트를 차지하는 지)를 계산하여 가장 설명력이 높은 벡터를 결정한다.

Eigendecomposition: AB=Bλ에서 B의 역행렬을 양변에 곱한것.

${\begin{aligned}\mathbf {A} \mathbf {v} &=\lambda \mathbf {v} \\\mathbf {A} \mathbf {Q} &=\mathbf {Q} \mathbf {\Lambda } \\\mathbf {A} &=\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{-1}.\end{aligned}}$

https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix

이 covariance matrix를 아이겐 디컴퍼지션하게 되면, 아이겐벨류는 대각행렬이 되고, 여기에는 대각선성분 분산만 남게 된다.

즉 다시말해 다른 차원과 correlation이 있는 공분산의 값은 모두 0이 되고, 분산만으로 표현하는 공간에 데이터를 보내는 것이다.

Whitening: Noise를 제거하고 저차원의 유효한 정보만 남기는 것.

PCA whitening: PCA를 수행한 다음 값이 큰 eigenvalue들만 일부 취하여 해당 eigenvector로 만든 eigenspace에 데이터를 projection 시켜서 저차원의 feature로 줄이는 것

SVD : 의미적으로 이러한 아이겐벨류 디컴퍼지션을 n*n의 정방행렬이 아닌, n*m의 행렬에 수행하도록 확장한 개념이다. 풀네임으로는 singular value decomposition 이라 한다.

계산이 끝나면 A = U S V 형태로 decomposition이 된다. U는 left 열벡터, V는 right 열벡터, S는 대각선 싱귤러 벨류이다.

svd는 AAt를 고유값분해, AtA를 고유값분해 한 것을 합친것이다. 그리고 이둘간의 공통 고유값들에 루트를 취해서 싱귤러 밸류를 구하고, 이것을 대각성분으로 사용한다.(AAt로 제곱한거라서 루트씌워주는 느낌)

그런데 이 U S V를 다곱하면 신기하게도 A가 나온다! 또 재밌게도 AAt와 AtA는 항상 공통의 고유값을 가진다.

또한 이것을 이용해서 슈도 인버스 매트릭스를 계산하기도하고, orthogonal matrix로 weight matrix를 초기화시켜줄 때 쓰기도하고, 굉장히 다양한 쓰임새가 있음.

아래 블로그에 잘 정리 및 증명이 됨.

http://darkpgmr.tistory.com/106

----------

PCA(Principle Components Analysis) : 데이터의 각 변수 차원에 대해 공분산 행렬을 구하고, 여기에 Eigenvalue Decomposition 을 하여, 모든 변수들을 가장 잘 설명하는 축을 찾는 방법.

(아이겐벡터 디컴퍼지션으로 공분산이 0이되고 ,분산만 남도록 하여 코릴레이션 없이 가장 압축을 잘하는 벡터를 찾는다.)

eigenvector를 이용해서 개발된 PCA(주성분분석법)는 영상 처리등에서 차원을 축소할 때 많이 쓰이는 방법이다.
원리는 전체 데이터들 편차에대한= 공분산 행렬을 계산한 다음, 그 공분산 행렬에대한 Eigenvalue 와 Eigenvector를 구한다음 전체데이터를 그 Eigenvector에 정사영 시켜서 데이터들의 패턴을 파악한다.

1. N차원의 데이터에 대해 각 차원의 평균에 대해 뺄샘을 하여 평균이 0이 되도록 shift 한다.
2. 위 데이터에 대해 N*N의 covariance matrix를 계산한다.
3. 아이겐 벨류 디컴퍼지션을 하여, 공분산 행렬을 가장 잘 설명하는 벡터를 찾는다.

4. 이렇게 찾은 벡터를 몇개 정하여(보통 아이겐 벨류의 weight가 90%넘는 벡터들을 선택), 해당 space로 정사영시켜 데이터를 다루는 차원축소를 수행한다.(2~3차원으로 줄여서 시각화하는 용으로도 많이 쓰인다.)

http://en.wikipedia.org/wiki/Principal_component_analysis

- 수식 이해

http://darkpgmr.tistory.com/110

위 블로그의 맨 밑부분에 나온 수식이 매우 중요함.

PCA는 임의의 방향 벡터에 데이터들을 정사영 시킨 값들이 최대가 되도록하는 방정식을 푼 것이다.
이를 풀어내면 결국 covariance 매트릭스에 대해 eigenvalue decomposition을 한 것이 된다.

-------

http://coolstu.blog.me/130176439747

http://darkpgmr.tistory.com/105

PCA : http://dokim.tistory.com/169

http://blog.naver.com/leerider/100190679279

http://darkpgmr.tistory.com/110