[Dimensionality Reduction] Supervised Methods 2: Genetic algorithm

본 포스트는 고려대학교 산업경영공학부 강필성 교수님의 Business Analytics 강의를 정리한 내용입니다.

 

Meta-heuristic

유전 알고리즘은 이전 FS, BE, SS 알고리즘보다는 시간이 조금 더 소요되지만, 성능은 더 높다.

이 알고리즘은 meta-heuristic 기반이고, 이는 굉장히 복잡한 문제들에 대해 trial과 error를 해결해가면서 효율적으로 solution을 찾는다.

이 접근법을 기반으로 만들어진 알고리즘은 neural network, ant colony algorithm, particle swarm optimization 등이 있다. 이러한 알고리즘들은 자연에서 motive가 되어 연구되었다.

Genetic Algorithm

유전 알고리즘에서 가장 중요한 3가지 step은 다음과 같다.

1. Selection : solution에 대한 퀄리티를 높일 수 있는 후보군을 찾는데 집중한다.
2. Crossover: 퀄리티가 우수한 객체를 조합하면서 더 좋은 대안이 있는지 탐색하는 과정
3. Mutation: 수렴 과정에서 local optima를 빠져나가기 위한 대안

유전 알고리즘을 사용한 feature selection의 전체 단계는 크게 6 step으로 나누어진다.

1. 염색체 초기화 및 파라미터 설정 (Initialization)
2. 각 염색체 선택 및 변수별 모델 학습
3. 각 염색체 적합도 평가 (Fitness evaluation)
4. 우수 염색체 선택 (Selection)
5. 다음 세대 염색체 생성 (Crossover & Mutation)
6. 최종 변수 집합 선택

여기서 5 → 2로 다시 돌아가게 되는데 이를 feed back loop라고 부른다. 해당 loop를 세대라고 부른다.

세대가 지남에 따라 퀄리티를 높이는 것을 목표로 하고, 더 이상의 성능 향상이 없을 때 6단계에서 최종적인 변수를 선택한다.

 

우선 유전 알고리즘은 selection만이 아닌 다른 최적화 문제에서도 사용된다. 각 문제에 따라 encoding scheme이 달라진다. variable selection에서는 binary encoding을 사용한다.

여기서 알아야 되는 용어가 있다. Chromosome은 위 그림과 같은 테이블이고, 각 요소는 gene이라고 부른다. 0이면 사용하지 않고, 1이면 사용한다는 것을 의미한다. 1에 대응하는 위치에 대응하는 변수를 실제 모델링에 사용한다는 의미이다.

유전 알고리즘에서는 많은 hyper parameter가 존재하는데, Initialization 단계에서는 이를 초기화한다.

hyper parameter의 리스트는 다음과 같다.

1. Chromosome 개수 : 만약 100이라면 이는 1개의 세대에서 100개의 변수 subset을 평가하겠다는 의미
2. Fitness function : Chromosome의 퀄리티를 평가하는 함수
3. Crossover mechanism : 뒤에서 다룰 예정이다.
4. Mutation 비율 : 뒤에서 다룰 예정이다.
5. 종료 조건 : Chromosome의 퀄리티가 일정 수준 이하면 종료 또는 최대 iteration에 도달

위 plot의 초록색 point는 best chromosome에 의해 선택된 변수들의 예측 성능이다. 하늘색 point는 해당 세대 chromosome의 평균 성능을 보여 준다.

이제 본격적으로 전체 step에 대해 자세하게 알아보자.

Step 1. Initialization

첫 세대에 대한 초기화는 랜덤으로 gene을 생성한다. 그 후 0.5 기준으로 cut-off 후 이진화한다.

Mutilvariate linear regression model 기준 아래와 같이 모델을 생성한다.

$$ \hat{y} = \hat{\beta}{0} +\hat{\beta}{2}x_{2}+\hat{\beta}{3}x{3}+\hat{\beta}{4}x{4}+\hat{\beta}{6}x{6}+\hat{\beta}{9}x{9}+\hat{\beta}{10}x{10} $$

위 모델은 chromosome 1의 예시 모델이다.

해당 모델을 가지고 학습을 진행한다. (step 2)

Step 3. Fitness Evaluation

학습 후 fitness function을 통해 평가를 진행한다. 이 과정을 통해 어떤 chromosome이 좋은지 알 수 있다. Fitness function의 지표는 무조건 높을수록 좋게 만든다. 작을수록 좋은 error의 경우도 1 - error와 같은 식을 통해 변환한다.

만약 동일한 성능을 가지고 있으면 변수의 개수가 적은 것이 좋은 것이고, 같은 수의 변수를 갖고 있다면 예측 성능이 더 좋은 것이 좋은 것으로 간주한다.

보통 Adjusted $R^{2}$, AIC, BIC와 같은 평가 지표를 사용한다.

8개의 chromosome에 대해 fitness function을 돌린 결과이고, 지표에 따라 rank을 매긴다. weight는 각 지표의 결과를 지표의 총합으로 나눈 것이다.

weight는 뒤에서 다룰 crossover에 영향을 준다.

Step 4. Selection

selection은 다음 세대를 생성하기 위해 우수한 chromosome을 선택하는 과정이다. 이를 통해 세대가 지날수록 더 우수한 성능을 가질 수 있다. selection의 방법은 크게 2가지로 나뉜다.

1. Deterministic selection

: Chromosome 중에 상위 n%에 속하는 애들만 다음 세대에 유전자를 남길 수 있다. rank를 기준으로 남기고, 나머지 chromosome은 폐기한다.

만약 50%라면 1~4 rank에 속하는 chromosome만 선택된다.

1. Probabilistic selection

: 확률을 사용하여 모든 chromosome에게 기회를 준다. rank가 높을수록 선택될 확률이 높다.

각 chromosome의 rank에 따라 높을 수록 확률을 높게 부여하고, 해당 값들을 통해 랜덤 한 수를 뽑는다.

만약 2개의 chromosome을 선택하기 위한 랜덤 숫자가 0.881, 0.499라면 위 그림과 같이 C4, C8이 선택될 것이다.

Step 5. Crossover & Mutation

Crossover

Crossover를 통해 2개의 chromosome을 섞는다. 이때 crossover point가 등장하는데, 이를 통해 부모 chromosome에서 어느 부분을 기준으로 끊을 것인가를 결정한다.

Crossover point가 1개인 경우의 예시이다.

Crossover point가 2개일 경우, 위 그림과 같은 결과가 된다.

극단적으로 Crossover point가 각 gene의 개수일 때는 random number를 통해 crossover를 진행할 수 있다. 위 그림에서는 0.5 이상의 gene들만 crossover를 진행한 예시이다.

Mutation

Mutation은 local optima에서 global optima로 가기 위해 사용한다.

이 또한 자식 chromosome에 대해 random number를 사용하며, mutation rate를 통해 mutation을 진행한다. 위 그림은 mutation rate가 0.01인 경우이다. 기존 child 2의 9번째 gene이 1에서 0으로 변환된 모습을 볼 수 있다.

mutation rate가 너무 높으면 optima 지점에 수렴하는 데 있어 시간이 오래 걸릴 수 있다.

Step 6. Find the Best Solution

위 plot과 같이 초반에는 fitness function의 성능은 급격하게 상승한다. 이후 성능이 수렴하거나 iteration이 종료되면 최종적으로 종료한다.

참고로 유전 알고리즘에서는 항상 top-1, top-2에 해당하는 chromosome을 저장한다. meta-heuristic 특성상 성능이 더 나빠질 수도 있기 때문이다.