cdjs의 코딩 공부방

Taxi-v2 Q-learning

import gym
import random
import numpy as np

env = gym.make("Taxi-v2")
env.reset()

q_table = np.zeros([env.observation_space.n, env.action_space.n])

alpha = 0.8
gamma = 0.95
epsilon = 1

success = 0

for i in range(10000):
    epsilon = 5 / (1 + i)
    state = env.reset()
    epochs = 0
    done = False

    while not done and epochs < 500:
        epochs += 1

        # e-greedy
        if random.uniform(0, 1) < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(q_table[state])

        next_state, reward, done, info = env.step(action)

        # update Q
        old_value = q_table[state, action]
        next_max = np.max(q_table[next_state])

        new_value = old_value + alpha * (reward + gamma * next_max - old_value)
        q_table[state, action] = new_value

        state = next_state

        if reward > 0:
            success += 1

print("Success rate : " + str(success / 10000))
env.close()

FrozenLake Q-learning

(V3 : Deterministic, V0 : Stochastic)

import gym
import numpy as np

gym.envs.registration.register(
    id='FrozenLake-v3',
    entry_point='gym.envs.toy_text:FrozenLakeEnv',
    kwargs={'map_name': '4x4',
            'is_slippery': False}
)
# Stochastic
# env = gym.make("FrozenLake-v0")

# Deterministic
env = gym.make("FrozenLake-v3")
env.reset()

q_table = np.zeros([env.observation_space.n, env.action_space.n])

alpha = 0.6
gamma = 0.6
epsilon = 1
success = 0

