Search
Duplicate

이상엽/ 선형대수학/ 자료의 처리

우선순위 평가

인접행렬

개념

요소간의 연결 관계를 나타내는 정사각 행렬
참조한 (화살표가 나가는) 쪽은 행에, 참조된 (화살표를 받는) 쪽은 열에 쓴다.
1은 2와 3으로 화살표를 쏘고 있으므로, 1행은 2열과 3열에 값이 있음.

권위벡터와 허브벡터

n×nn \times n 인접 행렬 A=(aij)A = (a_{ij})에 대하여
(i=1nai1i=1nai2...i=1nain)\left( \begin{array}{rrrr} \sum_{i = 1}^{n} a_{i1} \\ \sum_{i = 1}^{n} a_{i2} \\ ... \\ \sum_{i = 1}^{n} a_{in} \end{array} \right)(j=1na1jj=1na2j...j=1nanj)\left( \begin{array}{rrrr} \sum_{j = 1}^{n} a_{1j} \\ \sum_{j = 1}^{n} a_{2j} \\ ... \\ \sum_{j = 1}^{n} a_{nj} \end{array} \right)을 각각 AA의 권위벡터와 허브벡터라 하며, 각 벡터의 성분을 권위 가중치와 허브가중치라 한다.
가중치로부터 중요도를 판단한다는게 아이디어
권위 벡터(u0u_{0})는 연관받은 (열) 데이터에 대한 벡터가 된다. 그 각각의 값은 권위 가중치가 된다.
허브 벡터(v0v_{0})는 연관한 (행) 데이터에 대한 벡터가 된다. 그 각각의 값은 허브 가중치가 된다.
권위 벡터와 허브 벡터는 상호작용을 기반으로 계속 값이 업데이트 된다.
업데이트 되는 와중에 어떤 기준선에 도달하여 값이 안정되면 최종적으로 그 벡터를 중요도 평가에 사용한다.

순위평가 원리

인접행렬 AA와 초기권위벡터 u0u_{0}와 초기허브벡터 v0v_{0}에 대하여
uk={u0k=0AvkTAvkTk>0, vk={v0k=0Avk1Avk1k>0u_{k} = \begin{cases} u_{0} & k =0 \\ {A_{v_{k}}^{T} \over \|A_{v_{k}}^{T}\|} & k > 0 \end{cases},  v_{k} = \begin{cases} v_{0} & k =0 \\ {A_{v_{k-1}} \over \|A_{v_{k-1}}\|} & k > 0 \end{cases}
현재 권위 벡터는 이전 허브 벡터의 값을 원본 행렬(의 전치 행렬)에 곱하여 구하고, 마찬가지로 현재 허브 벡터는 이전 권위 벡터의 값을 원본 행렬에 곱하여 구한다.
이 곱을 반복하여 값을 업데이트 한다.
다만 이것을 점화식을 이용해서 구성하면 자기 자신만 보면 되는 (권위 벡터는 권위 벡터만으로, 허브 벡터는 허브 벡터만으로) 해석적인 결과가 구성되고, 이를 컴퓨터에 넣어서 계속 돌리면 값이 나온다.
와 같이 새로운 정규화된 권위벡터 uku_{k}와 허브벡터 vkv_{k}를 정의한다. (kk는 정수)
이때 uk,vku_{k}, v_{k}를 연립하면 다음과 같이 정규화된 uku_{k}vkv_{k}의 점화식을 얻을 수 있다.
uk=AvkTAvkT=AT(Auk1Auk1)AT(Auk1Auk1)=(ATA)uk1(ATA)uk1u_{k} = {A_{v_{k}}^{T} \over \|A_{v_{k}}^{T}\|} = {A^{T}({A_{u_{k-1}} \over \|A_{u_{k-1}}\|}) \over \|A^{T}({A_{u_{k-1}} \over \|A_{u_{k-1}}\|})\|} = {(A^{T}A)_{u_{k-1}} \over \|(A^{T}A)_{u_{k-1}}\|}
마찬가지로 vk=(AAT)vk1(AAT)vk1v_{k} = {(AA^{T})_{v_{k-1}} \over \|(AA^{T})_{v_{k-1}}\|}
이 벡터들이 안정화가 되었다고 판단되는 상태로부터 각각 최종 중요도를 판별한다.

사례

10개의 인터넷 페이지(ㄱ~ㅊ)들 간의 인접행렬 AA가 다음과 같다고 하자.
앞에서 소개된 절차에 따라 AA의 정규화된 권위벡터가 안정화 될 때까지 반복계산한 결과는 다음과 같다.
위 수식은 소숫점 4자리까지만 연산하는데, u9,u10u_{9}, u_{10}에 도달하면 값의 차이가 없기 때문에 더는 연산을 하지 않고 멈춘다.
만일 소숫점 자리를 5자리 이상으로 보면 더 돌 수 있다.
따라서 AA 권위가중치로부터 페이지 ㄱ, ㅂ, ㅅ, ㅈ는 관련이 적고, 그 외의 페이지는 중요도가 높은 것부터 ㅁ > ㅇ > ㄴ > ㅊ > ㄷ = ㄹ 순서대로 검색엔진에서 노출되어야 함을 알 수 있다.
요게 바로 구글 페이지 랭크 연산 방식
주요 키워드) 거듭제곱법(power method), 우세 고유벡터/값(dominant eigen vector/value)

자료압축

특잇값 분해

분해

한 행렬을 여러 행렬들의 곱으로 표현하는 것
ex) QR  분해, LU 분해, LDU 분해, 고윳값 분해, 헤센버그 분해, 슈르 분해, 특잇값 분해 등

