[기계학습] 12. Dimensionality Reduction

충남대학교의 김동일 교수님의 기계학습 수업을 기반으로 정리했습니다.

 

오늘은 차원 축소라고 불리는 Dimensionality Reduction에 대해서 알아보자.

 

1. Dimensionality Reduction, 차원 축소

1) Curse of Dimensionality, 차원의 저주

갑자기 차원의 저주..라니 무슨 말 일까?

 

일단 dimension은 일반적으로 feature(input)의 수를 의미한다.

동시에 높은 차원의 영역을 설명하는 것은 지수적으로 많은 데이터가 필요하다.

 

예를 들어 3차원 공간을 최소 8(2^3)개의 데이터가 골고루 커버할 수 있다. 반대로 생각하면 8개 밖에 없는 데이터를 100차원에서 다룬다는 것은, 영역을 골고루 사용하지 못하는 것을 의미한다. 8개의 데이터가 100차원에서 매우 국소한 영역을 차지하며, 그 말은 100개의 변수가 전부 데이터에 영향을 주는 것이 아니라는 것이다.

그러니 영향을 주는 변수만 다룰 수 있도록, 변수이자 차원을 최대한 축소하여 최대한 compact하고 dense한 환경에서 모델링을 해야, 전체 영역에 대해 모델이 골고루 이해할 수 있다.

 

변수가 많을 때(차원이 높을 때) 어떤 문제가 발생하는지 알아보자.

• 불필요한 변수가 존재
• 중복되는 변수가 존재
• Overfitting : 의미없는 변수에 의미 부여
• Computational Cost

즉, 중요한 변수들은 모든 변수의 부분집합이 될 수 있다!

 

2) Dimensionality Reduction

이상적인 상황

• More features, better performance (under the assumption of independency)

그러나 현실에서는

• All features cannot be independent to each other, 모든 변수가 독립을 가정하기 어렵다
• Noise features (including irrelevant, contains lots of noises…), 사용하면 위험한 변수들이 가득

 

따라서 우리의 목표는 '변수들의 작은 부분집합을 선택해서 학습하자!'

• Subset size: as small as possible (Occam’s Razor), 크기는 작으면 작을 수록
• Model performance: as good as possible, 성능은 좋으면 좋을 수록

 

3) Category of Dimensionality Reduction

자, 이제 차원을 축소하는 방법에 대해 알아보자. 차원 축소에는 두가지 방법이 있다

 

1. Feature selection method, 변수 선택

• 원래의 변수에서 직접 몇 개의 변수를 선택한다
• Filter 또는 Wrapper 방법이 있다

2. Feature extraction method, 변수 추출(구축)

• 원래의 변수를 기반으로 새로운 변수를 구축한다 by 함수

 

4) Category of Feature Selection

Feature selection method, 변수 선택 방법에는 Filter Approach와 Wrapper Approach가 있다.

기존 변수에서 선택하여 변수들의 부분 집합으로 학습을 하는 것은 똑같지만, 선택하는 과정에서 차이가 존재한다.

• Filter Approach
  Dimensionality reduction with one feed-forward preprocessing step
  학습 모델과 독립적으로 변수를 선택
• Wrapper Approach
  Learning method is involved and gives feed-back to dimensionality reduction process
  학습 모델의 참여와 피드백을 받아 변수를 선택

Wrapper가 더 성능이 좋으므로, 이를 기반으로 변수 선택 알고리즘들을 알아보도록 하자.

 

 

---

2. Feature Selection Method

1) Exhaustive Search

모든 경우의 변수들의 부분 집합을 알아보는 방법이 있을 수 있다. 즉, Full Search.

그렇다면 O(2^n-1)|n=#변수 의 복잡도가 나오는데, 지수시간의 복잡도는 실제로 구현하기에도 매우 복잡하므로 사용하지 않는다.

 

2) Heuristics

Full Search를 할 수 없으므로, 우리는 Heuristics를 통해 근사치를 구하려고 한다.

먼저 근사에는 Approximation과 Hearistic이 있는데, 간단히 전자는 범위내의 근사해라는 것을 증명해야 하지만 후자는 조금 naive한 근사값을 가진다. 

 

변수 선택을 위한 Heuristics 세가지 방법을 알아보자. (추가적으로 몇 개의 방식도 함께!)

• Forward search
• Backward search
• Stepwise search

 

3) 변수선택 : Forward Search, 전진 탐색 기법

변수를 하나씩 추가해가며, 모델의 성능을 높이는 변수를 선택하는 greedy한 방법이다.

