13. Sparse linear models

13.1. Introduction

출력과 상호 정보량이 큰 입력 변수들을 선택하는 여러 방법의 단점은 한 번에 한 개의 변수만 보는 국소적 접근법이어서 입력 변수간 상호작용을 포착할 수 없다는 것이다. 이에 대한 대안으로 한 번에 여러 개의 변수를 포착하는 모델 기반 접근법을 세울 수 있다. 어떤 연결 함수 f에 대해 일반화된 선형 모델 p(y | \mathbf{x}) = p(y | f(\mathbf{w}^{T} \mathbf{x})로 모델링된다면 가중치 벡터 \mathbf{w}희소 벡터, 즉 0이 많은 벡터로 만들어서 특성 선택을 할 수 있다. 다음의 용례들이 있다.

  • 학습 데이터 수 N이 작고 특성 차원수 D가 클 때 출력을 잘 예측할 수 있는 특성들의 집합을 선택할 때
  • 학습 데이터에 기반해 커널 함수를 적용시킨 기저 함수들에서 특성 선택을 할 때
  • 신호의 기저 함수에 대한 희소 표현을 찾을 때

13.2. Bayesian variable selection

변수를 선택하는 가장 자연스러운 방법은 다음과 같다. \gamma_{j}가 특성 j가 관련이 있다면 1, 없으면 0이 되는 변수라 할 때 목적은 비용함수 f(\mathbf{\gamma}) = -[\log p(\mathcal{D} | \mathbf{\gamma}) + \log p(\mathbf{\gamma})]가 있을 때 모델에 대한 사후분포 p(\mathbf{\gamma} | \mathcal{D}) = \frac{e^{-f(\mathbf{\gamma})}}{\sum_{\mathbf{\gamma}^{\prime}} e^{-f(\mathbf{\gamma}^{\prime})}} 을 계산하는 것이다. 용례는 각각의 이진 특성에 대한 모든 경우의 수를 그레이 코드 순으로 나열한 뒤 이 모델에 대한 사후분포를 계산해 최대 사후분포를 갖는 모델, 즉 최대사후확률추정 \hat{\mathbf{\gamma}} = \mathrm{argmax}p(\mathbf{\gamma} | \mathcal{D})을 찾는 것이다.

모든 비트 패턴의 나열 / 모델별 점수 함수 / 사후분포 / 주변포함확률분포.

또는 사후 주변 포함 확률 p(\gamma_{j} = 1 | \mathcal{D})을 이용해 중위값 모델 \hat{\mathbf{\gamma}} = \{ j : p(\gamma_{j} = 1 | \mathcal{D}) > 0.5\}을 찾을 수도 있다. 변수 선택은 차원수가 클 때 가장 유용하다. 이 때 사후분포와 최대사후확률추정을 완전히 계산하는 것은 거의 불가능하므로 더 빠른 알고리즘을 여러 방법으로 찾아볼 것이다.

13.2.1. The spike and slab model

사후분포 p(\mathbf{\gamma} | \mathcal{D}) \propto p(\mathbf{\gamma})p(\mathcal{D} | \mathbf{\gamma})을 계산하기 위해 사전분포와 가능도를 계산해보자.

비트 벡터에 대한 사전분포는 \lVert \mathbf{\gamma} \rVert_{0} = \sum_{j=1}^{D} \gamma_{j}l_{0} 유사 놈이고 \pi_{0}을 특성이 관련 있을 확률이라 할 때 p(\mathbf{\gamma}) = \prod_{j=1}^{D} \mathrm{Ber}(\gamma_{j} | \pi_{0}) = \pi_{0}^{\lVert \mathbf{\gamma} \rVert_{0}} (1 -\pi_{0})^{D - \lVert \mathbf{\gamma} \rVert_{0}}으로 잡을 수 있다. 이 때 로그 사전확률은 \lambda = \log \frac{1 - \pi_{0}}{\pi_{0}}일 때 \log p(\mathbf{\gamma} | \pi_{0}) = - \lambda \lVert \mathbf{\gamma} \rVert_{0} + \mathrm{const}가 된다.

가능도는 다음과 같이 쓸 수 있다: p(\mathcal{D} | \mathbf{\gamma}) = p(\mathbf{y} | \mathbf{X}, \mathbf{\gamma}) = \int \int p(\mathbf{y} | \mathbf{X}, \mathbf{w}, \mathbf{\gamma}) p(\mathbf{w} | \mathbf{\gamma}, \sigma^{2}) p(\sigma^{2}) d \mathbf{w} d \sigma^{2}

여기서 간략함을 위해 일반성을 잃지 않고 출력 변수의 평균은 0으로 가정한다. 가중치의 사전분포 p(w_{j}| \gamma_{j}, \sigma^{2})는 특성이 관계가 없을 때에는 w_{j} = 0으로 기대되므로 \delta_{0}(w_{j})를 쓰는 것이 좋을 것이다. 특성이 관계가 있을 때에는 \mathcal{N}(0, \sigma^{2} \sigma_{w}^{2})를 쓰는 것이 좋을 것이다. 이 분포는 0에서 치솟게 되고 \sigma_{w}^{2} \to \infty일 수록 균등 분포에 가까워지는 못과 판자 모델이 된다. 즉 사전분포에 의해 \gamma_{j} = 0인 변수에 대해서는 w_{j} = 0으로 유도되므로 이 변수들을 빼내면, 가우시안 가능도를 가정했을 때 전체 가능도는

p(\mathcal{D} | \mathbf{\gamma}) = \int \int p(\mathbf{y} | \mathbf{X}_{\mathbf{\gamma}} \mathbf{w}_{\mathbf{\gamma}}, \sigma^{2} \mathbf{I}_{N}) p(\mathbf{w}_{\mathbf{\gamma}} | \mathbf{0}_{\mathbf{\gamma}}, \sigma^{2}\sigma_{w}^{2} \mathbf{I}_{\mathbf{\gamma}}) p(\sigma^{2}) d \mathbf{w}_{\mathbf{\gamma}} d \sigma^{2}

가 된다. 여기서 \mathbf{X}_{\mathbf{\gamma}}\mathbf{w}_{\mathbf{\gamma}}\gamma_{j} = 1인 행들만 선택한 것이고, \mathbf{0}_{\mathbf{\gamma}}, \mathbf{I}_{\mathbf{\gamma}}\gamma_{j} = 0인 행들만 선택한 것이다. 이로부터 가중치 사전분포를 임의의 양의 정부호 행렬 \mathbf{\Sigma}_{\mathbf{\gamma}}에 대해 p(\mathbf{w} | \mathbf{\gamma}, \sigma^{2}) = \mathcal{N}(\mathbf{w}_{\mathbf{\gamma}} | \mathbf{0}_{\mathbf{\gamma}}, \sigma^{2} \mathbf{\Sigma}_{\mathbf{\gamma}})로 일반화시킬 수 있다.

이제 주변가능도를 계산할 수 있다. 노이즈 분산이 아는 값이라면, 주변가능도는 다음과 같아진다: p(\mathcal{D} | \mathbf{\gamma}, \sigma^{2}) = \int p(\mathbf{y} | \mathbf{X}_{\mathbf{\gamma}} \mathbf{w}_{\mathbf{\gamma}}, \sigma^{2} \mathbf{I}) p(\mathbf{w}_{\mathbf{\gamma}} | \mathbf{0}_{\mathbf{\gamma}}, \sigma^{2}\mathbf{\Sigma}_{\mathbf{\gamma}}) d \mathbf{w}_{\mathbf{\gamma}} = \mathcal{N}(\mathbf{y} | \mathbf{0}, \mathbf{C}_{\mathbf{\gamma}}) , \mathbf{C}_{\mathbf{\gamma}} = \sigma^{2} \mathbf{X}_{\mathbf{\gamma}} \mathbf{\Sigma}_{\mathbf{\gamma}} \mathbf{X}_{\mathbf{\gamma}}^{T} + \sigma^{2} \mathbf{I}_{N}.

노이즈 분산을 모른다면 사전분포를 적용한 뒤 그를 적분해 빼낸다. p(\sigma^{2}) = \mathrm{IG}(\sigma^{2} | a_{\sigma}, b_{\sigma}), 또는 여기에 a = b = 0을 적용해 p(\sigma^{2}) \propto \sigma^{-2}를 적용한다. p(\mathcal{D} | \mathbf{\gamma}, \sigma^{2}) = \int \int p(\mathbf{y} | \mathbf{X}_{\mathbf{\gamma}} \mathbf{w}_{\mathbf{\gamma}}, \sigma^{2} \mathbf{I}) p(\mathbf{w}_{\mathbf{\gamma}} | \mathbf{0}_{\mathbf{\gamma}}, \sigma^{2}\mathbf{\Sigma}_{\mathbf{\gamma}}) p(\sigma^{2}) d \mathbf{w}_{\mathbf{\gamma}} d \sigma^{2} \propto  \lvert \mathbf{X}_{\mathbf{\gamma}}^{T}\mathbf{X}_{\mathbf{\gamma}} + \mathbf{\Sigma}_{\mathbf{\gamma}}^{-1} \rvert^{-\frac{1}{2}} \lvert \mathbf{\Sigma}_{\mathbf{\gamma}}\rvert^{-\frac{1}{2}} (2 b_{\sigma} + S(\mathbf{\gamma}))^{-\frac{2 a_{\sigma} + N - 1}{2}}, S(\mathbf{\gamma}) = \mathbf{y}^{T} \mathbf{y} - \mathbf{y}^{T} \mathbf{X}_{\mathbf{\gamma}}(\mathbf{X}_{\mathbf{\gamma}}^{T}\mathbf{X}_{\mathbf{\gamma}} + \mathbf{\Sigma}_{\mathbf{\gamma}}^{-1})^{-1} \mathbf{X}_{\mathbf{\gamma}}^{T} \mathbf{y}

가우시안 가능도가 아닌 로지스틱 회귀 같은 경우에는 주변가능도가 닫힌 형태로 계산될 수 없으므로 BIC 근사를 이용한다.

\log p(\mathcal{D} | \mathbf{\gamma}) \simeq \log p(\mathbf{y} | \mathbf{X}, \hat{\mathbf{w}}_{\mathbf{\gamma}}, \hat{\sigma}^{2}) - \frac{\lVert \mathbf{\gamma} \rVert_{0}}{2} \log N

이 때 \hat{\mathbf{w}}_{\mathbf{\gamma}}는 최대사후확률추정, \lVert \mathbf{\gamma} \rVert_{0}은 모델의 자유도이다. 로그 사전확률을 더하면 전체 사후확률은 다음과 같다.

\log p(\mathcal{D} | \mathbf{\gamma}) \simeq \log p(\mathbf{y} | \mathbf{X}, \hat{\mathbf{w}}_{\mathbf{\gamma}}, \hat{\sigma}^{2}) - \frac{\lVert \mathbf{\gamma} \rVert_{0}}{2} \log N - \lambda \lVert \mathbf{\gamma} \rVert_{0} + \mathrm{const}

이 모델에서는 BIC 근사와 사전분포 이렇게 2개의 징벌 항이 존재한다.

13.2.2. From the Bernoulli-Gaussian model to l_{0} regularization

종종 사용되는 다른 모델은 다음과 같은 베르누이-가우시안, 또는 이진 마스크 모델이다.

y_{i} | \mathbf{x}_{i}, \mathbf{w}_{i}, \mathbf{\gamma}, \sigma^{2} \sim \mathcal{N}(\sum_{j} \gamma_{j} w_{j} w_{ij}, \sigma^{2}), \gamma_{j} \sim \mathrm{Ber}(\pi_{0}), w_{j} \sim \mathcal{N}(0, \sigma_{w}^{2})

이는 못과 판자 모델과 다르게 상관 없는 계수들을 적분해 빼내지 않는다. 또한, 못과 판자 모델은 \gamma_{j} \to w_{j} \to \mathbf{y}의 관계인 반면 이진 마스크 모델은 \gamma_{j} \to \mathbf{y} \leftarrow w_{j}의 관계로, 가능도로부터는 \gamma_{j}w_{j}만 추론이 가능하다.

이 모델의 흥미로운 점은 비-베이지안적 부분집합 선택에 쓰이는 목적 함수도 유도할 수 있다는 것이다. 결합 사전분포는 p(\mathbf{\gamma}, \mathbf{w}) \propto \mathcal{N}(\mathbf{w} | \mathbf{0}, \sigma_{w}^{2} \mathbf{I}) \pi_{0}^{\lVert \mathbf{\gamma} \rVert_{0}} (1 - \pi_{0})^{D - \lVert \mathbf{\gamma} \rVert_{0}}의 형태를 가지므로, 음의 로그사후확률은 f(\mathbf{\gamma}, \mathbf{w}) = -2 \sigma^{2} \log p(\mathbf{\gamma}, \mathbf{w}, \mathbf{y} | \mathbf{X}) = \lVert \mathbf{y} - \mathbf{X}_{\mathbf{\gamma}} \mathbf{w}_{\mathbf{\gamma}} \rVert^{2} + \frac{\sigma^{2}}{\sigma_{w}^{2}} \lVert \mathbf{w} \rVert^{2} + \lambda \lVert \mathbf{\gamma} \rVert_{0} + \mathrm{const} , \lambda = 2 \sigma^{2} \log \frac{1 - \pi_{0}}{\pi_{0}}이 된다. 이 때 \mathbf{w}\mathbf{\gamma}가 0인 부분과 0이 아닌 부분으로 나눈다면 0인 부분 \mathbf{w}_{-\mathbf{\gamma}} = \mathbf{0}으로 놓을 수 있다.

이 때 \sigma_{w}^{2} \to \infty, 즉 0이 아닌 가중치를 정규화하지 않을 때에는 목적 함수는 f(\mathbf{\gamma}, \mathbf{w}) = \lVert \mathbf{y} - \mathbf{X}_{\mathbf{\gamma}} \mathbf{w}_{\mathbf{\gamma}} \rVert_{2}^{2} + \lambda \lVert \mathbf{\gamma} \rVert_{0} 가 된다.

비트 벡터를 추적하는 대신 연관된 변수를 \mathbf{w}지지집합 위에서만 정의할 수 있다. 그렇게 되면 f(\mathbf{w}) = \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2} + \lambda \lVert \mathbf{w} \rVert_{0} 이 되는데, 이를 l_{0} 정규화라 한다. 이 목적 함수는 매끄러운 함수가 아니기 때문에 최적화하기 힘든데 이의 해법은 뒤에 다룬다.

