Machine Learning을 이용한 주가 패턴 분석(2) - Genetic Algorithm

   0.  회사일 짬짬히 하다보니 아무래도 진도가 빠르진 않다. 하지만 하나 하나 해보며 정리를 하다보면 언젠간 결과가 나올 것이다.
   일단 지난번에 Random Optimization을 가지고 테스트를 해봤다. 최적화라는 것이 어느정도 무작위성을 가지고 있는 것은 맞다. 아무래도 처음 답을 찍어서 이리저리 흔들어보며 더 나은 방향으로 나아가기 때문일 것이다. 하지만 너무 대놓고 무작위로 답을 찾아들어가면 작업을 많이 돌리면 돌릴수록 결과가 나아질 가능성이 높아지긴 하나 그 보장이 없으므로 무엇인가 안정적이면서 멋도 조금 나는 것들을 찾아보기로 했다.
   최적화의 기본적인 알고리즘인 Hill Climb의 경우 이웃 해답이라는 개념이 있어야 하는데, 내가 풀고자 하는 문제에서는 이웃 해답을 정의하기가 애매했다. 그래서 멋도 나고 쓸만한 것으로 유전자 알고리즘을 선택하기로 했다.

   1. 유전자 알고리즘은 일단 무작위로 임의의 갯수로 답을 찾는다. 그리고 이를 모집단으로 사용하여 가장 적은 비용을 갖는 몇 개의 해답을 골라내고(엘리트), 이 해답들을 약간 비틀어(변이를 일으켜) 다시 같은 작업을 반복한다. 이렇게 하면 좋은 답에서 얻어진 유전자를 바탕으로 더 좋은 답을 얻을 수 있다는 것이 유전자 알고리즘의 기본 사상이다.
   내가 풀고자 하는 문제는 찾아야 할 것이, 주가 추세 직선을 구성하는 점의 갯수와 그 점의 위치이다. 여기서 어떤 것을 변이시킬지 찾아야 한다. 여기서 점 자체를 변이시키면 변이에 대한 경우의 수가 너무 많다. 해서 점의 갯수를 변이 시키기로 하고, 그에 따라 현재 물려받은 점 들에 새로운 점을 추가하거나, 기존의 점을 삭제하기로 했다.
$$
 P_i = \{ (x_1, y_1), ... ,(x_n, y_n) | n \} \rightarrow P_{i+1} = \{(x_1, y_1), ... , (x_m, y_m)|m\},  m = n+1
$$
   위의 경우는 $i$에서 $i+1$로 세대가 넘어가면서 점이 하나 추가된 경우이다. 단 기존 세대에서 받아온 점은 그대로 유지하고 새로운 점만 하나 더 추가를 한다. 이 때 추가 또는 삭제 대상 점의 선정은 무작위로 하도록 했다. 이렇게 하면 엘리트 집단 안의 하나의 엘리트는 각자 두 개의 자손(더하기, 빼기)을 갖게 된다.
   앞서의 과정을 임의의 충분한 횟수만큼 돌리거나, 몇 세대동안 더이상 발전이 없을 경우(최선의 답이 바뀌지 않을 경우) 멈추는 방식으로 구현한다.

   2. 이 작업을 하면서 비용 함수를 조금 손을 봤다. 일단 점의 갯수에 패널티를 줄 때, 스케일을 고려하여 점의 갯수에서 전체 데이터 수를 나누어 일종의 비율로 나타내도록 했다. 즉, 다음과 같은 비용 함수를
$$
C = \sum_{i=1}^{n}(\hat{y}_i - y_i)^2 + \omega m
$$
다음과 같이 고쳤다.
$$
C = \sum_{i=1}^{n}(\hat{y}_i - y_i)^2 + m / n
$$
여기서 $n$은 전체 데이터의 갯수이다.
   그리고 여기다 하나 더 추가했다. 무릇 추세선이라고 하면 그럴싸하게 넓직하게 나와야 더 좋아보일 것이다. 그래서 점간 거리($x$의 거리)를 비용으로 추가하기로 했다. 그러면 아무래도 바로 옆 점을 추가하는데 부담을 느끼게 될 것이고 추세를 나타내는 점이 조금 더 넓게 퍼질 것으로 기대할 수 있다. 일단, 점 간거리를 다음과 같이 정의하자.