변수가 하나일 때, 전부 돌려보고 최선의 선택인 x3를 가져간다. 다음은 x3를 픽스한뒤 또 전부 돌려보며 변수가 두 개일 때 최선의 선택을 찾아간다. 이렇게 계속 반복하여 최선의 변수들을 찾아낸다.

 

 

4) 변수선택 : Backward Elimination, 후진 제거 기법

위와 반대로 변수를 하나씩 제거해나가며 모델 성능에 영향을 안 주는 변수를 제거하는 방법이다. 위와 방식도 똑같이 반복적으로 진행한다.

 

5) 변수선택 : Stepwise Search

하지만 위 두 가지 방법의 단점은 너무 greedy하다는 것이다! greedy는 지역적인 최적의 상황이며, 전체적인 최적의 상황이 아닐 수 있다. 따라서 이와 같은 문제를 개선한 것이 Stepwise Search이다.

 

Stepwise는 단계적으로 forward와 backward를 같이 사용한다. 초반에는 forward로 변수를 채워주고, 이후부터는 두 개를 번갈이 사용하며, 추가하고 빼고를 반복한다. 

 

• Any evaluation criteria can be used, 변수들의 성능을 측정하는 평가 지표는 어떤 것이든 가능

 

아래 지표는 통계에서 주로 사용하는 평가 지표들이다.

• Akaike Information Criteria (AIC)
  SSE + the number of feature selected

  

• Bayesian Information Criteria (BIC)
  SSE + the number of feature selected, std. value from the model trained with all features
  

  

6) 변수 선택 : L1 Parameter Regularization

추가적으로 Lasso Regression으로도 변수선택을 한 효과를 줄 수 있다.

(하지만 교수님은 All in one인 Lasso 방식을 변수 선택으로 사용하는 것을 선호하지 않으신다)

 

• Weight의 절대값을 줄이려고 하며,
• Weight가 0으로 갈 때가 최선의 선택
• Weight=0 인 변수들은 알아서 영향력을 잃어 제거됨

 

7) 변수 선택 : Meta-Heuristic

• Genetic Algorithm (GA)-based search, 유전자 알고리즘이라고 불린다
  • Exhaustive search: computational cost (but global optimum)
  • Local search: search space is very limited -> local optimum (but efficient)
• Main motivation of GA
  • Better efficiency than the exhaustive search
  • Better solution than the local search

즉, 이론적으로 local search보다 오래 걸리지만, global optimum에 도달할 수 있는 방식이다

 

• FYI : meta-heuristic
  • Heuristic approaches that can be generally used, Heuristic 방식 중 일반적으로 사용되는 방식
  • GA, simulated annealing, particle swarm optimization, etc.

 

8) Genetic Algorithm (GA)

• Evolutionary computing, 진화 연산의 한 분야
• Meta-heuristic approach의 방법
• Efficient search for the all search space, 전체 영역에서 효율적으로 찾는다
• (Theoretically) can obtain a global optimum, 전체적인 최적해를 구할 수 있다
• (Practically) can obtain a near-global optimum 

 

GA의 기본적인 아이디어를 보자. 일단 생태계에서 종은 세대가 지날 수록 아래와 같은 과정으로 진화를 한다.

 

Evolution Process

1. Selection : select two superior parents, 우수한 유전자가 선택되고
2. Cross-over : select two superior parents, 섞어서 자손을 만든다
3. Mutaion : mutate each gene in a rare probability, 동시에 돌연변이도 일어난다

이러한 정리를 진화 프로세스라고 하며, 이를 변수 선택에 적용하려고 한다.

아래는 전체적인 순서이며, 4번부터 7번이 계속 반복된다.

 

1. Chromosome encoding
2. Population setting
3. Fitness evaluation
4. Selection
5. Cross-over
6. Mutation
7. Create next generation

 

이제 순서대로 하나하나 알아보도록 하자.

1. Chromosome encoding

• The number of genes in a chromosome: the number of features, 변수의 집합을 나타내는 크로모좀
• Binary encoding: each gene represents each feature is selected or not, 값은 변수가 선택되었는지를 의미

 

 

 

 

2. Population setting

• A population consists of p chromosomes, p개의 크로마좀으로 구성
• Each chromosome is set randomly, 처음에는 랜덤하게 20% 정도의 1을 할당하는 크로마좀을 구성

p=500, 은 500개의 각각 다른 크로마좀들을 사용한다.

 

3. Fitness evaluation

