8. Logistic Regression

8.1. Introduction

p(y, \mathbf{x}) = p(y)p(\mathbf{x} | y)의 결합 모델을 만든 뒤 이를 관찰된 특성 \mathbf{x}에 대해 조건을 걸어 클래스 사후분포 p(y | \mathbf{x})을 유도하는 것을 생성적 분류기라 하고, 직접적으로 p(y | \mathbf{x})을 피팅하는 것을 구별적 분류기라 한다. 이 장에선 매개변수에 대해 선형인 구별적 분류기를 다룬다.

8.2. Model specification

로지스틱 회귀는 다음의 이진 분류 모델이다.

p(y | \mathbf{x}, \mathbf{w}) = \mathrm{Ber}(y | \mathrm{sigm}(\mathbf{w}^{T}\mathbf{x}))

이 확률 경계를 0.5로 두면 \mathbf{w}를 법선으로 두는 선형 결정 경계를 얻게 된다.

  • 로지스틱 회귀는 구현하기 쉽고 피팅하기 대단히 빠르다.
  • 로지스틱 회귀는 로그 확률 \mathrm{LO} = \log \frac{p(y=1 | \mathbf{x})}{ p(y=0 | \mathbf{x}) } = \mathbf{w}^{T} \mathbf{x} \mathbf{w}에 대해 선형이 되므로 표현하기도 쉽다.
  • 로지스틱 회귀는 다클래스 분류로 확장하기 쉽다.
  • 로지스틱 회귀는 비선형 결정 경계로 확장하기 쉽다.

8.3. Model fitting

8.3.1. MLE

\mu_{i} = \mathrm{sigm}(\mathbf{w}^{T} \mathbf{x}_{i})라 할 때 로지스틱 회귀의 음의 로그가능도는 다음과 같다.

\mathrm{NLL}(\mathbf{w}) = -\sum_{i=1}^{N} [y_{i} \log \mu_{i} + (1-y_{i}) \log(1-\mu_{i})]

이를 교차 엔트로피 오차 함수라고도 한다.

선형 회귀와 달리 로지스틱 회귀는 최대가능도근사를 닫힌 형태로 쓰는 것이 불가능하다. 그 대신에 최적화 알고리즘을 통해 이를 근사하며, 이를 위해 그라디언트와 헤시안을 다음과 같이 계산한다.

\mathbf{g} = \mathbf{X}^{T}(\mathbf{\mu} - \mathbf{y})

\mathbf{H} = \mathbf{X}^{T}\mathbf{S}\mathbf{X}

여기서 \mathbf{S} = \mathrm{diag}(\mu_{i}(1-\mu_{i}))이다. 헤시안은 양의 정부호가 되므로 음의 로그가능도는 볼록함수이고 최소값은 유일하다.

8.3.2. Steepest descent

제한되지 않은 최적화의 가장 단순한 방법은 그라디언트 하강 또는 급경사 하강이다. 이는 \mathbf{\theta}_{k+1} = \mathbf{\theta}_{k} - \eta_{k} \mathbf{g}_{k} 이며, \eta_{k}계단 크기 또는 학습률이라 한다. 계단 크기를 어떻게 결정하는가? 너무 작으면 수렴이 늦을 것이고 너무 크면 수렴하지 않을 것이다. 시작 지점에 상관없이 국소 최적점으로 수렴(전역 수렴)하려면 어떻게 할까? \eta\phi(\eta) = f(\mathbf{\theta}_{k} + \eta \mathbf{d}_{k})를 최소화하도록 잡으면 테일러 정리에 의해 \eta가 적당히 작을 경우 수렴이 보장된다. 이를 선 최적화(선 탐색)이라 한다.

선 탐색으로 찾은 \eta\phi^{\prime}(\eta) = \mathbf{d}^{T} \mathbf{g} (여기서 \mathbf{g} = f^{\prime}( \mathbf{\theta} + \eta \mathbf{d}))에 대해 \mathbf{g} = \mathbf{0}이 되거나 \mathbf{d} \perp \mathbf{g}가 되기 때문에 지그재그 형태의 이동을 보인다. 이를 방지하기 위해 모멘텀 항을 붙여 \mathbf{\theta}_{k+1} = \mathbf{\theta}_{k} - \eta_{k} \mathbf{g}_{k} + \mu_{k} ( \mathbf{\theta}_{k+1} - \mathbf{\theta}_{k}) 가 되도록 할 수 있는데, 이를 무거운 공 방법이라고 한다. 지그재그 이동을 피하기 위해 켤레 그라디언트 f(\mathbf{\theta}) = \mathbf{\theta}^{T} \mathbf{A} \mathbf{\theta}를 사용하는 방법도 있으나 자주 쓰이지는 않는다.

급경사 하강법의 예시.

8.3.3. Newton’s method

곡률(헤시안)을 이용한 이차 최적화 방법은 더 빠른데, 그 예로 뉴턴법이 있다. 이는 \mathbf{\theta}_{k+1} = \mathbf{\theta}_{k} - \eta_{k} \mathbf{H}_{k}^{-1} \mathbf{g}_{k} 을 반복적으로 업데이트하는 것이다. 이 때 \mathbf{H}_{k}는 양의 정부호여야 하는데, 그렇게 되지 않는다면 음수를 취하면 된다.

볼록함수와 비볼록함수에서의 뉴턴법.

르벤버그-마르카르트 알고리즘은 뉴턴법과 급경사하강을 섞은 방법으로 비선형 최소제곱 문제를 풀 때 많이 쓰인다. 또는 \mathbf{H}_{k}^{-1} \mathbf{g}_{k} 를 풀 때 켤레 그라디언트를 쓸 수 있는데, 헤시안이 양의 정칙일 때까지만 알고리즘을 반복하고 양의 정부호가 아니라면 중단하는 방법을 중단 뉴턴법이라 한다.

8.3.4. Iteratively reweighted least squares(IRLS)