for i in range(20000):
    epsilon = 1. / ((i // 1000) + 1)

    state = env.reset()
    epochs = 0
    done = False
    episode_reward = 0

    while not done and epochs < 500:
        epochs += 1
        
        # e-greedy
        if np.random.uniform(0, 1) < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(q_table[state])
            
        next_state, reward, done, info = env.step(action)
        
        # update Q
        old_value = q_table[state, action]
        next_max = np.max(q_table[next_state])

        q_table[state, action] = old_value + alpha * (reward + gamma * next_max - old_value)

        state = next_state

        episode_reward += reward

        if done and reward == 0:
            q_table[state][action] -= 1

        if reward == 1:
            success += 1

print("Success rate : " + str(success / 20000))
env.close()

오늘의 교훈

1. epsillon을 줄이자. (줄이는 코드를 안짜서 한참 헤멨음.)

2. epsillon을 줄이는 방법에 따라 결과가 천차만별이다. (Frozen-lake에서 epsillon을 1 / (i+1) 로 뒀더니 결과가 똥망함)

3. 시간은 얼마 없고 갈 길은 멀다. 빨리 공부해야지.

부록편에서는 지금까지의 강의를 하면서 개념 자체를 이해하는데 큰 필요성을 느끼지 못해 설명하지 않았던 수학적인 부분에 대해 설명합니다.

참고로 그렇게 수학적으로 깊게 파고들지는 않고, 간단히 개념을 이해할 정도로만 설명합니다.

1. 극한에 관하여

미분에 대해 알기 위해선 극한에 대해서 알아야 합니다.

그런데 사실 극한은 매우 간단합니다.

특정한 함수 f(x)가 L에 한없이 가까워 지는 것을 f(x)가 L에 수렴한다고 하고, 

이 때 L을 함수 f(x)의 x=a에서의 극한값이라고 합니다.

이 때, 이것을 기호로 lim x->a f(x) = L 으로 표현합니다.

주의하셔야 할 점은 x=a에서의 극한값이 x=a일 때의 값을 의미하진 않습니다.

x가 a에 수렴한다는 것은 x=a라는 것이 아니라, x의 값이 a에 최대한 근접했다는 뜻입니다.

위의 그래프를 보도록 합니다.

x가 a의 왼쪽 부분에서 시작해서 a에 한없이 가까워 진다고 해봅시다.

그럼 x가 a에 서서히 가까워질수록, f(x)의 값도 8로 가까워지게 됩니다.

마찬가지로 x가 a의 오른쪽 부분에서 시작해서 a에 한없이 가까워 진다고 해도,

x가 a에 서서히 가까워질수록 f(x)의 값도 8로 가까워집니다.

이 때 함수 f(x)에서 x=a에서의 극한값은 8이 됩니다.

2. 미분과 Gradient Descent

2-1. 평균 변화율이란?

함수에서 평균 변화율은 다음과 같이 정의합니다.

함수 y=f(x)에서 x의 값이 a에서 b까지 변할 때, 평균 변화율은

(f(x)의 변화량) / (x의 변화량) = (f(b) - f(a))/ (b-a) = (f(a) + x의 변화량) - f(a) / x의 변화량

으로 정의됩니다.

그리고, f(x)의 변화량과 x의 변화량은 기호로 각각 Δf(x), Δx라는 기호로도 나타낼 수 있는데, 그렇게 위 식을 쓰면

Δf(x) / Δx  =  (f(b) - f(a))/ (b-a)  =  (f(a) + Δx) - f(a) / Δx

라고도 쓸 수 있습니다.

막 어렵게 써놨지만, 간단히 말해서 함수 f(x)에서 a에서 b까지의 기울기를 의미합니다.

간단한 exercise로 y=x^2그래프에서 x의 값이 1에서 2까지 변할 때 평균 변화율을 생각해 보면,

Δf(x) = 2^2 - 1^2 = 4 - 1 = 3

Δx = 2 - 1 = 1

즉, 평균 변화율 Δf(x) / Δx = 3/1 = 3 이 됩니다.

그리고, 이는 (1,f(1))과 (2,f(2))를 잇는 직선의 기울기가 됩니다.

위 그래프에서 x가 x에서 x+h로 변할 때의 평균 변화율은 저 보라색 직선입니다.

공식으로 이해하지 말고, 그냥 간단히 직관으로 이해합시다.

2-2. 순간 변화율이란?

순간 변화율이란, 평균 변화율에서 x의 변화량이 0에 수렴할 때의 값을 의미합니다.

lim(b-a -> 0) (f(b) - f(a)) / (b-a) = lim (Δx->0)  Δf(x) / Δx = lim(Δx -> 0)  (Δ(x) + Δf(x)) / Δ(x) 

위의 그래프를 보며 이해해봅시다.

위의 그래프에서 왼쪽의 파란 점을 x, 오른쪽의 파란 점을 x+Δx라고 해봅시다.

이 때, Δx의 값을 대략 한 10에서 0으로 쭉 쭉 줄여보면,

Δx (x의 변화량)의 값도 0으로 쭉쭉 줄어들게 됩니다.

그리고, Δx를 계속해서 줄이면 x가 x에서 Δx까지 변할 때의 평균 변화율도 계속해서 변화합니다.

그러다가, Δx를 0에 수렴하게 줄이게 되면 저 두 점이 거의 만나게 될 것입니다.

(실제로 만나는 것은 아닙니다!! 극한값으로 가는것 뿐입니당)

이때 나오는 순간 변화율의 값을 미분계수라고 합니다.

그리고, 이 미분계수를 찾는 과정을 바로 미분이라고 합니다.

그런데 저 그래프를 잘 봐주시기 바랍니다.

순간 변화율은 Δx가 0으로 수렴할 때의 평균 변화율이라고 했으므로,

Δx가 0으로 수렴할 때, 파란 직선은 그래프의 접선으로 바뀌게 됩니다!

3. Gradient Descent

이를 토대로 Gradient descent를 이해해 봅시다.

Gradient Descent에서 우리가 하고 싶었던 것은 무엇인가 하면, 어떤 함수 f(x)가 최소가 되는 x를 찾는 것이었습니다!

위의 경우에는 x축에 w, y축에 J(w)로 적혀 있으므로 이를 따라 J(w)가 최소가 되는 w의 값을 찾아봅시다.

만약 처음 w값이 위의 그래프처럼 오른쪽 위쯤에 있다고 해봅시다.

그러면 그 W값을 미분하면, 위처럼 양수의 미분계수가 나오게 됩니다.

그런데 잘 생각해 봅시다.

미분계수가 양수라면, 즉 접선의 기울기가 왼쪽 아래와 오른쪽 위를 향하고 있다면 어떤 부분의 함숫값이 더 작을까요?

접선이 왼쪽 아래와 오른쪽 위를 향하고 있으므로, 당연히 아래를 향하는 왼쪽 부분의 함숫값이 더 작을 것입니다.

그리고 Gradient Descent의 목표는 J(w)가 최소가 되는 w의 값을 찾는 것이므로,

w를 함숫값이 더 작은 왼쪽 부분으로 넘겨 주어야 합니다.

즉, w값을 줄여야 한다는 것이죠.

즉, 어떤 함수에서 w값에 대한 미분계수가 양수라면, w의 값을 줄여주어야 합니다!

그렇다면 반대로 처음 w값이 왼쪽에 있었다면 어땠을까요?

그럼 x=w에서의 미분계수는 음수가 되었을 것입니다.

그리고 이 때는 접선의 기울기가 왼쪽 위와 오른쪽 아래를 향하고 있으므로,

함숫값은 왼쪽보다 오른쪽이 더 낮을 것입니다.

그리고 우리의 목적은 함숫값 J(w)를 최소로 하는 w의 값을 찾는 것이므로,

w를 함숫값이 더 작은 오른쪽 부분으로 넘겨 주어야 합니다.

즉, w의 값을 더 늘려야 하는 것이죠.

즉, 어떤 함수에서 w값에 대한 미분계수가 음수라면, w의 값을 늘려주어야 합니다!

그리고! 위에서 정리한 두개의 사실들을 하나로 합치자면,

"w의 값을 미분계수의 부호의 반대쪽으로 옮겨야 한다"입니다!

즉, 미분계수가 양수라면 w를 줄여야하고, 미분계수가 음수라면 w를 늘려야한다는 것이죠!

그러니, Gradient Descent에서 나오는 공식인

W := W - α * ∂/∂W cost(W)에서 α를 뺀 부분만큼은 이해가 되셨을 것 같습니다. (∂/∂W cost(W)는 cost(W)를 W에 대해 미분한다는 뜻입니다.)

양수를 빼면 줄어들고, 음수를 빼면 늘어나기 때문에, 저 미분계수에다가 α를 곱한 값을 w에서 빼주면 된다는 것입니다!

그런데, 왜 α를 곱해줘야 할까요?

미분계수에다가 α를 곱하지 않으면 w의 값을 한 번에 너무 멀리 보내버리게 되기 때문입니다.

그러면 위의 그림에서 왼쪽의 그래프마냥, J(w)값이 줄어들기는 커녕 늘어나는 방향으로 w가 바뀔 수도 있습니다.

그리고 마냥 미분계수만큼만 빼버리면 웬만하면 저런 식으로 w값이 날라가게 되므로,

α값을 곱해주어 너무 멀리 가는 것을 방지해 주는 것입니다.

(그러니까 일반적으로 α는 1보다는 작고 0보다는 큰 값이겠지요. 참고로, α는 learning rate라고 불립니다.)

이러한 이유에서, Gradient Descent를 반복하면, 즉!

W := W - α * ∂/∂W * cost(W)를 반복하면, 결국 w의 값이 J(w)가 최소가 되는 값으로 수렴하게 된다는 것을 알 수 있습니다!

이렇게 미분의 기본적 개념과 함께 Gradient Descent가 무엇인지 알아보았습니다.

혹시 이해가 덜 되었거나 더 알고싶은 점이 있다면 댓글로 물어보세요!!

이번 포스팅에서는, Logistic (regression) classification에 대해 알아볼 것입니다.

(왜 중간에 (regression)이 있는지는 나중에 다룰게요!)

우선 Logistic (regression) classification이 정확히 뭔지 알아보기 전에, 일단 Binary Classification이 뭐였는지 먼저 알아봅시다.

Binary Classification은 두개로 이루어진 값들을 분류하는 작업입니다.

가령 스팸메일 필터링을 한다고 했을 때는, 이 메일이 스팸인지 그냥 메일인지 확인해야 하겠죠?

이 때 이 메일을 스팸인지/그냥 메일인지 두 가지중 하나로 분류하는 작업을 바로 Binary Classification이라고 합니다.

그런데 이런 작업을 할 때, 어떤 메일이 스팸인지 / 그냥 메일인지 구분할 때 0과 1로 인코딩 작업을 거칩니다.

가령 스팸이면 1, 그냥 메일이면 0으로 두는 것이죠.

그런데 왜 이렇게 인코딩을 할까요?

왜 이러는지는 regression의 성질을 생각하면 조금 이해가 될 듯 합니다.

(우리가 배우는 모델은 classification 작업에 사용될 뿐이지, 엄연히 regression모델입니다!!!)

저번 시간까지 배웠던 linear regression의 결과값은 어떻게 나왔나요?

가령 성적을 예측하는 regression모델이라고 한다면, 예측한 점수를 결과값으로 내게 될 것입니다.

이렇듯, regression모델은 특정한 '값'을 '예측'하는데 사용됩니다.

그렇기 때문에 이런 regression 모델로 분류를 진행하려면, 이런 class들을 (스팸인지 아닌지) '값'으로 설정해야 합니다.

스팸 메일은 1, 그냥 메일은 0.. 이렇게 말이죠.

그리고 그렇게 예측한 값이 1에 가깝다면 스팸메일이다! 라고 예측을 하고,

예측한 값이 0에 가깝다면 진짜 메일이다! 라고 예측을 하는 겁니다.

그런데, 그럼 그냥 Linear regression 모델을 그냥 사용하면 안되는 걸까요?  안되니깐 다른 모델을 배우는거겠죠?

자, 위의 예시를 봅시다.

위의 그래프는 x축에 공부한 시간, y축에 pass / fail (1 / 0)이 그려진 그래프로,

공부한 시간 비례 시험에서 통과할지 실패할지 예측하는 모델을 그린 것입니다.

그럼 이것을 Linear regression모델로 짤 수도 있지 않을까요?

fail 과 pass를 나누는 직선 하나를 그린 뒤에,

그 직선의 y값이 0.5 이하이면 fail, 아니면 pass라고 하면 잘 작동할것 처럼 보이기도 합니다.

그런데, 저 오른쪽 끝부분 (아래에 50적혀있는) 의 동그라미를 봅시다. 

만약 어떤 학생이 정말 시험에서 너무 pass하고 싶어서 50시간이나 공부를 해서 pass를 받았다고 가정해 봅시다.

그러면 어떤 문제점이 발생하느냐 하면,

linear regression의 Hypothesis H(x) = WX + B 함수가 저 오른쪽의 동그라미도 감안하고 측정이 되므로,

저 동그라미가 없을때보다 직선이 조금 더 오른쪽 아래로 기울어지는 현상이 발생합니다.

그런데 이렇게 되면 원래는 pass였던 것들의 y값이 0.5 아래로 내려가버리면서 fail로 처리되는 문제가 발생하게 됩니다.

(위의 그래프에 그려진 파란 직선 두개 참고)

이렇듯, Binary classification (사실 classification 전체 다)를 수행하는 데 Linear Regression 모델은 적합하지 못합니다.

Linear regression을 사용하기 애매한 이유가 또 있습니다.

Linear regression의 경우 Hypothesis 함수를 H(x) = Wx + b 로 정의합니다. 그쵸?

그런데 어차피 y값들 (class, 스팸인지 아닌지)는 0이거나 1이 된다는 것을 우리는 이미 알고 있습니다.

(0, 1 인코딩을 이미 했고, 그렇게 분류하는것이 binary classification의 목적이니까요.)

그런데 Linear regression의 H(x)는 1보다 엄청 큰 수를 결과값으로 뱉을 수도 있고, 0보다 엄청 작은 수를 결과값으로 뱉을 수 있습니다.

가령 H(x) = 100x 라는 hypothesis가 있다고 해봅시다.

우리의 목적은 데이터들을 0과 1 둘중 하나의 값으로 분류하는 것이 목적이므로,

1에 가까운 값은 1로 분류하고, 0에 가까운 값은 0으로 분류하게 될 것입니다.

그런데 H(x) = 100x가 되버리면 (대략적으로) x가 0.01 이상일때는 모두 1로, x가 0 이하일때는 모두 0으로 분류되게 됩니다.

이러면 어떤 문제점이 발생해 버리냐하면, x값에 너무 민감하게 반응하는 모델이 만들어지게 됩니다.

즉, 연산상으로는 매우 작은 값(0.01)만 바뀌어도 아예 분류 자체가 바뀌어버리게 되는 것입니다.

이는 아까 위에서 설명했던 문제와 겹치며 linear regression 모델을 classification을 하는 용도로 사용하기 힘들게 만듭니다.

이를 해결하기 위하여 나온 것이 바로 logistic function (sigmoid function 이라고도 한다) 입니다.

원래 linear하던 H(x) = wx + b를 0과 1 사이의 함수로 바꿔주는 함수입니다.

수식으로 나타낸다면, g(z) = 1 / (1+ e^-z) 가 됩니다.

이렇게 hypothesis에 sigmoid 함수를 씌워주면, 무슨 함수였던지간에 결과값이 모두 0과 1 사이로 나오는 함수를 만들어 줄 수 있습니다.

(왜 이런 값이 나오는지 수학적으로 설명하는 것은 나중에 부록 편에서 다루겠습니다.)

그리고 이것을 Logistic regression의 Hypothesis로 나타낸다면 위와 같은 수식으로 나타내어 집니다.

(W T X 는 그냥 간단하게 W * X로 생각해 주시면 됩니다.

multi-variable의 경우에서도 사용할 수 있도록 만든 hypothesis인지라 저런 식이 들어갑니다.)

그리고 이렇게 H(x)의 값이 0과 1사이로 나오면, 사용하기에 매우 편리해 지게 됩니다.

위의 Hypothesis 함수로 regression을 한 결과값이 0.5이상인 경우엔 1로 분류하고, 0.5보다 작으면 0으로 분류하면 되는 것이죠.

(사실 아까 전에 0,1 encoding을 한 이유도 이것 때문입니다.)

*참고 : Logistic "Regression" 인 이유!

많은 분들이 왜 이 모델이 Regression 모델인지 헷갈려 하곤 합니다.

그러니까, Logistic regression은 사실 classification을 하는데 사용하는데, 왜 regression이라고 불리는가를 헷갈려 하는 것이죠.

하지만 Logistic regression모델은 결과값이 0과 1 사이로 한정되는 특성상 classification을 하는 데 사용되는 모델이긴 하지만, 결과값으로 특정한 "값"을 도출해내는 모델입니다.

가령, 성적을 예측하는 Linear regression은 점수 그 자체를 결과값으로 도출합니다. (10점, 30점, 60점 등등...)

그와 비슷하게 스팸 메일인지 아닌지를 분류하는 Logistic regression 모델은 0과 1 사이의 값 자체를 결과로 냅니다. (0, 0.2, 0.8 등등...)

그러니까, Logistic Regression은 입력값 x에 대해 0과 1로만 이루어진 y값에 최대한 가깝게 그려질 수 있는 함수를 만들어내는 모델인 것입니다.

그리고 결과값이 0.5보다 큰 (즉, 1에 가까운) 값들은 죄다 1로 분류해 버리는 것이고,

결과값이 0.5보다 작은 (즉, 0에 가까운) 값들은 죄다 0으로 분류해 버리는 것입니다.

그러니깐 그냥 이제부터 Logistic (regression) classification이 아니라

logistic regression모델이라고 부르겠습니다.

그런데, 이렇게 Hypothesis를 바꿔버리면 원래 쓰던 cost function은 사용하지 못합니다.

왜냐 하면, 원래 쓰던 Cost function을 여기다가도 적용해버리면 non-convex한 function이 나오게 되기 때문입니다.

(cost function이 convex function이어야 하는 이유는 2강 (https://cding.tistory.com/21) 에서 다뤘습니다!)

+ 왜 그렇게 되는지는 나중에 부록편에서 따로 더 설명하겠습니다.

그래서 logistic regression의 cost function은 따로 만들어 줘야 합니다.

logistic regression의 cost function은 다음과 같이 정의합니다 : 

y=1일때 c(H(x), y) = -log(H(x))

y=0일때 c(H(x), y) = -log(1 - H(x))

(단, 여기서 log는 상용로그가 아니라 자연상수 e를 밑으로 갖는 자연로그입니다.)

그런데 왜 cost function을 이렇게 정의했느냐를 제대로 설명하려면 엄청난 수학의 압박이 느껴지게 됩니다...

그러니 일단 지금은 직관적으로 왜 cost function을 이렇게 정의하는지만 알아봅시다.

그냥 지금 간단하게 생각해 봅시다.

(위의 그래프들은 x축에 h(x)값, y축에 cost 값을 나타내는 그래프입니다!!)

일단 y=1인 경우, 즉 h(x) = 1인 경우엔 왜 cost function은 -log(H(x))가 될까요?

(왼쪽 그래프 참고)

h(x)값이 0에서 1으로 이동하면 cost 값은 ∞에서 0으로 점점 줄어들게 되는 것을 확인할 수 있습니다.

즉, h(x)가 정답인 1로 가면 갈수록 cost는 줄어들고, 오답인 0으로 가면 갈수록 cost가 늘어납니다.

이러면 우리가 원하는 합리적인 cost function이 완성된 것이겠죠?

반대로, y=0인 경우, 즉 h(x) = 0인 경우에 cost function이 -log(1-H(x)) 인 이유도 동일합니다.

h(x)값이 1에서 0으로 이동하면 cost 값은 ∞에서 0으로 점점 줄어들게 되는 것을 확인할 수 있습니다.

즉, 이번에는 h(x)가 정답인 0로 가면 갈수록 cost는 줄어들고, 오답인 1으로 가면 갈수록 cost가 늘어납니다.

그냥 이정도로만 이해해 주시고, 왜 cost function을 이렇게 설정했는지는 나중에 부록 편에서 다루겠습니다.

그리고 위처럼 y=1일때와 y=0일때로 나누어도 좋겠지만,

직접 컴퓨터로 연산을 할 때는 간단한 수식으로 나타내는 것이 훨씬 좋겠죠?

그래서 나온 공식의 위의 파란 박스가 쳐진 수식입니다.

어려울것 하나 없습니다!

y=0일 때는 -y * log(H(x)) 부분이 0이 되면서 자연스럽게 -log(1 - H(x)) 라는 cost function이 나오게 되고,

y=1일 때는 (1-y) * log(1 - H(x)) 부분이 0이 되면서 자연스럽게 -log(H(x)) 라는 cost function이 나오게 됩니다.

그리고 컴퓨터로 연산을 할 때는 if문을 사용해서 y==1인 경우와 y==0인 경우로 나누지 않고,

그냥 위의 수식을 사용하게 될 것입니다.

(위의 ppt의 Gradient decent는 오타입니다...ㅎㅎ;)

Gradient descent는 그냥 다른 모델과 동일하게 cost(W)를 W에 대해 미분하는 것으로 적용하면 됩니다.

그리고 이를 tensorflow를 사용해서 코드로 적용할 때는 그냥 GradientDescentOptimizer(a) 로 적용하면 됩니다.

(실제 cost값을 미분하면 어떤 값이 나오는지는 그냥 설명하지 않겠습니다. 매우 불필요합니다. 부록에서도 설명 안할듯)

이렇게 Logistic regression에 대해서 알아봤습니다.

사실 이렇게만 설명해도 Logistic regression이 어떤 개념인지는 모두 이해하셨으리라 믿지만,

나중에 부록편에서 조금 더 수학적으로 접근해서 왜 cost function이 저렇게 나오는지 설명하겠습니다.

그럼 다음엔 softmax regression (multinomial classification)으로 찾아뵙겠습니다!

- 본 포스팅은 CS234 4강의 내용을 정리합니다.

이번 강의에선,

- Generalized Policy Iteration

- Importance of Exploration

- Monte Carlo Control

- Temporal Difference (TD) Methods for Control

- Maximization Bias

등에 대해 배운다.

On-policy learning이란 직접 경험한 내용을 바탕으로 policy를 예측하고, 개선해 나가는 과정이다.

즉, Agent가 직접 행한 내용에 대해서만 학습을 하는 것이다.

Off-policy learning은 그와 달리 이미 알고 있는 내용들을 바탕으로 아직 실행하지 않은 내용까지 예측해서 policy를 개선해 나가는 것이다.

가령, 다음과 같은 state와 action에 대한 policy를 생각해보자:

s1, a1, s1, a1

s1, a2, s1, a2

off-policy learning의 경우엔 위의 두 가지 policy를 조합하여

s1, a1, s1, a2

의 policy도 수행할 수 있게 된다.

이제 Policy Iteration이 뭔지 다시 한번 불러와 보자.

Policy Iteration이 뭐였느냐 한다면...

우선 Vπ를 계산해 준 다음,

그 값과 Reward model R, dynamics P를 바탕으로 policy를 개선해 나가는 과정이었다.

(자세한 내용은 2강에서 확인하도록 하자.)

그런데, Policy Iteration의 경우엔, 정확한 Reward model과 dynamics(~~가 일어날 확률)가 필요했다. 

그래서 저번 강의에서는 model-free policy evaluation에 대해 설명했었는데,

이걸 한번 Policy Iteration에 써먹어 보도록 하자.

그래서 나온 것이 Model Free Policy Iteration이다.

아이디어는 그냥 Reward model과 dynamics를 Q function으로 합쳐버려서

Qπ를 계산하고 이 π를 개선해 나가면 되지 않을까? 하는 생각인 것이다.

이번엔 Monte Carlo for On Policy Q Evaluation에 대해 알아보자.

이는 저번에 배웠던 Monte Carlo for on policy value evaluation과 매우 유사한데,

원래 value evaluation에서는 N(s), G(s)를 썼지만,

Q Evaluation에서는 N(s, a) 와 G(s, a)를 사용한다.

(사실 어느 정도 당연한 이야기인데... Q는 state뿐만 아니라 action 또한 사용하는 function이기 때문이다.)

즉, 원래는 State만을 사용하던 것에서 벗어나서, State, action 쌍을 사용하는 것이다.

이 방식으로, Policy Improvement를 더욱 간단히 만들 수 있다.

그냥 Qπ(s, a)의 argmax를 취하면 그게 다음 policy가 되는 것이다.

그리고 이 방식을 사용하면 Policy Iteration을 매우 간단하게, 그리고 Model-free하게 만들 수 있다.

하지만, 아직 신경써야 할 부분이 있다. 바로 Qπ를 compute하는 부분이다.

만약 policy가 Deterministic 할 때는 policy 안에 특정 action이 존재하지 않는다면, 그 action에 대한 Q function은 절대로 계산하지 못한다.

(결국엔 Deterministic 하다면 policy에 있는 action만 따라가니깐..)

이를 해결하고 model-free한 Qπ를 계산하기 위하여, Exploration을 해야 한다!

이 때 사용할 수 있는 방식이 ε-greedy policy라는 것이다.

매우 간단한 아이디어인데,

1 - ε 의 확률로는 그냥 argmax Qπ(s, a)를 따르고,

ε의 확률로는 그냥 action a (랜덤한 action)를 따르는 것이다.

즉, 그냥 대충 확률적으로 딴 길로 샌다는 것이다.

그럼 지금까지 배운 내용을 확인해보자. (맨 아래 답이 이미 나와있는 것은 못본 걸로 하자.)

지금 까지의 예제와 비슷하게 Mars Rover의 예제를 사용한다.

그런데, a1의 경우엔 [1 0 0 0 0 0 10]의 reward를, a2의 경우엔 [0 0 0 0 0 0 5]의 reward를 갖는다.

또한, ε = 0.5이고, Trajectory = (s3, a1, 0, s2, a2, 0, s3, a1, 0, s2, a2, 0, s1, a1, 1, terminal) 이다.

이 때, First visit MC on policy Q의 값은 무엇일까?

간단하게 생각하자.

우선 a1을 취한 경우를 생각하면,

(s3, a1, 0, s2), (s1, a1, 1, terminal)의 두 가지 경우밖에 존재하지 않는다.

그리고, 𝛾=1이므로 지나온 모든 states에 final reward 1을 넣어 Q(-, a1) = [1 0 1 0 0 0 0]이 나오게 된다.

이 때 s2의 경우엔 a1의 action을 취하지 않았기 때문에 0이 들어가게 된다.

그럼 a2를 취한 경우도 생각하면,

(s2, a2, 0, s1)밖에 존재하지 않는다. (First-visit이므로 두 번 지나간건 생각하지 않는다. 사실 그거나 그거나 𝛾=1이라..)

그렇다면 위와 비슷하게, Q(-, a2) = [0 1 0 0 0 0 0]이 나오게 된다.

간단하지 않은가?

위는 ε-greedy Policy Improvement방식을 사용하면, policy는 제자리에 머무르거나 무조건 더 좋은 방향으로 갈 수 밖에 없다는 것을 증명한다.

그냥 공식으로 되어 있으니 딱히 쓸 말이 더 없을 것 같다...

여기서 GLIE (Greedy in the Limit of Infinite Exploration)에 대하여 나온다.

GLIE는 Exploration을 효율적으로 만드는 것을 목적으로 한 일종의 전략인데,

간단히 말하면 모든 (s, a)를 무한히 지나고 나면 policy를 greedy하게 만드는 것이다.

이에 대한 간단한 예로, ε의 값이 조금씩 줄어드는 ε-greedy를 생각할 수 있다.

가령, ε = 1/i로 두는 것이다.

이러면 i가 무한대로 발산하면 ε=0으로 수렴하게 되고, 결국 1-ε가 1로 수렴하게 되어 언제나 greedy한 선택을 하게 된다.

이런 방식을 바로 GLIE하다고 하는 것이다.

(좀 더 간단히 말하자면, 그냥 무한히 exploration을 지나면 greedy해지는 알고리즘을 의미한다.)

그리고 다음은 ε-greedy policy를 적용한 Monte Carlo Control 알고리즘의 의사 코드이다.

그냥 쭉쭉 읽어나가면서 이해하면 될 것 같고...

조금 신경쓸 부분만 짚어보자면,

2번째 줄. policy 를 ε-greedy(Q)로 initialize하고 있다.

6번째 줄. 위에선 First visit이라고만 적혀 있지만, Every-visit을 해도 된다.

7번째 줄. 원래 Monte Carlo면 N(s, a)가 아니라 N(s)였겠지만, On Policy Q Improvement 이므로 N(s, a)가 된다.

11번째 줄. GLIE하게 만들어 주기 위해서 ε = 1/k로 만들어준다.

이제 예제로 한번 알아보도록 하자.

언제나와 같이 Mars Rover의 예시인데,

Q(-, a1) = [1 0 1 0 0 0 0], Q(-, a2) = [0 1 0 0 0 0 0] 일때

optimal policy π(s)는 무엇이고,

k = 3, ε = 1/k 일 때 ε-greedy policy는 무엇일까?

optimal policy는 argmax Q(s, a)이므로, [a1, a2, a1, tie, tie, tie, tie] 가 된다.

참고 : state s4 이후에는 모두 Q(-, a1), Q(-, a2)의 값이 0으로 같으므로 tie가 된다.
만약 tie가 나온다면 무조건 a1을 고르거나 a2를 고르는 등의 방식도 있고 랜덤으로 하나를 고르는 방식도 있는데, 일반적으로는 랜덤으로 하나를 고르는 방식이 더 효율이 좋다.

또한, k=3, ε=1/k라면 ε-greedy policy의 경우

2/3의 확률로는 [a1, a2, a1, tie, tie, tie, tie] 를 따르고,

1/3의 확률로는 그냥 아무데나 갈 것이다.

이번에는 MC 방식이 아닌 TD 방식을 생각해보자.

어떻게 하면 model-free하게 TD방식을 만들 수 있을까?

아이디어는 또 단순하다.

TD방식과 ε-greedy 방식을 같이 사용하여 Qπ를 계산한 후에, (Policy evaluation)

π = ε-greedy (Qπ)로 두어 policy를 개선한다. (Policy Improvement)

이렇듯 TD methods에 ε-greedy policy를 적용한 것을 SARSA (states action reward states action 라는 뜻ㅎ;;)라고 한다.

간단히 SARSA가 뭔지 설명하자면 현재 state에서 action을 취한 뒤에, 다음 state에서 action을 취하고 나서 policy improvement가 이루어지는 것이다.

다르게 말하자면, 현재 (st, at) 쌍에서의 상태를 관찰한 뒤에, 다음 state st+1 에서의 action at+1을 취하고 나서,

그 뒤에 관찰한 값을 바탕으로 현재 policy π를 update 하는 것이다.

그 외의 나머지 부분은 MC 방식과 비슷하게 위의 알고리즘을 그냥 읽으면 될 것 같다.

참고로, 7번째 줄에 적혀있는 α는 learning rate이다.

이 방법의 장점으로는, 모든 episode를 다 돌지 않아도 금방금방 policy improvement를 진행할 수 있다는 것이다.

그렇기 때문에, 만약 episode 하나하나가 매우 길다면, 이 방식이 매우 효율적이게 될 것이다.

그때 그때 (s, a)쌍만 주어진다면 바로바로 policy improvement가 가능하기 때문이다.

이 부분은 조금 이론적인 부분인데,

위의 두 가지를 만족하는 α를 선택하면 SARSA는 무조건 수렴한다는 것인데,

실제 상황에서는 저런 값은 잘 선택하지 않고, 그냥 하나하나 경험적으로 집어넣어 본다고 한다.

(그러니까 그냥 이론적으로 알고만 넘어가라는 뜻 ㅎ)

Q-learning은 지금까지 배웠던 SARSA에서 아주 약간만 바꾼 방식이다.

원래 SARSA에서는 다음 state와 action 의 (st+1, at+1)의 쌍을 취해서 

원래 Q(s+1, at+1)였던 것을 max Q(st+1, a')으로 바꾸어 준 것이다.

그러니까, 다음 action을 고를 때 그냥 아무거나 고르는 것이 아니라, Q의 값이 최대가 되는 action을 고른다는 얘기이다.

그리고 Q-learning에도 ε-greedy Exploration을 적용할 수 있다.

사실 SARSA랑 너무 똑같아서 딱히 할 말이 없다.

그냥 중간에 Q(st+1, at+1) 이었던 것이 max Q(st+1, a)가 된 것 뿐이다.

그리고 ε-greedy policy를 Q-learning에 적용할 때도, 위의 MC의 경우와 마찬가지로

GLIE함을 만족하여야 optimal Q*와 optimal π*를 구할 수 있다.

그런데, 원래는 unbias한 Q function을 사용하더라도, max연산을 하면 π의 예측값의 value V는 bias해질 수도 있다.

왜 그러는지는 위에 annotation으로 적혀있는 수식을 확인하면 될 것 같다.

(참고 : 1번째 줄에서 2번째줄로 넘어가는 수식에서 부등식이 생기는 이유 : 옌센 부등식 https://ko.wikipedia.org/wiki/%EC%98%8C%EC%84%BC_%EB%B6%80%EB%93%B1%EC%8B%9D)

이를 보완하기 위해서 고안된 방법이 바로 Double Learning이다.

예측치의 최댓값가 실제 값의 최댓값의 예측치로 사용되는 것을 피하기 위해서 고안되었다.

(예측치의 최댓값 <= 실제 값의 최대값의 예측치 이므로)

그래서 Q를 하나를 쓰는게 아니라 두 개 (Q1, Q2)로 나누어 사용한다.

그 중 Q1은 max action a*를 선택하는데 사용하고,

Q2는 a*의 값을 예측하는데 사용한다.

이렇게 하면, estimator가 bias해지는 것을 방지할 수 있다.

위는 Double Q-Learning의 작동 과정을 간단히 나타낸 것이다.

물론 Double Q-Learning은 Q-Learning보다 메모리 및 연산이 더 많이 필요하게 될 것이다.

하지만 특정 상황에서 Double Q-learning은 Q-learning보다 훨씬 더 빠르게 optimal한 값에 수렴할 수 있게 된다.

후반부는 강의 내에서도 교수님이 그냥 후딱후딱 넘어가는 바람에 나도 설명 후딱후딱 해버렸다.

어째 지금까지 모든 강의가 다 시간이 부족해서 후반부는 빠르게 넘어가는 느낌이다.

아무튼, 다음 CS234 5강에서 보도록 하자.

저번 편 세줄요약

1. 작년에 엄청 설레서 정올 치러감.

2. 그런데 시험 치는데 몬가 좀 이상했음.

3. 그리고 학교로 돌아와서 채점을 하는데...

시험을 끝나고 대략 한 3일정도? 뒤에 답지가 나왔다.

내 기억상으로는 그 답지가 나왔다는 사실을 안 때가 딱 청소시간이었던 것 같다.

아니었나? ㅎㅎ;;

아무튼 친구들한테 채점을 해 보라고 막 말한 뒤에 채점을 하려도 답지를 연 순간

경악을 금치 못했는데...

이게 말이 되는 정답표인지 모르겠다.

그냥 대충 보더라도 알겠지만;;

정답 없음이 3개고

정답이 두개인것도 하나 있네? ㅎㅎㅎ....

사실 정답표가 나오기 전에도 어느 정도 시험이 개판이었는지 알았기 때문에 그렇게까지 놀랍지는 않았으나

이렇게까지 심각할 줄은 몰랐다.

채점 당시 마냥 웃기기만 하더라.

내가 어떤 문제를 맞았는지 틀렸는지 볼 겨를도 그 당시는 없었다.

그냥 "아... 그렇구나? ㅋㅋㅋㅋㅋㅋㅋ 정답이 없으면 뭐지? 맞은거겠지? ㅋㅋㅋㅋㅋㅋ"

라는 생각만 들더라.

그러고 나서 나중에 기숙사로 돌아가서 내가 틀린 문제들을 보기 시작했는데...

일단 6번 문제가 나는 뭔 문제였는지 채점 당시엔 기억 안났는데

기숙사 돌아가서 보니깐 시험때 다 풀고 나서 답이 없길래 당황했던 그 문제더라.

그렇다.

내가 잘못 풀었던 게 아니라, 답이 진짜로 없었던 거다.

마냥 웃기더라 ㅋㅋㅋㅋ;; 초반엔 그거 한문제만 붙들고 있었는데...

근데 이건 시작에 불과했다.

12번.

4팀이 한 조를 구성하여 한 팀이 같은 조 내의 다른 모든 팀과 한번 씩만 대결하는 리그 방식으로 축구 경기를 하여 상위 2 팀을 선발하려고 한다. 한 경기에서 이길 경우 승점 3점, 무승부일 경우 승점 1점, 질 경우에는 승점이 0점인 리그경기가 다 끝났을 때, 3위 팀이 가질 수 있는 최대의 승점은 얼마인가? 단 승점이 같을 경우에는 골 득실 등을 따져 순위를 가리며, 각 팀의 골득실차는 모두 다르다고 가정한다.

① 3  ② 4  ③ 5  ④ 6  ⑤ 7

한번 풀어보는 것도 나쁘지 않을 것 같다. 그렇게 어려운 문제도 아니니...

이 문제를 풀 때, 난 당연히 4번이라고 생각하고 쉽게 넘어갔다.

승승패 / 승승패 / 승승패 / 패패패

이러면 총 승패수 각각 6회씩이니까 3등 팀도 6점을 얻을 수 있지 않은가?

애초에 이런 일들은 실제 스포츠 세상에도 흔히 일어나는 일이다.

근데 위에 사진을 보면 알겠지만 답이 3번이라네?

기숙사 침대에 누워서 그걸 보고 나서 어이가 털리더라.

보통 이렇게 답이 틀리면 "아.. 그렇구나.. 할텐데"

워낙에 문제가 많던 시험이어서 그런지 "뭐래는거냐 얘는?" 하는 느낌이었다.

그리고;

https://www.fifa.com/tournaments/archive/mensolympic/sydney2000/matches/index.html

ㅇㅇ.. 답은 3번이 맞았던 것이다.

주최측에서는 단순 정답 오기라는데

좀 삐딱하게 보면 출제진조차도 문제의 답을 모르고 문제를 낸 것이고,

아무리 잘 봐줘도 국가 공인 올림피아드 시험을 보는데 답지에 정답 오기를 내는 실수를 범한 것이다.

이떄쯤부터 이 시험은 완전히 망했다는 것이 느껴졌다.

그냥 답이 없다.

그대로 그냥 답지를 꺼버리고, 그냥 인터넷에서 무슨 얘기들이 오가나 궁금해서 검색이나 해봤다.

그 중에서 내 기억 상에 가장 웃겼던 것들을 좀 보자면...

초등부 8번.

0에서 6까지의 자연수를 한 번씩만 사용하여 만들 수 있는 세 자리의 자연수는 모두 몇 가지인가? 

① 180  ② 190  ③ 200  ④ 210  ⑤ 220

일단, 초등학교에서 (사실 고등학교까지 모두... 현대수학 배우기 전 까지는 모두 다..) 자연수는 1 이상의 정수를 의미한다.

그러니까, 초등학생이건 중학생이건 고등학생이건 모두 0은 자연수가 아닌 걸로 배우는데

0에서 6까지의 자연수는 대체 뭘까?

음... 고민을 해 보도록 하자...

초등부 14번.

다음 프로그램의 출력 결과는 무엇인가? 

int x = 9, y = 11;
if (x < 10)
  if (y > 10)
    printf("A");
  else
    printf("B");
printf("C");

① A  ② AB  ③ BC  ④ AC  ⑤ ABC

초등부 24번.

x=9, y=11일 때, 다음 프로그램의 출력 결과는 무엇인가? 

if (x < 10)
if (y > 10)
  printf("A,");
else
  printf("B,");
printf("C");

① A,  ② A,B,  ③ B,C  ④ A,C  ⑤ C

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

저거 둘다 초등부 동일 년도 문제다.

아무래도 들여쓰기랑 ,(comma)가 들어가면 아예 다른 문제가 되는듯하다.

아니 대체 어떻게 동일한 시험지에 동일한 문제를 출제할 수 있는지 모르겠다.

아니 진짜로 어떻게... 말이 안나온다 ㅋㅋㅋㅋ

고등부 49번.

다음 프로그램의 출력 결과는 무엇인가?

#define INT_MAX 2147483647
#define abs(x) (x<0) ? x*-1 : x
int f(char *D)
{
  int n = 14;
  int B[14][14];
  bool A[14][14];
  int i, j, k, m;
  for (i = 0; i<n; i++) {
    A[i][i] = true;
    B[i][i] = 0;
  }
  for (m = 1; m <= n; m++) {
    for (i = 0; i<n - m + 1; i++) {
      j = m + i - 1;
      if (m == 1) A[i][j] = A[i][j];
      if (m == 2) A[i][j] = D[i] == D[j]);
      else A[i][j] = (D[i] == D[j]) && A[i + 1][j - 1]);
      if (A[i][j] == true) B[i][j] = 0;
    else {
      B[i][j] = INT_MAX;
      for (k = i; k <= j - 1; k++)
        B[i][j] = B[i][j] < (B[i][k] + B[k + 1][j] + 1)? B[i][j] : (B[i][k] + B[k + 1][j] + 1);
      }
    }
  }
  return B[0][n - 1];
}

int main()
{
    char D[] = "ababbbabbababa";
    printf("%d", abs(f(D)));
    return 0;
}

이것도 정말 답이 없었던 것이 뭐냐면,

코드 자체가 틀린 코드였다.

우선, 코드 중간에 괄호가 하나가 없어서 컴파일조차 되지 않는다.

그렇다. 주최측에서 코딩문제를 컴파일도 안돌려보고 문제를 낸 것이다.

뭐? 컴파일 해본 다음에 실수로 괄호 하나를 빠뜨린거 아니냐고?

아니, 실행을 안 시켜본게 확실하다.

왜냐하면 어떻게 괄호를 고쳐서 코드를 컴파일 하더라도,

답이 INT_MAX 인 2147483647로 나오기 때문이다.

이정도면 코드 실행 한번도 안 해 본게 느껴지지 않는가?

(그냥 저걸 답으로 쓰면 안되냐고? OMR카드에 2147483647를 쓸수 있겠는가???)

아니 대체가 어떻게 된게 코드 문제에 코드 실행도 안시켜보고 문제를 내는지 이해가 안될 따름이다.

아무튼..

수없이 많은 문제 오류들과 정답 기입 오류(;;) 들 끝에, 결국 정보 올림피아드 주최측은 사과문을 올리기에 이른다.

그리고 올라온 이의 신청 검토 의견서가 나오게 된다.

그리고 하는 변명들은 가히 전설적이라 할 만 한데,

그 중 몇가지만 써보자면....

<초등부 8번 문항>

‘0이 자연수에 속하는가’에 대한 이의 제기가 많았으며, 수학교육과 교수와 현장 교사 등의 의견을 참조하고 정보과학계의 입장을 반영하였습니다.

현대 수학에서는 일반적으로 자연수에 0이 포함되는 것에 대해 두 가지의 다른 정의가 함께 사용되고 있습니다. 일반적으로 정수론에서는 0을 제외한 ‘양의 정수’를 사용하며, 집합론과 컴퓨터과학(전산학)의 이산수학에서는 0을 포함한 ‘음이 아닌 정수’를 자연수로 정의하여 사용하고 있습니다. 이러한 혼란 때문에 통상적으로 대부분의 책과 논문 등에서는 자연수에 대한 정의를 먼저 제시하고 내용을 전개해 나가고 있습니다. 본 문항의 지문에서도 ‘0에서 6까지의 자연수’라고 먼저 제시하였고 또한  0을 자연수에서 제외하고 문제를 푼 경우에 해당하는 답안이 보기에 존재하지 않으므로 혼란의 여지는 없습니다.

초등부 전체 응시자의 73.8%가 ‘0을 자연수라고 가정’하고 문제를 풀어 보기를 선택하였으며, 나머지 학생은 전혀 관계없는 오답을 선택하였습니다. 다만, 0이 자연수가 아니라고 가정하여 이 문제에 대한 답변을 아예 하지 않을 학생이 있을 가능성도 검토하였으나 전국대회 진출 여부에는 영향을 주지 않는다는 사실을 확인하였습니다.  

?

???

?????????????

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

초등부 문제에서 현대 수학에서 자연수의 정의와, 집합론과 컴퓨터과학의 이상수학의 자연수에 대한 정의를 알고 있어야 하나?

또, '0에서 6까지의 자연수' 라고 기입되어 있으면 그게 자연수의 정의를 제시한 것인가?

뭐지? 미친건가??

그럼 대부분의 책과 논문 등에서 "0 이상의 자연수에 대하여" 라는 한 문장만 존재하면 자연수의 정의를 다 한것인가?

정말 주최측의 설명이 이해가 잘 가고 납득이 될 따름이다.

44번.

한 컴퓨터회사의 구성원은 사장 1명과 직원들로 구성되어 있고, 회사의 각 직원은 최대 3명까지의 부하직원을 둘 수 있다. {X, Y, Null}의 표현은 두 명의 부하직원 X와 Y가 있으며, 없는 경우는 Null로 나타낸다. 또한 부하직원이 하나도 없으면 {Null, Null, Null}로 나타낸다. 만일 그 컴퓨터회사 모든 직원의 조직도에서 Null의 총 개수가 10인 경우, 최소 직원 수는 몇 명인가? 단, 사장의 직속상관(바로위의 상관)은 없고, 직원들의 직속상관은 1명이다.

① 2  ② 3  ③ 4  ④ 5  ⑤ 6

화두는 "사장도 직원에 속하는가?" 였는데,

그에 따른 주최측의 설명은 다음과 같다:

<중등부 8번 문항 / 고등부 44번 문항>

본 문항에서 회사의 구성원을 사장 1명과 직원들로 분리하여 설명하였기 때문에 사장은 직원에 포함되지 않고 {X, Y, Z}형식은 직원들에게만 해당됩니다. 따라서 직원들의 조직도에서 Null 개수가 10개를 만족하는 최소 직원의 수를 도출할 수 있습니다.

????????????

회사의 구성원을 사장 1명과 직원들로 분리하였기에 사장은 직원이 아니라고?

그럼 문제에서 "각 직원은 최대 3명까지의 부하직원을 둘 수 있다." 는 뭐지?

사장은 직원이 아니니깐 부하직원을 두면 안되는데? 아니 애초에 사장 얘기는 왜한걸까?

아니 그보다도, 사장 1명과 직원들로 분리하여 설명하면 사장은 직원이 아니라는건가?

동물들과 닭 한마리 이러면 닭은 동물이 아닌건가? 난 잘 모르겠는데;

아니 애초에 저게 사장 1명과 직원들로 분리한거 맞나? 그렇다기엔 너무 문장력이 떨어지는 느낌인데;;

+나는 어차피 모르고 풀어서 할말 없지만, 아무튼 이해가 안되던 문제가 11번이었다.

11번.

n 개의 수들을 가지고 완전 이진트리를 만들 경우 이 트리의 높이는 얼마인가?

① log2n 의 버림 값 ② (log2n)3 의 버림 값 ③ (log2n + 1) 의 버림 값 ④ (log2n - 1) 의 버림 값 ⑤ (log2n)2 의 버림 값

(log뒤의 2는 로그의 밑이다.)

이 문제에서, 완전 이진트리의 높이를 정의하지 않고 그냥 넘어가고 있다.

노드 한 개만 있는 상태는 높이가 몇인걸까?

이에 대한 해답은,

<고등부 11번 문제>

완전 이진트리는 루티드 트리(rooted tree)입니다. 루티드 트리에서 레벨(level)이라는 개념은 기본 정의가 없고, 깊이(depth)와 높이(height)는 정의가 있습니다. 깊이는 노드에 대해서만 정의되고, 높이는 노드, 트리 모두에 대해서 정의되는데 주어진 트리의 높이는 그 트리의 루트노드의 높이로 정의됩니다. 노드의 높이는 그 노드에서 연결된 가장 멀리 떨어진 단말노드(leaf node)까지 존재하는 가장 긴 경로에 존재하는 간선들의 수로 정의됩니다. 따라서 본 문항에서 노드가 1개일 경우 높이는 0입니다. 위의 정의에 따라 정답을 도출할 수 있습니다.

※ (참고자료) Introduction to Algorithms, MIT press, 3rd edition, page 1177

그렇단다.

아니 그런데 애초에, "공교육 기반 문제 출제"를 약속해 두고,

이의신청 검토 의견서에 참고자료랍시고 MIT에서 발행한 책을 두는건 이해가 잘 가지 않는다.

뭐하자는 거지?

+ 49번 단답식 문항의 답변.

<49번 단답식 문항>은 지문에 제시된 C코드에서 ‘(’ 부호 하나가 빠지게 된 편집오류에 해당합니다. 그 부호가 없더라도 정답을 유추할 수 있었겠지만, 코드오류가 명확하다고 판단하여 ‘정답없음’으로 처리하였습니다.

'(' 부호 하나가 빠진게 문제가 아니고 코드 자체의 오류가 문젠데 꼭 '(' 부호 하나 없어서 정답없음 처리한 듯이 써놨다.

놀라울 따름이다.

그리고, 그렇게 나는 그렇게 인생 첫 정올을 망치게 되었다.

나는 대략 커트라인에서 5점정도 떨어진 점수를 받고 전국 진출도 떨어지게 되었다.

하지만 본선 진출은 사실 시험 치기 전부터 알고 있었기에 별로 기분이 나쁘진 않았는데,

인생 첫 올림피아드를 나갔는데 이따구로 시험이 출제된 것 자체가 많이 억울하고 씁쓸했다.

추가하자면, 사실 전국대회 본선도 문제가 좀 많았다고 한다.

채점이 심하면 1시간까지도 미뤄졌다는 얘기가 있는데,

나는 전국대회에 나가보지 못했기 때문에 따로 할 말이 없다.

그냥 나무위키 가서 보도록 하자 ㅎㅎ...

....이것으로 2018년 정보올림피아드 시험을 봤던 후기를 끝내도록 하겠다.

뭔가 시험 후기가 아니라 문제까기에만 급급했던 것 같은데,

사실 시험 보면서, 그리고 시험이 끝나고 한 생각들이 온통 저런것들 뿐이어서....

나중에 시간이 된다면 어제 치뤘던 2019 정올 관련 후기도 올리도록 하겠다.

? 작년에 저렇게 개판을 쳤는데, 올해는 어떻게 잘 했냐고?

뭐, 그럭저럭 잘 했다.

1교시 까지는 ㅋ

아무튼 이에 관련된 후기는 나중에 올리도록 하겠다.

ㅃㅃ

* 쓰다 보니 너무 길게 써져서 2편으로 나누겠습니다. 사실 올해 정올 썰 풀려했는데;;

세줄요약

1. 작년에 엄청 설레서 정올 치러감.

2. 그런데 시험 치는데 몬가 좀 이상했음.

3. 엌ㅋㅋㅋㅋ 이게 올림피아드냐??? ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

작년, 디미고 입학 이후 꼭 한번 가보고 싶었던 정보올림피아드를 나갔었다.

그 당시, 말 그대로 배운 것도 거의 없는,

그냥 독학으로 딱 간단한 DP 짜는 법만 배운,

학교에서도 C언어 기초만 배운 정도의 상태에서 시험을 보러 갔다.

물론 그 당시까지만 해도 경시 예선에 프로그래밍 문제도 없어서

가벼운 마음으로, 그냥 시험을 치러 갔었다.

그런데...

https://namu.wiki/w/%ED%95%9C%EA%B5%AD%EC%A0%95%EB%B3%B4%EC%98%AC%EB%A6%BC%ED%94%BC%EC%95%84%EB%93%9C#s-3.4

(나무_위키) 

작년 정올이 개똥이었다.

개인적으로 그 때 기억을 되살려서 그 때 어땠는지 대충 말해보겠다.

https://www.acmicpc.net/jungol/2018/3

작년 정올 문제와, 그에 대한 의견들 (이라고 쓰고 오류까기 댓글)

처음 시험장에 들어가서 시험을 보려고 할때 까지만 해도 마냥 설렜었다.

시험 당시의 작년도, 제작년도 문제들도 다 풀어봐서

그런 식으로 문제가 출제될 줄 알고,

또 그 정도로 재밌게 문제가 나올줄 알았다.

그리고 사실 처음에는 그렇다고 생각했다.

그런데

6번문제를 풀다보니 답이 안나오는 것이었다.

난 솔직히, 내가 잘못푼 줄 알았다.

어떻게 푸는지 몰라서 막 풀었는데

답이 안나오니 시간은 끌리고 답답해 죽겠고...

결국 그냥 내가 1 잘못 더했나보지 하고 5번을 체크하고 넘어갔었다.

그런데 시험 끝나고 보니까 그게 문제오류였다네??

정답이 없는게 맞다네??

아무튼... 그 당시엔 그런거 몰랐으니까 넘어가고

11번 문제.

"n 개의 수들을 가지고 완전 이진트리를 만들 경우 이 트리의 높이는 얼마인가?"

그 당시 기준 약 3개년 기출을 풀어보면서, 이런 문제는 처음 봤다.

2018년 당시 정보올림피아드는 일반인도 풀 수 있게 (전문 교육 안받아도 학교 교육으로도 풀 수 있게) 시험을 내겠다고 했다.

그런데 지금까지 나온적도 없는 완전 이진트리 문제를 들고 왔다.

아까도 말했다시피, 나는 그 당시 완전 노베라 완전 이진트리가 뭔지 정확히도 몰랐다.

그래서 그냥 걸렀다. (나중에 또 나올 문제입니다.)

그리고 13번 문제.

보자마자 걸렀었다.

혹시 궁금할까봐 문제를 좀 써보자면,

"다음 표에서 X에 들어갈 수는 무엇인가?"

① 175  ② 235  ③ 280  ④ 344  ⑤ 388

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

진짜 솔직히 거를만 하지 않았나 싶다.

애초에 사고력이 얼마나 좋은지 대결하는 시험에서

저딴 문제를 낸다고?

심지어 저거 문제 진짜 그대로 쓴거다.

특정 규칙이 있다는 말 하나 없이 저렇게 나왔다.

저러면 대체 답을 어떻게 구하라는 건가?

그냥 까놓고 말해서, 왼쪽 위와 오른쪽 아래가 대칭인 표라고 해도 할 말 없지 않나?

대충 숫자 몇개 넣어보다가 때려쳤다.

그럼 규칙이 명확하면 또 모른다.

1 1 2 3 5 8 13 21 X 55 ...

에서 X에 들어갈 숫자는? 

이렇게라도 냈으면 거의 다들 별 말 없이 진행했을 텐데,

저 위의 저 표는 대체 뭘 보고 유추하라는 건지 모르겠다.

백준님의 댓글을 인용하자면,

"의도한 정답은 다음과 같다고 합니다.

칸 (i, j)에 들어있는 수는 (1, 1) ~ (i, j) 에 있는 수의 합

즉, (3, 3)이 42가 나오는 이유는 1 + 2 + 3 + 2 + 5 + 13 + 3 + 13 입니다."

와... 정말 너무 명확하고 일반적인 규칙이었어요!!! 대단합니다!!

..쓰다보니 화나서 문제 하나에 너무 길게 써버린 것 같다.

아무튼 이런 문제를 보자마자 정말 기가 차고 놀라워서 그냥 때려치우고 다음 문제로 넘어갔다.

14번.

"n 개의 수들을 가지고 최대 이진 힙 데이터 구조를 만들 경우 높이 h 에 위치하는 노드들의 최대 수는?"

보편적 공교육에서는 최대 이진 힙 데이터 구조와 완전 이진 트리를 배우나 보다.

정말 난이도가 개선되고, 또 공교육을 받은 학생들도 정말 풀 만하게 나오지 않았는가?

역시 초중고교 현직 교사가 문제 출제 및 검수위원으로 참여해서 그런지 더 훌륭해 보인다.

(심지어 이 문제에는 다른 이슈도 있었는데 그건 나중에...)

아무튼, 계속 문제풀이를 진행했다.

이 뒤쯤부터는 C언어로 코딩한 것을 분석하거나 하는 문제였는데,

문제가 내가 지금껏 보던 문제들과는 달랐다.

원래 아까 말했다시피, 문제들이 다들 되게 재밌었다.

풀다 보면 빡치는 문제들도 있긴 했지만 변별력 문제들만 그랬고,

다른 문제들은 곰곰히 생각하며 푸는 문제들이었는데...

20번.

다음 프로그램 중 주어진 문자열의 길이를 정확하게 출력하는 것은?

int i;
char s[] = "hello";
for(i=0; s[i]; ++i);
printf("A: %d ", i);
i=0;
while(s[i++]);
printf("B: %d ", i);
return 0;

① A 만 옳은 값을 출력한다

② B 만 옳은 값을 출력한다

③ A,B 모두 옳은 값을 출력한다

④ 모두 옳은 값이 아니다

⑤ 컴파일 에러가 발생한다

21번.

다음 프로그램의 출력 결과는 무엇인가?

char    str[] = "Welcome";
char* s = str;
while(*s)
printf("%c", *s++);

① Welcome   ② elcome   ③ 0   ④ Wel   ⑤ come

이게 왜 어떠냐고?

들여쓰기가 보이는가?

필자가 들여쓰기를 안 한 것이 아니다.

그냥 문제가 진짜로 저렇게 나왔다.

세상에 대체 누가 저따구로 코딩을 하는가?

열심히 곰곰히 생각해서 푸는 문제가 아니라, 

그냥 헷갈리라고 막 던져놓은 문제다.

아니 애초에 저런 문제는 나도 만들 수 있다.

사고력을 시험하겠다면서 무슨 들여쓰기도 안한 코드를 문제로 내는가?

저런문제가 한둘이 아니다.

27번.

다음 프로그램의 출력 결과는 무엇인가?

int num, temp1, temp2;
int A = 2;
int B = 12;
num = ((temp1 = B / A++) + (temp2 = B / ++A)) + ++B;
printf(“%d”, num);

① 20  ② 21  ③ 22  ④ 23  ⑤ 24

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

뭐가 문젠지는 딱 봐도 알겠지만 대충 나열하자면...

1. 이게 사고력이랑 무슨 상관이며,

2. 전/후위 증가를 물어보는 문제라고 하더라도 저따구로 코딩하는 사람은 아무도 없으며,

3. 심지어는 undefined behavior이기 때문에 어떻게 결과값이 나올지는 아무도 모른다. 심지어, 컴파일러에 따라 값이 다르게 나온다!

= 문제 질이 쓰레기다

이쯤부터 나는 무언가가 잘못되었다고 느끼고 있었다.

그러던 와중, 정확한 시기는 기억 안나는데

대충 중반이었으니 이때쯤 아니었을까 싶다.

갑자기 방송으로 오타 및 오기 방송을 하기 시작했다.

처음에는 "어라? 오타가 좀 있나보네" 하는 눈치로 오타를 고치기 시작했는데...

진짜 양심에 손을 얹고, 10~20문제 가량에 오타가 있었다.

장난이나 과장이 아니다.

첫 5문제정도는 "와 오타 많네 ㅋㅋㅋㅋ" 이러고 있었는데,

10문제정도 되니깐 "????? 뭐지 애내들 시험지 검수 안했나?" 하는 생각이 들더라.

진짜 고치면서 웃겨서 웃었었다.

다시 말하지만, 이거 국가 공인 올림피아드다.

일개 쪽지시험도 오타가 이렇게 많게는 안나온다.

더 충격적인 사실이 무엇이냐면,

이렇게 고치고도 시험이 끝날때 까지 정정해 주지 않은 오타들이 수두룩 빽빽 했었다는 것이다.

진짜 이쯤되면 답이 없다.

28번.

다음 프로그램의 출력 결과는 무엇인가?

int a = 3;
if (a = 4)
   printf(“A”);
else
   printf(“B”);
if (a = 0)
   printf(“C”);
else
   printf(“D”);

① AD  ② AC  ③ BC  ④ BD  ⑤ CD

엥? 이게 왜 문제냐고?

나도 처음엔 왜 문젠지 몰랐다.

근데, if문 안을 자세히 보면...

대입 연산자를 넣어쳐놨다.

아니 그래서 이게 대체 사고력 향상이나 그런거에 어떤 의미가 있는걸까?

이건 그냥 코드를 한줄한줄 아주 정성스럽게 읽어서 풀라는 의미 아닌가?

그냥 누구 눈썰미가 더 예리한가

틀린그림찾기 시합이 아닌가?

사실 처음엔 그냥 BD인줄 알았다가, 나중에 검토하다 답을 알게 되었다.

이쯤되면 한국눈썰미올림피아드로 이름을 바꿔야 된다.

29번.

다음과 같이 함수 f를 구현했을 때, f(5,12)의 값은?

int f(int m, int n) {
  if(n<=0 && m<=0) {
    return 1;
  }
  else {
    if(n >= m)
      return f(n-2,m)+f(n-3,m);
    else
      return f(n,m-3);
  }
}

① 73  ② 74  ③ 75  ④ 76  ⑤ 77

이건 그냥 간단히 짚고 넘어가겠다.

2점짜리 문제다.

이게 위의 28번 문제와 배점이 동일하다.

문제의 난이도가 같다고, 아니면 엇비슷하기라도 하다고 생각하는가?

본인의 생각에 맡기겠다.

그리고 본인이 이 시험이 매우, 굉장히, 엄청나게 이상하단걸 깨달은 문제가 바로 36번 문제인데...

36번.

a=1, b=0, c=-1 일 때, 다음 프로그램의 출력 결과는 무엇인가?

int i = 5;
if(a<b<c){
for(i--; i--; i--)
   printf(“%d ”, i);
} else {
for(i--; --i; i--)
   printf(“%d ”, i);
}

① 4 2 0   ② 3 1 -1 -3 5 ...   ③ 3 1   ④ 4 2 0 -2 4 ...   ⑤ 5 3 1

필자는 이 문제를 풀면서 진짜 어이가 너무 없었다.

if (a<b<c)라는 말도 안되는 undefined behavior를 사용한다.

아니 무슨;;; 저딴 개짓거리를 누가 실무에서 쓰고

또 누가 알고리즘 문제에 쓰는지 정말 궁금하기만 할 따름이다.

거기다가, 누가 대체 for문 안에 저따구로 쳐 써넣는가?

for (i--; i--; i--)

이딴거 쓰는거 본적 있는가?

이것도 다른 거지같은 문제들과 마찬가지로, 정말 실무에서 쓰면 바로 쫓겨나고, 애초에 쓸 일도 없는 문법으로,

그냥 간단히 문법 어거지로 꼬아서 답이 뭐가 나오는지 물어보는 셈이다.

게다가 저 문제, 들여쓰기도 이상하지 않은가?

재차 말하지만, 필자의 오기가 아니라

진짜로 시험에서 들여쓰기를 저따구로 해서 나왔다.

근데 사실 진짜 문제는 그게 아니다. (그래서 더 웃긴거다 ㅋㅋㅋㅋㅋ)

사실 시험장에서 필자가 문제를 풀 때, 저 쯤 되니 그냥 그러려니 하고 넘어갔다.

(사실 이때쯤에는 해탈했다. 문제의 질부터 오타 수두룩빽빽한거 까지...)

저 문제를 풀면, 답은 3 1 -1 -3 -5 ..... 가 나온다.

그러면 저 5개의 답지중에 무엇이 정답이겠는가?

2번이라고?

좀만 더 자세히 보자.

2번은 3 1 -1 -3 5 라고 적혀 있다.

저것도 마찬가지로 필자가 낸 오타나 오기가 아니다.

진짜 시험지에 저렇게 적혀 있었다.

이 문제로 필자는 시험장에서 감독관에게 이건 너무 확실히 오타가 아니냐고 물어보았으나,

돌아온 대답은 "대답할 수 없고, 추후에 이의신청을 넣으시기 바랍니다" 였다.

그리고 답안이 애초에 아니어서 검토를 안한 4번도 잘 보기 바란다.

4 2 0 -2 4 ...  라고 쓰여 있다.

아니 애초에 답이 될 수도 없는데 답지에는 왜 집어넣은걸까? 이게 진짜 의도였을까?

아 뭐 질문했는데 주최측에서는 문제 없다하니...

진짜 답도 없다는 생각을 했다.

그냥 문제 질부터 답까지 죄다 틀려먹은 문제다.

43번 문제도 의견이 조금 달려있는데, 필자는 딱히 생각없이 풀어서... 그냥 문제가 왜이렇게 더러운가 생각하며 풀었었다.

44번.

한 컴퓨터회사의 구성원은 사장 1명과 직원들로 구성되어 있고, 회사의 각 직원은 최대 3명까지의 부하직원을 둘 수 있다. {X, Y, Null}의 표현은 두 명의 부하직원 X와 Y가 있으며, 없는 경우는 Null로 나타낸다. 또한 부하직원이 하나도 없으면 {Null, Null, Null}로 나타낸다. 만일 그 컴퓨터회사 모든 직원의 조직도에서 Null의 총 개수가 10인 경우, 최소 직원 수는 몇 명인가? 단, 사장의 직속상관(바로위의 상관)은 없고, 직원들의 직속상관은 1명이다.

자, 자...

사장은 직원일까? 아닐까?

재밌는 점은, 사장을 직원으로 생각하면 문제의 답은 나오지 않는다.

그러므로, 사장은 직원이 아니다.

그러면 이쯤에서 의문이 생긴다.

사장 언급은 왜 한걸까?

사실 사장 언급 안해도 그냥 풀리는 문제를, 굳이 사장 언급을 해놓고 앉았다.

왜인지는... 나도 모르겠다. 문제를 꼬는 것도 아니고... 그냥 일부러 문제 애매하게 내는거에 맛들렸나?

이 이후부터는 솔직히 생각없이 막 풀어서 문제를 풀 때 아무 생각도 안했다.

사실 49번 문제는 풀기 귀찮아서 대충 풀고 거른 것도 있다.

아무튼 그렇게 시험을 마치고 집으로 돌아왔다.

처음 보는 정올 시험인데 이렇게 마치고 돌아온게 조금 짜증나고 억울한 면도 있었지만,

그래도 시험 마치고 돌아오는 길에는 기분이 어느 정도 괜찮았던 것 같다.

그리고 나서 대망의 답 공개일이 다가오고....

학교에서 친구들과 가채점용으로 써 온 답안지로 채점을 하게 되는데...

...쓰다 보니 너무 길어진 관계로 답 공개 이후는 2편에서 계속하도록 하겠다.

본 포스팅은 강화 학습 강의인 CS234 2강의 내용을 정리합니다.

매우 간단하게 용어 정리 및 공식만 적으므로, 자세한 내용은 강의 정리 포스팅을 보시기 바랍니다.

Markov Process : Markov한 상태를 띄는 Action / Control이 없는 random한 state들의 집합.

이를 행렬으로 나타낸 것을 Markov Chain 이라고 부른다.

Markov Reward Process (MRP) : Markov Process + Reward.

Markov Process에다가 Reward를 추가함. 

Horizon : 각각의 에피소드에 대한 time step의 개수.

Return function (Gₜ) - time step t부터 horizon까지의 reward의 discounted sum.

State Value Function (V(s)) - state s에서 얻을 수 있는 reward의 기댓값.

Discount Factor (𝛾) - immediate reward (즉각적 보상)과 future reward (미래에 얻을 보상)과의 연관관계.

0이면 연관 없음, 1이면 immediate = future

일반적으로 MRP value를 계산하는데 Dynamic Programming 방식이 사용됨. (Iterative Algorithm이라고도 함.)

Vₖ(s) = R(s) + 　∑s'∈S 𝛾P(s'|s) Vₖ₋₁(s')

(위 ppt에 더 정확하게 나와있음.)

Markov Decision Process (MDP) - MRP + Action.

이젠 Action까지 포함되어 있음.

(S, A, P, R, 𝛾)의 튜플로 표현함.

지금까지의 기호들을 설명하자면,

S는 Markov State s의 집합.

A는 actions 의 집합.

P는 각 action에 따른 dymanics/transition model. (위의 MRP / MP와 다르게 action이 포함되어 있음!)

R은 Reward function으로, 각 state와 action에 따른 reward의 기댓값.

𝛾는 Discount Factor.

Policy : 각각의 state에서 어떤 action을 취할지를 선택하는 것. (그냥 말 그대로 정책이다.)

Deterministic : 결정론적임. 취하고자 하는 행동은 무조건 일어남.

Stochastic : 무작위적임. 취하고자 하는 행동이 확률적으로 일어나거나 일어나지 않을 수도 있음.

MDP + Policy = MRP이다.

이를 활용하여, MDP의 Policy Evaluation에서도 MRP와 비슷한 공식을 응용할 수 있다.

MDP Control : optimal policy를 계산함.

이때 optimal policy는 π*(s)로 표현함.

optimal policy는 유니크한 optimal value function을 가짐.

Policy Iteration : optimal policy를 구하기 위한 Iterative Algorithm.

현재 policy가 특정 값에 수렴할 때까지 지속적으로 policy를 바꿔준다.

State-Action Value Qπ(s, a)

Qπ(s, a) = R(s, a) + 𝛾∑s'∈S P(s'|s, a)Vπ(s')

로 정의되는 함수.

Policy Improvement : Policy를 강화함.

모든 state와 action 중에서 Qπ(s,a) 값이 가장 큰 state s,action a를 구해서 그 값들을 policy로 적용시킴.

즉, Policy Iteration (PI) 는 다음과 같은 행동을 반복한다.

πᵢ의 값 V을 구한다.

그 값을 사용하여 Q(s,a)도 구한 뒤,

Policy Improvement를 사용하여 πᵢ₊₁을 구함.

이를 ||πᵢ - πᵢ₋₁||₁ > 0 일 때까지 (즉, 새로운 policy와 저번 policy의 차이가 없을 때까지) 반복함.

이러면 optimal policy를 찾아낼 수 있다!

(위 세 슬라이드는 수학적 내용임으로 설명하진 않으나, ppt를 보면 이해가 갈 것임.)

Value Iteration (VI) : Value를 활용하여 optimal policy를 구하는 방법.

V의 값이 수렴할 때 까지,

최대의 Reward가 나오는 R(s, a)와 𝛾∑s'∈S P(s'|s,a)Vπ(s') 를 더한 값을 V에 집어넣어줌.

PI와는 다르게 Policy Improvement 과정 없이 진행됨.

해석본은 아래 글에 있습니다. 여기서는 풀이만 하도록 하겠습니다.

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

optimal value function V(s) = R(s) + 𝛾Σ s'∈S P(s'|s)V(s') 이다.

이 때, action은 무조건 오른쪽으로 가는 것이고, deterministic한 상황이기 때문에 P(s'|s) = 1이 된다. (s'의 경우의 수는 1개이다.)

이를 정리하면,

V(s) = R(s) + 𝛾Σ s'∈S V(s')

이 때, s'은 s의 바로 오른쪽 (s=G일 때는 G)가 될 것이다.

이를 사용해 goal state G에서의 optimal value function을 구해 보면,

V(G) = R(G) + 𝛾Σ s'∈S V(G)

V(G) = 1 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

       = 1/(1-𝛾)             (등비급수)

V(sₙ₋₁) = R(G) + 𝛾Σ s'∈S V(s')

         = 0 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

         = 𝛾/(1-𝛾)

......

V(s₁) = 0 + 0 + 0 + ... + 𝛾ⁿ + 𝛾ⁿ⁺¹ + ....

       = 𝛾ⁿ / 1-𝛾

(b) optimal policy가 discount factor 𝛾의 영향을 받는지에 대해 서술하시오. [5점]

optimal policy의 경우, 0<𝛾인 모든 상황에서는 위의 '무조건 오른쪽으로 가는' action을 취할 것이다.

하지만 𝛾=0인 경우엔 0<𝛾인 경우와 비슷하게 무조건 오른쪽으로 가는 action만을 취하겠지만, 그 policy 말고 다른 policy 또한 optimal policy가 될 수 있다.

(오른쪽 왼쪽 오른쪽 오른쪽 오른쪽 .... 도 optimal policy라 할 수 있다.)

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

영향을 끼치지 않는다.

직관적으로 보자면, 어떤 상수 c를 더한다고 해도 결국 reward가 가장 큰 것을 G일 것이므로,

optimal policy는 언제나 오른쪽으로 가는 action을 취하는 policy이라는 점은 변하지 않는다.

optimal value function을 구하면,

c를 더한 V(s)를 new_V(s), 원래 V(s)를 old_V(s)라 할때,

new_V(s) = old_V(s) + c + 𝛾c + 𝛾^2c + .... 

            = old_V(s) + c/(1-𝛾)

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

우선 위의 방식으로 optimal value function을 구하면,

new_V(s) = a * (old_V(s) + c + 𝛾c + 𝛾^2c + .... )

            = a * old_V(s) + ac/(1-𝛾)

가 된다.

이 때 a>0이라면 optimal policy는 원래와 같이 goal state G로 곧장 가는, 무조건 오른쪽으로만 가는 policy가 될 것이다.

a=0이라면, 모든 reward가 0이 되므로 모든 value function과 policy가 optimal 해 진다. (바람직하진 못하겠지만)

a<0이라면, goal state G가 가장 낮은 reward를 갖게 되므로, goal state G를 거치지 않는 모든 policy는 모두 optimal policy가 될 것이다. (즉, G를 지나는 policy는 optimal 하지 못하다.)

또한, c의 값은 어떻게 변해도 아무런 영향을 끼치지 않는다.

Assignment 1 중에서 가장 쉬운 난이도 문제였습니다.

Value function의 공식을 알고 있는지,

Optimal policy와 Optimal value function의 개념을 알고 있는지,

그리고 value function의 공식을 응용할 수 있는지에 대해 묻는 문제들이었습니다.

사실상 공식에 대입하는 문제였네요 ㅎㅎ

오늘은 디미고 학생들의 노트북 관련 이야기를 하려고 한다.

노트북을 어떻게 쓰는가에 대한 이야기 말고,

그냥 어떤 노트북들을 들고 오는지에 대해, 그리고 어떤 노트북을 들고 오는 것이 좋을지에 대한 이야기이다.

학생들이 가장 많이 가지고 오는 노트북으로는 LG 그램과 삼성 오디세이가 있다.

보통 게임을 아예 안 할 생각으로 학교 오는 얘들은 LG 그램을 들고 오고,

게임을 조금 하진 않을까 하는 얘들은 삼성 오디세이를 고르는 것 같다.

장단점을 꼽아보자면...

LG 그램은 가볍고 얇으며 배터리가 오래 간다.

그래서 들고 다니기에 무리가 별로 없고, 쉬는 시간에 노트북으로 뭔가를 하다가 서랍에 집어넣기에 용이하다.

또, 연달아서 서너시간 동안 전문교과 수업을 듣더라도 충전기를 꼽을 필요 없이 계속 노트북을 사용할 수 있다.

하지만, GPU가 그렇게 좋지 않아서 사양 높은 게임을 돌리진 못하고 (학부모님들한테는 장점이 될수도 있긴 할듯 ㅎ)

내구성이 약간 떨어져서 잔고장이 조금 있는 편이다. (다만 AS가 좋아보이긴 했다.)

그리고 무엇보다도, 성능대비 가격이 조금 비싸다. 무게를 얻고 성능과 가격을 버린 느낌이다.

삼성 오디세이는 LG 그램과 정반대라고 보면 된다. (가격 제외)

GPU가 꽤 좋아서 성능이 잘 나오고, 가성비가 그렇게까지 나쁜 편은 아니다.

하지만 배터리가 별로 좋지 않아서 웬만하면 충전기를 들고 다녀야 하는 편이고,

조금 무거워서 들고 다니기 버겁다.

성능 대비 가격은 그램보다 낫긴 하지만, 그냥 가격만 놓고 보면 비슷한 수준인 것 같다.

개인적인 의견으로는 삼성 오디세이 살 바엔 그냥 LG 그램 사는게 나아 보인다.

개인차는 있겠지만 오디세이 산 친구들한테 물어보면 별로 안좋다고 하는 것 같고,

애초에 학교에서는 사양이 높은 게임을 별로 돌릴 일이 없다.

해봤자 카트나 피카츄배구 같은거나 하고 있는지라...

(사실 애초에 게임을 할 일 자체가 별로 없다... 개인차는 있겠지만)

또, 가벼운 것 보다도 배터리가 오래 가는 것이 꽤 괜찮아 보인다.

1학년때는 별로 체감이 안됐는데, 2학년이 돼서 전문교과를 3연강을 듣다 보니까 약간 체감이 되더라.

이것들 못지 않게 맥북을 갖고 오는 친구들도 있다.

근데 어차피 맥북을 산다면 애플빠라 사는걸 테니까

별로 할 말이 없다.

몇몇 프로그램들이 맥용으로는 안나와 있어서 불편한 거 빼고는 불만도 딱히 없어 보인다.

그냥, 성능 대비 가격이 오지게 비싸다는 것 밖에는 할 말이 없는 것 같다. 고장은... 비슷하게 나는 것 같던데..?

이 외에 다른 노트북들은 워낙 다양하게 들고와서 잘 모르겠다..

그래도 대충 노트북 고를 때 중요하게 생각할 점들을 좀 이야기 해보도록 하겠다.

우선, 최소한의 배터리 시간은 챙겨야 된다.

최소한 프로그래밍 시간 두시간은 버틸 정도의 노트북을 고르도록 하자.

웬만하면 두시간은 버티긴 하겠지만, 오디세이는 간혹 가다 못버틸 때도 있는 것 같긴 했다.

(간혹가다 한성컴퓨터 노트북은 한시간도 못버티더라;;; 이런건 진짜 사지 말자.)

성능은 그렇게까지 챙길 필요는 없다.

물론 디미고에 와서 어떤 프로그램을 개발할지에 따라 다르긴 하겠지만,

학교에서 가르치는 프로그래밍과 기초제도 시간에 쓰는 오토캐드만 쓴다고 하면

cpu i5정도여도 충분할 것 같고, gpu는 사실상 딱히 필요가 없으며, 램은 8GB만 챙기면 된다.

(램 4GB는 진짜 개오바임;; 애초에 그런거 들고오는 얘들도 못본듯)

하지만 디미고에 와서 애프터이펙트나 인공지능 학습같은 조금 성능을 필요로 하는 것들을 할 예정이라면,

거기에 맞춰서 알아서 성능 조절은 잘 하면 될 것 같다.

+ 참고로 말해두지만, 디미고 와서 게임을 한번도 안 할 확률은 0%에 수렴한다. 게임을 어느 정도는 돌릴 만한 성능은 챙겨오자.

자유시간에 친구들이 옆에서 게임하는데 보고만 있으면 서러워질 수도 있다...

무게도 솔직히 그렇게 중요하진 않아 보인다.

개인적으로 노트북을 들고다니기 그렇게 버거운 근력의 소유자는 아닌지라 ㅎ;

개개인 차가 나겠지만, 무게는 자기가 들고다닐수 있을만한 것으로 사도록 하자.

그리고 노트북 들고 그렇게 오래 돌아다닐 일은 없다.

가장 오래 들고 다닐 일은 집에서 학교 올 때나 학교에서 집에 갈때 정도인데,

통학시간 고려해서 힘들지 않을 정도로만 들고 다니자.

(학교 내에서는 오래 들고 있어봤자 5분이다.)

가격은 뭐.. 알아서 맞추도록 하자 ㅎ;

따로 생각나는 거 있으면 그 때 알아보도록 하자.

그럼 수고링 ㅎ

지금 필자는 디미고 기숙사에 누워있다.

힘든 야자시간을 끝내고 침대에 누워서

오늘 하루 동안 못 쓴 글을 쓰고 있다.

아마 평소였다면 휴대폰으로 딴짓을 하고 있거나

저번 주인가에 샀던 영어 책을 읽고 있었을 것이다.

이처럼 디미고의 기숙사는 하루가 끝나고 편히 쉴

수 있는 공간이다.

힘들고 고된 (과장 약간 포함) 야자 시간을 끝내고 나서

따뜻한 물로 몸을 데우고 난 뒤

점호를 끝내고 침대에 누우면

그것보다 좋은 것이 없는 것 같다.

... 그리고 이게 디미고 선생님들과 사감 선생님들이 원하는 디미고 기숙사의 모습이겠지?

당연하다면 당연한 이야기겠지만, 선생님들은 학생들이 기숙사에서 조용히 잠만 자기를 원한다.

하지만... 학생들의 마음은 당연히 그렇지 않다.

(참고로 필자는 기숙사에서 조용히 지내는 편이다. 애초에 이런 걸 쓰고 있는 것부터가 ㅎㅎ...)

많은 학생들이 친구들의 호실에 놀러가서 친구들과 논다.

하지만 이러다가 걸리면 '타숙실'이라고 해서, 매일 아침 구보를 뛰는 벌을 받게 된다.

그걸 피하기 위해서, 학생들은 친구 방에 놀러 가서 침대 뒤로 숨는다.

특히 타숙실과 같은 규정 위반이 5번이 적발되면 자치법정에 가야 하기 때문에,

자치 법정에 갈 수도 있는 친구들은 악착같이 숨어서 지내기도 한다.

그냥 타숙실 안 가고 조용히 자신의 호실에 있으면 되지 않냐고?

친구들과 한 침대에서 같이 웃고 떠드는 것보다 더 재미있는 것은 없다는 것을 수학여행 한 번이라도 갔다 온 사람들은 잘 알 것이다.

하루의 마지막을 친구와 소소한 대화를 나누며 지내고 싶은 것은 사실 너무 당연한 일인 것 같다.

(물론 남의 호실 들어가서 너무 시끄럽게는 하지 말아야겠지만 말이다.)

또 학교에서는 규정으로 막지만 학생들이 꼭 하는 것이 바로 음식물 반입이다.

이것도 사감 선생님들께 안들키려고 아주 꼭꼭 숨기는 친구들이 있다.

그러면 음식물 반입을 안하면 되는 거 아니냐고?

힘든 야자 시간을 끝내고 침대에 누워서 친구들과 떠드는 것도 그렇게 재밌는데,

맛있는 것 까지 먹으면서 하면 더 재미있지 않을까?

(저는 숙실에 음식물 반입을 한 적이 없습니다 선생님 ^^7)

심지어는 새벽에 친구들이랑 몰래 라면을 끓여먹는 얘들도 있다고 하니..

(이건 걸리면 중징계도 가능하지 않을까??)

아무튼, 이렇게 살아가는 곳이 디미고 기숙사이다.

너무 힘들면 지금 나처럼 침대에 누워서 폰질을 해도 되고,

좀 놀고싶으면 (몰래) 친구가 있는 호실로 놀러 가거나,

너무 피곤하면 일찍 자기도 하는 등

학생들이 가장 자유롭고 편하게 있을 수 있는 곳인 것 같다.

안타깝게도 점호가 끝나고 대략 30분 정도밖에 시간이 없기 때문에, 오랜 시간 놀지는 못한다.

30분가량 친구들과 놀거나 폰질을 하다가,

12시가 되는 순간 바로 폰을 내고 잠에 들어야 한다.

아무튼, 짧지만 디미고에서 가질 수 있는 가장 편안한 자유 시간이 바로 밤의 기숙사에서 지내는 시간이다.

친구들과 함께하는 즐거운 추억들도 많이 생기는 시간이기도 하고,

친구들과 가장 친해질 수 있는 시간이기도 하다.

그리고 이런 시간들이 바로, 디미고 생활을 버틸 수 있게 해주는 활력소인 것이다.