채린's datascience

https://hoonst.github.io/2020/11/15/Algorithms-for-Hyperparameter-Optimization/

https://velog.io/@suminwooo/%EB%AA%A8%EB%8D%B8-%ED%8A%9C%EB%8B%9D1

https://hyunsitstory.tistory.com/entry/python-%ED%8C%A8%ED%82%A4%EC%A7%80-%EB%AA%A8%EB%93%88-%ED%95%A8%EC%88%98-%ED%81%B4%EB%9E%98%EC%8A%A4-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC

Bayesian Optimization 방법은 좋은 성능에 비해 느리다는 단점이 있다. 게다가 sequential하게 진행되는 거라 병렬처리도 어렵다.

이를 개선할 수 있는 방법으로 hyperband가 있으며 빠르며 좋은 성능을 보여준다. Hyperband는 Successive HAlving(SHA) 방법을 기반으로 한다.

1. SHA(Succesive HAlving Algorithm)

Bandit 기반의 하이퍼파라메터 최적화 기법이다. MAB(Multi Armed Bandit)문제를 해결하는데 두가지 방법이 있다. 

한가지는 가장 큰 보상을 찾는 팔을 찾는 법, 다른 하나는 Exploitation-Exploration trade-off를 해결하는 것이다. 

SHA는 전자인 Best Armed Identification에 기반을 두고 있다. 

SHA는 주오진 Budget안에서 hyperparamter 조합을 랜덤하게 선택하여 loss를 평가한다. budget을 늘려가면서 성능이 떨어지는 비율을 정해 hyperparameter조합을 제거해나가는 방법이다. 이 방법은 몇개의 hyperparamter로 시작하지, 어떤 구간에서 줄여나갈지를 정해줘야한다. 이를 개선한것이 hyperband알고리즘이다. 

2. hyperband 알고리즘

https://pod3275.github.io/paper/2019/05/23/Hyperband.html

https://simpling.tistory.com/52

https://repositorio.pucrs.br/dspace/bitstream/10923/15244/2/Bandit_Based_Automated_Machine_Learning.pdf

Hyperparamter optimization

학습을 수행하기 전 hyperparameter설정을 하는데 이때 최적값을 탐색하는 문제해결법을 지칭한다. 

방법으로는 Manual, Grid, Random Search와 Bayesian optimization이 있다. 

1. Manual Search

일반적으로 하이퍼파라메터 탐색시 잘 알려진 노하우를 기반하여 hyperparameter를 설정하고 검증데이터셋(validation set)의 측정 결과를 성능으로 기록한다.

여러 시도 중 가장 높은 성능을 준 하이퍼파라메터를 선택했을 것이고 이런 방법을 Manual Search라고 한다. 

단점은 찾은 최적의 hyperparameter 값이 ‘실제로도’ 최적이라는 사실을 보장하기가 상대적으로 어렵다는 단점이 있고 또한, 여러 종류의 hyperparameter를 탐색할때 서로간의 상호영향관계를 나타내는 파라메터들도 존재하기 때문에 둘 ㅣ상의 파라메터를 탐색시 직관을 이용하기 어렵고 문제가 더욱 복잡해질 수 있는 단점이 있다. 

2. Grid Search

특정 구간 내의 후보 hyperparameter 값의 일정한 interval을 두고 이들 각각에 대하여 측정한 성능 결과를 기록한 뒤, 가장 높은 성능을 발휘했던 hyperparameter 값을 선정하는 방법이다. 

모든 경우의 수에 대해 평가 결과가 가장 좋은 hyperparameter세트를 찾는 방법이다. 

전역적인 탐색이 가능하다는 장점이 있지만, hyperparameter개수를 여러종류 가져가면 시간이 기하급수적으로 증가하는 단점이 있다. 

3. Random Search

탐색 대상 구간 내의 후보 hyperparameter 값들을 랜덤 샘플링(sampling)을 통해 선정한다는 점이 다릅니다.

탐색 대상 구간 내 후보 hyperparameter 값들을 랜덤 샘플링해서 선정하는 방법이다.

Grid Search에 비해 불필요한 반복 수행 횟수를 대폭 줄이면서, 동시에 정해진 간격(grid) 사이에 위치한 값들에 대해 동일한 확률로 탐색이 가능하며 최적의 hyperparameter 값을 더 빨리 찾는 장점이 있다. 

랜덤하게 선택하여 학습한 뒤 가장 좋은 parameter를 고를 수 있지만 여전히 불필요한 탐색을 반복하기도 한다. 

왜냐하면 다음에 시도할 hyperparameter 값을 선정하는데 이전 정보를 반영하지 않기 때문이다. 이를 개선한 것으로 전체적인 탐색을 가능하게 하며 사전지식까지 반영할 수 있는 Bayesian Optimization이 있다. 

4. Bayesian Optimization 

입력값 x 를 받은 목적함수 f(x)를 만들어 f(x)를 최대로 만드는 최적해를 찾는 것을 목적으로 한다. 

목적함수와 하이퍼파라메터 쌍을 대상으로 대체 모델을 만들고 하이퍼파라메터를 업데이트 해가면서 최적의 조합을 탐색한다. 

필요한 요소

- surrogate model은 여러 (x, f(x))로 확률적인 추정을 수행하는 모델이 필요하다. 

-  Acquisition Function은 확률적 추정 결과를 바탕으로 최적 입력값을 찾는데 있어 가장 유용할만한 다음 입력값을 추천해주는 함수이다. 

Expected Improvement(EI)는 Exploitation과 Exploration을 둘다 일정수준 포함하도록 설계한 것이고 이떄 많이 쓰이는게 Acquisition function이다. 

출처: https://wooono.tistory.com/102

[Feast] Feast(Feature Store)란? + Feast 사용법 — Dev study (tistory.com)

제한된 시간내에 최소의 loss를 갖는 모델의 hyperparameter를 찾는것이 목표다. 

홈 - Jay's Blog (otzslayer.github.io)

Multi-Armed Bandit algorithm은 굉장히 Profitable한 모델이며 이해하기가 쉽다. 

카지노 게임장에서 가장 유리한 슬롯을 찾는것부터 시작됐으며, Arm은 슬롯에 잡아당기는 부분, Bandit(노상강도)는 슬롯, 그리고 여러개의 슬롯중 최적의 효율을 내는 것을 탐색하기 위해 Multi-Armed Bandit이 탄생했다. 

1. greedy: 한번씩 플레이후, 가장 많이 돈을 딴 슬롯머신에 모두 투자한다. 

문제: 탐험(Exploration)이 충분히 이루어지지 않음

2. e-greedy(입실론 그리디): 동전을 던져서 윗면이 나오면 점수 좋았던 슬롯머신, 뒷면 나오면 랜덤선택

동전의 확률은 50:50이다. 50%의 확률로 greedy알고리즘에서 가장 좋았던 슬롯머신을 선택하고, 50%확률로 동전 뒷면이 나오면 슬롯과 상관없이 랜덤하게 골라서 한다. 여기서, 입실론이 하이퍼파라메터이다. 

3. UCB(Upper-Confidence-Bound): 좋은 수익률을 보이며 최적의 선택이 될 가능성이 있는 슬롯머신을 선택

기존에 greedy알고리즘과 비교하면, 빨간 박스가 추가되었다. 해당 슬롯머신이 최적의 슬롯머신이 될 수 있는 가능성이다. 

출처: 멀티 암드 밴딧(Multi-Armed Bandits) (brunch.co.kr)