13.2.3. Algorithms

모델의 수가 2^{D}개나 되므로 사후 분포를 정확히 구하거나 전역 최적해를 구하기는 어렵다. 대신에 모델을 피팅하거나 – \mathrm{argmax} p(\mathcal{D} | \mathbf{w})를 구하거나 – 주변가능도를 구하거나 – \int p(\mathcal{D} | \mathbf{w}) p(\mathbf{w}) d \mathbf{w} 을 구하거나 – 하는 휴리스틱한 방법을 쓴다. 이를 래퍼 방법이라 한다. 래퍼 방법을 쓸 때에는 이전 모델의 점수를 알고 있는 상태에서 다른 새로운 모델의 점수를 빠르게 계산할 수 있는지가 효율성의 핵심이 된다. 이것은 모델의 점수 함수를 계산하기 위한 충족 통계량이 업데이트의 형태로 변화될 수 있으면 된다. 보통 이것은 \mathbf{\gamma}^{\prime}\mathbf{\gamma}의 차이가 1비트이면서 f(\mathbf{\gamma})가 오로지 \mathbf{X}_{\mathbf{\gamma}}에 의존할 때에만 가능하다. 이 경우에는 \mathbf{X}_{\mathbf{\gamma}}^{T}\mathbf{X}_{\mathbf{\gamma}}에서 랭크 1 업데이트를 수행해 \mathbf{X}_{\mathbf{\gamma}^{\prime}}^{T} \mathbf{X}_{\mathbf{\gamma}^{\prime}}을 얻으며, 보통 QR 분해를 이용한다.

13.2.3.1. Greedy search

최대사후확률추정 모델을 찾고자 한다고 하자. l_{0}-정규화된 목적 함수를 쓴다면 최소 제곱법의 다양한 특성을 이용할 수 있다.

  • 단일 최적 치환 : 각 단계에서 현재 모델의 근방을 그 모델에서 1비트만 바꾼 모델의 집합으로 정의한 뒤 그 중 최적의 치환을 수행한다. 희소 모델을 구하고 있으므로 시작점은 \mathbf{\gamma} = \mathbf{0}이다. 더 이상 개선이 가능하지 않을 때까지 반복한다.
  • 직교 최소 제곱법 : \lambda = 0으로 두면 복잡도 징벌이 없으므로 모델에서 인자 삭제를 할 필요가 없다. 이 경우에는 단일 최적 치환 방법이 직교 최소 제곱법, 즉 탐욕 전방 선택법과 동치가 된다. 즉 각 단계에서 현재 모델의 근방을 그 모델에서 1비트만 추가한 모델의 집합으로 정의한 뒤 그 중 최적의 치환을 단계적으로 수행한다. 현재 특성 \mathbf{\gamma}_{t}에서 더해지는 새 특성 j^{\ast}j^{\ast} = \mathrm{argmin}_{j \notin \mathbf{\gamma}_{t}} \min_{\mathbf{w}} \lVert \mathbf{y} - (\mathbf{X}_{\mathbf{\gamma}_{t} \cup j})\mathbf{w} \rVert^{2}을 구한 뒤 이를 현재 특성 집합에 더한다. 이는 D - D_{t} 차원의 최소 제곱 문제를 푸는 것과 같다.
  • 직교 매칭 추적(OMP) : 직교 최소 제곱법은 비싸기 때문에 현재의 가중치를 고정시킨 뒤 다음의 j^{\ast} = \mathrm{argmin}_{j \notin \mathbf{\gamma}_{t}} \min_{\beta} \lVert \mathbf{y} - \mathbf{X} \mathbf{w}_{t} - \beta \mathbf{x}_{: j} \rVert^{2} 문제를 푸는 것을 생각할 수 있다. 이 때 최적해 \beta = \frac{\mathbf{x}_{:j}^{T} \mathbf{r}_{t}}{\lVert \mathbf{x}_{: j}\rVert^{2}}, \mathbf{r}_{t} = \mathbf{y} - \mathbf{X}\mathbf{w}_{t}이 된다. 행벡터가 단위 길이를 갖는다면 j^{\ast} = \mathrm{argmax} \mathbf{x}_{: j}^{T} \mathbf{r}_{t}가 되므로, 현재 나머지 벡터와 가장 상호 연관된 행벡터를 찾기만 하면 된다. 이는 한 반복 시마다 1개의 최소 제곱 문제만 풀기 때문에 더 빠르지만 정확도는 더 떨어진다.
  • 매칭 추적 : 현재 나머지 벡터와 가장 상호 연관된 특성 벡터를 계속 더하기만 하는 방법이 있는데, 이는 최소 제곱 부스팅과 본질적으로 같다.
  • 후방 선택 : 모든 변수가 모델에 존재하고 (포화 모델) 각 단계마다 최악의 변수를 하나씩 지워가는 방법이 있다. 이는 상황에 따라 변수가 하나도 없는 상태에서 각 단게마다 최적의 변수를 하나씩 추가하는 전방 선택법보다 유용할 수 있다. 하지만 대규모의 문제에서는 포화 모델을 피팅하기가 힘들기 때문에 적용하기 어렵다.
  • 전방-후방 알고리즘(FoBa) : 단일 최적 치환법과 비슷하지만, 각 단계마다 직교 매칭 추적 알고리즘을 사용한다.
  • 베이지안 매칭 추적 : 직교 매칭 추적과 비슷하지만, 최소 제곱 목적 함수 대신 베이지안 주변가능도 기준 점수를 사용한다.
직교 최소 제곱법에 따른 부분집합 크기/잔여 오차 플롯.

13.2.3.2. Stochastic search

사후확률을 근사할 때에는 최빈값을 단순히 찾기보다는 마르코프 연쇄 몬테 카를로법을 쓸 수 있다. 일반적인 방법은 메트로폴리스 헤이스팅스, 즉 분포에서 한 번에 한 개의 비트만 뒤집어서 p(\mathbf{\gamma} | \mathcal{D})에서 p(\mathbf{\gamma}^{\prime} | \mathcal{D})을 용이하게 계산하는 것이다. 하지만 잇나적인 상태 공간에서는 상태의 확률을 그냥 p(\mathbf{\gamma}, \mathcal{D}) = e^{-f(\mathbf{\gamma})}로 계산하면 되므로 상태를 재방문할 필요가 없게 되어 마르코프 연쇄 몬테 카를로 법은 비효율적이다. 이 때는 고득점 모델의 집합 \mathcal{S}를 만든 뒤에 근사 p(\mathbf{\gamma} | \mathcal{D}) \simeq \frac{e^{-f(\mathbf{\gamma})}}{\sum_{\mathbf{\gamma}^{\prime} \in \mathcal{S}} e^{-f(\mathbf{\gamma}^{\prime})}} 을 사용한다.

13.2.3.3. EM and variational inference

못과 판자 모델에서 기대값 최대화 방법은 직접 적용하기에는 부적합하다. 왜냐하면 p(\gamma_{j} = 1 | w_{j})를 계산할 때에는 델타 함수와 가우시안 함수를 비교해야 하기 때문이고, 델타 함수를 좁은 가우시안으로 대체하더라도 이는 국소적 해로 빠지기 쉽기 때문이다.

그 대신에 기대값 최대화 방법은 베르누이-가우시안 모델에 적용할 수 있다. 이 경우 p(\mathbf{\gamma} | \mathcal{D}, \mathbf{w})는 직접 계산할 수 없지만 (모든 비트가 상호 연관되어 있기 때문에) 평균 필드 근사 \prod_{j} q(\gamma_{j}) q(w_{j})의 꼴로 근사할 수는 있다.

13.3. l_{1} regularization: basics

변수가 여러 개면 p(\mathrm{\gamma} | \mathcal{D})의 사후최빈값을 찾기 힘들어진다. 다른 탐욕적 알고리즘은 잘 동작하기는 하지만 국소적 최적해에 빠질 수 있다. 이 문제의 원인 중 하나는 \gamma_{j}가 이산적이기 때문인데 이에 대응해서 이산적인 변수를 연속적인 변수로 근사하는 작업을 한다. 못과 판자 모델을 근사하기 위해서는 라플라스 분포를 이용하는데 라플라스 분포는 원점에 많은 확률질량이 몰려 있는 함수이기 때문이다.

p(\mathbf{w} | \lambda) = \prod_{j=1}^{D} \mathrm{Lap}(w_{j} | 0, \frac{1}{\lambda}) \propto \prod_{j=1}^{D} e^{-\lambda \lvert w_{j} \rvert} 의 사전분포를 생각하자. 이 때 오프셋에 대한 사전분포는 p(w_{0}) \propto 1을 쓴다. 이 때 최대사후확률추정을 구하기 위해 징벌된 음의 로그가능도를 구해 보면 f(\mathbf{w}) = -\log p(\mathcal{D} | \mathbf{w}) - \log p(\mathbf{w} | \lambda) = \mathrm{NLL}(\mathbf{w}) + \lambda \lVert \mathbf{w} \rVert_{1}이 된다 (여기서 \lVert \rVert_{1}l_{1} 놈). 이 때 \lambda가 커지면 추정 가중치 \hat{\mathbf{w}}는 희소 벡터가 된다. 이는 비볼록 목적 함수에 대한 볼록함수 근사라고 볼 수 있다.

선형 회귀의 경우엔 이 l_{1} 목적 함수는 f(\mathbf{w}) = \sum_{i=1}^{N} -\frac{1}{2 \sigma^{2}} (y_{i} - (w_{0} + \mathbf{w}^{T} \mathbf{x}_{i}))^{2} + \lambda \lVert \mathbf{w} \rVert_{1} = \mathrm{RSS}(\mathbf{w}) + 2 \lambda \sigma^{2} \lVert \mathbf{w} \rVert_{1} 이 된다. 이를 기저 추적 잡음 제어(BPDN)라 하며 평균이 0인 라플라스 사전분포를 더하고 최대사후확률추정을 수행하는 것을 l_{1} 정규화라 한다. 이는 임의의 볼록 또는 비볼록 음의 로그가능도 항에 적용될 수 있다.

13.3.1. Why does l_{1} regularization yield sparse solutions?

l_{2} 정규화는 희소 추정값을 유도하지 않지만 l_{1} 정규화는 유도하는가? 선형 회귀의 예에 대해 알아보자. (로지스틱 회귀나 다른 일반적 선형 모델에 대해서도 성립한다)

기저 추적 잡음 제어 목적 함수는 다음의 매끄럽지 않은 목적 함수이다: \min_{\mathbf{w}} \mathrm{RSS}(\mathbf{w}) + \lambda \lVert \mathbf{w} \rVert_{1} 이는 매끄러운 함수 \min_{\mathbf{w}} \mathrm{RSS}(\mathbf{w})\lVert \mathbf{w} \rVert_{1} \leq B라는 제한을 걸어 최적화하는 것과 같다. 이 때 B는 가중치의 l_{1} 놈의 상한이다. 큰 B값은 작은 \lambda 값에 대응하며 작은 B값은 큰 \lambda값에 대응할 것이다. 이를 라쏘(최소 절대 수축 선택 연산자) 방정식이라 한다.

유사하게, 능선 회귀 \min_{\mathbf{w}} \mathrm{RSS}(\mathbf{w}) + \lambda \lVert \mathbf{w} \rVert_{2}^{2}\min_{\mathbf{w}} \mathrm{RSS}(\mathbf{w})\lVert \mathbf{w} \rVert_{2}^{2} \leq B라는 제한을 걸어 최적화하는 것과 같다.

위 두 문제를 비교하면 최적해는 제한 조건면과 목적 함수의 접점에서 발생하는데, l_{1} 정규화는 제한 조건면이 마름모 꼴이므로 코너에서 접점이 발생할 확률이 훨씬 높은 반면 l_{2} 정규화는 제한 조건면이 구면이므로 코너가 존재하지 않는다. 따라서 l_{1} 정규화는 희소 최적해를 가질 확률이 높지만 l_{2}는 그렇지 않은 것이다.

13.3.2. Optimality condition for lasso

라쏘 목적 함수 \min_{\mathbf{w}} \mathrm{RSS}(\mathbf{w}) + \lambda \lVert \mathbf{w} \rVert_{1}의 두 번째 항은 w_{j} = 0일 때 미분가능하지 않으므로 이것은 매끄럽지 않은 최적화 문제이다. 이를 다루기 위해서는 도함수를 부분도함수 또는 부분경사로 확장하는데 \mathcal{I}\theta_{0}을 포함하는 구간이라 할 때 f : \mathcal{I} \to \mathbb{R}\theta_{0}에서의 부분도함수는 f(\theta) - f(\theta_{0}) \geq g(\theta - \theta_{0}) \forall \theta \in \mathcal{I}를 만족하는 스칼라 g이다. 이 때 부분도함수의 집합은 좌극한 a = \lim_{\theta \to \theta_{0}^{-}} \frac{f(\theta) - f(\theta_{0})}{\theta - \theta_{0}}과 우극한 b = \lim_{\theta \to \theta_{0}^{+}} \frac{f(\theta) - f(\theta_{0})}{\theta - \theta_{0}}의 구간 [a, b]로 정의된다. 이를 f의 \theta_{0}에서의 부분미분이라 하며 \partial f(\theta)|_{\theta_{0}}이 된다. f가 미분가능하면 부분미분은 도함수의 값과 같으며, 어떤 지점에서 부분미분값이 0인 것은 그 지점에서 극소/극대값을 갖는 것과 동치인 것도 같다.