특잇값

m×nm \times n 행렬 AA에 대하여 λ1,λ2,...,λn\lambda_{1}, \lambda_{2}, ... , \lambda_{n}ATAA^{T}A의 고윳값일 때
σ1=λ1,σ2=λ2,...σn=λn\sigma_{1} = \sqrt{\lambda_{1}}, \sigma_{2} = \sqrt{\lambda_{2}}, ... \sigma_{n} = \sqrt{\lambda_{n}}
AA의 특잇값이라 한다.
고윳값을 만들려면 정사각 행렬이어야 한다. 반면 특잇값은 임의의 행렬에서도 만들어낼 수 있음.
일반적인 행렬을 정사각 행렬로 만들기 위해 m×nm \times n 행렬 AA에 대하여 ATAA^{T}A를 한 후 거기서 특이값을 추출한다.
ex) 행렬 A=(110110)A = \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right)에 대하여
ATA=(101110)(110110)=(2112)A^{T}A = \left( \begin{array}{rrr} 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right) = \left( \begin{array}{rr} 2 & 1 \\ 1 & 2 \end{array} \right) 이므로
ATAA^{T}A 의 고유방정식은 λ24λ+3=(λ1)(λ3)=0\lambda^{2} - 4 \lambda + 3 = (\lambda - 1)(\lambda - 3) = 0이다
따라서 AA의 두 특잇값은 각각 3,1\sqrt{3}, 1이다.

특잇값 분해

영행렬이 아닌 임의의 m×nm \times n 행렬 AA는 다음과 같이 나타낼 수 있다.
A=UΣVTA = U \Sigma V^{T}
이때 U,VU, V는 직교행렬이며, AA는 주대각성분이 Σ\Sigma의 특잇값이고 나머지 성분들은 00m×nm \times n 행렬이다.
여기서 Σ\Sigma는 합을 의미하는 것이 아니라 σ\sigma의 대문자 형태이다. (벡터를 의미하는 σ\sigma의 행렬 형태)
ex) 행렬 A=(110110)A = \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right)는 다음과 같이 특잇값 분해된다.
(110110)=(63013662213662213)(300100)(22222222)\left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right) = \left( \begin{array}{rrr} {\sqrt{6} \over 3} & 0 & - {1 \over \sqrt{3}} \\ {\sqrt{6} \over 6} & -{\sqrt{2} \over 2} & {1 \over \sqrt{3}} \\ {\sqrt{6} \over 6} & {\sqrt{2} \over 2} & {1 \over \sqrt{3}} \end{array} \right) \left( \begin{array}{rrr} \sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0 \end{array} \right) \left( \begin{array}{rr} {\sqrt{2} \over 2} & {\sqrt{2} \over 2} \\ {\sqrt{2} \over 2} & -{\sqrt{2} \over 2} \end{array} \right)

