몬테카를로

예측 문제

동적계획법은 전이함수를 이용해서 가치를 추정

v_{k + 1} (s) = a \sum π (a ∣ s) s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{k} (s^{'})]

현실에서는 전이함수가 알려진 경우가 없음
예측 문제: 전이 함수가 없이 가치 함수를 추정하는 문제
cf) 제어 문제: 전이 함수 없이 정책을 최적화하는 문제

몬테카를로 법 Monte Carlo Methods

확률적 시행을 여러 번 반복하여 추정하는 방법
몬테카를로: 카지노로 유명한 유럽 모나코 공국의 지역
반지름 $r$ 인 원에 외접하는 정사각형이 있을 때
원의 넓이는 $π r^{2}$ , 사각형의 넓이는 $4 r^{2}$ 으로 $π : 4$ 비율
사각형 안에 균등 분포에 따라 무작위로 $b$ 개의 점을 찍음
원 안에 찍힌 점의 수가 $a$ 개면 $π$ 는 다음과 같이 계산:

π = \frac{4 a}{b}

몬테카를로 지역 사진

무작위 점 샘플링으로 원주율을 추정하는 그림

몬테카를로 법으로 원주율 구하기

import numpy as np
import matplotlib.pyplot as plt

a = b = 0
pi = []

for _ in range(10000):
    x, y = np.random.uniform(size=2)
    if x**2 + y**2 <= 1:
        a += 1
    else:
        b += 1
    pi.append(4 * a / (a + b))

plt.plot(pi)
pi[-1]

첫 방문 몬테카를로 First-visit Monte Carlo

정책을 이용해서 상태 $S_{t} = s$ 에 처음 방문해서 종료 상태에 도달할 때까지 환경과 상호작용
경험 튜플(experience tuple):
- 타임 스텝마다 (관찰, 행동, 보상, 새로운 관찰)의 순서쌍
궤적(trajectory): 경험 튜플의 시퀀스
얻어진 궤적을 이용하여 해당 상태의 수익(return) $G$ 를 구함
$G$ 를 여러 번 구해서 평균내면, 상태 $s$ 의 가치 $V (s)$ 를 구할 수 있음

V (S_{t}) \leftarrow V (S_{t}) + α [G_{t} - V (S_{t})]

첫 방문 몬테카를로

현재 추정하고자 하는 가치 함수의 상태
원은 비종료 상태
마지막에 +1을 보상으로 받고 에피소드가 종료
보상
사각형은 종료 상태
점은 행동

첫 방문 몬테카를로에서 궤적과 종료 상태를 나타내는 그림

첫 방문 몬테카를로

import numpy as np
from collections import defaultdict


class MCPrediction:
    def __init__(self, env, gamma=0.9):
        self.gamma = gamma
        self.env = env
        self.V = np.zeros(env.observation_space.n)
        self.returns = defaultdict(list)

    def select_action(self, policy, state):
        return policy[state]

    def generate_episode(self, policy):
        episode = []
        state, info = self.env.reset()
        done = False
        while not done:
            action = self.select_action(policy, state)
            next_state, reward, done, _, _ = self.env.step(action)
            episode.append((state, action, reward, next_state, done))
            state = next_state
        return episode

    def update_value(self, episode):
        G = 0
        for t in reversed(range(len(episode))):
            state, action, reward, next_state, done = episode[t]
            G = self.gamma * G + reward
            if state not in [x[0] for x in episode[:t]]:
                self.returns[state].append(G)
                self.V[state] = np.mean(self.returns[state])

    def evaluate_policy(self, policy, num_episodes=1000):
        nS = self.env.observation_space.n
        self.V_track = np.zeros((nS, num_episodes))
        for e in range(num_episodes):
            episode = self.generate_episode(policy)
            self.update_value(episode)
            self.V_track[:, e] = self.V.copy()
        return self.V, self.V_track

실험

env = SlipperyWalk(9)
init_state, info = env.reset()
gamma = 1.0
n_episodes = 500
P = env.unwrapped.P

pi = {i: 0 for i in range(env.observation_space.n)}
agent = MCPrediction(env)
V, V_track = agent.evaluate_policy(pi)

RMSE Root Mean Square Error

오차(error)의 제곱의 평균(mean)의 양의 제곱근(root)
cf) 표준편차
RMSE는 오차의 단위를 유지
- 예측값과 실제값이 온도(섭씨)라면 RMSE도 섭씨
큰 오차에 대해 더 큰 패널티를 부여

def rmse(x, y):
    return np.sqrt(np.mean((x - y)**2))

