Saturday, December 30, 2017

논문 요약 - Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning

Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning


관련 링크; 

해커뉴스 1면에도 실리고, 나름대로 이슈가 된 논문입니다. 학계에서 Deep RL의 인기에 대해 회의적인 시각이 제법 있는데 그런 사람들의 가려운데를 벅벅 긁어준 논문입니다.

이 논문은 크게보면 3가지 최적화 방법을 비교합니다. 우선 Gradient-based algorithm입니다. 보통 딥뉴럴넷은 backprop으로 현재 θ에서 비용함수loss function의 gradient(경사)를 구하고 그걸 이용해 gradient descent(경사하강법)을 수행하여 네트워크의 파라미터 θ를 갱신합니다. Evolution strategy(ES, 진화전략, 진화알고리즘)와 Genetic algorithm(GA, 유전 알고리즘)은 θ의 재조합, 돌연변이 등을 이용해 다음 세대의 θ를 만들고 이를 평가하는 방식입니다. 최근 딥러닝 기반의 강화학습이 학계에서 대세인데, 이 논문은 GA로도 Deep RL만큼 성능이 나오며 + 왜 그런지 + 어떤 면에서 장단점이 있는지를 소개합니다.

일단 저는 강화학습 알못, GA알못, ES알못임을 밝히는 바입니다. 이 논문이 굉장히 잘 쓴 논문이라 다행이네요.

Abstract

보통 딥뉴럴넷 학습은 그라디언트를 이용한다. 한편 ES는 Q-learning이나 정책 그라디언트망을 대체할수(도)있는 방법인데 사실 ES도 finite-difference를 이용해 파라미터를 갱신한다는 점에서 그라디언트를 근사하는 방법이라고 볼수있다. 이 논문은 GA의 가능성을 보고 이것저것 해봤다. 또 파라미터 스페이스에서 탐색이 안된 부분을 주로 찾아보는 Novelty search (NS)를 썼더니 reward를 극대화하는 DQN, A3C, ES, (일반적인) GA가 잘 안되는 문제에서도 잘 된다. 그리고 Deep GA는 병렬화가 쉽다는 장점이 있다. 

1. Introduction

첫 문단 생략.
둘째 문단: "While the GA always outperforms random,..": 일단 항상 GA>랜덤서치였는데, 랜덤서치가 DQN, A3C, ES를 이기는 결과도 일부 나왔다. (뒤에서 더 자세히 논함)
셋째 문단: GA로 학습한 네트워크는 파라미터를 아주 효율적으로 저장할 수 있다. 
넷째 문단 생략.

2. Background

각종 강화학습 논문을 소개합니다. 역시 생략합니다. 초록에서 이야기한대로 ES는 그라디언트 기반인 셈이라고 다시한번 강조하네요.

3. Methods

3.1 Genetic Algorithm

우선, 여기에서 사용한 GA는 리소스 등 몇가지 이유로 단순한 방법과 단순한 문제만 풉니다. 따라서 하이퍼파라미터 서치를 빡시게 하면 분명 더 성능이 잘나올거라고 이야기합니다. (뒤에서도 이 얘기는 반복합니다.)