부분도함수의 예

이를 라쏘 문제에 적용해 보자. 먼저 매끄럽지 않은 항을 무시해 보면 \frac{\partial}{\partial w_{j}} \mathrm{RSS}(\mathbf{w}) = a_{j} w_{j} - c_{j}, a_{j} = 2 \sum_{i=1}^{n} x_{ij}^{2}, c_{j} = 2 \sum_{i=1}^{n} x_{ij} (y_{i} - \mathbf{w}_{-j}^{T} \mathbf{x}_{i, -j})이 되는데 (여기서 \mathbf{w}_{-j}, \mathbf{x}_{i, -j}는 j번째 축을 뺀 것) c_{j}는 j번째 특성 벡터와 다른 특성 벡터로서의 나머지값과의 상관 계수에 비례함을 알 수 있다. 따라서 c_{j}의 크기는 특성 j가 얼마나 \mathbf{y}를 예측하는 데 관련이 있는지를 나타내는 지표이다. (다른 특성들과 현재 매개변수들과 비교했을 때).

징벌 항을 더했을 때의 부분미분 \partial_{w_{j}} f(\mathbf{w})w_{j} < 0일 때 a_{j}w_{j} - c_{j} - \lambda, w_{j} = 0일 때 [-c_{j} - \lambda, -c_{j} + \lambda], w_{j} > 0일 때 a_{j}w_{j} - c_{j} + \lambda가 된다. 그러므로 \mathbf{w}가 극소값일 조건은 전미분이 w_{j} < 0일 때 - \lambda, w_{j} = 0일 때 [- \lambda, \lambda], w_{j} > 0일 때 \lambda가 되는 것이다. c_{j}의 값에 따라 \partial_{w_{j}} f(\mathbf{w}) = 0의 해는 w_{j}의 3개의 서로 다른 값에서 발생한다.

  • c_{j} < -\lambda이면 특성은 나머지와 강한 음의 상관 관계를 갖는다. 부분미분은 \hat{w}_{j} = \frac{c_{j} + \lambda}{a_{j}} < 0에서 0이 된다.
  • -\lambda \leq c_{j} \leq \lambda이면 특성은 나머지와 약한 상관 관계를 갖는다. 부분미분은 \hat{w}_{j} = 0에서 0이 된다.
  • c_{j} > \lambda이면 특성은 나머지와 강한 양의 상관 관계를 갖는다. 부분미분은 \hat{w}_{j} = \frac{c_{j} - \lambda}{a_{j}} > 0에서 0이 된다.

이는 \hat{w}_{j} = \mathrm{soft}(\frac{c_{j}}{a_{j}}; \frac{\lambda}{a_{j}}) = \mathrm{sign}(\frac{c_{j}}{a_{j}}) (\lvert \frac{c_{j}}{a_{j}}\rvert - \delta)_{+}로 요약할 수 있다. 이를 약한 경계화라 한다. 그와 반대로 \hat{w}_{j}의 바깥 구간에서의 값들을 수축시키지 않는 것을 강한 경계화라 하는데 이는 가중치의 추정값을 원점을 지나는 직선과 일치시키도록 해서 약한 경계화와는 달리 비편향 추정자를 만들기 위함이다.

여기서 라쏘라는 단어의 근원을 알 수 있는데 이는 변수의 부분집합을 선택하고 모든 계수의 절대값을 징벌하여 그를 수축시키기 때문이다. \lambda = 0인 경우에는 일반적인 최소 제곱해를 얻게 되고 \lambda_{\max} = \lVert \mathbf{X}^{T} \mathbf{y} \rVert_{\infty} = \max_{j} \lvert \mathbf{y}^{T} \mathbf{x}_{: ,j}\rvert 일 때 \lambda \geq \lambda_{\max}이면 \hat{\mathbf{w}} =\mathbf{0}이 된다. 이는 (\mathbf{X}^{T} \mathbf{y})_{j} \in [-\lambda, \lambda]일 때 \mathbf{0}이 최적값이 되기 때문이다. 일반적으로, l_{1} 정규화 목적 함수의 최대 징벌 계수는 \lambda_{\max} = \max_{j} \lvert \nabla_{j} \mathrm{NLL} (\mathbf{0}) \rvert이 된다.

13.3.3. Comparison of least squares, lasso, ridge and subset selection

최소 제곱법, 라쏘, 능선 회귀를 비교해 보자. 계산의 편의를 위해 \mathbf{X}의 모든 특성은 정규직교한다고 가정하자. 이 경우 잔여 제곱합은 \mathrm{RSS}(\mathbf{w}) = \lVert \mathbf{y} - \mathbf{X}\mathbf{w} \rVert^{2} = \mathbf{y}^{T} \mathbf{y} + \mathbf{w}^{T} \mathbf{X}^{T} \mathbf{X} \mathbf{w} - 2 \mathbf{w}^{T} \mathbf{X}^{T} \mathbf{y} = \mathrm{const} + \sum_{k} w_{k}^{2} - 2 \sum_{k} \sum_{i} w_{k} x_{ik} y_{i}가 된다. 즉 이 식은 차원수마다 하나씩의 항들의 합으로 쪼개진다. 따라서 해석적으로 최대사후확률추정과 최대가능도추정을 구할 수 있다.

  • 최대가능도추정은 일반 최소제곱해로, \hat{w}_{k, \mathrm{OLS}} = \mathbf{x}_{: k}^{T} \mathbf{y}이 된다. (여기서 \mathbf{x}_{: k}\mathbf{X}의 k번째 열) 이는 k번째 특성의 반응 벡터로의 정사영이다.
  • 능선 회귀 추정은 \hat{w}_{k, \mathrm{ridge}} = \frac{\hat{w}_{k, \mathrm{OLS}}}{1 + \lambda}이 된다.
  • 라쏘 추정은 \hat{w}_{k, \mathrm{lasso}} = \mathrm{sign}(\hat{w}_{k, \mathrm{OLS}}(\lvert \hat{w}_{k, \mathrm{OLS}} \rvert - \frac{\lambda}{2})이 되며, 약한 경계화에 대응된다.
  • 부분집합 선택으로 K개의 특성을 선택하면 매개변수 추정은 \mathrm{rank}(\lvert \hat{w}_{k, \mathrm{OLS}} \rvert) \leq K일 때 \hat{w}_{k, \mathrm{OLS}}와 같아지고, 이외의 경우에는 0이 된다. 이는 강한 경계화에 대응된다.

어떤 문제에 대해서는 라쏘 회귀가 능선 회귀보다 더 좋고 어떤 문제에 대해서는 능선 회귀가 라쏘 회귀보다 더 좋다. 실제로는 엘라스틱 넷과 같은 라쏘와 능선 회귀의 혼합법이 종종 최고의 효과를 낸다.

라쏘 선형 회귀의 예.

13.3.4. Regularization path

\lambda를 증가시키면 최적해 \hat{\mathbf{w}}(\lambda)는 희소성을 띄게 되지만 이 희소성이 단조증가하지는 않는다. 각 특성에 대해 \hat{w}_{j}(\lambda)\lambda간의 관계를 플로팅할 수 있는데 이를 정규화 경로라 한다. \lambda = \infty면, 즉 l_{1} 징벌 항의 상한 B가 0이 되면 모든 계수가 0이 되지만 \lambda가 유한하면 모든 계수는 0이 아닌 값이 되고 \lambda가 줄어들수록 계수의 크기는 증가한다. B가 증가함에 따라 계수들은 가동되지만 B가 0과 B_{\max} = \lVert \hat{\mathbf{w}}_{\mathrm{OLS}} \rVert_{1} 사이의 값이라면 해는 희소해진다.

이 때 정규화 경로의 해는 B에 대해 구간적으로 선형 함수가 되며, 이 구간의 구분지점들은 해석적으로 구해낼 수 있다. 이는 LARS 알고리즘, 즉 최소 각도 회귀 및 수축 알고리즘의 기반이 된다. LARS 알고리즘은 최소 제곱법과 비슷한 시간복잡도로 전체 정규화 경로를 구해낼 수 있다. 정확히는 O(\min(ND^{2}, DN^{2}))이다.

정규화 경로를 따라서 B를 0부터 B_{\max}까지 증가시키면, 모든 가중치가 0인 최적해부터 모든 가중치가 0이 아닌 최적해까지 탐색할 수 있지만, 라쏘 정규화로는 가능한 모든 부분집합 전체를 탐색할 수는 없다. D > N이면 최적해는 최대 N개의 변수만 가질 수 있기 때문에 최소 l_{1} 놈에 해당하는 최소 제곱 해에는 도달할 수가 없다. l_{2} 정규화자를 같이 쓰면 (이를 엘라스틱 넷이라 한다), 학습 데이터 수보다 많은 변수를 갖는 희소 최적해도 구할 수 있다. 이는 N과 D 사이의 크기를 가진 모델을 탐색할 수 있게 해 준다.

능선 정규화 경로
라쏘 정규화 경로.
라쏘 회귀를 이용한 희소 신호 복원.

13.3.5. Model selection

l_{1} 정규화자를 이용해 연관된 변수의 집합을 추정할 수 있는데, 어떤 경우에는 데이터를 생성하는 매개변수의 참값 \mathbf{w}^{\ast}도 구해낼 수 있다. 이렇게 N \to \infty일 때의 모델 참값을 구해내는 방법을 모델 선택 일관성이라 한다.

어떤 희소 매개변수에 대해 노이즈 낀 관측이 주어졌을 때 이의 지지집합에 기반한 최소 제곱 추정을 할 수 있는데 이를 비편향화라 한다. 라쏘 회귀는 관계 없는 계수들뿐만 아니라 관계 있는 계수들도 축소시키기 때문에 이 과정은 필요하다. 비편향화를 적용한 희소 추정은 좋은 성능을 보이지만, 희소 가정을 하지 않은 최소 제곱 추정은 매우 성능이 나쁘다.

\lambda는 교차 검증으로 택할 수 있지만, 교차 검증은 좋은 예측 정확도를 낳는 \lambda를 선택하는 것이므로 모델의 참값과는 같지 않을 수 있다. 왜냐하면 l_{1} 정규화는 선택 뿐만 아니라 축소도 행하기 때문에 선택된 계수들은 0에 가깝게 수축되기 때문이다. 교차 검증법은 이를 방지하기 위해서 \lambda의 값을 크지 않게 잡아 버리므로 관계 없는 변수들까지 포함하는 덜 희소한 모델이 나온다. 사실, \lambda가 예측값 면에서 최적인지의 여부는 모델 선택 일관성을 이야기하지 않는다. 모델 선택 일관성을 유도하는 \lambda의 선택 방법은 뒤에서 다룰 것이다.

l_{1} 정규화의 단점은 데이터가 약간 변화하더라도 결과가 크게 달라질 수 있다는 점이다. 베이지안 접근법을 쓰면 사후 주변 포함 확률 p(\gamma_{j} = 1 | \mathcal{D})를 추정하므로 이런 상황에 더 잘 대처된다. 빈도학파적 해결책은 붓스트랩 재샘플링을 사용한 뒤 데이터의 다른 버전에 대해 추정자를 다시 적용하는 것이다. 각각의 변수가 수행 시마다 어느 빈도로 선택되었는지를 계산함으로써 사후 포함확률을 계산할 수 있는데, 이를 안정성 선택이라 한다. 이 안정성 선택으로 얻은 포함 확률에 어떤 기준 (예를 들면 90%)을 두어서 희소 추정자를 유도할 수 있다. 이를 붓스트랩 라쏘 또는 볼라쏘라 한다. 이는 일반 라쏘가 생성하는 위양성 표본을 제거하는 역할을 하며, 일반 라쏘에 비해 더 넓은 조건하에서 모델 선택 일관성으로 적용할 수 있다.

볼라쏘 회귀에서 \lambda를 선택할 때 교차검증을 사용하는 대신 열들을 섞어 거대한 검은색 영역을 만든 뒤 \lambda를 그 가운데에서 선택하는 휴리스틱을 쓸 수 있다. 베이지안 접근법은 더 이론적인 방법을 적용할 수 있다.

라쏘 vs 볼라쏘 비교

13.3.6. Bayesian inference for linear models with Laplace priors

희소 선형 모델에 대해 최대사후확률추정을 할 때 베이지안 추론도 적용할 수 있으나 사후평균과 사후중간값은 희소하지 않게 되며 희소한 해는 오로지 사후최빈값뿐이다. 이는 사후최빈값이 사후분포를 딱히 잘 대표하지 않는다는 또 하나의 예이기도 하다.

제곱예측오차를 최소화시키는 해는 사후최빈값이 아니라 사후평균인데, 못과 판자 사전분포와 사후평균을 사용하는 것은 라플라스 사전분포와 사후최빈값을 사용하는 것보다 더 낫다. 하지만 계산 복잡도가 조금 더 크다는 단점은 있다.

13.4. l_{1} regularization: algorithms

l_{1} 정규화 추정에 쓰는 알고리즘을 알아보자. 이차 손실 함수를 사용하는 라쏘 회귀에 대해서 주로 알아볼 것이지만 다른 세팅, 예컨대 로지스틱 회귀 등에도 확장이 가능하다.

13.4.1. Coordinate descent

모든 변수를 동시에 최적화하기보다는 하나하나씩 최적화하는 것이 쉬울 때가 있다. w_{j}^{\ast} = \mathrm{argmin}_{z} f(\mathbf{w} + z \mathbf{e}_{j}) - f(\mathbf{w})를 통해 j번째 계수를 구할 수 있는데, 각각의 계수를 순서대로 구할 수도 있고 무작위로 업데이트할 수도 있고 경사가 가장 급강하는 계수부터 업데이트할 수도 있다.

이러한 좌표별 경사 하강법은 각각의 1차원 최적화 문제를 해석적으로 풀 수 있을 때 의미가 있다. 예를 들어, 라쏘 회귀의 슈팅 알고리즘은은 다른 모든 계수들을 알고 있을 때 w_{j}의 최적값을 구할 수 있다. 로지스틱 회귀로의 확장도 가능하다.

13.4.2. LARS and other homotopy methods

좌표 하강법의 단점은 한 번에 한 개의 변수만 업데이트하기 때문에 수렴 속도가 느리다는 점이다. 활성 집합 방법은 한 번에 여러 개의 변수를 업데이트하지만, 어떤 변수가 업데이트되어야 하는지를 판단해야 하기 때문에 더 복잡하다. 활성 집합 방법은 한 번에 몇 개의 변수들을 추가하거나 삭제하므로 최적해로부터 시작점이 멀다면 시간이 오래 걸릴 수 있다. 하지만 여러 서로 다른 \lambda 값에 대해서도 정규화 경로를 구해낼 수 있다는 장점이 있다. 이 알고리즘은 \lambda_{k-1} \simeq \lambda_{k}인 경우 \hat{\mathbf{w}}(\lambda_{k})\hat{\mathbf{w}}(\lambda_{k-1})로부터 빠르게 계산할 수 있음을 이용한다. 이를 웜 스타팅이라 한다. 사실 \lambda의 단일 값을 구하려고 해도 웜 스타팅을 이용해 여러 최적해의 집합을 구하는 것이 계산적으로 더 효과적일 때가 가끔 있다. 이를 연속법 또는 호모토피법이라 한다. 이는 \lambda_{\ast}가 작을 때 이 값에서 직접적으로 콜드 스타팅하는 것보다 종종 훨씬 빠르다.

기계학습에서 가장 잘 알려진 호모토피법은 LARS법 (최소 각도 회귀 수축법)일 것이다. 이는 가능한 \lambda의 모든 값에 대해 \hat{\mathbf{w}}(\lambda)를 계산한다. 이는 먼저 반응 벡터 \mathbf{y}와 가장 관련이 있는 변수 하나만 선택될 정도로 \lambda를 큰 값으로 잡는 것으로부터 시작한다. 이로부터, 두 번째 변수도 선택될 때까지 \lambda의 값을 줄인다. 이 때 각 단계에서의 잔여 벡터는 F_{k}활성 집합일 때 \mathbf{r}_{k} = \mathbf{y} - \mathbf{X}_{:, F_{k}} \mathbf{w}_{k}이다. 이러한 \lambda의 값은 기하학적으로 구할 수 있으며 모든 변수들이 더해질 때까지 이를 반복한다.

라쏘 회귀의 정규화 경로에 해당하는 해들의 수열을 모두 얻고 싶다면 활성 집합에서 변수들이 제거되는 것을 허용해야 한다. 활성 집합에 변수들을 추가하는 것만 허용할 경우의 알고리즘을 최소 각도 회귀 또는 LAR이라 한다. 이는 최소 제곱법과 같은 게산복잡도인 O(ND \min(N, D))가 들며, 탐욕적 전방 선택이나 최소 제곱 부스팅과 비슷한 알고리즘이다.

LARS 알고리즘을 확장해 l_{1} 정규화된 일반적 선형 모델 (로지스틱 회귀 같은)에 대한 전체 정규화 경로를 계산하려는 시도는 많지만, 일반적으로 가능하지는 않다. 표준적인 접근법은 \lambda_{\max}로부터 시작하여 조금씩 그 값을 줄여나가는 것이다.

13.4.3. Proximal and gradient projection methods

스케일이 큰 문제에서는 호모토피법은 너무 느리므로 다른 방법들이 필요한데, 이런 방법들은 l_{1} 외에 다른 정규화자에 대해서도 잘 확장할 수 있다. 다음의 볼록 목적함수 f(\mathbf{\theta}) = L(\mathbf{\theta}) + R(\mathbf{\theta})을 고려하자. 여기서 L(\mathbf{\theta})는 볼록하고 미분가능한 손실 함수, R(\mathbf{\theta})는 볼록하지만 미분가능할 필요는 없는 정규화자 함수이다.

일부 경우에는 이 목적함수는 최적화하기 쉬워진다. 예를 들어 L(\mathbf{\theta}) = \mathrm{RSS}(\mathbf{\theta}), \mathbf{X} = \mathbf{I}라 하면 목적 함수는 f(\mathbf{\theta}) = R(\mathbf{\theta}) + \frac{1}{2} \lVert \mathbf{\theta} - \mathbf{y} \rVert_{2}^{2}가 된다. 이에 대한 최적해는 근위 연산자 \mathrm{prox}_{R}(\mathbf{y}) = \mathrm{argmin}_{\mathbf{z}} (R(\mathbf{z}) + \frac{1}{2} \lVert \mathbf{z} - \mathbf{y} \rVert_{2}^{2}) 가 되는데, 일반적으로는 이 연산자를 최적화의 반복 루프 내에서 계속 적용한다. 핵심은 서로 다른 정규화자에 대해 이 연산자를 어떻게 효과적으로 계산하고 일반적 손실 함수에 대해 어떻게 이를 확장하는지이다.

13.4.3.1. Proximal operators

R(\mathbf{\theta}) = \lambda \lVert \mathbf{\theta} \rVert_{1}이면 근위 연산자는 성분별 약한 경계화인 \mathrm{prox}_{R} (\mathbf{\theta}) = \mathrm{soft}(\mathbf{\theta}, \lambda)이다.

R(\mathbf{\theta}) = \lambda \lVert \mathbf{\theta} \rVert_{0}이면 근위 연산자는 성분별 강한 경계화인 \mathrm{prox}_{R} (\mathbf{\theta}) = \mathrm{hard}(\mathbf{\theta}, \sqrt{2 \lambda})이다.

R(\mathbf{\theta}) = \mathbf{0}_{S}({\mathbf{\theta}}) (여기서 \mathbf{0}_{S}는 집합 S에서의 0-지시함수) 이면 근위 연산자는 집합 S로의 사영 \mathrm{proj}_{C}(\mathbf{\theta})이 된다. 이는 O(D) 안에 계산 가능하다.

13.4.3.2. Proximal gradient method

경사 하강법에서 근위 연산자를 쓰려면 어떻게 할까? 기본 아이디어는 손실 함수를 다음과 같이 2차 근사하는 것이다: \mathbf{\theta}_{k+1} = \mathrm{argmin}_{\mathbf{z}} )R(\mathbf{z}) + L(\mathbf{\theta}_{k}) + \mathbf{g}_{k}^{T} (\mathbf{z} - \mathbf{\theta}_{k}) + \frac{1}{2t_{k}} \lVert \mathbf{z} - \mathbf{\theta}_{k} \rVert_{2}^{2})

