Linear Discriminant Analysis

Linear Classification

이번 포스트부터는 선형 방법으로 분류 문제를 해결하는 방법들에 대해 살펴보고자 한다. 여기서 분류^{classification} 문제란, 종속 변수와 예측값 $G(x)$ 가 이산집합 $\mathcal{G}$의 원소를 갖는 문제를 의미한다. 분류 문제의 핵심은 결정경계^{decision boundary}를 찾는 것인데, 결정경계가 선형인 것들만 우선 다루어보도록 하자.

Indicator Matrix를 이용한 선형회귀

종속변수 $y$가 $k$개의 값을 가질 수 있다고 하자. 즉, $N(\mathcal{G})=k$ 이다. 이때 단일변수 $y$를 $Y = (Y_1,\ldots,Y_k)$ 로 변환시키는데, 각 $Y_j$는 $G=j$이면 1이고 아닌 경우 0인 값을 취한다. 이런 방식으로 n개의 데이터에 대해 종속변수를 재설정하면 행렬 $\mathbf{Y}$ 를 얻을 수 있고, 행렬의 각 원소는 0 또는 1의 값만을 취한다.
이를 이용해 최소제곱법을 계산하면

\[\mathbf{\hat{Y}=X(X^\top X)^{-1}X^\top Y}\]

와 같은 형태를 생각할 수 있다. 여기서 선형회귀와의 차이점은, 회귀계수가 벡터가 아닌 행렬

\[\mathbf{\hat{B}=(X^\top X)^{-1}X^\top Y}\]

로 주어진다는 것이다. 이를 바탕으로, 새로운 input vector $x$가 주어질 때 이에 대한 예측값은

\[\hat{f}(x)^\top = (1,x^\top)\mathbf{\hat{B}} \in \mathbb{R^k}\]

로 계산할 수 있다. 또한, 우리는 분류를 해야할 목적을 가지고 있으므로 각 데이터에 대해 부여할 클래스는 예측값이 가장 높은 클래스를 부여해야 할 것이다. 따라서 예측 클래스 $\hat{G}(x)$ 는

\[\hat{G}(x) = \arg\max_{k\in\mathcal{G}}\hat{f_k}(x)\]

로 나타낼 수 있다.

선형회귀를 이용한 분류의 타당성

앞서 살펴본 회귀를 이용한 분류가 타당한지 의문이 생길 수 있다. 왜냐하면, 회귀는 설명력을 높이는 모형을 생성하는데 목적이 있지만, 분류는 클래스를 더 정확히 예측하는데 중점을 두기 때문이다. 분류에서 중요한 것은 사후확률^{Posterior Probability} $P(G=k\vert X=x)$ 을 추정하는 것이고, 이를 바탕으로 클래스 예측자를 만들어야 한다. 그렇다면 이는 앞서 계산한 예측자 $\hat{f}(x)$ 가 사후확률에 대해 좋은 추정치가 될 수 있는가의 문제로 이어진다.
$\sum_{k\in\mathcal{G}}\hat{f}_k(x) = 1$ 인 사실은 쉽게 확인할 수 있으나, 문제는 어떤 예측자 $\hat{f}$는 음수의 값을 취하고 1보다 큰 상황 역시 발생가능하다는 것이다. 단순히 생각하면 이는 확률을 추정하는데 걸림돌로 작용할 것으로 보인다. 하지만 이는 큰 문제가 되지 않는데, 기저 확장^{basis expansion}을 통해 일관된 추정이 가능하게끔 할 수 있다. 기저확장에 대해서는 추후에 다른 포스트에서 다루도록 할 것이다.

LDA^{Linear Discriminant Analysis}

LDA를 살펴보기 이전에 먼저 베이즈 정리를 바탕으로 사후확률 $P(G\vert X)$ 의 추정 과정에 대해 살펴보자.
클래스가 $G=k\;(k=1,\ldots,K)$인 확률변수 $X$의 조건부 확률밀도함수가 $f_k(x)$로 주어지고, 클래스 $k$에 대한 사전확률^{prior probability}이 $\pi_k$ 로 주어진다고 하자. 이때 $\sum_{k=1}^K\pi_k=1$ 을 만족한다. 베이즈 정리로부터 조건부확률은

\[P(G=k\vert X=x) = \frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l}\]

로 주어진다. 여기서 주목해야 할 것은 만약 우리가 확률밀도함수 $f_k$ 들에 대한 정보가 있다면 해당 조건부확률의 값을 도출해낼 수 있다는 것이다. 이때 확률밀도함수를 어떤 분포로 가정하느냐에 따라 다양한 방법이 있고, 여기에서 살펴볼 LDA는 정규분포를 이용한다.

LDA 가정

LDA는 앞서 언급한대로 조건부 확률밀도함수가 정규분포를 따르는데, 이때 클래스들의 공분산행렬이 모두 동일할 때를 가정한다. 즉,

\[\Sigma_k = \Sigma\quad\forall k\]

이고 클래스별 조건부 확률밀도함수는

\[f_k(x) = \frac{1}{(2\pi)^{p/2}\vert\Sigma\vert^{1/2}}\exp\left( -\frac{1}{2}(x-\mu_k)^\top\Sigma^{-1}(x-\mu_k)\right) \tag{*}\]

