AutoML-Zero: 'zero' 에서부터 스스로 진화하는 기계학습 알고리즘 (2)

AutoML-Zero: Evolving Machine Learning Algorithms From Scratch

휴먼 개입을 최소화

Evolution Search를 통해 backprop까지 스스로 발견한 기계학습

---

AutoML-Zero 알고리즘 개요 >>

2020/03/13 - [AI] - AutoML-Zero: 'zero' 에서부터 스스로 진화하는 기계학습 알고리즘 (1)

AutoML-Zero: 'zero' 에서부터 스스로 진화하는 기계학습 알고리즘 (1)

---

실험 결과

다음의 세 가지 질문에 답하기 위한 실험을 진행함

- AutoML-Zero 공간을 탐색하는 것은 얼마나 어려운 일인가

- 이 프레임워크를 사용하면 사람의 개입을 최소화하고도 납득할만한 알고리즘을 찾을 수 있는가

- 다양한 태스크에 대해 각기 다른 알고리즘을 찾을 수 있는가

복잡한 공간에서 간단한 뉴럴 넷 찾기

이 실험은 랜덤 탐색으로는 주어진 탐색 공간을 커버하기가 어렵다는 것 보여준다. 하지만 진화 알고리즘을 사용했을 때에는 흥미로운 알고리즘들이 발견되었다. 태스크의 난이도를 조절하며 진화 알고리즘의 장점을 탐색해보자.

 

# 회귀분석 알고리즘 찾기

실험 디테일 :

8차원을 가지는 1000개의 훈련과 100개의 평가 데이터를 랜덤하게 생성함. 데이터는 feature 벡터 x_i와 스칼라인 라벨 L(x_i)를 가짐. L은 각각의 태스크에 대해서는 고정되어 있지만, 태스크간에는 달라짐.

  - affine 태스크에서 L(x_i) = uㆍx_i + a, u는 랜덤 벡터, a는 랜덤 스칼라.

  - linear 태스크에서는 a=0.

모든 랜덤한 수는 평균 0, 분산 1인 표준 정규분포에서 샘플링하여 사용. 평가는 RMS error을 사용하고, 정규화는 불필요하므로 Normalize()함수는 identity를 사용 

 

이 실험에서는 탐색 공간을 문제를 푸는 데에 필요하는데에 알려진 연산만 사용하도록 제약함. 예를 들어 선형 데이터에 대해서 Learn은 4개의 instruction만을 가지는데, SGD는 4개의 instruction만 필요하기 때문. 또한 알고리즘의 길이를 고정하기 위해 가능한 변이중 삽입/ 제거 액션을 제거하고, 모든 구성함수들을 랜덤하게 초기화함. 참고로 변이에 대한 제약 조건은 제약 없이는 랜덤 서치는 도저히 해법을 찾을 수 없기 때문에 이 실험에서만 추가한 조건임.

간단한 문제를 푸는 알고리즘

- 이마저도 예제를 단순화하는 제약을 주지 않으면 랜덤 서치는 해결책을 찾지 못했음

 

문제의 난이도 올려보기

- 태스크의 난이도는 랜덤 서치 실험을 아주 아주 많이 수행해보면서 측정함.

- 탐색 중 사람이 디자인한 회귀선이나 뉴럴넷 모델보다 좋은 알고리즘 (acceptable)을 찾은 회수를 센다.

- 실험한 랜덤 서치 횟수 중 acceptable의 비율을 RS success rate로 정의한다.

- 너무나 많은 실험이 필요하기 때문에 로그 스케일로 표기했고, 예를 들어 선형 회귀(Linear regressor)에 대해서는 10^7.4번의 랜덤 서치를 수행할 때 한 번 좋은 결과를 얻을 수 있었다.

- 이에 비해 같은 방식으로 진화 알고리즘의 success rate를 계산해 위의 그래프로 나타내 보았다.

- 회귀 분석과 같은 아주 간단한 케이스만 해도 진화 알고리즘은 5배 효율적이었고, 비선형성이 도입되는 순간 랜덤서치는 따라잡을 수 없을 만큼 갭이 커진 것을 볼 수 있다.

 

