희소 사전 학습

희소 사전 학습(sparse dictionary learning) 또는 희소 코딩(sparse coding, 스파스 코딩) 또는 SDL은 입력 데이터의 선형 결합 형태의 기본 요소들과 그 기본 요소들 자체의 희소 표현을 찾는 것을 목표로 하는 표현 학습 방법이다. 이 요소들은 원자라고 불리며 사전을 구성한다. 사전의 원자는 직교일 필요가 없으며, 완전한 확장 집합일 수 있다. 이 문제 설정은 또한 표현되는 신호의 차원이 관찰되는 신호 중 어떤 하나보다 높을 수 있도록 허용한다. 이 두 가지 속성은 동일한 신호에 대해 여러 표현을 허용하는 겉보기에 중복되는 원자를 갖도록 하지만, 표현의 희소성과 유연성을 향상시키기도 한다.

희소 사전 학습의 가장 중요한 응용 분야 중 하나는 압축 감지 또는 신호 복원 분야이다. 압축 감지에서 고차원 신호는 신호가 희소하거나 거의 희소하다는 조건 하에 몇 가지 선형 측정만으로 복원될 수 있다. 모든 신호가 이 조건을 만족하는 것은 아니므로, 웨이블릿 변환 또는 래스터화된 행렬의 방향 그래디언트와 같은 해당 신호의 희소 표현을 찾는 것이 중요하다. 행렬 또는 고차원 벡터가 희소 공간으로 전송되면 기저 추적, CoSaMP,^[1] 또는 고속 비반복 알고리즘^[2]과 같은 다양한 복원 알고리즘을 사용하여 신호를 복원할 수 있다.

사전 학습의 핵심 원리 중 하나는 사전이 입력 데이터로부터 추론되어야 한다는 것이다. 희소 사전 학습 방법의 등장은 신호 처리에서 일반적으로 최소한의 구성 요소를 사용하여 입력 데이터를 표현하고자 한다는 사실에 의해 자극되었다. 이 접근 방식 이전에 일반적인 관행은 푸리에 또는 웨이블릿 변환과 같은 미리 정의된 사전을 사용하는 것이었다. 그러나 특정 경우에는 입력 데이터에 맞게 훈련된 사전이 희소성을 크게 향상시킬 수 있으며, 이는 데이터 분해, 압축 및 분석에 응용되며 이미지 노이즈 제거 및 분류, 비디오 및 오디오 처리 분야에서 사용되어 왔다. 희소성과 과완전 사전은 이미지 압축, 이미지 융합 및 인페인팅에 엄청난 응용 분야를 가지고 있다.

사전 학습을 통한 이미지 노이즈 제거

문제 정의

입력 데이터셋 ${\displaystyle X=[x_{1},...,x_{K}],x_{i}\in \mathbb {R} ^{d}}$가 주어졌을 때, ${\displaystyle \|X-\mathbf {D} R\|_{F}^{2}}$가 최소화되고 표현 ${\displaystyle r_{i}}$가 충분히 희소하도록 사전 ${\displaystyle \mathbf {D} \in \mathbb {R} ^{d\times n}:D=[d_{1},...,d_{n}]}$와 표현 ${\displaystyle R=[r_{1},...,r_{K}],r_{i}\in \mathbb {R} ^{n}}$를 찾고자 한다. 이는 다음과 같은 최적화 문제로 공식화될 수 있다.

