달력

10

« 2017/10 »

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  
  •  

'삽질예방/SVD'에 해당되는 글 1

  1. 2008.01.27 SVD와 압축
2008.01.27 09:29

SVD와 압축 삽질예방/SVD2008.01.27 09:29

출처 : http://markov.tistory.com/30
좋은 정보 감사합니다.

ㅡㅡㅡㅡㅡㅡㅡ

이번 글에서 다룰 내용은, m*n 행렬 X를 k*n 행렬 Z로 손실 압축(lossy compression)하는 방법입니다(k < n < m).

이렇게 크기가 줄어든 행렬 Z는, 목적에 따라 그 자체로 써먹을 수도 있지만 대부분은 원래의 m*n 행렬로 복원(decompression)한 다음에 사용하게 됩니다. 압축이 X에서 Z로의 변환이라면, 복원은 Z에서 X로의 역변환이 되겠죠. 역변환된 m*n 행렬을  이라고 합시다. 이는 손실 압축된 Z로부터 복원한 것이므로, 원래의 X와는 약간 다를 것입니다. 즉, "정보의 괴리"가 발생합니다.

우리의 목적은, 압축률을 k*n으로 고정하였을 때, 원래의 X와 복원된 간의 차이를 최소화 하는 압축 및 복원 알고리즘을 찾는 것입니다. 이것을 식으로 쓰면 아래와 같은 형태가 되겠죠.

(1)     

Z는 k*n으로 압축된 행렬이고 k < n이므로, Z의 rank는 최대 k입니다. 따라서 Z로부터 복원된 행렬 의 rank 또한 최대 k가 됩니다. 반면, 원래의 행렬 X의 rank는 n으로, k보다 큽니다. 즉, 식 (1)은 X와의 오차가 가장 작은 rank k짜리 행렬을 찾는 문제가 되며, 이를 rank-k approximation 이라고 합니다.

이때 식 (1)의 norm이 2 norm이나 Frobenius norm이라면, 오차가 가장 작은 rank-k 행렬은 X를 로 SVD한 것에서 [singular value가 가장 큰 순서대로 k개를 뽑아 구성한 행렬]이 됩니다(주1). 이를 식으로 나타내면 아래와 같습니다.

(2)     
                      

주석 보기


식 (2)에서 는 [U의 첫 번째부터 k번째까지의 열벡터들]만으로 이루어진 행렬을 의미하며(도 마찬가지 의미), 는 [S의 첫 번째부터 k번째까지의 대각선 원소값들]로 이루어진 대각행렬을 나타냅니다. 각 행렬의 밑에 해당 행렬의 크기를 괄호로 표시하였습니다.

자, 이것으로 우리는, "압축 후 복원된 행렬은 식 (2)와 같아야 한다"라는 사실을 알았습니다. 그러면 이제 남은 것은, "X를 어떻게 압축했다가 복원하면 식 (2)와 같은 행렬을 얻을 수 있는지?"를 유도해내는 일이 되겠죠!

압축과 복원은, 간단히 행렬의 곱으로 구현할 수 있습니다. 예를 들어 m*n 행렬 X를 k*n 행렬 Z로 압축한다고 하면, 아래와 같이 k*m짜리 행렬 W를 X 앞에 곱해주는 것입니다. 이때 W가 바로 압축 변환이 됩니다.

(3)     

이번엔 Z를 으로 복원해 보겠습니다. Z는 k*n이고 은 m*n이니, 복원 변환은 m*k짜리 행렬이 되며(이를 Y라고 합시다) 이것을 아래와 같이 Z 앞에 곱해주면 됩니다.

(4)     

이제 압축 변환 행렬 W와 복원 변환 행렬 Y가 각각 무엇인가를 구해야 합니다만, 그러기 전에 여기서 한 가지 짚고 넘어갈 점이 있습니다. 복원된 행렬을 재압축할 때의 문제인데요... jpg 파일을 편집해보신 분들은 많이 느끼셨을 점인데, jpg 포맷은 복원된 이미지를 재압축하면 정보의 추가 손실이 발생하지요. 마찬가지로 음원 압축에서 널리 쓰이는 mp3 포맷도 그렇고요. 이거 꽤 불편하고 나쁘지 않습니까? 이 글에서 다룰 알고리즘은 을 재압축하였을 때 추가적인 정보 손실이나 변환 없이 다시 Z로 돌아올 수 있도록 해 봅시다.

