Genetic Algorithm

-

01_3 : Dimensionality Reduction : Genetic Algorithm

Meta-Heuristic Approach

  • 매우 복잡한 문제들을 효율적 으로 Trials and Error 방법을 통해 해결한다.
  • 자연에서 발견되는 방법들을 응용하는 경우가 많다. (ex. Neural Network, Ant Colony Algorithm, Particle Swarm Optimization)
"Genetic Algorithm is an Evolutionary Algorithm that mimics the Reprodustion of Creatures"

Genetic Algorithm은 유전과 진화를 모방하여 Reproduction과정을 반복하고 이를 통해 Superior Solution을 찾습니다.

  • Selection : Quality를 향상시키는 더 좋은 해(Superior Solution)를 선택합니다.
  • Crossover : 현재의 해들을 다양하게 조합하여 더 나은 대안을 찾습니다.
  • Mutation : Local Optima에 빠지는 것을 방지하기 위해서 돌연변이를 발생시킵니다.


Genetic Algorithm의 변수 선택과정 (Feature Selection)

  1. Initiation : 염색체 초기화 및 파라미터 설정
  2. Fitness : 각 염색체별로 대응하는 변수를 사용하여 모델을 학습시킨다.
  3. Selection : 각각의 학습한 모델을 통해 각 염색체의 적합도 평가를 한다.
  4. Mating(Crossover) : 적합도 평가를 통해 선택된 염색체들을 통해 새로운 세대를 생성한다.
  5. Mutation : 새로운 세대들에 대하여 돌연변이를 발생시킨다. (2번으로 돌아가 과정을 반복한다)
  6. Final Generation : 5까지의 수행결과가 수렴한다면 최종적으로 해당 염색체를 선택한다.

유전 알고리즘은 변수 선택에만 사용되는 것이 아니라, 다양한 최적화 문제에 사용됩니다. 이 글에서는 변수 선택에 사용되는 유전 알고리즘을 기반으로 설명하겠습니다.


Step 1: Initialization

  • 인코딩 방법은 다른 종류의 task마다 다른 방법을 사용할 수 있습니다.
  • Variable Selection에는 일반적으로 Binary Encoding을 사용합니다. 그 중에서 Chromosome을 이용해 보겠습니다.

Encoding Chromosomes

Chromosome 구조는 아래와 같습니다. 이때 각 x는 유전자(Gene)이고, 아래 0, 1 비트는 0이면 해당 변수를 모델링에 사용하지 않음을, 1이면 해당 변수를 모델링에 사용함을 나타냅니다.

$x_1$$x_2$$x_3$$x_4$$x_5$$x_6$$x_7$$x_8$ ... $x_d$
10110100 ... 1

Parameter Initialization

  • The Number of chromosome (Population) : N개로 지정한다면 1 세대에서 N개의 변수 부분집합을 평가함
  • Fitness Function : 각각의 Chromosome의 Quality를 평가하는 함수
  • Crossover Mechanism : 교배 방법
  • The rate of mutation : 돌연변이율
  • Stopping criteria : 종료조건 (ex. minimum fitness improvement, maximum iterations)
이 과정을 다중선형회귀분석(Multiple Linear Regression)으로 표현하면, 아래의 chromosome에 대하여 다음 식을 새울 수 있다.

$x_1$$x_2$$x_3$$x_4$$x_5$
10101
$$ MLR : \hat{y}=\hat{\beta_0}+\hat{\beta_1}x_1+\hat{\beta_3}x_3+\hat{\beta_5}x_5 $$
($\beta_0$은 bias이다.)
그리고 해당 모델에 대하여 adjusted-R Squared value가 0.78이 나왔다면, 이는 chromosome의 fitness value가 0.78이라는 뜻이다.