\mathbf{z}에 관련없는 항을 제거하고 t_{k}로 곱하면 이는 \mathbf{u}_{k} = \mathbf{\theta}_{k} - t_{k} \nabla L(\mathbf{\theta}_{k})에 대해 \mathbf{\theta}_{k+1} = \mathrm{prox}_{t_{k}R}(\mathbf{u}_{k})가 된다. R(\mathbf{\theta}) = 0이면 이는 경사 하강법과 같고, R(\mathbf{\theta}) = \mathbf{0}_{S}(\mathbf{\theta})이면 이는 사영 경사 하강법과 같다. R(\mathbf{\theta}) = \lambda \lVert \mathbf{\theta} \rVert_{1}이면 이는 반복적 약한 경계화법이다. t_{k}를 구하는 법은, 이는 \mathbf{\theta}_{k} - \mathbf{\theta}_{k-1} \simeq t_{k}(\nabla L(\mathbf{\theta}_{k}) - \nabla L(\mathbf{\theta}_{k-1}))을 만족해야 하므로 t_{k} = \frac{(\mathbf{\theta}_{k} - \mathbf{\theta}_{k-1})^{T}(\mathbf{\theta}_{k} - \mathbf{\theta}_{k-1})}{(\mathbf{\theta}_{k} - \mathbf{\theta}_{k-1})^{T}(\nabla L(\mathbf{\theta}_{k}) - \nabla L(\mathbf{\theta}_{k-1}))}가 된다. 이를 바질라이-보르베인 또는 스펙트럼 스텝 사이즈라 한다. 이는 근위 연산자가 아니더라도 임의의 경사 하강법에 적용 가능하며, 목적 함수를 단조감소시키지는 않지만 일반적인 선 탐색 방법보다 훨씬 빠르다. (수렴을 보장하기 위해서는 목적 함수의 크기 M + 1의 슬라이딩 윈도에서의 평균값이 감소함을 필요로 한다.)

스펙트럼 스텝 사이즈를 반복적 약한 경계법과 접목시킨 뒤 \lambda를 점진적으로 줄이는 연속법을 적용하면 SpaRSA (분리 가능 근사에 의한 희소 재구축) 알고리즘이라는 빠른 방법을 얻을 수 있다.

13.4.3.3. Nesterov’s method

근위 경사 하강법의 더 빠른 버전은 이차 근사 전개를 가장 최근의 매개변수 값이 아닌 다른 점을 중심으로 전개한다. \mathbf{\theta}_{k+1} = \mathrm{prox}_{t_{k} R} (\mathbf{\pi}_{k} - t_{k} \nabla L(\mathbf{\pi}_{k})), \mathbf{\pi}(k) = \mathbf{\theta}_{k} + \frac{k-1}{k+2}(\mathbf{\theta}_{k} - \mathbf{\theta}_{k-1})으로 전개하는 것인데, 이를 네스테로프법이라 한다. t_{k}를 정하는 데에는 다양한 방법이 있지만 선 탐색법을 쓸 수 있다. 이것이 반복적 약한 경계법 및 점진적 연속법과 결합되면 빠른 반복 수축 경계 알고리즘 (FISTA)가 된다.

13.4.4. EM for lasso

라쏘 회귀를 라쏘로 풀려면 어떻게 할까? 은닉 변수가 없으므로 이상하게 보일 수 있지만, 라플라스 분포는 가우시안 비례 혼합 형태인 \mathrm{Lap}(w_{j} | 0, \frac{1}{\gamma}) = \frac{\gamma}{2} e^{-\gamma \lvert w_{j} \rvert} = \int \mathcal{N}(w_{j} | 0, \tau_{j}^{2}) \mathrm{Ga}(\tau_{j}^{2} | 1, \frac{\gamma^{2}}{2}) d \tau_{j}^{2}로 나타낼 수 있음을 이용한다. 이를 이용하면 라쏘 회귀 모델의 결합 분포는 \mathbf{\Lambda}_{\mathbf{\tau}} = \mathrm{diag}(\frac{1}{\tau_{j}^{2}})이고 \mathbf{X}가 표준화되고 \mathbf{y}가 원점을 중심으로 한다고 가정할 때

p(\mathbf{y}, \mathbf{w}, \mathbf{\tau}, \sigma^{2} | \mathbf{X}) = \mathcal{N}(\mathbf{y} | \mathbf{X}\mathbf{w}, \sigma^{2} \mathbf{I}_{N}) \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathbf{\Lambda}_{\mathbf{\tau}}) [\prod_{j} \mathrm{Ga}(\tau_{j}^{2} | 1, \frac{\gamma^{2}}{2})] \mathrm{IG}(\sigma^{2} | a_{\sigma}, b_{\sigma})

가 된다. 이를 좀 더 간략화시키면 다음과 같다.

p(\mathbf{y}, \mathbf{w}, \mathbf{\tau}, \sigma^{2} | \mathbf{X}) \propto (\sigma^{2})^{-\frac{N}{2}} e^{-\frac{1}{2\sigma^{2}} \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2}} \lvert \mathbf{\Lambda}_{\mathbf{\tau}}\rvert^{-\frac{1}{2}}e^{-\frac{1}{2} \mathbf{w}^{T} \mathbf{\Lambda}_{\mathbf{\tau}}^{-1} \mathbf{w}} [\prod_{j} e^{-\frac{\gamma^{2}}{2} \tau_{j}^{2}}] e^{-\frac{b_{\sigma}}{\sigma^{2}}} (\sigma^{2})^{-(a_{\gamma} + 1)}

이에 기대값 최대화 알고리즘을 적용한다.

13.4.4.1. Why EM?

l_{1} 최대사후확률추정 문제에 기대값 최대화 알고리즘을 써야 하는가? 잠재 변수에 기반한 접근은 다음의 이점이 있다.

  • 강건한 선형 회귀나 프로빗 회귀 등 모델의 여러 변형에 대해 쉽게 확장할 수 있다.
  • 감마 사전분포 이외의 사전분포의 사용도 고려하게 될 수 있다.
  • 최대사후확률추정뿐만 아니라 전체 사후분포도 계산할 수 있다. 이를 베이지안 라쏘라고 한다.

13.4.4.2. The objective function

\mathbf{w}에 관계 없는 항을 제외하면, 목적 함수는 l_{c}(\mathbf{w}) = -\frac{1}{2\sigma^{2}} \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2} - \frac{1}{2} \mathbf{w}^{T} \mathbf{\Lambda}_{\mathbf{\tau}} \mathbf{w} + \mathrm{const} 가 된다.

13.4.4.3. The E step