# 유전 알고리즘은 Ground Truch 네트워크를 복원할 수 있는가

좋은 솔루션이 존재한다는 것을 확실히 하기 위해서, regression task는 teacher NN을 사용해서 만들었고, evolution이 teature의 코드를 발견할 수 있는지도 실험해 보았다

실험 디테일 :

이제, 위 실험에서 사용했던 라벨링 함수는 teacher 네트워크로 사용됨:  L(x_i) = uㆍReLU(Wx_i) , W는 8x8 행렬, u는 랜덤 벡터. 훈련 데이터는 10만개로 늘림. 위의 실험과 같이 탐색 공간을 제한하였으나, 두 층의 FCN에서 사용되는 연산도 사용할 수 있도록 함. 탐색이 끝난 후 RMS loss가 가장 작은 알고리즘을 선택함. 탐색 공간에 대한 제약은 이번 실험까지만 적용

- 탐색 방법이 T_search에서 하나의 태스크만 사용하게 되면(D=1) 알고리즘은 티쳐 네트워크가 사용한 예측 함수로 정확하게 진화하고, 티쳐의 weight를 하드코딩함 (!)

- 탐색에서 태스크의 수를 늘리면 (예. D=100) 알고리즘은 태스크별로 다른 weight를 찾아야 하는데, 이 경우 진화 알고리즘은 forward pass를 찾아낼 뿐만 아니라, weight를 학습할 수 있는 backprop 코드를 발명함 (...???!!!!)

- 저자는 AutoML-Zero의 탐색 공간이 가능성 있고, 진화 알고리즘은 복잡한 태스크에 적합하다고 결론

- 찾아낸 backpropagation 코드 예시 :

<Figure 5>

사람의 개입을 최소화하여 실험하기

- 위의 실험처럼 티쳐 데이터셋을 두거나 연산을 사람이 선택하는 것은 알고 있는 알고리즘에게 호의적인 편향을 야기함

- 따라서 이번 섹션에서는 더 일반적인 옵션을 사용해서 실험해 봄

   : 다양한 연산들을 모두 활용할 수 있도록 하고, 현실적인 데이터에 대해 테스트하기 위해 CIFAR-10과 MNIST 클래스들로부터 추출한 2개 클래스에 대한 이진 분류 태스크로 실험

실험 디테일:

CIFAR-10과 MNIST 훈련 데이터로부터 태스크들을 추출함. 각각의 데이터는 10개 클래스에 대해 45개 쌍의 이진 분류 태스크를 구성할 수 있고, 각 태스크는 8000개의 훈련데이터와 2000개의 검증 데이터를 포함함. 이 중 36개 쌍을 랜덤하게 선택하여 T_search를 구성, 즉 9개의 쌍들은 T_select를 위해 남겨둠. CIFAR-10의 테스트 데이터는 최종 결과를 보이기 위해 남겨둠. feature의 차원은 8~256차원으로 축소하여 프록시 태스크를 구성함. 검증은 1<=D<=10개 태스크에 대해 수행. Setup, Predict, Learn 함수에서는 이제 각각 7 / 58 / 58개의 연산을 사용할 수 있음

이 실험의 전반적인 과정은 아래의 그림에 한 눈에 표시되어 있고, 이는 AutoML-zero를 가장 잘 보여주는 그림인 것 같음 

- 시작은 비어있는 알고리즘. 여기서부터 알고리즘은 스스로 진화해 나가고, 중요한 마일스톤들은 표기되어 있음

- 사람의 개입이 전혀 들어가지 않았는데도

   > Loss clipping, SGD, random learning rate와 같은 최적화 측면에서의 기교를 발견하고,

   > random weight initialization, multiplicative interection과 같은 기교를 발명해냈다는 사실은 정말 놀랍다!

   > 강화학습이 아타리게임의 트릭을 스스로 터득한 걸 봤을 때 느꼈던 놀라움이....

- 이러한 진화의 단계를 밟아가는 과정을 보면 진화 탐색이 랜덤서치보다 성능이 좋을 수밖에 없다는 것을 알 수 있다.

 