이제 사용한 유전 알고리즘 정리. N개의 개체로 이루어진 전체 인구 P를 진화시키는 방법입니다. 이 논문에서는 뉴럴넷 파라미터 θ셋 하나가 개체 하나에 해당합니다. 개체의 재생산, 즉 다음 세대의 생산은...

  - 상위 T개의 부모 후보를 선정하고, 
  - 이 그룹에서 최종적으로 k개의 부모를 고른 뒤, 
  - 각 부모 개체에 정규분포 노이즈를 더합니다 (θ'=θ+노이즈) (이 과정이 돌연변이에 해당). 
  - 그리고 이들의 성능/능력 (뉴럴넷에서는 loss_function(θ))을 평가한 뒤 제일 좋은 개체 N개를 골라서 더이상 변화 없이 그대로 사용합니다 (이를 elitism, 엘리트주의라고 부르네요).

이 과정을 잘 보면 제안하는 파라미터 압축방법을 이해할 수 있습니다. 최종 파라미터셋 θ_final은 θ_initial + sum_i(noise_i)입니다. θ_initial 역시 (정규)분포를 샘플링한것이죠. 즉, 랜덤 추출값 [θ_initial,  [noise_0, noise_1, ... noise_i]]를 알면 θ_final을 알 수 있습니다. 그런데 랜덤 추출값은 굳이 값을 저장할 필요가 없고, seed만 기억하고 있으면 되죠 (!)즉, θ와 noise대신 정수로 된 seed만 저장하는 방식으로 파라미터를 압축할 수 있습니다.

그동안 Q-learning, 정책 그라디언트대신 ES를 쓰자는 논문에서는 보통 분산 학습덕분에 효율이 좋다는걸 강조했는데 Deep GA는 ES보다도 더 빠릅니다. 그 이유는 두가지입니다.
  (1) ES는 각 세대마다 (즉, 각 θ 업데이트마다) θ의 갱신 방향 θ_delta을 결정하기 위해 수많은 θ_delta를 임의로 만들고 (=pseudo-offspring수 만큼), 이에 대해 전부 적합도/성능 (=loss function)을 계산한 뒤 이 적합도를 가중치로 사용하는 θ의 가중평균을 구합니다. 가중평균 연산이 아주 느리구요. Deep GA는 이 과정이 필요없습니다. (주: k=len(θ)=적어도 수십만, 많으면 수백만 이상, 전체 인구 n=10k 라고 해보면 가중 평균을 구하는 과정은 n * (O(k) 곱셉 + O(k) 덧셈) = O(nk)입니다.  Deep GA는 전체 인구수만큼 이 계산을 반복하지만 추가적인 연산이 없고 정렬만 하면 되므로 O(n log n)입니다. k가 log(n)보다 훨씬 크겠네요.)
  (2) ES는 batch normalization 비슷한걸 수행하는데 GA는 이런걸 안하고 단순히 랜덤 노이즈만 더하면 충분하다고 합니다. 이건 제가 ES알못이라 넘어갑니다.

3.2 Novelty search

DNN학습에 GA를 쓰면 GA에서 사용하는 노벨티 서치(참신성 탐색, NS)를 바로 갖다 쓸 수 있는 장점이 있습니다. NS는 참신한 행동(=탐색이 덜 된 파라미터 공간)을 적극 권장하는데 이 결과로 로컬 옵티마를 잘 탈출할 수 있습니다. 반면 단순히 성능(reward)를 추구하는 모델은 로컬 최적값을 벗어나기 힘듭니다. (주. 따라서 로컬 옵티마가 치명적인 문제라면 NS덕분에 Deep GA가 성능이 잘나오겠죠?)

NS와 behaviour characteristic, distance function등을 소개하는 다음문단은 생략합니다.


4. Experiments

4.1 Atari

일단, 연산량 문제로 아타리 게임중 일부를 골랐습니다. ES가 잘하는것/못하는것 골고루 섞었구요. (주: 그 외에도 제안하는 방법에 치우치지 않도록 여러모로 신경을 잘 썼네요.)

표1에 나와있는데, 기본적인 GA가 DQN, A3C, ES랑 비슷한 성능이 나옵니다. 

"Because performance did not plateu in the GA rusn, ..): 제안한 GA의 성능이 계속 올라가고 있었지만 무한히 기다릴순 없어서 실험을 종료한 결과입니다. 기다리면 더 잘나올수 있었다는 얘기죠. (주. 소위 "step size"가 항상 일정해서 그런걸까요? 흠..)

특이하게도, GA는 초반 성능 상승 속도가 엄청 빠릅니다. 많은 경우에 무려 약 1-10번째 세대에서 DQN 최종값보다 더 좋은 성능이 나옵니다! 여기서 드는 두가지 생각.
  - 랜덤 초기값에서 그리 멀지 않은 곳에 이미 괜찮은 파라미터벡터가 존재한다는 이야기죠. 
  - Q.그럼 랜덤 서치를 해도 혹시 GA만큼 잘 나오는거 아냐?

A. 아님 (표 1 참조). 그러나 4/13에서 랜덤서치가 DQN보다 잘나옵니다. (주: 랜덤서치를 정확히 어디에서 설명했는지 모르겠는데, GA에서 부모를 고를때 성능에 관계없이 무작위로 고르는거라고 짐작합니다만 그러면 성능이 왜 오르는건지 알수가 없군요. 혹시 아시는분!) 심지어 리워드 딜레이가 아주 심한, 즉 행동을 아주 많이 수행한 뒤에야 리워드를 계산하는 게임에서도 랜덤서치가 잘 되네요. 심지어 랜덤서치 1시간짜리가 DQN 7-10일 학습한것보다 성능이 잘 나왔습니다. 다른 seed로 랜덤서치를 여러번 해봐도 그렇다고 하니 운빨이 아니구요. (주: 이 부분은 더이상 자세한 설명이 없네요.)

이 결과를 보면 아타리 게임을 배우는게 Deep RL같이 복잡한 방법을 써야할만큼 어려운 문제가 아닌가 하는 생각이 듭니다. 그리고 그라디언트 하강법이 아니라 현재 파라미터 주변을 빡시게 탐색하는게 혹시 더 좋은거 아닌가 하는 의심이 들죠. 이는 섹션6에서 다시 이야기합니다. (주: 그런데, 대략 파라미터 변화하는 노이즈의 크기가 step size * gradient 크기랑 대충 비슷하다고 하면 그라디언트 방법은 gradient_f(θ)를 계산해서 이걸 최소화하는 방향을 결정하는거고, GA는 f(θ + 노이즈)를 전부 구해보는거니까 사실상 비슷한거아닌지. 그러면 GA는 다양한 스텝사이즈를 테스트해본다는 의미로 수렴하는건지? 하는 궁금증이 듭니다. 세대의 크기는 모델 앙상블 비슷한 효과같구요.)

4.2 Humanoid Locomotion

- 잘 나옵니다.
- 별 discussion은 없네요.


4.3 Image Hard Maze

한마디로 미로찾기입니다. 픽셀을 보고 에이전트가 길을 찾는게 목표입니다.

미로찾기를 하다보면 출구를 향해 거의 다 간것같은데 갑자기 막히는 경우가 있죠 (=deception). 알고리즘도 같은 문제가 발생합니다. 이는 비용함수가 로컬옵티멈에 빠진걸로 볼 수 있는데, 이를 벗어나야 하므로 GA-NS가 성능이 잘 나온것으로 보입니다. 같은 이유로 ES-NS도 성능이 잘 나왔습니다. 반면 평범한 ES, GA는 로컬옵티멈에서 빠져나오지 못합니다.

그림 4 아래에서는 ES<GA인 이유를 ES가 리워드의 '평균'을 내기때문이라고 이야기하네요. 즉 평균 리워드를 극대화하다보니 옵티멈 탈출에 실패하는 것이라는 이야기입니다.

DQN, A2C 역시 노벨티 서치가 부족해서 미로탈출에 실패합니다.


5. Compact network encoding

앞에서 말했듯이 random seed만 기억하면 됩니다. 끝.

6. Discussion

두번째 문단 빼고는 대체로 다 이야기된 내용이에요. 근데 제가 이 문단을 잘 이해를 못했습니다. 


----------

여기까지입니다. 제가 놓치거나 모르겠다고 한 부분 알려주시면 매우 감사드리겠습니다 :)


No comments:

Post a Comment