brunch

라이킷 55 댓글 8

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by Justin Lee Mar 11. 2016

AlphaGo에 적용된 딥러닝 알고리즘 분석

AlphaGo와 딥러닝 그리고 강화학습

AlphaGo에 적용된 딥러닝에 대해 조금 상세하게 적어보고자 한다.

AlphaGo의 전체 알고리즘이 궁금하신 분들은 내가 작성한 'AlphaGo 알고리즘 요약' 슬라이드를 참고하시기 바란다. 이 슬라이드를 먼저 읽는 것이 본 글 이해에 도움이 된다.

(슬라이드와 이 글은 모두 AlphaGo의 Nature 논문 "Mastering the game of Go with deep neural networks and tree search"을 분석한 내용임)

http://www.slideshare.net/zenithon/alphago

AlphaGo 알고리즘 요약

Google DeepMind의 AlphaGo가 작동하는 알고리즘을 간략하게 요약했습니다. 주로 기존의 자료 중 설명이 빈약했던 Reinforcement Learning에 대한 설명

www.slideshare.net

AlphaGo 알고리즘의 전체 골격을 이루는 Monte Carlo tree search(이하 MCTS)는 대부분의 바둑 AI 또는 각종 보드 게임 AI에 보편적으로 사용하는 알고리즘이다. 한마디로 특별하지 않다.

그 대신 AlphaGo는 tree search를 높은 승률로 제한된 시간 내 탐색하기 위해 딥러닝(deep learning)과 강화학습(reinforcement learning) 알고리즘을 사용했다.

AlphaGo에서 사용된 딥러닝 알고리즘은 Convolutional Neural Networks(이하 ConvNet)이다. ConvNet은 이미지 인식(recognition) 등에 가장 대표적으로 사용되고 있으며, 매년 ILSVRC 등을 통해 인식 정확도가 개선되고 있다.

AlphaGo는 KGS의 2천9백만 기보를 ConvNet으로 학습하여, P(a|s) 즉, 어떤 상태(status, s)에서의 다음 수를 둘 위치(action, a) 확률 분포를 구해낸다. 어찌보면 정석의 패턴을 익히는 것이라고 볼 수 있다. 이것을 SL policy network이라고 부른다. (논문에서 지은 이름)

즉, 사람의 기보에서 배운 가능성을 최대화하는 방향으로 학습한다.

maximize likelihood of human action

혼동하지 말아야할 점은 ConvNet에 학습할 기보 이미지를 그냥 입력하는 것이 아니라 기보를 한 지점 당 11가지 특징(이하 feature)을 갖는 데이터로 변환하여 넣는다. 11가지 특징은 해당 지점의 돌 색깔(내 돌, 상대방 돌, 빈 곳 등) 등 인데 이 11가지 feature를 표현하는 차원은 총 48차원이다.

11가지 feature 상세 내역

그래서 19 X 19 X 48 차원의 행렬(tensor) 데이터가 ConvNet으로 입력되어 학습된다. 그런데 이를 그대로 입력하지 않고 값이 0인 행렬을 높이, 넓이 4만큼 덧붙여(zero padding) 23 X 23 X 48 행렬로 최종 입력 데이터로 변환하여 넣는다. 그 다음은 일반적인 ConvNet 아키텍처에 따라 학습(training)을 시킨다. 학습의 목적 함수는 P(a|s)이다.

ConvNet 아키텍처 (SL policy network)

그리고 5 X 5 X 48 컨볼루션(convolution) 필터(kernel) 192개를 먹인다.

그러면 19 X 19 X 192 feature map이 나오고 여기에 2만큼 zero padding을 해서 21 X 21 X 192로 바꾼 다음, 3 X 3 X 192 필터 192개를 또 먹인다. 이런 과정을 2 ~ 12 레이어까지 반복한다. 이는 ConvNet의 Feed foward 방식이다.

컨볼루션 연산 예시

이런 SL policy network에 기보를 얼마나 학습시켰나 보면... KGS 6~9단의 160,000 경기로 부터 29,400,000 위치 정보를 뽑아서 학습했다. 이는 한 경기당 약 184가지의 바둑 돌의 위치 정보를 뽑은 셈이다. 이것이 정확히 첫 수 부터 184수까지 인지 아니면 184가지 모양을 뽑은 것인지는 알 수 없다. (즉, 논문에서 언급이 없음)

어쨌든, 첫 번째 ConvNet으로 AlphaGo가 학습하고자 한 것은 최대한 사람의 기보에 따른 현재 상태에서의 다음 수를 둘 위치이다.

또한 주목할 점은 policy network의 작은 정확도 개선이라도 AlphaGo 전체 승률 개선에 많은 영향을 미친다고 한다.

SL policy network 정확도 개선에 따른 AlphaGo 승률

SL policy network를 조금 더 개선하고자 기 학습된 SL policy network(ConvNet)을 복사해서 이를 강화학습(reinforcement learning)한다. 이렇게 추가적으로 학습된 ConvNet을 RL policy network라고 부른다.(논문에서 지은 이름)

RL policy network은 승리하면 +1, 패배하면 -1의 reward score를 부여하는 강화학습을 하는데, P(a|s) 확률을 구하도록 학습한다. 보통 강화학습에서는 현재 상태(s)와 행동(a)에 따라 최대 미래 reward를 주는 'value 함수'를 근사하는데, 여기서는 'policy gradient 강화학습' 방식으로 직접 P(a|s)를 구한다. 즉, policy gradient 알고리즘을 사용한 이유는 policy network가 value 함수가 아닌 확률을 구하는 목적이기 때문이다.

reward score(z_t)의 기대값이 최대화되는 방향으로 학습한다.

maximize expected outcome

그렇다면, 승리여부에 따라 reward를 준다는데 누구랑 승부를 겨룰까? 바로 또 다른 policy network이다. 즉, AlphaGo 자신과 self-play하는 것이다.

이렇게 학습된 RL policy network이 SL policy network과 싸워서 80% 더 승리한다고 한다!

착점을 찾는 policy network 다음, 해당 착점에 따른 승률을 예측하는 이른바 value network를 학습한다.

value network는 앞서 policy network(ConvNet)의 아키텍처와 동일하고 마지막 층만 확률이 아닌 예측 값을 구하도록 바꾼다.

그 다음 실제 reward score(z)와 value network의 예측 값 사이의 mean squared error(MSE)를 최소화하는 방향으로 학습한다.

minimize MSE

이미 완료된 게임( KSG 기보)으로 value network을 학습시키면 과적합(overfitting)이 발생하는데, 이는 하나의 돌 위치에 따라 이후 위치들이 강하게 연관되어있는 반면, 최종 예측값은 게임 내 전체에서 하나의 값으로 공유되기 때문이다. 즉, 돌 하나의 위치가 승부에 어떤 영향을 미치는지 학습하기 어렵다.

결국, value network는 새로운 착점을 생성한다기 보다 단지 KSG 기보 결과를 기억하는 역할만 하게 된다.

이 문제를 해결하기 위해 RL policy network끼리 self-play를 통해 자체 기보를 생성하고 이 데이터(약3천만 착점)로 value network를 학습시켜서 과적합 문제를 해결한다.