사전분포 관련된 항은 \mathrm{tr}(\mathbf{\Lambda}_{\mathbf{\tau}} \mathbf{w} \mathbf{w}^{T})로 쓸 수 있다. 그러므로 핵심은 \mathbb{E}[\frac{1}{\tau_{j}^{2}} | \mathbf{w}, \mathcal{D}]를 계산하는 것인데, 사후분포는 역가우시안 분포 p(\frac{1}{\tau_{j}^{2}} | \mathbf{w}, \mathcal{D}) = \mathrm{InverseGaussian}(\sqrt{\frac{\gamma^{2}}{w_{j}^{2}}}, \gamma^{2})이 되므로 \mathbb{E}[\frac{1}{\tau_{j}^{2}} | \mathbf{w}, \mathcal{D}] = \frac{\gamma}{\lvert w_{j} \rvert}이 된다.

E 단계의 결과물 \bar{\mathbf{\Lambda}} = \mathrm{diag}(\mathbb{E}[\frac{1}{\tau_{j}^{2}}])에 대해 w_{j} 중 많은 수가 0이므로 이 행렬은 잘 정의되지 않을 수 있다. M 단계의 추정을 \bar{\mathbf{\Lambda}}^{-1}로 나타낼 수 있으므로 이 문제는 해결 가능하다.

\sigma^{2}의 사후분포는 p(\sigma^{2} | \mathcal{D}, \mathbf{w}) = \mathrm{IG}(a_{\sigma} + \frac{N}{2}, b_{\sigma} + \frac{1}{2} (\mathbf{y} - \mathbf{X} \hat{\mathbf{w}})^{T}(\mathbf{y} - \mathbf{X} \hat{\mathbf{w}})) = \mathrm{IG}(a_{N}, b_{N})이 되므로, \mathbb{E}[\frac{1}{\sigma^{2}}] = \frac{a_{N}}{b_{N}} = \bar{\omega}이다.

13.4.4.4. The M step

M 단계는 \hat{\mathbf{w}} = \mathrm{argmax}_{\mathbf{w}} (-\frac{1}{2} \bar{\omega} \lVert \mathbf{y} - \mathbf{X} \mathbf{w}\rVert_{2}^{2} - \frac{1}{2} \mathbf{w}^{T} \bar{\mathbf{\Lambda}} \mathbf{w})를 계산하는 것이다. \mathbf{X} = \mathbf{U}\mathbf{D} \mathbf{V}^{T}를 특이값 분해라 할 때 매개변수의 추정값은 다음과 같다.

\hat{\mathbf{w}} = \bar{\mathbf{\Lambda}}^{-1} \mathbf{V} (\mathbf{V}^{T} \bar{\mathbf{\Lambda}}^{-1} \mathbf{V} + \frac{1}{\bar{\omega}} \mathbf{D}^{-2})^{-1} \mathbf{D}^{-1} \mathbf{U}^{T} \mathbf{y}

13.4.4.5. Caveat

라쏘 목적 함수는 볼록함수이기 때문에 이 방법은 항상 전역 최적해를 찾아내야겠지만 실제로는 가능하지 않다. 해의 참값이 w_{j}^{\ast} \neq 0인데 M 단계에서 \hat{w}_{j} = 0인 경우가 일어났다고 하면 그 다음 E 단계에서 \tau_{j}^{2} = 0이므로 그 다음 M 단계에서 \hat{w}_{j}는 또 다시 0이 된다. 그러므로 한 번 0으로 놓은 변수를 되돌릴 수 없어 영원히 해의 참값을 얻을 수 없다. 다행스럽게도 이런 경우는 적다.

13.5. l_{1} regularization: extensions

l_{1} 정규화의 확장을 알아보자.

13.5.1. Group lasso

일반적 l_{1} 정규화에서는 매개변수와 변수들간 1:1 대응 관계가 있으므로 \hat{w}_{j} = 0으로 세팅하면 변수 j가 제외된다. 하지만 보다 복잡한 모델에서는 매개변수와 변수간 관계가 1:1 대응이 아닐 수 있다. 예를 들면:

  • 다항 로지스틱 회귀 : 각 특성은 C개의 – 클래스 당 하나의 – 서로 다른 가중치에 연관되어 있다.
  • 범주화된 입력에 대한 선형 회귀 : 각각의 스칼라 입력은 길이 C 벡터에 원-핫 암호화되어 있다.
  • 다중 작업 학습 : 복수의 연관된 예측 문제를 풀며, 각각의 특성은 C개의 서로 다른 가중치에 연관되어 있다. 각각의 특성이 0개의 작업 또는 전체 작업에 선택될 수도 있으므로 가중치는 그룹 단위로 선택된다.

\lVert \mathbf{w} \rVert = \sum_{j} \sum_{c} \lvert w_{jc} \rvert 꼴의 l_{1} 정규화자를 그대로 쓴다면, \mathbf{w}_{j, :} 중 일부는 0이고 일부는 0이 아니게 될 것이다. 이를 방지하기 위해, 매개변수 벡터를 G개의 그룹으로 나누고 목적 함수는 \lVert \mathbf{w}_{g} \rVert_{2} = \sqrt{\sum_{j \in g} w_{j}^{2}} 이라 할 때 J(\mathbf{w}) = \mathrm{NLL}(\mathbf{w}) + \sum_{g=1}^{G} \lambda_{g} \lVert \mathbf{w}_{g} \rVert_{2}가 된다. 음의 로그가능도가 최소제곱 가능도라면 이 방법은 그룹 라쏘라 한다. \lambda_{g} = \lambda \lvert g \rvert를 사용함으로써 원소의 수가 많은 그룹에 대해서는 징벌치를 더 크게 부여할 수 있다. 2-놈 대신 제곱 2-놈을 사용하면 이것은 능선 회귀와 같다. 제곱근을 쓰는 이유는 그룹의 가중치 벡터 크기를 징벌하여 희소성을 유도하기 위한 것이다.

2-놈 대신 무한-놈 \lVert \mathbf{w}_{g} \rVert_{\infty} = \max_{j \in g} \lvert w_{j} \rvert를 쓸 수도 있다. 이것도 그룹 희소성을 유도한다. 그룹 라쏘는 그룹 구조를 나타내기 때문에 그룹화된 입력에 대해 일반 라쏘보다 더 좋은 결과를 낸다. l_{\infty} 놈은 블록 내의 모든 원소를 비슷한 크기로 맞추는 효과가 있다.

13.5.1.1. GSM interpretation of group lasso

그룹 라쏘는 사전분포 p(\mathbf{w} | \gamma, \sigma^{2}) \propto e^{-\frac{\gamma}{\sigma} \sum_{g=1}^{G} \lVert \mathbf{w}_{g} \rVert_{2}}에 대한 최대사후확률추정과 관계가 있다. 이 사전분포는 가우시안 비례 혼합으로 쓰일 수 있는데 그 형태는 d_{g}가 그룹의 크기일 때 \mathbf{w}_{g} | \sigma^{2}, \tau_{g}^{2} \sim \mathcal{N}(\mathbf{0} , \sigma^{2} \tau_{g}^{2} \mathbf{I}_{d_{g}}), \tau_{g}^{2} | \gamma \sim \mathrm{Ga}(\frac{d_{g} + 1}{2}, \frac{\gamma}{2})가 된다. 그러므로 그룹당 하나의 분산 항이 있고, 그 분산 항은 감마 사전분포로부터 유도되고, 그 감마 사전분포의 형태 매개변수는 그룹 크기에 의존하고, 비율 매개변수는 \gamma에 의존한다. \mathbf{w}_{j} 중 하나가 작으면 \tau_{j}^{2}도 작아지므로 \mathbf{w}_{j}의 나머지도 작아진다. 커질 경우도 같다. 그러므로 이 형태의 분포가 그룹화를 유도하는 것이다.

그룹 라쏘

13.5.1.2. Algorithms for group lasso

그룹 라쏘에는 다양한 알고리즘이 있다. 첫번째 접근법은 근위 경사 하강법이다. 정규화자가 분리 가능하므로, 근위 연산자 또한 l_{p} 정규화자에 대해 \mathrm{prox}_{R} (\mathbf{b}) = \mathrm{argmin}_{\mathbf{z} \in \mathbb{R}^{D_{g}}} (\lVert \mathbf{z} - \mathbf{b} \rVert_{2}^{2} + \lambda \lVert \mathbf{z} \rVert_{p}), \mathbf{b} = \mathbf{\theta}_{kg} - t_{k} \mathbf{g}_{kg}의 형태로 분해된다. p = 2이면 이는 \mathrm{prox}_{R} (\mathbf{b}) = \mathbf{b} - \mathrm{proj}_{\{\mathbf{z} : \lVert \mathbf{z} \rVert_{2} \leq \lambda\}}(\mathbf{b}) = \mathbf{b} \frac{\max(\lVert \mathbf{b} \rVert_{2} - \lambda, 0)}{\max(\lVert \mathbf{b} \rVert_{2} - \lambda, 0) + \lambda}가 된다. p = \inftyl_{2} 대신 l_{1} 구를 사용한다.

또 다른 접근법은 기대값 최대화 알고리즘의 변형이다. 이는 일반 라쏘와 거의 같지만, \tau_{j}^{2} = \tau_{g(j)}^{2}를 그룹별로 정한다. \sigma^{2}\mathbf{w}에 대한 조건분포는 그대로이지만, 몇 가지 변경 사항이 있다.

가중치 정밀도에 대한 조건분포는 공유된 가중치에 기반한 것으로 변경되어 \frac{1}{\tau_{g}^{2}} | \gamma, \mathbf{w}, \sigma^{2}, \mathbf{y}, \mathbf{X} \sim \mathrm{InverseGaussian}(\sqrt{\frac{\gamma^{2}\sigma^{2}}{\lVert \mathbf{w}_{g} \rVert_{2}^{2}}}, \gamma^{2})이 된다. (여기서 \mathbf{w}_{g}는 그룹 내 속한 가중치들의 제곱의 합). E 단계에서는 \mathbb{E}[\frac{1}{\tau_{g}^{2}}] = \frac{\gamma \sigma}{\lVert \mathbf{w}_{g} \rVert_{2}}이 된다.

조절 인자에 대한 조건분포도 p(\gamma^{2} | \mathbf{\tau}) = \mathrm{Ga}(a_{\gamma} + \frac{G}{2}, b_{\gamma} + \frac{1}{2} \sum_{g}^{G} \tau_{g}^{2})이 된다.

13.5.2. Fused lasso

인접한 가중치들이 비슷한 값을 갖게 하면서 희소성도 주려면 어떻게 해야 할까? 다음의 사전분포를 주면 된다: p(\mathbf{w} | \sigma^{2}) \propto e^{-\frac{\lambda_{1}}{\sigma}\sum_{j=1}^{D} \lvert w_{j} \rvert - \frac{\lambda_{2}}{\sigma} \sum_{j=1}^{D-1} \lvert w_{j+1} - w_{j} \rvert} 이를 융합된 라쏘 징벌항이라 한다. 함수 데이터 해석학에서 보통 \mathbf{X} = \mathbf{I}를 사용하여 각 신호 위치당 1개의 계수를 쓰고는 한다. 이 경우에 전체 목적 함수는 J(\mathbf{w}, \lambda_{1}, \lambda_{2}) = \sum_{i=1}^{N} (y_{i} - w_{i})^{2} + \lambda_{1} \sum_{i=1}^{N} \lvert w_{i} \rvert + \lambda_{2} \sum_{i=1}^{N-1} \lvert w_{i+1} - w_{i} \rvert 가 된다. 이는 그래프 내 사이클에도 확장할 수 있는데, 이 경우 전체 목적 함수는 J(\mathbf{w}, \lambda_{1}, \lambda_{2}) = \sum_{s \in V} (y_{s} - w_{s})^{2} + \lambda_{1} \sum_{s \in V} \lvert w_{s} \rvert + \lambda_{2} \sum_{(s, t) \in E} \lvert w_{s} - w_{t} \rvert 가 된다. 이를 그래프-유도 융합 라쏘라 한다. 용례는 생물학적 경로의 데이터베이스 등으로부터 그래프 기반 사전지식이 적용될 때가 있다.

13.5.2.1. GSM interpretation of fused lasso

융합된 라쏘 모델은 다음의 계층 모델과 같다:

\mathbf{w} | \sigma^{2}, \mathbf{\tau}, \mathbf{\omega} \sim \mathcal{N}(\mathbf{0}, \sigma^{2} \mathbf{\Sigma}(\mathbf{\tau}, \mathbf{\omega}), \tau_{j}^{2} | \gamma_{1} \sim \mathrm{Expon}(\frac{\gamma_{1}^{2}}{2}), \omega_{j}^{2} | \gamma_{2} \sim \mathrm{Expon}(\frac{\gamma_{2}^{2}}{2}), \mathbf{\Sigma} = \mathbf{\Omega}^{-1}이고 \mathbf{\Omega}는 주대각선이 \frac{1}{\tau_{j}^{2}} + \frac{1}{\omega_{j-1}^{2}} + \frac{1}{\omega_{j}^{2}}이고 부대각선이 -\frac{1}{\omega_{j}^{2}}인 삼대각행렬이 된다. 이 때 \frac{1}{w_{0}^{2}} = \frac{1}{w_{D}^{2}} = 0으로 정의한다. 이 모델은 체인 구조의 가우시안 마르코프 무작위 필드를 사전분포로 두고 분산을 무작위로 둔 모델이다. 그래프-유도 융합 라쏘 모델의 경우엔 가우시안 정밀도 행렬의 0 패턴에 그래프의 구조가 나타내어진다.

13.5.2.2. Algorithms for fused lasso

가우시안 사전분포의 마르코프 구조를 이용하면 융합 라쏘 모델에 대한 기대값 최대화 알고리즘을 일반화시킬 수 있다. 직접 풀 수도 있지만 계산 복잡도가 크다는 단점이 있다.

13.5.3. Elastic net (ridge and lasso combined)

라쏘 회귀는 변수 선택 과정에서 효과적이지만 몇 가지 문제가 있다.

  • 상호 연관도니 변수 그룹이 있을 때 라쏘 회귀는 그 중 무작위로 하나만 선택하는 경향이 있지만, 보통은 그룹 내 모든 연관 변수들을 같이 선택하는 것이 낫다. 그룹 라쏘를 쓰면 되지만 이는 그룹 구조를 알 때만 적용이 가능하다.
  • D > N이면 라쏘 회귀는 N개의 변수까지만 선택할 수 있다.
  • N > D인데 변수간 상호 연관이 되어 있다면 능선 회귀가 라쏘 회귀보다 더 성능이 좋다.

이를 위해 능선 회귀와 라쏘 회귀를 혼합한 엘라스틱 넷 방법이 있다.

13.5.3.1. Vanilla version

이 모델의 일반 버전은 다음의 목적 함수를 쓴다: J(\mathbf{w}, \lambda_{1}, \lambda_{2}) = \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert^{2} + \lambda_{2} \lVert \mathbf{w} \rVert_{2}^{2} + \lambda_{1} \lVert \mathbf{w} \rVert_{1} 이 때 이 징벌 함수는 \lambda_{2} > 0이라면 강볼록이 되어 \mathbf{X}가 꽉 찬 랭크가 아니더라도 유일한 전역 최소값을 갖는다. 사실 \mathbf{w}에 강볼록 징벌 함수가 주어지면 군집 효과, 즉 강하게 상호 연관된 변수들의 회귀 계수가 같게 맞춰지는 효과가 있다. 그와 반대로, 라쏘 회귀에서는 일부는 0이고 일부는 아닐 수도 있다.

13.5.3.2. Algorithms for vanilla elastic net

엘라스틱 넷 문제는 라쏘 문제의 데이터를 수정한 것이다. \tilde{\mathbf{X}} = c [\mathbf{X} ; \sqrt{\lambda_{2}} \mathbf{I}_{D}], \tilde{\mathbf{y}} = [\mathbf{y} ; \mathbf{0}_{D \times 1}], c = (1 + \lambda_{2})^{-\frac{1}{2}}라 하면 \hat{\tilde{\mathbf{w}}} = \mathrm{argmin}_{\tilde{\mathbf{w}}} (\lVert \tilde{\mathbf{y}} - \tilde{\mathbf{X}} \tilde{\mathbf{w}} \rVert^{2} + c \lambda_{1} \lVert \tilde{\mathbf{w}} \rVert_{1}), \mathbf{w} = c \tilde{\mathbf{w}}가 된다.

LARS 알고리즘을 이용해 이를 풀면 LARS-EN 알고리즘이라 한다. 변수 m개가 포함되어 있을 때 복잡도는 O(m^{3} + Dm^{2})이다. \tilde{\mathbf{X}}는 랭크가 D이므로 라쏘와는 달리 필요하면 m = D를 쓸 수도 있다. \lambda_{1}\lambda_{2}를 선택할 때는 교차검증을 이용한다.

13.5.3.3. Improved version

일반 엘라스틱 넷은 l_{2} 징벌치와 l_{1} 징벌치로 수축을 두 번이나 하기 때문에 성능이 그렇게 좋진 못하다. 해법은 일반 엘라스틱 넷으로 얻은 추정값들의 크기를 키워 l_{2} 수축을 되돌리는 것이다. \mathbf{w}^{\ast}가 본래의 해라고 할 때 \hat{\mathbf{w}} = \sqrt{1 + \lambda_{2}} \mathbf{w}^{\ast}를 쓰는 것인데, 이를 보정된 추정이라 하며, 이는 \hat{\mathbf{w}} = \mathrm{argmin}_{\mathbf{w}} \mathbf{w}^{T} (\frac{\mathbf{X}^{T} \mathbf{X} + \lambda_{2} \mathbf{I}}{1 + \lambda_{2}})\mathbf{w} - 2 \mathbf{y}^{T} \mathbf{X} \mathbf{w} + \lambda_{1} \lVert \mathbf{w} \rVert_{1}로 주어진다. 이 때 (\frac{\mathbf{X}^{T} \mathbf{X} + \lambda_{2} \mathbf{I}}{1 + \lambda_{2}}) = \frac{1}{1 + \lambda_{2}} \hat{\mathbf{\Sigma}} + \frac{\lambda_{2}}{1 + \lambda_{2}} \mathbf{I} 이므로, 엘라스틱 넷은 \hat{\mathbf{\Sigma}}\mathbf{I} 쪽으로 수축시킨 라쏘라고 볼 수 있다.

13.5.3.4. GSM interpretation of elastic net

엘라스틱 넷에 쓰인 사전분포의 형태는 다음과 같다: p(\mathbf{w} | \sigma^{2}) \propto e^{-\frac{\gamma_{1}}{\sigma} \sum_{j=1}^{D} \lvert w_{j} \rvert - \frac{\gamma_{2}}{2 \sigma^{2}} \sum_{j=1}^{D} w_{j}^{2}} 이는 가우시안 분포와 라플라스 분포의 곱이며, 다음의 계층 사전분포로 나타낼 수도 있다: w_{j} | \sigma^{2}, \tau_{j}^{2} \sim \mathcal{N}(0, \sigma^{2}(\tau_{j}^{-2} + \gamma_{2})^{-1}), \tau_{j}^{2} | \gamma_{1} \sim \mathrm{Expon}(\frac{\gamma_{1}^{2}}{2}). 이 때 \gamma_{2} = 0이라면 이는 일반 라쏘와 같다. 기대값 최대화 알고리즘을 통해 최대사후확률추정을 할 수도 있고 마르코프 연쇄 몬테 카를로법을 통해 베이지안 추론을 할 수도 있다.

13.6. Non-convex regularizers

라플라스 사전분포는 볼록 최적화 문제를 낳지만, 통계적인 관점에서 이 사전분포는 문제가 있다. 우선 0 근처에 충분한 확률질량을 배치하지 않는 분포이기 때문에 노이즈를 효과적으로 억제하지 못한다. 또한 큰 값에 대해 충분한 확률질량을 배치하지 않으므로 연관 계수의 지나친 수축을 유도할 수 있다. 이는 0 근처에 확률질량이 더 많고 꼬리가 더 두꺼운, 더 유연한 사전분포를 도입함으로써 해결 가능하다. 이렇게 되면 전역 해법을 찾을 수는 없게 되지만 이런 비볼록 방법은 종종 l_{1} 정규화를 정확도와 연관 변수 찾기 면에서 능가하기도 한다.

13.6.1. Bridge regression

l_{1}의 자연적 일반화는 다리 회귀로서 b \geq 0에 대해 \hat{\mathbf{w}} = \mathrm{NLL}(\mathbf{w}) + \lambda \sum_{j} \lvert w_{j} \rvert^{b} 의 꼴이다. 이는 지수승 분포 \mathrm{ExpPower}(w | \mu, a, b) = \frac{b}{2a \Gamma(1 + \frac{1}{b})} e^{-\frac{\lvert x - \mu \rvert^{b}}{a}}에 해당하는 최대사후확률추정이다. b = 2일 경우에 이는 가우시안 분포에 따른 능선 회귀이고, b = 1일 경우에 이는 라플라스 분포에 따른 라쏘 회귀이고, b = 0일 경우에 이는 l_{0} 회귀에 따르는 최적 부분집합 탐색 알고리즘이다. b < 1일 경우 목적 함수가 볼록함수가 아니게 되고 b > 1일 경우 희소성을 유도하지 않게 된다. 따라서 l_{1} 정규화는 l_{0} 놈에 대한 가장 타이트한 볼록 근사이다.

13.6.2. Hierarchical adaptive lasso

라쏘의 주된 단점 중 하나는 편향 추정자가 된다는 것인데, 이는 관계 없는 매개변수를 징벌하기 위해 \lambda를 크게 잡으면 관계 있는 매개변수들도 같이 징벌되는 경우가 많기 때문이다. 때문에 각각 매개변수마다 징벌 변수를 다르게 주면 좋을 것이다. 물론 징벌 변수 D개 각각을 교차검증으로 선택하는 것은 불가능하지만, 각각의 매개변수가 튜닝 매개변수로부터 유도되게 하고 그 튜닝 매개변수가 같은 켤레사전분포에서 유도되도록 하는 베이지언 세팅은 가능하다. 모델은 다음과 같다:

\gamma_{j} \sim \mathrm{IG}(a, b), \frac{\tau_{j}^{2}}{\gamma_{j}} \sim \mathrm{Ga}(1, \frac{\gamma_{j}^{2}}{2}), w_{j} | \tau_{j}^{2} \sim \mathcal{N}(0, \tau_{j}^{2})

이를 계층 적응적 라쏘(HAL)라고 한다. \tau_{j}^{2}를 적분해서 빼내면 w_{j}에 대한 라플라스 분포 \mathrm{Lap}(w_{j} | 0, \frac{1}{\gamma_{j}})이 된다. 이 결과는 p(w_{j})가 라플라스의 비례혼합 분포가 되는 것인데, 이는 기대값 최대화 알고리즘으로 국소적 사후최빈값을 피팅할 수 있다. 이로부터 나오는 추정값은 종종 라쏘 회귀보다 훨씬 좋은 성능을 보이는데, 이는 이 모델이 희소성을 유도할 때 더 알맞은 위치로 유도하기 때문이다.

가우시안, 라플라스, 지수승 분포에 대한 로그 사전분포/사후분포의 플롯.

13.6.2.1. EM for HAL

역감마 분포는 라플라스에 대해 켤레이므로, \gamma_{j}에 대한 E 단계는 p(\gamma_{j} | w_{j}) = \mathrm{IG}(a + 1, b + \lvert w_{j} \rvert)이다. \sigma^{2}에 대한 E 단계는 일반 라쏘와 같다. \mathbf{w}의 사전분포는 p(\mathbf{w} | \mathbf{\gamma}) = \prod_{j} \frac{1}{2 \gamma_{j}} e^{-\frac{\lvert w_{j} \rvert}{\gamma_{j}}}이 된다.

따라서 M 단계에서는 \hat{\mathbf{w}}_{t+1} = \mathrm{argmax}_{\mathbf{w}} (\log \mathcal{N}(\mathbf{y} | \mathbf{X}\mathbf{w}, \sigma^{2}) - \sum_{j} \lvert w_{j} \rvert \mathbb{E}[\frac{1}{\gamma_{j}}])을 최적화하게 된다. 기대값은 \mathbb{E}[\frac{1}{\gamma_{j}}] = \frac{a+1}{b + \lvert w_{j, t} \rvert} 이 되는데 이를 s_{j, t}이라 놓으면 M 단계는 가중치 라쏘 문제인 \hat{\mathbf{w}}_{t+1} = \mathrm{argmin}_{\mathbf{w}} \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2} + \sum_{j} s_{j, t} \lvert w_{j} \rvert 이 된다. 이는 LARS 등의 방법으로 풀 수 있다. 이 때 이전 단계에서 특정 계수가 크게 추정되었다면 s_{j, t}는 작아지므로 큰 계수는 크게 징벌되지 않는다. 하지만 작은 계수들은 크게 징벌된다. 이것이 각각의 계수에 대해 징벌의 세기를 다르게 조절하는 메커니즘이다. 이 결과는 라쏘의 결과값보다 종종 훨씬 희소해지면서, 편향도 적은 추정이 된다. a = b = 0으로 두고 1번의 반복만 수행한다면 적응적 라쏘 알고리즘이 된다. 기대값 최대화 알고리즘은 반복적 재가중 l_{1} 방법과 관계가 있다.

라쏘와 계층 적응적 라쏘의 컨투어.

13.6.2.2. Understanding the behavior of HAL

계층 적응적 라쏘에서 \gamma_{j}를 적분해 빼내면 주변분포는 p(w_{j} | a, b) = \frac{a}{2b} (\frac{\lvert w_{j} \rvert}{b} + 1)^{-(a+1)}이 되는데, 이것은 일반화된 t 분포의 특수한 경우이다. 일반화된 t 분포는 이중 파레토 분포인 \mathrm{GT}(w | \mu, a, c, q) = \frac{q}{2ca^{\frac{1}{q}} B(\frac{1}{q}, a)} (1 + \frac{\lvert w - \mu \rvert^{q}}{ac^{q}})^{-\frac{a + 1}{q}}을 말하는데, c는 비례 매개변수 (희소도를 결정), a는 자유도이다. q = 2, c = \sqrt{2}로 두면 일반적인 t 분포가 되고, a \to \infty로 두면 지수승 분포가 되고, q = 1, a = \infty로 두면 라플라스 분포가 된다. 여기서는 p(w_{j} | a, b) = \mathrm{GT}(w_{j} | 0, a, \frac{b}{a}, 1)이다.

이에 따른 징벌치 항은 \pi_{(a, b)} (w_{j}) = -\log p(w_{j}) = (a+1) \log (1 + \frac{\lvert w_{j} \rvert}{b}) + \mathrm{const}이 된다. 계층 적응적 라쏘의 징벌치 항은 일반 라쏘보다 희소성을 더 강하게 유도하고, 당연하지만 이 징벌치 항은 볼록함수가 아니다.