뉴턴법으로 이진 로지스틱 회귀의 최대가능도근사를 해 보자. 헤시안이 정칙이므로 \eta_{k} = 1을 쓰면, 반응 벡터 \mathbf{z}_{k} = \mathbf{X} \mathbf{w}_{k} + \mathbf{S}_{k}^{-1} (\mathbf{y} - \mathbf{\mu}_{k}) 일 때 \mathbf{w}_{k+1} = \mathbf{w}_{k} - \mathbf{H}^{-1}\mathbf{g}_{k} = (\mathbf{X}^{T} \mathbf{S}_{k} \mathbf{X})^{-1} \mathbf{X}^{T} \mathbf{S}_{k} \mathbf{z}_{k} 가 된다.

이는 가중 최소제곱 문제로서 \sum_{i=1}^{N} S_{ki}(z_{ki} - \mathbf{w}^{T} \mathbf{x}_{i})^{2} 를 최소화하는 문제가 된다. \mathbf{S}_{k}는 대각행렬이므로 이는 z_{ki} = \mathbf{w}_{k}^{T} \mathbf{x}_{i} + \frac{y_{i} - \mu_{ki}}{\mu_{ki} (1 - \mu_{ki})} 를 최소화하는 문제로 분해할 수 있는데, 이를 반복 재가중 최소제곱(IRLS)이라 한다.

8.3.5. Quasi-Newton (variable metric) methods

뉴턴법의 단점은 헤시안을 계산하는 데 오래 걸린다는 점이다. 유사-뉴턴법은 그라디언트를 통해 헤시안을 근사한다. 가장 널리 알려진 방법은 BFGS법으로 \mathbf{B}_{k} \approx \mathbf{H}_{k}를 다음과 같이 업데이트한다.

\mathbf{B}_{k+1} = \mathbf{B}_{k} + \frac{\mathbf{y}_{k} \mathbf{y}_{k}^{T} }{ \mathbf{y}_{k}^{T} \mathbf{s}_{k}} - \frac{( \mathbf{B}_{k}  \mathbf{s}_{k} )( \mathbf{B}_{k}  \mathbf{s}_{k} )^{T}}{ \mathbf{s}_{k}^{T} \mathbf{B}_{k}  \mathbf{s}_{k} }

\mathbf{s}_{k} = \mathbf{\theta}_{k} - \mathbf{\theta}_{k-1}

\mathbf{y}_{k} = \mathbf{g}_{k} - \mathbf{g}_{k-1}

이는 행렬에 대한 랭크 2 업데이트이며 양의 정부호성을 유지한다. 아니면 \mathbf{C}_{k} \approx \mathbf{H}_{k} 를 다음과 같이 근사할 수도 있다:

\mathbf{C}_{k+1} = (\mathbf{I} - \frac{\mathbf{s}_{k} \mathbf{y}_{k}^{T} }{ \mathbf{y}_{k}^{T} \mathbf{s}_{k}})\mathbf{C}_{k}  (\mathbf{I} - \frac{\mathbf{y}_{k} \mathbf{s}_{k}^{T} }{ \mathbf{y}_{k}^{T} \mathbf{s}_{k}}) +  \frac{\mathbf{s}_{k} \mathbf{s}_{k}^{T} }{ \mathbf{y}_{k}^{T} \mathbf{s}_{k}}

헤시안을 직접 저장하는 것은 O(D^{2}) 만큼의 메모리가 들기 때문에, 큰 문제에서는 메모리 제한 BFGS(L-BFGS)을 사용해 헤시안이나 역 헤시안을 대각 행렬 + 저 랭크 행렬로 근사하기도 한다. 이 때 \mathbf{H}^{-1}\mathbf{g}_{k} 은 가장 최근의 \mathbf{s}_{k}, \mathbf{y}_{k}들의 내적만 활용하게 되며 공간복잡도는 O(mD)가 된다. 보통 m \sim 20 정도면 충분하다.

8.3.6. l_{2} regularization

선형 회귀에서 능선 회귀를 하는 것처럼, 로지스틱 회귀에서도 l_{2} 정규화가 필요하다. 특히 데이터가 선형 분리가 가능할 때, 최대가능도근사는 선형 임계 유닛이 되는데, 이는 학습 데이터에 확률을 몰아버리므로 과적합이 되어 일반화가 잘 되지 않는다. 이를 방지하기 위해 l_{2} 정규화를 하면 목적, 그라디언트, 헤시안 함수가 다음과 같아진다.

f_{L}(\mathbf{w}) = \mathrm{NLL}(\mathbf{w}) + \lambda \mathbf{w}^{T} \mathbf{w}

\mathbf{g}_{L}(\mathbf{w}) = \mathbf{g}(\mathbf{w}) + 2 \lambda \mathbf{w}

\mathbf{H}_{L}(\mathbf{w}) = \mathbf{H}(\mathbf{w}) + 2 \lambda \mathbf{I}

기존 알고리즘에 이를 대입하기만 하면 된다.

8.3.7. Multi-class logistic regression

다항 로지스틱 회귀(최대 엔트로피 분류기)를 고려해 보자. 이는 다음의 모델이다:

p(y = c | \mathbf{x}, \mathbf{W}) = \frac{e^{\mathbf{w}_{c}^{T} \mathbf{x}}}{\sum_{c'=1}^{C}  \mathbf{w}_{c'}^{T} \mathbf{x} } 여기서 \mathbf{w}_{c}\mathbf{W}의 c번째 열이다.

이를 약간 변형한 조건부 로짓 모델은 각각의 데이터에 대해 서로 다른 클래스의 세트들을 표준화한다. 이는 사용자가 제공되는 아이템들을 묶어서 선택을 할 때 (ex. 물건들을 골라서 만드는 장바구니)를 모델링하는 데 유용하다.

\mu_{ic} = p(y_{i} = c | \mathbf{x}_{i}, \mathbf{W}) 라 하면 음의 로그가능도는

f(\mathbf{W}) = -\sum_{i=1}^{N} [(\sum_{c=1}^{C} y_{ic} \mathbf{w}_{c}^{T} \mathbf{x}_{i}) - \log (\sum_{c'=1}^{C} e^{\mathbf{w}_{c'}^{T} \mathbf{x}_{i}})] 이다.

