[Reinforcement Learning-1] Thompson sampling model

 

 

출처 : DeepAI

톰슨 샘플링

 

 

톰슨 샘플링 모델은 강화학습의 가장 기본적인 모델입니다.

강화학습을 이해하기 위한 기본적인 선형대수, 확률론은 배제하고 진행해보겠습니다!

 

Beta Distribution

톰슨 샘플링 모델은 Beta Distribution을 활용합니다.

 

출처 : Statlect

 

Beta Distribution이란, Gaussian Distribution처럼 특정 사건에 대한 분포 표를 의미합니다.

독특하게 인자가 두개인대요 Beta(a,b)로써

a와 b는 각각의 반대의 사건을 의미하며, 극단적으로는 b=1-a로 볼수 있습니다.

 

출처 : Vose software

톰슨모델은 위의 그림처럼 그려지게 됩니다.

a가 커질수록 분포가 오른쪽으로 움직이고, b가 커질수록 분포가 왼쪽으로 움직이는것을 확인하실 수 있는데

여기서 a와 b를 개발자가 원하는 확률을 넣게되면, 해당 사건들이 발생할 수 있는 확률분포표(pdf)를 상기와 같은 형식으로 그려내게 됩니다.

 

 

단번에 이해는 어려우실겁니다!

간단한 실생활문제로 쉽게 이해해보시죠!

슬롯머신이 3대 있다고 가정했을때, 어느 슬롯머신이 가장 내 재산을 잘불려주는지? 찾아내는것을 강화학습으로 찾아보고자 합니다.

 

[가정]

슬롯 1 : 20%

슬롯 2 : 31%

슬롯 3 : 14%

 

이렇게 3개의 슬롯머신이 내 돈을 2배로 불려줄 확률이 정해져있습니다. 물론, 톰슨모델은 모르는 상황입니다.

 

Beta(a,b)에서 a와 b를 저는 이렇게 두어보겠습니다

 

a : 내 돈을 불렸을때 +1

b : 내 돈을 잃었을때 +1

 

이렇게 두게되면 위의 베타 함수로 그려진 슬롯머신중 어떤것을 쓸때가 가장 좋을까요??

 

바로 초록색입니다!

당연히 빨간색이 제일 안좋은 슬롯머신이겠죠!

 

베타함수에 대한 분포분석을 통해 3개의 슬롯머신중 어떤것을 뽑아야 좋을지 코드와함께 정리해보겠습니다.

 

 

코드

import numpy as np

conversionRates = [0.2, 0.31, 0.14]

N = 2000

d = len(conversionRates)

Array 연산을 위한 numpy library를 불러오고
conversionRates로 각각의 슬롯머신 3대에 대한 당첨확률을 정의합니다.
2000번의 반복을 통해 톰슨모델이 제대로 2번슬롯머신을 찾아내는지 보겠습니다.

X = np.zeros((N, d))

for i in range(N):

    for j in range(d):

        if np.random.rand() < conversionRates[j]:

            X[i][j] = 1

conversionRates보다 낮은 난수(rand)를 가질때 X[i][j]=1 이라는 말은, 해당 확률로써 당첨되었을때와 동일한 의미입니다.

nPosReward = np.zeros(d)

nNegReward = np.zeros(d)

nPosReward는 돈을 땃을때를 의미하는 Beta(a,b)중 a에 해당하며
nRegReward는 b에 해당합니다.
돈을 땄을때는 a를 +1, 돈을 잃었을때는 b를 +1할것입니다.

for i in range(N):

    selected = 0

    maxRandom = 0

    for j in range(d):

        randomBeta = np.random.beta(nPosReward[j] + 1, nNegReward[j] + 1)

        if randomBeta > maxRandom:

            maxRandom = randomBeta

            selected = j

    if X[i][selected] == 1:

        nPosReward[selected] += 1

    else:

        nNegReward[selected] += 1

i는 '행'을 의미하며 2천번 룰렛을 돌리는 시간을 의미합니다.
j는 0~2로 3대의 슬롯머신을 각각 돌릴때를 의미합니다.
beta(a,b) = np.random.beta(a,b)이므로 현재 a에는 돈을 땄을때, b에는 돈을 잃었을때 임을 볼 수 있습니다.

        if randomBeta > maxRandom:
            maxRandom = randomBeta
            selected = j

이부분이 중요한데요,
3대의 룰렛을 돌렸을때 나오는 각각의 당첨확률중 가장 높았던것을 j라고 선택합니다.

    if X[i][selected] == 1:
        nPosReward[selected] += 1
    else:
        nNegReward[selected] += 1

그다음, 선택된 룰렛이 1이냐?(돈을 땄냐?)를 판단하고 Yes라면 a +=1, 아니라면 b+=1을 해줍니다.

nSelected = nPosReward + nNegReward 

for i in range(d):

    print('Machine number ' + str(i + 1) + ' was selected ' + str(nSelected[i]) + ' times')

print('Conclusion: Best machine is machine number ' + str(np.argmax(nSelected) + 1))

톰슨 모델로 추정해낸 최고 확률의 룰렛을 찾아냅니다.

 

 

결과

톰슨 모델로 정확하게 룰렛 2번이 확률이 높다는것을 찾아내고 있습니다.

 

위에 돌린것이 무슨 코드인지 다시 요약하자면

conversionRates = [0.2, 0.31, 0.14]

저희는 이렇게 각각의 룰렛 확률을 주어, 당첨될 확률 데이터를 모두 만들었습니다.

 

하지만 톰슨모델은 이 확률을 모르고있습니다!

그냥, 이 확률을 가진 룰렛으로 게임을 했을때 나온 데이터값들을 통해 추정할 뿐이죠

 

이렇게 '보상'이라는 방식을 Beta Distribution으로 해석하여 pdf분석을 통해 목표하는것을 찾아내는 방식이 톰슨 샘플링 모델입니다 :)

 

 

코드전문

 

import numpy as np

 

conversionRates = [0.2, 0.31, 0.14]

N = 2000

d = len(conversionRates)

 

X = np.zeros((N, d))

for i in range(N):

    for j in range(d):

        if np.random.rand() < conversionRates[j]:

            X[i][j] = 1

nPosReward = np.zeros(d)

nNegReward = np.zeros(d)

 

for i in range(N):

    selected = 0

    maxRandom = 0

    for j in range(d):

        randomBeta = np.random.beta(nPosReward[j] + 1, nNegReward[j] + 1)

        if randomBeta > maxRandom:

            maxRandom = randomBeta

            selected = j

    if X[i][selected] == 1:

        nPosReward[selected] += 1

    else:

        nNegReward[selected] += 1

nSelected = nPosReward + nNegReward 

for i in range(d):

    print('Machine number ' + str(i + 1) + ' was selected ' + str(nSelected[i]) + ' times')

print('Conclusion: Best machine is machine number ' + str(np.argmax(nSelected) + 1))

print(nPosReward)

print(nNegReward)

print(nSelected)

print(X)

sum = np.sum(nSelected)

print(sum)