Example : Population Initialization

  • Random number generation for each gene
  • Convert the random numbers to binary values (cut-off 설정을 통해 각 value가 cut-off 이상이면 1로, 미만이면 0으로 변환한다.)
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Chromosome 1 0.23 0.89 0.92 0.11 0.36 0.17 0.95 0.32
Chromosome 2 0.56 0.82 0.19 0.64 0.56 0.33 0.13 0.57
Chromosome 3 0.70 0.65 0.33 0.29 0.43 0.66 0.86 0.22
Chromosome 4 0.49 0.32 0.36 0.59 0.19 0.36 0.35 0.36
Chromosome 5 0.98 0.44 0.29 0.94 0.77 0.81 0.47 0.93
Chromosome 6 0.31 0.70 0.88 0.16 0.58 0.12 0.74 0.12
$$\Downarrow$$Convert (cut-off = 0.5)$$\Downarrow$$
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Chromosome 1 0 1 0 0 0 0 1 0
Chromosome 2 1 1 0 1 1 0 0 1
Chromosome 3 1 1 0 0 0 1 1 0
Chromosome 4 0 1 0 1 0 0 0 0
Chromosome 5 1 0 0 1 1 1 0 1
Chromosome 6 0 1 1 0 1 0 1 0

Example : Train the model (Step 2 : Fitness)

이렇게 생성한 Population을 기반으로 각 Chromosome에 대하여 Multivariate Linear Regression model을 생성한다.
예를 들어 Chromosome 2에 대하여 아래의 MLR model이 만들어진다.
$$ MLR :  \hat{y}=\hat{\beta_0}+\hat{\beta_1}x_1+\hat{\beta_2}x_2+\hat{\beta_4}x_4+\hat{\beta_5}x_5+\hat{\beta_8}x_8 $$


Step 3 : Fitness Evaluation

  • Fitness Function : 어떤 Chromosome이 더 좋은지 판별하는 기준
일반적으로 더 높은 Fitness value를 가지면, 더 좋은 Chromosome이다. (때문에 회귀분석에서 RMSE(Root Mean Squared Error)가 더 작은 model이 더 좋다고 판별하고 싶다면, Fitness Function으로 (1-RMSE)를 사용하는 등의 변형이 필요하다.)

Fitness Function은 아래 두가지의 Common Criteria를 내장해야 한다.
  • 만약 두 Chromosome이 동일한 Fitness value를 가진다면, 둘 중 더 적은 변수(variable)를 사용한 것이 더 선호된다.
  • 같은 수의 변수(variable)을 사용한다면, 더 높은 예측 성능을 보이는 것이 더 선호된다.
선형회귀분석의 경우 위의 조건을 만족하는 fitness function으로 Adjusted $R^2$, Akaike information criterion(AIC), Bayesian Information Criterion(BIC)가 그 예시이다.

Example : Fitness Function

Adjusted $R^2$를 Fitness Function으로 사용하여, 각 Adjusted $R^2$ Value를 기반으로 Rank를 매기고, Weight를 구한다. $$ Weight = \frac{Adj. R^2}{\sum{Adj. R^2}} $$
Adj $R^2$ Rank Weight
Chromosome 1 0.73 2 0.209
Chromosome 2 0.79 1 0.226
Chromosome 3 0.35 6 0.100
Chromosome 4 0.61 3 0.175
Chromosome 5 0.47 5 0.134
Chromosome 6 0.54 4 0.155


Step 4 : Selection

다음 새대의 population을 생성하기 위해 현재 population 중 가장 우월한(Superior) Chromosome을 선택한다.
  • Deterministic selection
    • 상위 N%의 Chromosome을 선택한다.
    • 하위 (100-N)%의 chromosome은 선택되지 않는다.
  • Probabilistic Selection
    • 각 Chromosome의 Fitness value를 Selection weight로 사용한다.
    • 모든 Chromosome은 각각의 확률로 선택된다. (Fitness value가 높을수록 선택될 확률이 높다)

