K-SVD: Sparse Dictionary building algorithm

K-SVD An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation.pdf

 Sparse Representation이라는 용어는 2010년을 넘어서 나름 Hot한 주제인 것 같다. 기본 컨셉은 간단하다. 주어진 어떤 data를 특정 basis의 Linear combination으로 나타내고자 하는 것이다. 일반적인 PCA가 이러한 문제를 푸는 solution이였지만 주어진 모든 basis를 사용해서 data를 표현한다는 단점이 있다. (노이즈 성분 등 불필요한 성분도 같이 표현될 여지가 있다.)

 이러한 단점을 보완하기 위해서 Sparse라는 개념은 도입했다. Idea는 간단하다. 우리가 찾고자 하는 basis의 Linear coefficient를 sparse하게 하는 조건을 추가하면 된다. 이를 위해서 L0-norm minimization 문제를 풀면 되는데, 이는 수학적으로 NP Hard이기 때문에 여러 근사 방법을 통해서 실제 solution을 구하게 된다. 이에 대표적인 방법이 Sparse PCA이다. 사실 설명이 약간 꼬인 감이 있는데(벌써..) Sparse PCA의 경우 basis들이 sparse하게 나타내진다. 

 여튼 다시 원래 문제로 돌아와서 이러한 solution을 구하는데는 두 가지 문제가 있다. 하나는 over complete한 (즉 data의 dimension보다 Dictionary의 atom의 수가 더 많아한다. 2배 이상이야 된다고 증명된듯) Dictionary를 찾아야 하고, 이렇게 찾은 Dictionary에서 Sparse한 solution을 찾아야 한다. 이번 포스팅에서 설명하고자 하는 것은 Overcomplete한 Dictionary를 만드는 알고리즘인 K-SVD에 대한 것이다. 

 위의 논문의 저자가 친절하게도 프로그램을 올려줘서 내가 자주 사용하는 MNIST Digit dataset으로 실험을 해 보았다. 실험 환경은 간단하다. 총 2000개의 글자 사진을 이용해서 Dictionary를 만들었다. Dictionary의 element의 수는 Data의 dimension인 784의 두 배로 하였고, 초기 Dictionary는 Data를 그대로 사용하게 하였다. 이렇게 해서 만들어진 Dictionary는 다음과 같다. Dictionary의 각 Atom이 글자 모양을 띄고 있는 것을 알 수 있다. 즉 제대로 학습이 되었음을 알 수 있다. 

 학습 결과:

그림1. 학습된 Over complete Dictionary

 프로젝트 파일: 

KSVD MNIST demo.z01

KSVD MNIST demo.z02

KSVD MNIST demo.z03

KSVD MNIST demo.zip

 노트 정리: