특잇값 분해(Singular value decomposition)

행렬 $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$가 평면을 어떻게 바꾸는지 봅시다. 길이 1인 벡터⁠(vector)⁠들의 끝, 곧 단위원⁠(unit circle)⁠은 선형변환⁠(linear transformation)⁠을 거치면 타원⁠(ellipse)⁠이 됩니다. 이 타원의 가장 긴 반지름은 $\sqrt{45} \approx 6.708$, 가장 짧은 반지름은 $\sqrt5 \approx 2.236$입니다. 원 위에서 그 두 끝으로 가는 벡터는 $\vec v_1 = (1, 1)/\sqrt2$와 $\vec v_2 = (-1, 1)/\sqrt2$입니다. 이 둘은 서로 수직이고, 도착한 $A\vec v_1 = (3, 9)/\sqrt2$와 $A\vec v_2 = (-3, 1)/\sqrt2$도 서로 수직입니다(내적⁠(dot product)⁠이 $(-9 + 9)/2 = 0$). 변환 앞에서도 뒤에서도 수직인 두 방향이 있다는 것, 이것이 특잇값 분해의 핵심입니다. 두 반지름 $\sigma_1 \ge \sigma_2$를 A의 특잇값이라 부릅니다.

그러면 A가 하는 일을 세 단계로 나눌 수 있습니다. 먼저 $\vec v_1, \vec v_2$가 좌표축에 오도록 돌리고($V^{\mathsf T}$), 두 축 방향으로 각각 $\sigma_1$배, $\sigma_2$배 늘인 뒤($\Sigma$), 늘어난 두 축을 $A\vec v_1, A\vec v_2$ 방향의 단위벡터 $\vec u_1, \vec u_2$로 돌립니다($U$). 오른쪽에서 왼쪽으로 읽는 행렬의 곱⁠(matrix multiplication)⁠으로 쓰면 $A = U\Sigma V^{\mathsf T}$입니다. 단계 t = 를 0에서 3까지 끌어 보세요. t = 1에서 $\vec v_1, \vec v_2$가 좌표축 위에 놓이고, t = 2에서 원이 축에 나란한 타원이 되며, t = 3에서 흐린 점선 타원과 겹칩니다. 행렬:

지금 행렬의 특잇값은 $\sigma_1 =$ , $\sigma_2 =$ 입니다. 둘을 곱한 값()은 행렬식⁠(determinant)⁠의 절댓값()과 같습니다. 회전은 넓이⁠(area)⁠를 바꾸지 않으니 넓이 배율은 늘이는 단계에서만 생기기 때문입니다. '뒤집기가 든 행렬'처럼 행렬식이 음수이면 평면이 한 번 뒤집힙니다. 보통의 분해에서는 특잇값을 늘 0 이상으로 두므로, 그 뒤집기는 U와 V 가운데 하나가 맡습니다. 이 그림은 첫째와 셋째 단계를 회전으로만 두는 대신, 둘째 단계에서 한 축을 음수 배로 늘려(0을 지나 반대쪽으로) 뒤집기를 보여 줍니다. '계수 1인 행렬'에서는 $\sigma_2 = 0$이라 원이 선분으로 납작해집니다. 0이 아닌 특잇값의 개수가 행렬의 계수, 곧 열공간⁠(column space)⁠의 차원입니다.