식 (4)에서  라고 했으니, 이걸 다시 압축하려면 W를 곱하면 되겠군요. 즉, WYWX = Z, 또는 WYWX = WX가 되어야 합니다(식 (3)에 의해 Z = WX이므로).
따라서,  가 되어야 합니다. 이는 다시 말하면,

(5)         이고  

이어야 한다는 얘기가 됩니다. 직교행렬(orthogonal matrix)과 비슷한 조건인데, 는 성립하지 않는다는 것이 다릅니다(주2).

주석 보기


따라서 식 (4)의 우변은 가 되는데, 이때 X를 로 SVD하면 더 쪼개지죠.
또한, [식 (4) = 식 (2) = ]이므로, 아래와 같이 식 (6)을 얻을 수 있으며

(6)     

이를 풀면 최종적으로 식 (7)과 같이 답을 얻을 수 있습니다(주3). 식 (7)에서 Q는 크기가 k*k인 임의의 직교행렬을 의미합니다.

(7)     

주석 보기


즉, U 앞에 곱해지는 행렬이 직교행렬이라면, 무엇을 곱하든 최적의(= 정보 손실을 최소화 하는) 압축 변환 행렬 W를 얻을 수 있습니다. ambiguity가 있다는 거죠. 하지만 Q가 달라짐으로 해서 나타나는 변화는, 기껏해야 W가 span하는 공간의 좌표계가 회전(rotation)하거나 좌표축의 순서가 바뀌는(permutation) 정도 뿐입니다. 만약 우리 목적이 X로부터 추상화된 의미를 뽑아내는 것이라면 Q를 설정하는 것이 중요한 문제가 되겠지만, 목적이 압축일 때는 Q를 어떻게 잡든 전혀 영향을 주지 않습니다. 따라서 식 (7)의 Q에 단위행렬을 대입하여(단위행렬도 직교행렬이죠) 아래와 같은 결과를 얻을 수 있습니다.

(8)     

결론적으로, 압축률이 [1 - k/m]일 때(즉, m*n 행렬을 k*n으로 압축), 복원된 행렬의 정보 손실을 최소화 하는 압축 및 복원 알고리즘은 아래와 같습니다.

  • 준비 과정: X를 아래와 같이 singular value decomposition하여 U를 얻는다.
         
  • 압축
         
  • 복원
         

자... 이렇게 해서 알고리즘이 나왔네요. 식이 참 간단해 보이는데, complexity는 얼마나 되는 걸까요?
위의 알고리즘에서 가장 시간이 오래 걸리는 부분은, 아이러니하게도 '준비 과정' 부분입니다. 통상적인 알고리즘을 쓰게 되면, m*n 행렬(m > n) X를 SVD 하는 데에 이 걸립니다.

하지만 우리가 원하는 건 모든 singular vector가 아니죠. singular value가 가장 큰 순서대로 k개의 벡터만 있으면 되니까요. 이럴 때는 time complexity를 꽤 많이 줄일 수 있습니다. 널리 쓰이는 방법으로는 Lanczos algorithm이 있는데, 이건 이 걸립니다. 통상적인 알고리즘에 비해 훨씬 쓸만하죠!
뿐만 아니라, 이 분야는 정말 끊임없이 알고리즘이 나오는 분야여서, 보다 효율적인 알고리즘들도 하나하나 찾을 수 없을 정도로 많죠. (구글링을 해보니 첫 페이지부터 짜리 알고리즘이 나오는군요;;)

마지막으로 구현에 대해 말씀드리고 글을 마치겠습니다. 압축과 복원 부분이야 그냥 행렬 곱셈이니까 구현이 어렵지 않고, SVD는 지원하는 공개 라이브러리들이 많으니 언어에 맞게 골라 사용하시면 됩니다.

  • C/C++: LAPACK이 널리 쓰입니다(Redhat Linux, Windows). 또한, 단순히 SVD를 위해 쓰기는 다소 무겁지만 OpenCV도 아주 좋은 라이브러리입니다(이건 .NET도 지원합니다). OpenCV는 Visual Studio를 위해 프로젝트 파일(.sln, .proj)을 제공하며, 컴파일하려면 약간의 설정이 필요합니다.
  • Java: JAMA라는 라이브러리가 있습니다. 구현은 통상적인 알고리즘을 쓴 것 같습니다만, 설치/사용법이 아주 간편하고, 꼭 필요한 몇 개의 decomposition 방법들만 구현되어 있어 가볍습니다.
  • Ruby: linalg라는, LAPACK을 wrapping한 라이브러리를 추천합니다. JAMA와 마찬가지로 설치/사용법이 아주 간편합니다.
신고
Posted by Kwang-sung Jun