크로네커 곱\mathbf{A} \otimes \mathbf{B}로 표기하면 그라디언트와 헤시안은 다음과 같다:

\mathbf{g}(\mathbf{W}) = \nabla f(\mathbf{W}) = \sum_{i=1}^{N} (\mathbf{\mu}_{i} - \mathbf{y}_{i}) \otimes \mathbf{x}_{i}

\mathbf{H}(\mathbf{W}) = \nabla^{2} f(\mathbf{W}) = \sum_{i=1}^{N} (\mathrm{diag}(\mathbf{\mu}_{i}) - \mathbf{\mu}_{i}\mathbf{\mu}_{i}^{T} ) \otimes (\mathbf{x}_{i}\mathbf{x}_{i}^{T})

이제 정규화 케이스, 즉 사전분포 p(\mathbf{W}) = \prod_{c} \mathcal{N}(\mathbf{w}_{c} | \mathbf{0}, \mathbf{V}_{0})을 도입하는 경우를 고려해 보자. 이 경우 목적, 그라디언트, 헤시안 함수는 다음과 같다.

f_{L}(\mathbf{W}) = f(\mathbf{W}) + \frac{1}{2} \sum_{c} \mathbf{w}_{c} \mathbf{V}_{0}^{-1} \mathbf{w}_{c}

\mathbf{g}_{L}(\mathbf{W}) = \mathbf{g}(\mathbf{W}) + \mathbf{V}_{0}^{-1} (\sum_{c} \mathbf{w}_{c})

\mathbf{H}_{L}(\mathbf{W}) = \mathbf{H}(\mathbf{W}) + \mathbf{I}_{C} \otimes \mathbf{V}_{0}^{-1}

이 때 헤시안의 공간복잡도는 O(C^{2}D^{2})이므로 메모리 제한 BFGS이 뉴턴법보다 많이 쓰인다.

8.4. Bayesian logistic regression

로지스틱 회귀에는 적절한 켤레사전분포가 없으므로 사후분포를 정확히 계산할 수는 없다. 그 대신에 근사해야 한다.

8.4.1. Laplace approximation

사후분포에 대한 가우시안 근사 (안장점 근사)는 어떻게 할까? 에너지 함수(음의 로그 사후분포) E(\mathbf{\theta}) = -\log p(\mathbf{\theta}, \mathcal{D}) 에 대해 p(\mathbf{\theta} | \mathcal{D}) = \frac{1}{p(\mathcal{D})} e^{-E(\mathbf{\theta})}로 놓을 수 있다. 이 때 사후분포의 최빈값 (즉, 최저 에너지 상태)를 \mathbf{\theta}^{\ast} 이라 하면 테일러 전개에 의해 E(\mathbf{\theta}) \approx  E(\mathbf{\theta}^{\ast}) + (\mathbf{\theta} - \mathbf{\theta}^{\ast})^{T} \mathbf{g} + \frac{1}{2} (\mathbf{\theta} - \mathbf{\theta}^{\ast})^{T}  \mathbf{H} (\mathbf{\theta} - \mathbf{\theta}^{\ast}) 이 된다. 최빈값의 정의에 의해 그라디언트는 0이므로,

\hat{p}(\mathbf{\theta} | \mathcal{D}) \propto \mathcal{N}(\mathbf{\theta} | \mathbf{\theta}^{\ast}, \mathbf{H}^{-1}) 이 성립하게 된다. 이를 라플라스 근사라 한다.

8.4.2. Derivation of the Bayesian information criterion (BIC)

로그 주변가능도에 대한 라플라스 근사는 다음과 같이 다시 쓸 수 있다.

\log p(\mathcal{D}) \approx \log p(\mathcal{D} | \mathbf{\theta}^{\ast}) + \log p(\mathbf{\theta}^{\ast}) - \frac{1}{2} \log \lvert \mathbf{H} \rvert

균등사전분포를 사용한다면 2번째 항은 없어진다. 3번째 항 (오컴 인자)는 모델의 복잡도를 측정하는 지표로서 헤시안이 풀 랭크라면 \log \lvert \mathbf{H} \rvert = D \log N + \log \lvert \hat{\mathbf{H}} \rvert가 된다. (D = \mathrm{dim}(\mathbf{\theta})) \log \lvert \hat{\mathbf{H}} \rvert는 N에 독립적이므로 이를 무시하면 5.3.2.4.에서 봤던 BIC 스코어 식을 얻는다:

\log p(\mathcal{D}) \approx \log p(\mathcal{D} | \mathbf{\theta}^{\ast}) - \frac{D}{2} \log N

8.4.3. Gaussian approximation for logistic regression

로지스틱 회귀에 대한 가우시안 근사는 어떻게 할까? 가우시안 사전분포 p(\mathbf{w}) = \mathcal{N}(\mathbf{w} | \mathbf{0}, \mathbf{V}_{0}) 이라 하면 사후분포의 근사 p(\mathbf{w} | \mathcal{D}) \approx \mathcal{N}(\mathbf{w} | \hat{\mathbf{w}}, \mathbf{H}^{-1}) 은 다음과 같아진다:

\hat{\mathbf{w}} = \mathrm{argmin}_{\mathbf{w}} -(\log p(\mathcal{D} | \mathbf{w}) + \log p(\mathbf{w}))

\mathbf{H} = \nabla^{2}  -(\log p(\mathcal{D} | \mathbf{w}) + \log p(\mathbf{w})) |_{ \hat{\mathbf{w}} }

선형 분리 가능한 2D 데이터에서는 최대가능도근사가 계단 함수가 되므로 잘 정의되지 않는다. 구형 가우시안 사전분포를 도입하면 최적해가 “무한으로 치솟는” 문제가 해결된다.

8.4.4. Approximating the posterior predictive

사후예측분포 p(y | \mathbf{x}, \mathcal{D}) = \int p(y | \mathbf{x}, \mathbf{w})p(\mathbf{w} | \mathcal{D}) d \mathbf{w} 는 로지스틱 회귀에서 계산 가능하지 않다. 가장 간단한 근사는 대입 근사이다. 이진 분류의 경우에는 p(y = 1 | \mathbf{w}, \mathcal{D}) \approx p(y = 1 | \mathbf{x}, \mathbb{E}[\mathbf{w}]) 로 근사할 수 있다 (\mathbb{E}[\mathbf{w}] 은 사후평균으로 베이즈 점이 된다).