모든 행렬에 있습니다. 크기가 m×n인 실수⁠(real number)⁠ 행렬 A는 무엇이든 $A = U\Sigma V^{\mathsf T}$로 쓸 수 있습니다. U(m×m)와 V(n×n)는 직교 행렬⁠(orthogonal matrix)⁠, 곧 열들이 서로 수직이고 길이가 1이어서 길이와 각을 바꾸지 않는 행렬(회전이나 뒤집기)입니다. Σ(m×n)는 대각선에만 $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$이 놓이고 나머지 칸은 0인 행렬입니다. 정사각형이 아니어도, 대각화⁠(diagonalization)⁠할 수 없는 행렬이어도 됩니다. 까닭은 짧습니다. $A^{\mathsf T}A$는 대칭 행렬⁠(symmetric matrix)⁠이라서 서로 수직인 고유벡터⁠(eigenvector)⁠ $\vec v_1, \ldots, \vec v_n$으로 좌표축을 모두 채울 수 있습니다(스펙트럼 정리⁠, spectral theorem⁠). 고유값⁠(eigenvalue)⁠을 $\lambda_j$라 하면 $(A\vec v_i)\cdot(A\vec v_j) = \vec v_i^{\mathsf T}A^{\mathsf T}A\,\vec v_j = \lambda_j\,(\vec v_i\cdot\vec v_j)$입니다. 이 값은 $i \ne j$이면 0이고, $i = j$이면 $|A\vec v_i|^2 = \lambda_i$라서 음수가 아닙니다. 곧 서로 수직인 $\vec v_i$들은 A를 거친 뒤에도 서로 수직이고, 길이는 $\sigma_i = \sqrt{\lambda_i}$가 됩니다(고유값을 큰 것부터 늘어놓습니다). $\sigma_i > 0$인 것마다 $\vec u_i = A\vec v_i/\sigma_i$로 두고, 모자라는 u는 서로 수직인 단위벡터로 채웁니다. $\sigma_i = 0$이면 $A\vec v_i = \vec 0$이므로, 어느 경우든 $A\vec v_i = \sigma_i\vec u_i$입니다. 이것을 열마다 모으면 $AV = U\Sigma$이고, V가 직교 행렬이라 $VV^{\mathsf T} = I$이니 양변 오른쪽에 $V^{\mathsf T}$를 곱하면 $A = U\Sigma V^{\mathsf T}$입니다.

특잇값은 고유값이 아닙니다. 고유벡터는 변환 뒤에도 제 직선 위에 머무는 방향이라, 들어갈 때와 나올 때 같은 축을 씁니다. 특잇값 분해는 들어가는 쪽(v)과 나오는 쪽(u)에 서로 다른 수직 축을 허락하고, 그래서 언제나 있습니다. '밀기' 행렬을 골라 보세요. 고유값은 1 하나뿐이고 고유벡터의 방향도 하나뿐이라 대각화할 수 없지만, 특잇값은 $(\sqrt5 + 1)/2 \approx 1.618$과 $(\sqrt5 - 1)/2 \approx 0.618$, 곧 황금비⁠(golden ratio)⁠와 그 역수입니다. 특잇값과 고유값이 같아지는 것은 대칭이면서 고유값이 모두 0 이상인 행렬(공분산 행렬⁠(covariance matrix)⁠이 그런 예)일 때이고, 대칭 행렬 일반에서는 특잇값이 고유값의 절댓값입니다.

가장 좋은 근사. 분해를 풀어 쓰면 A는 계수 1인 행렬들의 합입니다.

$$A = \sigma_1 \vec u_1 \vec v_1^{\mathsf T} + \sigma_2 \vec u_2 \vec v_2^{\mathsf T} + \cdots + \sigma_r \vec u_r \vec v_r^{\mathsf T}$$

각 항 $\vec u\,\vec v^{\mathsf T}$는 세로 벡터 하나와 가로 벡터 하나를 곱한 표, 곧 모든 행이 한 행의 배수⁠(multiple)⁠인 표입니다. 앞의 k항만 남긴 것을 $A_k$라 합시다. 출발점은 행렬의 칸별 제곱합이 특잇값의 제곱합과 같다는 사실입니다($\sum_{i,j} a_{ij}^2 = \sigma_1^2 + \cdots + \sigma_r^2$). U와 $V^{\mathsf T}$는 길이를 바꾸지 않으니 제곱합을 Σ에서 재도 같기 때문입니다. 1936년 칼 에카르트와 게일 영은, 계수가 k 이하인 행렬 가운데 칸별 차의 제곱합으로 재어 $A_k$보다 A에 더 가까운 것은 없고, 그때의 제곱합이 버린 특잇값의 제곱합 $\sigma_{k+1}^2 + \cdots + \sigma_r^2$임을 보였습니다(에카르트–영 정리⁠, Eckart–Young theorem⁠). 아래는 32×32 화소의 흑백 그림을, 칸마다 밝기(0은 검정, 1은 흰색)를 적은 행렬로 본 것입니다. 그림: , 남기는 항 k =

