본문 바로가기

Enginius/Machine Learning

An Introduction to Variable and Feature Selection

Variable selection


Variable과 feature selection은 매우 중요하다. 특히나 하나의 item에 대해서 수 십, 수 백, 혹은 수 천 개의 변수가 있는 경우에는 더하다. 인터넷 문서, 유전자 분석 등에선 이런 경우가 있다. variable selection의 목표는 세 가지로 나뉜다. 

1. Predictor 의 성능을 높이기 위해서 

2. 좀 더 빠르고, cost-effective한 (효율적인) predictor를 만들기 위해서 

3. 마지막으로는, 데이터를 생성한 underlying process를 더 잘 이해하기 위해서 이다. 


Check list 


1. Domain knowledge가 있는가? 만약 그렇다면 ad hoc feature를 만들어라. 

2. 데이터들이 commensurate한가? 스케일이 맞지 않으면 normalize해라. 

3. 데이터들 사이에 interdependence가 있는가? 만약 그렇다면 feature set을 늘려서 서로 conjunctive하게 해라. 

4. 입력 변수를 prune할 필요가 있는가? 예를 들면 속도나 효율을 위해서. 만약 그렇지 않다면 disjunctive한 feature를 만들던가 feature들을 weighted sum해서 써라. 

5. 각 feature를 개별적으로 이해해야 하나? 만약 그렇다면 variable ranking을 해라. 

6. Predictor가 필요한가? 

7. 데이터가 dirty한가? 만약 그렇다면 top ranking variable을 이용해서 outlier를 걸러내라. 

8. 무엇을 먼저 할 지아는가? 모른다면 linear을 해봐라. 그리고 forward selection을 써라. 

9. 새로운 아이디어와 시간, 그리고 충분한 데이터가 있는가? 그렇다면 이것저것 해봐라. 

10. 안정적인 solution을 원하는가? 그렇다면 여러번 해보고, bootstraps를 써라. (당연)



Variable ranking


많은 variable selection algorithm들은 variable ranking을 중요한 메커니즘으로 사용하는데 이는 이 알고리즘이 단순하고, 많은 데이터에도 적합하고, 실제로도 괜찮은 결과가 나오기 때문이다. 그래서 많은 논문에서 이를 baseline으로 사용한다. 이 알고리즘은 예측을 위해서만 사용되지는 않는다. 


우리에게 '$m$'개의 데이터가 있고, 각 데이터는 '$n$'차원의 입력과 '$1$'차원의 출력으로 이뤄졌다고 하자. Variable ranking은 '$S(i)$'의 scoring function을 사용해서 각 차원의 score를 매긴다. 즉 입력 데이터의 몇 번째 차원이 중요한지를 구하려고 한다. 


Kohavi and John (1997)에 따르면 variable ranking을 filter method이다. 즉 이것이 으미하는 것은 predictor가 무엇인지 상관없이 이는 preprocessing step이라는 것이다. 물론 특정 가정이 주어지는 이는 주어진 predictor에 대해서 optimal choice일 수 있다. 자세한 것은 생략. 


Correlation criteria

Pearson correlation coefficient는 다음과 같이 정의된다. 

$$ R(i) = \frac{cov(X_i, Y)}{\sqrt{var(X_i)var(Y)}} $$

여기서 '$cov$'는 covariance를 '$var$'는 variance를 의미한다. 이 '$R(i)$'의 추정치는 다음과 같이 구해진다. 

$$ R(i) = \frac{ \sum_{k=1}^m(x_{k,i}-\bar{x}_i)(y_k-\bar{y})}{\sqrt{\sum_{k-1}^m(x_{k,i}-\bar{x}_i)^2 \sum_{k=1}^m(y_k-\bar{y})^2)}} $$

이 변수는 '$x_i$'와 '$y$'의 평균을 0으로 한 뒤의 cosince이다.


Linear regression에서는, '$R(i)$'는 평균 주변에 total variation의 fraction을 의미하기 때문에, '$R(i)^2$'는 각 individual variable들의 linear fit이 얼마나 잘 되었는지를 나타내게 된다.


이 변수는 two-class 분류에도 확장될 수 있다. 이 때 '$y$'는 '$+1$' 혹은 '$-1$'이다. 그리고 이는 Fisher's criterion과도 밀접한 관계가 있는 것이 알려졌다. 


'$R(i)$'와 같은 correlation criteria는 variable과 target 사이에 linear dependency만을 고려할 수 있다. 이러한 제약을 nonlinear까지 확장시키는 방법은 한 variable만을 사용해서 target과 non-linear fit을 만들고, 이 fit이 얼마나 잘되었는지를 확인하는 것이다. 하지만 overfitting의 문제 때문에 쉽지 않아보인다. 


Single variable classifiers


앞에서 이미 언급했듯이 '$R(i)^2$'를 regression문제에 ranking criterion으로 사용하는 것은 각 변수의 linear fit이 얼마나 잘되었는지를 의미한다. 이러한 아이디어를 classification으로 확장시킬 수 있다. 즉 각 single variable로 만들어진 분류기의 성능을 확인하는 것이다. 



Small but revealing examples


모가 잘되고, 모가 안되는지 확인해보자. 


Can presumably redundant variables help each other?


불필해보이는 변수들이 서로 도움이 되는가? 

Variable ranking의 일반적인 criticism은 이것이 redundant subset을 고르게 된다는 것이다. 더 작은 subset of complementary variables로도 같은 성능이 얻어질 수 있다는 것이다. 하지만 혹자는 redundant 변수를 더함으로서 성능 향상을 이룰 수 있는지 궁금할 것이다. 



