Fisher LDA 이론 정리

이전 아맞다에서 Linear Discriminant Analysis (LDA)에 대해 다루었다. 이번에는 Fisher LDA에 대해서 수식적으로 이해해 보는 글을 작성한다. 

이전글: 

https://hi-lu.tistory.com/entry/%EC%95%84-%EB%A7%9E%EB%8B%A4-%08LDA%EC%84%A0%ED%98%95%ED%8C%90%EB%B3%84%EB%B6%84%EC%84%9D

LDA(선형판별분석) 에 대한 완벽 개념

참고 : 머피의 머신러닝 

 

---

사전지식

LDA

지난글인 LDA에 대해 이미 읽었다 가정하고 LDA에 대해 간략히 요약해 보자. Discriminant Analysis, 판별모델은 class posterior 기반의 모델로, 데이터 x가 주어졌을 때 특정한 클래스 c로 분류될 확률을 구하는 문제였다. 이 posterior에 log를 붙인 log posterior가 판별 함수의 역할을 한다. 

LDA의 class posterior

이때 y가 class c에 해당할 때의 x 분포(class conditional likelihood)가 가우시안 분포라면 Gaussian Discriminant Analysis(GDA)가 된다. 각 클래스별로 가우시안 분포를 따르는 것이며, log posterior가 최대가 되는 평균 u와 분산 ∑를 구하는 것이 목표다. 

 

만약 모든 클래스의 공분산이 같다면 (∑c1 = ∑c2 = ∑c3 ...) LDA를 의미한다. 이럴 경우 x에 따라서 공분산값이 달라지지 않기 때문에 log posterior가 예쁘게 정리가 된다. W * x + b (linear)와 같이 말이다. 

 

 

EigenVector

행렬을 고유값(λ)과 고유 벡터(u)로 분리할 수 있다. 한 행렬에게는 행렬의 rank만큼의  eigen value와 vector를 가질 수 있으며, 각 쌍에서 eigenvalue는 항상 최대값을 지닌다. 예를들어 한 쌍의 고유행렬 후보가 [2,4] 라면 실제 고유값은 최대로 나눌 수 있는 2, 고유벡터는 [1,2]가 된다.

 

즉 어떠한 벡터를 A u= λ * u로 나타낼 수 있으며 이때  λ는 A를 나눌 수 있는 최대값임이 핵심이다.

 

 

Fisher's LDA (FLDA)

LDA의 문제점 중 하나는 피쳐 dimension이 커질수록 high dimensionality 문제에 빠진다는 것이다. 이런 문제들을 해결하는 방법론은 피쳐를 사영(projection) 하여 dimension을 줄이는 Principal Component Analysis(PCA) 계열이 대표적이긴 하지만, class y의 정보가 주어지는 supervised 계열에서 굳이 쓸 필요가 없다. 대체제로 나온 게 FLDA다. FLDA는 판별 모델 속성과 생성모델 속성을 둘 다 갖고 있는데, 한 가지 단점은 차원 dimension이 클래스의 수보다 작아야 한다는 것이다. 

• FLDA : K <= C - 1 을 만족해야 한다.

PCA와 FLDA의 차이는 아래 그림에서 볼 수 있다. 왼쪽이 PCA의 projection 결과, 오른쪽이 FLDA의 projection 결과다. 해당 데이터에서 PCA보다 FLDA가 더 잘 클래스를 구분했음을 알 수 있다. (책에선 이렇게 간단한 예제로 나왔지만 FLDA가 PCA보다 무조건 잘 사영된다는 건 절대 아니다.) 

PCA와 FLDA

 

1D projection

데이터를 1차원으로 projection해본 예시를 통해 FLDA가 어떤 특성을 지니게 되는지 알아보자. 2개의 클래스(C = 2)로 분류하고자 하는 데이터를 생각해 보자. FLDA에서도 클래스간 평균은 멀게,  클래스 내 분산은 가깝게 학습되길 원한다. 데이터 x에 대해 두 클래스별 평균은 아래와 같이 나올 거다. 