V_true = policy_evaluation(pi, P)
V_true[-1] -= 1
rmse(V, V_true)

수렴 과정

import matplotlib.pyplot as plt


def plot_value_track(V_track, V_true, env):
    colors = plt.cm.viridis(np.linspace(0, 1, env.length - 2))

    for i in range(env.length - 2):
        j = i + 1
        plt.plot(V_track[j], color=colors[i])  # 추정가치
        plt.hlines(V_true[j], 0, 1000, colors=colors[i], linestyles='dashed')  # 실제가치
        plt.text(0, V_true[j], f'{i}')


plot_value_track(V_track, V_true, env)

몬테카를로 추정 가치가 실제 가치로 수렴하는 과정

linspace

지정된 범위 내에서 균일하게 분포된 숫자들을 생성
np.linspace(start, stop, num)
- start: 생성할 숫자들의 시작 값.
- stop: 생성할 숫자들의 끝 값.
- num: 생성할 숫자의 개수.
np.linspace(0, 1, env.length - 2)는 0과 1 사이를 균일하게 나눈 env.length - 2개의 숫자를 생성
- 예) env.length = 9면 0에서 1까지 균일하게 나눈 8개 숫자 생성

Viridis 컬러맵

지각적으로 균일한 컬러맵(Perceptually Uniform Color Maps) 중에 하나
데이터의 특정 범위가 시각적으로 강조되거나 왜곡되지 않도록 인간의 시각 시스템이 색상의 변화를 균일하게 인식할 수 있도록 설계
어두운 파란색에서 밝은 노란색까지 색상을 포함
색맹을 포함한 다양한 시각적 장애를 가진 사람들도 보기 쉬움
색상이 밝기와 잘 대응하므로, 흑백으로 인쇄해도 잘 보임
그 외 비슷한 컬러맵으로 plasma, inferno, magma, cividis 등이 있음

Viridis와 유사한 지각적으로 균일한 컬러맵 비교

선 스타일

Matplotlib 선 스타일 예시

모든 방문 몬테카를로 every-visit MC

첫 방문 몬테카를로는 상태 $s$ 를 독립적으로 샘플링하기 때문에, 여러 번 샘플링할 경우 $V (s)$ 가 실제 값에 수렴
만약 한 궤적에서 상태 $s$ 에 다시 방문하더라도 가치 계산에는 반영 X → 이름이 "첫 방문"인 이유
첫 방문 몬테카를로가 더 오래되고(1940년대), 더 표준적
"모든 방문" 몬테카를로는 다시 방문한 경우도 가치 계산에 반영
모든 방문 몬테카를로도 실제 값에 수렴한다는 것이 1996년에 증명

몬테카를로 법의 장단점

편향되지 않은 추정치를 주는 것은 큰 장점
상태 가치 함수를 갱신하기 위해 실제 수익 $G$ 를 얻을 때까지 기다려야 함
- 에피소드가 끝나지 않거나 매우 긴 경우 사용이 어려움
$t$ 부터 $T$ 까지 여러 타임 스텝의 모든 보상을 더하므로 $G$ 의 분산이 큼
편향이 작아도 분산이 크면 샘플링의 효율성이 떨어짐
편향이 크더라도 분산을 줄일 수 있으면 샘플링의 효율성을 높일 수 있음

편향-분산 교환 bias-variance trade-off

머신러닝에서 편향과 분산 사이의 교환 관계
단순한 모델은 모델의 구조에 따라 나올 수 있는 결론이 제한(높은 편향)되지만 데이터에 따라 결론이 달라지지 않음(낮은 분산)
- 데이터에서 충분히 반영하지 못하는 과소적합(underfitting)의 위험
복잡한 모델은 데이터에 따라 결론이 달라지고(높은 분산), 다양한 결론이 나올 수 있음(낮은 편향)
- 데이터의 작은 노이즈에도 결론이 달라지는 과대적합(overfitting)의 위험

편향-분산 교환 관계 그래프

과적합

과대적합 overfitting: 모델이 실제 패턴보다 복잡
과소적합 underfitting: 모델이 실제 패턴보다 단순

과소적합, 적절한 적합, 과대적합 비교

퀴즈

문제 1 / 8맞음: 0힌트: 0틀림: 0채점중: 0남음: 8

예측 문제의 설명으로 가장 알맞은 것은 무엇입니까?

○전이 함수가 없이 가치 함수를 추정하는 문제
○전이 함수 없이 정책을 최적화하는 문제
○모든 상태에서 최적 행동을 직접 지정하는 문제
○환경의 상태 공간을 하나로 줄이는 문제

