이 강의의 목표는 아래 식을 스스로 설명할 수 있게 되는 것입니다.
A=UΣVT
말로 풀면 다음과 같습니다.
어떤 행렬 A도 입력 방향, 방향별 크기, 출력 방향으로 나누어 읽을 수 있다.
이 한 줄을 이해하면 다음 질문에도 답할 수 있습니다.
- 행렬을 왜 세 행렬로 쪼개는가?
- U, Σ, VT는 각각 무엇을 하는가?
- 특이값은 왜 방향의 중요도인가?
- 랭크와 저랭크 근사는 SVD와 어떻게 연결되는가?
- 이미지 압축, 노이즈 제거, 추천 시스템에서 왜 SVD가 쓰이는가?
| 기호 |
읽는 법 |
뜻 |
| A |
행렬 A |
입력 벡터를 출력 벡터로 보내는 변환 |
| U |
행렬 U |
출력 공간의 중요한 방향들을 열벡터로 모은 직교행렬 |
| Σ |
시그마 |
방향별 크기인 특이값을 대각에 놓은 행렬 |
| V |
행렬 V |
입력 공간의 중요한 방향들을 열벡터로 모은 직교행렬 |
| VT |
V 전치 |
입력 벡터를 V의 방향 기준으로 분해하는 행렬 |
| σi |
시그마 i |
i번째 특이값 |
| k |
케이 |
저랭크 근사에서 남길 방향의 개수 |
| Ak |
A 서브 k |
A의 랭크 k 근사 |
| 랭크 |
rank |
행렬 안에 살아 있는 독립 방향의 수 |
앞 강의에서 배운 행렬곱, 전치, 내적, 직교, 노름을 그대로 사용합니다.
9강에서 대각행렬은 각 좌표축을 독립적으로 늘리는 변환이라고 봤습니다.
[3002]
이 행렬은 x축을 3배, y축을 2배 늘립니다. 대각행렬은 변환의 의미가 바로 읽힙니다.
하지만 일반 행렬은 좌표축을 섞습니다.
A=[3223]
이 행렬은 표준 좌표축 기준으로 보면 한눈에 읽기 어렵습니다. SVD는 이 문제를 다음 방식으로 해결합니다.
표준 좌표축이 아니라 행렬에 잘 맞는 특별한 방향으로 다시 보면, 일반 행렬도 방향별 늘리기로 읽을 수 있다.
그래서 SVD는 행렬을 다음 세 단계로 나눕니다.
A=UΣVT
- VT: 입력 벡터를 특별한 입력 방향 기준으로 분해한다.
- Σ: 각 방향 성분을 특이값만큼 늘리거나 줄인다.
- U: 늘어난 성분을 출력 공간의 방향으로 다시 조립한다.
SVD의 그림은 단위원에서 시작하면 쉽습니다. 길이가 1인 모든 벡터의 집합을 행렬 A에 넣어 봅시다.
평면에서는 원이 타원으로 변합니다. 어떤 방향은 많이 늘어나고, 어떤 방향은 적게 늘어나며, 어떤 방향은 0으로 눌릴 수도 있습니다.
- 가장 많이 늘어나는 입력 방향이 v1입니다.
- 그때 늘어난 길이가 σ1입니다.
- 도착한 출력 방향이 u1입니다.
그다음으로 중요한 방향이 v2, 크기가 σ2, 출력 방향이 u2가 됩니다. 같은 방식으로 vi, σi, ui가 정해집니다.
정사각 행렬이 아니어도 같은 관점이 유지됩니다. m×n 행렬은 n차원 입력을 m차원 출력으로 보내고, SVD는 그 변환에 가장 잘 맞는 입력 방향과 출력 방향, 그리고 방향별 크기를 찾아 줍니다.
SVD에서 U와 V는 직교행렬입니다. 직교행렬 Q는 다음을 만족합니다.
QTQ=I
즉 열벡터들의 길이가 1이고 서로 직교합니다. 중요한 성질은 길이를 보존한다는 것입니다.
∥Qx∥2=(Qx)T(Qx)=xTQTQx=xTx=∥x∥2
따라서 직교행렬은 벡터의 길이를 바꾸지 않고 방향만 바꿉니다. 회전이나 반사로 이해하면 됩니다.
반면 Σ는 대각행렬입니다.
Σ=⎣⎢⎡σ1000σ2000σ3⎦⎥⎤
대각행렬은 방향끼리 섞지 않고 각 성분만 따로 늘립니다. 그래서 A=UΣVT는 다음처럼 읽을 수 있습니다.
A=출력 방향 조립×방향별 늘리기×입력 방향 분해
길이를 실제로 바꾸는 단계는 가운데 Σ뿐입니다. 그래서 Σ의 대각 성분인 특이값이 행렬의 핵심 크기 정보입니다.
입력 벡터 x에 대해
Ax=UΣVTx
입니다. 오른쪽부터 차례대로 읽습니다.
V의 열벡터를 v1,v2,…,vn이라고 하면 VTx의 i번째 성분은
(VTx)i=viTx
입니다. 이것은 x가 vi 방향으로 얼마나 가는지를 내적으로 재는 것입니다.
Σ를 곱하면 각 성분이 특이값만큼 커집니다.
ΣVTx=(σ1(v1Tx),σ2(v2Tx),…,σn(vnTx))T
큰 특이값 방향은 많이 반영되고, 작은 특이값 방향은 적게 반영됩니다.
U의 열벡터를 u1,u2,…라고 하면 최종 출력은
Ax=i∑σi(viTx)ui
입니다. 이 식이 SVD의 작동 방식을 가장 압축적으로 보여 줍니다.
여기서 ∑i는 "모든 i에 대해 더하라"는 뜻의 합 기호입니다. 모양 때문에 큰 시그마라고도 부르지만, 이 강의에서는 특이값 σi와 헷갈리지 않도록 ∑i는 합 기호, σi는 특이값이라고 부르겠습니다.
입력 x를 입력 방향 vi들에 비추고, 각 양을 σi만큼 키운 뒤, 출력 방향 ui들로 다시 더한다.
먼저 쉬운 행렬을 봅시다.
A=[3004]
이 행렬은 x축을 3배, y축을 4배 늘립니다. 특이값은 4와 3입니다. 보통 큰 순서로 놓으므로
Σ=[4003]
로 씁니다. 이때 입력 방향과 출력 방향의 순서도 특이값 순서에 맞춰 바꾸면 됩니다.
U=[0110],Σ=[4003],VT=[0110]
확인하면
UΣVT=[3004]=A
입니다. 이 예제의 핵심은 특이값을 큰 순서로 놓으면 U와 V의 방향 순서도 함께 맞춰야 한다는 점입니다.
이번에는 비대각 행렬을 봅니다.
A=[3223]
이 행렬의 SVD 중 하나는 다음과 같습니다.
U=21[11−11],Σ=[5001],VT=21[1−111]
곱하면
UΣVT=[3223]
가 됩니다. 표준 좌표축으로는 섞여 보이던 행렬도, 적절한 입력 방향과 출력 방향을 잡으면 5배와 1배 늘리기로 분해됩니다.
특이값은 Σ의 대각 성분입니다.
σ1≥σ2≥⋯≥0
보통 큰 것부터 나열합니다. vi가 길이 1인 입력 방향이면
∥Avi∥=σi
입니다. 즉 σi는 그 입력 방향에서 길이가 몇 배 되는지를 나타냅니다.
- σi가 크면 그 방향은 행렬 변환에서 중요합니다.
- σi가 작으면 그 방향은 영향이 작습니다.
- σi=0이면 그 방향은 영벡터로 눌립니다.
특이값은 음수가 될 수 없습니다. 길이의 변화량이기 때문입니다. 더 정확히는 ATA의 고윳값을 λi라고 할 때
σi=λi
이고, ATA는 항상 양의 준정부호입니다.
xT(ATA)x=(Ax)T(Ax)=∥Ax∥2≥0
따라서 ATA의 고윳값은 0 이상이고, 그 제곱근인 특이값도 0 이상입니다.
고윳값분해는 기본적으로 정사각 행렬을 다룹니다. 반면 SVD는 직사각 행렬에도 적용됩니다.
A가 m×n 행렬이면
- ATA는 n×n 정사각 행렬입니다.
- AAT는 m×m 정사각 행렬입니다.
이 두 행렬의 0이 아닌 고윳값은 같습니다. 그 공통 고윳값의 제곱근이 A의 특이값입니다.
σi=λi
예를 들어
A=[3223]
이면
ATA=[13121213]
이고 이 행렬의 고윳값은 25와 1입니다. 따라서 특이값은
25=5,1=1
입니다.
행렬의 랭크는 서로 독립인 방향의 수입니다.
예를 들어
A=[122436]
의 열벡터들은 모두 같은 방향입니다.
[24]=2[12],[36]=3[12]
그래서 랭크는 1입니다.
SVD에서는 랭크를 특이값으로 읽을 수 있습니다.
랭크 = 0이 아닌 특이값의 개수
예를 들어 특이값이 10,3,0이면 랭크는 2입니다. 마지막 방향은 0으로 눌렸기 때문에 살아 있는 방향으로 세지 않습니다.
5절에서 본 식
Ax=i∑σi(viTx)ui
는 "행렬 A가 벡터 x에 작용한 결과"를 쓴 식입니다. 이제 이 식을 행렬 자체에 대한 식으로 바꿔 봅시다.
먼저 한 항만 봅니다.
σi(viTx)ui
여기서 viTx는 내적이므로 숫자 하나입니다. 따라서 숫자끼리는 순서를 바꿔도 되어서 다음처럼 쓸 수 있습니다.
σi(viTx)ui=σiui(viTx)
이제 결합법칙으로 괄호를 바꿔 봅니다.
ui(viTx)=(uiviT)x
왜냐하면 ui는 세로 벡터, viT는 가로 벡터이기 때문입니다. 크기를 쓰면
ui:m×1,viT:1×n,x:n×1
이고,
ui(viTx):(m×1)(1×1)=m×1
(uiviT)x:(m×n)(n×1)=m×1
입니다. 두 식은 같은 벡터를 만듭니다. 따라서 한 항은 다음처럼 바꿀 수 있습니다.
σi(viTx)ui=(σiuiviT)x
이제 모든 i에 대해 더하면
Ax=i∑(σiuiviT)x
입니다. 오른쪽의 각 항은 모두 같은 x를 곱하고 있으므로, 다시 묶을 수 있습니다.
Ax=(i∑σiuiviT)x
즉 어떤 입력 x를 넣어도 A를 곱한 결과와 ∑iσiuiviT를 곱한 결과가 같습니다. 모든 x에 대해 같은 변환을 하므로 두 행렬 자체가 같습니다.
A=i=1∑rσiuiviT
여기서 r은 랭크입니다. uiviT는 세로 벡터와 가로 벡터의 곱입니다.
uiviT=(u1i,u2i,…,umi)T[v1iv2i⋯]
이런 곱을 외적이라고 부릅니다. 외적으로 만든 행렬은 랭크가 1입니다. 따라서 SVD는 다음처럼 읽을 수 있습니다.
행렬 A를 랭크 1짜리 조각들의 합으로 나누고, 각 조각의 크기를 특이값으로 표시한다.
특이값은 큰 것부터 정렬합니다.
σ1≥σ2≥⋯≥σr>0
실제 데이터에서는 앞쪽 몇 개 특이값이 크고 뒤쪽 특이값은 매우 작은 경우가 많습니다. 그러면 작은 특이값에 해당하는 조각을 버려도 전체 행렬이 크게 달라지지 않습니다.
앞의 k개 조각만 남기면 랭크 k 근사 Ak가 됩니다.
A≈Ak=i=1∑kσiuiviT=UkΣkVkT
여기서
- Uk는 U에서 앞의 k개 열만 남긴 행렬입니다.
- Σk는 앞의 k개 특이값만 남긴 대각행렬입니다.
- VkT는 VT에서 앞의 k개 행만 남긴 행렬입니다.
예를 들어
A=10u1v1T+3u2v2T+0.2u3v3T
이면 랭크 2 근사는
A2=10u1v1T+3u2v2T
입니다. 0.2u3v3T는 영향이 작으므로 버립니다.
에커트-영 정리(Eckart-Young theorem)는 다음을 말합니다.
랭크가 k 이하인 모든 행렬 중에서 A에 가장 가까운 행렬은 Ak=UkΣkVkT이다.
수식으로 쓰면 임의의 랭크 k 이하 행렬 B에 대해
∥A−Ak∥≤∥A−B∥
입니다.
직관은 단순합니다. SVD는 A를 서로 직교하는 랭크 1 조각으로 나누고, 그 조각들을 큰 순서로 정렬합니다. k개만 남겨야 한다면 큰 조각부터 남기는 것이 손실을 가장 작게 만듭니다.
저랭크 근사의 오차는 어떤 노름으로 재는지에 따라 달라집니다.
스펙트럴 노름은 행렬이 입력 벡터를 최대 몇 배까지 늘릴 수 있는지를 봅니다.
∥A∥2=σ1
랭크 k 근사의 스펙트럴 오차는
∥A−Ak∥2=σk+1
입니다. 버린 특이값 중 가장 큰 값이 오차입니다.
프로베니우스 노름은 행렬의 모든 원소를 긴 벡터처럼 보고 길이를 잽니다.
∥A∥F=i,j∑Aij2
SVD로 쓰면
∥A∥F=σ12+σ22+⋯+σr2
랭크 k 근사의 프로베니우스 오차는
∥A−Ak∥F=σk+12+σk+22+⋯+σr2
입니다. 버린 특이값들의 제곱합이 버린 정보의 총량입니다.
특이값이 10,3,0.2,0.01이라고 합시다.
- k=1이면 스펙트럴 오차는 3입니다.
- k=2이면 스펙트럴 오차는 0.2입니다.
- k=3이면 스펙트럴 오차는 0.01입니다.
k를 늘릴수록 오차는 줄어듭니다. 특이값이 빠르게 작아지는 행렬일수록 적은 k로도 좋은 근사가 가능합니다.
흑백 이미지는 픽셀 밝기 값을 모은 행렬입니다. 1000x1000 이미지는 100만 개 숫자를 가진 행렬입니다.
SVD 후 k=50만 남기면 U50, Σ50, V50T만 저장합니다. 원래 행렬 전체를 저장하는 것보다 훨씬 적은 숫자로 이미지의 주요 윤곽을 보존할 수 있습니다.
작은 잡음은 보통 작은 특이값 방향에 섞입니다. 저랭크 근사로 작은 특이값 조각을 버리면 큰 구조는 남기고 잡음은 줄일 수 있습니다.
사용자-아이템 평점 행렬은 매우 큽니다. SVD를 사용하면 사용자의 취향과 아이템의 특징을 몇 개의 숨겨진 축으로 요약할 수 있습니다. 이 축을 이용해 비어 있는 평점을 추정합니다.
단어-문서 행렬에 SVD를 적용하면 단어와 문서의 숨겨진 의미 축을 찾을 수 있습니다. 이를 잠재 의미 분석(Latent Semantic Analysis)이라고 합니다.
어떤 행렬의 특이값이 다음과 같다고 합시다.
σ1=8,σ2=5,σ3=0.5,σ4=0.01
0이 아닌 특이값이 4개이므로 랭크는 4입니다.
랭크 2로 근사하면 스펙트럴 오차는
σ3=0.5
입니다.
프로베니우스 노름 기준으로 전체 정보량을 특이값 제곱합으로 보면
82+52+0.52+0.012=64+25+0.25+0.0001=89.2501
랭크 2 근사가 보존하는 양은
82+52=89
입니다. 비율은
89.250189≈99.7%
입니다. 네 방향 중 두 방향만 남겨도 대부분의 정보를 보존합니다.
다음 대각행렬을 봅시다.
A=⎣⎢⎡500030001⎦⎥⎤
특이값은 5, 3, 1입니다. 랭크 1 근사는 가장 큰 특이값 5만 남깁니다.
A1=⎣⎢⎡500000000⎦⎥⎤
버린 부분은
A−A1=⎣⎢⎡000030001⎦⎥⎤
입니다. 스펙트럴 오차는 다음 특이값인 3입니다.
7절의 SVD를 다시 사용합니다.
U=21[11−11],Σ=[5001],VT=21[1−111]
입력 x=(1,0)T를 넣으면 먼저
VTx=21[1−1]
입니다. 특이값을 곱하면
ΣVTx=21[5−1]
입니다. 마지막으로 U를 곱하면
UΣVTx=[32]
가 됩니다. 실제로
[3223][10]=[32]
이므로 세 단계 분해가 원래 행렬곱과 같은 결과를 냅니다.
100x100 행렬의 특이값이 다음과 같다고 합시다.
σ1=50,σ2=20,σ3=5,σ4=0.1,σ5=0.001,σ6=⋯=σ100≈0
원래 행렬은 100×100=10000개 숫자를 저장해야 합니다.
랭크 3 근사는 다음을 저장합니다.
- U3: 100×3=300개
- Σ3: 3×3=9개
- V3T: 3×100=300개
총 609개입니다.
10000609=6.09%
즉 약 6%의 저장 공간만 사용합니다.
정보 보존 비율은 특이값 제곱합으로 계산할 수 있습니다.
502+202+52+0.12+0.0012502+202+52=2925.0100012925≈99.9997%
저장 공간은 크게 줄이면서 대부분의 정보를 보존합니다.
- SVD는 A=UΣVT로 행렬을 분해한다.
- VT는 입력을 좋은 방향 기준으로 분해한다.
- Σ는 각 방향 성분을 특이값만큼 늘린다.
- U는 늘어난 성분을 출력 방향으로 조립한다.
- 특이값은 방향별 길이 변화량이며 항상 0 이상이다.
- 큰 특이값은 중요한 방향, 작은 특이값은 덜 중요한 방향을 뜻한다.
- 랭크는 0이 아닌 특이값의 개수다.
- SVD는 행렬을 랭크 1 조각들의 합으로 해석하게 해 준다.
- 저랭크 근사는 큰 특이값 조각만 남기고 작은 조각을 버리는 것이다.
- Ak=UkΣkVkT는 랭크 k 행렬 중 최선의 근사다.
- 스펙트럴 오차는 σk+1이고, 프로베니우스 오차는 버린 특이값 제곱합의 제곱근이다.
- SVD는 이미지 압축, 노이즈 제거, 추천 시스템, 자연어 처리에 쓰인다.
-
A=UΣVT에서 VT, Σ, U의 역할을 순서대로 말할 수 있는가?
-
직교행렬이 왜 길이를 보존하는지 QTQ=I로 설명할 수 있는가?
-
특이값이 왜 0 이상인지 설명할 수 있는가?
-
특이값이 7,2,0인 행렬의 랭크는 몇인가?
-
특이값이 10,3,0.1인 행렬을 랭크 1로 근사하면 스펙트럴 오차는 얼마인가?
-
저랭크 근사가 작은 특이값을 버리는 이유를 말할 수 있는가?
-
이미지 압축에서 k를 너무 작게 잡으면 어떤 일이 생기는가?
-
추천 시스템에서 사용자-아이템 행렬을 저랭크로 본다는 말이 무슨 뜻인지 설명할 수 있는가?
-
A=∑iσiuiviT가 왜 랭크 1 조각들의 합인지 설명할 수 있는가?
-
SVD가 고윳값분해보다 더 일반적인 이유를 말할 수 있는가?