2016년 4월 20일 수요일

[Genetic Algorithm, 유전 알고리즘] 요약& 1. motivation

여기서는 Tom M. Mitchell의 Machine learning 책을 공부해보도록 할거다. 아마 중간중간 사족도 달거같고, 개인적인 질문이 생기면 그걸 해결하는 과정도 같이 적어보도록 하겠다.

가설공간에 대한 배경지식이 필요하다.

유전 알고리즘(이하 GA알고리즘)은 생명체의 진화를 비슷하게(loosely) 구현한 기계학습 방법이다. 보통 생명체는 ATCG로 이뤄진 유전자의 서열이 변하면서 진화가 이루어지는데, GA알고리즘에서는 생명체 대신 가설(hypotheses)의 집합이 다음의 과정을 거쳐 진화한다.
  1. 처음에 무작위로 뽑은 가설의 집합(1세대 가설집합)이 있다. 이 집합의 가설은 유전자 서열을 대신하는 bit 서열을 갖는다.
  2. 무작위 변이, crossover 같은 실제 생명체에서 일어나는 '유전자가 변하는 과정'을 bit 서열에 적용시킨다.
  3. 변한 여러가지 서열을 갖는 가설들을 학습의 목적에 맞는 기준을 갖고 평가한다.
  4. 평가점수가 가장 높은, 그러니까 잘 맞는 가설만 살려서 다음 세대의 가설로 삼는다.
  5. 2번으로 돌아간다.
이 유전 알고리즘은 다양한 학습 과제나 최적화 문제에 잘 작동한다. 예를들어, 로봇 조종하는 규칙을 정하는 문제나 위상기하학(topology) 최적화 문제, 인공신경망의 파라미터를 학습하는데 쓰인다고 한다.

아무래도 저 bit 서열의 의미, 유전자가 변하는 과정, 평가 방법 및 기준이 이 알고리즘의 중요한 맥락일듯 싶다. 생물학도였었던 배경을 살려서 잘 공부해보도록 해야겠다.




1. 유전 알고리즘이 생긴 배경

위에서도 말했듯 유전 알고리즘은 생물학적 진화를 본따서 만든 학습 방법이고, 가설을 찾기 위해 General to specific(넓은 범주부터 좁혀나가는 방식)이나 simple to complex(조건을 점차 늘리는 방식)의 방향성이 있는 탐색을 하기 보다는 반복적으로 변이(변화)를 일으키고 현재 가장 좋은 가설의 부분들을 조합해나가는 방식으로 가설을 찾아낸다.
각 단계에서의 가설들의 집합(모임)을 세대(population)이라 표현하고, 그 세대의 가장 좋은 일부 가설의 자손들이 다음세대를 이루게 된다. 다시 말해 이 과정은 생성-확인(generate and test)을 반복하며 가장 좋은 현재 세대의 가설에 생긴 변이를 가장 먼저 고려하는 일종의 beam search라고 말 할 수 있겠다. 이 유전 알고리즘이 인기를 얻은 이유는 다음과 같다.

  • 생명체에서, 유전은 적응을 위한 강건하고(robust) 성공적인 방법이다.
  • 유전 알고리즘은 서로 연관된 복잡한 가설공간의 부분들을 탐색할 수 있다. 이 부분들이 전체적인 가설 적합도에 끼치는 영향력을 모델링하기 힘든 경우라도 가능하다.
  • 유전 알고리즘을 병렬화하는게 쉽다. 컴퓨터 하드웨어의 성능이 떨어지는 경우도 잘 돌아간다.
이 챕터에서는, 유전 알고리즘의 접근 방법, 적용에 대해 살펴보고 실제로 가설공간을 탐색하는 특성에 대해 검증을 해 볼 것이다. 또 물론, 유전 프로그램이라고 불리는 변이(variant)에 대해 살펴볼 것인데, 프로그램의 거의 대부분이 적합도 결정에 관한다. 유전 알고리즘이나 유전 프로그래밍은 진화론적 컴퓨테이션이라고 불리는 분야에서 가장 인기있는 방법론이다.
챕터의 마지막에서는 생물학에서 말하는 진화연구와 관련된 몇가지의 주제(Baldwin effect, 생명체 개개인의 학습이 유전적 형질로 이어지면 더 잘 살아남는다는 이론)도 다루겠다.

볼드윈 효과같은 이론도 GA에 적용이 된다면, 다른 진화론도 적용시킬 방법이 있을 것 같다. 일단은 자세한 알고리즘이나 실제로의 적용을 잘 모르겠으니까 공부하면서 생각을 해봐야겠음.

가설 공간(space of hypotheses)

가설 공간이란 어떤 문제를 해결하는데 필요한 가능성 있는 가설 후보군의 집합을 의미한다. 예를들어 오늘 운동을 할 것인가를 맞추는 알고리즘을 생각해 볼때,

  • 가설 A : 오늘 비가 안오면 운동을 할 것이다.
  • 가설 B : 오늘 밥을 고기를 먹으면 운동을 할 것이다.
    ......
  • 가설 N : 오늘 X 를 하면 운동을 할 것이다.

와 같은 여러개의 가설을 생각할 수 있고 이러한 가설들의 집합을 가설 공간(space of hypotheses)라고 한다. 여기서 운동을 할것인가를 가장 잘 맞추는 알고리즘은 가설 여러개를 포함할수도 있고 아닐 수도 있고 가설들끼리 연관이 존재할 수도 있다.

결정 트리(decision tree)나 유전 알고리즘(Genetic Algorithm)과 같은 기계학습 방법론들은 어떤 문제를 해결 할 수 있는 가장 최적화된 가설, 혹은 가설의 집합을 찾는것이 목표이다.
근데 보통 해결하고 싶은 대다수의 문제는 보통 말도 안되는 가설, 예를 들어 위의 운동할까말까 문제에서,

  • 가설 X : 오늘 길을 걷다 동전을 줍는데 누가 와서 엉덩이를 차면 운동을 할 것이다.

처럼 말도 안되는 가설들을 상당히 많이 포함한다. 따라서 효과적으로 가설공간을 탐색하는 알고리즘이란 이런 말도 안되는 가설들을 얼마나 잘 제외하는가에 달려있다고 할 수 있다.