끄적끄적

요약

 Bayes' theorem을 이용한 Maximum a posteriori estmation(MAP)을 이용한 모델과 MAP과 least mean-square estimation 사이의 관계에 대하여 다룹니다.

Bayes' theorem

 Regressor $x$가 environment $w$와 상호작용하여 response $d$가 관측되었다고 할 때, 확률론을 이용하면 environment $w$에 대한 조건부 확률 $p_{W,D \vert X}(w,d,x)$는 아래와 같이 쓸 수 있다. 

 $p_{W,D \vert X}(w,d,x) = p_{W \vert D,X}(w \vert d,x)p_D(d) =p_{D \vert W,X}(d \vert w,x)p_W(w)$

 또한, 위의 식을 이용하면 조건부 확률 $p_{W \vert D,X}(w \vert d,x)$을 아래와 같이 쓸 수 있는데, 이것이 Bayes' theorem이다.

 $p_{W \vert D,X}(w \vert d,x) = \frac{p_{D \vert W,X}(d \vert w,x)p_W(w)}{p_D(d)}$

 즉, Bayes' theorem이란, $w$에 대한 조건부 확률을 $w$에 대한 사전확률(믿음)과 관측값 $d$에 대한 조건부 확률을 이용하여 나타내는 것이다.

용어정리

 Observation density : $p_{D \vert W,X}(d \vert w,x)$로, 주어진 환경 $w$하에서 stimuli $x$에 대하여 response $d$가 관측될 확률을 나타낸다.

 Prior : $p_W(w)$로, 관측전의 $w$에 대한 information을 나타내며 앞으로는 $\pi(w)$라고 쓰겠습니다.

 Posterior density : $p_{W \vert D,X}(w \vert d,x)$로, 관측 후의 $w$에 대한 조건부 확률로, 앞으로는 $\pi(w \vert d,x)$로 쓰겠습니다.

 Evidence : $p_D(d)$로, $d$에 대한 통계 분석에 의한 information을 나타낸다.

Maximum likelihood estimation(ML)과 Maximum a posteriori estimation(MAP)

 Likelihood function $l(w \vert d,x)는

 $l(w \vert d,x) = p_{D \vert W,X}(d \vert w,x)$,

 즉, observation density라고 할 수 있고, 위의 Bayes' theorem을 통해 posteriori $\pi(w \vert d,x)$는 다음과 같이 쓸 수 있다.

 $\pi(w \vert d,x) \propto l(w \vert d,x)\pi(w)$

 따라서 ML estimation of $w$ $w_{ML}$과 MAP estimation of $w$ $w_{MAP}$은 아래와 같이 쓸 수 있다.

 $w_{ML} = \underset{w}{\operatorname{argmax}}l(w \vert d,x)$

 $w_{MAP} = \underset{w}{\operatorname{argmax}}\pi(w \vert d,x)$

 둘의 차이점을 살펴보면, $w_{ML}$의 경우에는 $w$에 대한 prior를 고려하지 않는다. 또한 많은 경우에 $\pi(w \vert d,x)$ 값 자체보다는 $log(\pi(w \vert d,x))$ 값이 편리한 경우가 많으므로, 계산상의 편의를 위하여 앞으로는 $w_{MAP} = \underset{w}{\operatorname{argmax}}log(\pi(w \vert d,x))$를 사용한다. 

Parameter estimation in a Gaussian Environment

 Gaussian environment에서의 MAP 추정은 우리에게 친숙한 least-square estimation과 연관되는데, 이를 보이겠다.

 이를 보이기 위해서는 세가지 가정이 필요한데, 먼저 N개의 sample data $({\mathbf{x}_i,d_i})_{i=1}^N$은 i.i.d이다. 또한, $d_i = w^T \mathbf{x}_i + \epsilon_i$ 일 때, error $\epsilon_i$ 역시 Gaussian 분포를 따른다. 

 $p_E(\epsilon_i) = \frac{1}{\sqrt{2 \pi} \sigma}exp(-\frac{\epsilon_i^2}{2 \sigma^2})$

 또한 $\mathbf{w}$가 길이 M인 벡터라 할 때, M개의 각각의 요소들은 stationary하다. 여기서는 각각의 요소들이 독립적이며 평균이 0이고, 분산이 $\sigma_w^2$라 가정한다.

 $\pi(w_k) = \frac{1}{\sqrt{2 \pi} \sigma_w}exp(-\frac{w_k^2}{2 \sigma_w^2})$

 위의 가정들을 종합해보면, $\mathbb{E}[D_i] = \mathbf{w}^T \mathbf{x}_i, var[D_i] = \sigma^2$ 가 된다. 이를 가지고 liklihood function을 쓰면 아래와 같다. 

 $ㅣ(\mathbf{w} \vert d_i, x_i) = \Pi_{i=1}^N l(\mathbf{w} \vert d_i, \mathbf{x}_i) = \frac{1}{^\sqrt{2 \pi} \sigma)^N} exp(-\frac{1}{2 \sigma^2}\sum_i (d_i - w^T \mathbf{x}_i))$

 Prior $\pi(\mathbf{w})$의 경우, 앞에서 $w$의 각각의 요소들이 i.i.d임을 가정했으므로 다음과 같이 쓸 수 있다.