class mean

 평균 u을 w에 projection한 새로운 평균 m (m = w*u) 과 데이터를 w에 projection한 새로운 데이터 z (z = w*x) 를 통해 사영 공간에서의 분산을 아래와 같이 구할 수 있다. 분산이 (데이터 - 평균)의 제곱임을 기억하자. 

 

variance

사영공간에서의 평균과 분산을 통해 새로운 목적함수를 설계할 수 있다. 아래 식의 분자는 평균간의 차, 분모는 variance간 합을 의미한다. 분자가 커지고 분모가 작아지게끔 목적함수를 최적화할 것이다. 

 

새 objective fcn

위 함수의 m과 s 은 각각 사영하고자 했던 벡터 w로 나타낼 수 있었다. 이를 대입해보자. 이 식의 분자 u2 - u1의 제곱을 (1)클래스 간 얼마나 멀리 떨어져 있는지로 해석할 수 있다. 마찬가지로 분모는 (2)클래스 내에서 얼마나 데이터가 멀리 떨어져 있는지를 의미한다. 

(1)는 S_b, (2)는 S_w라는 행렬이 된다.  다시 정리하지만 Sb는 평균 차의 제곱, Sw는 분산을 의미한다. 

클래스 간 평균 차

클래스 내 분산

따라서 목적함수 J는 아래와 같이 쓸 수 있다. 

J의 최대값을 구하기 위해서 d J(w) = 0 을 만족하는 지점을 찾아야 한다. 미분을 해보자. 

 

J의 최대값을 구하기 위해 미분시 0이 되는 지점을 찾아야 한다.

따라서 J를 최대화하기 위해선 S_w * w가  S_b의 eigenvector가 되어야 한다.  즉 S_b w를 고유값 분해했다고 생각했을 때, eigen value λ가 J와 동치가 된다! (eigenvalue의 정의를 다시 생각해보자.) 

Sb *w 수식

 

 

지금 전제조건은 클래스가 2종류일때를 보고 있으므로 비교적 간단하게 정리할 수 있는데, Sb * w는 평균차(u2 - u1) 와 사영한 평균 차 (m2 - m1) 의 곱이 된다. 

Sb * w 수식

 

지금까지 모은 수식들을 통해서 λ w 의 식을 아래와 같이 정리할 수 있다. 

이 식은 다음처럼 w에 대한 비례관계를 도출할 수 있다. 물론 w는 방향을 의미하기 때문에 S-1_w (u2 - u1)와 동일한 값을 가질 때와 같은 말이 된다. 

FLDA의 사영 w

따라서 2개의 클래스가 있을 때 FLDA의 사영 w는 아래의 값이 최적인 것이다!

 

 

multiple classes와 더 큰 dimension에서의 FLDA

1D FLDA에서는 하나의 벡터 w에 대해 사영했지만, 2개 초과의 multi class를 행렬 W에 대해 사영한다고 생각해보자. 위에서는 u1, u2 그리고 m1, m2 2개만 필요했지만 이제 각각 c개에 대해 생각해봐야 한다. 그래서 Sw~와 Sb~는 아래와 같이 다시 쓰여진다. 이때 S~ =  WT * S * W를 의미한다.  

 

목적함수도 위에서 생각한 개념 그대로 가져온다. 

objective fcn

여기서 생각해봐야할 점은 Sb의 rank다. 클래스 수 C에 대해 C-1 이 Sb의 rank이기 때문에, projection linear dimension은 절대 C-1보다 커질 수가 없는 것이다.

참고로 만약 S가 특이행렬(역행렬 X)이라면 PCA와 식이 동일해진다. 

 

 

---

 

오늘은 데이터 피쳐를 사영함으로써 동작하는 FLDA의 수식적 이해를 진행해 보았다. eigen value의 특성을 이용해 클래스간 거리는 멀고 클래스내 거리는 가깝게 하는 목적 함수를 최대화할 수 있었다. 이를 2개 클래스 데이터를 기준으로 해서 수식을 전개해 보는 것을 중심으로 풀어보았다. 처음엔 이해하는데 조금 오래 걸렸는데, 이 글을 읽는 분들은 나보다 빨리 이해하는데 도움이 되면 좋겠다.