[study] Thompson Sampling

• 의사결정의 딜레마: 탐색과 활용의 균형 

-  요즘 시대의 급변하는 환경 속 , 기업과 연구자들은 데이터 기반 의사결정을 통해 최적의 선택을 내리기 위해 고군분투 하고 있습니다. 특히 여러 옵션 중 하나를 선택할 때 발생하는 탐색(Exploration) 과 활용(Exploitation) 사이의 균형문제는 매우 중요한 과제로 대두됨

 

[Ex]

활용의 숫자가 늘어나면 탐색의 숫자가 줄어들고 활용의 숫자가 줄어들면 탐색의 숫자가 늘어남

 

- 어떠한 예로 온라인 광고 캠페인을 진행한다고 할 때, 이미 검증된 광고에 계속 투자하는 '활용' 전략은 안정적인 결과를 보장하지만, 동시에 새로운 광고 형식이나 창의적인 아이디어를 시도라는 '탐색'의 기회를 놓칠 위험이 있음, 반대로 , 모든 자원을 새로운 시도에만 투자하면 과거의 성공 사례에서 얻을 수 있는 안정적인 이익을 포기할 수밖에 없습니다.

 

이처럼, 단순히 과거의 성과만을 따르거나 모든 가능성을 무작정 시도하는 방식은 장기적인 성공을 보장하지 않습니다. 적절한 균형을 유지하는 것이 핵심이며, 이를 통해 리소스의 효율적 배분과 함께 잠재적인 성장 기회를 극대화할 수 있습니다.

 

이러한 딜레마를 해결하기 위해 제안된 접근법 중 하나가 바로 톰슨 샘플링 입니다.

 

 

• Thonpson Sampling

• 톰슨 샘플링 이란? 

- 톰슨 샘플링은 탐색과 활용 문제를 효과적으로 해결하기 위한 확률론적 접근법입니다. 이 알고리즘은 각 옵션의 성공 확률을 베이지안 업데이트 방식으로 추정하며, 이를 바탕으로 매 순간 최적의 선택을 합니다.

 

 

• 사전지식 

- 베이지안 확률(Bayesian Probability) 

: 베이지안 확률은 사전확률(prior)을 기반으로, 새로운 데이터를 관측할 때마다 이를 업데이트 하여 사후 확률(posterior)을 도출하는 접근 방식 입니다.

이 과정을 통해, 불확실한 상황에서도 점진적으로 확신을 높여갈 수 있습니다.

출처:https://bioinformaticsandme.tistory.com/47

- 확률 분포 및 베타 분포 

: 확률 분포는 어떤 사건이 발생할 가능성을 수치적으로 표현하는 도구임, 이론적으로 여러 형태가 있지만 톰슨 샘플링에서는 선택지의 성공률을 나타내는데 사용됩니다.

 베타 분포는 

이진 성공/실패 문제에서 많이 두 매개변수 α와 β에 따라 [0,1] 구간에서 정의되는 연속 확률 분포들의 가족임, 특히 이진 문제에 많이 사용되는데 0과1 사이의 값을 가지며, 다양한 모양을 통해 불확실성을 효과적으로 표현할 수 있습니다. 

베타 분포의 여러 형태

-멀티암드 밴딧 문제 (Multi-Armed Bandit Problem)

: 멀티암드 밴딧 문제는 여러 개의 슬롯 머신(또는 선택지) 중에서 최대의 보상을 주는 옵션을 찾는 문제로, 탐색(새로운 옵션 시도)과 활용(현재 최고 옵션 활용) 사이의 균형이 핵심입니다.

 

 

• 톰슨 샘플링의 주요 개념 및 작동 원리

-톰슨 샘플링은 베이지안 접근 방식을 활용하여 탐색과 활요문제를 해결하는 알고리즘입니다. 여기서는 그 작동 원리를 단계별로 살펴 보겠습니다.

 

1.베이지안 확률 모델 업데이트 

Beta(1,1)은 균등한 초기 상태를, Beta(5,1)은 성공 데이터를 반영해 오른쪽으로 치우친 분포를, 그리고 Beta(1,5)는 실패 데이터를 반영해 왼쪽으로 치우친 분포를 보여줍니다.

-사전 확률 설정(prior): 알고리즘은 각 선택지에 대해 초기에 사전 확률 분포를 할당합니다. 예를 들어, 이진 성공/실패 문제에서는 베타 분포를 많이 사용합니다.

 

-데이터 관측 및 업데이트: 각 선택지를 시도한 후, 성공 혹은 실패와 같은 결과가 관측됩니다 . 이 데이터를 바탕으로 베이지안 업데이트가 진행되어, 각 선택지의 사후 확률(posterior)이 재계산됩니다.

 

2. 확률 분포 샘플링

 

-무작위 샘플링: 업데이트된 사후 확률 분포에서 무작위로 샘플링을 진행합니다. 이때, 각 옵션으로부터 하나씩 샘플을 뽑아, 가장 높은 값을 가진 옵션을 선택합니다.

==> 단순히 평균값이나 최빈값만 보는 것이 아니라, 분포 전체의 모양과 불확실 성을 함께 반영합니다.

 

3. 동적 의사결정 및 균형 유지

 

-탐색과 활용의 균형: 톰슨 샘플링은 불확실성이 큰 옵션에서도 무작위 샘플링을 통해 선택될 가능성을 남겨두므로, 새로운 옵션을 탐색할 여지를 제공합니다. 동시에, 지금까지의 데이터가 풍부한 옵션은 더 높은 확률로 선택되어 활용됩니다.

 

-환경 변화에 대한 적응: 데이터가 계속 업데이트됨에 따라, 알고리즘은 환경의 변화에 유연하게 반응할 수 있습니다. 초기에는 탐색을 많이 하다가, 데이터가 축적됨에 따라 점차 활용에 초점을 맞추게 됩니다.

 

 

• 정리

- 이러한 과정을 통해 톰슨 샘플링은 단순한 탐욕적 선택 방법보다 더 정교하게 의사 결정을 수행합니다. 베이지안 업데이트와 확률 분포 샘플링을 결합함으로써, 불확실성을 자연스럽게 반영하며 최적의 선택을 내릴 수 있게 됩니다.