축소된 특잇값 분해

특잇값 분해에서 00인 성분들로만 이루어진, 대수적으로 무의미한 행 또는 열을 제거한 형태를 축소된 특잇값 분해라고 한다.
즉, A=U1Σ1V1T=(u1,u2,...,uk)(σ10...00σ2...0............00...σk)(v1Tv2T...vkT)A = U_{1} \Sigma_{1} V_{1}^{T} = (u_{1}, u_{2}, ... , u_{k}) \left( \begin{array}{rrrr} \sigma_{1} & 0 & ... & 0 \\ 0 & \sigma_{2} & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... & \sigma_{k} \end{array} \right) \left( \begin{array}{rrrr} v_{1}^{T} \\ v_{2}^{T} \\ ... \\ v_{k}^{T} \end{array} \right)
또한 축소된 특잇값 분해를 이용하여 행렬 AA를 다음과 같이 전개한 것을 AA의 축소된 특잇값 전개라 한다.
A=σ1u1v1T+σ2u2v2T+...+σkukvkT A = \sigma_{1}u_{1}v_{1}^{T} + \sigma_{2}u_{2}v_{2}^{T} + ... + \sigma_{k}u_{k}v_{k}^{T} 
ex)
(110110)=(63013662213662213)(300100)(22222222)\left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right) = \left( \begin{array}{rrr} {\sqrt{6} \over 3} & 0 & - {1 \over \sqrt{3}} \\ {\sqrt{6} \over 6} & -{\sqrt{2} \over 2} & {1 \over \sqrt{3}} \\ {\sqrt{6} \over 6} & {\sqrt{2} \over 2} & {1 \over \sqrt{3}} \end{array} \right) \left( \begin{array}{rrr} \sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0 \end{array} \right) \left( \begin{array}{rr} {\sqrt{2} \over 2} & {\sqrt{2} \over 2} \\ {\sqrt{2} \over 2} & -{\sqrt{2} \over 2} \end{array} \right)
=(63066226622)(3001)(22222222)= \left( \begin{array}{rrr} {\sqrt{6} \over 3} & 0 \\ {\sqrt{6} \over 6} & -{\sqrt{2} \over 2} \\ {\sqrt{6} \over 6} & {\sqrt{2} \over 2} \end{array} \right) \left( \begin{array}{rr} \sqrt{3} & 0 \\ 0 & 1 \end{array} \right) \left( \begin{array}{rr} {\sqrt{2} \over 2} & {\sqrt{2} \over 2} \\ {\sqrt{2} \over 2} & -{\sqrt{2} \over 2} \end{array} \right)
=3u1v1T+u2v2T= \sqrt{3}u_{1}v_{1}^{T} + u_{2}v_{2}^{T}

자료압축 원리

압축되지 않은 m×nm \times n 행렬 AA를 위한 필요 저장 공간은 mnmn이다.
AA를 축소된 특잇값 분해한 결과가 A=σ1u1v1T+σ2u2v2T+...+σkukvkTA = \sigma_{1}u_{1}v_{1}^{T} + \sigma_{2}u_{2}v_{2}^{T} + ... + \sigma_{k}u_{k}v_{k}^{T} 라면
이제 필요한 저장 공간은 k+km+kn=k(1+m+n)(σ1σ2...σk)k + km + kn = k(1 + m + n) (\sigma_{1} \geq \sigma_{2} \geq ... \geq \sigma_{k}) 이다.
kk는 특잇값 개수 = Σ\Sigma의 행개수 or 열개수
mmUU의 행 개수 = uiu_{i}의 성분개수
nnVTV^{T}의 열 개수 = viTv_{i}^{T}의 성분개수
충분히 작다고 판단되는 σr+1,...σk\sigma_{r+1}, ... \sigma_{k} 에 대응하는 항들을 추가로 제거하면, 이때 필요한 저장 공간은 r(1+m+n)r(1 + m + n) 뿐이다.