$$
D = \{x_i - x_{i-1}\}, i=2,...n
$$
   이 값을 비용으로 사용하기 위해서는 점 간거리가 가까울수록 비용 부과를 더 해야하니 위의 벡터의 요소들을 각각 역수를 취하자.
$$
\hat{D}=\{ \frac{1}{x_i - x_{i-1}}\}
$$
   비용은 $\hat{D}$의 각 요소의 제곱의 합으로 나타내면 되므로 $ \hat{D}^T\hat{D}$ 로 표현할 수 있다. 그래서 최종적으로 현재 구현한 비용 함수는 다음과 같다.
$$
C = \sum_{i=1}^{n}(\hat{y}_i - y_i)^2 + m / n + \hat{D}^T\hat{D}
$$
   이런 식으로 찾아낸 주가 패턴 두가지를 아래 그림으로 첨부한다.

   3. 이제 이런 방식으로 구해진 패턴 데이터를 어떻게 머신 러닝에 적용할 데이터로 만들지 고민해봐야 한다. 아마도 텐서플로를 기반으로 작업을 진행할 것 같으니, 앞으론 텐서플로를 정리해보도록 하겠다.

조금 더 복잡한 Chain Rule

0. PDE를 써서 FDM으로 만들 때 복잡한 수식을 변환하거나, 격자 자체의 방향을 틀어버리는 목적으로 변수 치환을 많이 한다. 그 때 연산자 변환을 위해서 chain-rule을 자주 사용하는데, 2차 미분으로 넘어가면서 헷갈리는 경우가 많아 정리를 해두려 한다.

1. 복잡한 chain-rule에 대해 이해를 해보려다가 인터넷을 뒤적거리다 보니, 꽤 괜찮은 방법을 찾았다. 그 것은 바로 일종의 이항트리를 이용하는 방식이다. 다음과 같은 함수가 있다고 가정하자.

$$ \psi = x+y, \eta = x-y $$

여기서 $x$와 $y$를 변수로 갖는 함수를 $f(x, y)$로 하고 $\psi$와 $\eta$를 변수로 갖는 함수를 $g(\psi, \eta)$라고 하자. 여기서 $f(.) = g(.)$이라 하면, 내가 관심있는 것은 $\partial{f} / \partial{x}$를 어떻게 $\psi$와 $\eta$에 대해 변환할 수 있을까이다.
   변환을 시작하기 전에 다음과 같은 다이어그램을 그려보자.

$  g \\
 / \backslash \\
\psi   \eta \\
/ \backslash / \backslash \\
x  y x  y $

 뭔가 좀 후지긴 한데... 어쨌든, $g$는 $\psi, \eta$의 함수이고, 또 각각은 $x, y$의 함수라는 의미이다. 그래서 chain-rule을 이용하여 미분을 할 때 각 트리를 따라 내려가면 수월하게 할 수 있다. 트리의 가지를 하나 내려올 때마다 미분이 추가된다고 보면 된다. 즉, $g$에서 $\psi$로 오면 $g$를 $\psi$로, $\psi$에서 $x$로 오면 $\psi$를 $x$로 미분한다는 의미이다.

2. 1차 미분
   $\partial{f}/\partial{x}$를 변환하기 위해서, 즉 $\partial{g}/\partial{x}$를 찾기 위해서는 위 트리를 따라 내려가며 $x$가 나올 수 있는 경우를 모두 찾는다. 여기서는 $g \rightarrow \psi \rightarrow x$와 $g \rightarrow \eta \rightarrow x$의 두가지가 있다. 즉, $\psi, \eta$ 각각에 대해 미분을 해줘야 한다는 의미이다. 그래서 종합하면 다음과 같다.
$$  \frac{\partial f}{\partial x} = \frac{\partial g}{\partial \psi} \frac{\partial \psi}{\partial x} + \frac{\partial g}{\partial \eta} \frac{\partial \eta}{\partial x}  $$    그리고 앞에 정의한 $\psi, \eta$를 $x$에 대해 미분해서 넣어주면 다음과 같은 결과가 나온다.

$$ \frac{\partial f}{\partial x} = \frac{\partial g}{\partial \psi} + \frac{\partial g}{\partial \eta}  ... (1)$$
   만약 $y$에 대해서 찾는다면 위와 같은 방식으로 트리를 타고 내려오면 쉽게 이해할 수 있다.

