선형판별분석(Linear Discriminant Analysis)
21 Mar 2017 | Linear Discriminant Analysis
이번 포스팅에선 선형판별분석(Linear Discriminant Analysis : LDA)에 대해서 살펴보고자 합니다. LDA는 데이터 분포를 학습해 결정경계(Decision boundary)를 만들어 데이터를 분류(classification)하는 모델입니다. 이번 글은 기본적으로 고려대 강필성 교수님, 김성범 교수님 강의를 참고로 했음을 먼저 밝힙니다. 자, 그럼 시작하겠습니다.
LDA의 배경과 목적
LDA는 아래 그림처럼 데이터를 특정 한 축에 사영(projection)한 후에 두 범주를 잘 구분할 수 있는 직선을 찾는 걸 목표로 합니다. 모델 이름에 linear라는 이름이 붙은 이유이기도 합니다.
왼쪽과 오른쪽 축 가운데 분류가 더 잘 됐다고 판단할 수 있는 축은 무엇일까요? 딱 봐도 오른쪽이 좀 더 나아보입니다. 빨간색 점과 파란색 점을 분류하는 걸 목표로 했는데 왼쪽 그림에 나타난 축은 중간에 빨간색과 파란색 점이 뒤섞여 있기 때문이지요. 반대로 오른쪽 그림은 색깔이 서로 다른 점들이 섞이지 않고 비교적 뚜렷하게 구분되고 있는 점을 확인할 수 있습니다. 녹색 축을 따라서 같은 위치에 있는 점들의 빈도를 세어서 히스토그램처럼 그리면 바로 위와 같은 그림이 됩니다.
그렇다면 두 범주를 잘 구분할 수 있는 직선은 어떤 성질을 지녀야 할까요? 사영 후 두 범주의 중심(평균)이 서로 멀도록, 그 분산이 작도록 해야할 겁니다. 왼쪽 그림을 오른쪽과 비교해서 보면 왼쪽 그림은 사영 후 두 범주 중심이 가깝고, 분산은 커서 데이터가 서로 잘 분류가 안되고 있는 걸 볼 수가 있습니다. 반대로 오른쪽 그림은 사영 후 두 범주 중심이 멀고, 분산은 작아서 분류가 비교적 잘 되고 있죠. LDA는 바로 이런 직선을 찾도록 해줍니다.
LDA에 대한 첫번째 접근
자, 그럼 이제 본격적으로 LDA에 대해 알아볼까요? $p$차원의 입력벡터 $x$(변수 $p$개)를 $w$라는 벡터(축)에 사영시킨 후 생성되는 1차원상의 좌표값(스칼라)를 아래와 같이 $y$라고 정의합니다. 각각 $N_1$개와 $N_2$개의 관측치를 갖는 $C_1$과 $C_2$ 두 범주에 대해 원래 입력공간(2차원)에서 각 범주의 중심(평균) 벡터도 아래와 같이 $m_1$, $m_2$라고 정의합니다.
\[y={ \overrightarrow { w } }^{ T }\overrightarrow { x } \\ { m }_{ 1 }=\frac { 1 }{ { N }_{ 1 } } \sum _{ n\in { C }_{ 1 } }^{ }{ { x }_{ n } } \\ { m }_{ 2 }=\frac { 1 }{ { N }_{ 2 } } \sum _{ n\in { C }_{ 2 } }^{ }{ { x }_{ n } }\]
일단 사영후 두 범주의 중심이 멀리 떨어져 위치하는 벡터 $w$를 찾아야 합니다. 각 중심과 $w$와의 관계식은 아래와 같습니다.
\[{ m }_{ 2 }-{ m }_{ 1 }={ w }^{ T }({ m }_{ 2 }-{ m }_{ 1 })\\ { m }_{ k }={ w }^{ T }{ m }_{ k }\]
사영 후 각 범주에 속한 관측치들은 해당 범주 중심에 가까이 있을 수록 좋습니다. 다시 말해 분산이 작아야 한다는 겁니다. 사영 후 분산은 아래 식과 같습니다.
\[{ s }_{ k }^{ 2 }=\sum _{ n\in { C }_{ k } }^{ }{ { ({ y }_{ n }-{ m }_{ k }) }^{ 2 } }\]
두 범주의 중심은 최대화하고, 분산은 최소화하는 게 우리의 목표입니다. 동시에 한꺼번에 할 수는 없을까요? 간단한 방법이 있습니다. 두 범주 중심을 분자, 두 범주의 분산을 분모에 넣고 이 식을 최대화하는 겁니다. 이를 행렬 형태의 목적함수로 나타내면 다음과 같습니다.
\[J(w)=\frac { { ({ m }_{ 1 }-{ m }_{ 2 }) }^{ 2 } }{ { s }_{ 1 }^{ 2 }+{ s }_{ 2 }^{ 2 } } =\frac { { w }^{ T }{ S }_{ B }w }{ { w }^{ T }{ S }_{ W }w } \\ { S }_{ B }=({ m }_{ 1 }-{ m }_{ 2 }){ ({ m }_{ 1 }-{ m }_{ 2 }) }^{ T }\\ { S }_{ W }=\sum _{ n\in { C }_{ 1 } }^{ }{ ({ x }_{ n }-{ m }_{ 1 }){ ({ x }_{ n }-{ m }_{ 1 }) }^{ T } } +\sum _{ n\in { C }_{ 2 } }^{ }{ ({ x }_{ n }-{ m }_{ 2 }){ ({ x }_{ n }-{ m }_{ 2 }) }^{ T } }\]
목적함수 $J(w)$은 $w$에 대해 미분한 값이 0이 되는 지점에서 최대값을 가집니다. 아래 식과 같습니다.
\[({ w }^{ T }{ S }_{ B }w){ S }_{ W }w=({ w }^{ T }{ S }_{ W }w){ S }_{ B }w\]
그런데 위 식에서 괄호 안은 계산해보면 스칼라가 됩니다. 각각의 차원수를 고려하면 (1Xd) (dXd) (dX1)이 되기 때문입니다. 그럼 위 식 양변을 좌변 괄호안의 스칼라값으로 나누어 약간 정리를 하면 아래와 같은 형태가 됩니다.
\[{ S }_{ W }w=\lambda { S }_{ B }w\\ { { S }_{ B } }^{ -1 }{ S }_{ W }w=\lambda w\]
이 식 어디서 많이 보시지 않았나요? 네 그렇습니다. 바로 고유값, 고유벡터 구할 때 바로 그 $AX=λX$ 꼴입니다. 즉 새로운 축 $w$는 $S_B$의 역행렬과 $S_W$를 내적한 행렬의 고유벡터라는 이야기죠.
자, 그럼 여기서 $S_B$와 $S_W$는 어떻게 구할까요? 각각 우리가 가진 데이터의 평균과 분산입니다. 데이터로부터 구할 수 있다는 이야기죠. 이 행렬을 고유값분해하여 새로운 축 $w$를 구할 수 있습니다.
이를 가지고 예측은 어떻게 할까요? 새로운 데이터($x’$)가 주어지면 이를 $w$와 내적해 각각의 스코어를 낼 수 있습니다. 그 스코어가 일정값보다 크면 $C_1$범주, 작으면 $C_2$ 범주로 분류를 하게 됩니다.
LDA에 대한 두번째 접근
LDA를 확률모형으로부터 도출할 수도 있습니다. 베이즈 룰(Bayes’ Rule)을 이용한 방식입니다. 베이즈 룰 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다. 그럼 베이즈 룰을 활용해 LDA를 구현해보도록 할까요? 범주가 두 개($W_1$, $W_2$) 있다고 가정해보죠. 이를 그림으로 나타내보면 아래처럼 될 겁니다.
우선 데이터($X$)로부터 사전확률 $P(W_1)$, $P(W_2)$을 구합니다. 어떻게 구하느냐고요? 범주가 $W_1$인 데이터 개수, $W_2$인 데이터 개수를 각각 전체 데이터 개수로 나눠주면 됩니다. 우리가 하고 싶은 건 이겁니다. 새로운 데이터 $x$가 주어졌을 때 이게 어떤 클래스에 속하는지 알아맞혀 보려고 하는 것이죠. 이를 지금까지 논의한 내용을 바탕으로 식을 쓰면 아래와 같이 됩니다.
\[\begin{align*}
P({ W }_{ i }|x)&=\frac { P(x|{ W }_{ i })P({ W }_{ i }) }{ P(x) } \\
&=\frac { P(x|{ W }_{ i })P({ W }_{ i }) }{ P(x|{ W }_{ 1 })P({ W }_{ 1 })+P(x|{ W }_{ 2 })P({ W }_{ 2 }) }
\end{align*}\]
새로운 데이터 $x$가 등장하면 LDA 모델은 P($W_1$|x)와 P($W_2$|x)를 각각 구합니다. 둘 중 전자가 크면 $W_1$으로, 후자가 크면 $W_2$로 분류를 하게 되는 방식입니다. 사후확률인 P($W_i$|x)는 새로운 데이터 $x$가 주어졌을 때(=정답 범주를 모를 때=예측할 때) $W_i$일 확률, 즉 검증데이터가 특정 범주에 할당하기 위한 스코어를 의미합니다. 범주 분류를 위한 확률(스코어)를 내어주는 함수를 판별함수(discriminant function)라고 합니다.
LDA의 중요한 가정은 데이터 분포가 다변량 정규분포(multivariate normal distribution)을 따른다는 사실입니다. 많은 자연, 사회현상이 정규분포를 따르고 있고 그 예측력 또한 많은 실험을 통해 검증된 연속확률분포입니다. 다변량 정규분포의 파라메터는 평균(벡터)와 공분산(행렬)입니다. 이 두 파라메터와 정규분포 확률함수로 P(x|$W_i$)를 구할 수 있고, 이를 우리가 이미 알고 있는 사전확률 $P(W_i)$과 함께 계산해 범주를 판별한다는 것이 LDA를 베이지안 관점에서 접근하는 방식의 핵심입니다.
마치며
자, 그럼 복기를 해볼까요? 두번째 챕터에서 설명드린 두 범주의 데이터를 가장 잘 분류하는 새로운 축인 $w$는 두 범주의 평균 벡터의 차이를 분자, 두 범주 분산의 합을 분모로 두고 이 식을 최대화하는 과정에서 도출됩니다. 미지수 $w$로 미분을 해서 0이 되는 지점이 이 식을 최대화하는 지점입니다. 베이지안 법칙 관점에서는 사후확률 P($W_1$|x)와 P($W_2$|x)가 같은 지점을 결정경계로 놓고 식을 도출하게 되는데요, 이것이 결과적으로는 첫번째 방식인 $w$로 미분을 해서 0이 되는 지점과 본질적으로 같게 돼서 두 접근이 사실상 같은 결과를 내는 것을 확인할 수 있습니다. 두 접근 모두 데이터의 분포가 $p$차원의 다변량 정규분포를 따른다는 전제가 내재돼 있습니다.
LDA로 두 개 범주를 분류한 부분은 좌측 상단 그림과 같습니다. 두번째 접근에서 각 범주의 공분산행렬이 동일하다는 가정을 하고 식을 정리하면 $Ax+b=0$ 꼴의 선형식이 된다고 설명을 했는데요. 실제로 결정경계가 직선임을 시각적으로도 확인할 수 있습니다. 그런데 공분산이 다르다고 놓고 식을 정리하면 $Ax^2+Bx+c=0$ 꼴의 Quadratic form이 됩니다. 그래서 우측 상단 그림을 보면 결정경계가 비선형인 모양을 볼 수 있습니다.
LDA이든 QDA이든 학습데이터의 정보를 압축해 데이터 분류를 위한 결정경계를 만들어낸다는 점에서 본질적으로 동일합니다. 학습데이터의 패턴만 가지고도 충분히 좋은 예측모델을 만들어낼 수 있다는 얘기입니다. 질문이나 제언 있으시면 언제든지 댓글, 이메일로 알려주시기 바랍니다. 여기까지 읽어주셔서 대단히 감사합니다.
Appendix : 두번째 접근의 수식 도출
LDA를 베이지안 관점에서 접근하는 방식과 관련해 수식을 유도해 보겠습니다. 저 역시 정리 용도로 남겨두는 것이니 스킵하셔도 무방합니다.
정규분포를 따르는 $N$개 데이터가 $k$개 범주로 구성돼 있는 $p$차원(변수 개수=$p$개)의 데이터 $X$의 평균과 공분산은 각각 아래와 같습니다. 평균벡터의 요소는 각각 변수 관측치의 평균입니다. 예컨대 $μ_1$은 데이터 첫번째 변수의 평균입니다. 마찬가지로 공분산행렬의 요소는 각각 변수 관측치의 공분산입니다. σ12는 첫번째 변수와 두번째 변수의 공분산, 즉 $cov(X_1, X_2)$입니다.
\[\mu =\begin{bmatrix} { \mu }_{ 1 } \\ ... \\ { \mu }_{ p } \end{bmatrix}\\ \Sigma =\begin{bmatrix} { \sigma }_{ 11 } & ... & { \sigma }_{ 1p } \\ ... & ... & ... \\ { \sigma }_{ p1 } & ... & { \sigma }_{ pp } \end{bmatrix}\]
위 두 개 파라메터만 알고 있으면 아래와 같이 이미 정의돼 있는 다변량 정규분포 확률함수로 P(x|$W_i$)를 구할 수 있게 됩니다. 그렇다면 P(x|$W_i$)의 의미는 무엇일까요? 범주정보가 주어졌을 때(=정답 범주를 알고 있을 때=학습할 때) $x$가 나타날 확률, 즉 학습데이터 내에 있는 $W_i$의 분포가 됩니다. P(x|$W_i$)는 다음과 같습니다. ($p$는 데이터 변수 개수)
\[P(X=x|{ W }_{ i })=P(x|{ W }_{ i })=\frac { 1 }{ { (2\pi ) }^{ p/2 }{ \left| { \Sigma }_{ i } \right| }^{ 1/2 } } \exp\left[ -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i }) \right]\]
판별함수 $σ$는 새로운 데이터 $x$에 대해 범주(클래스)를 할당해주는 역할을 하는데요, 범주 개수($k$개)만큼의 판별함수가 필요하게 됩니다. 새로운 데이터에 대해 가장 큰 확률값을 내어주는 범주로 분류하게 됩니다. 판별함수 식은 아래와 같습니다.
\[\begin{align*}
{ \sigma }_{ i }(x)&=P({ W }_{ i }|x)\\
&\propto P(x|{ W }_{ i })P({ W }_{ i })\\
&\propto \ln { P(x|{ W }_{ i }) } +\ln { P( W }_{ i }) \\
\end{align*}\]
위의 판별함수 계산에서 유의할 부분은 $P(x)$를 나눠주는 부분을 생략해도 된다는 점입니다. $k$개 판별함수의 분모는 $P(x)$로 동일하고, 범주 예측엔 판별함수 결과값 크기만 중요하기 때문에 분모를 생략해 계산상 이득을 취하기 위해서입니다. 이 식에 자연로그를 취해도 판별함수 간 크기는 달라지지 않기 때문에 계산상 편의를 위해 로그변환을 한 것이 위 식 마지막 결과입니다.
위 식 P(x|$W_i$)에 다변량 정규분포의 확률함수를 대입해 정리하면 아래와 같습니다.
\(\begin{align*}ln { P(x|{ W }_{ i }) } &= \ln { \frac { 1 }{ { (2\pi ) }^{ p/2 }{ \left| { \Sigma }_{ i } \right| }^{ 1/2 } } } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i })\\
&=\ln { \frac { 1 }{ { (2\pi ) }^{ p/2 } } } +\ln { \frac { 1 }{ { \left| { \Sigma }_{ i } \right| }^{ 1/2 } } } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i })\\
&=-\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ i } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i })
\end{align*}\)
위 식을 자세히 보시면 미지수가 하나도 없는 상수라는 점을 확인할 수 있습니다. 데이터 $x$는 물론 변수 개수인 $p$, $π$, $Σ$, 평균까지 이미 우리가 다 알고 있는 값들이기 때문입니다. 이 값들을 위 식에 넣어서 계산하기만 하면 P(x|$W_i$)를 바로 구할 수 있습니다. 한편 나머지 $P(W_i)$는 i번째 범주의 개체 수를 전체 데이터 수로 나눠서($N_i/N$) 바로 구할 수 있습니다.
그럼 이제 결정경계(decision boundary)를 살펴보겠습니다. 범주가 두 개일 때를 예를 들어보죠. 판별함수 $σ_1$과 $σ_2$의 값이 같은 지점이 바로 분류 경계면이 될 겁니다. $σ_1$이 조금이라도 크면 $W_1$ 범주, 반대 상황이면 $W_2$ 범주로 분류되기 때문입니다. 이를 위 식을 기준으로 넣어서 정리하면 아래와 같은 식이 됩니다.
\[\begin{align*}
{ \sigma }_{ 1 }(x)-{ \sigma }_{ 2 }(x)&=0
\\ -\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ 1 } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ 1 }) }^{ T }{ { \Sigma }_{ 1 } }^{ -1 }(x-{ \mu }_{ 1 })+\ln { P({ W }_{ 1 }) } \\-(-\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ 2 } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ 2 }) }^{ T }{ { \Sigma }_{ 2 } }^{ -1 }(x-{ \mu }_{ 2 })+\ln { P({ W }_{ 2 }) } )&=0\\
{ (x-{ \mu }_{ 1 }) }^{ T }{ { \Sigma }_{ 1 } }^{ -1 }(x-{ \mu }_{ 1 })-{ (x-{ \mu }_{ 2 }) }^{ T }{ { \Sigma }_{ 2 } }^{ -1 }(x-{ \mu }_{ 2 })-\ln { \frac { \left| { \Sigma }_{ 2 } \right| }{ \left| { \Sigma }_{ 1 } \right| } } +2\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } &=0
\end{align*}\]
뭔가 식이 엄청 복잡해보이죠? 일단은 범주 각각의 분산이 동일하다고 가정해보겠습니다. 그러면 둘의 분산은 합동분산(pooled variance) 공식에 의해 아래와 같이 같이 쓸 수 있습니다.
\[{ \Sigma }_{ 1 }={ \Sigma }_{ 2 }={ \Sigma }=\left[ \frac { { n }_{ 1 }-1 }{ ({ n }_{ 1 }-1)+({ n }_{ 2 }-1) } \right] { \Sigma }_{ 1 }+\left[ \frac { { n }_{ 2 }-1 }{ ({ n }_{ 1 }-1)+({ n }_{ 2 }-1) } \right] { \Sigma }_{ 2 }\]
이를 판별함수 식에 넣어 정리하면 아래와 같습니다.
\[{ { (\mu }_{ 1 }-{ \mu }_{ 2 }) }^{ T }{ \Sigma }^{ -1 }x-\frac { 1 }{ 2 } { { (\mu }_{ 1 }-{ \mu }_{ 2 }) }^{ T }{ \Sigma }^{ -1 }{ { (\mu }_{ 1 }+{ \mu }_{ 2 }) }-\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } =0\]
위 식은 복잡해보이지만 자세히 뜯어보면 $Ax+b=0$의 선형식(linear equation)이 됩니다. $x$를 제외하면 미지수가 전혀 없는 상수항이기 때문입니다. 결정경계가 직선 모양이라는 뜻인데요. 이 상수항들은 모두 학습데이터의 패턴이 녹아들어 있는 결과입니다. 위 식에 $x$를 넣어 0보다 큰 값이 나오면 $W_1$ 범주, 그렇지 않으면 $W_2$ 범주로 분류하는 방식입니다.
한편 $Σ_1$과 $Σ_2$가 각각 다르다고 놓고 풀면 아래와 같은 식이 됩니다.
\[-\frac { 1 }{ 2 } { x }^{ T }({ { \Sigma }_{ 1 } }^{ -1 }-{ { \Sigma }_{ 2 } }^{ -1 })x+({ \mu }_{ 1 }{ { \Sigma }_{ 1 } }^{ -1 }+{ \mu }_{ 2 }{ { \Sigma }_{ 2 } }^{ -1 })x-\frac { 1 }{ 2 } ({ \mu }_{ 1 }^{ 2 }{ { \Sigma }_{ 1 } }^{ -1 }-{ \mu }_{ 2 }^{ 2 }{ { \Sigma }_{ 1 } }^{ -1 })+\frac { 1 }{ 2 } \ln { \frac { \left| { \Sigma }_{ 2 } \right| }{ \left| { \Sigma }_{ 1 } \right| } } -\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } =0\]
위 식도 자세히 보면 $Ax^2+bx+c=0$의 2차식 형태입니다. 따라서 결정경계는 곡선 형태가 됩니다.
이번 포스팅에선 선형판별분석(Linear Discriminant Analysis : LDA)에 대해서 살펴보고자 합니다. LDA는 데이터 분포를 학습해 결정경계(Decision boundary)를 만들어 데이터를 분류(classification)하는 모델입니다. 이번 글은 기본적으로 고려대 강필성 교수님, 김성범 교수님 강의를 참고로 했음을 먼저 밝힙니다. 자, 그럼 시작하겠습니다.
LDA의 배경과 목적
LDA는 아래 그림처럼 데이터를 특정 한 축에 사영(projection)한 후에 두 범주를 잘 구분할 수 있는 직선을 찾는 걸 목표로 합니다. 모델 이름에 linear라는 이름이 붙은 이유이기도 합니다.
왼쪽과 오른쪽 축 가운데 분류가 더 잘 됐다고 판단할 수 있는 축은 무엇일까요? 딱 봐도 오른쪽이 좀 더 나아보입니다. 빨간색 점과 파란색 점을 분류하는 걸 목표로 했는데 왼쪽 그림에 나타난 축은 중간에 빨간색과 파란색 점이 뒤섞여 있기 때문이지요. 반대로 오른쪽 그림은 색깔이 서로 다른 점들이 섞이지 않고 비교적 뚜렷하게 구분되고 있는 점을 확인할 수 있습니다. 녹색 축을 따라서 같은 위치에 있는 점들의 빈도를 세어서 히스토그램처럼 그리면 바로 위와 같은 그림이 됩니다.
그렇다면 두 범주를 잘 구분할 수 있는 직선은 어떤 성질을 지녀야 할까요? 사영 후 두 범주의 중심(평균)이 서로 멀도록, 그 분산이 작도록 해야할 겁니다. 왼쪽 그림을 오른쪽과 비교해서 보면 왼쪽 그림은 사영 후 두 범주 중심이 가깝고, 분산은 커서 데이터가 서로 잘 분류가 안되고 있는 걸 볼 수가 있습니다. 반대로 오른쪽 그림은 사영 후 두 범주 중심이 멀고, 분산은 작아서 분류가 비교적 잘 되고 있죠. LDA는 바로 이런 직선을 찾도록 해줍니다.
LDA에 대한 첫번째 접근
자, 그럼 이제 본격적으로 LDA에 대해 알아볼까요? $p$차원의 입력벡터 $x$(변수 $p$개)를 $w$라는 벡터(축)에 사영시킨 후 생성되는 1차원상의 좌표값(스칼라)를 아래와 같이 $y$라고 정의합니다. 각각 $N_1$개와 $N_2$개의 관측치를 갖는 $C_1$과 $C_2$ 두 범주에 대해 원래 입력공간(2차원)에서 각 범주의 중심(평균) 벡터도 아래와 같이 $m_1$, $m_2$라고 정의합니다.
\[y={ \overrightarrow { w } }^{ T }\overrightarrow { x } \\ { m }_{ 1 }=\frac { 1 }{ { N }_{ 1 } } \sum _{ n\in { C }_{ 1 } }^{ }{ { x }_{ n } } \\ { m }_{ 2 }=\frac { 1 }{ { N }_{ 2 } } \sum _{ n\in { C }_{ 2 } }^{ }{ { x }_{ n } }\]일단 사영후 두 범주의 중심이 멀리 떨어져 위치하는 벡터 $w$를 찾아야 합니다. 각 중심과 $w$와의 관계식은 아래와 같습니다.
\[{ m }_{ 2 }-{ m }_{ 1 }={ w }^{ T }({ m }_{ 2 }-{ m }_{ 1 })\\ { m }_{ k }={ w }^{ T }{ m }_{ k }\]사영 후 각 범주에 속한 관측치들은 해당 범주 중심에 가까이 있을 수록 좋습니다. 다시 말해 분산이 작아야 한다는 겁니다. 사영 후 분산은 아래 식과 같습니다.
\[{ s }_{ k }^{ 2 }=\sum _{ n\in { C }_{ k } }^{ }{ { ({ y }_{ n }-{ m }_{ k }) }^{ 2 } }\]두 범주의 중심은 최대화하고, 분산은 최소화하는 게 우리의 목표입니다. 동시에 한꺼번에 할 수는 없을까요? 간단한 방법이 있습니다. 두 범주 중심을 분자, 두 범주의 분산을 분모에 넣고 이 식을 최대화하는 겁니다. 이를 행렬 형태의 목적함수로 나타내면 다음과 같습니다.
\[J(w)=\frac { { ({ m }_{ 1 }-{ m }_{ 2 }) }^{ 2 } }{ { s }_{ 1 }^{ 2 }+{ s }_{ 2 }^{ 2 } } =\frac { { w }^{ T }{ S }_{ B }w }{ { w }^{ T }{ S }_{ W }w } \\ { S }_{ B }=({ m }_{ 1 }-{ m }_{ 2 }){ ({ m }_{ 1 }-{ m }_{ 2 }) }^{ T }\\ { S }_{ W }=\sum _{ n\in { C }_{ 1 } }^{ }{ ({ x }_{ n }-{ m }_{ 1 }){ ({ x }_{ n }-{ m }_{ 1 }) }^{ T } } +\sum _{ n\in { C }_{ 2 } }^{ }{ ({ x }_{ n }-{ m }_{ 2 }){ ({ x }_{ n }-{ m }_{ 2 }) }^{ T } }\]목적함수 $J(w)$은 $w$에 대해 미분한 값이 0이 되는 지점에서 최대값을 가집니다. 아래 식과 같습니다.
\[({ w }^{ T }{ S }_{ B }w){ S }_{ W }w=({ w }^{ T }{ S }_{ W }w){ S }_{ B }w\]그런데 위 식에서 괄호 안은 계산해보면 스칼라가 됩니다. 각각의 차원수를 고려하면 (1Xd) (dXd) (dX1)이 되기 때문입니다. 그럼 위 식 양변을 좌변 괄호안의 스칼라값으로 나누어 약간 정리를 하면 아래와 같은 형태가 됩니다.
\[{ S }_{ W }w=\lambda { S }_{ B }w\\ { { S }_{ B } }^{ -1 }{ S }_{ W }w=\lambda w\]이 식 어디서 많이 보시지 않았나요? 네 그렇습니다. 바로 고유값, 고유벡터 구할 때 바로 그 $AX=λX$ 꼴입니다. 즉 새로운 축 $w$는 $S_B$의 역행렬과 $S_W$를 내적한 행렬의 고유벡터라는 이야기죠.
자, 그럼 여기서 $S_B$와 $S_W$는 어떻게 구할까요? 각각 우리가 가진 데이터의 평균과 분산입니다. 데이터로부터 구할 수 있다는 이야기죠. 이 행렬을 고유값분해하여 새로운 축 $w$를 구할 수 있습니다.
이를 가지고 예측은 어떻게 할까요? 새로운 데이터($x’$)가 주어지면 이를 $w$와 내적해 각각의 스코어를 낼 수 있습니다. 그 스코어가 일정값보다 크면 $C_1$범주, 작으면 $C_2$ 범주로 분류를 하게 됩니다.
LDA에 대한 두번째 접근
LDA를 확률모형으로부터 도출할 수도 있습니다. 베이즈 룰(Bayes’ Rule)을 이용한 방식입니다. 베이즈 룰 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다. 그럼 베이즈 룰을 활용해 LDA를 구현해보도록 할까요? 범주가 두 개($W_1$, $W_2$) 있다고 가정해보죠. 이를 그림으로 나타내보면 아래처럼 될 겁니다.
우선 데이터($X$)로부터 사전확률 $P(W_1)$, $P(W_2)$을 구합니다. 어떻게 구하느냐고요? 범주가 $W_1$인 데이터 개수, $W_2$인 데이터 개수를 각각 전체 데이터 개수로 나눠주면 됩니다. 우리가 하고 싶은 건 이겁니다. 새로운 데이터 $x$가 주어졌을 때 이게 어떤 클래스에 속하는지 알아맞혀 보려고 하는 것이죠. 이를 지금까지 논의한 내용을 바탕으로 식을 쓰면 아래와 같이 됩니다.
\[\begin{align*} P({ W }_{ i }|x)&=\frac { P(x|{ W }_{ i })P({ W }_{ i }) }{ P(x) } \\ &=\frac { P(x|{ W }_{ i })P({ W }_{ i }) }{ P(x|{ W }_{ 1 })P({ W }_{ 1 })+P(x|{ W }_{ 2 })P({ W }_{ 2 }) } \end{align*}\]새로운 데이터 $x$가 등장하면 LDA 모델은 P($W_1$|x)와 P($W_2$|x)를 각각 구합니다. 둘 중 전자가 크면 $W_1$으로, 후자가 크면 $W_2$로 분류를 하게 되는 방식입니다. 사후확률인 P($W_i$|x)는 새로운 데이터 $x$가 주어졌을 때(=정답 범주를 모를 때=예측할 때) $W_i$일 확률, 즉 검증데이터가 특정 범주에 할당하기 위한 스코어를 의미합니다. 범주 분류를 위한 확률(스코어)를 내어주는 함수를 판별함수(discriminant function)라고 합니다.
LDA의 중요한 가정은 데이터 분포가 다변량 정규분포(multivariate normal distribution)을 따른다는 사실입니다. 많은 자연, 사회현상이 정규분포를 따르고 있고 그 예측력 또한 많은 실험을 통해 검증된 연속확률분포입니다. 다변량 정규분포의 파라메터는 평균(벡터)와 공분산(행렬)입니다. 이 두 파라메터와 정규분포 확률함수로 P(x|$W_i$)를 구할 수 있고, 이를 우리가 이미 알고 있는 사전확률 $P(W_i)$과 함께 계산해 범주를 판별한다는 것이 LDA를 베이지안 관점에서 접근하는 방식의 핵심입니다.
마치며
자, 그럼 복기를 해볼까요? 두번째 챕터에서 설명드린 두 범주의 데이터를 가장 잘 분류하는 새로운 축인 $w$는 두 범주의 평균 벡터의 차이를 분자, 두 범주 분산의 합을 분모로 두고 이 식을 최대화하는 과정에서 도출됩니다. 미지수 $w$로 미분을 해서 0이 되는 지점이 이 식을 최대화하는 지점입니다. 베이지안 법칙 관점에서는 사후확률 P($W_1$|x)와 P($W_2$|x)가 같은 지점을 결정경계로 놓고 식을 도출하게 되는데요, 이것이 결과적으로는 첫번째 방식인 $w$로 미분을 해서 0이 되는 지점과 본질적으로 같게 돼서 두 접근이 사실상 같은 결과를 내는 것을 확인할 수 있습니다. 두 접근 모두 데이터의 분포가 $p$차원의 다변량 정규분포를 따른다는 전제가 내재돼 있습니다.
LDA로 두 개 범주를 분류한 부분은 좌측 상단 그림과 같습니다. 두번째 접근에서 각 범주의 공분산행렬이 동일하다는 가정을 하고 식을 정리하면 $Ax+b=0$ 꼴의 선형식이 된다고 설명을 했는데요. 실제로 결정경계가 직선임을 시각적으로도 확인할 수 있습니다. 그런데 공분산이 다르다고 놓고 식을 정리하면 $Ax^2+Bx+c=0$ 꼴의 Quadratic form이 됩니다. 그래서 우측 상단 그림을 보면 결정경계가 비선형인 모양을 볼 수 있습니다.
LDA이든 QDA이든 학습데이터의 정보를 압축해 데이터 분류를 위한 결정경계를 만들어낸다는 점에서 본질적으로 동일합니다. 학습데이터의 패턴만 가지고도 충분히 좋은 예측모델을 만들어낼 수 있다는 얘기입니다. 질문이나 제언 있으시면 언제든지 댓글, 이메일로 알려주시기 바랍니다. 여기까지 읽어주셔서 대단히 감사합니다.
Appendix : 두번째 접근의 수식 도출
LDA를 베이지안 관점에서 접근하는 방식과 관련해 수식을 유도해 보겠습니다. 저 역시 정리 용도로 남겨두는 것이니 스킵하셔도 무방합니다.
정규분포를 따르는 $N$개 데이터가 $k$개 범주로 구성돼 있는 $p$차원(변수 개수=$p$개)의 데이터 $X$의 평균과 공분산은 각각 아래와 같습니다. 평균벡터의 요소는 각각 변수 관측치의 평균입니다. 예컨대 $μ_1$은 데이터 첫번째 변수의 평균입니다. 마찬가지로 공분산행렬의 요소는 각각 변수 관측치의 공분산입니다. σ12는 첫번째 변수와 두번째 변수의 공분산, 즉 $cov(X_1, X_2)$입니다.
\[\mu =\begin{bmatrix} { \mu }_{ 1 } \\ ... \\ { \mu }_{ p } \end{bmatrix}\\ \Sigma =\begin{bmatrix} { \sigma }_{ 11 } & ... & { \sigma }_{ 1p } \\ ... & ... & ... \\ { \sigma }_{ p1 } & ... & { \sigma }_{ pp } \end{bmatrix}\]위 두 개 파라메터만 알고 있으면 아래와 같이 이미 정의돼 있는 다변량 정규분포 확률함수로 P(x|$W_i$)를 구할 수 있게 됩니다. 그렇다면 P(x|$W_i$)의 의미는 무엇일까요? 범주정보가 주어졌을 때(=정답 범주를 알고 있을 때=학습할 때) $x$가 나타날 확률, 즉 학습데이터 내에 있는 $W_i$의 분포가 됩니다. P(x|$W_i$)는 다음과 같습니다. ($p$는 데이터 변수 개수)
\[P(X=x|{ W }_{ i })=P(x|{ W }_{ i })=\frac { 1 }{ { (2\pi ) }^{ p/2 }{ \left| { \Sigma }_{ i } \right| }^{ 1/2 } } \exp\left[ -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i }) \right]\]판별함수 $σ$는 새로운 데이터 $x$에 대해 범주(클래스)를 할당해주는 역할을 하는데요, 범주 개수($k$개)만큼의 판별함수가 필요하게 됩니다. 새로운 데이터에 대해 가장 큰 확률값을 내어주는 범주로 분류하게 됩니다. 판별함수 식은 아래와 같습니다.
\[\begin{align*} { \sigma }_{ i }(x)&=P({ W }_{ i }|x)\\ &\propto P(x|{ W }_{ i })P({ W }_{ i })\\ &\propto \ln { P(x|{ W }_{ i }) } +\ln { P( W }_{ i }) \\ \end{align*}\]위의 판별함수 계산에서 유의할 부분은 $P(x)$를 나눠주는 부분을 생략해도 된다는 점입니다. $k$개 판별함수의 분모는 $P(x)$로 동일하고, 범주 예측엔 판별함수 결과값 크기만 중요하기 때문에 분모를 생략해 계산상 이득을 취하기 위해서입니다. 이 식에 자연로그를 취해도 판별함수 간 크기는 달라지지 않기 때문에 계산상 편의를 위해 로그변환을 한 것이 위 식 마지막 결과입니다.
위 식 P(x|$W_i$)에 다변량 정규분포의 확률함수를 대입해 정리하면 아래와 같습니다. \(\begin{align*}ln { P(x|{ W }_{ i }) } &= \ln { \frac { 1 }{ { (2\pi ) }^{ p/2 }{ \left| { \Sigma }_{ i } \right| }^{ 1/2 } } } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i })\\ &=\ln { \frac { 1 }{ { (2\pi ) }^{ p/2 } } } +\ln { \frac { 1 }{ { \left| { \Sigma }_{ i } \right| }^{ 1/2 } } } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i })\\ &=-\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ i } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ i }) }^{ T }{ { \Sigma }_{ i } }^{ -1 }(x-{ \mu }_{ i }) \end{align*}\)
위 식을 자세히 보시면 미지수가 하나도 없는 상수라는 점을 확인할 수 있습니다. 데이터 $x$는 물론 변수 개수인 $p$, $π$, $Σ$, 평균까지 이미 우리가 다 알고 있는 값들이기 때문입니다. 이 값들을 위 식에 넣어서 계산하기만 하면 P(x|$W_i$)를 바로 구할 수 있습니다. 한편 나머지 $P(W_i)$는 i번째 범주의 개체 수를 전체 데이터 수로 나눠서($N_i/N$) 바로 구할 수 있습니다.
그럼 이제 결정경계(decision boundary)를 살펴보겠습니다. 범주가 두 개일 때를 예를 들어보죠. 판별함수 $σ_1$과 $σ_2$의 값이 같은 지점이 바로 분류 경계면이 될 겁니다. $σ_1$이 조금이라도 크면 $W_1$ 범주, 반대 상황이면 $W_2$ 범주로 분류되기 때문입니다. 이를 위 식을 기준으로 넣어서 정리하면 아래와 같은 식이 됩니다.
\[\begin{align*} { \sigma }_{ 1 }(x)-{ \sigma }_{ 2 }(x)&=0 \\ -\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ 1 } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ 1 }) }^{ T }{ { \Sigma }_{ 1 } }^{ -1 }(x-{ \mu }_{ 1 })+\ln { P({ W }_{ 1 }) } \\-(-\frac { p }{ 2 } \ln { 2\pi } -\frac { 1 }{ 2 } \ln { \left| { \Sigma }_{ 2 } \right| } -\frac { 1 }{ 2 } { (x-{ \mu }_{ 2 }) }^{ T }{ { \Sigma }_{ 2 } }^{ -1 }(x-{ \mu }_{ 2 })+\ln { P({ W }_{ 2 }) } )&=0\\ { (x-{ \mu }_{ 1 }) }^{ T }{ { \Sigma }_{ 1 } }^{ -1 }(x-{ \mu }_{ 1 })-{ (x-{ \mu }_{ 2 }) }^{ T }{ { \Sigma }_{ 2 } }^{ -1 }(x-{ \mu }_{ 2 })-\ln { \frac { \left| { \Sigma }_{ 2 } \right| }{ \left| { \Sigma }_{ 1 } \right| } } +2\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } &=0 \end{align*}\]뭔가 식이 엄청 복잡해보이죠? 일단은 범주 각각의 분산이 동일하다고 가정해보겠습니다. 그러면 둘의 분산은 합동분산(pooled variance) 공식에 의해 아래와 같이 같이 쓸 수 있습니다.
\[{ \Sigma }_{ 1 }={ \Sigma }_{ 2 }={ \Sigma }=\left[ \frac { { n }_{ 1 }-1 }{ ({ n }_{ 1 }-1)+({ n }_{ 2 }-1) } \right] { \Sigma }_{ 1 }+\left[ \frac { { n }_{ 2 }-1 }{ ({ n }_{ 1 }-1)+({ n }_{ 2 }-1) } \right] { \Sigma }_{ 2 }\]이를 판별함수 식에 넣어 정리하면 아래와 같습니다.
\[{ { (\mu }_{ 1 }-{ \mu }_{ 2 }) }^{ T }{ \Sigma }^{ -1 }x-\frac { 1 }{ 2 } { { (\mu }_{ 1 }-{ \mu }_{ 2 }) }^{ T }{ \Sigma }^{ -1 }{ { (\mu }_{ 1 }+{ \mu }_{ 2 }) }-\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } =0\]위 식은 복잡해보이지만 자세히 뜯어보면 $Ax+b=0$의 선형식(linear equation)이 됩니다. $x$를 제외하면 미지수가 전혀 없는 상수항이기 때문입니다. 결정경계가 직선 모양이라는 뜻인데요. 이 상수항들은 모두 학습데이터의 패턴이 녹아들어 있는 결과입니다. 위 식에 $x$를 넣어 0보다 큰 값이 나오면 $W_1$ 범주, 그렇지 않으면 $W_2$ 범주로 분류하는 방식입니다.
한편 $Σ_1$과 $Σ_2$가 각각 다르다고 놓고 풀면 아래와 같은 식이 됩니다.
\[-\frac { 1 }{ 2 } { x }^{ T }({ { \Sigma }_{ 1 } }^{ -1 }-{ { \Sigma }_{ 2 } }^{ -1 })x+({ \mu }_{ 1 }{ { \Sigma }_{ 1 } }^{ -1 }+{ \mu }_{ 2 }{ { \Sigma }_{ 2 } }^{ -1 })x-\frac { 1 }{ 2 } ({ \mu }_{ 1 }^{ 2 }{ { \Sigma }_{ 1 } }^{ -1 }-{ \mu }_{ 2 }^{ 2 }{ { \Sigma }_{ 1 } }^{ -1 })+\frac { 1 }{ 2 } \ln { \frac { \left| { \Sigma }_{ 2 } \right| }{ \left| { \Sigma }_{ 1 } \right| } } -\ln { \frac { P({ W }_{ 1 }) }{ P({ W }_{ 2 }) } } =0\]위 식도 자세히 보면 $Ax^2+bx+c=0$의 2차식 형태입니다. 따라서 결정경계는 곡선 형태가 됩니다.
Comments