논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

UFLDL Tutorial 18. Unsupervised Learning – Sparse Coding

Sparse Coding

스파스 코딩(Sparse coding)은 비교사학습의 한 방법으로 데이터를 효율적으로 표현하기 위해 과적합(over-complete)된 러닝 셋을 학습하기 위한 방법입니다. 스파스 코딩의 목표는 입력 벡터 $\mathbf{x}$를 선형 조합(linear combination)으로 나타낼 수 있는 기저 벡터들 $\phi_i$을 찾는 것입니다.

$$ \mathbf{x} = \sum_{i=1}^k a_i \mathbf{\phi}_{i} $$

주성분분석(Principal Component Analysis, PCA)과 같은 테크닉은 과적합 기저 벡터 셋을 효과적으로 학습하게 해주는 반면에, 여기서는 입력 벡터 $\mathbf{x} \in \mathbb{R}^n, k \lt n$ 인 over-complete된 기저 벡터를 찾도록 해 줍니다. 과적합 기저가 갖는 장점은, 입력 데이터에 내포하고 있는 구조와 패턴을 더 잘 획득할 수 있다는 점입니다. 하지만 과적합 기저를 사사용하면 입력 벡터 $\mathbf{x}$에 의해 정해지는 그 계수 $a_i$가 더 이상 유일하지 않다는 단점이 있습니다. 따라서 스파스 코딩에서는 스파시티(sparsity)라는 추가적인 조건을 통해서 과적합에 의해 생기는 degeneracy를 해결하고자 합니다.

이제 스파시티를 0이 아닌 컴포넌트, 혹은 0에 가까운 값이 아닌 컴포넌트로 정의하여봅시다. 요구사항은 계수 $a_i$가 입력 베거에서 대해서 스파스한 평균 값이 되도록 하는 것입니다. 따라서 계수 중 가능한 적은 수의 계수들만이 0에서 먼 값을 가지도록 하고자 합니다. 입력 데이터의 표현법이 가졌으면 하는 이 스파시티 특성은 보통 이미지와 같이 sensory 데이터가 에지나 표면과 같은 한정된 수의 기초적인 요소들의 중첩으로 기술될 수 있다는 발견에서 유래되었다고 할 수 있습니다. 인간의 시각 피질의 성질과의 비교 또한 정당화되고 있습니다.(?)

스파스 코딩의 비용 함수(cost function)은 $m$개 입력 벡터에 대해서 아래와 같이 정의됩니다.

$$ \text{minimize}_{a^{(j)}_i,\mathbf{\phi}_{i}} \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i) $$

여기서 $S(\dot)$는 스파시티 비용 함수로 계수 $a_i$가 0으로부터 멀면 페널라이즈 하는 항입니다. 첫번째 항은 알고리즘이 벡터 $\mathbf{x}$ 잘 표현하도록 의도하는 복원 항으로 사용되었고, 두번째 항은 스파시티 페널티 항으로 표현 $\mathbf{x}$의 표현이 스파스하도록 하는 항입니다. $\lambda$는 두 항의 상대적인 중요도를 정의하는 스케일 상수입니다.

스파시티의 직접적인 측정법으로 $L_0$ norm $S(a_i) = \mathbf{1}(|a_i|>0)$이 있지만 이는 미분이 불가능하고 최적화하기가 힘이 듭니다. 따라서 스파시티의 비용 $S(\dot)$을 측저하기 위한 일반적인 선택은 $L_1$ 페널티 $S(a_i) = |a_i|_1$를 사용하고 여기에 로그 패널티 $S(a_i)=\log(1+a_i^2)$를 사용합니다.

추가적으로 $a_i$를 스케일 다운된 값이 나오고, $\phi_i$가 스케일링 업 되어 페널티가 임의로 작게 나올 수도 있습니다.이를 방지하기 위해 $||\phi||^2$를 어떤 상수 $C$보다 적도록 제한하는 방법을 사용할 수 있습니다.

이제 전체 스파스 코딩의 비용 함수는 $\phi$의 조건을 포함하여 아래와 같습니다.

$$ \begin{array}{rc} \text{minimize}_{a^{(j)}_i,\mathbf{\phi}_{i}} & \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i) \\ \text{subject to} & \left|\left|\mathbf{\phi}_i\right|\right|^2 \leq C, \forall i = 1,...,k \\ \end{array}$$

