알파고는 일종의 그림이라고 볼 수 있습니다. 당연하게도, 그림은 여러 물감이 서로 간에 뒤섞여서 만들어집니다. 알파고를 이루고 있는 물감은 다양합니다. 서로 간에 섞여서 새로운 색깔이 나오기도 하고요. 저는 그 중 아주 기초적인 부분 몇 가지에 대해 제가 아는 지식을 나누기 위해 이 글을 작성했습니다. 이 글은 알파고의 구조에 대한 완전한 설명이 아니며, 알파고의 자그마한 부분의 이론적 기초가 어떻게 짜여있는지를 설명하는 것이 목적입니다. 일단은 강화학습에 대해 먼저 얘기해볼 것이고요.
그럼 본론으로 들어가겠습니다. 이 글에서는 먼저 강화학습에 대한 대략적인 개요와 함께 MDP(Markov Decision Process)란 걸 짧게 설명하고 넘어가고, 그 MDP에 뒤따르는 가치 배정 문제(Credit assignment problem) 그리고 그 보상 배정 문제를 답하기 위해 나타난 벨만 방정식(Bellman‘s equation), 그리고 그 벨만 방정식에 대한 해답인 가치 반복(Value Iteration)을 얘기해볼겁니다.
강화학습은 인공지능이 세상으로부터 얻을 수 있는 보상을 최적화시키기 위해 전략을 짜도록 학습시키는 학문입니다. 따지고 보면 가장 초기적인 기계학습이라 할 수도 있겠죠. 1959년에 기계학습의 개척자 아서 새뮤얼이 자기 자신을 이길 수 있는 체커 인공지능을 개발해낸 순간을 기계학습의 분수령 중 하나로 여기고들 있으니까요. 강화학습은 20세기 중반 무렵에 행동주의의 영향을 받으며 지금까지 쭉 성장해왔고, 확률론과 통계학에서 여러 기법/개념들을 많이 수입해와서 이론적 기반을 쌓아오며 지금 현 수준에 도달했습니다. 그 이론적 기법의 핵심에는 MDP란게 있는데, 그거에 관해 얘기하며 본격적인 물꼬를 터 보도록 하겠습니다.
MDP는 세상을, 여러 상태(State)들로 나누어져 있고 이미 규정되어 있는 행동(Action)을 취함으로써 그 상태들 사이를 이미 규정되어 있는 확률에 따라 이동할 수 있는 모델로 다루는 방법론입니다.
간단하게 말하자면, 동전이 하나 있다고 해봅시다. 앞면이거나 뒷면이거나, 둘 중 하나겠죠. 이 동전이 취할 수 있는 상태는 딱 두 가지, 앞면 혹은 뒷면밖에 없습니다. 일단 앞면이라고 합시다.
저희는 이 동전에 대해 한가지 행동을 취할 수 있습니다. 튕기는 거요. 이 동전을 튕기면 무슨 일이 일어날까요? 반반의 확률로 앞면 혹은 뒷면이 나옵니다. 만약 앞면이 나온다면 동전의 상태는 변화하지 않습니다. 앞면에서 시작해서 앞면으로 넘어갔다면 사실상 아무 변화가 없는 거죠. 만약 뒷면이 나왔다면 앞면에서 시작해 뒷면으로 넘어간 거니 상태에 변화가 생겼습니다. 여기서 핵심은 행동 자체는 결정론적일지언정 그 행동의 결과는 확률론적이란 부분입니다. 동전을 튕긴다는 행동을 취하면 50%의 확률로 앞면이 나올 수도, 50%의 확률로 뒷면이 나올 수도 있습니다.
이렇게 이미 규정되어 있는 상태들 사이에 확률론적인 관계를 구축하는 것이 바로 MDP입니다. 앞면 뒷면은 상태(State)이고, 튕기는 행동은 행동(Action)이며, 그 행동을 취했을 시 나타날 결과들의 확률은 모델(Model; Transition function)입니다. 상태는 그 세계에서 일어날 수 있는 모든 경우의 수를 다루고 있다 보시면 되고, 행동은 한 상태에서 다른 상태로 이동하기 위해 취할 수 있는 모든 행동들을 다루고 있다 보면 되며, 모델은 이름 그대로 그 세계가 어떻게 작동하는가에 대한 법칙을 정한다 볼 수 있습니다. 여기에 마지막으로 보상도 덧붙히자면, 보상(Reward)는 각 상태와 연결되어 있는 보상을 뜻합니다. 예를 들자면, 동전 튕기기를 가지고 천원내기를 한다면 앞면이 나올 때는 천원의 보상이 주어지고 뒷면이 나올 때는 천원의 손실이 주어지는거죠. 각 상태에 진입했을 때 주어지는 것으로 볼 수도, 아니면 각 상태에서 특정 행동을 했을 때 주어지는 것으로 볼 수도 있는데, 사실 둘 모두 별 차이 없습니다. 이건 나중에 좀 더 얘기가 진행되면 무슨 말인지 이해가실겁니다.
정리하겠습니다. 강화학습에서 사용되는 MDP는 상태, 행동, 모델, 보상, 이 4가지를 가지고 세상을 구축하는 수학적 방법론입니다. 정책(Policy)란 것도 있긴 한데, 이건 나중에 얘기하겠습니다. 보시면 알겠지만 이 MDP는 모든 강화학습 기법에 있어서 절대 빼놓고 얘기할 수 없는 아주아주 중요한 부분입니다. 모든 강화학습 기법은 MDP로 구축 된 세상의 안에서 인공지능이 어떻게해야 가장 많은 보상을 얻을 수 있는지 최적의 전략을 찾아내는 것입니다. 비유하자면 헌법 같은거죠. 헌법의 어떤 부분에 초점을 맞추느냐에 따라 민법과 형법이 나뉠 수 있지만, 결국 둘 모두 뿌리는 헌법에 두고 있습니다.
그런데 이 MDP에는 아주 결정적인 문제점이 있습니다. 바로 가치배정문제(Credit assignment problem)이라는건데, 아주 골 때리는 놈이죠.
여러분은 살아가며 지금까지 많은 게임을 해오셨을겁니다. 아마 다들 스타 한두판은 해보셨겠죠. 여러분이 친구와 스타를 한판 했다고 가정합시다. 안타깝게도 졌습니다. 매우 안 좋은 결과입니다. 지는건 기분이 나쁘고, 지고 싶지 않습니다. 왜 졌는지 공부를 해서 다음부터는 비슷한 실수를 안 저지르고 싶습니다.
그런데 대체 왜 진걸까요? 어디서 실수가 있었던걸까요? 여러분은 이영호 저리가라 할 수준의 실력을 선보였지만, 마지막에 아주 결정적인 실수를 하나 저질렀던걸까요? 아니면 뭐 하나 꼭 집어 말하긴 어렵고 그냥 그만그만한 실수들을 시작부터 끝까지 끊임없이 저질러서 그게 계속 누적이 됬던 걸까요? 그도 아니라면 아예 초반에 아주 결정적인 실수를 저질러버려서 나중엔 아무리 발버둥을치더라도 그걸 극복할 수 없었던걸까요?
기계는 그걸 모릅니다. 졌다는건 아는데, 어디에 문제가 있는건지는 알 수가 없습니다. 패배하기까지 거쳐 간 상태들중 어느 상태에 안 좋은 가치값을 배정해야하는건지 영 아리송합니다. 그걸 판단하기 위해서는 일단 기준이 있어야하는데, 애초에 그 기준이 없어서 학습을 하려는거죠. 즉, 이런 딜레마에 빠진겁니다.
1. 학습을 하기 위해서는 어느 부분에 문제가 있던건지를 정확하게 판단해야한다.
2. 그것을 판단하기 위해서는 명확한 기준이 있어야한다.
3. 근데 학습하려는 대상이 바로 그 기준이다.
무언가를 학습하기 위해선 이미 학습을 다 끝낸 상태여야한다는 아주 골 때리는 딜레마에 빠진거죠. 이 딜레마를 해결하지 못한다면 강화학습이 존재할 수 없습니다. 그래서 이걸 해결하기 위해 유틸리티 함수란걸 도입합니다. 간략하게 설명드리자면, 유틸리티 함수는 예상가치입니다. 한 상태에 진입할 시 미래에 기대할 수 있는 예상가치를 함수로 나타낸거죠. 복권에 당첨 될 경우 당첨금을 가지고 재테크를 할 수 있으니 그 재테크 예상수익도 복권 당첨금과 합쳐서 계산하는거랑 비슷하다 보면 됩니다.
수학적으로 표기하자면, U(s1)를 s1란 상태의 유틸리티 값이라 할 시 유틸리티 함수는 이렇게 정의됩니다.
U(s1) = R(s1) + d * max{∑ [T(s1, a, s2) * U(s2)]}
a s2
s1, s2 = 상태
R(s1) = 첫번째 상태에서 얻는 즉각적인 보상
max{} = 최적의 행동 a를 택하는 것
a
d = 일종의 감가상각. 무한한 지평선 문제라는걸 해결하고 벨만 방정식을 유도해내기 위해 유틸리티 함수를 일차적으로 정의해내는 과정에서 필수적으로 도입하게 되는데, 걍 이런게 있구나 하고 넘어가도 무방.
T(s1, a, s2) = 첫번째 상태 s1에서 행동 a를 택할 경우 s2로 넘어가게 되는 확률
이걸 벨만 방정식(Bellman Equation)이라 하는데, 혹시 관심가실 분이 있을까봐 함 올려봤습니다. 뭔 말인지 몰라도 제가 앞으로 할 얘기 이해하는데 별 지장 없습니다. 걍 넘기셔도 됩니다.
이 벨만 방정식을 통해 유틸리티 함수를 정의하게 되면 여러가지 이득이 있습니다. 생각해보세요. 현재 즉각적으로 획득할 수 있는 보상과 함께 앞으로 미래에 얻을 수 있을 모든 보상들까지 예측할 수 있다면, 그냥 예상가치가 가장 높은 행동들을 택하기만 하면 되는게 아니겠습니까?
안타깝게도 세상살이라는게 그렇게 간단하지가 않습니다. 문제가 하나 있거든요. 벨만 방정식의 안에 이미 유틸리티 함수가 들어있단겁니다. 유틸리티 함수를 정의하는 방정식 안에 이미 유틸리티 함수가 들어가있으니, 유틸리티 함수가 없으면 유틸리티 함수를 구할 수 없는거죠. 맙소사, 왠 외계어 덩어리 방정식을 구했는데도 다시 시작점으로 돌아와버렸습니다.
이걸 해결하기 위해서 가치반복(Value iteration)이란 방법을 사용합니다. 유틸리티 함수 없이는 유틸리티 함수를 구할 수 없으니 일단 유틸리티 함수를 아무렇게나 만들어내고 시작하는겁니다. 그 과정은 다음과 같습니다.
1. 일단 유틸리티 함수에 무작위적으로 아무 값이나 배정하고 시작한다.
2. 각 상태의 유틸리티 값을 주변 상태들의 유틸리티 값에 따라 수정한다.
3. 무한반복.
수학적으로 표기하자면, U_t(s1)를 t번째로 수정한 유틸리티 함수라 할시 다음과 같이 정의됩니다.
U_t+1(s1) = R(s1) + d * max{∑ [T(s1, a, s2) * U_t(s2)]}
a s2
역시 이게 무슨 말인지만 대강 받아들이고 넘어가시면 됩니다. 이 수식은 복잡해 보이지만 여느 복잡한 수식들이 대부분 그렇듯이 내용물은 매우 간단하고 직관적입니다. 한 상태 s1이 있다고하면, 그 상태에 대한 유틸리티 값은 일단 완전히 무작위적으로 배정됩니다. 그 상태의 주위에는 역시 비슷하게 무작위적으로 배정 된 유틸리티 값을 지닌 다른 상태들이 존재합니다. 그럼 그 주변의 유틸리티 값을 가지고 s1의 유틸리티 값을 수정하고, 모든 상태들에 대해 이것을 반복합니다. 이게 다에요.
무작위 값을 가지고 시작을 했는데 단순히 여러차례 반복하는 것 가지고 유의미한 결과물을 얻어낸다는게 매우 이상하게 느껴질 수 있습니다. 하지만 이 가치반복 수식이 진정한 유틸리티 값을 얻어낼 수 있도록 도와주는 아주 강력한 힘이 있습니다. 바로 R(s1), 즉 즉각적인 보상입니다. 계속 학습을 반복하고 또 반복하다보면 각 상태들의 즉각적인 보상이 서서히 나머지 상태들을 향해 컵속의 잉크처럼 퍼져나가다 결국 진정한 유틸리티 값을 얻어내는 것이지요. 주변의 유틸리티 값에 따라 각 상태의 유틸리티 값을 꾸준히 수정해나가다보면 어느 순간 그 모든 상태들이 나머지와 끈끈하게 엮이게 된다고 보실 수도 있습니다.
정책은 이 유틸리티 값을 가지고 얻어낼 수 있는 하나의 대전략입니다. 각 상태에서 이동할 수 있는 다음 상태들을 모두 늘어놓은다음, 그 상태들의 유틸리티 값을 모두 다 비교해가지고 가장 예상가치가 큰 행동을 결정하는 것이지요. 정책은 각 상태마다 하나씩 존재합니다. 각 상태마다 내릴 수 있는 최적의 행동은 하나밖에 없으니까요.
여기서 상태가 아니라 행동이라 말한 이유는 MDP의 확률론적인 특징 때문입니다. 각 행동은 여러 상태들과 확률론적으로 연결되어 있습니다. 한 상태가 아주 높은 유틸리티 값을 지니고 있다해서 그 상태와 이어져있는 한 행동의 예상가치 역시 무조건 높은 것은 아니니까요. 그 행동과 연결되어 있는 모든 상태의 유틸리티 값을 보고, 그 행동을 취해 해당 상태로 넘어갈 수 있는 확률에 그 유틸리티 값을 곱한 다음, 그것들을 총합해서 그 행동의 예상가치를 구하는 것입니다.
그런데 어차피 정책이 중요한거라면 굳이 유틸리티 값을 정확하게 구할 필요는 없습니다. 그냥 대강 대소차이만 얼핏 잘 구분된다면 굳이 유틸리티 값을 정확하게 구할 필요 없이 곧장 정책으로 넘어가는게 효율적이죠. 이걸 정책반복(Policy iteration)이라 부르고, 다음과 같은 과정을 통해 이루어집니다.
1. 무작위로 각 상태에 대해 정책들을 정한다.
2. 무작위로 정한 정책에 따라 유틸리티 함수를 정한다.
3. 모든 상태에 대해 주변의 유틸리티 값에 따라 정책을 곧장 수정한다.
4. 수정 된 정책을 가지고 다시 새롭게 유틸리티 함수를 정한다.
5. 무한반복.
수학적으로 표기하자면, p_t(s1)을 t번째로 수정한 상태 s1의 정책이라 할 시 다음과 같이 정의됩니다.
U_t(s1) = R(s1) + d *∑ [T(s1, p_t(s1), s2) * U_t(s2)]
s2
이걸 도만 방정식(Doman‘s Equation)이라 합니다. 훨씬 간결해졌죠? 이렇게 되면 상태, 행동, 보상, 모델, 이 4가지를 가지고 그 안에서 언제나 최적의 전략에 따라 행동하는 인공지능을 만들 수 있습니다. 이게 강화학습의 가장 기초적인 뼈대입니다.
다음엔 뉴런연결망의 기본원리에 대한 글을 올리도록 하겠습니다.
찬성: 
반대: 
김우재
르웨느
밝은스텔라
Comment ' 12