k항은 수 $k(32 + 32 + 1)$개, 지금은 개로 적을 수 있습니다(원래는 1024개). 버린 몫은 전체 제곱합의 이고, 칸별 오차를 제곱해 평균⁠(mean)⁠한 뒤 제곱근을 씌운 값(RMS)은 입니다. '타탄 무늬'는 행마다 정해진 수와 열마다 정해진 수를 더한 것이라 계수가 2이고, k = 2면 완전히 되살아납니다. 셋째부터의 특잇값은 반올림 오차⁠(round-off error)⁠만큼 작습니다. '웃는 얼굴'은 k가 6에서 8쯤이면 알아볼 만하고, k = 16이면 RMS가 0.001보다 작아 차이가 보이지 않습니다. '잡음'에서는 첫 항이 평균 밝기에 가까운 고른 회색 한 장을 잡고 나면 나머지 특잇값이 고르게 퍼져 있어서, k = 16이어도 RMS가 0.1 가까이 남습니다. 줄일 수 있는 것은 구조이지 무작위가 아닙니다(콜모고로프 복잡도⁠(Kolmogorov complexity)⁠).

실제 사진 압축은 이렇게 하지 않습니다. 특잇벡터⁠(singular vector)⁠는 그림마다 달라서 u와 v까지 함께 적어야 하니, 웃는 얼굴을 k = 8로 적어도 수 520개로 절반쯤 줄 뿐입니다. JPEG은 그림을 8×8 화소 조각으로 나누고, 모든 그림에 같은 코사인⁠(cosine)⁠ 무늬를 쓰는 이산 코사인 변환⁠(discrete cosine transform)⁠을 씁니다. 무늬가 정해져 있으니 계수만 적으면 됩니다. 특잇값 분해가 빛나는 곳은 데이터의 주된 방향을 찾을 때입니다. n명 × d개 변수의 데이터 표에서 각 열의 평균을 뺀 행렬을 X라 하면 $X^{\mathsf T}X = V\Sigma^{\mathsf T}\Sigma V^{\mathsf T}$이므로, 주성분 분석⁠(principal component analysis)⁠의 축은 V의 열이고 각 축의 분산⁠(variance)⁠은 $\sigma_i^2/(n-1)$입니다. 실제 계산에서는 공분산 행렬을 만들지 않고 X를 바로 분해합니다. $X^{\mathsf T}X$를 만들면 특잇값이 제곱되어, 작은 특잇값이 반올림 오차에 묻히기 쉽기 때문입니다. 오늘날 널리 쓰는 알고리즘⁠(algorithm)⁠들은 1965년 진 골럽과 윌리엄 카한이 내놓은 방법을 바탕으로 합니다.

