Linear Discriminant Analysis(LDA) Approach

Classification의 경우를 살펴보자. Classifier를 표현하는 흔한 방법은 Discriminatn 함수를 사용하는 것이다. Input Data에 대해 클래스를 가장 잘 설명할 수 있는 함수를 정의하고 최대값을 가지는 Class를 설정하는 방식이라고 이해하면 된다.

 

그렇다면 Discriminant 함수는 어떤 것인가. Decision Boundary 란 클래스를 구분할 수 있는 선을 하나 긋는 것이라고 생각하면 된다. 클래스 0에 대해서 가지는 확률값이 높은 경우 클래스 0로 판별, 클래스 1에 대해서 가지는 확률값이 높은 경우 클래스 1로 판별하게 된다.

 

Generative classifier 란 데이터를 생성하기 위한 모델이다. 그렇기 때문에 데이터가 생성될 확률인 Joint Probability를 사용한다. 이 확률을 사용하여 바로 Classifier로 활용을 할 수 없기 때문에 베이즈 정리가 Posterior 로 변경하여 구해야 한다. 이 경우 LDA라고 불리는 분석 방식을 사용한다.

Generative Classifier와 Discriminative Classifier 모두 조건부 확률을 사용한다는 점이 공통점이지만 Generative의 경우 베이지안 이론을 활용한다는 점이 차이점이다. (접근 방식에 있어서 차별점이 있음으로 이해를 하면 될 것 같다)

 

 

LDA란 Between Class를 최대화하거나 Within Class 분산을 최소화하는 방식으로 샘플 데이터를 구분하는 것을 의미한다. D-dim을 가지는 데이터를 하나의 선으로 Project하는 문제를 생각해보면 된다. 

 

무슨 뜻인가 하면 해당 그래프를 보면 이해하기 쉬울 것이다. 빨간색과 파란색 데이터를 분류하기 위한 가장 적절한 선을 찾는 방법은 하나의 선으로 Project를 했을 때 섞이는 구간이 안생기는 선을 찾는 것이다. 오른쪽 아래의 선의 경우 가장 잘 구분했다고 표현할 수 있을 것이다.

 

Fisher가 해당 방법을 두 가지의 논리로 제안한다. 클래스들 간의 평균 거리를 최대화할 수 있는 분산과 클래스 내의 분산을 최소화할 수 있는 선을 찾으면 된다는 것이다. 

 

 

계속해서 LDA의 방식을 살펴보고 있다. Sw는 각 클래스 내의 분산이고 Sb는 클래스 간의 분산을 나타낸다고 하면 된다.

 

이를 히스토그램으로 살펴보면 선을 어떻게 긋는가 에 따라서 Project되는 분포가 완전히 다름을 알 수 있다. 그리고 그림상으로 보기만 해도 오른쪽이 Class를 더 잘 분별하고 있음을 알 수 있다.

 

그렇다면 W를 어떻게 찾는다는 것인가? Between class variance와 Within class variance 간의 적절한 비율을 최대화할 수 있는 방법을 살펴보면 될 것이다. Between Class는 클수록 With Class는 작을 수록 좋기 때문에 비율을 최대화할 수 있는 경우를 찾으면 두 가지의 경우를 만족한다는 것을 알 수 있다.

 

그렇다면 LDA의 Objective function은 단순히 Error에 관한 것이 아니라 Variance에 대한 비율을 최대화할 수 있는 방식으로 진행이 된다. M0를 Class 0 의 평균 M1을 Class 1의 평균이라고 했을 때 위의 식처럼 표현할 수 있다. 각 클래스의 평균은 그렇다면 어떻게 구하는지 살펴보자. Weight와 각 Input 데이터인 X를 Projection 한 것의 평균이다. Variance의 경우 Project한 공간에서 이미 구한 평균과의 차이의 제곱을 다 더한 것이라고 보면 된다. W^T에 대해서 식 밖으로 꺼내면 Original Space를 Square한 것의 곱으로 표현할 수 있다.

 

이 경우 Projection 하기 전인 Original Space에서의 상황을 표현한 것이다. S0와 S1은 각각 클래스의 분산을 표현한 것이다. 분산은 각각의 Input과 평균의 차이의 제곱이므로 위처럼 Transpose를 통해서 곱한 꼴로 표현이 된다. S0와 S1을 더한 것이 Sw로 Within-class 분산이 된다. 클래스 내의 분산의 합은 최소가 되어야 한다. 반대로 클래스 간의 평균의 차이의 제곱은 Between Class 분산으로 이 값이 커야 클래스 간의 분류를 잘한 경우라고 할 수 있다. 즉, 여기서 표현하는 Sw와 Sb는 Projection 공간이 아닌 Original 공간에서의 분산에 해당함을 알면 된다.

 

Objective 함수를 다시 분해하면 Weight에 대해서 표현할 수 있다. 이때 제약조건을 추가하고자 한다. 그렇다면 라그랑주 방법으로 최적화 지점을 찾을 수 있을 것이다.

이 부분은 Projection space 에서의 상황을 강조한 것이다. 각각 클래스의 평균을 Projection하면 하나의 Space에 존재하므로 차이의 제곱꼴 형태로 바로 표현할 수 있다. Within Class 분산도 동일하게 표현할 수 있다. 하지만 이 경우는 General 하게 표현했으므로 하나의 Unique한 값을 가질 수 없다. 그래서 Within Class 분산을 1로 Constraint를 부여하여 하나의 Unique한 값을 가지게 할 수 있다.

 

그래서 Objective 함수는 분모가 1이 되어 With in class 만 최적화하면 되는 문제로 귀결된다.

 

분산을 최대화하는 것이 Objective 함수의 목적인데 (-) 부호를 붙이게 되면 최소화하는 문제로 변경이 된다. Weight에 대해서 부분 미분을 수행하게 되면 아래 쪽에 보이는 최종적인 수식을 얻을 수 있다.

 

이를 다시 살펴보면 결국 Eigenvalue Decomposition을 하는 내용이 된다. 이 경우에 Sw가 Inverse 가능해야 한다는 것이 전제이며 Sw^-1 * Sb의 Eigenvalue를 찾는 문제가 된다. 

 

이제 Prediction을 하면 된다. LDA를 요약해서 말하면 새로운 축으로 Projection 하는 것을 의미한다. 그래서 LDA를 한 값이 특정 값(Threshold) 보다 크거나 , 작을 때로 Class를 분류하게 되면 예측을 할 수 있다.