Matrix Factorization은 어떻게 추천시스템이 될 수 있을까? - 2
0
119
시작하며
※ 수식이 깨져보이신다면 새로고침을 해주세요
본 게시글은 Mathematics of Machine Learning ↗ 책을 번역하였습니다. 복습 시 한 호흡에 읽히도록 필요한 부분만 개인적인 해석을 달아 정리해 놓는 것이 이 글의 목적입니다.
이번엔 내용이 좀 많고 어려웠습니다..! Matrix decomposition의 원리를 다 이해해보려고 며칠동안 독기품고 정리했습니다..!!
4단원 목차를 다시 한 번 정리하고 오늘 다룰 부분을 알아보겠습니다.
4. Matrix Decompositions
4.1 Determinant and Trace
4.2 Eigenvalues and Eigenvectors ← 여기 끝부분
4.3 Cholesky Decomposition ← 여기
4.4 Eigendecomposition and Diagonalization ← 여기
4.5 Singular Value Decomposition
이번 글에서 다룰 내용은 4.2의 끝부분, 4.3, 4.4 단원입니다.
뒤에도 더 있지만, SVD까지 정리하는 것을 목표로 하고 있습니다!
Eigenvector 이야기가 아직 끝나지 않았다!
4.2 Eigenvalues and Eigenvectors(이어서)
Graphical Intuition in Two Dimensions
determinants, eigenvectors, eigenvalues에 대한 직관적인 이해로 들어가보자. Figure 4.4는 행렬
Figure 4.4
. 두 고유벡터의 방향이 2차원 canonical basis와 나란한 상황이다. 수직축 방향으로 2만큼 늘어나고(고유값 ), 수평축 방향으로 만큼 압축된다. 넓이는 보존된다. 은 전단 매핑(sheering mapping)인데, 즉, y축의 양의 방향에 있다면 오른쪽으로, 음의 방향에 있다면 왼쪽으로 전단한다. 이 매핑도 넓이를 보존한다. 고유값은 두 값이 동일한 이며, 고유 벡터들은 collinear이다. 즉, 그림처럼 수평 축 방향으로만 늘어나거나 줄어든다. 은 점들을 , 즉 30도만큼 반시계 방향으로 회전시키다. 그리고 허수의 고유값을 갖는다. 은 표준 기저에서의 2차원 도메인을 1차원으로 줄이는 매핑이다. 한 개의 고유값이 0이기 때문에, 이에 해당하는 파란색 고유벡터 방향의 점들은 넓이가 0이 된다. 반면 이와 수직인 빨간색 고유벡터 방향으로는 고유값인 만큼 늘어난다. 는 전단도 하고 늘리기도 하는 매핑이다. 이 행렬의 determinant는 이기 때문에, 넓이를 75%로 만든다. 빨간 고유벡터 방향의 넓이는 에 의해 늘어나고, 파란 고유벡터 방향의 넓이는 에 의해 줄어든다.
다음엔 대칭행렬에 대한 이야기가 나온다. 왜 대칭행렬을 중요하게 다루는 것인지 써가면서 이해해볼 수 있겠지..?
Theorem 4.14 행렬
가 주어졌을 때, 언제나 symmetric, positive semidefinite 행렬 을 얻을 수 있다.
위 정리로부터 symmetric 행렬을 어떻게 활용할 수 있는지 생각해볼 수 있다. Symmetric이라는건
- 이중 전치의 성질 :
- 곱의 전치 성질 :
두 가지가 있다.
또한,
Symmetric, positive (semi)definite 행렬은 3단원에 나오는데, 잠시 살펴보자.
Definition 3.4 (Symmetric, Positive Definite Matrix)
위 식을 만족하는 대칭 행렬
을 symmetric, positive definite, 또는 그냥 positive definite이라고 부른다.
예를 들어
Symmetric, positive definite 행렬은 머신러닝에서 중요한 역할을 담당한다. definite이라는 단어는 수학에서 일관되게 ‘양수’로 결정된다는 의미를 갖는다.
내적(Inner product)는 벡터 공간 전반에서 일반화된 개념이다. 흔히 생각하는 Dot product(점곱,
Definition 3.3
를 벡터 공간이라고 하고, 를 두 벡터를 실수로 매핑하는 bilinear mapping(첫 번째 변수와 두 번째 변수 모두가 선형성을 갖는 매핑, Ex. dot product)라고 하자. 그렇다면 Positive definite, symmetric bilinear mapping 을 에 대한 내적(inner product)라고 부른다. 관례적으로 라고 쓴다.
Dot product가 아닌 Inner product의 예시로
벡터 공간
이 때의
symmetric positive definite 행렬에 대해서는 여기까지만 알아보도록 하고, 다음에 기회가 되면 더 자세하게 파보도록 하자 😅
positive semidefinite이란, 영벡터가 아닌 벡터
Spectral Theorem, eigenvalue에 trace와 대한 기하학적 해석 등이 나오는데 여긴 점프!
Example 4.9 (Google’s PageRank - Webpages as Eigenvectors) 구글은 행렬
의 고유값 중 최대값에 대응되는 고유벡터를 이용하여 검색 시 페이지에 대한 랭크를 결정한다. 이러한 ‘PageRank’라고 불리는 알고리즘은 1996년 스탠포드 대학교의 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)에 의해 탄생했다. 어느 한 웹페이지의 중요도는 해당 웹페이지를 링크한 페이지의 중요도에 의해 계산될 수 있다. 개발자들은 모든 웹사이트들을 하나의 거대한 directed graph로 만든 후, 각 페이지가 어디에 링크되는지 보았다. PageRank는 웹사이트
의 가중치(중요도) 로서 를 가리키는 페이지의 수를 사용한다. 추가적으로, 를 가리키는 웹사이트의 중요도도 고려한다. 어느 유저의 탐색은 이 그래프의 전이 행렬(transition matrix) 로 나타낼 수 있을 것이다. 그럼 이 행렬은 누군가가 얼마의 확률로 어느 페이지에 도달할지 알려준다. 어느 웹사이트의 초기 중요도 벡터를 라고 해보자. , , , 가 라는 벡터로 수렴한다. 의 특성이 그렇다. 이 벡터 를 PageRank라고 부르며, 를 만족한다. 즉, 어느 웹사이트의 중요도 벡터는 행렬 의 고유값 1에 상응하는 고유벡터인 셈이다. 를 정규화하면( ), 각 요소는 확률로 해석될 수 있다. 상세한 사항은 원논문 Page et al., 1999에서 찾아볼 수 있다.
4.3 Cholesky Decomposition
머신러닝에서 우리가 자주 마주치는 특별한 유형의 행렬을 분해하는데는 다양한 방법들이 있다. 양의 실수
Theorem 4.18 (Cholesky Decomposition). Symmetric, positive definite 행렬
는 로 분해될 수 있다. 은 양의 대각 요소를 가진 lower triangular 행렬이다.
이 때의
을 의 Cholesky factor라고 부르며, 은 유일하다.
이제 symmetric positive definite 행렬에 대해 Cholesky 분해하는 예제를 보자.
Example 4.10 (Cholesky Factorization) Symmetric, positive definite 행렬
이 있다고 하자. Cholesky 분해 을 해보자.
우변을 곱한 결과는
첫 수식의 좌변과 위 수식의 우변의 대각 요소끼리 비교하면 다음과 같은 관계가 도출된다.
똑같이 대각 아래쪽만 비교하면, 다음과 같이 쓸 수 있다.
이런 방식으로 어떠한 symmetric, positive definite
행렬에 대하여도 Cholesky 분해를 할 수 있다.
Cholesky 분해는 머신러닝에서 수 계산을 할 때 매우 중요한 도구이다! 예를 들어, 공분산 행렬은 symmetric positive definite 행렬인데, 많은 곱셈 연산이 필요하다. 하지만 Cholesky 행렬을 사용하면 가우시안 분산으로부터 샘플들을 생성할 수 있다든가(?), 랜덤 변수의 선형 변환을 가능하게 해서 오토인코더같은 통계 모델에서 그래디언트를 계산할 때 널리 사용된다든가 하는 것이다. (음..어렵네)
또, Cholesky 분해를 통해 determinant를 쉽게 계산할 수 있다.
4.4 Eigendecomposition and Diagonalization
대각 행렬(diagonal matrix)은 대각 위치가 아닌 요소들이 모두 0인 행렬이다. 즉,
와 같은 형태이다. 대각 행렬의 determinant, powers, inverse는 빠르게 계산할 수 있다. Determinant는 대각 요소들의 곱이며, 거듭제곱
행렬을 어떻게 diagonal 형태로 변환할 수 있는지 살펴보자.
Definition 2.22 (Similarity). 만약
인 regular(=invertible) 행렬 가 존재한다면, 두 행렬 , 은 similar하다.
Similarity에 대해서는 추후에 자세히 다뤄보도록 하고… 일단
Definition 4.19 (Diagonalizable). 만약 행렬
가 diagonal matrix 와 similar이면, 즉, 를 만족하는 invertible 행렬 이 존재하면, 는 diagonalizable하다.
이제부터
말은 복잡하지만, 결국 다음과 같이 표현만 바꾼 것이다.
대각화(diagonalization) 정의에 따르면
Theorem 4.20 (Eigendecomposition). 정방 행렬
은 다음과 같이 분해될 수 있다.
이 때
이고 는 대각 요소가 의 고유값인 대각 행렬이고, 의 고유벡터가 의 기저를 형성해야 한다.
Theorem 4.20은 non-defective인 행렬만이 대각화 될 수 있고
Symmetric 행렬에 대하여, 우리는 고유값 분해에 대한 더욱 강력한 결과를 얻을 수 있다.
Theorem 4.21. Symmetric 행렬
은 항상 대각화 될 수 있다.
위 정리는 spectral 정리(Theorem 4.15)로부터 곧바로 정리되는 것이다. 복잡해질까봐 Spectral Theorem을 위에서 다루진 않았는데, 대강의 내용은 대칭행렬은 실수의 고유값과 고유벡터를 가지며 고유벡터들은 서로 직교한다는 것이다. Spectral 정리는 우리가
Geometric Intuition for the Eigendecomposition
행렬의 eigendecomposition을 다음과 같이 해석할 수 있다:
Example 4.11 (Eigendecomposition)
의 eigendecomposition을 계산해보자. Step1 : 고유값과 고유벡터를 계산하자. 의 특성방정식은 다음과 같다.
의 고유값은 과 이 된다. 특성 방정식의 근이 곧 고유값이니 말이다. 그리고 고유값과 고유벡터의 정의를 이용해 다음을 계산하면,
를 계산한 다음과 같이 고유벡터
, 를 계산할 수있다.
Step2 : Eigendecomposition 존재여부 판단. 고유벡터
는 의 기저를 형성할 수 있다. 그러므로 는 대각화 가능하다. Step3 :
를 대각화하기 위해 행렬 를 만든다. 의 고유벡터를 모아 를 만들자.
그러면 다음을 얻을 수 있다.
동일하게, 다음을 얻는다. (이 때는
이라는 것을 이용한다. 고유벡터 과 가 ONB를 구성하기 때문이다.)
-
대각행렬
의 제곱은 효율적으로 이루어진다. 그러므로, eigenvalue decomposition(만약 존재한다면)을 통해서 행렬 에 대한 행렬 제곱을 찾을 수 있다 를 계산하는 것은 효율적인데, 각각의 대각 요소에 제곱만 하면 되기 때문이다! -
eigendecomposition
이 존재한다고 가정하자. 그럼,
위처럼
고유값 분해는 정방행렬에 대해서만 사용된다. 일반적인 형태의 행렬을 분해하면 매우 유용할 것이다! 다음 챕터에서 일반적인 형태의 행렬 분해 방법인 singular value decomposition에 대해 알아본다!
Leave a Comment:
로그인 후 댓글을 작성할 수 있습니다.
Comments:
No comments yet. Be the first to comment!