'2017/04'에 해당되는 글 1건

  1. 2017.04.24 진화 연산의 한계

진화 연산은 여러면에서 매력적입니다. 공간에 대한 분포를 잘 모르고, 문제정의만 하면 왠만큼 해를 구할 수 있다는 것이야 말로 엄청난 매력이라 할 수 있죠. 복잡한 수학이 들어가 있지도 않고, 알고리즘만 이해할 수 있으면 누구나 쉽게 구현하고 접근할 수 있습니다. 이런 장점으로 많은 사랑을 받아왔죠.


그러나 이 부분이 진화 연산의 장점이면서 동시에 한계입니다. Evolutionary Strategies 나 기타 Covariance Matrix Adaptation 기법 등이 나왔지만, 여긴 수학의 영역에 약간의 진화연산의 Mutation 의 기법이 들어갔다고 보는게 맞을 것 같습니다. 또는 Mutation 이라는 것이 확률적이라 표현하는 확률의 기법이 들어갔다고도 볼 수 있겠네요. 거의 Random 에 가까운 속성으로 인하여, 해를 찾아도 왜 찾았을 까에 대해서 물음표가 생기고, 다시 한번 수행하더라도 꼭 그렇게 찾을 수 있다는 보장을 하기도 어렵습니다.


흡사, 문제 풀이를 로또와 같이 한다고 느끼는 사람도 있을 것 입니다. 아직은 주어진 해 공간에 대해 모두 시험해볼 수 없으니 이것을 대체하여 로또의 확률을 느끼는 것과 같이 대량의 시험을 해보는 그런 상황으로 비추어지기도 할 것이고, 언젠가 양자컴퓨터나 기타 더 강력한 컴퓨팅 환경이 주어졌을 때, 모든 경우의 수에 대해 시뮬레이션을 해보고 그 결과를 얻어내는 것과 진화 연산의 차이가 없어지는 날이 오겠죠.


이런 한계는 Genetic Programming 에서 더 심하게 나타납니다. 우리는 주어진 수식에 대해 파라미터를 계산하거나 신경망이나 기타 접근 방식을 통해 수식 자체를 근사화하여 모사하는 행위를 하지만, 이것은 값을 따라가도록 하는 어떤 방향성을 Loss-function 으로 정의하여 그 근거를 가지고 있습니다. 물론, Back-propagation 이 편미분이 연속적으로 연결되어 있는 chain-rule 이라는 것도 확인할 수 있습니다.


그러나 수식 자체를 Tree 형태로 표현한 것에 대해서 수식 자체가 갖는 공간적 표현을 수학적으로 모사하지 못합니다. (지금은 하고 있는데, 제가 모르고 있는 것일 수도... ) Tree 의 특정 위치를 교환하거나, 전혀 다른 Sub-tree 로 교체하여 수식을 풀어나간다고 하지만, 그 자체에 대해 어떤 수학적 근거를 갖는지에 대해서는 설명하기가 어렵습니다. 특히나 Fitness function 의 정의가 어떤 방향으로 유도한다고는 하지만, 이것이 항상 그 방향으로 유도되어 나아가는 것도 아니라는 것을 확인할 수 있습니다.


예전에 Tree 의 Distance Metric 을 정의한 여러가지 사례가 있었는데, 이 Distance Metric 은 비교적 Tree 의 차이에 대해 정의할 수 있었고, 이 Metric 을 통해서 특정 Tree 형태로 수렴할 수 있도록 Guidance 로 사용할 수 있었습니다. 문제는 Tree 의 구조적 형태가 좋은 해와 그렇지 않은 해를 구분하기에는 적절치 않았다는 것에 있었죠. 즉, 우리가 어떤 형태의 Tree 로 해를 유도한다고 해도, 사실 그 구조를 가진 해가 좋은 해인지를 판별할 방법이 없었습니다.


Genetic Programming 이나 Grammatical Evolution 은 진화 연산 중에서 Tree 구조를 사용하여 새로운 구조를 만들어나 갈 수 있다는 장점이 있지만, 반면 연속적인 시간 변화에 대한 값으로 주어진 결과물을 모사하기 위한 어떤 구조를 만들어낸다는 측면에서 2차원으로 주어진 데이터를 전혀 다른 공간의 형태로 Mapping 하는 일종의 Black-box Optimization 으로 생각하기에 아직은 수학적으로 접근할 수 있는 부분에 한계가 있는 것 같습니다.


언젠가는 연속적인 시계열 데이터나 기타 일련의 알고리즘을 Tree 나 다른 형태로 Mapping 하는 수학적 방법에 대한 제안이 있을지 모르겠습니다만, 이러한 부분이 극복되지 않는다면 결국 진화연산은 항상 랜덤에 의존하는 그런 최적화 방식으로 치부되지 않을까 싶습니다. Schema 이론이나 기타 몇가지 이론이 있지만, 그렇다 해도 말이죠.

Posted by SHHyun