Probabilistic Interpretation

지금까지 스파스 코딩을 입력 공간을 스팬하는 스파스하고 과적합된 기저 집합을 찾는 관점에서 살펴보았습니다. 다른 방법으로는 생성적 모델(generative model)의 확률적인 관점(probabilistic perspective)에서 스파스 코딩을 생각해볼 수 있습니다.

보통 이미지를 $k$개의 독립적인 소스 특징 $\phi_i$들의 선형 누적과 여기에 추가되는 노이즈로 모델링하는 문제를 생각해봅시다.

$$ \mathbf{x} = \sum_{i=1}^k a_i \mathbf{\phi}_{i} + \nu(\mathbf{x}) $$

우리 목표는 기저 특징 벡터 $\phi$가 이미지의 분포 확률 $P(\mathbf{x}\mid\mathbf{\phi})$ 입력 데이터의 경험적인 분포(empirical distribution) $P^*(\mathbf{x})$에 가까이 가도록 하는 집합을 찾는 것입니다. 이렇게 되는 한가지 방법은 $P^*(\mathbf{x})$과 $P(\mathbf{x}|\phi)$ 사이의 KL divergence를 최소화하는 것입니다. KL divergence는 아래와 같이 정의됩니다.

$$ D(P^*(\mathbf{x})||P(\mathbf{x}\mid\mathbf{\phi})) = \int P^*(\mathbf{x}) \log \left(\frac{P^*(\mathbf{x})}{P(\mathbf{x}\mid\mathbf{\phi})}\right)d\mathbf{x} $$

경험적 분포 $P^*(\mathbf{x})$는 우리가 $\phi$를 어떻게 선택하느냐에 따라 일정한 값을 가지기 때문에 이것은 $P(\mathbf{x}|\phi)$의 log-likelihood를 최대화 하는 것과 동일합니다.

$\nu$가 분산 $\sigma^2$를 갖는 가우시안 화이트 노이즈라고 가정하면 아래를 얻을 수 있습니다.

$$ P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) = \frac{1}{Z} \exp\left(- \frac{(\mathbf{x}-\sum^{k}_{i=1} a_i \mathbf{\phi}_{i})^2}{2\sigma^2}\right) $$

분포 $P(\mathbf{x}\mid\mathbf{\phi})$를 결정하기 위해서는 사전 분포 $P(\mathbf{a})$또한 정의되어야 합니다. 입력된 특징들이 서로 독립적이라고 가정한다면, 우리의 사전 분포를 분해(factorize)할 수 있습니다.

$$ P(\mathbf{a}) = \prod_{i=1}^{k} P(a_i) $$

여기에서 스파시티 가정을 적용하고자 합니다. 그 가정이란 어떤 한 이미지는 상대적으로 적은 소스 특징들의 곱으로 나타낼 수 있다는 가정입니다. 따라서 우리는 $a_i$의 확률 분포가 0인 지점에서 피크이고 높은 첨도를 갖기를 원합니다. 이러한 사전 분포를 편리하게 모델링하기 위해 다음과 같이 파라미터를 사용합니다.

$$ P(a_i) = \frac{1}{Z}\exp(-\beta S(a_i)) $$

여기서 $S(a_i)$는 사전 분포의 모양을 결정하는 함수입니다.

이제 $ P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi})$과 $P(\mathbf{a})$를 정의되엇으니, $\phi$를 이용한 모델에서 데이터 $\mathbf{x}$의 확률을 정의할 수 있습니다.

$$ P(\mathbf{x} \mid \mathbf{\phi}) = \int P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) P(\mathbf{a}) d\mathbf{a} $$

그리고 우리가 원하는 $\phi$를 찾으려면 이 문제를 아래와 같이 축소시킬 수 있습니다.

$$ \mathbf{\phi}^*=\text{argmax}_{\mathbf{\phi}} E\left[ \log(P(\mathbf{x} \mid \mathbf{\phi})) \right]
$$

여기서 $E\left[ \cdot \right]$는 입력 데이터에 대한 기대값입니다.