$\pi(w) = \Pi_{k=1}^M \pi(w_k) = \frac{1}{(\sqrt{2 \pi} \sigma_w)^M}exp(\frac{1}{2\sigma_w^2}\sum_k w_k^2) = \frac{1}{(\sqrt{2 \pi} \sigma_w)^M}exp(\frac{1}{2\sigma_w^2}\lVert \mathbf{w} \rVert^2)$

 Priori와 likelihood 함수를 모두 구했으므로, Posteiori는 다음과 같이 쓸 수 있다.

 $\pi(w \vert d,x) \propto exp[-\frac{1}{\sqrt{2 \pi} \sigma}\sum_i(d_i - \mathbf{w}^T \mathbf{w}_i)^2 - \frac{1}{\sqrt{2 \pi} \sigma_w}\lVert \mathbf{w} \rVert^2 ]$

 $w_{MAP} = \underset{w}{\operatorname{argmax}}[-\frac{1}{\sqrt{2 \pi}}\sum_i(d_i - \mathbf{w}^T \mathbf{w}_i)^2 - \frac{\lambda}{\sqrt{2 \pi}}\lVert \mathbf{w} \rVert^2], \lambda = \frac{\sigma^2}{\sigma_w^2}$

 여기서 argmax 함수 안의 첫 항은 least-square estimation 에서 쓰는 quadratic error function이며, 뒤의 항은 regularization이라 할 수 있다. 즉, 가우시안 환경에서의 MAP 추정은 regularized least-square 추정이 된다. 또한 $\lambda \rightarrow 0 (\sigma_w \rightarrow \infty)$인 경우, 즉, $w$의 분포가 uniform 분포인 경우에는 MAP 추정이 ML 추정과 같아진다.

* Neural Networks and Learning Machines -Simon Haykin 의 책을 스터디한 내용을 정리한 것입니다.

유형 : dp

첫번째 오답

 동전들의 가치가 1, 2, 5로 주어지는 경우를 예로들면, 단순히 가치 i를 만드는 경우의 수 dp[i] = dp[i-1]+dp[i-2]+dp[i-5] 로 만드는 경우에는, 중복된 경우를 따로 카운트하게 되어 오답이 된다. 예를들면 i=3 인 경우를 예로 들면, dp[2]+dp[1]이 되는데, dp[2]를 사용하는 경우를 살펴보면, dp[2]는 1을 두개 쓴 경우와 2를 한개 쓴 경우 해서 2가지가 되고, 여기에 1을 한개 더 사용하여 3을 만드는 경우이므로 총 2가지 (1을 3개), (1을 1개, 2를 1개)가 된다. dp[1]은 1을 한개 사용하는 경우 한가지가 존재하고, 여기에 2를 한 개 사용하여 3을 만드는 경우가 되므로, (1을 1개, 2를 1개) 한가지가 된다. 따라서 dp[3] = 3 이라고 계산하게 되는데, 위의 세가지를 살펴보면 (1을 1개, 2를 1개) 가 두번 세어진 것을 알 수 있다. 즉, 1을 먼저 쓰고 2를 쓴 경우와, 2를 먼저 쓰고 1을 쓴 경우를 다르게 체크하는 것이다.

 따라서 이러한 중복되는 경우의 수를 피하기 위해 아래에서는 n 종류의 동전만을 사용하는 경우를 나누어서 계산하게 된다.