${\displaystyle {\underset {\mathbf {D} \in {\mathcal {C}},r_{i}\in \mathbb {R} ^{n}}{\text{argmin}}}\sum _{i=1}^{K}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{0}}$, 여기서 ${\displaystyle {\mathcal {C}}\equiv \{\mathbf {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}}$, ${\displaystyle \lambda >0}$

${\displaystyle {\mathcal {C}}}$는 원자들이 임의로 높은 값에 도달하는 것을 방지하여 ${\displaystyle r_{i}}$의 임의로 낮은(하지만 0이 아닌) 값을 허용하도록 ${\displaystyle \mathbf {D} }$를 제약해야 한다. ${\displaystyle \lambda }$는 희소성과 최소화 오류 사이의 균형을 제어한다.

위의 최소화 문제는 ℓ₀-"노름" 때문에 볼록이 아니며 이 문제를 해결하는 것은 NP-완전이다.^[3] 어떤 경우에는 L¹-노름이 희소성을 보장하는 것으로 알려져 있어^[4] 위의 문제는 다른 변수가 고정될 때 각 변수 ${\displaystyle \mathbf {D} }$와 ${\displaystyle \mathbf {R} }$에 대해 볼록 최적화 문제가 되지만, ${\displaystyle (\mathbf {D} ,\mathbf {R} )}$에 대해서는 공동으로 볼록이 아니다.

사전의 속성

위에 정의된 사전 ${\displaystyle \mathbf {D} }$는 ${\displaystyle n<d}$일 경우 "불완전"할 수 있으며, ${\displaystyle n>d}$일 경우 "과완전"할 수 있는데, 후자가 희소 사전 학습 문제에 대한 일반적인 가정이다. 완전 사전의 경우는 표현 관점에서 어떤 개선도 제공하지 않으므로 고려되지 않는다.

불완전 사전은 실제 입력 데이터가 더 낮은 차원의 공간에 놓여 있는 설정을 나타낸다. 이 경우는 차원 축소 (통계학) 및 원자 ${\displaystyle d_{1},...,d_{n}}$이 직교해야 하는 주성분 분석과 같은 기술과 밀접하게 관련되어 있다. 이러한 부분 공간의 선택은 효율적인 차원 축소에 중요하지만, 이는 사소하지 않다. 그리고 사전 표현 기반의 차원 축소는 데이터 분석 또는 분류와 같은 특정 작업을 해결하기 위해 확장될 수 있다. 그러나 이들의 주요 단점은 원자 선택을 제한한다는 것이다.

그러나 과완전 사전은 원자가 직교할 것을 요구하지 않으므로 (어쨌든 기저를 가질 수 없다) 더 유연한 사전과 풍부한 데이터 표현을 허용한다.

신호의 희소 표현을 허용하는 과완전 사전은 잘 알려진 변환 행렬(웨이블릿 변환, 푸리에 변환)이 될 수도 있고, 주어진 신호를 최적으로 희소하게 표현할 수 있도록 요소가 변경되도록 공식화될 수도 있다. 학습된 사전은 미리 정의된 변환 행렬에 비해 더 희소한 솔루션을 제공할 수 있다.

알고리즘

위에 설명된 최적화 문제는 사전 또는 희소 코딩 중 하나를 고정했을 때 볼록 문제로 해결될 수 있으므로, 대부분의 알고리즘은 하나를 반복적으로 업데이트한 다음 다른 하나를 업데이트하는 아이디어에 기반한다.

주어진 사전 ${\displaystyle \mathbf {D} }$를 가지고 최적의 희소 코딩 ${\displaystyle R}$을 찾는 문제는 희소 근사 (또는 단순히 희소 코딩 문제)로 알려져 있다. 이를 해결하기 위해 여러 알고리즘 (예: 매칭 추적 및 LASSO)이 개발되었으며 아래 설명된 알고리즘에 통합되어 있다.

최적 방향법 (MOD)

최적 방향법(MOD)은 희소 사전 학습 문제를 해결하기 위해 도입된 최초의 방법 중 하나였다.^[5] 핵심 아이디어는 표현 벡터의 비제로 구성 요소 수를 제한하여 최소화 문제를 해결하는 것이다.

${\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T}$

여기서 ${\displaystyle F}$는 프로베니우스 노름을 나타낸다. MOD는 매칭 추적과 같은 방법을 사용하여 희소 코딩을 얻는 것과 ${\displaystyle \mathbf {D} =XR^{+}}$에 의해 주어진 문제의 해석적 해를 계산하여 사전을 업데이트하는 것을 번갈아 수행한다. 여기서 ${\displaystyle R^{+}}$는 무어-펜로즈 유사역행렬이다. 이 업데이트 후 ${\displaystyle \mathbf {D} }$는 제약 조건에 맞게 정규화되고 새로운 희소 코딩이 다시 얻어진다. 이 과정은 수렴할 때까지 (또는 잔차가 충분히 작을 때까지) 반복된다.

MOD는 몇 번의 반복만으로 수렴하여 저차원 입력 데이터 ${\displaystyle X}$에 매우 효율적인 방법임이 입증되었다. 그러나 행렬 역연산의 높은 복잡성으로 인해 고차원 경우에서 유사역행렬을 계산하는 것은 많은 경우 불가능하다. 이러한 단점은 다른 사전 학습 방법의 개발을 촉진했다.

K-SVD

 이 부분의 본문은 K-SVD입니다.

K-SVD는 사전의 원자들을 하나씩 업데이트하기 위해 핵심적으로 SVD를 수행하는 알고리즘이며, 기본적으로 K-평균의 일반화이다. 이 알고리즘은 MOD 접근 방식과 동일하게 입력 데이터 ${\displaystyle x_{i}}$의 각 요소가 ${\displaystyle T_{0}}$개 이하의 요소의 선형 결합으로 인코딩되도록 강제한다.

${\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}}$

이 알고리즘의 핵심은 먼저 사전을 고정하고, 위 제약 조건 하에서 가능한 최상의 ${\displaystyle R}$을 찾은 다음 (직교 매칭 추적 사용), 다음 방식으로 사전 ${\displaystyle \mathbf {D} }$의 원자를 반복적으로 업데이트하는 것이다.

