오늘은 최근에 논문을 보면서 관심이 생긴 스파스 사전 학습(sparse dictionary learning)에 대해 정리하려고 한다. 스파스 사전 학습은 스파스 코딩(sparse coding)이라는 기법을 활용하는 사전 학습이다. 이 방법은 꽤 오래 전에 제안되었지만 아이디어와 성능 면에서 꽤 매력적인 알고리즘이다. 우선 이름을 구성하고 있는 단어들을 하나씩 보면서 대략 이것이 무엇인지 파악해보자. 


"sparse"는 '드문, 희박한'이란 의미를 갖고 있는데, 일반적으로 수학에서 벡터나 행렬의 많은 원소가 0일 때 스파스(sparse)하다고 말한다[1]. 그리고 "dictionary"는 다들 알다시피 '사전'이이고, "learning"은 '학습'이다. 사전 학습은 즉 우리가 영어사전에서 모르는 단어의 뜻을 찾는 것과 같이 어떤 주어진 간단한 단서(e.g. 스펠링)를 이용해서 필요한 정보(e.g. 단어의 뜻과 용법)를 찾아내는 방식의 알고리즘이다. 앞에 스파스를 붙인 스파스 사전 학습은 매우 적은 단서로 필요한 정보를 찾아내는 방법이라고 보면 될 것이다. 그렇다면 이제 본격적으로 스파스 사전 학습에 대해 이해해보자. 그전에 잠시 컴퓨터 비전의 한 연구 분야를 설명할 것이다.  



▶ 이미지 품질 평가(image quality assessment, IQA)란? 


컴퓨터 비전 연구 영역 중에는 이미지 품질 평가(image quality assessment, IQA)라는 과제가 있다. 간단히 말해서 주어진 이미지를 보고 이미지의 품질이 좋은지 나쁜지 판정하는 것이다. 만약 이미지에 왜곡(distortion)이 많이 가해졌다면 품질이 나쁠 것이고, 그렇지 않으면 품질이 좋을 것이다. 또한 어떤 유형의 왜곡은 어느 수준까지는 가해져도 우리가 인지하는데 큰 방해를 주지 않는 반면, 어떤 왜곡은 조금만 가해져도 상당히 인지 품질(perceptual quality)을 떨어뜨린다. 감을 잡기 위해 그림1을 보자. 



그림1에 두 개의 왜곡된 이미지와 각각의 DMOS(differential mean opinion score)값들이 있는데, DMOS가 클 수록 인지 품질이 나쁜 것이다. 왼쪽 이미지의 인지 품질이 오른쪽 이미지보다는 훨씬 좋다는 것을 알 수 있다. 이 DMOS 값은 여러 명의 사람들이 직접 왜곡된 이미지들을 보고 점수 매긴 것을 평균낸 것이다(자세하게는 조금 다르지만 이렇게 이해하고 넘어가도 무방하다). 이러한 품질 점수를 사람이 아닌 컴퓨터를 통해서 예측해낼 수 있다면, 이미지와 관련된 여러 분야에서 응용될 수 있을 것이다. 왜냐하면 이미지를 최종적으로 전달 받을 사람들이 좋은 지각 품질로 받아볼 수 있게 해야하기 때문이다. 갑자기 IQA라는 분야를 잠시 소개한 이유는 스파스 사전 학습이 이 분야에 활용된 예를 통해 스파스 사전 학습이 무엇인지 구체적으로 설명하기 위함이다. 



▶ 스파스 사전 학습(sparse dictionary learning)이란?


우리에게 100장의 왜곡된 이미지들과 그에 상응하는 DMOS값들을 포함하고 있는 데이터베이스가 있다고 생각해보자. 일단 데이터베이스 내의 100장의 왜곡된 이미지들에서 품질과 관련되어 있는 이미지 특성들(f)을 도출한다. 20개를 도출했다고 하자. 즉, 각 이미지당 20개의 특성을 도출한 것이다. 한 이미지의 특성을 열 벡터(20 x 1)로 해서 행으로 차곡차곡 나열하면 하나의 행렬이 만들어지고, 이 행렬의 크기는 20 x 100이 된다(그림2). 이것을 사전(dictionary)이라고 부른다. 사전 안에 있는 하나의 열 벡터(column vector)들을 각각 atom이라고 부른다. 이 경우에는 사전 안에 100개의 atom이 있는 셈이다.  


그림2. 20x100의 행렬로 사전이 만들어졌다.


사전 학습의 원리를 간단히 설명하자면, 데이터베이스에 존재하지 않는 새로운 왜곡된 이미지에서도 20개의 특성을 도출한 다음에 사전에서 그것과 가장 비슷한 특성값들을 갖고 있는 것을 찾아내서 그것의 점수가 새로운 이미지의 품질이라고 판단하는 것이다. 만약 새로운 이미지의 특성이 45번째 이미지의 특성과 가장 유사하다면, 새로운 이미지의 품질 점수가 45번째 이미지와 비슷하다고 판단하는 것이다. 


따라서 어떤 이미지의 품질을 평가하고 싶다면, 우선 마찬가지로 20개의 특성을 도출해야 한다. 그 다음에 특성이 사전에 있는 열 벡터들, 즉 atom들의 선형 조합으로 표현되게 한다(). 


그림3. 테스트할 이미지의 특성들을 아톰들의 선형조합으로 나타내야 한다.


그런데 이때 최대한 많은 계수들이 0이 되게 해야한다(스파스(sparse)하게 만들기 위해서). 이것을 아래와 같이 나타낸다. 조금 어려워보일 수 있는데 당황하지 말고 천천히 아래의 설명을 읽어보자. 