3. 2차 미분
   이제 $\partial^2 f/\partial{x}^2$를 변환하고 싶다. 그럼 앞의 그래프에서 $g$를 (1)번 식의 각 항으로 바꾸어 각각 진행한다. 즉, 두 항에 대해 앞과 같은 그래프 태우기를 한다. 그럼 다음과 같은 순서로 진행된다.

$$  \frac{\partial^2 f}{\partial{x}^2} = \frac{\partial}{\partial x} (\frac{\partial g}{\partial \psi} +
 \frac{\partial g}{\partial \eta} ) \\ = (\frac{\partial^2 g}{\partial{\psi}^2} \frac{\partial{\psi}}{\partial x}
 + \frac{\partial^2 g}{\partial{\psi}\partial{\eta}}\frac{\partial \eta}{\partial x})
 +  (\frac{\partial^2 g}{\partial{\eta}^2} \frac{\partial{\eta}}{\partial x}
 + \frac{\partial^2 g}{\partial{\psi}\partial{\eta}}\frac{\partial \psi}{\partial x}) $$
   즉, 트리의 각 가지를 타고 내려오며 해당 미분을 해주면 된다는 의미다. 

4. 합성 미분
   합성 미분도 위의 방식대로 $x$가 필요할 때는 $x$를 찾는 방향으로, $y$가 필요하면 $y$를 찾는 방향으로 움직이면 된다.

Machine Learning을 이용한 주가패턴 분석(1) - Cost Function, Random Optimization

0. 시작
   최근 AI가 화두인지라 귀가 얇은 나도 역시 관심을 갖게 되었다. 그리고 업 자체가 금융업이다보니 시장을 AI를 이용하여 분석한다면 무엇인가 괜찮은 프로젝트가 나올 것 같다는 생각이 들었다. 하여, 주가패턴을 분석하는 프로젝트를 시작하고자 한다. 앞으로 올릴 포스트들은 그 프로젝트를 진행하면서 진행 상황을 기록하기 위한 목적이다.

1. 방법론 선택
   일단 주가 차트를 분석하기 위해서는 일정 기간의 주가 차트를 일정한 패턴으로 만들어내야 한다. 결국 추세를 어떻게 표현할지가 관건이다. 추세를 나타내는 방법은 MA(Moving Average)를 그린다든가 어떤 Regression 기법을 이용하여 그리는 방법을 사용할 수 있을 것이다. 하지만 이 방법들은 추세 표현력은 좋으나 Machine Learning을 사용하기 위한 데이터로 전환할 수 있는 방법이 쉽게 떠오르지 않았다. 그래서 더 단순하고 직관적인 방법을 찾으려 했다.
   나의 멘토이신 C박사님의 아이디어는 주가 차트를 임의의 직선의 조합으로 나타내 보자는 것이었고, 이 방식이라면 패턴 분석용 데이터를 만드는데 더 수월할 것이라는 판단이 들었다. 직선의 경우 기울기, 시작점, 끝점으로 단순히 표현할 수 있기 때문이다. 그래서 최적화 기법을 이용하여 직선 및 점의 갯수를 찾아내고 그 데이터를 이용하여 패턴 분석을 하기로 했다.

2. 프로그래밍 언어
   일단 최적화를 구현하기 위한 언어는 R로 선택하였다. 처음에 python과 R을 모두 고민했으나, 내 손에 편하고 데이터 분석에 강점이 있는 R을 사용하기로 했다.

3. 데이터
   주가 데이터는 팀 내의 데이터베이스 또는 블룸버그 터미널을 이용하여 S&P500 주가를 다운받아서 사용하였다. 단, 주가 자체의 값을 그대로 데이터로 이용할 경우 Cost Function을 구현하는데 있어 어떤 가중치를 정하는데 지수마다 달라질 수 있으므로, 주가를 정규화(normalization)을 한다. 여기서는 나에게 매우 익숙한 로그 수익률을 사용하였다.

$ y_i = \ln(\frac{S_i}{S_0}), i=1, ..., n $

 여기서 $y_i$는 정규화한 수익률이고 $S_i$는 포인트의 주가, $S_0$는 시작 지점의 주가이다. 그리고 x축의 경우 휴일 등의 변수가 있으므로 날짜로 하기보단 1부터 n까지의 정수를 사용하기로 했다.

