Cara's Moving Cara's Moving

SVD를 이해해보자! 라는 마음으로 들었던 선형대수였는데 정말 많은 것들을 얻을 수 있었던 주재걸 교수님의 오픈 강의 "인공지능을 위한 선형대수"였다. 오늘은 그렇다면, 기존에 쌓았던 지식을 바탕으로 Eigendecomposition과 SVD가 Machine Learning에서 어떻게 쓰이는지 살펴보고자 한다. 먼저, Machine learning에서는 A Matrix에 대하여, A가 m*n(Feature by example)이라고 할 때, A'A (A: A의 transpose를 표현)의 matrix 혹은 AA' matrix에 대해서 가장 관심이 많다. 왼쪽 matrix의 행벡터와 오른쪽 matrix의 열벡터의 내적값으로 구성된 AA' matrix는 Feature들의 correlation 정보를 포함하고..

(AA')와 (A'A)가 대칭행렬이라고 언급하며 특이값분해(2)의 포스팅을 마무리하였다. 이 포스팅에서는 대칭행렬의 특징을 다루고자 한다. A'A(A'는 A의 transpose한 행렬이라고 생각하자)가 SVD에서 나온 이유는, SVD를 eigendecomposition으로 풀기 위함이었다. 일반적으로 (n*n)크기의 B라는 정사각행렬은 linearly independent한 eigenvector가 존재할 때만 대각화가 가능하다. 하지만, 신기하게도 Symmetric Matrix에 대해서, 그러니까 대각선을 중심으로 접었을 때 데칼코마니처럼 값이 같은 경우의 Matrx의 경우에는 항상 대각화가 가능하다(Always diagonalizable). 대각화가 가능하므로, Eigendecomposition이 무조..

SVD를 바로 구하는 알고리즘은 없으나, 보통 Eigendecomposition을 구하는 방식으로 우회하여 구할 수 있다고 한다. Eigendecomposition은 정사각행렬에 대해서만 가능하므로, AA'(A의 transpose를 a'로 표현) 혹은 A'A으로 생각해보면 첫번째 등식에서 다음 등식으로 (SVD공식에 의해서) 두번째 등식에서 다음 등식으로 (Othonomal한 성질에 의해서, V의 transpose한 행렬은 V의 역행렬과 같다) 또한, Σ행렬의 전치행렬은 자기 자신이므로, UΣΣ'U' = UΣ^(2)U'가 된다. i) 식과 ii)식의 마지막 부분 UΣ^(2)U'을 보면, 상당히 유사한 모습을 띄고 있다. 다시 한번 말하지만 U는 Othonomal행렬이므로, U' 와 U의 역행렬은 같다. ..

Eigendecomposition과의 차이점은, 분해(decomposition) 대상인 A matrix의 형태가 직사각행렬(m*n, m>n)이라는 점이다. A = UΣV' 의 식을 만족하는 U와 V'를 뽑아내는 과정이라고 볼 수 있으며, 여기에서 U와 V'(첨자 transpose로 표현)는 각 행렬의 열벡터가 orthnormal하다. 즉, 열 벡터의 길이가 1이며, 각기 다른 열벡터들은 서로 직교하는 성질을 만족한다. Σ의 경우, 대각 성분을 제외하고는 다른 성분들은 다 0의 값을 가진다. SVD의 기본형태에서는 U가 m*m의 크기를, V가 n*n의 크기를, Σ가 m*n의 크기를 가지나, Σ가 대각행렬이기 때문에 아래의 줄어든 형태(Reduced form of SVD)로 보아도 무방하다. 특히, 위의 식..

정사영(projection)이라는 개념은, linearly independent한 벡터들을 orthgonal vector들로 변환할 때 등장하게 되는 개념이다. 특히, linearly independet한 벡터들을(어떤 컬럼 A)를 orthogonal한 벡터들로 만들어주는 과정을 그람-슈미츠 정교화(Gram-Schmidt)라고 부른다. 먼저, 정사영한 길이를 구하는 공식은 다음의 과정을 통해 도출할 수 있다. 마지막 부분에 벡터로 나타낸 부분을 원래의 y벡터에 빼주면, u라는 벡터에 있어서 orthogonal한 새로운 벡터 y'가 만들어진다. 이러한 과정을 반복해서 하는 것이 그람-슈미츠 정교화 과정이며, 이 과정을 통해서 A matrix의 orthonomal한 matrix를 구할 수 있게 된다.

Eigendecomposition n*n크기의 정사각행렬 A matrix를 Diagonal matrix를 포함한 메트릭스의 곱으로 분해하는 방식이다.(iii)의 식) 이를 위해서는 A에 대한 대각화(Diagonalize)가 가능한가? 에 대한 질문부터 먼저 해야 한다. i)의 식을 통해서 D를 구할 수 있는가? 즉, i)식에서, V는 역행렬이 존재해야 하며, D는 대각 성분을 제외하고 모두 다 0인 요소여야 한다. 여기에서 Eigenvector와 Eigenvalue의 개념이 나오는 이유는 ii)식과 관련이 있다. 우변을 보면, V를 각각의 람다배 한 값이다. 즉, A에 의해 선형변환한 V의 열벡터들은, 그 벡터의 방향은 보존된 채 크기만 변화하게 된다. 대각화가 eigenvector와 eigenvalue..

특성방정식Characteristic Equation은 n * n 크기의 정사각행렬 A의 특성을 밝혀가는 과정이다. 이 방정식을 통해서, Eigenvector와 Eigenvalue를 구할 수 있다. 특히, 위의 그림에서 선형 변환 A에 의해서, 보통은 x의 방향과 크기가 모두 변하나 이 경우 벡터 x의 크기만 변하는 상태이다. 이를 만족하는 x와 스칼라 람다값은 각각 eigen vector, eigen value를 나타내며, 행렬의 연산량을 줄여주기 때문에 용이한 개념이기도 하다. 이때, 좌변으로 식을 정리하여, 우변은 원소가 0인 메트릭스로 만들면, 아래의 식이 나온다. 이 때, 벡터 x가 모두 0인 해를 제외하는 해(non-trivial solution)를 가지기 위해서, 위의 식을 만족하기 위해서는 ..