Example : Selection

  • Deterministic selection : 예를들어 상위 50%를 선택한다고 한다면, 1~3위를 한  Chromosome 2, Chromosome 1, Chromosome 4 가 선택될 것이다.
  • Probabilistic Selection : 각 Fitness value에 따라 Cumulative weight를 설정한다.
parent를 선택하는 과정은 0~1사이 2개의 난수를 생성하여 해당 난수를 포함하는 Chromosome을 선택한다. 
예를들어, 난수 생성과정에서 0.825, 0.169 두 난수가 만들어졌다면, 0.825에 대해서는 Chromosome 5가 선택되고, 0.169에 대해서는 Chromosome 1이 선택된다.


Step 5 : Crossover & Mutation

  • Crossover (Reproduction)
    • 2개의 parent chromosome으로부터 2개의 child chromosome이 생성된다.
    • Crossover point는 1~n(total number of gents)사이의 값을 가질 수 있다.
예를들어 2개의 Crossover point를 지정한 경우 Crossover의 결과이다.
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Chromosome 2 1 1 0 1 1 0 0 1
Chromosome 4 0 1 0 1 0 0 0 0
$$\Downarrow$$Crossover$$\Downarrow$$
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Child1 0 1 0 1 1 0 0 0
Child2 1 1 0 1 0 0 0 1

극단적으로 모든 Gene에 대하여 확률적으로 Crossover이 일어나게 할수 있다.
아래와 같이 n개의 Crossover point를 지정한다면, 각 Gene에 대하여 Random number를 생성하고 Random number이 역치(이 예시에서는 0.5)를 넘는 경우에만 crossover이 되도록 한다.

$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Chromosome 2 1 1 0 1 1 0 0 1
Chromosome 4 0 1 0 1 0 0 0 0
Random number 0.93 0.12 0.45 0.48 0.86 0.62 0.78 0.21
$$\Downarrow$$Crossover$$\Downarrow$$
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Child1 0 1 0 1 0 0 0 1
Child2 1 1 0 1 1 0 0 0

생성 가능한 다음 세대의 가능성 관점에서 Deterministic보다 Probabilistic이 더 자유도가 높고, Crossover point가 클수록 자유도가 높다.

  • Mutation
    • 돌연변이를 통해 Solution이 Local optima에서 빠져나올 기회가 생긴다. (Global optima에 도달하는 것이 가장 좋은 Solution)
    • Mutation rate를 너무 크게 지정하면, Converge를 하는데 너무 오래 걸릴 수 있다. (적절한 값으로 지정해야 하며, 일반적으로 0.01을 사용한다.)

$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Child1 0 1 0 1 0 0 0 1
Random number 0.54 0.71 0.43 0.95 0.91 0.44 0.82 0.11
Child2 1 1 0 1 1 0 0 0
Random number 0.35 0.68 0.28 0.19 0.07 0.93 0.01 0.48
$$\Downarrow$$Mutation$$\Downarrow$$
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$
Child1 0 1 0 1 0 0 0 1
Child2 1 1 0 1 1 0 1 0


Step5 : Find the best solution

일반적으로 Genetic Algorithm의 초반 stage에서는 상당한 성능 향상이 나타난다. 하지만 세대가 거듭될수록 점차 성능 향상의 폭이 줄어든다.

성능 향상의 정도가 역치 이하이거나, 반복 횟수의 제한에 도달하면(criteria are satisfied) 가장 높은 Fitness value인  Chromosome을 선택한다.

+ 추가적인 Skill로, 이전 세대에서 Fitness Value가 가장 높은 두 Chromosome을 다음세대에 포함시키는 테크닉이 있다. 이 방법을 통해 수렴 속도를 개선하고, 안정성을 높일 수 있다.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 참고하여 작성되었습니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

One-Class SVM & SVDD

-
이미지
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp...
자세한 내용 보기

Support Vector Regression (SVR)

-
이미지
02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...
자세한 내용 보기

Self-Training & Co-Training

-
이미지
 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating ...
자세한 내용 보기