Reinforcement Learning/Multi-Armed Bandits8 Contextual Bandits - LinUCB 금번 포스팅을 시작하면서 multi-armed bandit 포스팅의 초반부를 상기시켜보겠습니다. Bandit을 크게 stochastic, non-stochastic으로 분류했고, 그 다음 분류는 context-free, context로 분류했습니다. 지금까지 살펴본 ε-greedy, UCB, Thompson Sampling의 알고리즘은 context-free에 해당하는 방법이었습니다. 즉 action을 선택하기 앞서 주어진 환경을 전혀 고려하지 않고 매시도 독립적으로 의사결정을 해왔습니다. 이번 포스팅에서는 context를 고려하는 contextual bandits, 그 중에서도 가장 유명한 Li, Lihong, et al., 2010의 LinUCB를 살펴보겠습니다. 어떠한 형태의 co-work도 환영합.. 2021. 1. 30. Bayesian Bandits - Thompson Sampling 이번 포스팅은 Bayesian Bandits을 살펴보려고 합니다. 특히 Bayesian Bandits 중 대표적인 알고리즘인 Thompson Sampling을 부제로 선정했습니다. :) On The View of Bayesian Frequentist는 확률을 상대빈도의 관점으로 바라보지만, Bayesian은 확률을 어떤 사건에 대한 믿음의 정도로 해석합니다. 동전을 던져서 앞면이 나올 확률에 대해서 Frequentist는 "10000번 던지면 앞면이 5000번 나온다."고 해석하는 것이고, Bayesian은 "경험에 의하면 앞면이 나온다고 50% 믿는다."라고 해석합니다. Prior vs. Posterior Probability? 위 예시에서 Bayesian의 멘트 중 "경험에 의하면"이라는 문구가 있습.. 2021. 1. 14. Stochastic Bandits (3) - UCB (Upper Confidence Bound) 이번 포스팅은 Stochastic Bandits 그리고 Frequentists 관점의 연속입니다. 직전 포스팅에서는 reward의 확률 분포를 Point Estimation하는 관점에서 살펴보았고, 대응하는 알고리즘으로는 ε-greedy를 살펴보았습니다. 이번 포스팅에서는 Interval Estimation하는 관점의 algorithm인 Upper Confidence Bound Algorithm (UCB Algorithm)이 메인입니다. Point Estimation vs. Interval Estimation Frequentist의 확률 철학은 많은 시도를 반복했을때 사건이 발생한 상대빈도를 의미한다고 했습니다. 이러한 상대빈도를 추청하는 방식에는 크게 두가지 방식이 있는데, Point Estimatio.. 2021. 1. 3. Stochastic Bandits (2) - ε-greedy 이전 포스팅에서 Stochastic Bandits에 대한 개요를 다루었습니다. 짧게 Reward에 확률 분포를 가정하는 MAB라고 요약 할 수 있습니다. 이번 포스팅에서는 Reward의 확률 분포를 Frequentist의 관점에서 point estimation하는 방법을 다루려고 합니다. 대표적인 알고리즘은 ε-greedy이고, 부제로 선정했습니다. :) On The View of Frequentist Frequentist, Bayesian의 구분은 확률을 해석하는 철학적인 차이입니다. Frequentist는 확률을 상대빈도의 관점으로 바라보며, 이는 많은 시도를 했을때 사건(Event)이 발생한 상대빈도로 확률을 정의합니다. 반면 Bayesian은 확률을 어떤 사건(Event)에 대한 믿음의 정도를 정.. 2020. 12. 18. Stochastic Bandits (1) - Introduction Introduction to Multi-armed Bandit (1), (2)에서 MAB가 무엇이고, 목적은 어떤 것인지에 대해 살펴보았습니다. 본격적으로 MAB를 푸는 Algorithm을 소개하려고합니다. Algorithm의 첫 주제로는 Stochastic Bandits이란 이름으로 Multi-Armed Bandits의 중간 session을 열었습니다. 시작하겠습니다. 이번 포스팅에서는 Stochastic Bandits이란 무엇이고, Stochastic Bandits이라는 큰 틀 안에서 최적의 arm을 찾기 위해 approach에 대한 scketch를 한 후, 이어질 포스팅에서 UCB, Thompson Sampling, linUCB 등 저명한 알고리즘을 다루겠습니다. Formulation MAB는 ar.. 2020. 12. 9. Introduction to Multi-Armed Bandits (2) 직전 포스팅에서 MAB 개요 중, MAB, Exploration-Exploiation Trade-off, Application Example등을 살펴보았습니다. 이번 포스팅에서는 본격적으로 MAB Algorithm을 다루기 앞서 (1) 제 블로그를 읽어가기 위한 notation에 대한 framework을 제시하고, (2) 앞으로 다루게될 MAB Algorithm와 대응하는 branches를 제시해보고자 합니다. Glossaries and Notation of MAB 앞으로 다룰 MAB 문제를 풀기위한 알고리즘 설명을 위한 용어와 수식 notation을 정리해보겠습니다. 행동의 주체를 Bandit, Player, Agent라고 합니다. 이 Player는 매 라운드별 행동을 선택합니다. 이때 라운드는 rou.. 2020. 12. 2. Introduction to Multi-Armed Bandits (1) 오늘 포스팅을 시작으로 Multi-Armed Bandits (MAB)에 대하여 차근차근 정리하고자 합니다. 며칠전 예고(?)와 같이 제가 느끼기엔 MAB에 대하여 스토리가 있게 체계적으로 풀어가는 글들을 찾기가 어려웠고, 작게나마 MAB를 recommendation에 적용하길 고민하고 계시는 분들과 연구를 목적으로 기본적인 틀을 잡을 수 있는데 도움이 되길 바랍니다 :) Multi-Armed Bandit? 먼저 MAB란 무엇일까요? 단어를 두덩이로 쪼개서 보면, "multi-armed" + "bandit"으로 살펴볼 수 있습니다. 직역하면 "팔이 많은 강도"라는 뜻입니다. 어떤 팔이 많은 강도가 슬롯머신 $K$개 위에 팔을 모두 올려놨습니다. 그런데 이 강도는 팔이 많지만, 한 번에 딱 하나의 팔을 선택.. 2020. 12. 1. Multi-Armed Bandits 곧 추천시스템(Recommendation System)에서 활용가능한 관점의 Multi-Armed Bandits에 관한 포스팅이 하나둘 써내려갈 예정입니다. 많은 관심부탁드립니다. 많은 분들이 공감하시겠지만, $\epsilon$-greedy, UCB (Upper Confidence Bound), TS (Thompson Sampling)등 토막토막의 MAB관련된 글들은 영문이든, 국문이든 구글에서 쉽게 찾아볼 수 있지만, MAB의 큰틀을 제시해줄 수 있는 문서가 부족합니다. 앞으로 이어질 포스팅 하나하나를 연결하고 큰 밑그림을 그려가는 작업이 순탄하지는 않았고, 부족한 점이 많을 것으로 생각됩니다. 그럼에도 불구하고 많은 피드백을 주시면 정말 감사하겠습니다. ㅎㅎ 곧 찾아뵙겠습니다. 감사합니다:) yjjo.. 2020. 11. 26. 이전 1 다음
