알파고 알고리즘

알파고에 대해 찾으면 가장 많이 나오는 단어 중 하나는 아마도 인공지능 일껍니다. 그리고 그에 대해 좀더 검색해보면 다음 세 단어를 가장 많이 접하게 될꺼에요.

Monte Carlo tree search
Deep learning
Reinforcement learning

이 세 단어를 중심으로 알파고가 어떻게 작동하는지 정리해보도록 하겠습니다.

1. Monte Carlo tree search

몬테 카를로는 도박으로 유명한 모나코의 한 도시라고 합니다. 흔히 random sampling을 반복하는 방식일 때 Monte Carlo라는 말을 붙이는거 같아요. 몬테 카를로 트리 검색이라는 방법은 알파고 알고리즘을 통해 처음 접하게 된 단어입니다.

신경망의 깊이가 깊어지면 학습시켜야 하는 신경망들도 많아지겠지요. 제가 신경망을 처음 배운 2000년도 초반 즈음만 해도 이 계산이 불가능해서 신경망 층이 겨우 한개인 shallow neural network이였습니다. 그런데 어느샌가 하드웨어 기술도, 수학 기술도 점점 발달해서 지금은 여러 층으로 이루어진 deep neural network이 나왔습니다. 알파고의 경우 13개의 층을 가졌다고 하고요. 아마 이 많은 신경망들을 학습시킬 데이터 (빅데이터)도 충분히 있었기에 가능한 것일껍니다.

여튼 KGB라

계산량을 어떻게 줄일 수 있을까요. 트리 사이즈가 커지는 이유는 아마 두 가지 입니다. width가 넓고, depth가 깊기 때문에. 그래서 알파고는 인간 바둑 전문가가 만든 3000만 기보를 이용하여 width와 depth를 줄이는 방법을 제안합니다. width의 경우 인간이라면 결코 두지 않을 수를 삭제해버려요. 이 '인간이라면 결코 두지 않을 경우의 수'를 학습하는데 deep convolutional neural network이라는 방법을 이용합니다.