당연하게도 이런 대입 근사는 불확실성을 잘 측정하지 못한다. 더 나은 방법은 없을까?

8.4.4.1. Monte Carlo approximation

더 나은 방법으로는 몬테 카를로 방법이 있다. \mathbf{w}_{s} \sim p(\mathbf{w} | \mathcal{D})이 사후분포로부터의 표본일 때

p(y = 1 | \mathbf{x}, \mathcal{D}) \approx \frac{1}{S} \sum_{s=1}^{S} \mathrm{sigm} (\mathbf{w}_{s}^{T} \mathbf{x}) 로 근사하는 것이다. 이렇게 하면 여러 관측으로부터의 평균을 내게 되므로 결정 경계가 직선이 되더라도 사후예측밀도함수는 선형이 아니게 된다.

8.4.4.2. Probit approximation (moderated output)

사후분포에 대한 가우시안 근사 p(\mathbf{w} | \mathcal{D}) \approx \mathcal{N}(\mathbf{w} | \mathbf{m}_{N}, \mathbf{V}_{N}) 이 있을 때 이를 다음과 같이 근사할 수 있다. 이진 분류의 경우:

p(y = 1 | \mathbf{x}, \mathcal{D}) \approx \int \mathrm{sigm}(a) \mathcal{N}(a|\mu, \sigma^{2}) da

a = \mathbf{w}^{T} \mathbf{x} , \mu = \mathbb{E}[a] = \mathbf{m}_{N}^{T} \mathbf{x} , \sigma^{2} = \mathrm{var}[a] = \mathbf{x}^{T} \mathbf{V}_{N} \mathbf{x}

이를 근사하려면 어떻게 할까? 프로빗 함수 \Phi(a) = \int_{-\infty}^{a} \mathcal{N} (x | 0, 1) dx 에 대해 \int \Phi(\lambda a) \mathcal{N}(a | \mu, \sigma^{2}) da = \Phi(\frac{\mu}{\sqrt{\sigma^{2} + \lambda^{-2}}}) 가 되는 성질을 이용한다면 \mathrm{sigm}(a) \approx \Phi(\lambda a) 이 되므로

\int \mathrm{sigm}(a) \mathcal{N}(a|\mu, \sigma^{2}) da \approx \mathrm{sigm}(\mu \sqrt{1 + \frac{\pi \sigma^{2}}{8}})

로 근사할 수 있다. 이를 완화된 출력이라 하는데, 이 이유는 해당 근사가 대입 근사 \mathrm{sigm}(\mu) 값 이하이므로 대입 근사와는 같은 결정 경계를 가져 오감지율은 동일하게 되지만 로그 가능도는 더 완화된 값을 내기 때문이다.

8.4.5. Residual analysis (outlier detection)

잔차 분석(케이스 분석)은 이상치를 감지할 때 유용하다. 이는 \hat{y}_{i} = \hat{\mathbf{w}}^{T} \mathbf{x}_{i} 일 때 r_{i} = y_{i} - \hat{y}_{i} \sim \mathcal{N}(0, \sigma^{2}) 를 계산함으로써 이루어진다. 해당 값들의 가우시안 분포에 대한 실측 사분위수를 나타내는 qq-플롯을 찍으면 직선에 대해 크게 벗어나는 값들을 이상치라 할 수 있다.

이러한 고전적인 방법은 이진 분류에 대해서는 잘 작동하지는 못하는데, 이는 테스트 통계량이 점근적으로 가우시안이 된다는 전제를 하기 때문이다. 하지만 베이지안식 접근법에서는 이상치들을 p(y_{i} | \hat{y}_{i})가 작은 값들로 정의할 수 있다. 또는 이상치들을 사후예측분포의 교차검증확률 p(y_{i} | \mathbf{x}_{i}, \mathbf{x}_{-i}, \mathbf{y}_{-i}) = \int p(y_{i} | \mathbf{x}_{i} , \mathbf{w}) \prod_{j \neq i} p(y_{j} | \mathbf{x}_{j}, \mathbf{w}) p(\mathbf{w}) d \mathbf{w} 이 작은 값들로 정의할 수도 있다.

8.5. Online learning and stochastic optimization

고전적인 기계학습에서는 데이터의 배치에 대해 f(\mathbf{\theta}) = \frac{1}{N} \sum_{i=1}^{N} f(\mathbf{\theta}, \mathbf{z}_{i}) 을 최적화하는 오프라인 학습을 다룬다. 그러나 스트림 형태의 데이터에 대해서는 온라인 학습을 해야 한다.

8.5.1. Online learning and regret minimization

각 단계의 입력 샘플 \mathbf{z}_{k}에 대해 출력 매개변수 근사 반응 \mathbf{\theta}_{k}을 내어야 한다 할 때, 온라인 학습에서의 목적 함수는 후회도로 정의된다. 이것은 지금까지 계산한 손실함수들의 평균에서, 손실함수를 최소화하는 매개변수 근사값을 대입했을 때의 손실을 뺀 것이며, \mathrm{regret}_{k} = \frac{1}{k} \sum_{t=1}^{k} f(\mathbf{\theta}_{t}, \mathbf{z}_{t}) - \min_{\mathbf{\theta}_{\ast} \in \Theta}  \frac{1}{k} \sum_{t=1}^{k} f(\mathbf{\theta}_{\ast}, \mathbf{z}_{t}) 로 정의된다.

후회도를 최소화하는 온라인 학습에서의 간단한 알고리즘은 온라인 그라디언트 하강법으로, 각 단계에서 파라미터를 \mathbf{\theta}_{k+1} = \mathrm{proj}_{\Theta}(\mathbf{\theta}_{k} - \eta_{k} \mathbf{g}_{k}) 로 업데이트하는 것이다. 아래에서 후회도 최소화와 전통적인 목적 함수(최대가능도근사 같은)가 어떻게 관련이 있는지 보자.

