Search
Duplicate

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

우선순위 평가

인접행렬

개념

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

권위벡터와 허브벡터

n×nn \times n 인접 행렬 A=(aij)A = (a_{ij})에 대하여
(∑i=1nai1∑i=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=1na1j∑j=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=0AvkT∥AvkT∥k>0, vk={v0k=0Avk−1∥Avk−1∥k>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=AvkT∥AvkT∥=AT(Auk−1∥Auk−1∥)∥AT(Auk−1∥Auk−1∥)∥=(ATA)uk−1∥(ATA)uk−1∥u_{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)vk−1∥(AAT)vk−1∥v_{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 의 고유방정식은 λ2−4λ+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의 특잇값이고 나머지 성분들은 00인 m×nm \times n 행렬이다.
•
여기서 Σ\Sigma는 합을 의미하는 것이 아니라 σ\sigma의 대문자 형태이다. (벡터를 의미하는 σ\sigma의 행렬 형태)
ex) 행렬 A=(110110)A = \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right)는 다음과 같이 특잇값 분해된다.
(110110)=(630−1366−2213662213)(300100)(222222−22)\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)=(630−1366−2213662213)(300100)(222222−22)\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)
=(63066−226622)(3001)(222222−22)= \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 열개수
•
mm은 UU의 행 개수 = uiu_{i}의 성분개수
•
nn은 VTV^{T}의 열 개수 = viTv_{i}^{T}의 성분개수
충분히 작다고 판단되는 σr+1,...σk\sigma_{r+1}, ... \sigma_{k} 에 대응하는 항들을 추가로 제거하면, 이때 필요한 저장 공간은 r(1+m+n)r(1 + m + n) 뿐이다.
Made with