...(공식1: 최적의 스파스 표현 계수를 찾는 공식1)


공식1에서 는  최대한 많은 요소들을 0으로 만들면서 를 만족시키는 를 의미하며, 스파스 표현 계수(sparse representation coefficient)라고 불린다. (L0-minimization)은 벡터 내의 0이 아닌 요소의 총 개수를 구하는 방법이다. 그리고 s.t.은 최적화 문제에서 subject to의 약자로서 '~을 조건으로'라는 뜻이다[3]. 즉, 인 조건 아래에서 의 최대한 많은 요소들을 0으로 만드는 인 을 찾으라는 것이다. 결과적으로 의 대부분의 요소들은 0일 것이다. 그런데 L0-minimization은 너무 복잡해서 푸는 것이 거의 불가능하다는 뜻의 NP-hard 문제라고 불린다. 따라서 L0-minimization 대신 L1-norm이 사용되면서 공식1은 공식2로 대체된다. 


...(공식2: 최적의 스파스 표현 계수를 찾는 공식2)


그리고 공식2에 있던 조건을 식에 포함시키면 공식3으로 전환할 수 있다. 


...(공식3: 최적의 스파스 표현 계수를 찾는 공식3)


여기서 는 양의 상수로 두 항의 균형을 맞추는 역할을 한다. 아무튼 핵심은 가 되게 하면서, 가장 스파스한 표현인 를 찾는다는 것이다. 공식3은 라쏘를 이용해서 해결할 수 있다. 

(라쏘에 대해 관심이 있다면, http://bskyvision.com/193을 참고하자)


를 찾았다면, 이제 테스트 이미지의 품질 점수를 예측할 때가 되었다. 만약 테스트 이미지에서 도출한 20개의 특성(f)이 사전에 있는 세번째 atom, 즉 과 가장 유사하다면 아마도 이 가장 큰 값을 갖고 있을 것이다(그림4). 또한 이 도출된 세번째 이미지의 DMOS값과 테스트 이미지의 DMOS값이 가장 유사할 것이다. 만약 f가 f37과 가장 유사하다면, 아마도 이 가장 큰 값을 갖고 있을 것이고 테스트 이미지의 품질은 37번째 이미지의 DMOS값과 가장 비슷할 것이다.


그림4. 만약 테스트 이미지의 특성 f가 f3과 가장 유사하다면, a3이 가장 큰 값을 갖고 있을 것이다.


이것을 염두에 두고 아래 식을 보자. 


...(공식4: 테스트 이미지의 품질 예측)


공식4의 분자 부분을 잘 보면, 사전 내의 i번째 이미지의 DMOS값과 의 i번째 요소를 곱한 것들을 모두 더한 것임을 알 수 있다. 즉 이 큰 만큼 i번째 이미지의 DMOS의 영향력이 커지는 것이다. 사전에서 가장 비슷한 애들의 내용을 조합해서 결과를 만들어내는 것이다. 


스파스 사전 학습으로 예측된 이미지 품질 점수가 사람들이 직접 보고 평가를 매긴 것(DMOS)과 꽤 비슷하다는 것을 몇몇 연구에서 밝혀냈다[4]. 다른 머신 러닝 알고리즘이나 딥 러닝을 활용한 IQA 알고리즘들이 더 좋은 성능을 산출한 경우도 있지만, 스파스 사전 학습을 활용하는 것도 하나의 괜찮은 방법인 것 같다. 

 


▶ 정리


스파스 사전 학습은 label 값을 모르는 어떤 데이터를 사전 내에 있는 atom들의 선형 조합()으로 나타내는데, 이때 선형 계수들이 아래와 같이 최대한 많이 0이 되게 하는 선형 계수들을 찾아내는 학습 알고리즘이다. 



물론 L0-minimization 대신에 L1-norm을 사용하기 때문에 조금 다른 결과가 나오겠지만 개념 설명을 위해서 이렇게 표현했다. 아무튼 이렇게 해서 얻은 스파스 표현 계수들()이 새로운 데이터의 라벨(label) 값을 예측하는데 사용된다. 스파스 사전 학습은 위에서 소개한 IQA를 제외하고도 상당히 많은 컴퓨터 비전 분야에서 응용되어 사용되고 있다. 

  

부족한 글이지만, 여기까지 천천히 정독하신 분들은 분명 도움이 되셨을 것이라고 생각합니다. 질문이나, 잘못된 것 있으면 꼭 댓글 남겨주시고, 글이 도움이 되셨다면 공감 눌러주세요:D




<참고 자료>

[1] 다다 사토시, 처음 배우는 인공지능

[2] https://rorasa.wordpress.com/2012/05/13/l0-norm-l1-norm-l2-norm-l-infinity-norm/ => norm에 대한 설명

[3] https://math.stackexchange.com/questions/934108/what-does-s-t-mean => 최적화 문제에서 s.t.의 의미 설명 

[4] D. Tao, "Sparse representation for blind image quality assessment", IEEE Conference on Computer Vision & Pattern Recognition, 2012

[5] https://en.wikipedia.org/wiki/Sparse_dictionary_learning



Posted by 톈진난만

댓글을 달아 주세요

  1. 송기대장 2017.11.07 16:29 신고  댓글주소  수정/삭제  댓글쓰기

    수학공부좀 다시해야겠네요 덜덜..
    퀄리티 있는자료 감사합니다



티스토리 툴바