8.5.2. Stochastic optimization and risk minimization

과거의 후회도를 최소화하는 대신, 미래의 기대손실 f(\mathbf{\theta}) = \mathbb{E}[f(\mathbf{\theta}, \mathbf{z})] 을 최소화한다고 하자. 이처럼 목적함수의 변수 중 일부가 확률변수인 경우를 추계적 최적화라고 한다.

분포로부터 무한정의 데이터 스트림이 도달할 때, 추계적 목적 함수를 최적화하는하나의 방법은 각 단계마다 목적 함수를 업데이트하는 것이다. 이를 추계적 그라디언트 하강법이라 하며, 단일 매개변수를 최적화할 경우 \bar{\mathbf{\theta}}_{k} =  \bar{\mathbf{\theta}}_{k-1}  - \frac{1}{k} ( \bar{\mathbf{\theta}}_{k-1} - \mathbf{\theta}_{k} ) 로 업데이트할 수 있다. 이를 폴야크-루퍼트 평균법이라 한다.

8.5.2.1. Setting the step size

추계적 그라디언트 하강법은 수렴이 보장되지 않는다. 수렴이 보장되기 위한 학습률의 조건은 로빈스-몬로 조건으로, 학습률의 스케쥴\sum_{k=1}^{\infty} \eta_{k} = \infty , \sum_{k=1}^{\infty} \eta_{k}^{2} < \infty 을 만족하면 된다. 이렇게 학습률을 보정해줘야 하는 것은 추계적 그라디언트 하강법의 단점인데, 간단한 휴리스틱은 데이터의 부분집합 하나에 대해 여러 학습률을 시도해본 뒤 가장 빠르게 목적함수가 감소하는 학습률을 택해 나머지 데이터에도 적용시키는 것이다. 이것은 수렴을 보장하지는 않지만 적당한 지점에서 알고리즘을 멈출 수 있다 (빠른 중단).

8.5.2.2. Per-parameter step sizes

추계적 그라디언트 하강법의 또 다른 단점은 모든 매개변수에 대해 같은 학습률을 사용한다는 것이다. 이에 대한 대안으로 에이다그라드(적응적 그라디언트)를 택할 수 있으며, 이는 \theta_{i, k+1} = \theta_{i, k} - \eta \frac{g_{i, k}}{\tau_{0} + \sqrt{\sum_{t=1}^{k} g_{i, t}^{2} }} 로 매개변수를 업데이트한다. 이는 후회도 최소화를 위해 도입되었지만, 일반적인 경우에도 쓸 수 있다.

8.5.2.3. SGD compared to batch learning

데이터 스트림이 무한정이 아니라면, 학습 데이터에서 데이터를 샘플링해 이를 시뮬레이트할 수 있다. 보통은 데이터를 무작위로 섞은 뒤 추계적 그라디언트 하강법을 행하는데, 이 과정에서 전체 데이터 셋을 한 번 통과하는 것을 에포크라 한다. 오프라인 학습에서는, 데이터를 B개씩 미니배치로 묶어 계산할 수 있다. B = 1일 때는 추계적 그라디언트 하강이고, B = N일 때는 급경사 그라디언트 하강이다. 보통은 B ~ 100 정도가 쓰인다.

많은 데이터 셋에서도 SGD(추계적 그라디언트 하강)은 꽤 좋은 성능을 보이고는 하는데, 이는 그라디언트는 몇 개의 데이터로 근사해도 정확도가 괜찮기 때문에, 모든 데이터셋을 전부 고려해 그라디언트를 매 단계마다 계산하는 것은 낭비에 가깝기 때문이다. 속도뿐만 아니라, SGD는 국소적 최적점에 갇힐 위험도 적다. 보통은 SGD를 통해 매개변수를 초기화시키고 L-BFGS 등을 통해 배치 최적화를 하고는 한다.

8.5.3. The LMS algorithm

선형 회귀의 최대가능도근사를 온라인 학습에서 찾으려면 어떻게 할까? k번째 단계에서 온라인 그라디언트는 \mathbf{g}_{k} = \mathbf{x}_{k} (\mathbf{\theta}_{k}^{T} \mathbf{x}_{k} - y_{k}) 이 된다. 그라디언트를 계산한 뒤에는 \mathbf{\theta}_{k+1} = \mathbf{\theta}_{k} - \eta_{k} \mathbf{g}_{k}와 같이 매개변수를 업데이트한다. (조건이 걸리지 않은 최적화이므로 매개변수 업데이트에서 온라인 학습과 같은 정사영은 불필요하다). 이를 최소평균제곱법(LMS), 델타 룰, 위드로우-호프 룰이라고도 한다.

LMS 알고리즘의 도식화.

LMS 알고리즘이 최적점을 찾으려면 데이터 셋을 여러 번 패스해야 한다. 이에 반해 칼만 필터같은 2차 정보를 쓰는 재귀적 최소제곱법은 한 번의 패스로도 최적화할 수 있는데, 이는 나중에 다룬다.

8.5.4. The perceptron algorithm

이진 로지스틱 회귀의 온라인 버전을 생각해 보자. 가중치 업데이트는 \mu_{k} = p(y_{k} = 1 | \mathbf{x}_{k}, \mathbf{\theta}_{k}) 라 할 때 \mathbf{\theta}_{k+1} = \mathbf{\theta}_{k} - \eta_{k+1}(\mu_{k+1} - y_{k+1}) \mathbf{x}_{k+1} 의 형태로 이루어지며, 이는 LMS 알고리즘와 같은 형태임을 알 수 있다 (사실 이 식은 모든 일반화된 선형 모델에 대해 성립한다).