${\displaystyle \|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}}$

알고리즘의 다음 단계에는 잔차 행렬 ${\displaystyle E_{k}}$의 랭크-1 근사, ${\displaystyle d_{k}}$ 업데이트, 업데이트 후 ${\displaystyle x_{k}}$의 희소성 강제가 포함된다. 이 알고리즘은 사전 학습의 표준으로 간주되며 다양한 응용 분야에서 사용된다. 그러나 MOD와 약점을 공유하며, 비교적 낮은 차원의 신호에만 효율적이고 지역 최솟값에 갇힐 가능성이 있다.

확률적 경사 하강법

 이 부분의 본문은 확률적 경사 하강법입니다.

또한 반복 투영을 사용하여 널리 사용되는 확률적 경사 하강법을 이 문제를 해결하는 데 적용할 수 있다.^[6] 이 방법의 아이디어는 1차 확률적 경사를 사용하여 사전을 업데이트하고 이를 제약 집합 ${\displaystyle {\mathcal {C}}}$에 투영하는 것이다. i번째 반복에서 발생하는 단계는 다음 표현식으로 설명된다.

${\displaystyle \mathbf {D} _{i}={\text{proj}}_{\mathcal {C}}\left\{\mathbf {D} _{i-1}-\delta _{i}\nabla _{\mathbf {D} }\sum _{i\in S}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right\}}$, 여기서 ${\displaystyle S}$는 ${\displaystyle \{1...K\}}$의 임의의 부분집합이고 ${\displaystyle \delta _{i}}$는 경사 하강 단계이다.

라그랑주 이중 방법

이중 라그랑주 문제를 해결하는 데 기반한 알고리즘은 희소 함수로 인한 복잡성 없이 사전을 효율적으로 해결하는 방법을 제공한다.^[7] 다음 라그랑주 함수를 고려해 보자.

${\displaystyle {\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}\left((X-\mathbf {D} R)^{T}(X-\mathbf {D} R)\right)+\sum _{j=1}^{n}\lambda _{j}\left({\sum _{i=1}^{d}\mathbf {D} _{ij}^{2}-c}\right)}$, 여기서 ${\displaystyle c}$는 원자의 노름에 대한 제약 조건이고 ${\displaystyle \lambda _{i}}$는 대각 행렬 ${\displaystyle \Lambda }$를 형성하는 이중 변수이다.

${\displaystyle \mathbf {D} }$에 대해 최소화한 후 라그랑주 이중의 해석적 표현을 제공할 수 있다.

${\displaystyle {\mathcal {D}}(\Lambda )=\min _{\mathbf {D} }{\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}(X^{T}X-XR^{T}(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}-c\Lambda )}$.

이중 값에 최적화 방법 중 하나를 적용한 후 (뉴턴 방법 또는 켤레 기울기) ${\displaystyle \mathbf {D} }$의 값을 얻는다.

${\displaystyle \mathbf {D} ^{T}=(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}}$

이 문제를 해결하는 것은 계산적으로 덜 어렵다. 이중 변수의 양 ${\displaystyle n}$이 원본 문제의 변수 양보다 훨씬 적은 경우가 많기 때문이다.

LASSO

 이 부분의 본문은 라쏘입니다.

이 접근 방식에서 최적화 문제는 다음과 같이 공식화된다.

${\displaystyle \min _{r\in \mathbb {R} ^{n}}\{\,\,\|r\|_{1}\}\,\,{\text{subject to}}\,\,\|X-\mathbf {D} R\|_{F}^{2}<\epsilon }$, 여기서 ${\displaystyle \epsilon }$은 재구성 LASSO에서 허용되는 오류이다.

이것은 해 벡터에서 L¹-노름 제약 조건에 따라 최소 제곱 오차를 최소화함으로써 ${\displaystyle r_{i}}$의 추정치를 찾는다.

${\displaystyle \min _{r\in \mathbb {R} ^{n}}\,\,{\dfrac {1}{2}}\,\,\|X-\mathbf {D} r\|_{F}^{2}+\lambda \,\,\|r\|_{1}}$, 여기서 ${\displaystyle \lambda >0}$는 희소성과 재구성 오차 사이의 균형을 제어한다. 이것은 전역 최적 솔루션을 제공한다.^[8] 또한 희소 코딩을 위한 온라인 사전 학습도 참조.

파라미터 훈련 방법

파라미터 훈련 방법은 분석적으로 구성된 사전과 학습된 사전이라는 두 세계의 장점을 모두 통합하는 것을 목표로 한다.^[9] 이를 통해 임의 크기의 신호에도 잠재적으로 적용될 수 있는 보다 강력하고 일반화된 사전을 구축할 수 있다. 주목할 만한 접근 방식은 다음과 같다.