아쉽게도 $P(\mathbf{x} \mid \mathbf{\phi})$를 얻기 위해서 $\mathbf{a}$에 대해 적분하는 것은 일반적으로 쉽지 않습니다. 만약 $P(\mathbf{x} \mid \mathbf{\phi})$의 분포가 $\mathbf{a}$에 대해서 충분히 뾰족하다면, $P(\mathbf{x} \mid \mathbf{\phi})$의 최대 값으로 그것의 적분의 근사값으로 이용할 수 있습니다.

$$ \mathbf{\phi}^{*'}=\text{argmax}_{\mathbf{\phi}} E\left[ \max_{\mathbf{a}} \log(P(\mathbf{x} \mid \mathbf{\phi})) \right] $$

이전에 우리가 $a_i$의 스케일을 낮추고 $\phi$의 스케일을 올려서 추정한 확률 값을 증가시킨 것과 같이, $가근처에서피크이므로제한조건을우리의특징P(a_i)가 0 근처에서 피크이므로 norm 제한 조건을 우리의 특징 $\phi$에 걸어서 이를 막을 것입니다.

최종적으로 우리의 원래 코스트 함수를 선형 생성적 모델의 에너지 함수를 통해 정의할 수 있습니다.

$$ \begin{array}{rl} E\left( \mathbf{x} , \mathbf{a} \mid \mathbf{\phi} \right) & := -\log \left( P(\mathbf{x}\mid \mathbf{\phi},\mathbf{a}\right)P(\mathbf{a})) \\ &= \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i) \end{array} $$

$ \lambda = 2\sigma^2\beta$이고, 관계없는 상수는 생략하였습니다. Log-likelihood의 최대화는 네어지 함수를 최소화하는 것과 동일하기 때문에 원래의 최적화 문제를 다음과 같이 변화시켰습니다.

$$ \mathbf{\phi}^{*},\mathbf{a}^{*}=\text{argmin}_{\mathbf{\phi},\mathbf{a}} \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i) $$

확률적 접근을 이용해서 $L_1$ 페널티 $|a_i|_1$과 $S(\dot)$의 로그 페널티 $\log(1+a_i^2)$는 라플라시안 $P(a_i) \propto \exp\left(-\beta|a_i|\right)$과 Cauchy 사전 확률 $P(a_i) \propto \frac{\beta}{1+a_i^2}$를 사용하는 것에 해당한다는 것을 볼 수 있었습니다.

Learning

학습은 기저 벡터들 $\phi$를 2개의 분리된 최적화로 구성된 스파스 코딩을 이용합니다. 첫번째는 각 트레이닝 데이터 $\mathbf{x}$에 대해서 계수 $a_i$에 대한 최적화를 하는 것이고, 두번째는 기저 벡터들 $\phi$을 트레이닝 데이터들에 대해서 최적화 하는 것입니다.

$L_1$ 스파시티 페널티를 가정하면, $a^{(j)}_i$를 학습하는 것은 $L_1$으로 레귤러라이즈된, $a^{(j)}_i$에서 컨벡스한 Least Sqaure 문제로 줄여집니다. 또한 이를 위한 여러 테크닉들이 만들어져 있습니다. CVS와 같은 컨벡스 최적화 소프트웨어를 이러한 L1 레귤러라이즈된 Least Square를 푸는데 사용할 수 있습니다. 만약 $S(\dot)$가 log 페널티처럼 미분가능하다고 한다면 conjugate gradient와 같은 그래디언트 기반의 방법 또한 사용할 수 있습니다.

$L_2$ norm 제한요건을 이용하여 기저 벡터들을 학습하는 것 또한, $\phi$에 대해서 컨벡스하다는 quadratic 제한을 가진 Least square 문제로 줄여집니다. CVX같은 표준 컨벡스 최적화 소프트웨어나 다른 반복적 방법들로 이 문제를 풀 수 있습니다. 하지만 Lagrange dual 문제를 푸는 더 효과적인 방법들도 개발되어있습니다.

위에서 설명한 것에 따라 기저 벡터들을 학습을 마쳤더라도 새로운 데이터 샘플을 인코드하기 위해서는 새로운 계수들을 얻기위해 최적화 과정이 수행되어야 한다는 한계가 있습니다. 이러한 "런타임" 코스트는 스파스 코딩이 기존의 피드포워드 구조에 비해서 테스트 시간에도 계산적으로 비싸다는 것을 의미합니다.


Tags:
Add a Comment Trackback