공학 알파고의 일부 원리 - 1

[메가스콤네노스]

알파고에 대한 얘기가 이 커뮤니티에서 많이 이루어지고 있어서 이 글을 함 올려봅니다. 다른 곳에 제가 방금 쓴 글을 함 가져와봤습니다.

알파고는 일종의 그림이라고 볼 수 있습니다. 당연하게도, 그림은 여러 물감이 서로 간에 뒤섞여서 만들어집니다. 알파고를 이루고 있는 물감은 다양합니다. 서로 간에 섞여서 새로운 색깔이 나오기도 하고요. 저는 그 중 아주 기초적인 부분 몇 가지에 대해 제가 아는 지식을 나누기 위해 이 글을 작성했습니다. 이 글은 알파고의 구조에 대한 완전한 설명이 아니며, 알파고의 자그마한 부분의 이론적 기초가 어떻게 짜여있는지를 설명하는 것이 목적입니다. 일단은 강화학습에 대해 먼저 얘기해볼 것이고요.

그럼 본론으로 들어가겠습니다. 이 글에서는 먼저 강화학습에 대한 대략적인 개요와 함께 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가지를 가지고 그 안에서 언제나 최적의 전략에 따라 행동하는 인공지능을 만들 수 있습니다. 이게 강화학습의 가장 기초적인 뼈대입니다. 

다음엔 뉴런연결망의 기본원리에 대한 글을 올리도록 하겠습니다.

[경기도주민]

잘 읽었습니다. 어떻게 이런것들을 알고계신지 궁금합니다.

[메가스콤네노스]

예전부터 기계학습에 관심을 가지고 있었어가지고 이런저런 공부를 해왔습니다.

[복동이]

이걸 보니까 생물의 진화도 이것과 유사하게 진행되었을지도 모르겠다는 생각이 드는군요.

[메가스콤네노스]

MDP의 확률론적인 특징은 확실히 그런 점에서 매우 흥미롭습니다. 저희가 살아가는 세계는 매우 불확실한 곳이고 같은 행동을 했건만 매우 다른 결과가 나올 수도 있으니까요.

[첝]

실제로 인간 아기는 외부세계에 대한 일종의 통계적 분석을 통해 세상에 대해 학습한다고 합니다.

[메가스콤네노스]

흥미로운 사실이네요.

[halvarian]

벨만 방정식의 d값에 대해 좀 더 자세히 알 수 있는 자료가 있을까요? U(s1)을 고려할 때 U(s2)를 너무 크게 고려하지 않도록 하려고 시간가치 비슷한걸 부여한 정도인 건 알겠는데 구체적으로 d값이 어떻게 정해지는지에 대한 원리가 궁금하네요.

[메가스콤네노스]

d값을 시간가치와 비슷한 것으로 보신 것은 정확합니다. 우선 유틸리티 값을 정의하는데 있어 나타나는 무한한 지평선 문제(Infinite Horizon)라는 것부터 언급해보겠습니다.

동전이 하나 있습니다. 동전을 튕긴다면 님은 무조건 백원을 얻습니다. 앞면이 나오던 뒷면이 나오던간에요. 동전을 튕기지 않는다면, 님은 무조건 오십원을 얻습니다. 튕기던 튕기지 않던 무조건 님은 이득을 봅니다. 단지 얻는 이득의 총량이 달라질 뿐이지요. 그렇다면 이 세계에서 님이 내릴 수 있는 최적의 행동은 무엇일까요? 당연히 동전을 튕기는겁니다. 동전을 튕긴다면 백원을 얻고 동전을 튕기지 않으면 오십원을 얻으니까요.

[메가스콤네노스]

문제는 이 세계에는 시간제한이 없다는겁니다. 님은 원하신다면 동전을 백번 튕길수도, 천번, 만번, 천만번, 무한한 숫자의 행동을 취하실 수 있습니다. 아무 제한이 없으니까요. 모든 상태에서 동전을 튕기는 전략을 p1이라 하고 모든 상태에서 동전을 튕기지 않는 전략을 p2이라 합시다. 아무 제한이 없는 무한한 지평선의 세계에서 p1을 택할시 예상되는 유틸리티값과 p2을 택할시 예상되는 유틸리티 값에 차이점이 존재할까요? 둘 다 무한인데도요? p1이 p2보다 유리한건 분명한데, 둘 다 예상가치가 무한에 다다르니 사실상 비교가 불가능합니다. 이걸 바로 무한한 지평선 문제라 합니다.

[메가스콤네노스]

이 무한한 지평선 문제는 다른 부작용과도 이어집니다. 승리의 직전에 도달했을 때 승리를 취해서 게임을 끝내는 올바른 결정을 하는 대신 게임을 끝내지 않고 계속 시간만 끄는 기괴한 결정을 내리는 식으로요. 인공지능의 목적은 보상을 최적화하는거고, 승리를 취한다면 더 이상 보상을 얻을 수 없지만 승리를 취하지 않으면 계속 보상을 무한히 누적시킬 수 있으니 무한한 지평선의 세계에서 인공지능은 승리를 취하지 않는게 이득입니다. 이것은 무조건 해결해야만하는 아주 큰 문제입니다.

[메가스콤네노스]

그래서 도입 된 d값은 이렇게 정의됩니다.

0 <= d < 1