풀이 및 두번째 오답

 먼저 dp를 n x k+1 사이즈의 리스트로 선언한다. dp[n][k]는 첫 n+1개의 코인(0부터 세니까)을 사용하여 가치 k를 만드는 경우의 수이다. dp[0]의 경우에는 첫번째 동전만을 사용하는 경우이므로, dp[0]의 경우,

[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)] 로 초기화 해준다. 즉, k가 coin[0]으로 나누어지는 경우에만 가치 k를 첫번째 코인만으로 만들수 있다. 그 후의 점화식은 아래와 같다.

$dp[i][j]=\begin{cases}dp[i-1][j], & \mbox{if j < coin[i]} \\ dp[i][j-coin[i]]+dp[i-1][j], & otherwise\end{cases}$

 첫 경우는, 만드려는 가치 j가 i번째 코인의 가치보다 작은 경우로, 이러한 경우에는 i번째 코인을 사용할 수 없으므로, 전의 것을 그냥 사용하면 된다. 두번째 경우에서 dp[i][j-coin[i]]는 i번째 코인도 사용해서 가치 j-coin[i]를 만든 후에 i번째 코인을 사용하는 경우이고, dp[i-1][j]의 경우에는 i번째 코인을 사용하지 않는 경우가 된다. 이렇게 계산하면 위의 오답의 예를 다시 살펴보면 dp[1][3] (첫번째, 두번째 코인을 사용하여 가치 3을 만드는 경우의 수)는 dp[1][1] + dp[0][3] 이 된다. dp[1][1]의 경우에는 dp[0][1]로 주어지므로, 1이 되고, dp[0][3] 역시 1이므로, 위와 같이 중복된 경우는 세지 않을 수 있다. 

Python Code

코드로 나타내면 다음과 같은데, 문제는 dp의 공간 복잡도가 $O(n\dots k)$가 되어 메모리 초과가 된다.

공간복잡도 줄이기

 그런데, 위의 코드를 살펴보면 실질적으로 dp[i][j]를 계산하는 13, 15 line에서 dp[i-1][j]가 계속 반복되는 것을 볼 수 있다. 즉, dp를 길이 k+1인 리스트로 선언한 후 15번째 줄의 우항의 마지막 항을 버리면 된다.

Python Code

문제링크

유형 : dp라고 쓰여있지만 완전탐색...

문제풀이

 10,21,321 처럼 큰 자리의 숫자가 작은 자리의 숫자보다 큰 숫자를 구하는 문제로, 결국 [0,1,2,3,4,5,6,7,8,9] 만들 수 있는 모든 subset을 구하는 문제와 동일하다.

 무슨 말인가 하니, 위의 0 ~ 9 숫자 중 중복되지 않는 n개의 숫자를 뽑으면 그 숫자들로 만들 수 있는 감소하는 숫자는 1개밖에 존재하지 않는다. 예를 들어 1,3,5를 골랐다면 531 이외의 가능한 감소하는 수는 없다. 따라서 1 ~ 9로 만들수 있는 감소하는 수의 총개수는 $2^{10} -1$ 개가 되는데, 그 이유는 0 ~ 9 총 10개의 숫자 모두 선택한다, 안 한다 두 개의 경우가 존재하기 때문이다. 따라서 입력값 n이 1024 이상인 경우에는 -1을 반환하면 된다(실제 구현할 때는 0부터 셈으로 1023 이상). 1023 이하인 경우에는, 10개의 숫자 중 뽑는 n개의 숫자를 1개부터 10개까지 늘리며 모든 가능한 조합으로 숫자를 만든 후, 정렬하여 n번째 수를 반환하면 된다.

Python Code

21 line 은, depth번째 수 i 로 가능한 것들의 조건인데, i는 depth-1보다는 작아야 하고, 앞으로 digit-depth 만큼의 수를 더 뽑아야 하기 때문에, 뒤에 digit-depth만큼의 수는 남겨두어야 한다.

29 line의 digit이 위에서 말한 n(몇 개를 선택할 것인지로 몇 자릿수의 숫자를 만들지를 의미)이다.

문제 링크