artificial neural network는 1943년인가 인간의 뇌 속에 신경망, 특히 visual system 쪽의 신경망을 모방한 수학 모델입니다. 인간이 물체를 보면 (눈을 통해 물체가 입력되면) 여러 층으로 구성된 신경세포들을 거치면서 색->형태->깊이->방향 이런 식으로 물체의 특징(feature)을 인식하게 된다고 합니다. 이렇게 인식된 종합하고 기억을 더듬어 그 물체는 무엇무엇이다 하고 출력을 내보내는거지요. 이 과정을 모방해서 신경세포를 노드로 생각하고 각 특징들을 인식하는 노드의 층을 여러겹 쌓아 오른쪽 그림과 같이 인공신경망을 만듭니다 (그림 출처 http://www.rsipvision.com/exploring-deep-learning/). 처음 학습이 안된 상태에서 이 인공신경망에 입력을 넣어봤자 그 입력값이 무엇을 뜻하는지 출력하지 못합니다. 많은 데이터들을 이용하여 이 신경망이 잘못 출력을 할 때마다 에러를 고치도록 다시 학습시켜야 합니다. 이 과정을 training이라고 부르고 그 기술을 backpropagation이라고 부릅니다.

2. Deep learning

(출처 : https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)

wikipedia를 찾아보니 위와 같은 예제와 함께 설명이 나옵니다. 현재 상태 (s)에 가장 왼쪽과 같은 트리가 주어져있다고 가정합니다. 현재 상태가 맨 상단의 노드 (루트)에 있고, 선택할 수 있는 다음 상태가 트리로 주어져있습니다. 그리고 트리의 각 노드엔 그 노드를 선택할 경우 승률이 표기되어 있습니다. 현재 루트에서 선택할 수 있는 노드는 3개이고, 각 노드의 승률은 0.7 (7/10), 0.5 (4/8), 0 (0/3)으로 주어져 있습니다. 이 때 승률이 가장 높은 노드를 선택하는게 좋겠지요. 그래서 7/10으로 표기된 노드를 선택합니다. 다음에는 역시 승률이 높은 5/6이 표기된 노드를 선택하게 됩니다. 그 다음은 역시 3/3으로 승률이 높은 노드 선택. 트리가 주어져 있고 각 노드에 대한 승률을 알 수 있다면, 이와 같은 방식으로 승률이 높은 쪽을 선택함으로써 이길 확률을 높힐 수 있을 것입니다 (selection step).

하지만 여기까지 와보니 더이상 선택할 수 있는 경우의 수가 계산되어 있지 않습니다. 그럼 트리를 확장합니다 (expansion step). 그리고 그 방향으로 확장할 경우 승률을 끝까지 계산해봐요 (simulation step). 시뮬레이션 결과 0:1로 '패'한다고 나왔다면, 그에 대한 결과를 다시 루트쪽으로 업데이트 해갑니다 (backpropagation step). 3/3이 3/4로, 5/6이 5/7로, 7/10이 7/11로, 11/21이 11/22로 바뀌겠지요. 이를 통해 이쪽 방향으로 가면 지는 경우의 수 하나가 업데이트 된 것입니다. 이와 같이 몬테 카를로 트리 서치는 이와 같이 selection, expansion, simulation, backpropagation을 계속 반복해가며 승률이 가장 높은 경우의 수를 선택할 수 있게 해주는 방법입니다.

이를 바둑에 적용해보면 오른쪽 그림과 같습니다. 맨처음 흑돌이 주어지고 (state) 다음에 백돌을 두면 (action) 다음 상태가 되는데 이 때 백돌을 놓을 수 있는 경우의 수가 이미 흑돌이 놓였던 곳 이외의 모든 자리가 될 것이고, 그 가능성 만큼 트리의 넓이 (width)가 넓어질 것입니다. 그리고 백돌이 놓인 자리에 따라 다음 흑돌이 놓일 경우의 수가 결정이 되겠지요.

체스 챔피온을 이긴 인공지능 딥블루도 몬테 카를로 트리 검색 방법으로 작동을 했다고 합니다. 하지만 체스의 경우 바둑판보다 경우의 수가 적기 때문에 각 자리에 대한 승률을 계산할 수 있었다고 해요. 하지만 바둑의 경우 경우의 수가 1.74 곱하기 10의 172승. 우주에 존재하는 원자수가 대략 10의 80승으로 추정된다고 하니 우주의 원자수보다 더 많은 경우의 수가 존재하는 거라고 하네요. 계산이 불가능하다고. 그래서 알파고는 이 계산량을 줄이기 위한 알고리즘을 추가합니다.

이런 식으로 바둑전문가들이 만들어놓은 기보를 이용하여 일단 알파고를 학습시켰습니다. 이렇게 학습된 알파고도 바둑을 어느 정도 두었다고 하는데 승률을 잊어먹었습니다. 바둑의 역사가 2000년이라지만 분명 인간이 만든 기보엔 그에 따른 편견이 들어있을 수 있지 않을까 합니다. 그래서 알파고는 알파고와의 대결을 통해 편견을 깰만한 데이터를 재생산합니다. 이 때는 알파고 스스로 다른 알파고가 두는 상황에 따라 이기기 위해 바둑을 두어야 겠지요. 이와 같이 주어진 환경에 의해 피드백을 주고 받으며 작동하는 기계학습 알고리즘을 강화학습 (reinforcement learning)이라고 합니다. 저도 잘은 모르지만 알고리즘을 보면서 이자율 따라 적금 계산하는거랑 비슷하다는 인상을 받았었습니다. 여튼 reinforcement learning을 기반으로 알파고 끼리 대결을 벌인 후 습득된 데이터를 이용하여 다시 인공신경망을 학습하는데 위의 방식은 트리의 넓이를 줄이기 위해 사용하는거고요. 결과적으로 다음에 둘 최적의 장소는 오른쪽 그림과 같이 승률이 가장 높아지는 곳을 학습하여 결정하게 됩니다.

뭔가 설명이 용두사미가 된거 같....

참고문헌 : David Silver, et. al., ‘Mastering the game of Go with deep neural networks and tree search’ Nature 2016.

3. Reinforcement learning

는 곳에 등록된 3000만건의 기보를 이용하여 인간이 보통 이런 상태에서 두는 다음 수를 학습시켰다고 합니다. 이를 통해 만약 현재 바둑판 상태 (s)가 오른쪽 그림의 맨 아래와 같을 때 가능한 다음 액션 (a)이 맨위의 그림처럼 확률로 나오게 됩니다. 확률이 높은 몇 곳을 추려내어 몬테 카를로 트리의 넓이를 확 줄여버립니다. depth도 마찬가지로 줄이게 되는데요. 이 때는 속도가 중요하므로 depth로 승률을 계산하는건 1층 정도의 단순한 neural network를 썼다고 합니다.

Page updated

Google Sites

Report abuse