• 변환 불변 사전.^[10] 이 사전은 유한 크기 신호 패치용으로 구성된 사전에서 유래한 원자들의 변환으로 구성된다. 이를 통해 결과 사전은 임의 크기 신호에 대한 표현을 제공할 수 있다.
• 다중 스케일 사전.^[11] 이 방법은 희소성을 향상시키기 위해 다양한 스케일의 사전으로 구성된 사전을 구축하는 데 중점을 둔다.
• 희소 사전.^[12] 이 방법은 희소 표현을 제공할 뿐만 아니라 ${\displaystyle \mathbf {D} =\mathbf {B} \mathbf {A} }$ 표현식에 의해 강제되는 희소 사전을 구축하는 데 중점을 둔다. 여기서 ${\displaystyle \mathbf {B} }$는 빠른 계산과 같은 바람직한 속성을 가진 미리 정의된 분석 사전이고 ${\displaystyle \mathbf {A} }$는 희소 행렬이다. 이러한 공식화는 분석 사전의 빠른 구현과 희소 접근 방식의 유연성을 직접 결합할 수 있게 한다.

온라인 사전 학습 (LASSO 접근 방식)

희소 사전 학습에 대한 많은 일반적인 접근 방식은 전체 입력 데이터 ${\displaystyle X}$ (또는 최소한 충분히 큰 훈련 데이터셋)가 알고리즘에서 사용 가능해야 한다는 사실에 의존한다. 그러나 입력 데이터의 크기가 너무 커서 메모리에 담을 수 없을 때와 같이 실제 시나리오에서는 그렇지 않을 수 있다. 이 가정을 할 수 없는 또 다른 경우는 입력 데이터가 스트림 형태로 들어올 때이다. 이러한 경우는 온라인 학습 연구 분야에 속하며, 이는 본질적으로 새로운 데이터 포인트 ${\displaystyle x}$가 사용 가능해지면 모델을 반복적으로 업데이트하는 것을 제안한다.

사전은 다음 방식으로 온라인으로 학습될 수 있다.^[13]

1. ${\displaystyle t=1...T:}$
2. 새로운 샘플 ${\displaystyle x_{t}}$를 그린다.
3. LARS를 사용하여 희소 코딩을 찾는다. ${\displaystyle r_{t}={\underset {r\in \mathbb {R} ^{n}}{\text{argmin}}}\left({\frac {1}{2}}\|x_{t}-\mathbf {D} _{t-1}r\|+\lambda \|r\|_{1}\right)}$
4. 블록-좌표 접근 방식을 사용하여 사전을 업데이트한다. ${\displaystyle \mathbf {D} _{t}={\underset {\mathbf {D} \in {\mathcal {C}}}{\text{argmin}}}{\frac {1}{t}}\sum _{i=1}^{t}\left({\frac {1}{2}}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right)}$

이 방법을 통해 새로운 데이터가 희소 표현 학습에 사용할 수 있게 됨에 따라 사전을 점진적으로 업데이트할 수 있으며 (종종 크기가 매우 큰) 데이터셋을 저장하는 데 필요한 메모리 양을 크게 줄일 수 있다.

응용 분야

사전 학습 프레임워크, 즉 데이터 자체에서 학습된 몇 가지 기본 요소를 사용하여 입력 신호를 선형 분해하는 방식은 다양한 이미지 및 비디오 처리 작업에서 최신 기술 수준의 결과를 가져왔다. 이 기술은 각 클래스에 대해 특정 사전을 구축했다면, 가장 희소한 표현에 해당하는 사전을 찾아 입력 신호를 분류하는 방식으로 분류 문제에 적용될 수 있다. 또한 신호 잡음 제거에도 유용한 속성을 가지고 있다. 일반적으로 입력 신호의 의미 있는 부분을 희소하게 표현하도록 사전을 학습할 수 있지만, 입력의 잡음은 훨씬 덜 희소한 표현을 갖기 때문이다.^[14]

희소 사전 학습은 다양한 이미지, 비디오, 오디오 처리 작업뿐만 아니라 텍스처 합성^[15] 및 비지도 클러스터링에도 성공적으로 적용되었다.^[16] Bag-of-Words 모델과의 평가에서,^[17][18] 희소 코딩은 객체 범주 인식 작업에서 다른 코딩 접근 방식을 능가하는 것으로 경험적으로 밝혀졌다.

사전 학습은 의료 신호를 상세하게 분석하는 데 사용된다. 이러한 의료 신호에는 뇌전도(EEG), 심전도(ECG), 자기 공명 영상(MRI), 기능적 MRI(fMRI), 연속 혈당 측정기^[19] 및 초음파 컴퓨터 단층 촬영(USCT)이 포함되며, 각 신호를 분석하기 위해 다른 가정이 사용된다.

같이 보기

• 희소 근사
• 희소 PCA
• K-SVD
• 행렬 분해
• 신경 희소 코딩