여기에 대한 근사는, \hat{y}_{i} = \mathrm{argmax}_{y \in \{0,1\}} p(y | \mathbf{x}_{i}, \mathbf{\theta})이라 할 때 그라디언트를 \mathbf{g}_{i} \approx (\hat{y}_{i} - y_{i})\mathbf{x}_{i} 로 근사할 수 있다. 각각의 단계에서 가중치 벡터의 업데이트는 그라디언트를 더함으로써 이루어지는데, 이는 예측값이 맞게 되면 그라디언트가 0이 되므로 더 이상 업데이트가 되지 않으며, 예측값이 틀리게 되면 학습율에 2가 곱해진 뒤 업데이트가 된다. 이 과정을 퍼셉트론 알고리즘이라 하며, 이는 데이터가 선형 분리 가능하면 수렴이 보장된다. 데이터가 선형 분리가능하지 않다면 수렴이 보장되지 않으며 수렴한다고 해도 느리다.

로지스틱 회귀를 학습하는 데에는 퍼셉트론 알고리즘보다 더 좋은 알고리즘이 많지만 (SGD, IRLS 등), 퍼셉트론 알고리즘의 역사적 의의는 그것이 아날로그 하드웨어에서 가장 최초로 구현된 기계학습 알고리즘이라는 것이다. 또한, 주변분포 계산이 최대사후확률분포근사보다 쉬울 때에도 쓸 수 있다.

8.5.5. A Bayesian view

온라인 학습의 또 다른 방법은 베이지안 방식을 적용시키는 것이다. 이는 p(\mathbf{\theta} | \mathcal{D}_{1 : k}) \propto p(\mathcal{D}_{k} | \mathbf{\theta}) p(\mathbf{\theta} | \mathcal{D}_{1 : k-1}) 을 연속적으로 적용하는 것이다. 이는 사후분포 전체를 계산하므로 점 근사에 대해 불확실성을 더 잘 모델링하고, 초매개변수에 대해서도 온라인 학습을 할 수 있다. 교차검증법은 온라인 학습에는 쓸 수 없기 때문에 이 방식은 의미가 있다. 또한 SGD에 비해 빠를 때도 있다. 간단한 예로는 칼만 필터 등의 모델이 있다.

8.6. Generative vs discriminative classifiers

구별적 분류기를 학습시킬 때는 조건부 로그가능도 \sum_{i=1}^{N} \log p(y_{i} | \mathbf{x}_{i}, \mathbf{\theta}) 을 최대화시키는 반면, 생성적 분류기를 학습시킬 때는 결합 로그가능도 \sum_{i=1}^{N} \log p(y_{i}, \mathbf{x}_{i} | \mathbf{\theta}) 을 최대화시킨다는 차이가 있다.

가우시안 판별식 분석하의 클래스 사후분포는 로지스틱 회귀와 같다. 역은 성립하지 않으므로 가우시안 판별식 가정은 로지스틱 회귀 가정보다 더 강한 조건이다. 가우시안 판별식 가정이 성립할 때에는 로지스틱 회귀에 비해 학습 데이터가 덜 필요하지만 그렇지 않을 때는 로지스틱 회귀가 더 낫다. 이는 구별적 분류기의 경우 특성의 분포를 모델링할 필요가 없기 때문인데, 일반적으로 구별적 분류기는 더 정확한 성능을 보이지만 정확성만 중요한 것은 아니다. 아래에서 구별적 분류기와 생성적 분류기의 장단점을 비교해 볼 것이다.

8.6.1. Pros and cons of each approach

  • 피팅하기 쉬운가? : 생성적 분류기는 훨씬 피팅하기 쉽다.
  • 클래스별로 피팅해야 하는가? : 생성적 분류기는 각각의 클래스 조건분포를 근사하므로 클래스를 추가할 때 모델을 재학습할 필요가 없다. 그 반대로 구별적 분류기는 모든 매개변수가 상호작용하므로 클래스를 추가할 때 모델을 재학습시켜야 한다.
  • 숨겨진 특성을 잘 다루는가? : 생성적 분류기는 숨겨진 특성을 잘 다룰 수 있지만, 구별적 분류기는 어렵다.
  • 라벨되지 않은 학습 데이터를 다룰 수 있는가? : 반지도 학습은 생성적 분류기에서 더 쉽고, 구별적 분류기에서는 훨씬 어렵다.
  • 입출력에 대해 대칭적인가? : 생성적 분류기는 역방향으로 적용시켜, 출력이 있을 때 p(\mathbf{x}|y)를 통해 그에 걸맞는 입력을 재생성할 수 있다. 구별적 분류기에서는 불가능하다.
  • 특성에 대한 전처리가 가능한가? : 구별적 분류기의 가장 큰 이점은 입력을 전처리할 수 있다는 것이다. 즉, 기저 함수 확장을 이용해 \mathbf{x}\mathbf{\phi}(\mathbf{x})로 대체할 수 있다. 생성적 분류기에서는 특성들이 여러 방식으로 상호 연관되어 있어 전처리된 데이터에 새 모델을 정의하기 어렵다.
  • 확률들이 잘 맞춰져 있는가? : 생성적 분류기에서는 종종 들어맞지 않는 강한 가정 (나이브 베이스 분류기의 클래스별 조건부 독립같은)을 하고는 하는데, 이는 클래스 사후확률을 치우쳐지게 만들고는 한다. 구별적 분류기에서는 이런 문제가 적다.
클래스 조건분포(좌)는 클래스 사후분포(우)에 대해 훨씬 복잡할 수 있다.

8.6.2. Dealing with missing data

가끔 입력의 일부는 관측되지 않는다. 이를 유실 데이터 문제라 한다. 생성적 분류기의 큰 이점은 유실된 데이터에 대처할 수 있다는 점이다.