1보다 작고 0보다 크거나 같은 숫자. 벨만 방정식에서 보이다시피, d값이 0이라면 수식의 오른쪽 부분이 모두 다 사라집니다. 미래의 가치를 아예 눈꼽만큼도 보지 않는거죠. d값이 1이라면 없는거나 다름 없고 그렇다면 뒤에 곧 후술할 기하급수를 이용할 수 없으니 d값은 1보다 작아야합니다. d값이 1보다 작다면, 벨만방정식의 특수한 구조에 의해 아주 재밌는 일이 일어납니다. 벨만 방정식의 안에 이미 유틸리티 함수가 들어있잖아요? 그런데 벨만 방정식 안에 포함되어있는 유틸리티 함수에도 역시 d값이 들어있습니다.

[메가스콤네노스]

그럼 벨만방정식 안에 포함되어있는 유틸리티 함수 안에 포함되어있는 유틸리티 함수 안에 역시 d값이 들어있고, 무한반복. 끊임없이 자기자신을 호출하는 재귀적인 함수이기 때문에 d값은 꾸준히 호출되고 또 호출되면서 계속 제곱이 되어갑니다. 그런데 d는 1보다 작은 숫자죠? 그렇다면 d는 꾸준히 계속 작아집니다. 벨만방정식 안에서 유틸리티 함수가 호출되는 것은 미래의 예상가치를 산출하기 위해서인데, 방정식 구조상 그 예상가치의 예상가치가 또다시 산출되게 되고, 결국엔 예상가치의 예상가치의 예상가치 역시 또 산출되며 이것이 무한히 반복됩니다. 그런데 예상가치가 산출 될 때마다 d값이 꾸준히 계속 적용되니

[메가스콤네노스]

결국엔 d값이 0에 수렴하게되고 d값이 0에 수렴하고나면 사실상 그것이 지평선의 끝이 되버립니다. 무한한 지평선이 유한한 지평선으로 바뀌는거죠. 하지만 이 지평선은 계속 위치를 바꿉니다. s1에서 s2로 넘어가서 다시 s2에서부터의 예상가치를 산출하게되면, 여전히 동일한 거리에 유한한 지평선이 놓여집니다. 아무리 이동해도 상태와 지평선간의 거리가 바뀌지 않는거죠. 아주 큰 장점입니다.

[메가스콤네노스]

그럼 이제 유틸리티 값을 이렇게 정의해봅시다.
∞
U(s1, s2, s3, s4 ~~~) = ∑d^t * R(st)
t=0

st는 t번째 상태 s를 일컫는거고, R(st)는 t번째 상태 st의 즉각보상을 뜻합니다. 그냥 모든 상태에 대해 즉각보상 값을 다 더한건데, 매번 d값을 제곱해가면서 서서히 줄여나갔습니다. 그럼 이건 기하급수를 이용해, R(m)를 각 상태가 얻을 수 있는 최대의 보상값이라 할 시, 이렇게 정리할 수가 있습니다.
∞ ∞
∑d^t * R(st) <= ∑d^t * R(st) = R(m) / (1 - d)
t=0 t=0

[메가스콤네노스]

이렇게 d와 기하급수를 이용해 유틸리티 함수의 무한한 지평선 문제를 해결하고나면 결국 벨만방정식을 유도할 수 있게 됩니다.

[메가스콤네노스]

여기서 핵심은, 유틸리티 값의 최고값은 모든 상태에 대해 최대보상 R(m)을 넣은겁니다. 즉, 유틸리티 값이 어떻게 되던간에 모든 유틸리티 값은(댓글창에는 시그마를 제대로 쓰기가 힘드네요; 아래에 t=0 넣고 위에 무한기호 넣어서 보세요) ∑d^t * R(st) 보다 작거나 같습니다. 그런데, 유틸리티 함수라는게 얻을 수 있는 가~~장 높은 값이, 무한이 아니라 유한입니다. 기하급수에 의해 정의되었으니까요. 그럼 무한한 지평선 문제가 해결되는겁니다.

[halvarian]

결국 무한한 지평선 문제를 해결하기 위해 0<=d<1으로 설정한다는 건데, 그렇다면 효용함수의 d값은 사람이 처음 설정한 임의의 값이 계속 남게 되는건가요? 아니면 딥러닝 과정에서 적절한 d값을 컴퓨터가 추론하면서, 최초에 사람이 설계한 효용함수보다 좀 더 적절한 d값을 갖도록 효용함수를 수정해 나가는 프로세스가 추가적으로 있는건가요?

[메가스콤네노스]

보통은 여러 다양한 d값을 시험해보고 가장 적당한 값이 구해지면 그걸 쭉 사용합니다. 알파고는 어떤지 잘 모르겠는데, 아마 비슷할겁니다.

[halvarian]

그렇군요! 설명 감사합니다. 다음 글도 기대하겠습니다 ^^

[메가스콤네노스]

감사합니다 ㅎㅎ

[메가스콤네노스]

아 근데 기계학습에 관심이 가셔가지고 좀 더 자세히 배워보고 싶으시다면 class central 들어가서 기계학습 강의 괜찮은거 찾아 들어보세요. 좋은거 많습니다.

[첝]

대학 들어갔을 때 나도 이런 걸 했어야하는데... ㅠㅠ