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

우선순위 평가

인접행렬

개념

요소간의 연결 관계를 나타내는 정사각 행렬

  • 참조한 (화살표가 나가는) 쪽은 행에, 참조된 (화살표를 받는) 쪽은 열에 쓴다.
    • 1은 2와 3으로 화살표를 쏘고 있으므로, 1행은 2열과 3열에 값이 있음.

권위벡터와 허브벡터

n \times n 인접행렬 A = (a_{ij}) 에 대하여

\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) \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) 을 각각 A 의 권위벡터와 허브벡터라 하며, 각 벡터의 성분을 권위 가중치와 허브가중치라 한다.

  • 가중치로부터 중요도를 판단한다는게 아이디어
    • 권위 벡터(u_{0} )는 연관받은 (열) 데이터에 대한 벡터가 된다. 그 각각의 값은 권위 가중치가 된다.
    • 허브 벡터(v_{0} )는 연관한 (행) 데이터에 대한 벡터가 된다. 그 각각의 값은 허브 가중치가 된다.
  • 권위 벡터와 허브 벡터는 상호작용을 기반으로 계속 값이 업데이트 된다.
    • 업데이트 되는 와중에 어떤 기준선에 도달하여 값이 안정되면 최종적으로 그 벡터를 중요도 평가에 사용한다.

순위평가 원리

인접행렬 A 와 초기권위벡터 u_{0} 와 초기허브벡터 v_{0} 에 대하여

u_{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}

  • 현재 권위 벡터는 이전 허브 벡터의 값을 원본 행렬(의 전치 행렬)에 곱하여 구하고, 마찬가지로 현재 허브 벡터는 이전 권위 벡터의 값을 원본 행렬에 곱하여 구한다.
    • 이 곱을 반복하여 값을 업데이트 한다.
  • 다만 이것을 점화식을 이용해서 구성하면 자기 자신만 보면 되는 (권위 벡터는 권위 벡터만으로, 허브 벡터는 허브 벡터만으로) 해석적인 결과가 구성되고, 이를 컴퓨터에 넣어서 계속 돌리면 값이 나온다.

와 같이 새로운 정규화된 권위벡터 u_{k} 와 허브벡터 v_{k} 를 정의한다. (k 는 정수)

이때 u_{k}, v_{k} 를 연립하면 다음과 같이 정규화된 u_{k} v_{k} 의 점화식을 얻을 수 있다.

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}}\|}

마찬가지로 v_{k} = {(AA^{T})_{v_{k-1}} \over \|(AA^{T})_{v_{k-1}}\|}

이 벡터들이 안정화가 되었다고 판단되는 상태로부터 각각 최종 중요도를 판별한다.

사례

10개의 인터넷 페이지(ㄱ~ㅊ)들 간의 인접행렬 $latex A &s=2가 다음과 같다고 하자.

앞에서 소개된 절차에 따라 $latex A &s=2의 정규화된 권위벡터가 안정화 될 때까지 반복계산한 결과는 다음과 같다.

  • 위 수식은 소숫점 4자리까지만 연산하는데, u_{9}, u_{10} 에 도달하면 값의 차이가 없기 때문에 더는 연산을 하지 않고 멈춘다.
    • 만일 소숫점 자리를 5자리 이상으로 보면 더 돌 수 있다.

따라서 $latex A &s=2 권위가중치로부터 페이지 ㄱ, ㅂ, ㅅ, ㅈ는 관련이 적고, 그 외의 페이지는 중요도가 높은 것부터 ㅁ > ㅇ > ㄴ > ㅊ > ㄷ = ㄹ 순서대로 검색엔진에서 노출되어야 함을 알 수 있다.

  • 요게 바로 구글 페이지 랭크 연산 방식
  • 주요 키워드) 거듭제곱법(power method), 우세 고유벡터/값(dominant eigen vector/value)

자료압축

특잇값 분해

분해

한 행렬을 여러 행렬들의 곱으로 표현하는 것

ex) QR  분해, LU 분해, LDU 분해, 고윳값 분해, 헤센버그 분해, 슈르 분해, 특잇값 분해 등

특잇값

m \times n 행렬 A 에 대하여 \lambda_{1}, \lambda_{2}, ... , \lambda_{n} A^{T}A 의 고윳값일 때

\sigma_{1} = \sqrt{\lambda_{1}}, \sigma_{2} = \sqrt{\lambda_{2}}, ... \sigma_{n} = \sqrt{\lambda_{n}}

A 의 특잇값이라 한다.

  • 고윳값을 만들려면 정사각 행렬이어야 한다. 반면 특잇값은 임의의 행렬에서도 만들어낼 수 있음.
    • 일반적인 행렬을 정사각 행렬로 만들기 위해  m \times n 행렬 A 에 대하여 A^{T}A 를 한 후 거기서 특이값을 추출한다.

ex) 행렬 A = \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right) 에 대하여

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) 이므로

A^{T}A 의 고유방정식은 \lambda^{2} - 4 \lambda + 3 = (\lambda - 1)(\lambda - 3) = 0 이다

따라서 A 의 두 특잇값은 각각 \sqrt{3}, 1 이다.

특잇값 분해

영행렬이 아닌 임의의 m \times n 행렬 A 는 다음과 같이 나타낼 수 있다.

A = U \Sigma V^{T}

이때 U, V 는 직교행렬이며, A 는 주대각성분이 \Sigma 의 특잇값이고 나머지 성분들은 0 m \times n 행렬이다.

  • 여기서 \Sigma 는 합을 의미하는 것이 아니라 \sigma 의 대문자 형태이다. (벡터를 의미하는 \sigma 의 행렬 형태)

ex) 행렬 A = \left( \begin{array}{rrr} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{array} \right) 는 다음과 같이 특잇값 분해된다.

\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)

축소된 특잇값 분해

특잇값 분해에서 0 인 성분들로만 이루어진, 대수적으로 무의미한 행 또는 열을 제거한 형태를 축소된 특잇값 분해라고 한다.

즉, 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)

또한 축소된 특잇값 분해를 이용하여 행렬 A 를 다음과 같이 전개한 것을 A 의 축소된 특잇값 전개라 한다.

A = \sigma_{1}u_{1}v_{1}^{T} + \sigma_{2}u_{2}v_{2}^{T} + ... + \sigma_{k}u_{k}v_{k}^{T} 

ex)

\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)

= \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)

= \sqrt{3}u_{1}v_{1}^{T} + u_{2}v_{2}^{T}

자료압축 원리

압축되지 않은 m \times n 행렬 A 를 위한 필요 저장 공간은 mn 이다.

A 를 축소된 특잇값 분해한 결과가 A = \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) (\sigma_{1} \geq \sigma_{2} \geq ... \geq \sigma_{k}) 이다.

  • k 는 특잇값 개수 = \Sigma 의 행개수 or 열개수
  • m U 의 행 개수 = u_{i} 의 성분개수
  • n V^{T} 의 열 개수 = v_{i}^{T} 의 성분개수

충분히 작다고 판단되는 \sigma_{r+1}, ... \sigma_{k} 에 대응하는 항들을 추가로 제거하면, 이때 필요한 저장 공간은 r(1 + m + n) 뿐이다.

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.