• Fitness는 적합도, 얼마나 우수한 Model인가? 즉 우수한 유전자 = 변수인가?
• Fitness can be differ to problems, 적합도는 문제마다 다를 수 있다
• Fitness function in feature selection method 
  • AIC, BIC, Adjusted R2, etc…
  • Validation error
• Train each model with each feature set, then calculate fitness function for each model
  각각의 모델에 대해서 적합도를 평가한다

 

 

4. Selection

평가를 통해 우수성을 검증한 뒤, 이제 선택을 한다

 

• With fitness value of each chromosome
• Deterministic selection
  • Selection of top n% parents with the fitness values
    상위 n%의 부모들을 선택
    그러나 local optimal이면 어떡해!
• Probabilistic selection
  • Fitness value is an weight to be selected
    그래서 선택에 확률값을 주어 결정하는 방식을 주로 사용한다
    아래 동그라미 판에 다트를 두번 던져서 걸리면 교배! 하는 방식
  

 

5. Cross-over

• Make two children with two parents, (식의 수월함을 위해)

간단히 자식을 만드는 방법에는 부모의 유전자 중 랜덤하게 골라 서로 교환해주는 방식이 있다.

• We can choice different cross-over point, 교환하는 포인트는 자유롭게 결정해도 된다

아래 예시는 특정 범위를 정하고 랜덤값을 모든 배열 값에 대해 구해서, 특정 값 이상이 되면 배열 값을 변환해 준다.

 

6. Mutation

위와 같은 방식은 새로운 영역으로 이동할 수는 없다. 그래서 사용하는 것이 mutation이다.

• With a very small probability (<= 3%) 만약 낮은 랜덤값을 가지면 값을 전환해준다
• Jump to another search space, 이동하기 위함이며
• Escape from local optimal, 동시에 지역의 최적을 피하기 위함이다

 

7. Create next generation

• Make p new chromosomes with p parent chromosomes
• Solution can be evolved through the generation, 진화가 진행될 수록 성능이 좋은 모델이 생성된다

 

 

아래와 같이 성능이 우수해짐을 알 수 있다.

참고로 일반적으로 100개 이상의 p가 300~400번의 세대를 거쳐야 좋은 성능을 가진다.

또한 Crosssover와 Mutaion을 진행할때 확실하게 변화가 있어야, generation을 거듭할수록 여러 영역을 둘러보며 좋은 solution을 찾을 수 있다.

 

Set of hyper-parameters

• # of chromosomes in a population, 100개 이상
• # of generations, 300~500개 이상 (충분히!)
• Selection method, 확률적인 방법 쓰세요!
• Cross-over rate, 50% 정도 섞어요!
• Mutation rate, 3%
• Termination criteria, 몇 회 이상 또는 평균 fitness의 변화가 없을 때 등 

 

GA Tips

• Don’t worry about # of population (computing power)
• Probabilistic approach is preferred
• You can try more than two fitness values at one time, 두가지 적합도 계산도 OK 
• The best chromosome can always remain (like invincible), 최고의 크로마좀은 언제나 남아있도록 다음세대로 복붙해 유지하는건 교수님 팁(전교 1등은 우리학교에^^)

 

Pros/Cons

• Meta-heuristic : So we don’t know how close the solution is to the optimal solution
  실제 전체적인 최적해와 얼마나 유사한지 알 수 없다, 그냥 이론상으로!
• Solution can be upgraded through a number of evolution
  해결법은 진화를 통해 개선이 된다
• Theoretically, the solution is global optimum
• Be patient, 인내심 필수..^^
• Define the fitness function, 문제에 따라 달라질 수 있으므로 매우 중요
• If you have a lot of time, but you don’t want to spend your time to think
  시간이 많다면 한 번 돌려보는 거 추천
• One of optimization methods, but optimization gurus don’t like GA
  솔직히 최적화 + 수학 하시는 분들은 별로 안좋아한다..

 

---

3. Feature Extraction

1. Feature Extraction Method

이제 변수를 줄이는 두번째 방법인 feature extraction을 알아보자

origin 변수를 기반으로 새로운 변수를 만들어내는 방법으로, 대표적으로 PCA가 있다.

 

1) Principal Component Analysis (PCA, 주성분분석)

PCA는 다양한 분야에서 많이 사용되는 분석방법이다.

 

• Principal : 주요한
• Component : 요소
• Goal
  • Identify bases (axes) that contains the variance of the original data as much as possible
    original data의 분산을 가능하면 잘 유지할 수있는 새로운 축을 찾는다(분산 최대화가 목표)
  • Variable means a lot when the variance is large
    즉, 변수는 바뀌지만 변수가 가지고 있는 정보량을 유지할 수 있어야 한다

 