이를 가중치가 직교행렬인 선형 회귀에 적용해보면, \hat{\mathbf{w}}_{\mathrm{MLE}} = \mathbf{X}^{T} \mathbf{y}, \hat{\mathbf{y}}_{\mathrm{MLE}} = \mathbf{X} \hat{\mathbf{w}}_{\mathrm{MLE}}로 뒀을 때 목적 함수는 J(\mathbf{w}) = \frac{1}{2} \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2} + \sum_{j=1}^{D} \pi_{(a, b)} ( \lvert w_{j} \rvert ) = \frac{1}{2} \lVert \mathbf{y} - \hat{\mathbf{y}} \rVert^{2} + \frac{1}{2} \sum_{j=1}^{D} (\hat{w}_{j, \mathrm{MLE}} - w_{j})^{2} + \sum_{j=1}^{D} \pi_{(a, b)} (\lvert w_{j} \rvert)이 된다. 그러므로 다음의 1차원 최적화 문제 \hat{w}_{j} = \mathrm{argmin}_{w_{j}} (\frac{1}{2}(\hat{w}_{j, \mathrm{MLE}} - w_{j})^{2} + \pi_{(a, b)}(w_{j}))을 품으로써 최대사후확률추정을 한 번에 한 차원씩 계산할 수 있다. l_{1} 추정자는 일반적인 약한 경계법과 비슷한 행보를 보이지만, 큰 계수들도 0으로 수축하기 때문에 그렇게 바람직하지는 않다. 이에 비해 계층 적응적 라쏘 추정자는 강한 경계법과 비슷한 행보를 보인다.

정규 감마 경계법.

13.6.3. Other hierarchical priors

희소성을 유도하는 다른 계층적 사전분포도 많지만, 일반적으로는 이들이 오목함수는 아니다. 흥미로운 사전분포 중 하나는 정규-제프리 분포 \mathrm{Ga}(\tau_{j}^{2} | 0, 0) \propto \frac{1}{\tau_{j}^{2}}인데, 결과 주변분포는 p(w_{j}) = \mathrm{NI}(w_{j}) \propto \frac{1}{\lvert w_{j} \rvert}이 된다. 이는 계층 적응적 라쏘 추정, 즉 강한 경계법과 비슷한 경계법이지만, 자유도 매개변수가 없으므로 튜닝할 것도 없지만 희소정도를 조정할 수도 없다는 장단점이 존재한다.

13.7. Automatic relevance determination (ARD) / sparse Bayesian learning (SBL)

지금까지 알아본 사전분포는 곱분해 사전분포 p(\mathbf{w}) = \prod_{j} p(w_{j})를 사용했다. 이 사전분포는 w_{j} \sim \mathcal{N}(0, \tau_{j}^{2}) 꼴의 가우시안 비례혼합으로 표현할 수도 있고, 이런 잠재 분산들을 이용하면 \tau_{j}^{2} \to w_{j} \to \mathbf{y} \Leftarrow \mathbf{X}의 모델을 표현할 수 있고, 그 뒤에 기대값 최대화 알고리즘으로 최대사후확률추정을 수행할 수 있다. 여기서는 E 단계에서 p(\tau_{j}^{2} | w_{j})를 추론하고 M 단계에서는 \mathbf{w}\mathbf{y}, \mathbf{X}, \mathbf{\tau}로부터 추정한다. 이는 닫힌 형태의 가중치 l_{2} 정규화를 쓰거나 가중치 l_{1} 정규화를 쓴다. 최대사후확률추정 대신 베이지안 추론을 할 수도 있다.

여기서는 실측 베이즈에 기반한 또 다른 접근법을 다루는데, \mathbf{w}를 적분해 빼내고 \mathbf{\tau}에 대해 주변가능도를 최대화시킨다. 이런 실측 베이스 과정은 기대값 최대화로 구현될 수도 있고, l_{1} 과정에 재가중을 할 수도 있다. 이러한 분산들을 추정하면 이를 대입해 가중치들의 사후평균 \mathbb{E}[\mathbf{w} | \hat{\mathbf{\tau}}, \mathcal{D}]를 계산하는데, 이는 희소한 추정이 된다. 신경망의 경우에는 이는 자동 연관성 판별(ARD)라 하며, 선형 모델의 경우에는 희소 베이지안 학습(SBL)이라 한다. 선형 모델에 대해 기저 확대까지 하면 연관 벡터 기계(RVM)이라 한다.

13.7.1. ARD for linear regression

일반화된 선형 모델에 대한 자동 연관성 판별법은 라플라스 근사를 사용한다. 이 때 가중치 정밀도 \alpha_{j} = \frac{1}{\tau_{j}^{2}}, 측정 정밀도 \beta = \frac{1}{\sigma^{2}}로 두고 모델은 p(y | \mathbf{x}, \mathbf{w}, \beta) = \mathcal{N}(y | \mathbf{w}^{T} \mathbf{x}, \frac{1}{\beta}), p(\mathbf{w}) = \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathrm{diag}(\alpha_{i}^{-1}))이 된다. 이 때 주변가능도는 p(\mathbf{y} | \mathbf{X}, \mathbf{\alpha}, \beta) = \int \mathcal{N}(\mathbf{y} | \mathbf{X} \mathbf{w}, \frac{1}{\beta} \mathbf{I}_{N}) \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathrm{diag}(\alpha_{i}^{-1})) d \mathbf{w} = \mathcal{N} (\mathbf{y} | \mathbf{0}, \frac{1}{\beta}\mathbf{I}_{N} + \mathbf{X} \mathrm{diag}(\alpha_{i}^{-1}) \mathbf{X}^{T}) = (2 \pi)^{-\frac{N}{2}} \lvert \mathbf{C}_{\mathbf{\alpha}} \rvert^{-\frac{1}{2}} e^{-\frac{1}{2} \mathbf{y}^{T} \mathbf{C}_{\mathbf{\alpha}}^{-1} \mathbf{y}}, \mathbf{C}_{\mathbf{\alpha}} = \frac{1}{\beta} \mathbf{I}_{N} + \mathbf{X} \mathbf{A}^{-1} \mathbf{X}^{T}이 된다. 이는 못과 판자 모델의 주변가능도에서 이진 특성을 연속 특성으로 변경한 것과 같다.

로그 목적함수는 l(\mathbf{\alpha}, \beta) = -\frac{1}{2} \log p(\mathbf{y} | \mathbf{X}, \mathbf{\alpha}, \beta) = \log \lvert \mathbf{C}_{\mathbf{\alpha}} \rvert + \mathbf{y}^{T} \mathbf{C}_{\mathbf{\alpha}}^{-1} \mathbf{y}이 되는데, 이를 정규화하기 위해서는 정밀도 각각에 대한 켤레사전분포를 \alpha_{j} \sim \mathrm{Ga}(a, b), \beta \sim \mathrm{Ga}(c, d)로 둔다. 이 경우의 로그 목적함수는 l(\mathbf{\alpha}, \beta) = \log \lvert \mathbf{C}_{\mathbf{\alpha}} \rvert + \mathbf{y}^{T} \mathbf{C}_{\mathbf{\alpha}}^{-1} \mathbf{y} + \sum_{j} (a \log \alpha_{j} - b \alpha_{j}) + c \log \beta - d \beta가 되며, \mathbf{\alpha}\beta에 대한 베이지안 추론을 할 때 유용하다. 실측 베이스를 기반으로 할 때는 a = b = c = d = 0으로 세팅하며, 이 때 희소도가 최대가 된다.

위의 목적함수는 어떻게 최적화할까? 이는 못과 판자 모델에서 \mathbf{\gamma}의 최적값을 찾는 것, 즉 l_{0} 정규화와 비슷하지만, 국소적 최적값이 훨씬 더 적으므로 최적화하기 더 쉬워진다. \mathbf{\alpha}\beta를 추정하고 나면 사후분포는 p(\mathbf{w} | \mathcal{D}, \hat{\mathbf{\alpha}}, \hat{\beta}) = \mathcal{N}(\hat{\beta}(\hat{\beta} \mathbf{X}^{T} \mathbf{X} + \mathrm{diag}(\alpha_{j}))^{-1} \mathbf{X}^{T}\mathbf{y}, (\hat{\beta} \mathbf{X}^{T} \mathbf{X} + \mathrm{diag}(\alpha_{j}))^{-1})로 계산된다. 이는 희소성을 유도하므로 희소 베이지안 학습이라고 불린다.

13.7.2. Whence sparsity?

\hat{\alpha}_{j} \simeq 0이면, \hat{w}_{j} \simeq \hat{w}_{j, \mathrm{MLE}}이 되는데, 이는 0으로 수축하는 가우시안 사전분포는 0의 정밀도를 갖게 되기 때문이다. 반대로 \hat{\alpha}_{j} \simeq \infty이면, w_{j} = 0이므로 \hat{w}_{j} \simeq 0이 된다. 따라서 관계 없는 특성들은 가중치가 떨어져 나가게 된다. 다시 말하면, 주변가능도는 \alpha_{j}가 작지면 \mathbf{X}_{:,j}가 연관 없는 경우는 확률질량을 낭비하기 때문에 이러한 해들을 징벌한다.

13.7.3. Connection to MAP estimation

자동 연관성 판별은 최대사후확률추정법과 퍽 다르다. 여기서는 \mathbf{\alpha}를 적분해서 빼내고 \mathbf{w}를 최적화하는 것이 아니라 그 반대를 수행한다. w_{j}는 사후분포와 연관되어 있고 \alpha_{j}를 추정할 때에는 모든 특성으로부터 정보를 추출하기 때문에 유효한 사전분포 p(\mathbf{w} | \hat{\mathbf{\alpha}})비 곱분해이며 \mathcal{D}에 의존하게 된다. 자동 연관성 판별은 \hat{\mathbf{w}}_{\mathrm{ARD}} = \mathrm{argmin}_{\mathbf{w}} (\beta \lVert \mathbf{y} - \mathbf{X} \mathbf{w} \rVert_{2}^{2} + \min_{\mathbf{\alpha} \geq 0} \sum_{j} \alpha_{j} w_{j}^{2} + \log \lvert \mathbf{C}_{\mathbf{\alpha}} \rvert)의 최적화 문제를 푸는 것과 같다.

비 곱분해 사전분포를 쓰는 최대사후확률추정은 곱분해 사전분포를 쓰는 최대사후확률추정보다 나은데, 국소적 최적해의 수가 더 적으면서 전역 최적해가 l_{0} 목적 함수의 전역 최적해와 일치하는 성질을 갖기 때문이다.

13.7.4. Algorithms for ARD

자동 연관성 판별을 어떻게 구현할까?

13.7.4.1. EM algorithm

가장 쉬운 방법은 기대값 최대화이다. 기대완전데이터 로그가능도는 \mathbf{A} = \mathrm{diag}(\alpha_{j})라 할 때 Q(\mathbf{\alpha}, \beta) = \mathbb{E}[\log \mathcal{N}(\mathbf{y} | \mathbf{X}\mathbf{w}, \sigma^{2} \mathbf{I}) + \log \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathbf{A}^{-1})] = \frac{1}{2} N \log \beta - \frac{\beta}{2} (\lVert \mathbf{y} - \mathbf{X} \mathbf{\mu} \rVert^{2} + \mathrm{tr}(\mathbf{X}^{T} \mathbf{X} \mathbf{\Sigma})) + \frac{1}{2} \sum_{j} \log \alpha_{j} - \frac{1}{2} \mathrm{tr}[\mathbf{A}(\mathbf{\mu}\mathbf{\mu}^{T} + \mathbf{\Sigma})] + \mathrm{const}가 된다. 이 때 \mathbf{\mu}\mathbf{\Sigma}\mathbf{\alpha}, \beta로부터 추정한 사후분포의 매개변수값들이다.

\alpha_{j} \sim \mathrm{Ga}(a, b), \beta \sim \mathrm{Ga}(c, d)로 사전분포를 두면 징벌된 목적 함수는 Q^{\prime}(\mathbf{\alpha}, \beta) = Q(\mathbf{\alpha}, \beta) + \sum_{j} (a \log \alpha_{j} - b \alpha_{j}) + c \log \beta - d \beta이 된다. \frac{d Q^{\prime}}{d \alpha_{j}} = 0으로 두면 \alpha_{j} = \frac{1 + 2a}{m_{j}^{2} + \sigma_{jj} + 2b}가 된다. \alpha_{j} = \alpha들이 전부 일치하고 a = b = 0인 경우에는 이 업데이트는 \alpha = \frac{D}{\mathbf{\mu}^{T} \mathbf{\mu} + \mathrm{tr}(\mathbf{\Sigma})}이 되고, \beta에 대한 업데이트는 \beta = \frac{N + 2c}{\lVert \mathbf{y} - \mathbf{X} \mathbf{\mu} \rVert^{2} + \beta_{t-1}^{-1} \sum_{j} (1 - \alpha_{j} \sum_{jj}) + 2d}이 된다.

13.7.4.2. Fixed-point algorithm

더 빠르고 직접적인 접근법은 목적함수를 직접 최적화하는 것이다. 최적값 업데이트는 다음과 같다: \alpha_{j} = \frac{\gamma_{j} + 2a}{m_{j}^{2} + 2b}, \beta = \frac{N - \sum_{j} \gamma_{j} + 2c}{\lVert \mathbf{y} - \mathbf{X} \mathbf{\mu} \rVert^{2} + 2d}, \gamma_{j} = 1 - \alpha_{j} \sigma_{jj}.

이 때 \gamma_{j}w_{j}가 얼마나 데이터로부터 잘 판정되는지를 알려주는 지표이므로 \gamma = \sum_{j} \gamma_{j}는 모델의 자유도가 된다. \mathbf{\alpha}, \beta가 모두 \mathbf{\mu}, \mathbf{\Sigma}에 의존하므로 이 식들은 수렴할 때까지 재추정되어야 한다. 수렴 시에는 이 결과들은 기대값 최대화로 얻은 결과들과 같지만, 목적 함수가 볼록함수가 아니기 때문에 초기값에 의존하기도 한다.

13.7.4.3. Iteratively reweighted l_{1} algorithm