최종적으로 CIFAR-10의 테스트 셋에 대해 성능을 테스트해 보았을 때

- AutoML-Zero : 84.06%

- 선형 모델 (logistic regression) : 77.65%

- 2-layer FCN : 82.22%

사람이 디자인한 선형, 비선형 아키텍쳐의 베이스라인보다 AutoML-Zero의 성능이 좋았음.

 

다른 데이터셋에서도 선형 모델보다 성능이 훨씬 우수하고, 비선형 모델보다 우수함을 보임.

- SVHN : 88.12% vs 59.58% vs 85.14%

- ImageNet : 80.78% vs 76.44% vs 78.44%

- Fashin MNIST : 98.60% vs 97.90% vs 98.21%

 

현재 실험의 search space는 비교적 간단하여 딥러닝 SOTA에 기여한 batch normalization이나 convolution과 같은 연산을 조합해낼 수는 없다. 그럼에도 불구하고 진화 탐색을 거친 알고리즘은 몇몇 흥미로운 특성을 보였다. 특히 주목할만한 feature 네 가지를 발견해냈는데, ablation study를 해본 결과, 이 feature이 유용함을 증명할 수 있었다.

 

(1) input에 noise를 더하는 행동 - regularize 효과가 있을 것으로 추정함

     : input x에 대해 uniform 분포에서 추출한 랜덤 벡터u를 더하거나 빼는 방법을 찾아냄

(2) multiplicative interactions - bilinear한 형태로 상호작용을 모델링함

     : output = a^T W b 의 연산 수행

(3) weight W에 대한 그라디언트 g를 계산하고, 이를 단위 벡터로 정규화함(normalize)

(4) accumulated weight - 추론할 때 사용한 weight W'는 각 학습 스텝에서 만들어진 weight의 합을 사용함 

     : 이 방법은  averaged perceptron에서 가중치의 평균을 활용한 것과 아이디어가 유사한데, 이 알고리즘에서는 평균을 사용하는 대신 weight를 축적해서 사용함. 

 

결론적으로 AutoML-Zero framework는 밑바닥에서부터 진화하여 휴먼 디자인의 영역까지 발견해낼 수 있었다

(이런 디자인을 미리 발견한 사람의 직관이 대단한걸까 스스로 깨우친 기계가 대단한걸까 🙃)

알고리즘의 적응 능력

- 세 가지 다른 타입의 태스크로 확대해 탐색의 적용성을 실험해 봄. 

- 각각의 태스크는 각자 "어려운 점"이 있음 (예. 데이터가 너무 적다거나)

- 그 결과, 진화는 각각 태스크의 챌린지를 해결할 수 있는 방식으로 이루어진다는 것을 발견함

- 모델이 밑바닥부터 학습 가능하다는 것은 이전 실험에서 증명되었으므로, 이번 실험부터는 <Figure 5>을 시작점으로 삼음

 

훈련 데이터가 적은 경우

- 80개의 예시 데이터만 사용해 100epoch동안 반복

- 이 경우 알고리즘은 데이터에 노이즈를 주입하는 식으로 augment하는 방법을 터득

   > 이 방법은 noisy ReLU의 맥락과 유사하고 Dropout을 연상시키기도 한다.

- 이것이 우연한 행운으로 이루어진것은 아닌지 검증하기 위해 800개 예제를 100번 반복할 때와 비교해본 결과, noisy ReLU는 통계적으로 유의미하게 적은 데이터에 대해 자주 나타남을 확인함.

 

빠르게 학습하기

- 800개의 예제를 10epoch동안만 훈련한 결과, learning rate decay 를 반복적으로 선택함

- 반면 100epoch 훈련할 경우 decay 현상은 거의 발견되지 않음

 

멀티 클래스 분류

- 이번 실험에서는 CIFAR-10의 10개 클래스를 모두 분류하도록 훈련함

- 이 경우 weight matrit의 평균에 대한 변형을 learning rate로 사용했는데, 이 방법이 왜 멀티클래스에서 유용한지 파악하지는 목했지만, 이진 분류에서는 한 번도 발견되지 않았던 이 방법이 멀티 클래스에서는 통계적으로 유의미하게 선호됨