얼마나 민감한가. 정사각 행렬에서 $\sigma_1/\sigma_n$을 조건수라 합니다. 타원이 길쭉할수록 크고, 연립방정식 $A\vec x = \vec b$를 풀 때 b의 상대 오차⁠(relative error)⁠가 x에서 최대 이만큼 부풀 수 있습니다. 지금 행렬의 조건수⁠(condition number)⁠는 입니다. $\sigma_n = 0$이면 역행렬⁠(inverse matrix)⁠이 없지만, 0이 아닌 특잇값만 역수⁠(inverse)⁠로 바꾼 유사역행렬⁠(pseudoinverse)⁠ $A^{+} = V\Sigma^{+}U^{\mathsf T}$는 어느 행렬에나 있습니다. $A^{+}\vec b$는 오차 제곱합 $|A\vec x - \vec b|^2$을 가장 작게 하는 x 가운데 길이가 가장 짧은 것입니다(최소제곱법⁠(method of least squares)⁠, 정사영⁠(orthogonal projection)⁠). 경사 하강법⁠(gradient descent)⁠이 길쭉한 골짜기에서 느린 까닭도 같은 종류의 수, 곧 이계도함수를 모은 헤세 행렬⁠(Hessian matrix)⁠의 조건수입니다. 분해 자체는 1873년 이탈리아의 에우제니오 벨트라미와 1874년 프랑스의 카미유 조르당이 정사각 행렬에 대해 따로 찾았습니다.

이어지는 곳. 대형 언어 모델⁠(language model)⁠을 새 일에 맞춰 고칠 때 널리 쓰는 LoRA(2021년 마이크로소프트의 에드워드 후 등)는 d×k 가중치⁠(weight)⁠ 행렬 W를 그대로 두고, 고칠 양 ΔW만 계수 r 이하의 곱 BA(B는 d×r, A는 r×k)로 제한해 배웁니다. d = k = 4096, r = 8이면 배울 수가 1677만 7216개에서 6만 5536개, 곧 0.39%로 줍니다. 고칠 양이 낮은 계수로 충분하다는 것은 GPT-3 같은 모형에서 잰 실험적 관찰이지 정리가 아니고, LoRA가 특잇값 분해를 계산하는 것도 아닙니다. 다만 계수 r인 행렬로 ΔW를 얼마나 가깝게 흉내 낼 수 있는지의 한계는 에카르트–영 정리가 정해 줍니다.

낱말을 벡터로 나타내는 단어 임베딩⁠(word embedding)⁠도 이 분해와 가깝습니다. 그 조상 격인 잠재 의미 분석(LSA, 1990)은 낱말×문서 빈도 표에서 앞의 k항만 남겨 낱말 벡터를 얻었습니다. 2014년 오메르 레비와 요아브 골드버그는 word2vec의 한 학습 방식이, 벡터의 차원이 충분히 크다는 가정 아래, 낱말 쌍의 점별 상호 정보에서 상수를 뺀 표를 암묵적으로 분해하는 것으로 볼 수 있음을 보였습니다. 신경망⁠(neural network)⁠에서도 같은 답이 나옵니다. 평균을 뺀 데이터로 숨은 단위가 k개인 선형 오토인코더⁠(autoencoder)⁠를 학습시켜 제곱 오차를 가장 작게 만들면, 배운 부분공간⁠(subspace)⁠은 처음 k개 주성분이 펼치는 부분공간과 같습니다. 깊은 신경망의 역전파⁠(backpropagation)⁠에서는 기울기⁠(slope)⁠가 층마다 야코비 행렬⁠(Jacobian matrix)⁠을 곱하며 흐릅니다. 그 특잇값이 층마다 모두 1보다 작으면 기울기가 거듭 줄어 사라지고, 모두 1보다 크면 거듭 커져 폭발합니다.

더 추상적인 눈으로 보면, $A = \sum_i \sigma_i\, \vec u_i \vec v_i^{\mathsf T}$는 행렬을 계수 1인 조각들의 합으로 쓰는 것입니다. 행렬을 두 벡터 공간⁠(vector space)⁠을 곱해 만든 공간(텐서곱⁠, tensor product⁠)의 원소⁠(element)⁠로 보면 이 조각은 곱꼴 원소 $\vec u \otimes \vec v$이고, 0이 아닌 특잇값의 개수는 곱꼴 원소를 가장 적게 몇 개 더해야 그 행렬이 되는지를 알려 줍니다. 텐서곱을 합성과 나란히 다루는 틀은 모노이드⁠(monoid)⁠ 범주⁠(category)⁠에 있습니다.