아래 첫번째 그래프를 보면, x1과 x2를 통해 data들의 분산이 가장 큰 직선을 만들었다. 그리고 해당 직선을 기준으로 파란선이 decision boundary가 될 수 있다.

 

이때 x1과 x2으로 만든 그래프가 아닌 변량을 최대한 똑같이 유지하는 검은 직선 PC1을 기준으로 하는 data분포에서, 우리는 새로운 2차원 DB가 아닌 간단하게 대략 0.7이상은 빨강 data가, 그 이하는 파랑 data가 있음을 분류할 수 있다!

 

이것이 PCA이다!

 

그럼 검은 직선, 축은 어떻게 구하는가?

 

Dimensionality reduction

• Mapping to a new variable (PC) while keeping the original variance
  원래의 변수들을 통해서 새로운 변수를 만드는데, 새로운 변수의 값을 통해서 원래의 변수값을 알 수 없다
  즉 설명력이 떨어지는 모델이 된다

 

 

자 이제 Mapping을 하기 전에 선형대수에서 배웠던 내용을 복습해보자.

우리는 벡터 b를 a에 매핑하려고 한다. 식은 아래와 같고, 결국 p는 벡터 a와 b를 내적한 것과 같다는 결과를 얻을 수 있다.

다음은 Covariance와 Eigenvector and eigenvalue를 복습해보자.

두가지를 전제로 하여, 아래 세가지를 기억하고 넘어가자

• X의 평균이 0이면 Cov는 (X XT)/n
• Ax = λx

• 

 

Mapping X to w

• Projected points = wTX
  우리는 wTX를 통해 w를 알아내려고 한다
• Covariance of projected points(when X has zero mean value )
  
  where S is covariance matrix of X
  공분산을 사용하기 위해 wTX와 그의 전치행렬을 곱한다
  이때 우리는 X의 공분산 XXT(S라 하자)를 알고 있으므로, 해당 식에 사용한다

 

지금까지 우리가 얻을 정보를 아래 두가지로 정리할 수 있다. 그리고 공분산 최대화를 위한 w를 알아보는 것을 목표로 한다는 것을 잊지말자.

• Max(wT X XT w = wT S w) 
• wT w = 1

위의 두 식에서 변수는 w뿐이므로 이를 사용하여 계산한다.

또한 두가지 가정도 존재하는데

• w는 unit vector
• X는 zero mean으로 정규화되어 있음

 

(L은 라그랑지안) 이를 통해 위를 만족시키는 w를 찾을 수 있는데, 이때 eigen vector and eigen value 문제임을 알 수 있다! 

하지만 S의 크기에 따라 그만큼의 eigen vector and eigen value의 수가 나온다. 따라서 pc도 그에 맞는 개수로 나오게 된다! 그리고 이 모든 pc는 전부 독립이며 직각이다!

 

아래에의 예시에서도 2차원 임으로 두 가지의 pc가 나오며, 이 두가지가 직각임을 알 수 있다.

예시를 보자.

 

 

 

 

4번의 분산설명력을 통해 5번 분석을 진행한다. 더 높은 비율을 가지는 순서대로 전체 변화량의 해당 eigen vector의 영향력을 알 수 있다. 그리고 이를 기준으로 data들을 올려주면 된다!

 

근데 2개의 변수로 2개의 pc를 만들면, 결국 2개의 변수가 되는 것이 아닌가..?

아래 예시를 한번 보자! 13개의 origin 변수를 통해서 13개의 pc를 만들었지만, 이때 중요한 것은 누적분산비이다.

누적 분산비가 93%일때의 사용한 pc 개수는 7개로, origin보다 적은 수를 가진다 (pc를 loading vector라고도 부른다)

따라서 기준을 정하여 차원 축소의 범위를 결정한다.

 

 

차원이 작아질 수록 설명력도 줄어들지만, loading vector(변수들의 비율)를 통해 간접적으로 설명이 가능하다.

 

Number of PC Selected

• d-dimensional original space can make d numbers of PC
• I may select to contain 80~90% of original variance
  누적분산비의 80-90%까지 pc들을 선택할 수 있다

pc 4개 정도를 사용해도 괜찮은 결과가 나온다

 

Variations

• Singular Value Decomposition (SVD),
  PCA는 square matrix를 다루지만 SVD는 rectangular matrix로 확장
• Kernel PCA, nonliner한 mapping도 가능
• Autoencoder(with linear activation function)
  NN중에서도 위의 기능을 통해 PCA와 같은 기능을 수행할 수 있다