달고나 17. Exploration과 MAB
Algorithm. MAB for Exploration
기계학습 (Machine Learning)의 최대 장점은 배운 대로 잘한다는 점이다. 하지만 최대 단점은 배운 것만 잘한다는 점이다. 즉 학습 데이터가 커버하는 영역 내의 샘플은 잘 예측하는데, 영역 밖의 샘플은 보통 예측에서 많이 벗어난다. 학술 용어로 -- 학술 용어 같지 않지만 -- Explorarion-Exploitation Tradeoff라 한다. 영어 사전에서 Exploration과 Exploitation을 찾아보면 탐험, 탐색, 개척, 개발 등으로 거의 비슷하게 번역돼있고, 어떤 한글책에는 '탐험과 이용'이라고 표현한 것도 봤다. '탐험'은 맞는데 '이용'은 다소 부족한 느낌이다. 어쨌든 Exploitation (탐색?)은 우리가 알고 있는 영역 내를 샅샅이 훑어보는 조사라면, Exploration (탐험)은 미지의 영역을 찾아 나서는 탐험이다. 한번 탐험된 곳은 이제 탐색의 영역이 된다. 예를 들어, 불과 몇 세기 전만 하더라도 아프리카 대륙은 미지의 탐험의 대상이었지만, 이젠 탐색의 대상으로 바뀌었다. 하지만 깊은 바다인 심해나 태양계 밖의 우주는 여전히 탐험의 공간이다. 기계학습에서는 학습 데이터의 유무 (또는 데이터의 분포)로 탐색과 탐험의 경계가 정해진다.
예를 들어, 학습 데이터에서 X값이 0에서 10 사이에 고르게 분포돼있고 각 샘플마다 Y가 실수 값으로 정의돼있다고 가정하자. 이를 바탕으로 일반 선현 회귀 모델 Linear Regression을 구축해서 'Y = f(X) = 3 X + 5'라는 예측 모델을 만들었다고 가정하자. 그러면 X가 0일 때는 Y는 5가 되고, X가 10일 때는 Y는 35가 된다. 그리고 X가 0과 10 사이에서는 위의 식대로 Y값을 바로 예측할 수 있다. 그런데, 새로운 데이터 X = 11이 주어졌을 때, Y = 38로 추론 inference 하는 것이 맞느냐?라는 의문이 든다. 현재 모델은 0부터 10 사이의 X값으로만 예측해서 이 구간에서는 정확하게 예측하지만 10을 벗어난 구간에서는 전혀 본 적이 없기 때문에 Y = 38이라고 확신할 수 없다. 물론 관성에 따라서 Y = 38일 가능성이 매우 높다. 그렇다면 X = 20 또는 X = 100에서도 Y = f(X)가 그대로 유효할 것인가? 간혹 모델이 불연속적이고 급격히 출렁이기도 하겠지만 지엽적으로는 연속이고 거의 변화가 없다고 가정해도 큰 무리는 없다. 하지만 앞의 예와 같이 새로운 데이터가 지엽적이지 않을 때는 어떻게 할 것인가? 이전 글에서도 적었지만 기계학습 또는 예측모델은 학습 데이터를 잘 맞추는 것도 중요하지만 (training error), 이제껏 보지 못한 unseen 데이터를 정확하게 추론하는 것이 더 중요하다 (validation error, test error). 말장난처럼 들리겠지만 Unseen 데이터를 정확히 추론하기 위해서는 Seen 데이터로 만들어서 학습에 반영하면 된다. 이렇게 Seen 데이터로 만드는 과정을 Exploration이라 한다. 예를 들어, 정상적이 기계의 설정값이 [0 10]이었다면 일부러 설정값을 (가끔) -2나 15로 바꿔서 Y값을 실측하고 이를 학습 데이터로 활용하는 거다.
그런데 실제 환경에서 99% 이상은 X값이 0과 10 사이에 존재한다. 이 범위를 벗어난 값으로 설정하면 불량이 일어날 것이 뻔한데도 만일을 위해서 12나 13, 15로 임의로 설정값을 바꾸는 것이 합당한가? 에 대한 의문은 여전하다. 1% 미만, 또는 0.1%, 0.0001%의 가능성을 위해서 극한 실험 (일종의 스트레스 테스트)를 하는 게 맞을까? 사고는 항상 예측하지 못한 블랙스완에서 비롯되지만 미지의 영역을 너무 많이 의식하는 것 또한 크게 바람직하지는 않다. 그래서 대부분은 현재 허용치 내에서 최적화를 하고, 아주 가끔씩 미지의 영역을 탐험해보는 것이 바람직해 보인다. 즉, 탐색 Exploitation을 통해서 효율을 극대화하지만 가끔 탐험 비용을 사용해서 새로운 학습 데이터를 수집한다. 실제 (인터넷) 서비스에서 적게는 1%, 많게는 10% 정도의 트래픽을 랜덤 버킷으로 설정하는 이유이기도 하다. 특히 Cold-start 아이템은 노출 기회가 없어서 정보가 부족하고 또 정보가 부족해서 노출 기회를 얻지 못하는데, 랜덤 버킷 또는 랜덤 로직에 의해서 간헐적으로 노출 기회를 얻어서 데이터/정보를 수집하고 이를 바탕으로 상황에 맞게 최적화된 노출을 보장한다.
'적당히 탐험 기회를 준다' 또는 '적당 비율로 랜덤 버킷을 둔다'로 이 글을 마치면 욕먹기 딱 좋다. 얼마나 또 어떻게 탐험과 탐색을 나누는가는 다른 논문들을 참고하기 바란다. 욕먹더라도 크게 손해를 보지 않는 선에서 탐험을 허용한다 정도로 에둘러서 정리하는 게 맞을 듯하다. 대신 이 탐험-탐색 문제에서 가장 자주 등장하는 기법을 소개한다.
보통 MAB로 불리는 Multi-Armed Bandit이 이 탐험-탐색 문제에 가장 흔히 이용된다. Bandit은 흔히 파친코로 불리는 Slot Machine을 뜻한다. 요즘 라시 베가스 등의 카지노에 가면 그냥 버튼식이지만 예전에는 스롯머신에 레버 (Arm)이 하나씩 붙어있고 이를 당기면 기계식으로 작동했었다. 이를 single-armed bandit라 부르므로 MAB는 팔이 여럿인 슬롯머신이다. 팔이 여럿인 머신은 상상하기 어려우니 카지노에 SAB가 여러 대 있다고 생각하자. 지금 당장 해외여행은 어려우니 주말에 강원랜드에 놀러 갔다고 하자. 현재 코인이 1,000개 있고 잭팟이 터지면 10만큼 Reward를 받는다. 객장에 들어서니 잭팟 확률이 5%, 10%, 15%인 세 대의 슬롯머신이 있다. 이때 여러분이라면 어떤 전략을 취해서 Reward를 최대화하겠는가? 문제 같지도 않다. 당연히 C 머신에서 1,000번 모두 플레이해서 R=1,500을 받는 게 최선이다.
위의 문제는 당연히 비현실적이다. 카지노에서 잭팟 확률을 머신마다 공지하지 않기 때문이다. 뿐만 아니라, 해당 카지노에 처음 방문했다면 과거에 어떤 머신에서 잭팟이 얼마나 많이 터졌는지에 관한 정보가 전무하다. 이제 문제를 수정해서 고유의 잭팟 확률 (고객은 수치를 모름)을 갖는 3대의 머신 A, B, C가 있는 비밀의 방에 들어가서 1,000의 플레이 기회가 있다면 어떻게 하는 것이 최선인가?
전략은 여러 가지가 있다. 아무 거나 한대를 선택해서 1,000번 플레이하는 것도 방법이다. 운이 좋으면 15%인 C를 선택해서 R=1,500을 얻을 수 있지만, 운이 나쁘면 5%인 A를 택해서 R=500밖에 얻지 못한다. 다른 전략은 모든 머신에서 균등하게 333번씩 플레이하고 R=1,000을 얻는다. 전략 1은 확률의 확률 게임이 돼버렸고, 전략 2는 나쁘진 않지만 몇 시간 동안 노동했는데 결국 본전이다. 최대 (R=1,500)는 아니더라도 그래도 남는 장사 (이기는 게임)을 하고 싶다. 그래서 등장한 전략이 Exploration&Exploitation 전략이다.
E&E 전략의 핵심은 (가능한) 소수의 Exploration을 통해서 미지의 winning probability를 찾고, 남은 모든 기회를 가장 확률이 높은 머신에 All-in 하는, 즉 Exploitation 한다는 거다. 실제 적용에서 말처럼 쉽지만은 않다. 관건은 얼마나 빨리 정확한 확률을 찾느냐다. 최소한의 트라이로 확률을 찾아야지 Exploitation 할 기회가 많이 남기 때문이다. 그런데 확률 게임이 늘 그렇듯이 명확하지가 않다. 5/10/15%인 A, B, C 머신에서 각각 10회씩 플레이했는데, A에서 잭팟이 2번, B에서 1번, C에서 0번이 터졌다고 해서 나머지 970번을 A 머신에 올인하면 결과는 뻔하다. 그렇다고 정확한 확률을 얻겠다고 각각을 300회씩 플레이해서 16번, 29번, 43번의 잭팟 결과를 얻고 나서 나머지 100회를 C 머신에 투자하는 것은 Exploration을 너무 과도하게 적용해서 최종 Reward가 별로 크지 않다.
이제 절충해서 100회씩 플레이를 해서 6번, 11번, 13번이란 결과를 얻었다. 여기서 그냥 C가 가장 높기 때문에 나머지 700번을 C에 올인할 수도 있다. 아직도 조금 의심스럽다면 A는 아무래도 가장 낮아 보이니, B와 C에 100번씩을 더 플레이해서 9번, 16번의 잭팟 정보를 더 얻고, 남은 500번을 C에 올인하는 방법도 있다. 어쨌든 이렇게 조금씩 try 해보면서 정확한 확률 (또는 기댓값)을 찾아서 가장 가능성이 높은 쪽으로 몰아가는 것이 E&E 전략의 기본이다. 다소 단순하게 설명했는데, 실제 문제에서는 시스템마다 갖는 확률 분포를 가정해서 MAB를 적용한다. 보통의 경우 결괏값 (Y)은 잭팟 여부, 클릭 여부, 구매 여부 등과 같이 1 또는 0으로 표시된다. 그래서 Beta 분포를 가정해서 MAB (E&E)를 적용한 사례가 흔하다.
요약.
확실하면 Exploitation, 의심스러우면 점진적 Exploration.
