유전자 프로그래밍과 트레이딩 첫째

1.
통계적 학습이론과 트레이딩에 이어서 한발짝만 더 들어가보려고 했습니다. 유전자 알고리즘을 하면 정리해 보자, 이런 생각을 들게 했던 논문이 있습니다.

Comparison of Genetic Algorithms for Trading Strategies

제목이 멋진데 유료라서 몇 쪽만 볼 수 있습니다만 흥미진진한 주제입니다. 첫 걸음을 내딛으려고 하는데 바로 막힙니다. ‘통계적 학습이론’,’유전자알고리즘’, ‘유전자 프로그래밍’ 그리고 ‘기계학습’을 어떻게 정의하고 이해하여야 할지 막막합니다. 먼저 통계학과 기계학습은 어떤 관계일까요? 어떤 글은 통계학과 기계학습의 차이점을 데이타를 바라보는 관점이나 태도의 차이로 다룹니다.

통계학은 ‘실패의 가능성’에, 기계학습은 ‘성공의 가능성’에 각기 관심을 두고 이론을 쌓아올리는 것 같다. 물론 얼마나 데이터 분석이 실패할 수 있는지 탐구하는 것과 성공할 수 있는지 탐구하는 것은 넓게 보면 일맥상통하는 이야기이다. 통계학의 경우에는 “이렇게 조심스럽게 분석했는데도 불구하고 통계적으로 유의미하다는 결과를 얻었다면 어느 정도 결론에 자신감을 가져도 좋다”고 그 이론을 해석할 수 있고, 기계학습의 경우에도 “데이터가 부족하면 원하는 성과를 달성할 수 없을 것이다”라고 뒤집어 이론을 해석하는 것이 가능하다. 다만 두 이론의 출발점이 각기 다르기 때문에, 한 쪽에는 통계학의 결과가, 다른 쪽에는 기계학습의 결과가 더 많이 쌓여있는 것이 아닌가 한다. 또한, 비약일지는 모르겠으나 이러한 태도 차이가 최근의 ‘빅데이터’ 열풍에 기계학습자들은 적극적으로 올라타는 한편 통계학자들은 상대적으로 신중한 모습을 보이는 것을 설명하는지도 모른다. 적어도 기계학습자들이 자신의 이론이 응용 분야에서 사용될 수 있는 가능성들에 통계학자들보다 더 많은 관심을 보이는 것 만큼은 부정하기 힘든 사실이다.
통계학의 태도, 기계학습의 태도중에서

같은 주제를 아주 깊게 토론한 글들입니다. 기조는 비슷합니다.

Statistics vs. Machine Learning, fight!
The Two Cultures: statistics vs. machine learning?

Download (PDF, 300KB)

이런 차이를 지닌 통계학과 기계학습이 이론적으로 통합한 것이 통계적 학습이론으로 상상할 수 있지만 정의를 보면 통계학의 관점에서 기계학습이론을 정립한 것이 통계적 학습이론입니다.학습이론의 뿌리가 통계학이면 통계적 학습이론이라고 하는 듯 합니다.

Support Vector Machine모델은 1995 년 Vladimir Naumovich Vapnik 에 의해 개발된 통계적 학습이론으로서 학습데이터와 범주 정보의 학습진단을 대상으로 학습과정에서 얻어진 확률분포를 이용하여 의사결정함수를 추정한후 이 함수에 따라 새로운 데이터를 이원 분류하는 것으로 분류 문제에 있어서 일반화 기능이 높기 때문에 많은 분야에서 응용되고 있습니다.

재무예측을 위한 Support Vector Machine의 최적화

Download (PDF, 727KB)

2.
그러면 유전자 알고리즘과 유전자 프로그래밍은 어떤 의미일까요? 먼저 문병로 교수가 쓴 ‘유전 알고리즘‘에 있는 정의입니다.

유전 알고리즘 (Genetic Algorithm) 이란 자연계에 있어서 생물의 유전 (Genetics) 과 진화 (Evolution) 의 메카니즘을 공학적으로 모델화하는 것에 의해 생물이 갖는 환경에서의 적응능력을 취급하는 것이고, 1975년에 John Holland 가 저서 “Adaptation on Natural and Artificial Systems” 에 처음 소개한 자연도태 의 원리를 기초로 한 최적화 (Optimization) 방법이다. Genetic algorithm 은 탐색 (Search), 최적화 및 기계학습 (Machine Learning) 을 위한 도구로 많이 사용한다

생물은 세포로 구성되고 세포에는 핵이 있으며 그 핵 중에는 염색체 (Chromosome) 라는 것이 있다. 사람의 체세포의 경우에는 46개의 염색체가 있고, 염색체는 주로 DNA로 구성되어 있다. 이 DNA 는 4종류의 염기라고 부르는 화학 물질이 중요한 구성 요소며, DNA가 가지는 정보는 이들 4종류의 염기의 구성 방법에 있다. DNA 는 2중 나선구조로 되어 있으며, 이들이 복잡하게 겹쳐져서 염색체를 구성하고 있다. 유전자 (Gene) 란 유전정보를 담당하는 DNA 를 말한다. 특정의 유전자는 염색체의 특정 위치에 존재한다. 결국 유전정보는 염색체상에서의 위치 (유전자 위치) 와 염기의 배열에 의해 표현되는 것이다