---

결론

본 논문에서는 "제한 사항을 최소화한 채 기본적인 연산에서 시작해 전체 머신러닝 알고리즘을 자동으로 발견하자"라는 AutoML에 대한 야심찬 목표를 세웠다. 탐색 공간에서 사람이 줄 수 있는 바이어스를 줄이고, 새로운 기계학습 개념을 발견하길 기대하였다. 그 시작점으로 이 논문에서는 기계 학습 알고리즘을 세 개의 함수로 구성하는 프레임워크를 세웠다. 비어있는 구성 함수에서 기본적인 수할 연산만을 사용하여 선형 회귀함수, 뉴럴넷, 경사하강법, 상호작용 모델링, 가중치 평균법, 그라디언트 정규화 등을 발견해낼 수 있었다. 이러한 연구 결과는 놀랍지만, 여전히 더 많은 연구가 이루어져야 한다. 

 

Search Method

- 이번 연구에서 초점을 맞춘 부분은 아니었지만, 향후 더 연구해야 할 분야이다

 

진화된 알고리즘 검증하기

- 새로운 태스크에 대해 만들어진 알고리즘을 검증하기 위해서는 하이퍼파라메터 튜닝이 필요하다

- 그러나, 자세히 조사해보지 않는 한, 변수들이 어떤 의미인지 우리는 모른다 (예. s7이 learning rate를 의미?)

- 프로그램에 있는 모든 상수들을 단순하게 튜닝하는 것은 충분하지가 않다. (hyperparameter coupling 현상)

- 지금은 상호 의존성이 있는 하이퍼파라메터를 수동으로 decoupling하고 코드를 디버깅해야 하지만, 이를 자동화하는 방법을 futuer work로 연구해야 한다.

 

알고리즘을 뜯어보는 꿀팁

- 만들어진 알고리즘에 대한 원본 코드는 복잡하기 때문에 이를 해석하기 위해 큰 노력이 필요하다. 
- 먼저 static 분석을 통해 중복되는 연산을 제거하여 코드를 정리한다.

- 다음으로 흥미로운 코드 스니펫들을 찾기 위해 독립적인 탐색 실험에서 반복적으로 등장하는 것을 찾는다. 이렇게 convergent evolution이 일어난다는 것은 해당 코드가 유익할 수 있다고 볼 수 있기 때문이다. 찾아낸 코드가 유익할 것이라는 가설을 증명하기 위해 ablations (knock-outs)과 knock-ins 실험을 했다. knock-in은 찾은 코드를 더 간단한 알고리즘에 삽입해보고, 거기서도 유용한지 보는 것이다. 이러한 기법은 복잡한 시스템을 다루어야 하는 자연과학이나 기계학습 분야에서 사용할 수 있는 분석 팁이다.

 

Architecture Search의 미래

- 탐색 공간을 강화하고 연구한 덕분에, 자동 아키텍쳐 서치분야의 연구는 크게 진전되었다.

- 2년만에 수백개의 GPU가 필요했던 NAS가 하나만 사용해도 되게 되었고

- 복잡한 디자인이 필요했던 것 NAS를 본 논문에서 AutoML-Zero으로 간결하게 만들었다.

- 이번 연구에서는 문제를 단순하게 하기 위해 한 번에 하나의 예제를 처리하는 실험을 진행하였다. 하지만 알고리즘에 루프를 추가하거나 더 높은 차원의 텐서를 추가하면 배치를 처리할 수도 있게 될 것이고, 그러면 batch-norm같은 흥미로운 현상을 발견하게 될지도 모른다.

- 함수 호출(function call)을 연산에 추가해 보는 것도 흥미로울 것 같다. 지금은 레이어 다음에 레이어를 쌓는 방식으로만 이루어져 있는데, 따라서 같은 레이어가 반복되더라도 이를 반복하는 수밖에 없다. 향후 함수 호출을 추가해 실험해보면 좀 더  깊은 구조를 찾아내게 될지도 모른다.