r_{i} \in \{0, 1\}\mathbf{x}_{i}가 관측되었는지 여부를 결정하는 변수라 하자. 샘플의 관측에 영향을 주는 변수를 \mathbf{\phi}라 할 때 결합 모델 p(\mathbf{x}_{i}, r_{i} | \mathbf{\theta}, \mathbf{\phi}) = p(r_{i} | \mathbf{x}_{i}, \mathbf{\phi}) p(\mathbf{x}_{i} | \mathbf{\theta}) 에 대해 p(r_{i} | \mathbf{x}_{i}, \mathbf{\phi}) =  p(r_{i} | \mathbf{\phi}) 이라면 데이터가 완전 무작위 유실(MCAR) 된다고 하고, 데이터의 관측된 부분 \mathbf{x}_{i}^{o}에 대해 p(r_{i} | \mathbf{x}_{i}, \mathbf{\phi}) =  p(r_{i} | \mathbf{x}_{i}^{o}, \mathbf{\phi}) 라면 데이터가 무작위 유실(MAR) 된다고 한다. 둘 다 아닐 경우 데이터가 비무작위 유실 (NMAR) 된다고 한다. 이 경우 데이터가 어떻게 유실되는지를 모델링하면 유실된 데이터와 그에 해당하는 매개변수에 대해 더 잘 알수 있게 된다. 그 예시로 협업 필터링 문제가 있다.

유실된 데이터가 테스트 시점에만 유실되는지 (즉 학습 데이터가 완전 데이터인지) 학습 시점에도 유실되는지에 따라서도 다르다. 클래스 라벨이 학습 시점에도 유실된다면 반지도학습이라 한다.

8.6.2.1. Missing data at test time

생성적 분류기에서 무작위 유실되는 특성은 적분해 빼내면 된다. 예를 들어 특성 x_{1}이 유실되었다면 p(y = c | \mathbf{x}_{2 : D}, \mathbf{\theta}) \propto p(y = c | \mathbf{\theta})p(\mathbf{x}_{2 : D} | y = c, \mathbf{\theta}) = p(y = c | \mathbf{\theta}) \sum_{x_{1}} p(x_{1}, \mathbf{x}_{2 : D} | y = c, \mathbf{\theta})  로 계산할 수 있다.

8.6.2.2. Missing data at training time

학습 시점에도 데이터가 유실된다면 문제는 더 어려워진다. 이 경우 최대가능도근사나 최대사후확률근사는 더 이상 간단한 문제가 아니게 된다. EM 알고리즘 등으로 이 경우를 다루며, 이는 나중에 다룬다.

8.6.3. Fisher’s linear discriminant analysis (FLDA)

판별식 분석은 다변수 정규분포를 특성에 대해 피팅해야 하므로 고차원 문제를 다루기는 어렵다. 간단한 방법은 주성분 분석으로 차원을 낮추는 방법이 있으나 주성분 분석은 클래스 라벨을 고려하지 않는 비지도방법이므로 주성분 분석으로 차원을 낮춘 뒤 구한 해가 최적해라는 보장은 없다. 다른 대안은 차원을 낮추는 사영 행렬 \mathbf{W}를 구할 때 사영하고 난 뒤의 데이터에 가우시안 조건을 거는 것이다. 이를 피셔 선형 판별식 분석(FLDA)라 한다. 이는 구별적/생성적 방법의 흥미로운 혼합이라 볼 수 있다. 이 방식의 단점은 낮출 수 있는 차원이 L \leq C - 1로 제한된다는 것이다.

2D 데이터의 분류. 피셔 선형 판별식 분석이 주성분 분석보다 데이터를 더 잘 분리한다.

8.6.3.1. Derivation of the optimal 1d projection

이진 분류에 대해서 클래스 조건평균을 \mathbf{\mu}_{1} = \frac{1}{N_{1}} \sum_{i : y_{1} = 1} \mathbf{x}_{i} , \mathbf{\mu}_{2} = \frac{1}{N_{2}} \sum_{i : y_{2} = 1} \mathbf{x}_{i} 라 하자.

m_{k} = \mathbf{w}^{T} \mathbf{\mu}_{k} 를 클래스 조건평균의 매개변수에 대한 사영이라 하고, z_{k} = \mathbf{w}^{T} \mathbf{x}_{k} 를 데이터의 매개변수에 대한 사영이라고 하면 사영된 점들의 분산은 s_{k}^{2} = \sum_{i : y_{i} = k} (z_{i} - m_{k})^{2} 에 비례한다. 이 때 목적은 m_{2} - m_{1}을 최대화시키면서 사영된 데이터들의 분산도 최소화시키는 (즉, 두 데이터 집단을 가장 잘 분리하는) \mathbf{w}를 찾는 것이다. 이 때 최대화시키는 목적함수는 J(\mathbf{w}) = \frac{(m_{2} - m_{1})^{2}}{s_{1}^{2} + s_{2}^{2}} 가 된다.

\mathbf{S}_{B} = (\mathbf{\mu}_{2} - \mathbf{\mu}_{1}) (\mathbf{\mu}_{2} - \mathbf{\mu}_{1})^{T} 을 클래스간 산포행렬, \mathbf{S}_{W} = \sum_{k} \sum_{i : y_{i} = k} (\mathbf{x}_{i} - \mathbf{\mu}_{k})  (\mathbf{x}_{i} - \mathbf{\mu}_{k})^{T} 을 클래스내 산포행렬이라 하면 J(\mathbf{w})\mathbf{S}_{B}\mathbf{w} = \frac{\mathbf{w}^{T} \mathbf{S}_{B} \mathbf{w}}{ \mathbf{w}^{T} \mathbf{S}_{W} \mathbf{w} }\mathbf{S}_{W} \mathbf{w} 일 때 최대화되는데, 이를 일반화된 고유값 문제라 한다. 이 경우 \mathbf{S}_{W}의 역행렬이 존재하면 \mathbf{w} \propto \mathbf{S}_{W}^{-1} (\mathbf{\mu}_{2} - \mathbf{\mu}_{1})이 된다. 이것이 이진 분류에서 최적의 해이다. \mathbf{S}_{W} \propto \mathbf{I}라면, 즉 공유 공분산행렬이 방향을 보존한다면, 최적해는 클래스 평균을 잇는 벡터가 될 것이다. 이는 직관적으로 당연하다.

8.6.3.2. Extension to higher dimensions and multiple classes

고차원/다중 클래스로 문제를 확장하자면, \mathbf{W}를 사영 행렬, \mathbf{z}_{i} = \mathbf{W} \mathbf{x}_{i}을 사영된 데이터, \mathbf{m}_{c}를 사영된 클래스 평균, \mathbf{m}을 사영된 전체 평균이라 할 때,