부모로 부터 유전자에 의해 생물로서의 정보 전달이 행해지면 다음세대에는 각 개체 중에서도 보다 우수한 즉, 환경에 적응도가 높은 개체의 유전 정보가 우선적으로 전해진다. 적응도가 낮은 개체는 수명이 짧고, 증식할 수 없게 되기 때문이다. 동시에 적응도가 낮은 종족도 자연 도태되어 간다. 이러한 원리에 기초하여 세대를 거듭해 가면 차례로 환경에 적응도가 높은 개체가 많아진다. 이것이 유전 (Genetics) 과 진화 (Evolution) 의 기본적인 원리이다.

Genetic algorithm 은 풀고자하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성하게 된다. 즉 풀고자 하는 문제에 대한 가능한 해들을 염색체로 표현한 다음 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성한다. 각각의 가능한 해를 하나의 유기체 (Organism) 또는 개체 (Individual) 로 보며 이들의 집합을 개체군 (Population) 이라 한다. 하나의 개체는 보통 한 개 또는 여러 개의 염색체로 구성되며 염색체를 변형하는 연산자들을 유전연산자 (Genetic Operator) 라 한다. 기본적인 연산자는 다음의 3가지가 있다. 선택 (Selection, 집단 중에서 적응도의 분포에 따라서 다음의 단계로 교배를 행하는 개체의 생존 분포를 결정한다. 적응도의 분포에 기초하고 있기 때문에 적응도가 높은 개체일수록 보다 많은 자손을 남기기 쉽게 된다), 교배 (Crossover, 2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시킨다), 돌연변이 (Mutation, 유전자의 어떤 부분의 값을 강제적으로 변화시킨다),

유전 알고리즘을 이용하여 어떤 문제에 대한 해를 찾기 위해서는 먼저 두 가지의 준비 작업이 필요하다. 하나는 풀고자 하는 문제에 대한 가능한 해를 염색체의 형태로 표현 (encoding) 하는 것이다. 또 다른 하나는 각 염색체가 문제를 해결하는데 얼마나 좋은지를 측정하기 위한 평가함수 즉 적합함수 (Fitness Function) 을 결정하는 것이다.
Genetic Algorithm중에서

다음으로 유전자 프로그래밍입니다. ‘유전적 프로그래밍을 사용한 탐색 알고리즘의 발달’은 다음과 같이 정의하고 있습니다.

유전적 프로그래밍은 재생산에 필요한 작동 유전자, 돌연변이, 염색체 교차 등을 사용하여 주어진 문제를 해결하는 프로그램을 발견하는 기술

그러면 유전 알고리즘과 유전자 프로그래밍의 관계에 대한 설명입니다.

Genetic programming is a branch of genetic algorithms. The main difference between genetic programming and genetic algorithms is the representation of the solution. Genetic programming creates computer programs in the lisp or scheme computer languages as the solution. Genetic algorithms create a string of numbers that represent the solution. Genetic programming, uses four steps to solve problems

1) Generate an initial population of random compositions of the functions and terminals of the problem (computer programs).
2) Execute each program in the population and assign it a fitness value according to how well it solves the problem.
3) Create a new population of computer programs.
i) Copy the best existing programs
ii) Create new computer programs by mutation.
iii) Create new computer programs by crossover(sexual reproduction).
4) The best computer program that appeared in any generation, the best-so-far solution, is designated as the result of genetic programming [Koza 1992].

Genetic Algorithms (GA) are search algorithms that mimic the process of natural evolution where each individual is a candidate solution: individuals are generally raw data in whatever encoding format has been defined.

Genetic Programming (GP) is considered a special case of GA, where each individual is a computer program (not just raw data). GP explore the algorithmic search space and evolve computer programs to perform a defined task.

3.
통계적 학습이론, 기계학습, 유전자 알고리즘, 유전자 프로그래밍의 관계가 궁금합니다. 아주 단순화하면 전산학의 한 분야인 인공지능(Artificial Intellgence)가 있습니다.

기계학습이란 인공지능 연구 과제 중 하나로 인간의 자연스러운 학습 능력을 컴퓨터로 구현하는 기술 및 방법을 말한다. 어느 정도 수량을 가진 샘플 데이터 집합을 대상으로 분석해 그 데이터에서 유용한 규칙, 지식표현, 판단 기준을 추출한다. 음성인식과 화상인식, 메일의 스팸필터, 추천 엔진, 일기 예보나 차량정체 예보, 기기 고장 예측, 유전자 분석 등 기계학습의 응용 범위는 광범위하다.

