# Belief Propagation

Acyclic PGM 모델을 학습하여 MLE나 MAP를 수행하기 위한 알고리즘이다. Cyclic PGM의 경우 수렴성이 보장되지 않고, 계속 확률분포가 진동하지만, Acyclic한 경우 수렴성이 이론적으로 증명되었다고 한다.

어떤 임의의 parametric PGM모델을 Acyclic하게 만들고, 이것의 파라미터를 MLE나 MAP에 대해 최적화 하기 위해 각 그래프에서의 Node가 자기와 연결된 주변 Node로 Belief Propagation을 시키고, 이것들이 모여서 1번의 학습이 이뤄진다. 이러한 Belief Propagation을 계속해서 iteration하면서 학습을 수행하게 된다.


기본개념: https://en.wikipedia.org/wiki/Belief_propagation

by 곽동현 이스텔리앙 2018.01.05 22:50

# Multi-armed bandit(=K-armed bandit)
여기서 armed는 action이고, K는 action의 개수를 의미함.

- Multi-armed bandit = One-state MDP
one-state MDP란 것은 state가 1가지로, 항상 고정된 상태를 의미함. 즉 state가 변하지 않기 때문에 이는 곧 state를 무시한다는 말과 동일함. 한마디로 state가 없는 MDP임


# Contextual bandit(=Associative Search)
Multi-armed bandit에서 한발 나아가, context를 given condition으로 받아서 문제를 확장한것임. 이때 context는 state와 다른데, 원래의 MDP에서는 Transition probability에 의해 (s, a -> s', r')가 되는 반면, contextual bandit에서는 (context, a -> r')으로 a가 다음 context에 영향을 주지 않음.


# Thompson Sampling
톰슨 샘플링은 기본적인 Exploration-Exploitation 문제를 다루는 Contextual bandit 알고리즘 중 하나로, contextual bandit이기 때문에 추천시스템에서 매우 잘 사용되는 알고리즘이다. (보통 추천 시스템은 사용자의 profile등을 context로 놓고 톰슨 샘플링을 사용함)

대략적인 그 개념을 이해하자면, Bayesian Approach를 Multi-armed bandit에 적용하여,여 Reward 분포를 MAP estimation으로 찾아서 action을 수행하는 알고리즘이다.

- Likelihood = P(r | a, context, Θ)
ex) Bernoulli distribution

- Prior = P(Θ)
ex) Beta distribution

- Posterior ∝ P(r | a, context, Θ)*P(Θ)


말로 설명하자면, 현재 내가 가지고 있는 P(r | a, context, Θ) 분포(처음엔 유니폼 랜덤)로 부터, reward의 기대값이 가장 큰 action a를 선택을 한다음, 그 action을 실행하여 새로운 데이터 D={r, a, context}를 구한다.
그다음 이 데이터 D를 이용해 likelihood를 최대화 하도록 학습하여 Θ를 찾고, 기존에 가지고 있던 P(r | a, context, Θ)를 prior로 놓고 sequential Bayesian learning을 하여 새로운 Posterior를 알아낸다.(이 부분은 추측임. 틀릴수도 있음. sequential bayesian을 안스고 그냥 매번 새로운 MAP을 할 수도 있음.)
위 과정을 계속 반복하여, 점점 더 정확한 Θ를 업데이트하고, 이로부터 더 정확해진 P(r | a, s, Θ)를 이용해 보다 좋은 action을 고르도록 위 과정을 반복한다.


기본 개념: https://en.wikipedia.org/wiki/Thompson_sampling

자세한 설명: http://sanghyukchun.github.io/96/
실제 구현 코드: https://github.com/wealthfront/thompson-sampling/blob/master/src/main/java/com/wealthfront/thompsonsampling/BatchedThompsonSampling.java

동영상 강의: https://www.youtube.com/watch?v=G7heaR0_9I0

by 곽동현 이스텔리앙 2018.01.05 21:47

Mac에서 압축한 파일을 window에서 압축 해제했더니 파일 제목이 깨질 때

winarchiver lite

를 사용해서 압축하면 됨 (압축할 때 setting에서 Korean window옵션 선택)

by 곽동현 이스텔리앙 2017.12.18 21:12
| 1 2 3 4 5 6 7 ··· 72 |