\tilde{\mathbf{S}}_{W} = \sum_{c=1}^{C} \sum_{i : y_{i} = c} (\mathbf{z}_{i} - \mathbf{m}_{c}) (\mathbf{z}_{i} - \mathbf{m}_{c})^{T}  을 클래스내 산포행렬, \tilde{\mathbf{S}}_{B} = \sum_{c=1}^{C} N_{c} (\mathbf{z}_{i} - \mathbf{m}) (\mathbf{z}_{i} - \mathbf{m})^{T}  을 클래스간 산포행렬이라 하면 목적함수는 J(\mathbf{W}) = \frac{\lvert  \tilde{\mathbf{S}}_{B} \rvert}{ \lvert  \tilde{\mathbf{S}}_{W} \rvert } =  \frac{\lvert \mathbf{W}^{T} \mathbf{S}_{B} \mathbf{W} \rvert}{ \lvert   \mathbf{W}^{T} \mathbf{S}_{W} \mathbf{W}  \rvert } 이 된다. (이 때 \mathbf{S}_{B}, \mathbf{S}_{W} 는 사영 전 원래 공간에서 정의되는 산포행렬들이다.)

이 경우에 해는 \mathbf{U}\mathbf{S}_{W}^{-\frac{1}{2}} \mathbf{S}_{B} \mathbf{S}_{W}^{-\frac{1}{2}} 의 첫 L개의 고유벡터라 할 때 \mathbf{W} = \mathbf{S}_{W}^{-\frac{1}{2}} \mathbf{U} 가 된다. 이 해를 구할 때 \mathbf{S}_{W}가 역행렬이 존재함을 가정하는데, 존재하지 않는다면 주성분 분석을 해서 역행렬이 존재하게 만들면 된다.

피셔 선형 판별식분석의 예.

클래스간 산포행렬 \mathbf{S}_{B}의 랭크는 최대 C – 1이므로 피셔 선형 판별식분석은 최대 L \leq C - 1차원까지밖에 적용할 수 없다.

피셔 선형 판별식분석의 또 다른 활용은 특성 선택을 할 수 있다. \tilde{\mathbf{S}}_{T} =  \tilde{\mathbf{S}}_{W} + \tilde{\mathbf{S}}_{B} 이라 할 때 특성의 부분집합의 대표성을 J(\mathbf{Z}) = \mathrm{tr}( \tilde{\mathbf{S}}_{B}  \tilde{\mathbf{S}}_{T}^{-1} ) 이라 할 수 있다. 이를 피셔 점수라 한다. 최적의 특성 부분집합을 택하는 시간복잡도는 지수 시간복잡도가 들기 때문에 보통 한 번에 특성 하나씩 선택할지 여부를 결정한다.

8.6.3.3. Probabilistic interpretation of FLDA

피셔 선형 판별식분석의 확률적 표현을 찾기 위해서는 이분산성 선형 판별식분석(HLDA) 접근을 쓴다. 이는 사영된 데이터에 대해 가우시안 공분산 행렬을 클래스마다 피팅하기는 하는데, 첫 L개의 벡터만 클래스 의존적으로 하고 나머지 D – L개의 벡터는 클래스간 공유를 시키는 것이다. 즉, p(\mathbf{z}_{i} | \mathbf{\theta}, y_{i} = c) = \mathcal{N}(\mathbf{z}_{i} | \mathbf{\mu}_{c}, \mathbf{\Sigma}_{c}) , \mathbf{\mu}_{c} = (\mathbf{m}_{c}; \mathbf{m}_{0}) , \mathbf{\Sigma}_{c} =  \begin{pmatrix} \mathbf{S}_{c} & \mathbf{0} \\ \mathbf{0} & \mathbf{S}_{0} \end{pmatrix} 이라 하면 \mathbf{m}_{0}, \mathbf{S}_{0} 은 클래스간 공유를 시키는 것이다. 이 때 원본 데이터의 확률밀도함수는 p(\mathbf{x}_{i} | y_{i} = c, \mathbf{W}, \mathbf{\theta}) = \lvert \mathbf{W} \rvert \mathcal{N}(\mathbf{W}_{L} \mathbf{x}_{i} | \mathbf{m}_{c}, \mathbf{S}_{c}) \mathcal{N} (\mathbf{W}_{H} \mathbf{x}_{i} | \mathbf{m}_{0}, \mathbf{S}_{0}) 이 된다. \mathbf{W}는 그라디언트 하강으로 최적화할 수 있고, 그 이후에는 \mathbf{\theta}의 최대가능도근사는 쉽게 구할 수 있다.

\mathbf{\Sigma}_{c}가 대각이면 \mathbf{W}의 닫힌 꼴 해가 존재한다. \mathbf{\Sigma}_{c}가 전부 같다면 고전적 선형 판별식 분석이 된다. 사영한 공간 내에서 클래스 공분산이 다를 경우 이분산성 선형 판별식 분석은 일반적인 선형 판별식 분석보다 좋은 성능을 낸다. 음성 인식 등 혼합 데이터에서 이러한 경향이 두드러진다. 더 나아가 각 클래스별로 사영 행렬을 다르게 할 수 있는데, 이를 다중 선형 판별식 분석이라 한다.

요점 정리

  • 로지스틱 회귀 : 가장 기본적 선형 구별적 분류기로, p(y | \mathbf{x}, \mathbf{w}) = \mathrm{Ber}(y | \mathrm{sigm}(\mathbf{w}^{T}\mathbf{x})) 로 모델링된다.
  • 로지스틱 회귀의 최대가능도근사는 닫힌 꼴의 최적해가 존재하지 않으므로 그라디언트 하강법뉴턴법 등으로 최적해를 근사한다. l_{2} 정규화도 사용할 수 있다.
  • 사전분포를 적용해 베이지안 로지스틱 회귀를 수행해 대응되는 사후분포를 구할 수 있다.
  • 스트리밍되는 데이터에 대해서는 온라인 학습과 추계적 그라디언트 하강법을 적용할 수 있다.
  • 구별적 분류기와 생성적 분류기는 각각의 장단점을 가진다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중