위 그림 1에 있는 분류 분제를 고려해보자. 각 class에 대해서 우리는 100개의 random example을 뽑았다. 그리고 서로 다른 variable들은 해당 클래스의 reference position을 45도씩 돌리면서 뽑았다. 즉 애초에 소스는 같은 곳에서 얻어진 것이다. 그렇다면 redundant 데이터를 사용하는 것은 어떤 의미가 있을까? 우리의 예측을 좀 더 확실하게 할 수 있다는 것이다. 이는 다음의 기초적인 확률에 기반한다. 

'$n$'개의 iid random variable을 평균을 내면, standard deviation은 '$\sqrt{n}$'만큼씩 줄게 된다. 즉 같은 source에서 나온 redundant할 수 있는 변수를 더함으로서 우리는 더 좋은 class separation을 얻을 수 있게 되는 것이다. (하나의 데이터가 아니라 데이터의 축이 늘어나는 것이다! 헛갈리지 말자. )


How does correlation impact variable redundancy?

Redundancy를 나타내는 다른 지표는 correlation이다. 혹자는 variable redundancy가 within class variable correlation을 높일 때 어떻게 변하는지 궁금할 것이다. 아래 그림 2에서 각 class의 중심은 이전 예제와 같이 있다. 하지만 여기서 우리는 co-variance를 추가하였다. 



위와 다르게 두 데이터가 같은 방향으로 나타나는 것을 알 수 있다. 이는 co-variance 때문이다. Covarance의 off diag term이 0이 아닐 경우 위와 같이 데이터의 양상이 비슷하게 나타나는 것을 알 수 있다. 결론만 말하자면 두 variable이 완전히 correlate되어있다면, 이것이 진정한 redundant하다는 것을 나타낸다. 


위의 두 예제 모두 데이터를 각 축으로 projection 시키면 같은 분포를 같는다. (Gaussian의 marginal은 다시 Gaussian) 즉 여기서 알 수 있는 것은 variable 사이의 correlation이 매우 중요하다는 것이 각 variable 사이의 correlation을 고려하지 않고, 각각을 따로 볼 경우 옳지 못한 분석이 된다는 것이다. 


Can a variable that is useless by itself be useful with others?

이 질문 좀 철학적이다. 혼자로는 쓸모 없는데 같이는 쓸모 있을 수 있는가? 

다변수 방법론의 concern 중 하나는 이들은 overfitting에 약하다는 것이다. 이러한 양상은 데이터의 차원이 수에 비해서 클 경우에 많이 생긴다. 그래서 적은 수의 변수 만을 사용하는 것이 좋아보인다. 하지만 혹자는 이게 중요한 데이터를 잃어버릴 수 있지 않을까 하는 걱정이 생길 수 있다. 



위의 그림을 보자. (3.a) 두 class conditional 분포가 나와있고, 이들의 covariance는 같다. (오른쪽 아래로..) 이 데이터는 두 축을 모두 보면 분리가 되지만, 한 축으로 옮겼을 경우에는 분리가 안될수도 있다. 그래서 한 축의 데이터만 보면 쓸모가 없어보일 수도 있지만, 한 축을 쓰는 것보다는 두 축을 쓰는 것이 항상 더 좋은 결과를 낼 수 있다. 여기서 알 수 있는 것은 한 축만 봐선 쓸모가 없을 수 있지만 다른 축과 합쳐졌을 땐 그 정보가 큰 정보를 줄 수 있다는 것이다. 


다음 질문은 그들 각각은 쓸모가 없는데, 합쳐지면 좋을 수 있냐는 것이다? 결론만 말하자면 좋을 수 있다. (위의 xor 문제를 보자.)


Variable subset selection


이전 섹션에서 우리는 변수의 subset을 고르는 것의 효용성에 대해서 살펴봤고, ranking에 대해서도 봤다. 이제 우리가 다루고자 하는 문제를 다뤄보자. 우린 이를 세 가지로 분리한다. 


1. Wrappers: 우리가 사용하고자하는 learning machine을 black box로 보고, predictive power를 이용해서 subset of variables의 score를 매긴다. 

2. Filters: Predictor와 상관 없이 고른다. 

3. Embedded method: 는 학습 단계에 selection을 넣는다. 



Feature construction and space dimensionality reduction


Variable의 차원을 단순히 고르는 것도 좋지만, 여러 다른 cost를 고려하지 않는다면 차원 축소도 좋은 방법일 것이다. 기계 학습의 art는 적절한 데이터 표현을 고름으로써 시작된다. Feature construction 방법론엔

Clustering, PCA/SVD, LDA와 같은 선형 방법론들, wavelet transform, Fourier 변환 등이 있다. 


Feature construction에는 두 가지 목표가 있다. 하나는 데이터를 잘 재구성하는 것이고, 다른 하나는 효과적은 predictor를 만드는 것이다. 첫 번째 문제는 unsupervised 방법론이고, 압축 등과 연관이 많다. 두 번째 방법론은 supervised이다. 


Clustering - kmeans, spectral clstering

Matrix factorization - SVD, RPCA류 

Supervised feature selection: nested subset, filters 


Validation methods


여기서는 generalization performance에 대해서 생각해보자. 어려운 문제지 이는.. Cross validation, 극단적인 leave one out 등에 대해선 윤성로 교수님의 ML 수업을 정리한데 잘 정리되어 있다.