Softmax와 UCB 알고리즘의 결합을 통한 성능 개선 연구-베이지안 확률론을 이용하여-
A Study on Performance Improvement with Combination of Softmax and UCB Algorithm -Using Bayesian Statistics-
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
대형 웹사이트에서 아이디어를 대조군과 비교 실험하기 위한 방법으로 A/B테스트가 주목받고 있다. 일반적인 A/B테스트는 테스트할 모든 버전에 사용자들을 동일하게 할당하여 진행한다. 그러나 테스트 도중의 결과가 매우 안 좋은 버전이라 하더라도, 여전히 다른 버전과 균등하게 사용자들을 할당받는다. 이는 실험기간이 길어질수록 기회비용이 커지는 것을 의미한다. 이러한 문제를 해결하기 위해 제기된 것이 Multi-Armed Bandit 문제다. A/B테스트의 기회비용 문제와 관련되어 있는, Multi-Armed Bandit의 탐색과 활용의 딜레마를 풀기 위한 대표적인 알고리즘으로 UCB 알고리즘이 있다. 하지만 시행횟수가 제한되고 많은 버전을 테스트해야 하는 상황에서 UCB 알고리즘은 비효율적인 시행이 발생하여 만족스럽지 못한 결과를 낼 가능성이 높다. 이러한 문제를 해결하기 위해 본 논문에서는 Multi-Armed Bandit 알고리즘 중 하나인 Softmax 알고리즘에서 베이지안 확률론을 이용하여 우수한 버전을 선출한 뒤, UCB 알고리즘으로 전환하는 Softmax/UCB 알고리즘을 제시한다.
Abstract
A / B testing is getting attention as a way to compare ideas on large web sites. A common A / B test is performed by equally assigning users to all versions to be tested. However, even if the results of some versions are very bad, the same number of users will be allocated during testing. To solve this problem, the Multi-Armed Bandit issue was raised. The UCB algorithm is a representative algorithm for solving the dilemma of exploration and utilization of MAB, which is related to the opportunity cost problem of A / B test. However, in a situation where the number of trials is limited and many versions have to be tested, the UCB algorithm is likely to produce unsatisfactory results due to inefficient trial. To solve this problem, in this thesis, I propose a Softmax/UCB algorithm that selects a superior version using the Bayesian statistics in the Softmax algorithm step and then switches to the UCB algorithm step.
참고문헌 (4)
- John Myles White, "Bandit Algorithms for Website Optimiztion" (2014), O'REILLY
- Volodymyr Kuleshov, "Algorithms for the multi-armed bandit problem", Journal of Machine Learning Research, 1 (2000)
- Earman, John, "Bayes or bust? A critical examination of Bayesian confirmation theory" (1992)
- "수학백과"[URL]