[카카오AI리포트]알파고를 만든 강화학습 비밀part2
강화학습(reinforcement learning) 스터디(2편)
이세돌과 알파고의 경기가 있은지 약 1년 후인 2017년 5월 당시 바둑 세계 랭킹 1위의 커제와 더욱 강력해진 알파고의 경기가 진행되었습니다. 알파고는 커제와 중국 기사들에게 단 한 경기도 내주지 않으며 이전에 비해 더욱 완벽해진 모습을 보여줬습니다. 그리고 마치 더 이상 상대할 인간이 남지 않은 것 마냥 알파고는 커제와의 대국을 마지막으로 은퇴했습니다. 1년 전 이세돌이 이긴 한 경기가 인간이 알파고에서 승리한 마지막 경기로 남게 되었습니다.
[카카오 AI 리포트] Vol. 6 (2017년 8월호) 는 다음 내용으로 구성되어 있습니다.
[1] Industry - 데이터와 음성인식
01. 하용호 : 머신러닝 적용의 실제, 논문이 가르쳐주지 않는것들
[2] Trends - 생생한 AI 현장의 이야기
04. 하영식 : AI 접목된 의료영상의 주요 플레이어들
[3] Learning - AI 연구 동향과 강화학습 개념
06. 엄태웅 : 딥러닝 연구의 현재와 미래 part 2
07. 최성준, 이경재 : 알파고를 탄생시킨 강화학습의 비밀 part 2 (이번글)
[4] Information
[카카오 AI 리포트] Vol. 6 전체글 다운받기
내용 중간의 [ ]는 뒷부분에 설명 및 관련 문헌의 소개 내용이 있음을 알리는 부호입니다. 예를 들어, [1]에 대한 설명은 '설명 및 참고문헌'의 첫 번째에 해당합니다.
강화학습 스터디 시리즈를 지난 Part1 - 알파고를 탄생시킨 강화학습의 비밀 에 이어서 Part2로 서울대학교 박사과정에 재학중인 최성준, 이경재 님께서 이야기 해주십니다.
바둑을 시작한 지 채 5년이 되지않은 알파고가 이토록 바둑을 잘 둘 수 있었던 이유는 무엇일까? 이에 대해서 자세히 알아보기 이전에 바둑이란 게임이 왜 이제껏 컴퓨터에게 난공불락이었는지 알아보도록 하자. 일반적으로 바둑이나 체스와 같이 두 명의 선수가 번갈아가면서 하는 게임을 해결하기 위해 사용한 알고리즘은 트리 탐색(tree search) 기반의 전수 조사(발생 가능한 모든 경우의 수를 고려하는 경우)였다. 대표적인 예로 체스를 두는 IBM의 '딥블루'가 있다. 딥블루는 상대방과 자신이 둘 수 있는 경우의 수를 12수 정도를 고려하여 최적의 수를 찾으며, 당시 체스 세계챔피언이었던 러시아의 가리 카스파로프(Garry Kasparov)에게 승리를 거두었다. 당연히 딥블루 이후 인공지능과 인간의 체스 승부에서 승리의 신은 인간의 손을 들어주지 않았다.
체스 게임의 경우 발생 가능한 모든 경우의 수를 계산해보면 10의 100승 정도가 된다. 이 수는 엄청 큰 수임에는 분명하나 병렬 처리 기술을 활용하면 주어진 시간 내에 모두 처리 가능한 수이다. 하지만 바둑 게임의 경우 발생 가능한 경우의 수는 10의 200승이 넘어가고, 이는 전 우주에 있는 분자의 수 보다 많은 수다. 다시 말해, 현존하는 기술로는 이 모든 경우의 수를 처리할 수 없고, 당분간도 없을 예정이다.
알파고의 엄청난 기력(바둑 실력)은 크게 두 가지 기법의 조합으로 이뤄져있다. 첫 번째는 모든 가능한 수를 조사하지 않아도, 제한된 시간 내에 효과적으로 수를 계산하는 몬테카를로트리탐색(Monte Carlo tree search, MCTS)방법이고, 두 번째는 심도 학습(deep learning)을 통해서 이 MCTS를 더 효과적으로 수행하는 것이다. 여기서 심도 학습은 크게 두 가지 네트워크를 학습시키는데 사용되었는데, 현재 바둑판이 주어졌을 때, 상대방이 다음에 어디를 둘지 예측하는 policy network와 바둑의 판세를 읽어는 value network이다. 심도 학습이 이러한 역할을 할 수 있었던 것은 딥신경망(deep neural network)이 다른 알고리즘에 비해 훨씬 더 많은 양의 정보를 고려할 수 있고, 이에 따른 높은 일반화의 성능 때문이다.
알파고에 사용된 MCTS 외에도 심도 학습은 일반적인 강화 학습(reinforcement learning)에도 많이 사용되고 있고, 이러한 형태의 강화 학습을 deep reinforcement learning (Deep RL)이라고 부른다. 뒤에서 더 자세히 설명하겠지만, Deep RL은 크게 두 가지로 나뉠 수 있다. 첫째로는 Q function을 딥신경망으로 모델링하는 DQN(deep Q Network)와 둘째, 정책함수(policy function)를 모델링하는 심화 정책 경도(deep policy gradient)이다.
알파고의 방법론
일반적으로 기계학습에서 “Monte Calro”가 들어간 방법론들은 샘플링(sampling)을 통해서 문제를 해결하는 방법을 의미하는데, MCTS도 이와 유사하다. 체스 게임을 다루던 기존의 트리탐색 방식은 모든 경우의 수를 검색해 가장 좋은 수를 고르는 반면, MCTS는 몇 가지 해봄직한 수를 샘플링하여 검색하는 방법을 취한다. 즉 모든 수를 검색하기에는 바둑의 수가 너무 많으니 그 중에서 몇 가지 가능성이 있는 수를 우선적으로 탐색하는 것이다. 여기서 “해봄직”한 수를 고르고, 나와 상대방이 되어 수를 진행해 나가고, 현재 주어진 바둑판의 판세를 읽는데 모두 딥뉴럴네트워크가 사용된다. 강화학습에 나오는 Q value와 같은 의미로 이 수를 두었을 때 미래에 내가 얻을 보상, 즉 게임의 승패를 의미하는 값을 예측한다.
이 값을 추측하기 위해서 두 가지 값을 이용하는데 첫 번째는 승패 예측 값이다. 승패 예측을 하기 위해서 두 번째 네트워크인 value network를 이용한다. value network가 하는 일은 어떤 수를 두었을 때, 그 바둑판의 판세를 읽고 이길지 질지를 예측하는 것이다. 그리고 Q value를 추측하기 위한 두 번째 값으로 샘플링을 통한 예측 값을 사용한다. 어떤 수를 두었을 때, 그 후에 일어날 미래의 대국을 시뮬레이션 해보고 시뮬레이션 결과로부터 승패를 예측하는 것이다.
그리고 시뮬레이션 승패 결과와 value network의 승패 예측 결과를 적절히 합하여 탐색한 수에 대한 Q value를 예측한다. 이렇게 몇 가지 해봄직한 수에 대해 Q value를 예측하고 예측된 수중 가장 좋은 수를 선택하는 것이 알파고의 알고리즘이다. 이제부터 MCTS의 원리와 MCTS에 사용되었던 네트워크(network)를 어떻게 학습시켰는지에 대해 알아 보도록 한다.
트리탐색 방법(tree search)
MCTS를 알아보기 전에, 기존 방법론인 트리탐색(tree search)이 어떤 원리로 작동하는지, 어떻게 바둑처럼 번갈아가면서 플레이하는 게임을 풀 수 있는지에 대해서 살펴보도록 한다. 그림 1.과 같이 tic-tac-toe를 예시로 살펴보자.
그림 1. tic-tac-to게임의 트리탐색 해결 방법. 출처 : http://snipd.net/minimax-algorithm-with-alpha-beta-pruning-in-c탐색트리의 가장 위에 위치한 보드가 현재 플레이어의 상태를 의미하고, [그림 1]에서 X표시가 플레이어의 돌을 O표시가 상대방의 돌을 의미한다. 트리탐색 방법에서는, 먼저 플레이어가 할 수 있는 가능한 행동들로 첫 번째 가지를 확장시킨다. 두 번째 줄의 보드들이 플레이어가 각각의 수를 두었을 때 보드의 상태를 나타낸다. 그리고 다음 가지는 상대방이 둘 수 있는 모든 수를 고려하여 확장시킨다. 이런 식으로 플레이어와 상대방이 둘 수 있는 모든 수를 나무(tree)가지를 뒤집은 형태로 그린 것이 [그림 1]의 모습이다. 이렇게 나뭇가지를 만드는 과정을 확장(expansion)이라고 한다.
모든 수에 대해 나뭇가지를 확장하면 트리의 마지막 줄에는 게임이 끝난 상태의 보드들이 저장되고 게임의 승패 혹은 점수를 계산 할 수 있다. 이 점수를 [그림 1]의 마지막 줄에 있는 0과 1로 표현했다. 0은 무승부를 1은 플레이어의 승리를 의미한다. 이후 Tree의 마지막 줄에서부터 가장 꼭대기까지 승패의 결과를 업데이트 한다. 이 업데이트 과정을 거치면서 각 가지들은 승패에 대한 기댓값을 갖게 되고 이는 플레이어의 승률을 의미한다. 정보를 업데이트(update)한다는 것은 수를 두었을 때 플레이어가 승리 할지 패배 할지에 관해 위로 전파시키는 과정을 말한다.
승패 정보를 밑에서부터 위로 전파시키는 데에는 따라야 할 규칙이 있는데, 이것을 최소-최대정리(Mini-Max theorem)라고 한다. 플레이어는 항상 점수가 가장 높은 수를 선택하고 상대방은 항상 플레이어의 점수가 낮아지는 수를 선택하는 것을 말한다. [그림 1]에서 두 번째 가지에서 첫 번째 가지로 승패 정보를 업데이트 시킬 때, 각각의 가지들이 두 개씩 존재하기 때문에 어느 한 정보를 선택해서 업데이트 하게 되는데, 두 번째 가지는 상대방이 둘 수 있는 수를 나열 한 것이고, 상대방에 대한 업데이트 규칙이 적용된다. 즉, 더 작은 점수가 윗가지로 전파되는 것이다.
상대방은 자신의 승리를 위해서 플레이어의 점수가 최소화 되도록 행동해야하기 때문이다. 이와는 반대로 플레이어는 자신의 점수가 최대가 되는 행동을 선택하여 점수를 전파한다. 이렇게 모든 승패 정보가 트리의 뿌리(root)까지 전파되었으면, 플레이어는 승리할 확률이 가장 큰 경우의 수를 선택하면 된다. 승패를 전파하는 과정에서 상대방은 항상 플레이어가 가장 낮은 점수를 받도록 혹은 패할 확률이 높은 행동을 했기 때문에 뿌리에서는 항상 최악의 상황을 고려한 수를 두게 되어 적어도 비길 수 있게 된다.(그렇지 못하다면 그 게임은 처음부터 상대방에게 유리한 게임일 것이다.) 이런 방식을 “최악의 상황들 중 최선의 행동을 선택한다.”라고 표현 할 수 있고 이 원리를 최소-최대정리라고 하는 것이다.
트리탐색 방법을 간단하게 요약하면, 상대방의 수를 모두 고려하여 트리를 만든 뒤 트리의 마지막 노드(node)를 이용하여 게임의 승패를 결정하고, 이 정보를 트리의 뿌리까지 전파(정보 업데이트)시키는 것이다.
몬테카를로트리탐색 방법
바둑 게임에 트리 탐색기법을 적용한다고 생각해보자. 첫수부터 시작하여 모든 경우의 수를 트리로 만든다면 엄청난 수의 가지치기를 해야 할 것이다. 만약 이것이 가능하다면 바둑의 필승 법 혹은 지지 않는 법 등이 개발되었을지도 모른다. 그러나 바둑의 모든 수를 나타내는 방대한 트리를 저장할 메모리와 이 트리의 승패 정보를 처리할 수 있는 컴퓨터는 아직까지 존재하지 않는다. 이런 문제를 해결하기 위해서 트리탐색에 몬테카를로 방법을 적용하게 된다. 몬테카를로 방법은 대부분의 경우 샘플링 기법이라고 바꿔서 말해도 의미가 통한다. MCTS는 기존의 트리탐색과 같이 모든 경우의 수를 조사하는 것이 아니고 몇 가지의 경우를 샘플링하여 조사하는 것이다. 샘플링에 기반을 둔 MCTS 알고리즘은 [그림 2]와 같은 순서로 진행된다. 선택(selection), 확장(expansion), 시뮬레이션(simulation), 역전파(back propagation) 네 단계를 거치면서 문제의 답을 찾아가게 된다.
그림 2. 몬테카를로트리탐색 방법 개요그림 출처 : https://www.researchgate.net/publication/23751563_Progressive_Strategies_for_Monte-Carlo_Tree_Search
MCTS의 작동 과정을 간단히 설명하면, 먼저 어떤 수를 탐색할지 선택(selection)하고, 탐색하고자 하는 경우의 수로 확장(expansion)한 뒤, 확장한 수의 승패를 예측(simulation)하고, 그 결과를 나무의 뿌리쪽으로 업데이트 하는 역전파(back propagation)과정으로 이루어진다. 뒤에서 자세히 설명하겠지만, 알파고에서는 선택 과정과 예측 과정에서 컨볼루셔널 뉴럴 네트워크(convolutional neural network)가 사용되었다.[그림 3]은 MCTS 네가지 방법이 반복(iteration)적으로 이루어지는 모습을 나타낸 것이다.
각각의 방법을 자세히 알아 보도록 하자. 먼저, 선택 과정에서 어떤 노드, 어떤 수를 탐색할지 선택하게 된다([그림 3]의 오각형 모양 노드). 이때는 특정 규칙을 따라서 탐색할 경우의 수를 선택하게 되는데, 이런 규칙을 선택 규칙(selection rule)이라고 한다. 알파고에서는 UCT(upper confidence bounds for trees)라는 방식의 선택 규칙을 사용하였다. 알파고에 적용된 UCT를 설명하기 전에 이러한 선택 규칙이 MCTS의 성능에 미치는 영향을 먼저 생각해보자. 어떤 경우의 수를 탐색할지 선택하기 위해서 주로 두 가지 기준을 이용한다.
첫 번째는 ‘얼마나 다양한 수를 탐색할지’ 그리고 두 번째는 ‘한 가지 수를 얼마나 여러 번 시뮬레이션 할지’ 이다. 기계학습(machine learning)에서는 이런 기준을 탐색과 활용(exploration and exploitation)라고 부른다. 경우의 수를 다양하게 탐색하는 것은 어떤 식으로 성능에 영향을 미치게 될까? 직관적으로 생각해보면, 좋은 수를 시뮬레이션 해보지 못하면 좋은 수의 승률을 예측하지 못하고 최종적으로는 다음 경우의 수를 선택 하지 못하는 것이다.
따라서 다양한 수를 탐색하는 것은 좋은 수를 찾아내는데 있어서 중요한 역할을 한다. 두 번째로 한 가지 경우의 수를 여러 번 시뮬레이션 하는 것은 탐색하는 수의 승률 예측의 정확도를 결정하게 된다. 이 시뮬레이션 과정이 몬테카를로 또는 샘플링 과정이기 때문에 많은 샘플을 뽑으면 뽑을수록 높은 정확도로 승률을 예측하게 된다. 정확한 승률 예측을 해야 좋은 경우의 수와 나쁜 경우의 수를 정확히 구별해 낼 수 있게 된다. 선택(selection) 과정에서는 매번 새로운 수를 시뮬레이션 할지 아니면 이전에 탐색했던 수를 다시 시뮬레이션 하여 승률 예측의 정확도를 높일지를 비교하여 탐색할 수를 결정 하게 된다.
이때 탐색(exploration)을 너무 많이 하게 되면 승률 예측의 정확도가 떨어지게 되고 반대로 활용(exploitation)을 너무 많이 하게 되면 다양한 경우의 수를 탐색하지 못해 최적의 수를 찾지 못하게 된다. 따라서 이 둘 사이의 적절한관계(tradeoff)를 고려하여 탐색과 활용을 하는 것이 MCTS의 핵심이다. 추가적으로 tradeoff는 강화학습 에서도 중요하게 다뤄지는 문제이다.
알파고에서는 이러한 exploration and exploitation tradeoff를 해결하기 위해서 아래와 같은 UCT 형태의 선택 규칙을 사용한다.
St 는 현재 주어진 바둑판을 의미하고, at 는 다음에 탐색해야할 수(행동)를 의미한다. 그리고 Q(St, a) 는 지금까지 예측한 각각의 경우의 수 a에 대한 승률을 나타내고 u(St, a) 는 보너스 값으로 P(s,a)와 N(S,a) 에 의해서 결정된다. P(S,a) 는 프로기사들의 기보를 통해서 학습하는 값으로 프로기사들은 현재의 바둑판 상황 St 에서 a라는 수를 선택할 확률을 의미한다.
그리고 N(S,a)은 a라는 수가 탐색 과정에서 얼마나 선택 되었는지를 말한다. 따라서 u(St,a) 는 a라는 수가 많이 선택되게 되면 N(S,a)이 증가하여 줄어들게 되는 값이고 P(S,a)에 비례하므로 프로기사들이 둘 확률이 높은 수에 대해서는 큰 값을, 둘 확률이 낮은 수에 대해서는 작은 값을 갖게 되어있다. u(St, a)의 역할은 프로기사들이라면 선택할 만한 다양한 수들이 탐색하도록 만드는 것이다. Q(St, a) 와 u(St,a) 값이 경쟁하면서 탐색과 활용을 조절하게 된다. MCTS의 초반에는 시뮬레이션 횟수 N(s,a)가 작기 때문에 u(St,a)가 Q(St,a)에 비해서 더 큰 값을 갖게 되고 따라서 다양한 수를 탐색하게 된다. 그리고 많은 시뮬레이션을 거쳐 N(S,a)가 적당히 커지게 되면 u(St,a)가 작아지면서 Q(St, a)의 영향을 받게 되고, 승률이 높은 수를 집중적으로 탐색하게 된다.
이러한 과정에서 가능한 모든 수를 동등하게 탐색하지 않고 P(S, a)에 비례하여 탐색하기 때문에 프로기사들이 주로 두었던 수에 기반하여 탐색을 하게 된다. 그리고 P(S,a)를 모델링 하기 위해서 딥 컨볼루셔널 뉴럴 네트워크(deep convolutional neural network)가 사용되었다.
한 가지 수를 탐색한다는 것은 시뮬레이션을 통해 게임을 끝까지 진행하고 그 시뮬레이션의 승패 결과를 얻는 것을 말한다. 시뮬레이션하기 위해서는 플레이어와 상대가 어떻게 행동할 것인가, 혹은 바둑으로 치자면 어떤 수를 둘 것인가에 대한 행동 양식이 있어야 한다. 이것을 정책(policy)이라고 부르는데 [그림 3]에서는 시뮬레이션에 사용되는 정책을 기본정책(default policy)라고 표시하였다.
가장 쉽게 적용 할 수 있는 방법은 기본 정책으로 랜덤하게 행동을 취하는 무작위정책(random policy)를 사용하는 것이다. 다시 말해 무작위로 수를 두는 것이다. 또는 시뮬레이션의 정확도를 높이기 위해서 다양한 휴리스틱(heuristic)들을 사용한다. 알파고에서는 기본 정책에 프로기사들의 대국 기보를 기반으로 학습한 rollout policy network를 사용함으로써 시뮬레이션의 정확도를 높였다. 그리고 이 시뮬레이션 결과를 보완 해주는 역할로 value network를 사용하였다. Value network는 시뮬레이션을 하지 않고, 현재 주어진 바둑판을 보고 승패를 예측하는 역할을 하여서 시뮬레이션 횟수를 줄이는데 도움을 주었다. 그리고 이 value network의 승패 예측이 꽤 정확히 작동했기 때문에 알파고가 좋은 수를 찾을 수 있었다.
시뮬레이션이 끝나면 승패 결과를 얻게 되는데 [그림 4]에서 네모 상자에 써져있는 것이 승패의 결과이다. 1은 승리 0은 패배를 의미한다. 그 뒤에는 승패 결과를 탐색을 시작한 오각형 모양의 노드에 업데이트 한다. 따라서 탐색을 반복하면 반복 할수록 승패 결과가 쌓이게 되고 이 값을 통해 각각의 수들의 승률을 추정 할 수 있게 된다. [그림 3]의 각 노드에 써져있는 숫자들이 바로 승률을 의미한다. 그리고 충분한 횟수만큼 탐색을 한 뒤에는 승률이 가장 높은 수를 선택하는 것이 MCTS의 작동 방식이다.
그림 3. 몬테카를로트리탐색에서 단계별로 탐색을 확장하는 과정. 출처 : https://jay.tech.blog/2017/01/01/heuristic-search-mcts/value network 와 policy network
지금부터는 딥뉴럴네트워크가 MCTS에서 어떻게 활용되고 있는지 알아보도록 하자. 먼저, 각각의 네트워크의 역할과 학습 방식을 설명하고 그 네트워크들이 MCTS의 어느 부분에 들어가게 되는지 설명하려고 한다. 알파고는 총 세 가지 뉴럴 네트워크(neural network)들을 사용하였다. 각각 뉴럴 네트워크의 이름은 rollout network, supervised policy network, 그리고 value network이다. 앞의 두 가지 네트워크는 현재 바둑판의 상태를 파악하고 다음 수를 예측하는 역할을 하고, value network는 현재 바둑판의 상태를 파악해서 게임의 승패를 예측하는 역할을 한다.
이 세 가지 네트워크들의 공통점은 모두 ‘예측’하는 역할을 한다는 것이다. 다음 수를 예측하거나 승패를 예측하는 것을 머신러닝의 분류(classification) 문제로 바꿀 수 있는데, 알파고는 바로 이 분류 문제에 딥러닝을 적용함으로써 큰 성능 향상을 가져올 수 있었다. 다음 수를 예측하는 것은 현재 바둑판에 놓여있는 바둑알을 입력하여 다음 19x19가지의 경우의 수중에 한 가지를 선택하는 문제로 볼 수 있다. 그리고 승패를 예측하는 것은 현재 바둑판 상태를 입력해서 승 혹은 패, 둘 중 한 가지를 선택하는 문제로 볼 수 있다.
이렇게 몇 가지의 선택지 중 한 가지를 고르는 분류 문제에서 딥러닝이 탁월한 성능을 보여주고 있다.최근들어 다양한 딥러닝 기법들이 개발되면서 분류 문제에서 딥러닝이 탁월한 성능을 보여주었고 알파고는 이를 바둑에 적용한 것이다. 예를 들어 이미지를 보고 이미지 속에 어떤 물체가 있는지 고르는 문제, 혹은 사람이 있는지 없는지, 입력한 이미지가 고양이인지 아닌지 등을 맞추는 것은 딥러닝이 탁월한 성능을 보이는 분류 문제들이다. 바둑판의 판세 예측, 다음에 둘 수의 예측 문제들을 분류 문제로 바라보고 딥러닝을 적용한 것은 딥러닝이 좋은 성능을 보일 수 있는 문제에 적절히 적용한 것이라고 생각한다.
그림 4.네트워크의 지도학습 단계 [3] 그림 출처 : https://blog.acolyer.org/2016/09/20/mastering-the-game-of-go-with-deep-neural-networks-and-tree-search/
이제부터 rollout policy, supervised policy, value network를 살펴보도록 하자. Rollout policy와 supervised policy는 같은 것을 학습 한다. 현재 바둑판 상태를 파악해 다음 수를 어디에 두어야 하는지를 예측하는 것인데, 왜 두 가지 네트워크를 같이 학습시킬까? 이유는 서로 같은 것을 학습하지만 쓰이는 곳이 다르기 때문이다.
Rollout policy는 MCTS의 시뮬레이션에 사용되고 supervised policy는 선택 과정에 사용되어진다. 이 때문에 학습하는 것은 같지만, 그 구조에 차이가 있게 된다. Rollout policy는 히든 레이어(hidden layer)가 없는 아주 간단한 형태의 구조를 사용하였고 supervised policy는 히든 레이어가 11층 있는 복잡한 구조를 사용하였다 [3]. Rollout policy를 간단한 형태로 만든 이유는 시뮬레이션 속도를 빠르게하기 위해서다. 딥뉴럴네트워크의 특성상 히든 레이어가 많아지면 변수(parameter)가 늘어나고 연산 횟수가 늘어나게 된다.
실제로 몇 만 번의 시뮬레이션을 하는 MCTS에서 히든 레이어가 많은 복잡한 형태의 네트워크를 사용하게 되면 빠른 계산이 어렵게 될 것이고 이를 피하기 위해서 rollout policy는 매우 간단한 형태의 구조를 사용하였다. 반대로 MCTS의 선택 과정에 사용되는 supervised policy는 상대적으로 복잡한 구조의 네트워크를 이용하였다. Supervised policy는 앞서 나온 수식으로 학습을 하게 되는데, 이에 활용한 데이터가 프로기사들의 기보들로서 프로기사들이 주로 두는 경우의 수들을 정답(supervised)의 확률로 기억하게 된다. 즉, 프로기사들이 주로 뒀던 수들은 높은 확률을 갖도록 학습된다. 즉 탐색 과정에서 의미 없는 수를 탐색하는 것이 아니라, 프로기사들이 주로 두는 수를 우선순위로 하여 탐색을 진행 하게 해주는 역할을 한다.
이 네트워크가 rollout policy에 비해 복잡한 이유는 시뮬레이션에 사용되지 않아 상대적으로 느리게 학습이 진행되고, 높은 정확성을 필요로 하기 때문이다. 일반적으로 네트워크의 깊이(히든 레이어의 개수)가 많아지면 성능이 높아진다고 알려져 있기 때문에 많은 양의 기보를 더 정확히 학습하기 위해서 supervised policy는 rollout policy에 비해 더 복잡한 네트워크를 사용하게 된 것이다.
마지막으로, value network는 현재 바둑판의 상태를 통해 승패를 예측하도록 학습되었는데, 이 네트워크를 통해서 시뮬레이션 횟수를 줄일 수 있었다고 본다. 기존 강화 학습에 많이 사용하던 rollout policy의 시뮬레이션에 의존한 승패 예측 방식이 알파고에서는 시뮬레이션과 value network를 같이 사용하면서 많은 시뮬레이션을 하지 않고 기보 데이터의 도움을 받아 적은 시뮬레이션으로도 높은 승패 예측 정확도를 낼 수 있었다고 보는 것이다. 이때 value network를 학습시키기 위해서 기존에 한국의 프로기사들이 두었던 대국의 기보와 알파고 끼리 둔 바둑 기보를 합하여 학습을 하게 했는데, 이 부분에서 재미있는 사실을 한 가지 발견 할 수 있다.
알파고에 사용한 value network는 왜 프로기사들의 기보와 알파고 끼리 대국한 기보를 합쳐서 학습 한 것일까? 바로 프로기사의 기보에 있는 바이어스 효과를 없애기 위해서다. 프로기사들에게는 보통 기풍이라는 것이 존재 한다. 예를 들면, 이창호와 같은 기사는 치밀한 계산 하에 수비적인 바둑을 구사하는 반면, 이세돌 같은 바둑기사는 꽤 공격적으로 바둑을 둔다. 기풍이라는 것은 프로기사의 기보 데이터가 다양한 샘플을 담고있지 못하게 하는 것이다. 즉, 기보를 만들어내는 기사들은 저마다의 기풍으로 바둑을 두기 때문에 다양한 기보가 생성되는 것이 아니고, 비슷비슷한 형태의 바둑기보들이 생성되는 것이다.
여기서 생기는 바이어스 때문에 실제로 프로기사의 데이터를 이용하여 학습한 경우 학습에 사용된 트레이닝 셋에서는 높은 예측 정확도를 보이지만 학습에 사용되지 않은 테스트 셋에서는 낮은 예측 정확도를 보인다. 이러한 경우를 일반화(generalization)가 좋지 못하다고 하는 것으로, 학습에 사용된 데이터에 대해서는 높은 확률로 승패 결과를 맞추지만 학습에 사용되지 않은, 즉 처음 보는 데이터에 대해서는 승패 결과를 잘 맞추지 못하는 것을 말한다. 이런 현상을 알파고에서는 알파고 끼리 대국한 기보 데이터를 추가하여 학습함으로써 해결하였다. 여태까지 설명한 세 가지 네트워크들은 [그림 5]와 같이 선택과 시뮬레이션(simulation, 다른 말로는 evaluation)에 사용되고 있다.
그림 5. 알파고에 적용된 몬테카를로트리탐색 방법. 종합하자면, 알파고의 알고리즘은 딥러닝을 기존의 방법론인 MCTS의 선택과 시뮬레이션 과정에 적용한 것이다. 승패 예측과 탐색의 우선순위 등을 많은 양의 데이터를 통해 학습된 딥러닝과 기존의 방법론인 MCTS를 융합하여 극복하였다는 사실은, 딥러닝을 다른 분야에 적용하는데 있어서 본받을 만한 선례를 만들었다고 생각한다.
DQN과 DQN의 학습 기법
이제 다시 강화학습으로 돌아와서 강화학습에서 딥러닝이 사용된 배경과 그 학습 방법을 알아보자. 딥강화학습(deep reinforcement learning)은 벽돌깨기와 같은 아타리(Atari) 게임 문제를 해결한 deep Q learning에서 시작하여 지금은 연속공간에서의 정책함수(policy function)와 그 정책함수의 좋고 나쁨을 평가하는 Q함수(Q function)를 동시에 학습하는 actor critic 방법까지 진화 하였다. 강화학습 입장에서 딥러닝은 Q함수를 모델링하기 위한 함수 추정 모델 중 한 가지 불과 하다. 일반적인 regression 기법들을 강화학습에 적용 시킬 수 있도록 이론적으로 발전해 왔다. 딥러닝 이전에는 커널 회귀 분석(kernel regression)을 이용한 방법들이 많이 연구되었다. 그러나 딥러닝 알고리즘 발전과 GPU의 등장에 힘입어 커널 방법을 제치고 deep Q learning이 강화 학습에 사용되고 있다. 최근 딥강화학습 연구 결과들은 이미 과거에 간단한 함수 추정 방법론을 이용하여 연구되었던 방식들을 딥뉴럴네트워크로 바꾼 경우가 많이 있다.
강화학습과 DQN의 함수 추정(function approximation)
강화학습에서 함수 추정(function apporoximation)이 적용된 이유는 무엇일까? 함수 추정의 특성은 일반화(generalization)에 있는데 바로 이 일반화 특성을 이용하여서 학습한 Q 함수는 모델에 효율적으로 사용될 수 있게 한다. 강화학습이 진행 되는 과정은 간략히 두 과정으로 나뉘는데 샘플링을 통해 에피소드들을 모으고 모여진 에피소드들을 기반으로 Q 값과 정책값을 업데이트 시키는 것이다. 강화학습이 이러한 샘플링 기법이기 때문에 발생하는 한 가지 문제점이 있는데 바로 차원의 저주(curse of dimensionality)이다. 일반적으로 상태 공간의 크기가 커지면 커질수록 Q 값이 수렴하는데 더 많은 에피소드들을 필요로 하게 된다. 예를 들어 9*9 바둑 문제를 강화 학습을 통해서 풀려고 하면, 전체 상태 공간이 10^38 정도로 어마어마하게 큰 공간에서 샘플링을 해야 한다. 따라서 수렴속도가 현저하게 떨어지게 된다.
이러한 문제를 해결하기 위해서 함수 추정 기법을 사용하게 되는 것이다. 현재 상태를 잘 표현해 줄 수 있는 특징(feature)들을 추출하고 이 특징에 대한 Q 함수를 학습시키게 된다. 이런 방식을 취하는 이유는 일반화 효과를 이용하려는 것이다. 샘플링이 많이 되지 않은 지역일지라도 Q 함수의 일반화가 잘 되어있다면, 처음 마주 하는 상황에서도 정확한 Q 값을 예측 할 수 있을 것이다.
이렇게 특징을 이용하는 것은 문제를 기술하는 표현(representation)을 변경하는 것이다. 다시 9*9 바둑의 예를 들면, 고전적인 강화 학습 기법을 이용하기 위해서는 바둑판의 가능한 모든 경우의 수에 대해서 Q 값을 찾아야 한다. 10^38개의 상태가 존재 하고 각 상태에서 취할 수 있는 행동까지 고려한다면, 어마어마하게 많은 Q 값을 찾아 내야 하는 것이다. 그러나 만약, 우리가 바둑 판을 몇 가지 중요한 특징을 이용하여 나타내면 적은 샘플로 여러 상태의 Q 값을 추론 할 수 있게 된다. 예를 들어 바둑판을 보고 현재 상대방의 집 수와 자신의 집수, 혹은 ‘패’가 가능한지, ‘축’이 가능한지의 여부로 현재의 바둑판을 나타낸다고 해보자. 이러한 특징들을 바둑판으로부터 추출하면, 처음보는 수, 처음보는 바둑판일 지라도 비슷한 특징을 갖고 있다면 현재 상태가 좋은지 나쁜지, 어떤 행동을 해야 하는지를 추론 할 수 있게 된다.
Q 함수를 특징을 이용한 함수 추정 기법으로 학습시키기 위해서는 수식 상 약간의 재정의가 필요하다. 기존의 강화학습에서 사용되었던 업데이트 식을 다시 한번 살펴보면 아래와 같다.
위 수식에서 오른쪽 항을 타겟값(target value)이라고 한다. 함수 추정 기법을 이용하지 않은 일반적인 강화 학습에서는 모든 상태와 행동 쌍에 대하여 이 타겟값을 업데이트하면 되지만, 함수 추정 기법을 이용하면 우리가 업데이트해야 할 것이 함수의 파라미터로 바뀌게 된다. 기존의 모든 상태와 행동에 대해 정의 됐던 Q 함수를 아래와 같이 근사 하는 것이다.
이렇게 Q 값을 추정 하게 되면, 가보지 못한 상태(state) 라고 해도 비슷한 특징 점을 갖는 상태라면 Q 값을 추론 할 수 있다는 장점이 있다. Q 네트워크를 업데이트하는 방식은 다음과 같은 손실(loss)을 최소화 하는 파라미터를 찾는 것이다.
이 손실 함수의 의미는 새로운 타겟값에 가장 가까운 예측을 하는 파라미터를 찾는 것이다. Q 를 추론하는 네트워크를 디자인 하는 방법은 여러 가지가 있는데 가장 많이 사용하는 것은 [그림 6]의 세 번째 방식이다. 뉴럴네트워크의 입력은 상태(state)가 되는 것이고, 출력은 각각의 행동을 취했을 때 얻을 수 있는 Q 값을 유추 한다. 참고로 알파고 에서는 첫 번째 형태의 네트워크가 사용되었다.
그림 6. Q함수의 파라미터(parameter)를 찾는 방식이러한 형태의 디자인을 위해서는 한 가지 조건이 필요한데 바로 취할 수 있는 행동의 개수가 유한해야 한다는 것이다. 예를들어 바둑 게임은 경우의 수가 많긴 하지만 행동의 최대 개수는 19*19로 제한 되어있다. 반면에, 자율 주행을 하는 자동차를 학습시키는 문제의 경우에는, 엑셀을 어느 정도 밟을지, 핸들을 어느 각도로 틀지와 같이 연속적인 값을 갖기 때문에 유한한 행동으로 표현하기 힘들다. 이렇게 연속적인 행동 공간에서 deep Q learning을 적용하기 위해서는 연속공간을 이산화(discretization) 해야 한다. 하지만 연속적인 행동공간을 이산화 시키지 않아도 적용 할 수 있는 방법이 있는데 이것이 바로 policy gradient과 actor critic 모델이다.
Double DQN 과 듀얼 네트워크(dueling network)
DQN이 네이쳐(Nature)지에 실린 이후에 많은 연구자들이 deep Q learning을 연구하기 시작했다. 첫 번째 소개할 방식은 학습방식과 네트워크 구조에 관한 것이다. DQN을 학습 시키다보면 네트워크 성능이 불안정하게 증가하는 것을 볼 수 있다. 과하게 좋은 Q 값을 주어서 네트워크가 더 이상 성능 향상을 하지 못하는 경우가 발생한다. 이런 현상들은 딥러닝 방법을 도입하기 이전 부터 발생하던 현상으로, 일반적인 함수 추정을 이용해도 주로 나타나는 현상이었다.
이 현상을 막기 위해서 등장한 기법이 double DQN이다. 이름에서도 알 수 있듯이, double DQN은 두개의 네트워크로 구성되어 있다. 이 두 개의 네트워크를 이용하여서 안정적이고 정확한 Q 값을 학습을 할수 있다. 두 개의 네트워크 중 한 네트워크는 빠르게 업데이트하면서 에피소드를 만들어 내는 역할을 하고 다른 네트워크는 상대적으로 느리게 업데이트 하면서 어느 한 행동의 Q 값을 과도하게 커지지 않도록 해준다. 또한, 기존의 DQN에 비해 Q 값이 천천히 변하기 때문에 훨씬 안정적인 학습이 가능하다. Double DQN과 DQN의 차이는 타겟값을 구하는 방식에 있다. 아래와 함수가 Double DQN의 학습에 사용된다.
위의 수식에서 ɵ- 와 ɵ 는 double DQN에 있는 두 네트워크의 파라미터를 의미한다. 하나는 느리게 업데이트 되는 네트워크를 의미하고, 다른 하나는 빠르게 업데이트 되는 네트워크를 의미한다. 먼저 ɵ- 를 업데이트 하는 방식은 간단한데, 일정한 반복횟수 마다 업데이트를 실시해 주게 된다. 이와 같은 방식으로 타겟값을 구한다는 것은 현재까지 추정된 Q 값 중 가장 좋은 행동을 고르고 이 행동에 대한 타겟값을 구할 때는 기존 업데이트된 파라미터를 추정된 Q값에 이용하는 것이다. 기존의 방식에서는 항상 Q의 최댓값을 이용하여 업데이트가 진행되었기 때문에 한 번 잘못 Q값을 추정하기 시작하면 그 에러가 계속해서 커지는 형태였다면, double DQN에서는 네트워크 파라미터가 천천히 업데이트되기 때문에 에러의 전파가 빠르지 않고 안정적인 학습이 가능해진다.
두 번째로 소개할 방식은 듀얼 네트워크(dueling network) 방식이다. [그림 7]과 같은 새로운 DQN 구조를 제안했다. Q 값의 정의로부터 유도되는 한 가지 수식에서 아이디어를 얻은 새로운 DQN구조를 가지고 있다.
Q 값의 의미는 현재 상태에서 행동을 취할 때 얻을 수 있는 보상의 합을 의미한다. 이 값을 두 가지로 분리해서 생각해보면 밸류(V)와 어드벤티지(A)가 된다. V 값이 의미하는 것은 현재 상태에서 최선의 행동을 취했을 때 얻을 수 있는 보상의 합이다. 그리고 A는 최선인 행동과 다른 행동들 사이의 보상의 차를 의미한다.
듀얼 네트워크는 기존의 Q 값을 V와 A로 나누어서 예측하는 [그림 7]과 같은 구조를 제시하였다. 이러한 구조를 제시하는 이유는 간단한 직관으로부터 나왔다고한다. Q 값을 추론하는 것을 두 가지로 분리해서 생각한 것인데, 현재 상태가 좋은지 나쁜지를 V 값으로 추론하고 그 중에서 어떤 행동을 고를지를 A 값을 이용하여 추론하였다. 즉, V 값은 바이어스 같은 역할을 하고 V를 중심으로 좋고 나쁨을 A 값을 이용하여 추론 하게 되는 것이다.
그림 7. 듀얼 네트워크 구조 (dueling network) [4] 글 | 최성준 : sungjoon.choi@cpslab.snu.ac.kr
서울대 전기 컴퓨터 공학부를 졸업하고, 동 대학원에서 박사 과정 중에 있다. 학부 때는 리눅스 커널을 열심히 팠었고, 회사에서 청소 로봇을 만들기도 하다가, 대학원에 와서는 기계학습과 로보틱스를 결합하는 연구를 진행하고 있다. 주로 연구하는 분야는 강화 학습과 모방 학습으로 비슷한 분야의 연구자들을 항상 찾고 있다. 박사 졸업이 가까워짐에 따라 페북에 자주 출몰하며 최근 들어 그 정점을 찍고 있으며 현재는 미국의 한 회사에서 인턴을 하고 있다.
글 | 이경재 : kyungjae.lee@cpslab.snu.ac.kr
서울대 전기 컴퓨터 공학부를 졸업한 뒤, 동 대학원 석박사 통합과정으로 입학하였다. 현재는 박사과정에 있으며, 주 연구 분야는 모방학습과 지능형 로보틱스이다. 좀 더 세부적으로는 역 강화 학습을 연구하고 있다. 나름 재미있는 분야라고 생각해서 시작했는데 한국에서는 비슷한 연구를 하는 연구자를 만나기 어려운 것 같아 아쉽다. 관심 있는 사람이나 이 연구를 하고 있는 사람과의 만남이라면 언제든 환영이다. 한동안 군대 문제를 해결하기 위해 연구를 접고 영어공부에 매진했으나 영어실력은 그대로라고 한다. 최근 다시 연구를 시작하였으며 인공지능 및 로보틱스 분야의 많은 사람들과 교류하고 싶다.
참고문헌
[1] 논문 | Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., and Petersen, S. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.
[2] 논문 | Van Hasselt, Hado, Arthur Guez, and David Silver. "Deep Reinforcement Learning with Double Q-Learning." AAAI. 2016.
[3] 논문 | Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484-489.
[4] 논문 | Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot, Nando de Freitas: Dueling Network Architectures for Deep Reinforcement Learning. ICML 2016: 1995-2003
