Machine Learning : 모델 선택 방법. 2. Feature Selection

모델 선택에 있어 특별하고도 중요한 경우가 feature selection이다. feature의 수가 매우 큰 n 개 즉  n>>m (m=모델의 총개수) 라고 하자. 그런데 그 많은 feature 중에 몇개 만이 learning에 relevant (관련된) 것이라고 추측할 수 있을 것이다. 만약 n 개의 입력 feature들에 대해 (perceptron 같은, 입력에 가중치를 곱해 합한 값이 threshold를 넘으면 활성화되고 아니면 비활성화되는) simple linear classifier 를 사용한다고 가정하면, VC dimension (Vapnik-Chervonenkis dimension, 통계적 분류 알고리즘의 capacity를 측정하는 것으로, "어떤 알고리즘이 shatter할 수 (나눌수) 있는 포인트의 가장 큰 집합의 요소의 수"로서 정의됨) 은 O(n) 이 될 것이고, 이러한 overfitting은 잠재적인 문제를 갖게 될 것이다.
어떤 세팅에서, feature selection 알고리즘을 적용하여 feature의 수를 줄일 수 있다. n 개의 feature가 주어졌을 때, 2^n 개의 가능한 feature subset 이 있을 것이다. 그러면 feature selection은, 2^n 가능 모델들에 대한 model selection 문제로 바뀔수 있다. 큰수의 n에 대해, 모든 2^n 개의 모델을 비교하는 것은 무리가 있다(expensive하다). 그래서, 좋은 feature subset 을 찾는데, 휴리스틱 검색 과정 (heuristic search procedure)를 사용할 수 있다.
다음 과정을 "forward search" 라고 한다.

forward search:
1. feature index subset F를 공집합으로 초기화
2. 반복 {
  (a) i=1, ... , n , 이미 F에 포함된 feature 를 제외하면서 하나씩 넣어서 F_i 라는 subset 만들고, 이 집합의 feature 들을 이용해, 학습, 평가를 수행한다.
  (b) 위 과정에서 가장 좋은 결과를 갖는 F_i 를 선택, F라고 한다.
}
3. 전체 검색 과정을 반복하여 최선의 subset을 찾아낸다.

이 말은 결국, 1단계에서 가장 좋은 feature 1개를 뽑고, 2단계에서는 전단계에서 뽑은 feature에 1개를 더 추가해서 가장 좋은 feature set을 뽑는 과정을 반복하며 feature set을 찾는 알고리즘이다.
예를 들어, feature 가 3개가 있다면,
F_1 = {1}, F_2 = {2} , F_3 = {3} 으로 subset들이 만들어지고, 각각을 적용하여 평가하여 가장 좋은 subset을 찾아낸다. 예를 들어 F_2 였다면, 이를 F 라고 한다.
그다음 루프에서는, F를 포함하여, F_1 = {1,2}, F_3 = {2,3} 식으로 전단계에서 선택한 feature set을 포함하여 나머지 feature를 하나씩 넣어가면서 subset을 만들고 평가를 수행한다. 이러한 과정을 통해 feature selection을 수행한다. 이 과정은 feature의 개수가 미리 지정된 threshold 개수가 되면 중단한다.
이 알고리즘은 wrapper model feature selection 중 하나가된다.

backforward search:
반대로 F={1,...,n} 로 놓고 하나씩 빼가는 과정을 반복하는 것을 backward search라고 한다.

Wrapper feature selection 알고리즘은 종종 잘 동작하기도 하지만, 계산량이 O(n^2) 로 많은 편이다.

Filter feature selection 은 휴리스틱하지만 좀 계산량이 적다. 이 방법의 아이디어는, 각 feature x_i가 클래스 레벨 y 에 얼마나 informative한지 (영향력이 있는지) 측정하는 simple score S(i) 를 계산하는 것이다. 그리고 가장 높은 점수 S(i)를 가진 feature  k개를 선택하는 방법이다.
S(i)의 예로는 x_i와 y 간의 correlation 을 이용하는 것이다. 실제로는 mutual information MI(x_i, y) 를 S(i)로 쓸 수 있다.

확률 p(x_i, y), p(x_i), p(y) 는 training set의 empirical distributions에 따라 평가될 수 있다.

이 score 의 의미는, mutual information은 Kullback-Leibler (KL) divergence로 표현될 수 있음에 주목하면 알 수 있다.

이는 확률분포 p(x_i,y) 와 p(x_i)p(y)가 얼마나 다른가를 나타낸다. 만약 x_i와 y가 서로 독립적인 random variable이라면, p(x_i, y) = p(x_i)p(y) 일 것이고, KL-divergence는 0이 된다. 이런 것을 x_i는 y에 대해 "non-informative하다."라고 한다. 반대의 경우 x_i 는 informative 하고, MI 값은 큰 값이 될 것이다.

그럼 최종적으로 선택할 feature의 개수 k는 어떻게 결정할 것인가? 표준적인 방법 중 하나는, 가능한 k 값에 대해, cross validation을 수행하는 것이다. 예를 들어, naive Bayes 를 text classification에 적용할때, 여기서 설명한 feature subset을 선택하는 방법을 사용하면, classifier accuracy를 향상시키기도 한다.

(참고: 스탠포드 Andrew Ng 강의노트)