인공지능을 연구하는 이론으로 기계학습이론이 위치하고 있고 생명이 진화모델을 이론화한 기계학습이론이 유전자 알고리즘입니다. 유전자 프로그래밍은 유전자 알고리즘이 진화할 수 있는 환경을 만들어저는 것이 아닐까 합니다.

Genetic Programming (GP) 은 Genetic Algorithm (GA) 의 유전자형을 구조적인 표현이 취급될 수 있도록 확장하여 프로그램의 생성과 학습, 추론, 개념형성 등에 적용하는 것을 목적으로 한다. GP의 기본적인 생각은 스텐포드 대학의 J. Koza로부터 제안되었다. 현재 Koza의 연구실에는 다수의 GP 연구자가 모여 GP는 GA에 있어서 한 분야를 확립하고 있다.

이상을 Genetic Programming이 정리한 내용입니다.

Genetic Algorithms
Genetic Programming is a specialization of genetic algorithms (GA) where individuals are computer programs. This heuristic is routinely used to generate useful solutions to optimization and search problems. A genetic algorithm requires:

Genetic representation
Fitness function

performing the Genetic operations of Selection (genetic algorithm) and Crossover (genetic algorithm)

Evolutionary Algorithms(Genetic algorithm)
Genetic algorithms belong to the larger class of evolutionary algorithms (EA). An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection. EAs are individual components that participate in an artificial evolution (AE).

Evolutionary Computation
An evolutionary algorithm (EA) is subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. Evolutionary computation, introduced by John Henry Holland in the 1970s and more popular since 1990s mimics the population-based sexual evolution through reproduction of generations.

Computational Intelligence
Computational Intelligence (CI) is a set of Nature-inspired computational methodologies and approaches and field of Artificial Intelligence. It primarily includes many-valued logic or Fuzzy logic, Neural Networks, Evolutionary Computation, swarm intelligence and Artificial immune system.

어떤 개발자가 Genetic Algorithms: What’s the difference between Genetic Algorithms and Genetic Programming?에 단 댓글입니다. 단순하지만 이해가 편합니다.

Genetic Algorithms (GA) are trying to optimize a fixed number of variables. Genetic Programming (GP), on the other hand, is trying to optimize an entire structure with dynamic size, as well as any parameters of that structure. So for example you can use GA to find the best slope (a) and constant parameter (b) for a simple regression of the type y = a*x + b. With GP you could try different functions on x (a*x, x^a, a^x, sin(a*x), a*x^2 + b*x + c, etc.) that would better predict y. So GP can be seen as a more flexible version of GAs, or GAs as a special case of GP with a constant number of variables.

Genetic Programming을 개척한 분은 John. Koza교수입니다.John Koza가 쓴 Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems)이 교과서같은 역할을 하나 봅니다. 그런데 좀 어렵다고 하네요. 그래서 전산하는 분들이 찾는 책은 Wolfgang Banzhaf가 쓴 Genetic Programming: An Introduction (The Morgan Kaufmann Series in Artificial Intelligence)입니다.

4.
제가 어떤 주제를 이해하기 위한 가장 손쉬운 방법으로 택한 것은 정의입니다. 그리고 공통점과 차이점을 이해하는 것입니다. 이상의 글쓰기도 같습니다. 그렇지만 통섭의 시대입니다. 전산적 방법이 많은 학문에서 사요하고 있습니다. 통계학과 전산학의 교집합도 점점 넓어지지 않을까 합니다. 그런 의미에서 이상과 같은 개념 구분은 무의미할 수도 있습니다. 그래도 초보자에게 좋은 방법이라고 생각합니다.

이제 유전자 알고리즘이나 유전자 프로그래밍이 어떻게 트레이딩으로 이어질까요? 2006년에 쓰여진 글입니다.

[김형식의 과학적투자]인공지능 투자 세계 1 – 신경망(Neural Network)을 사용한 투자
[김형식의 과학적투자]인공지능 투자 2 – 유전자 프로그래밍(Genetic Programming)을 사용한 투자

국내 학회도 관련한 논문을 내놓고 있습니다.

Support Vector Machines와 유전자 알고리즘을 이용한 지능형 트레이딩 시스템 개발

Download (PDF, 991KB)

투자 의사결정 지원을 위한 유전자 알고리즘 기반의 다중 인공지능 기법 결합 모형

Download (PDF, Unknown)

큰 틀은 달라지지 않았지만 이상의 글을 쓴 때가 지난 3월입니다. 몇 달동안 정신없었고 집중을 못하다가 마음을 먹고 마무리합니다.

레이턴시를 대신하여 자리 잡은 데이타.
요즘 해외 글을 보면 유전자 프로그래밍을 이용한 전략들을 소개하는 글들이 많습니다. 다음 글은 유전자 프로그래밍을 트레이딩에 적용한 것중 Python이나 R을 이용한 사례를 살펴보겠습니다. 프로젝트 PM을 하느라 짬을 내기 쉽지 않지만…