요약

 MDP를 통해서 확률적으로 변화하는 과정을 어떻게 모델링하는지를 배웠지만, 현실의 많은 문제에서는 action $a$를 취했을 때 Transition probability $T(s,a,s')$와 $Reward(s,a,s')$을 알 수 없다. Reinforcement Learning이란 이러한 상황에서 policy $\pi$에 따른 path(episode)가 주어졌을 때, $T(s,a,s')$와 $Reward(s,a,s')$, 또는 각 상황$(s,a)$에서 주어지는 찬스라고 할 수 있는 $Q(s,a)$를 계산하는 방법이라고 할 수 있다.  

Model-based Monte Carlo

 Data(episode)가 $s_0;a_1 r_1 s_1;a_2 r_2 s_2; \dots$ 로 주어졌을 때, $T$와 $Reward$를 추측하는 가장 간단한 방법은 데이터로부터 $(s,a,s')$이 몇 번 나타나는지 세는 것이다. ($\hat{}$은 추정량을 의미)

 $\hat{T}(s,a,s')=\frac{\mbox{# of (s,a,s') occurs}}{\mbox{# of (s,a) occurs}}$

 $\hat{Reward}(s,a,s') = r \mbox{ in }(s,a,r,s')$

 수많은 데이터로부터 위의 과정을 통해 $T$와 $Reward$를 추정하는 것이 Model-based Monte Carlo 방법인데, 이 문제의 가장 큰 문제는, data에서 나타나지 않는 $(s,a)$에 대하여는 위의 값들을 알 수가 없다는 것이다. 즉, $s$에서 policy $\pi(s)$가 고정되어 있을때, $\pi(s)$에 의하여 선택되어 지지 않는 $a$가 있을 경우, 그 $a$에 대한 값들을 추정할 수가 없다.

 따라서 reinforcement learning을 하기 위해서는 다양한 $(s,a)$에 대하여 탐사해야 하는데, 이러한 문제를 exploration이라 하며 아주 중요한 문제이다.

Model-free Monte Carlo

 사실 $T$와 $Reward$로 우리가 하려는 것은 $V_\pi(s)$와 $Q_\pi(s,a)$를 구하려는 것이므로, $T$와 $Reward$가 아닌 $\hat{Q}_\pi(s,a)$를 직접 구할 수도 있는데 이것이 Model-free Monte Carlo에서 하고자 하는 것이다. utility $u_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots$ 로 주어질 때, Q value의 추정값은 다음과 같이 쓸 수 있다

 $\hat{Q}_\pi(s,a) = \mathbb{E}[u_t]$ where $s_{t-1} = s, a_t = a$

 하지만, 위에서 구한 추정값은 $\hat{Q}_\pi$ 이지 $\hat{Q}_{opt}$가 아니다. 즉, 이 방법은 데이터가 생성되는데에 사용된 $\pi$에 굉장히 의존적이다. 

 알고리즘은 아래와 같이 쓸 수 있다.

For each (s,a,u):

    $\hat{Q}_\pi(s,a) \leftarrow (1-\eta)\hat{Q}_\pi(s,a) + \eta u$, where $\eta = \frac{1}{\# of (s,a,u)}$

즉, 기존의 값 $\hat{Q}_\pi(s,a)$ 와 새로운 데이터 $u$ 가 서로 맞도록 조절해 가는 것이다. 또한, 위의 식을 아래와 같이 고쳐씀으로써, Model-free Monte Carlo의 target이 $u$임을 알 수 있다.

    $\hat{Q}_\pi(s,a) \leftarrow \hat{Q}_\pi(s,a) - \eta(\hat{Q}_\pi(s,a) - u)$

SARSA

 위에 언급했듯, Model-based MC의 target은 $u$인데, 문제는 $u$의 variance가 매우 크다는 것이다. 전 강의의 동전던지기 문제를 예로 들면 $u = 4, 8, 12, 16, \dots$ 의 값들이 나타날 것이다. 데이터가 아주 많다면 위처럼 평균을 취함으로써 맞출 수 있겠지만, 더 효율적인 방법으로서 제시되는 것이 SARSA이다.

    $\hat{Q}_\pi(s,a) \leftarrow (1-\eta)\hat{Q}_\pi(s,a) + \eta(r + \gamma\hat{Q}_\pi(s',a'))$

위의 업데이트 과정에서 알 수 있듯, model-free MC에서는 모든 r값의 함으로 u를 계산했다면, SARSA에서는 첫번째 Reward r값만을 취하고 뒤의 Reward들은 추정값인 $\hat{Q}_\pi(s',a')$으로 대체한다. 이렇게 함으로써 데이터 간의 $u$ 값의 편차를 줄일 수 있다. 다시 동전던지기 문제를 예로 들면, 첫번째에 실패한 데이터의 경우 $u=4+0$이 되고, 1번 이상 성공한 경우는 $u=4+\hat{Q}_\pi(s',a')$으로 모두 같게 된다. 또한, 실제 $u$값이 아닌 추정값이기에 편향(biased)되었다고 할 수 있다.

Q-Learning

 위의 SARSA가 $(s,a,r,s',a')$에 대한 모델링이었다면, Q-Learning은 $(s,a,r,s')$에 대한 모델링이다. 따라서 여기서는 $\hat{Q}_\pi(s',a')$ 대신 $V_{opt}(s')$을 사용하게 된다.

    $\hat{Q}_{opt}(s,a) \leftarrow (1-\eta)\hat{Q}_{opt}(s,a) + \eta(r + \gamma V_{opt}(s'))$

 여기서는 $\hat{V}_\pi(s)$가 아닌 $\hat{V}_{opt}(s,a)$ 이므로, 특정 policy에 대한 예측값이 아닌 $s$에서 가능한 모든 $a$에 대하여 최적의 값이 된다. 또한, Q-Learning 역시 다음과 같이 Stochastic하게 구현할 수도 있다.

    $\hat{Q}_{opt}(s,a) \leftarrow \hat{Q}_{opt}(s,a) - \eta(\hat{Q}_{opt}(s,a) - (r + \gamma V_{opt}(s')))$

Exploration

 위에서 언급했듯, reinforcement learning을 성공적으로 학습시키기 위해서는 모든 $(s,a)$를 돌아다닐 필요가 있다. 따라서 데이터를 생성할 policy를 정하는 것은 굉장히 중요한 일이다. 만약 $\pi(s)$가 $\hat{Q}_{opt}(s,a)$를 최대화 시키도록 하면, 여러 $(s,a)$를 돌아다니지 않고, 처음 발견한 가장 좋은 $a$만을 계속해서 선택할 것이다. 즉, Greedy하게 되어버린다. 그렇다고 random하게만 $a$를 선택하면 생성된 데이터들의 $u$값이 너무 낮게 된다. 따라서, 좋은 곳을 적절한 비율로 선택하며 가끔 색다른 선택도 하는 방식이 좋을 것이고, 이것이 Epsilon Greedy 방법이다. 즉, $1-\epsilon$의 확률로 전자를 택하고 $\epsilon$의 확률로 후자를 택하는 방법이다.

유형 : dp

문제풀이

* 지금 설명할 풀이는 효율이 좋지 못합니다.

 b 도시에 i번째로 도착했을 때, 가능한 기내식 점수들의 합은 dp[a][i-1]+air[a][b] 가 됩니다. (air[a][b]는 a에서 b 구간 비행기의 기내식의 점수)

 따라서 dp[b][i]의 점화식은 아래와 같이 쓸 수 있습니다.

 dp[b][i] = max(dp[a][i-1]+air[a][b] for b보다 작은 모든 a)

 다만 위의 식을 진행하는 데에 있어서, i-1번째로 a에 도착한 경우와 a에서 b구간의 비행기가 있다는 조건을 위한 조건문이 추가로 들어가야합니다.

 위의 점화식을 b를 n까지, i는 m까지 반복 한 후, dp[n]의 최댓값을 반환하면 됩니다.

Python Code

line13에 try 문이 들어간 이유는 if문을 만족하는 a가 하나도 없는 경우 max함수에서 에러가 발생하기 때문입니다.

문제링크

유형 : dp

문제풀이

 포도주 시식 문제와 유사하지만, 마지막 계단을 반드시 밟아야한다는 제한이 있다. 

 따라서 i번째 계단의 점수가 s[i]라 하면, i번째 계단을 밟았을 때의 최대 점수 dp[i]는 다음과 같이 주어진다.

 dp[i] = max(dp[i-2]+s[i], dp[i-3]+s[i-1]+s[i])

 즉, 2칸 전 계단을 밟고 이번 계단을 밟거나, 3칸 전 계단을 밟고 전칸을 밟고 이번 계단을 밟거나 두가지 조건이 가능하다.

list 초기화와 append

 위의 문제를 해결하는데 있어서, dp를 먼저 빈 list로 선언한 후 append로 하나씩 채워갈 수도 있고, dp를 길이가 n인 리스트로 선언한 후, i번째 요소를 바꿔가는 방법이 있는데, 후자가 효율적이다. 전자로 통과한 후, 후자의 방법으로 바꾸었더니 80ms 에서 56ms로 줄었다.

Python Code

요약

 Greedy나 DP 알고리즘 문제에서 많이 볼 수 있는 Search Problem에서는 특정 state $s$에서 action $a$를 취하면 확정적으로 새로운 state $s'$으로 간다. 하지만 여기서는 조금 더 현실세계의 특성을 반영하여 action $a$를 취했을 때, $s'$으로 갈 확률$T(s,a,s')$이 주어진다. 

 이번 장에서는 확률과정에서의 optimum path를 찾는 방법에 대하여 다룬다.

예제 설명 및 MDP

 이번 장에서는 설명을 위하여 동전을 던져서 앞뒤를 맞추는데, 도전할 경우에는 4원을 받고, 성공할 경우에는 다시 또 게임을 하고 실패할 경우에는 4원을 받고 끝나며, 도전을 포기할 경우에는 6원을 받고 끝나는 게임을 예로 들어 설명하겠습니다.

 이 게임에서 $4n$원을 받을 확률은 앞뒤를 맞출 확률이 1/2이므로 $1/2^n$으로 주어지게 됩니다. 이 때, 내가 받을 것으로 기대되는 reward를 utility라고 하며, 계속 도전할 경우의 utility는

$utility = 4 \times \frac{1}{2} + 8 \times \frac{1}{4} + 12 \times \frac{1}{8} + \dots$

으로 주어지며, 포기할 경우의 utility는

$utility = 6 \times 1$

로 주어지게 됩니다.

 이 장의 목표는 utility를 최대로 만드는 최선의 전략(policy)를 찾는 것입니다.

 또한, 위의 예제를 Markov Decesion Process(MDP) 로 나타내고 그림으로 표현하면 아래와 같이 표현할 수 있습니다. Transition이 현재의 상태에만 의존하기 때문에 Markov 모형이라 할 수 있습니다.

Discounting

 Discounting($\gamma$)이란 당장의 보상을 미래의 보상보다 더 선호하는 경향성을 나타내기 위한 파라미터로서, step이 지남에 따라 exponential하게 보상의 가치가 낮아진다는 가정이 들어가게 됩니다. 예를 들어, 3 단계 후의 utility 역시 $4 \times \frac{1}{2}$ 이지만, $\gamma$가 0.9인 경우의 utility는 $(0.9)^2 \times 4 \times \frac{1}{2}$ 가 됩니다. 즉, reward의 가치가 하락한 것을 알 수 있습니다. $\gamma = 1$인 경우에는 현재의 reward와 미래의 reward의 가치가 같으며, $\gamma = 0$인 경우에는 미래의 reward는 가치가 없는 극단적인 경우를 나타냅니다.

Policy evalution

 이제 state $s$에서 기대되는 utility를 최대화하기 위해 선택해야 하는 전략(policy)를 구하기 위해 몇가지 변수를 정의하겠습니다. $s$에서 policy $\pi(s)$를 따를 때, value of policy를 $V_\pi(s)$, Q-value of policy를 $Q_\pi(s,a)$라 하고 정의는 아래와 같습니다.

$V_\pi(s)=\begin{cases}0, & \mbox{if s is end} \\Q_\pi(s,a), & otherwise\end{cases}$

$Q_\pi(s,a)=\sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_\pi(s')]$

 위의 예제에서 $\pi = "도전"$인 경우의 Value of policy 는 아래와 같이 풀 수 있습니다.

$V_\pi(end) = 0$

$V_\pi(in) = \frac{1}{2}(4+V_\pi(end)) + \frac{1}{2}(4+V_\pi(in)) = 8$ (도전 후 실패한 경우 + 도전 후 성공한 경우)

 위의 예제처럼 아주 쉬운 경우에는 이처럼 손으로 풀리지만, state가 아주 많거나 관계가 복잡한 경우에는 손으로 깔끔하게 풀린다고 보장할 수 없다. 따라서 앞의 강의들에서 사용했던 머신러닝의 아이디어를 가져와서 최적의 $V_\pi(s)$ 값을 찾게 되는데, 이러한 방법을 Policy evaluation이라 한다. 

 적당히 $V_\pi(s)$값이 수렴할 때 까지 $V_\pi(s)$ 값을 여러 step에 걸쳐 update해 나갈건데,
1. t step에서의 value of policy를 $V_\pi^{(t)}(s)$라 하면, 먼저 $V_\pi^{(t)}(s)$를 모든 s값에 대하여 0인 벡터로 초기화 해준다.

 2. 그 후 각각의 state $s$에 대하여 아래와 같이 update를 해준다.

 $V_\pi^{(t)}(s) = \sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_\pi^{(t-1)}(s')] \equiv Q_\pi^{(t-1)}(s,\pi(s))$

 3. 위의 과정을 아래와 같이 변화량이 일정값 이하가 될때까지 반복해준다.

 $max_s \lvert V_\pi^{(t)}(s) - V_\pi^{(t-1)}(s) \rvert \le \epsilon$

Value iteration

 위에서 value of policy 값을 recurrent하게 구하는 방법을 알았으니, 이를 이용하여 이번에는 최적의 value $V_{opt}(s)$ 를 구할 것인데 이러한 방법을 value iteration이라 한다.

$V_{opt}(s)=\begin{cases}0, & \mbox{if s is end} \\Q_{opt}(s,a), & otherwise\end{cases}$

$Q_{opt}(s,a)=\sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_{opt}(s')]$

  코딩으로 구현하는 방법은 위의 policy evaluation과 같은데 과정 2의 업데이트 방식만 아래와 같이 바꿔주면 된다.

 $V_{opt}^{(t)}(s) = max_a \sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_{opt}^{(t-1)}(s')] \equiv max_a Q_{opt}^{(t-1)}(s,\pi(s))$

Python Code(클릭 시 github로)

MDP Modeling

 line6 : state $s$가 in 일때는 가능한 $a$가 bet과 notBet으로 주어집니다.

 line8 : $s = 'in'$인 경우, bet을 취할 경우에는 4원을 받고 1/2의 확률로 in으로, 1/2의 확률로 end로 가게 됩니다. $s='end'$인 경우에는, 확정적으로 reward가 없습니다.

 line23 : 위의 코드에서는 $\gamma = 1$, 즉, 미래의 reward와 현재의 reward의 가치가 같습니다.

Value iteration

 line30 : $V_{opt}(s)$를 모든 s에서 0으로 초기화합니다.

 line38 : $s='end'$인 경우에는 reward를 받을 수 없으므로 value of policy는 항상 0이 됩니다.

 line42 : 위에서 설명한 value iteration의 종료조건인 과정3을 나타냅니다. $V$ 값의 변화량이 0.001 이하가 되면 과정을 종료합니다.

위의 코드를 돌려보면 $V('in') = 8, V('out') = 0$으로 위에서 손으로 푼 결과와 같은 값을 얻을 수 있습니다. 따라서 Optimal policy $\pi('in')$은 'in'상태에 계속 머무르기 위한 '도전'이 됩니다.

유형 : 스택

풀이과정

 Stack이란 후입선출하는 자료구조로 이를 이용하여 괄호의 균형을 체크한다.

 stack은 그냥 list를 선언하여 활용했는데, 어차피 맨 뒤의 것만 지울것이기 때문이다(list.pop()). 만약 앞의 것을 지워야한다면 deque를 선언하여 활용하는 것이 좋다.

 1. 문자열의 앞에서 부터 확인하는데, 왼괄호('(','[')를 만나면 stack에 넣어준다.

 2. 오른괄호를 만나면 stack의 맨 뒤의 원소를 확인하여 둘이 짝이면 stack의 맨 뒤의 것을 제거한 후 넘어가고(list.pop()), 짝이 맞지 않는다면 균형이 잡히지 않은 괄호이기 때문에 'no'를 리턴해준다.

입출력

 문제자체는 굉장히 쉬운 문제인데, 이상한데서 고생을 했다. 바로 입출력 문제인데, Python3에서 input()으로 입력을 받을 경우에는 뒤에 개행문자가 없지만 sys.stdin.readline()으로 입력을 받을 경우에는 뒤에 개행문자가 추가되어 입력이 들어온다. 따라서 이를 유의해야한다.

Python Code