으로 주어진다(변수가 p개로 주어진다고 가정하자).
이러한 가정 하에서, 두 클래스 $G=k, G=l$ 의 결정경계^{decision boundary}를 찾는 상황을 생각해보자. 결정경계는 두 조건부확률 $P(G=k\vert X=x),P(G=l\vert X=x)$ 이 동일한 지점을 찾는 것이므로 로그오즈비(log-odds)가 0이되는 식을 찾으면 된다. 즉,

\[\begin{aligned} \log\frac{P(G=k\vert X=x)}{P(G=l\vert X=x)} &= \log\frac{f_k(x)}{f_l(x)}+\log\frac{\pi_k}{\pi_l}\\ &=\log\frac{\pi_k}{\pi_l}-\frac{1}{2}(\mu_k+\mu_l)^\top\Sigma^{-1}(\mu_k-\mu_l)\\ &+x^\top\Sigma^{-1}(\mu_k-\mu_l)\\ &=0 \end{aligned}\tag{1}\]

마지막 등식을 살펴보면 이는 $x$에 대해 선형인 방정식이므로, 선형결정경계라고 할 수 있다. 즉, p차원 공간에서 이 결정경계는 초평면^Hyperplane의 형태로 나타나며, 이 초평면은 예측 클래스들을 분류하는 기준이 된다.

Linar Discriminant function

앞서 구한 선형결정경계 식 $(1)$에서 클래스 $G=k$에 대해서만 다음과 같이

\[\delta_k(x) = x^\top\Sigma^{-1}\mu_k - \frac{1}{2}\mu_k^\top\Sigma^{-1}\mu_k+\log\pi_k\]

정의한 $x$에 대한 함수를 linear discriminant function이라고 한다. 이때 $G(x) = \arg\max_k\delta_k(x)$ 로 두면 이는 클래스 예측 기준과 동일한 것을 확인할 수 있다.

문제는, 실제 LDA를 활용해야 하는 상황은 표본(sample)을 기반으로 하기 때문에 우리는 모수 \(\pi_k,\mu_k,\Sigma\) 대신 이에 대한 추정치를 사용해야 한다. 따라서 사전확률 \(\pi_k\)는 상대도수 \(\hat{\pi}_k=N_k/N\), 평균벡터 \(\mu_k\) 대신 표본평균

\[\hat{\mu}_k=\sum_{g_i=k}x_i/N_i\]

과 공분산행렬 $\Sigma$ 대신 표본분산

\[\hat{\Sigma} = \sum_{k=1}^K\sum_{g_i=k}(x_i-\hat{\mu}_k)(x_i-\hat{\mu}_k)^\top/(N-K)\]

을 사용한다.

Quadratic discriminant analysis

만일 식 $(*)$에서 클래스들의 공분산행렬이 동일하다는 가정이 없다고 하자. 그러면 discriminant function을 구하는 과정에서 항의 소거가 발생하지 않고, 따라서

\[\delta_k(x)= -\frac{1}{2}\log\vert \Sigma_k\vert -\frac{1}{2}(x-\mu_k)^\top\Sigma_k^{-1}(x-\mu_k)+\log\pi_k\tag{2}\]

위와 같은 형태로 discriminant function이 구해지는데, 이를 quadratic discriminant function 이라고 하며, 이를 이용한 분석을 QDA라고 정의한다. Quadratic인 이유는 식 $(2)$의 우변의 두번째 항이 $x$에 대해 이차항이기 때문이며 이를 바탕으로 얻어지는 결정경계 역시 quadratic이다.
QDA는 LDA와 비슷하게 작용하는데, 가장 큰 차이점이 있다면 실제 사용하는 과정에서 공분산행렬의 추정치를 각 클래스별로 사용해야 한다는 것이다.

LDA와 QDA는 고전적이고, 현대 머신러닝 기법들에 비해 단순하다고 생각될 수 있다. 그러나 정규분포를 가정하여 단순한(1차 혹은 2차의) 결정경계를 추정하는 방식은 상당히 안정적이고, 이는 편향-분산 tradeoff 관계에서 낮은 분산을 얻어낼 수 있다.

LDA의 계산

LDA와 QDA의 결정경계를 계산하는 과정은, 앞서 언급한 표본공분산행렬 $\Sigma$(LDA) 또는 $\Sigma_k$(QDA) 를 대각화하여 간단히 만들 수 있다. QDA 상황에서 고유값분해로부터 표본공분산행렬이

\[\hat{\Sigma}_k = \mathbf{U}_k\mathbf{D}_k\mathbf{U}_k^\top\tag{3}\]

로 분해된다고 하자. 이때 $\mathbf{U_k}$ 는 $p\times p$ 정규직교행렬(orthonormal)이고, $\mathbf{D_k}$ 는 고유값들을 대각성분($d_{kl}$)으로 하는 대각행렬이다. 이를 이용하면. discriminant function $\delta_k(x)$ 를 계산할 때

\[(x-\hat{\mu}_k)^\top\hat{\Sigma}_k^{-1}(x-\hat{\mu}_k) = [\mathbf{U}+k^\top(x-\hat{\mu}_k)]^\top\mathbf{D}_k^{-1}[\mathbf{U}_k^\top(x-\hat{\mu}+k)]\] \[\log\vert \hat{\Sigma}_k\vert = \sum_l\log d_{kl}\]

임을 이용할 수 있다. 이때 아래 식은 ‘행렬식 = 대각원소의 곱’으로부터 얻어진다.

References

• Hastie, T., Tibshirani, R., Friedman, J. H., & Friedman, J. H. (2009). The elements of statistical learning: data mining, inference, and prediction (Vol. 2, pp. 1-758). New York: springer.