자동 연관성 판별 문제를 푸는 또 다른 접근법은 그것을 최대사후확률추정 문제로 보는 것이다. 로그 사전분포 그 자체는 복잡한 형태를 갖고 있어도 그를 \lvert w_{j} \rvert에 대한 비감소 볼록함수로 볼 수 있으므로 반복 재가중 l_{1} 문제 \mathbf{w}_{t+1} = \mathrm{argmin}_{\mathbf{w}} (\mathrm{NLL}(\mathbf{w}) + \sum_{j} \lambda_{j, t} \lvert w_{j} \rvert)을 푸는 것과 같다. \lambda_{j, 0} = 1로 초기화하고, 각 반복 단계에서 \lambda_{j, t + 1} = [\mathbf{X}_{:, j}(\sigma^{2} (\mathbf{I} + \mathbf{X} \mathrm{diag}(\frac{1}{\lambda_{j}}\mathrm{diag}(\lvert w_{j, t+1}\rvert))^{-1})\mathbf{X}^{T})^{-1} \mathbf{X}_{:, j}]^{\frac{1}{2}}로 업데이트한다. 이 때 새로운 징벌치 \lambda_{j}모든 가중치값에 의존한다는 점에서 적응적 라쏘법과는 다르다.

이 차이점을 이해하려면, 기본 가능해 (\mathbf{X} \mathbf{w} = \mathbf{y}를 만족하는 해)를 구했을 때 같은 성질을 만족하면서 훨씬 희소한 해를 구하고자 한다고 하자. 가중치가 작다고만 해서 징벌치를 증가시키는 것은 현재의 국소적 해에 더더욱 갇히게 되므로 도움이 되지 않는다. 그 대신, 가중치가 작으면서 \lVert \mathbf{w}_{t+1} \rVert < N으로 만드는 해의 징벌치를 증가시키는 것이 낫다. 이 역할을 하는 것은 공분산 항 (\mathbf{I} + \mathbf{X} \mathrm{diag}(\frac{1}{\lambda_{j}}\mathrm{diag}(\lvert w_{j, t+1}\rvert))^{-1}이다. \mathbf{w}가 기본 가능해이면 이 행렬은 꽉 찬 랭크이므로 징벌치는 별로 증가하지 않지만, \mathbf{w}가 N보다 희소하면 이 행렬은 꽉 찬 랭크가 아니므로 0의 값을 갖는 계수에 대한 징벌치들이 증가하여 희소해를 유도하게 된다.

13.7.5. ARD for logistic regression

이진 로지스틱 회귀 p(y | \mathbf{x}, \mathbf{w}) = \mathrm{Ber}(y | \mathrm{sigm}(\mathbf{w}^{T} \mathbf{x}))에 대해 같은 가우시안 사전분포 p(\mathbf{w}) = \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathbf{A}^{-1})을 사용한다면, 사전분포가 로지스틱 가능도함수에 켤레분포가 아니기 때문에 \mathbf{\alpha}에 기대값 최적화를 사용할 수 없다. 하나의 접근법은 E 단계에 변량 근사를 수행하는 것이고, 더 간단한 방법은 라플라스 근사를 사용하는 것이다. 이 때는 \beta를 업데이트할 필요가 없지만, 수렴한다는 보장을 잃게 된다. 또는 반복 재가중 l_{1} 문제를 풀 수도 있다.

13.8. Sparse coding

희소 사전분포를 지도학습뿐만 아니라 비지도학습에 쓰려면 어떻게 할까? 라플라스 분포같이 희소성을 유도하는 비가우시안 사전분포를 쓴다면 각각 관찰된 벡터 \mathbf{x}_{i}를 기저 벡터의 희소 결합으로 근사할 수 있다. 이 때 희소 패턴은 데이터에 따라 달라진다. 기저 벡터 집합 \mathbf{W}을 직교한다고 가정하면 희소 암호화법이 되는데, 이 때 인자 부하 행렬 \mathbf{W}사전, 이 행렬의 각 열은 원자로 불린다. 희소 표현의 관점에서 L > D인 경우가 흔한데, 이 경우 표현을 과완전이라 한다.

희소 암호화법에서 사전은 고정될 수도 있고 학습될 수도 있다. 고정된 경우 많은 자연적 신호를 적은 수의 선형결합으로 근사할 수 있는 파형이나 DCT 기저를 쓴다. 학습할 경우 가능도 \log p(\mathcal{D} | \mathbf{W}) = \sum_{i=1}^{N} \log \int_{\mathbf{z}_{i}} \mathcal{N}(\mathbf{x}_{i} | \mathbf{W} \mathbf{z}_{i}, \sigma^{2} \mathbf{I}) p(\mathbf{z}_{i}) d \mathbf{z}_{i}를 최대화시키는 방법을 쓴다.

희소 암호화법을 희소 주성분 분석과 헷갈리면 안 된다. 희소 주성분 분석은 희소화 사전분포를 회귀 가중치 \mathbf{W}에 적용하지만, 희소 암호화는 희소화 사전분포를 잠재 인자 \mathbf{z}_{i}에 적용한다. 하지만 이 두 방법은 결합될 수 있는데, 이를 희소 행렬 분해라 한다.

13.8.1. Learning a sparse coding dictionary

위의 로그 가능도는 직접 최대화시키기 힘든 목적 함수이기 때문에 다음의 근사를 이용하고는 한다. \log p(\mathcal{D} | \mathbf{W}) \simeq \sum_{i=1}^{N} \max_{\mathbf{z}_{i}} [\log \mathcal{N}(\mathbf{x}_{i} | \mathbf{W} \mathbf{z}_{i}, \sigma^{2} \mathbf{I}) + \log p(\mathbf{z}_{i})] 여기서 p(\mathbf{z}_{i})가 라플라스 분포라면, 음의 로그가능도는 \mathrm{NLL}(\mathbf{W}, \mathbf{Z}) = \sum_{i=1}^{N} (\frac{1}{2} \lVert \mathbf{x}_{i} - \mathbf{W} \mathbf{z}_{i} \rVert_{2}^{2} + \lambda \lVert \mathbf{z}_{i} \rVert_{1})이 된다. \mathbf{W}가 임의로 커지는 것을 막기 위해, 해당 열들의 l_{2} 놈을 1 이하로 제한하는 조건 \mathcal{C} = \{ \mathbf{W} \in \mathbb{R}^{D \times L} | \mathbf{w}_{j}^{T} \mathbf{w}_{j} \leq 1\}을 걸기도 하며, 이로부터 \min_{\mathbf{W} \in \mathcal{C}, \mathbf{Z} \in \mathbb{R}^{D \times L}} \mathrm{NLL}(\mathbf{W}, \mathbf{Z})을 풀게 된다. \mathbf{z}_{i}가 고정된 경우 \mathbf{W}에 대한 최적화는 단순한 선형 제곱 문제가 되고, \mathbf{W}가 고정된 경우 \mathbf{Z}에 대한 최적화는 라쏘 문제와 같다. 이에 따라 \mathbf{W}\mathbf{Z}를 번갈아 최적화하게 되는데 이를 분석-합성 반복이라고 하며, 이 알고리즘이 너무 느린 경우엔 다른 좀 더 복잡한 알고리즘들을 사용한다.

이와 비슷한 다른 여러 모델이 있다. 음이 아닌 행렬 분해(NMF) 문제는 \min_{\mathbf{W} \in \mathcal{C}, \mathbf{Z} \in \mathbb{R}^{L \times N}} [\frac{1}{2} \sum_{i=1} \lVert \mathbf{x}_{i} - \mathbf{W} \mathbf{z}_{i}\rVert_{2}^{2}] 목적 함수를 \mathbf{W} \geq 0, \mathbf{z}_{i} \geq 0의 조건에 대해 최적화하는 것이다. 이 모델에는 초매개변수가 없다. 이 조건을 쓰는 이유는 학습된 사전은 음이 아닌 성분의 음이 아닌 합으로 표현하는 것이 음일 수도 있고 양일 수도 있는 원자의 희소한 합으로 표현하는 것보다 더 낫다는 직관 때문이다. 물론 잠재 인자에 대해 희소화 사전분포를 쓰는 것을 병행할 수도 있다. 이를 음이 아닌 희소 암호화라 한다.

위에서 양수 조건을 없애는 대신 희소 조건을 도입할 수도 있는데 이를 희소 행렬 분해라 하며 \min_{\mathbf{W} \in \mathcal{C}, \mathbf{Z} \in \mathbb{R}^{L \times N}} \frac{1}{2} \sum_{i=1}^{N}[\lVert \mathbf{x}_{i} - \mathbf{W} \mathbf{z}_{i} \rVert_{2}^{2} + \lambda \lVert \mathbf{z}_{i} \rVert_{1}]\lVert \mathbf{w}_{j} \rVert_{2}^{2} + \gamma \lVert \mathbf{w}_{j} \rVert_{1} \leq 1의 조건하에 최적화시키는 것이다. 이의 여러 변형도 가능하며 음의 로그가능도 함수를 라쏘에서 그룹 라쏘나 융합 라쏘로 바꿀 수도 있다.

라플라스 분포 대신 다른 희소화 사전분포를 쓸 수도 있다. 베르누이 분포로부터 유도되는 이진 마스크 모델을 쓸 수도 있고, 베타 프로세스 같은 비 매개변수적 사전분포를 쓸 수도 있다 (이렇게 하면 크기 제한 없는 사전에 대한 모델이 만들어진다). 깁스 샘플링이나 변량 베이스같은 모델을 써서 베이지안 추론을 할 수 있다. 이 때는 노이즈가 커질수록 사전의 유효 크기는 작아지며, 이것이 과적합을 방지하게 된다.

13.8.2. Results of dictionary learning from image patches

자연적 이미지의 패치들을 단순한 시각적 필터로 이루어진 기저 벡터들의 희소 결합으로 나타낼 수 있는데 이 필터들은 주로 선이나 줄을 감지하는 필터가 된다. 흥미롭게도, 독립 성분 분석을 적용해도 비슷한 결과가 나오지만, 주성분 분석은 별로 좋은 결과가 나오지 않는다.

13.8.3. Compressed sensing

희소 암호화에서 사전을 통한 접근법은 그렇게 유용하지는 않다. 데이터 \mathbf{x}를 관찰하는 대신, 그의 저차원에 대한 사영 \mathbf{y} = \mathbf{R} \mathbf{x} + \mathbf{\epsilon}을 관찰해 보자. 사영 행렬 \mathbf{R}은 안다고 가정한다. 목표는 p(\mathbf{x} | \mathbf{y}, \mathbf{R})을 추론하는 것이다. 이 때는 적절한 사전분포에 대해 베이지안 추론을 사용하여 자연적 신호는 기저함수들의 가중치합으로 나타낼 수 있음을, 즉 \mathbf{W}가 사전이고 \mathbf{z}가 희소한 사전분포일 때 \mathbf{x} = \mathbf{W} \mathbf{z}를 가정하는 것이다. 이를 압축 감지라 한다.

압축 감지가 동작하려면 기저 함수를 잘 정해야 하며 그렇지 않으면 해가 희소하지 않게 된다. 사전을 고정시킬 수도 있지만 희소 암호화를 이용해 컨텍스트에 맞는 사전을 학습시키는 것이 성능이 좋다. 감지 행렬 \mathbf{R}은 무작위로 정하기도 하지만 사전에 대해 사영시키는 것이 성능이 좋다.

13.8.4. Image impainting and denoising

텍스트가 덮어씌워져 있거나 금이 가 있는 식으로 손상된 이미지가 있을 때 원본 이미지를 복원하는 것을 이미지 덧그림 또는 이미지 잡음 제거라 한다. 이는 압축 감지의 특수한 경우로 볼 수 있는데, 이미지를 서로 겹치는 조각 \mathbf{y}_{i}들로 분할하고 그를 \mathbf{y}로 이어붙이는 것이다. 이후 \mathbf{R}을 각각의 조각에 사영하는 행렬로 정의하고 \mathcal{V}\mathbf{y}의 오염되지 않은 성분들로, \mathcal{H}를 숨겨진 성분들로 정의한다. 이미지 덧그림을 위해서는 p(\mathbf{y}_{\mathcal{H}} | \mathbf{y}_{\mathcal{V}}, \mathbf{\theta})을 계산하는데, 여기서 \mathbf{\theta}는 사전 \mathbf{W}와 희소도 \lambda를 정하는 모델 매개변수이다. 사전은 이미지의 데이터베이스로부터 오프라인으로 학습될 수도 있고 오염되지 않은 원본 이미지 자체로부터 학습될 수도 있다.

또는 그래프 모델 (전문가 영역 모델)을 사용해 잠재 변수 모델을 쓰는 대신 인접 이미지 조각간 상호 연관 관계를 암호화할 수도 있지만, 계산 복잡도가 더 크게 든다.

요점 정리

  • 희소 가중치 모델 : 특성은 많고 학습 데이터는 적고 특성 중 여럿이 0인 모델.
  • 베이지안 변수 선택 : 특성 각각을 비트 벡터로 삼아 희소성을 모델링.
  • l_{1} 정규화 : 희소성을 유도하는 정규화. 선형 회귀에 적용하면 라쏘 회귀가 된다.
  • l_{1} 정규화를 계산하는 데는 좌표 하강법, LARS 법 등의 알고리즘이 쓰인다.
  • l_{1} 정규화를 확장하여 그룹 라쏘, 융합 라쏘 등의 알고리즘을 만들 수 있다.
  • 비슷한 방식을 비볼록 정규화자 함수에도 적용할 수 있다.
  • 자동 연관성 판별 : 실측 베이스를 이용한 희소 가중치 모델 피팅.
  • 희소 암호화 : 관측을 직교 기저 벡터들의 희소 결합으로 표현.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중