Blackbox HPO(1): Grid search와 Random search

이 글은

* Automated Machine Learning(2019; Hutter F., Kotthoff L., Vanschoren J., Springer) *

을 참조하여 작성되었습니다.

 

또한,

그림은 제가 직접 작성하였음을 알려드립니다.

---

 

안녕하세요 :)

이번 글에서는 Blackbox Hyperparameter Optimization에 대해 정리하고자 합니다. 우선 포스팅에서 다루는 모든 방법론을 아우르는 개념인 Blackbox Optimization이 무엇인지 간략히 살펴보고, 몇 가지 방법론에 대해 알아보도록 할게요.

 

1. Blackbox Optimization

 

그림1. 블랙박스 모델

 

Blackbox 모델은 입출력 값이 아닌 모델 내부의 인과관계와 같은 구조를 명확히 알 수 없는 모델을 의미합니다. 때문에 모델을 통해 도출된 출력 값이 발생한 이유를 알기가 어렵습니다. 대표적으로 인공신경망을 예로 들 수 있습니다. 이에 따라, 여기서 말하는 blackbox optimization은 blackbox 모델을 활용한 최적화 방법론이라고 간단히 표현할 수 있겠네요.

 

HPO 문제에는 모든 blackbox optimization 방법론이 적용될 수 있습니다. 방법론을 통과했을 때, 왜 그런 결과가 나왔는지 알면 좋겠지만, 어찌 되었든 결과적으로 최적 값의 도출이 우선적으로 진행되어야 하기 때문에 blackbox 모델이 적용되는 게 허용됩니다.

 

모델 여부에 따라 방법론을 구분할 수 있는데요, 여기서는 model-free의 방법론 몇가지와 Bayesian 모델 기반의 방법론을 중심으로 다루고자 합니다.

 

---

2. 모델 없는(model-free) Blackbox Optimization 방법론

 

HPO에 적용되는 기본적인 model-free blackbox optimization 방법론은 Grid search와 Random search가 손꼽힙니다. 이 방법들은 모델이 존재하지 않기 때문에 초기에 설정된 파라미터(Grid search의 경우 검색 구간, random search의 경우 random seed)에 따라 해당 경우에 발생한 결과값을 중 가장 좋은 값을 최적 값으로 결정하게 됩니다.

 

(1) Grid search

 

Grid search는 특정 구간마다 탐색이 발생하게 됩니다. 예를 들어, 구간이 5로 결정되었을 때, hyperparameter가 5, 10, 15, ... 일 경우의 결과값을 바탕으로 최적해를 선택하게 됩니다. 즉, 최적 hyperparameter는 {5, 10, 15, ...; 5의 배수}의 집합에서 존재하게 됩니다.

 

이 방법의 가장 큰 맹점은 차원의 저주(curse of dimensionality)가 발생할 수 밖에 없다는 것입니다. 1개의 hyperparameter를 결정해야 한다면, 큰 문제는 없습니다. 하지만, 검색해야 할 hyperparameter의 수가 많아질수록, 검색하는 횟수가 exponential 하게 증가합니다. 결국 다수의 hyperparameter 중 최적해를 찾기 위해서는 오랜 시간이 걸릴 수밖에 없는 구조를 가집니다.

 

또 다른 문제는 구간마다 탐색을 수행하기 때문에 광역 최적해(global optimum)를 찾기 어렵다는 점입니다. 만약 설정된 구간 내, 위의 예시에서는 3 혹은 17이 최적해라고 할 때, grid search를 통해 최적해를 찾을 수 있을까요? 당연히 5, 10, 15, 20, ..의 값만 탐색을 하니 찾을 수 없겠죠. 이 경우 결정된 최적해의 경우 지역 최적해(local optimum)이 되는 것이죠.

 

(2) Random search

 

Random search는 간단히 grid search를 대체할 수 있는 다른 방법론입니다. 이 방법론은 말 그대로 무작위로 hyperparameter를 선택하여 그에 대한 결과를 만들고, 그중 가장 좋은 값을 도출한 hyperparameter를 최적해로 봅니다. 무작위 함수를 수식으로 표현하기 위해 활용되는 파라미터는 random seed 하나로, 이 값만 설정되어 있다면 확인해 볼 hyperparameter를 결정할 수 있습니다.

 

이 방법론은 한정된 비용(=탐색 횟수) 안에서 유용한 방법입니다. 정해진 횟수만큼만 무작위 값을 도출 및 결과 탐색을 발생시키면 되기 때문이죠. 이는 결국 grid search의 가장 큰 문제 중 하나였던 차원의 저주에서 벗어날 수 있게 합니다.

 

Random search는 탐색 초기에 유용하게 활용될 수 있습니다. 하지만, 최적해를 찾는데는 적합하지 않습니다. Random search는 무작위로 결과를 뽑는다는 점에서 샘플링과 연결 지을 수 있습니다. Random search를 통해 도출된 결과값은 표본으로서 활용되어, 목표를 달성하기 위한 힌트로서 활용될 수 있습니다. 그러나 무작위로 값을 선택하기 때문에, 도출된 값이 최적인지 아닌지 판단할 수 있는 방법이 없습니다. 그래서 문제에 대한 아무런 힌트가 없는 초기에 활용하는 것이 유용합니다.

 

(+) Population-based methods(개체군 기반 최적화)

 

대표적인 population 기반의 방법론은 1) 유전자 알고리즘(GA, genetic algorithms), 2) evolutionary algorithm, 3) evolutionary strategies, 4) particle swarm optimization(PSO)가 있습니다. 이 방법론들은 교차(crossover)와 변이(mutation)를 통해 최적해를 찾아가게 됩니다.

 

그림2 교차(Crossover)

 

교차는 population들이 일부를 서로 교환하는 방식으로 진행됩니다. 교차를 통해 새로운 population을 만들어내면서 최적값을 찾아가는 것이죠. 하지만, 이런 교차를 통해서 얻을 수 있는 population은 초기의 population의 구성에 의존할 수 밖에 없습니다. 다시 말해 구성 변화의 범주가 고정되어 있어 완전히 새로운 구성의 population을 얻는데 한계가 발생합니다.

 

그림3 변이(Muation)

 

이와 같은 문제를 해결하기 위해 변이를 활용합니다. 여기서 변이는 생물학에서 배운 돌연변이와 동일한 개념입니다. 일반적으로 변이는 확률적으로 발생하며 population의 일부가 무작위로 변환되는 방식을 통해 수행됩니다. 결국 이러한 진화 방식을 통해 환경에 더 잘 적응하는 값(=최적해)을 얻고자 하는 것이죠.

 

---

 

여기서 살펴본 Blackbox Hyperparameter Optimization 방법론은 model-free입니다. 다음 글에서는 가장 대표적인 HPO 방법인 Bayesian 기반의 최적화 방법론에 대해 살펴보겠습니다.

 

감사합니다.