퀴즈를 풀려면 대화형 기능을 불러와야 합니다.

예측 문제의 설명으로 가장 알맞은 것은 무엇입니까?

슬라이드에서는 예측 문제와 제어 문제를 구분했습니다.

전이 함수가 없이 가치 함수를 추정하는 문제전이 함수 없이 정책을 최적화하는 문제모든 상태에서 최적 행동을 직접 지정하는 문제환경의 상태 공간을 하나로 줄이는 문제

전이 함수가 없이 가치 함수를 추정하는 문제

몬테카를로 법의 핵심 아이디어는 무엇입니까?

원주율 추정 예시는 무작위 점을 많이 찍어 비율을 계산합니다.

확률적 시행을 여러 번 반복하여 추정한다전이 함수를 알고 있을 때만 값을 정확히 계산한다항상 한 번의 시행만으로 정답을 구한다정책을 사용하지 않고 상태 공간을 삭제한다

확률적 시행을 여러 번 반복하여 추정한다

첫 방문 몬테카를로에 대한 설명으로 올바른 것을 모두 고르세요.

첫 방문이라는 이름은 한 궤적 안에서 같은 상태를 다시 만났을 때의 처리와 관련됩니다.

상태에 처음 방문해서 종료 상태에 도달할 때까지 환경과 상호작용한다얻어진 궤적으로 해당 상태의 수익 (G)를 구한다한 궤적에서 같은 상태를 다시 방문해도 가치 계산에 반영하지 않는다전이 함수가 반드시 알려져 있어야만 사용할 수 있다

상태에 처음 방문해서 종료 상태에 도달할 때까지 환경과 상호작용한다, 얻어진 궤적으로 해당 상태의 수익 (G)를 구한다, 한 궤적에서 같은 상태를 다시 방문해도 가치 계산에 반영하지 않는다

RMSE의 특징으로 슬라이드에서 설명한 것은 무엇입니까?

RMSE는 오차를 제곱한 뒤 평균과 제곱근을 사용합니다.

오차의 단위를 유지하고 큰 오차에 더 큰 패널티를 부여한다오차의 부호만 비교하고 단위는 제거한다예측값과 실제값이 같아도 항상 1이 된다분산을 계산하지 않고 최댓값만 사용한다

오차의 단위를 유지하고 큰 오차에 더 큰 패널티를 부여한다

np.linspace(start, stop, num)에서 num은 무엇을 의미합니까?

start, stop, num의 세 인자가 각각 무엇을 담당하는지 떠올리면 됩니다.

생성할 숫자의 개수생성할 숫자들의 시작 값생성할 숫자들의 끝 값색상표의 이름

생성할 숫자의 개수

Viridis 컬러맵에 대한 설명으로 올바른 것을 모두 고르세요.

Viridis는 시각적 왜곡을 줄이고 접근성을 고려한 컬러맵입니다.

지각적으로 균일한 컬러맵 중 하나이다어두운 파란색에서 밝은 노란색까지 색상을 포함한다색맹을 포함한 다양한 시각적 장애를 가진 사람들도 보기 쉽다흑백 인쇄에서는 반드시 정보를 잃도록 설계되었다

지각적으로 균일한 컬러맵 중 하나이다, 어두운 파란색에서 밝은 노란색까지 색상을 포함한다, 색맹을 포함한 다양한 시각적 장애를 가진 사람들도 보기 쉽다

몬테카를로 법의 장단점에 대한 설명으로 올바른 것을 모두 고르세요.

몬테카를로 법은 실제 수익을 사용하기 때문에 편향과 분산의 특성이 뚜렷합니다.

편향되지 않은 추정치를 주는 것은 큰 장점이다상태 가치 함수를 갱신하려면 실제 수익 (G)를 얻을 때까지 기다려야 한다(G)의 분산이 커질 수 있다에피소드가 끝나지 않아도 항상 즉시 갱신할 수 있다

편향되지 않은 추정치를 주는 것은 큰 장점이다, 상태 가치 함수를 갱신하려면 실제 수익 (G)를 얻을 때까지 기다려야 한다, (G)의 분산이 커질 수 있다

과대적합(overfitting)에 대한 설명으로 알맞은 것은 무엇입니까?

과대적합은 복잡한 모델과 높은 분산 위험에 연결됩니다.

모델이 실제 패턴보다 복잡한 경우모델이 실제 패턴보다 단순한 경우오차의 단위를 유지하는 평가 지표상태를 처음 방문했을 때만 갱신하는 방법

모델이 실제 패턴보다 복잡한 경우