[인공지능] Fisher Discriminant Analysis(선형판별분석)

Fisher Discriminant Analysis란?

FDA 혹은, Linear Discriminant Analysis(LDA)라고 불린다.

데이터들을 하나의 직선(1차원 공간)에 projection시킨 후 그 projection된 data들이 잘 구분이 되는가를 판단하는 방법이다.

출처 : https://imgur.com/6ggd2F0

데이터가 잘 구분되어있다는 의미는 위 그림 중, 왼쪽 보단 오른쪽 처럼 구분이 되어야 됨을 의미한다. 이 특성을 보자면, 데이터들이 모여있고, 중심부가 서로 멀수록 데이터의 구분이 잘 됐음을 알 수 있다. 즉, projection 후 두 데이터들의 중심(평균)이 서로 멀수록, 그 분산이 작을수록 구분이 잘 되었다고 얘기할 수 있다. 이렇게 잘 분류되게끔 하는 하나의 vector w를 구하는 것이 LDA이다.

 

 

 

variance 구하기

데이터 D = {x}_i^N  라고 할 때,

원래 data들의 평균

projection된 data들의 평균은

따라서 w방향에 projection된 data들의 분산은

||w||=1으로 생각을 하기 때문에,  위와 같은 식으로 구할 수 있다.

가운데 [ ]안의 식은 covariance Matrix(∑, 공분산행렬 , x가 D차원 벡터일 때 DxD matrix)로 표현할 수 있다.

 

 

FDA(LDA)를 사용하여 objective function만들기

data가 잘 분류되기 위해선 위에서 언급한 것 처럼 각 class의 분산은 작아야하고, 평균은 멀리 떨어져있어야 된다(전체 데이터의 분산은 커야된다.).

데이터를 projection 했을 때 그래프가 다음과 같고

다음 조건들을 만족한다면, objective function은

 

 

이 된다.

 

 

잘 분류되기 위해 분자는 전체 분산으로, 최대한 커져야되고, 분모는 class conditional density function의 variable으로, 최대한 작아야된다. 즉, L(w)의 최대값을 갖게하는 w가 optimal solution이 된다.

분모 ( )안에 있는 값들은 각 데이터별로 가중치를 주기 위해 추가되었다.

 

 

 

Object function으로 부터 w값 알아내기

이런 꼴은 eigenvector problem (Ax - (lambda)x = 0)과 비슷하다. 

그래서 이러한 꼴은 Generalized eingenvector problem이라 지칭하고, 이는 해석해를 가지도록 문제를 풀었다고 간주한다.

 

 

이때, 시그마 값들이 DxD matrix이기 때문에 조건을 만족시키는 결과값은 최대 D개까지 나올 수 있다.(D개의 eigen vector)

이중 L(w)가 최대가 되게끔 하는 w를 찾아야되는데

최대 D개의 eigen value들 중에서 가장 큰 값이 최대값이 되고, 그때의 eigen vector가 우리가 원하는 solution, w이다.

 

 

 

문제점

이 방법을 사용한다면, 데이터 수가 차원보다 적을 경우 문제가 생긴다 (N < D)

 

문제가 생기는 이유.

 

∑는 모든 벡터에서 뮤를 빼주면서 계산이 되기 떄문에, (N-1) dimensional space를 span할 수 있다. (Rank가 N-1)

∑₁₂의 Rank는 ∑₁의 Rank + ∑₂의 Rank이기 때문에 (N₁-1)+(N₂-1) = N-2가 된다.

 

D차원 vector v가 있다고 가정했을 때,

∑에는 포함되지만 ∑₁₂에는 포함되지 않는 값이 무조건 있다.(∑의 space는 n-1, ∑₁₂의 space는 n-2이기 때문에)

이는 v^T∑v != 0 & v^T∑₁₂v = 0 인 v가 무조건 존재한다는 의미이다.(v가 ∑₁₂의 Null space에  포함되는 경우가 생긴다) 때문에

즉, objective function은 ∑₁₂가 포함하지않고있는 v방향을 solution으로 내놓는 상황이 발생한다.

 

 

문제상황 예시

2개의 class가 있을 때 다음과 같은 sampling data들이 있다고 가정하자.

각 class는 같은 방향만을 span하고, 그에 수직인 v벡터가 optimal solution이 된다.

sampling data가 바뀌어 다음과 같이 주어진다면

같은 방향으로 span하지 않는 data가 하나만 나오더라도 solution이 v벡터가 나오지 않는다.

이처럼 N<D상황에선, sampling data하나하나마다 solution이 계속 바뀌는 상황이 발생한다. (ill-posed problem, 잘 정의되지않은 문제)

 

다시말하면, class내부의 variance가 전혀 없는 상황까지 줄어드는 공간이 반드시 있고, 그 방향이 ∑₁₂의 Null space가 된다.

때문에, 다른 sampling data로 solution을 찾아보면 이전 solution과 절대로 다르게 나오게된다.

이는 data 하나하나를 너무 많이 고려를 한 것이고 이를 over fitting했다고 말한다.

 

 

해결방법

Regularization을 해준다.

따라서, 보통 가지고있는 data수가 충분히 많지 않은 경우에는 regularization을 해주어야된다.