4. Cost Function(비용 함수)
   최적화를 하기 위해서는 비용 함수가 중요하다. 이는 내가 생각한 답이 어느정도의 오류를 가지고 있는지 표현하기 위한 함수이다. 최적화는 이 오류(비용) 값을 가장 적게 할 수 있는 답을 찾는 것이다. 비용 함수에서 비용은 '직선 추정치($\hat{y}$)과 실제 주가수익률($y$)의 차이'가 하나 있고, 추정을 위해 사용하는 점의 수가 너무 많을 경우 overfitting의 문제가 있으므로 점의 갯수도 비용으로 들어가야 한다.
   주가 추정에 의한 차이는 잘 알려진 Least square로 하고 점의 갯수에 의한 패널티는 간단하게 일정 가중치를 점의 갯수에 곱하여 더하기로 했다.

 $ C = \sum_{i=1}^{n}(\hat{y}_i - y_i)^2 + \omega m $

   여기서 $n$은 전체 점의 갯수이고, $m$은 직선을 구성하기 위한 점의 수이다. 그리고 $\omega$는 패널티를 주기 위한 가중치인데, 앞으로 이 값을 어떻게 조절하느냐가 꽤 중요할 것이다. 이제 이 비용 함수를 이용하여 최적화 기법을 구현해보도록 하자

5. 가장 단순한 Random Search
   Random Search는 말 그대로 무작위로 추정용 점의 갯수와 위치를 찾는 방법이다. 테스트를 할 때 1만번을 돌도록 구현했고, 이 방법은 추후 구현할 최적화 기법과의 비교 용도로 사용할 것이다. 아래 간단한 결과 그래프를 첨부한다. 푸른색이 실제 주가 수익률이고 붉은색이 추정한 수익률이다.

   확실히 뭔가 어중간한 느낌은 있으나 나름 잘 찾아낸 것 같다. 앞으로 다양한 최적화 알고리즘을 구현하면서 그 결과를 살펴볼 것이다.

A Brief History of Time - Stephen Hawking

0. 선물받은 킨들의 첫 도서이다. 아무래도 공대생이지만 물리학에 약해 읽는데 걱정이 많았으나, 그래도 꽤 부드럽게 읽을 수 있었다. 물론 책 중반부터 아무리 쉽게 얘기하고 싶어도 애초에 어려운 내용들을 풀어나가다보니 한 번 읽어서 이해 안되는 부분이 꽤 많았다. (그렇다고 다시 읽거나 하진 않았다. -_-)

1. 고전의 시대부터 사람들은 주변에 관심을 갖고, 자신만의 생각을 발전시킨다. 지구와 우주의 구성을 땅, 물, 불 등이라고 생각했던 고대 철학자, 우주의 중심을 지구라 생각했던 종교인들도 있었다. 그리고 시간이 지나며 많은 사람들이 관찰하고 실험하고 이론을 만들면서 과학이 발전한다.
 인간의 우주를 이해하고자하는 끝없는 노력은 우주를 설명하고자 하는 하나의 통합하는 이론을 만드는 것을 지향점으로 삼는다.

2. 뉴턴부터 시작되는 역학은 아이인슈타인의 상대성 이론을 거쳐 불확실성을 고려하는 양자역학으로 흐르고, 쿼크와 전자의 저에너지부터 빅뱅과 우주 생성을 생각하는 고에너지까지 사람의 과학적 호기심과 탐구는 우주의 진리를 찾기위해 동분서주한다. 하지만 그 어느 것도 완벽하게 우주를 하나의 모습으로 설명할 수 없다는 것은, 아직 인간이 관찰하고 실험할 수 있는 영역은 우주의 크기에 비해 매우 적다는 것으로 이해되고, 그와 더불어 그렇게 상상력을 발휘하여 이만큼 발전시킨 것도 정말 놀랍다고 할 수 있다.

3. 이 책은 우주와 시간을 이해하기위한 인간의 노력을 한권에 담았다. 스티븐 호킹 박사가 워낙 물리학계의 거두이다 보니 어려운 이론도 쉽게 말로 풀어쓰는 저력이 있다. 물론 모두 다 쉬운 것은 아니고 이해를 다 할 수도 없지만, 사람들의 우주와 시간을 이해하기 위한 노력을 이렇게 한 눈으로 볼 수 있다는 것은 정말 행운이리라.