학습목표
- Exploration and Exploitation 의 이해
- Epsilon-greedy Strategy의 이해
Single agent approaches로 Anatomical landmark detection을 하는 프로젝트를 진행하기 위해 참고한 논문에서
training하는 방법으로
"During training, the agent follows an epsilon-greedy policy. The terminal state is reached when the distance to the target landmark is less or equal than 1mm. During testing, the agent starts in the 80% inner region of the image and follows a full greedy policy. The episode ends when the agent oscillates or after 1500 steps."
라고 제시하고 있었다.
그래서 epsilon-greedy policy에 대해 다시 공부하고 이해한 내용을 정리해보고자 한다.
내가 도박장에 갔다고 생각해보자.
여기엔 10개의 슬롯머신이 있고, 0$~10$의 보상을 제공한다. 각 슬롯머신마다 평균보상이 다르므로 평균보상이 제일 높은 슬롯머신을 찾아다니는게 좋겠다 :))
※ 예를 들어 3번 슬롯머신의 평균보상이 9$이고, 1번 슬롯머신의 평균 보상이 $4라고 하자. 물론 각 시행의 보상은 확률적이므로 1번 슬롯머신에서도 9$가 나올 수 있지만 '평균보상'이 저렇기 때문에 여러번 하다보면 결국 1번 슬롯머신의 평균 보상이 3번 슬롯머신의 것보다 낮을 것이라고 예상가능하다.
일단 이런 상황을 공식적으로 서술해보자.
각 play(k)에서 나는 n개의 action(여기선 10개의 슬롯머신 중 하나를 선택하는 행위 a)를 선택해서 레버를 당긴다. 그리고 그에 맞는 보상을 받는다. (Rk (reward at play k))
그렇다면 같은 시간에 돈을 가자 많이 벌 수 있는 방법은 뭘까? 내가 이 도박장에 갔다면 어떻게 하고 있을까?
우선 처음 몇 번은 서로 다른 슬롯머신을 택해서 당기는 동작을 하고, 그 보상을 관찰할 것이다. 그리고 그 다음에는 지금까지 당겨본 것 중에서 보상이 가장 컸던 걸 계속해서 선택해서 당기겠지.
이걸 또 수식으로 표현해보자.
이전 시행들에 기초한 기대보상(expected reward) 개념이 필요하고, k번째 시행에서 동작 a의 기대보상은 Qk(a)로 나타내자. a동작을 했을 때 기대하는 보상의 양인 그때까지 a의 모든 보상의 산술평균을 리턴하는 함수이다.
따라서, 이전 동작들과 관찰은 이후 동작에 영향을 미친다.
이 함수는 특정 동작(a)의 가치를 리턴해준다는 점에서 동작 가치 함수 라고 한다. 그리고 이 함수를 Q로 표기하기 때문에 Q함수라고 부르기도 한다.
Qk(a) = (R1+R2+...+Rk) / ka수도코드로는?
def exp_reward(action, history):
rewards_for_action = history[action}
return sum(rewards_for_action) / len(rewards_for_action)그럼 이 동작 가치 함수를 적용해서 평균 보상이 가장 큰 동작을 하는 알고리즘을 구현해볼까?
그냥 간단하게 동작 가치 함수가 가장 큰 동작을 선택하면 된다.
수도코드
def get_best_action(actions, history):
exp_rewards = [exp_reward(action, history) for action in actions]
return argmax(exp_rewards)python code
def get_best_action(actions):
best_action = 0
max_action_value = 0
for i in range(len(actions)):
cur_action_value = get_action_value(actions[i])
if cur_action_value > max_actioin_value:
best_action = i
max_action_value = cur_action_valuue
return best_action이렇게 지금까지의 경험에만 근거해서 최선의 것을 선택하는 접근 방식을 greedy method라고 부른다.
같은 시간에 돈을 가자 많이 벌 수 있는 방법은 뭘까? 내가 이 도박장에 갔다면 어떻게 하고 있을까? 라는 질문에
우선 처음 몇 번은 서로 다른 슬롯머신을 택해서 당기는 동작을 하고, 그 보상을 관찰할 것이다. 그리고 그 다음에는 지금까지 당겨본 것 중에서 보상이 가장 컸던 걸 계속해서 선택해서 당기겠지. 라고 답하였다.
여기서 '우선 처음 몇 번은 서로 다른 슬롯머신을 택해서 당기는 동작을 하고'에 해당하는 것이 동작의 결과를 무작위로 탐험해본다는 의미에서 탐험(Exploration)라고 부른다.
그리고 '그 다음에는 지금까지 당겨본 것 중에서 보상이 가장 컸던 걸 계속해서 선택해서 당기겠지'에 해당하는 것이 지금까지 수집한 지식에 기초해서 보상이 가장 큰 동작을 결정하고 그것만 계속해서 시도하는 것이라는 의미에서 활용(Exploitation)이라고 부른다.
우리는 언제까지고 탐험만 하거나, 아니면 탐험은 딱 한번만 하고 그걸 계속 활용하지는 않을 것이다.
무작위로 선택해서 그 보상이 얼마난지 지식을 수집하는 탐험과 그때까지 배운 가장 가치있는 지식을 계속 선택하는 활용을 적절한 비율, 균형점을 찾아서 그 비율로 진행 할 것이다.(정말 사람이 배우는 과정이랑 똑같아서 신기하다..ㅋㅋㅋㅋ)
비율을 엡실론(ε)으로 잡아서 ε의 확률로 탐험(Exploration)을 적용하고 1-ε 확률로 활용(Exploitation)을 적용하여서 위에서 살펴본 greedy method를 하는 것을 Epsilon-greedy strategy라고 한다.
다시 슬롯머신 예제에서 Epsilon-greedy strategy을 적용해보자.
슬롯머신 선택 동작의 수 n = 10
각 슬롯머신에서 최대 보상 $10가 나올 (무작위) 확률 probs = np.random.rand(n)
python code
import numpy as np
import scipy import stats
import random
import matplotlib.pyplot as plt
n = 10 #슬롯머신의 개수
probs = np.random.rand(n) #각 슬롯머신에서 최대 보상 $10가 나올 (무작위) 확률
eps = 0.2 #엡실론 값
여기서 보상을 계산하는 방법은 0에서 1사이의 부동소수점 난수를 구해서 그것이 슬롯머신의 확률prob보다 작으면 보상에 1을 더하는 과정을 10회 반복하는 방법을 사용
python code
def get_reward(prob, n=10):
reward = 0
for i in range(n):
if random.random() < prob:
reward += 1
return reward
지금까지 어떤 동작을 했고, 그에 따른 어떤 보상이 주어졌는지 기록을 저장하는 배열과 동작이 이뤄질 때마다 갱신하는 함수
python code
record = np.zeros((n, 2)) #1열: i번(행) 슬롯머신을 당신 횟수, 2열: 현재까지의 평균보상
#보상 기록(record) 갱신 함수
def update_record(record, action, r):
new_r = (record[action,0]*record[action,1]+r) / (record[action,0]+1)
record[action,0] += 1
record[action,1] = new_r
return record
현재까지 평균 보상이 가장 큰 동작을 선택하는 함수
python code
def get_best_action(actions):
best_action_index = np.argmax(record[:,1], axis=0)
return best_action_index
이제 본격적으로 Epsilon-greedy strategy을 적용하여서
같은 시간에 돈을 가자 많이 벌 수 있는 방법은 뭘까? 내가 이 도박장에 갔다면 어떻게 하고 있을까? 에 대한 해법 python code
fig, ax = plt.subplots(1,1)
ax.set_xlabel("Plays")
ax.set_ylabel("Avg Reward")
record = np.zeros((n,2))
probs = np.random.rand(n)
eps = 0.2
rewards = [0]
for i in range(500):
if random.random() > eps: #20%의 확률로 탐험
choice = get_best_action(record)
else: #80%의 확률로 활용
choice = np.random.randint(10)
r = get_reward(probs[choice]) #위의 과정을 통해 결정된 동작에 따른 보상 계산
record = update_record(record,choice,r) #그리고 그 기록을 갱신
mean_reward = ((i+1) * rewards[-1] + r)/(i+2) #전체적인 보상을 계산하기 위한 보상 평균 갱신
rewards.append(mean_reward)
ax.scatter(np.arange(len(rewards)),rewards)
시행을 지금 500번 하는 것으로 코드를 짰는데, 이 시행이 반복될 수록 rewards가 증가한다는 것은 알고리즘이 이 도박장에 대한 해법을 배워나간다는 것이다.
지금까지 도박장의 Epsilon-greedy strategy을 적용하여서 슬롯머신을 택하고 가장 보상을 많이 받는 방법을 학습해나가는 강화학습 전략에 대해 구현해보았다.
흠.. 그런데 보충해야할 것이 있다.
지금까지 정리한 것에는 '동작'개념만 있지 '상태'개념은 들어가지 않은 것 같다.
medical image에서 landmark detection의 경우 이미지(즉, 환경)의 정보를 사용한 '상태'개념이 들어가므로 문맥적 정보를 고려한 문제로 바라보고 해법을 찾아야하지 않을까?
그렇다 이렇게 문맥적 정보를 고려하게 되면 상태 공간의 개념이 도입되며, 그러면 가능한 상태-동작-보상의 조합 수가 폭발적으로 늘어난다. (앞서 동작-보상 조합만 있었을 때는 k번째 시행에서 동작 a를 했을 때 보상 r로 이루어진 배열만 있어서 단순 for문으로 가장 높은 보상을 찾아내었었다.)
그래서 필요한 것이 바로바로 딥러닝 신경망!
신경망을 이용하면 대량의 상태-동작-보상의 조합에서 관계성을 배울 수 있을 것이다. 그러므로 이러한 정보에 기초해서 결정을 내리는 agent로써 역할을 하는 것이 바로 신경망이 되어야 한다.
다음에는 문맥적인 개념이 도입된 문제의 해법을 신경망 구축과 함께 정리해 볼 것이다.