끄적끄적

Bayes' theorem

 Conditional probability를 활용하여 $P(A\cap B)$ 를 쓰면 다음과 같다.

$P(A\cap B) = P(A \vert B)P(B) = P(B \vert A)P(A)$

위 수식의 의미는, 사건 A와 사건 B가 함께 일어날 확률은 사건 A가 일어나고 사건 B가 일어나거나, 사건 B가 일어나고 사건 A가 일어날 확률로 쓸 수 있다는 것이다.

 위의 수식을 이용하면 $P(A \vert B)$를 다음과 같이 쓸 수 있다.

$P(A \vert B) = \frac{P(B \vert A)P(A)}{P(B)}$

이 수식을 베이즈 정리라 한다.

용어 정리

위 수식을 활용하기 위해 A를 가설, B를 데이터라 하면,

$P(hypothesis \vert data) = \frac{P(data \vert hypothesis)P(hypothesis)}{P(data)}$

라 쓸 수 있다.

$P(hypothesis \vert data)$ : posterior probability(사후확률)라 하며, 주어진 데이터 하에 가설이 참일 확률을 의미한다.

$P(data \vert hypothesis)$ : 가설 하의 데이터의 likelihood이다.

$P(data)$ : marginal probability

$P(hypothesis)$ : Prior probability(사전확률)로 가설에 대한 초기 믿음을 나타낸다.

Naive Bayes' Classifier

 입력 feature $\vec{x}$를 통해 class $y$를 유추하는 모델을 생각해보면 베이즈 정리에 의해 다음과 같이 쓸 수 있다.

$P(y_j \vert \vec{x}) = \frac{P(\vec{x} \vert y_j)P(y_j)}{P(y_j}$

우항의 분모를 다시 쓰면,

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert x_1, \dots, x_n, y_j)$

이며, $x_i$가 서로 독립이라는 가정을 하면(강력한 가정이며 이 때문에 Naive Bayes' classifier이다),

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert y_j)P(x_2 \vert y_j) \dots P(x_n \vert y_j)P(y_j) = \prod_k P(x_k \vert y_j)P(y_j)$

라 쓸 수 있다.

 이 때, 주어진 feature $\vec{x}$에 대한 예측 클래스 $\hat{y}$ 는 다음과 같다.

$\hat{y} = \underset{y_j}{argmax} \prod_k P(x_k \vert y_j)P(y_j)$

Laplace Smoothing

 위 모형의 문제는 샘플의 개수가 적을 때 $P(x_i \vert y_j) = 0$ 이 생기는 문제가 발생할 수 있다. 즉, 데이터 기반으로 likelihood를 계산하다보니 등장하지 않은 데이터에 대해서는 class $y_j$일 확률이 아예 없다고 하는 강력한 모형이 만들어지는 것이다. 이러한 강력한 모형은 바람직 하지 않으므로

$P(x_i \vert y_j) = \frac{\mbox{# number of }x_i + cP(x_i}{\mbox{# of } y_j + c}$

와 같이, 아주 작은 값을 분모와 분자에 더해줘 확률이 0이 되는 것을 피한다.

Application with Iris dataset

 붓꽃 분류 데이터를 활용하여 실습해 보겠습니다. 해당 데이터에서 feature는 4개로 ['sepal length', 'sepal width', 'petal length', 'petal width'] 이고, class는 [0,1,2] 세개로 주어집니다.

 주어진 데이터에 맞게 각 확률을 구해주면 됩니다. 또한, 계산의 편의성을 위해 모든 인풋값을 반올림하여 사용하였습니다. 연속값을 사용하는 경우에는 특정 구간의 데이터 개수를 세면 됩니다.

 Prior probability : 모든 클래스의 데이터가 각 50개씩 주어지므로 1/3으로 했습니다.

 Marginal probability : $[x_1, x_2, x_3, x_4]$ 의 개수를 센 후, 전체 개수로 나누어주면 각 인풋 데이터에 맞는 Marginal probability가 됩니다.

 Likelihood : $P(x_i \vert y)$ 의 개수를 세어 확률을 측정합니다.

 코드는 깃허브를 참조해주세요.

 Github link

 학습과 테스트 데이터는 8:2로 나누었으며, 30개의 테스트셋에 대해 약 93%의 정확도를 보이는 것을 확인할 수 있습니다.

Reinforcement learning의 목표

 결국 강화학습에서 하고자 하는것은 세상이 어떻게 돌아가는지를 모를때 ($T(s,a,s'), Reward(s,a,s')$ 등 우리의 행동에 따른 보상을 알 수 없을 때), 현재 상태 $s$에서 utility를 최대화하기 위한 policy $\pi(s)$와 그에 따른 보상 $V_{opt}(s)$ 또는 $Q_{opt}(s,a)$를 추정하는 것이다. MDP를 모르는 상황에서 우리가 MDP를 추정하여 만들어가는 과정이라고도 할 수 있다. 이를 위해서 데이터를 수집하고 그를 바탕으로 여러 값들을 추정하게 된다.

방법론 요약

 강화학습의 방법론으로는 크게 4가지가 있는데, 먼저 Model-based Monte Carlo 방법의 경우에는 가장 단순하게 주어진 데이터로 부터 통계적으로 $\hat{T}$ 와 $\hat{Reward}$를 추정하는 것이다.

 Model-free Monte Carlo 방법의 경우에는 위의 방법과는 다르게 $\hat{Q}_\pi$를 추정하게 된다. 즉, 각 Transition probability와 그에 따른 utility를 구하는 것이 아니라 현재 상태에서 얻을 수 있는 $utility$의 기댓값, 즉 우리가 데이터를 얻은 전략에 따른 $Q_\pi$를 직접 구한다.

 SARSA의 경우에도 Model-free MC의 다른 방식으로, $\hat{Q}_\pi$를 추정하지만, $utility$를 u가 아닌 $r + \hat{Q}_\pi$로 대체함으로써 target의 variance를 줄인다.

 마지막으로 Q-Learning의 경우에는 $\hat{Q}_{opt}$를 추정하는데, MDP에서 $Q_{opt}$를 구하는 방식을 활용하되, target을 $\hat{Q}_{opt}$에 따른 $\V_{opt}$를 활용하여 $r+\hat{V}_{opt}$로 한다. 

On-policy와 Off-policy

 위의 네 방법을 보면, Model-based Monte Carlo와 Q-Learning의 경우에는 추정하는 값이 $\pi$에 독립적이다. 이러한 경우를 Off-policy라고 하며, 반대로 Model-free Monte Carlo와 SARSA의 경우에는 추정하는 값이 내가 데이터를 얻기 위해 취한 $\pi$에 의존적이며, 이러한 경우를 On-policy라 한다. 즉, 직접적으로 optimal value를 구하는지 아니면 $\pi$에 따른 value를 먼저 구하는지가 두 개의 차이라 할 수 있다.

 여기서는 앞의 MDP와는 달리, 우리의 전략이 자신의 state $s$ 뿐 아니라, 상대 플레이어들의 전략으로부터도 영향을 받는다. 여기서는 플레이어가 둘(나 agent와 상대 opp)인 제로섬 게임(내가 $10을 따면, 상대는 $10을 잃는다는 의미에서의)을 예로 설명한다.

Game

 기본적인 접근법은 searching problem과 MDP와 유사하다. searching problem은, 현재 나의 state $s$ 노드가 $succ(s,a)$들을 자식노드로 같는 식으로 트리를 만들고 그 트리를 탐사함으로써 최적의 선택(action $a$)를 찾는다는 것을 의미하며, MDP처럼 state $s$에서 취할 수 있는 actions $a$들이 존재한다. 단지 여기서는 state $s$가 $Players(s)$에 속해있다. 또한, MDP에서는 $a$를 취할 때마다 cost가 존재했다면, 여기서는 $s$가 end state에 도달해야 Utility(s)가 존재한다( 게임이 끝나야 내가 내가 이겼는지 졌는지 알고 그에 대한 보상을 받는다). 또한, agent와 opp가 번갈아가며 $s$를 결정하고 둘의 $s$는 서로에게 fully observable하다.

 이 강의에서 사용한 예시는 다음과 같다. A박스에는 -50과 50이, B박스에는 1과 3이, C박스에는 -5와 15가 들어있으며, agent는 A, B, C 중에서 하나를 고르며, opp는 agent가 고른 박스에 들어있는 2개의 공 중 하나를 고른다. 따라서 당연히 공에 써있는 값을 최대화하기 위한 agent의 전략은 opp의 전략에 의존할 것이다. opp가 둘 중 아무거나 고른다면 박스안의 공의 평균이 가장 높은 C박스를 고르는 것이 최선의 전략일 것이고, opp가 둘 중 낮은 값의 공을 뽑는다면 들어있는 공의 최솟값이 가장 큰 B박스를 고르는 것이 최선일 것이다. 이 강의의 목적은 이러한 전략을 모델링하고 컴퓨팅을 통해서 최적의 전략을 찾는것이다.

 이 게임에서의 Value $V_{eval}$은 다음과 같다.

 $V_{eval}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \sum_{a \in Actions(s)} \pi_{agent}(s,a)V_{eval}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{eval}(Succ(s,a)), & Player(s) = opp \end{cases}$

 2, 3번째 조건은, 누구의 턴이냐에 따라 누구의 policy를 기반으로 V값을 계산해야 하는지 나타낸다.

Expectimax

 agent가 자신의 전략을 정할 때, 가장 기본적인 전략은 내 이득을 최대화하는 선택을 하는 것이다. 이러한 선택을 하는 노드를 max노드라 한다. 이러한 max노드에서는 가장 큰 값을 같는 자식 노드를 취한다. 즉, MDP의 예제에서처럼 가능한 모든 자식노드들에 대한 평균값을 V 값으로 취하는 것이 아닌, 최댓값을 갖는 자식 노드를 취하며, 이러한 방식에 의해 얻어진 V값을 expectimax value $V_{exptmax}(s)$라 한다. 위의 예제에서 상자를 고르면 안의 두 공 중 랜덤하게 하나가 선택된다면 $V_{exptmax}(s) = 5$ 가 된다(두 공 중 하나가 임의로 선택되므로 평균값이 가장 높은 상자를 취한다). Expectimax를 취하는 경우의 V 값은 다음과 같다.

 $V_{exptmax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{exptmax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{exptmax}(Succ(s,a)), & Player(s) = opp \end{cases}$

  이 경우의 전략을 나타내면 아래와 같다.

$\pi_{exptmax(r)} = arg \max_{a \in Actions(s)}mean_{a \in Actions(s)} V_{eval}(Succ(s,a))$ (agent의 전략)

$\pi_{r} = \begin{cases} \min_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \\ \max_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \end{cases}$ (opp의 전략)

 즉, opp는 아무거나 뽑고, agent의 경우에는 공들의 평균값이 가장 높은 것을 고른다.

 이러한 접근의 문제점은 상대방의 전략이 $\pi_r$이 아니면 제대로 대처할 수 없다는 것이다. 위의 예제를 예로 들면, 상대가 두 공 중 임의로 공을 뽑지 않고 두 공 중 값이 낮은 공만을 뽑을 경우 제대로 대처할 수 없다.

Minimax

 위의 문제를 해결하기 위한 전략이 Minimax 이다. 즉, 최악의 경우만을 상정하여 내가 취할 전략을 정하는 것이다. 위의 예제에서는 상대가 값이 낮은 공만을 뽑을거라고 생각하며 $a$를 취하게 되므로 공의 값들 중 낮은 값이 가장 큰 B 상자를 택하게 될 것이다$V_{minimax}(s) = 1$. 이러한 경우의 V값은 아래와 같이 주어진다.

 $V_{minimax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{minimax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \min_{a \in Actions(s)} \pi_{opp}(s,a)V_{minimax}(Succ(s,a)), & Player(s) = opp \end{cases}$

 즉, 상대는 최솟값만 선택하므로, 나는 최솟값이 가장 큰 상자를 선택하는 것이다. minimax에서의 전략 $\pi$는 다음과 같이 주어진다.

$\pi_{max} = arg \max_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (agent의 전략)

$\pi_{min} = arg \min_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (opp의 전략)

비교

 이제 agent와 opp의 전략에 따라 $V$가 어떻게 달라지는지 보겠다. 먼저, $\pi_{opp} = \pi_{r}$ 인 경우에는

$V(\pi_{exptmax{r}},\pi_r) = 5, V(\pi_{max},\pi_r) = 2$ 가 된다. 또한, $\pi_{opp} = \pi_{min}$ 인 경우에는, $V(\pi_{exptmax{r}},\pi_{min}) = -5, V(\pi_{max},\pi_{min}) = 1$ 가 되다. 즉, agent가 opp의 전략을 제대로 알지 못하는 경우에는 손해를 볼 수 있다.   

Computation

 위와 같은 단발성 게임이 아닌 체스 등과 같이 상대와 내가 계속해서 Action을 취하는 경우 나의 최적의 선택을 찾기 위해서는 위와 같은 트리를 만든 후, 가장 최적의 해를 주는 branch를 찾으면 될 것이다. 하지만, 여기서 문제는 tree가 너무 커지면 모든 가능성에 대해서 탐사하는 것이 현실적으로 불가능하거나 너무 비효율적이라는 것이다. 선택지가 b개이고, 트리의 깊이가 d까지 내려갈 경우에 완전탐색을 하게 되면 시간복잡도는 $O(b^{2d})$이 된다. 여기서 해결책이 두가지가 있는데, 첫번째는 내가 게임에 대하여 잘 알고 있을 경우, 트리를 탐색하지 않고, 현 상황을 분석하여 적절한 점수를 주어 결괏값을 예측하는 것이다. 예를 들어 체스의 경우, 왕의 안전성, 가지고 있는 말의 개수, 움직일 수 있는 말의 개수 등을 이용하여 각 $a$에 대한 Reward를 계산하는 방법이 있다. 두번째는 tree의 필요없는 가지들을 쳐내는 것이다.

요약

 LMS 알고리즘은 가장 유명한 학습법 중 하나이며, LMS 알고리즘은 성능이 좋으면서도, 빠르고 효율적이며 코드 짜기도 쉽다. 본 포스트에서는 선형회귀만을 다룹니다.

Adpative Filter

 LMS 알고리즘은 adaptive filter라고 할 수 있으며 filtering process와 adaptive process가 합쳐져 있다. $w$와 i번째 샘플 $x(i)$로부터 예상된 결과가 $y(i)$라 할때, $y(i)$와 실제 정답 $d(i)$를 비교함으로써 error $e(i)$를 얻는 과정이 filtering process이고, $e(i)$로부터 $w$를 적절하게 수정해 나가는 과정이 adaptive process이다.

 어떤 이상적인 분류기의 모델로서 optimal solution $w*$가 있다고 할때, 실제 $w*$는 알 수가 없으므로, 우리의 목표는 가지고 있는 sample들로부터 error를 가장 작게 만드는 $w$를 찾는 것이다. $w$에 관한 error를 $\mathcal{E}$라 하면, $\mathcal{E}(w*) <= \mathcal{E}(w)$ 일 것이며, $w*$가 optimal solution일 조건은 $\triangledown\mathcal{E}(w*) = 0$ 이다.

 $w$가 $w*$에 가까워지도록 하는 adaptive filter는 iterative descent의 방식으로 진행된다. 즉 i번째 iteration에서의 error를 $\mathcal{E}(w(n)) $라 하면 $\mathcal{E}(w(n+1)) < \mathcal{E}(w(n)) $가 된다.

Steepest Decsent Algorithm

 말그대로 가장 가파른 곳으로 내려가는 알고리즘으로, $w$에 대한 에러 $\mathcal{E}(w)$의 경사가 가장 가파른 곳으로 내려가는 알고리즘으로, 

 $w(n+1) = w(n) - \eta $\triangledown\mathcal{E}(w)$

 $ \triangle w(n) = w(n+1) = w(n) = - \eta $\triangledown\mathcal{E}(w) = -\eta g(n)$

가 된다. 이러한 방식을 통해 $w$가 $w*$에 가까워지는 이유는 다음과 같이 error를 테일러 전개 함으로써 알 수 있다.

 $\mathcal{E}(w(n+1)) = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \mathcal{O}((\triangle w(n))^2) \simeq \mathcal{E}(w(n)) - \eta g^T(n)g(n) = \mathcal{E}(w(n)) - \eta \parallel g(n) \parallel^2$

 $ \therefore \mathcal{E}(w(n+1)) < \mathcal{E}(w(n)) $

Newton's Method

 이번에는 에러 함수를 이차항까지 테일러전개를 하면 아래와 같다.

 $ \triangle(\mathcal{E}(w(n))) = \mathcal{E}(w(n+1)) - \mathcal{E}(w(n)) $

        $ = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \frac{1}{2} \triangledown^2 \mathcal{E}(w(n))^T (\triangle w(n))^2 + \mathcal{O}((\triangle w(n))^3) - \mathcal{E}(w(n)) $

        $ = g^T(n) \triangle w(n) + \frac{1}{2} \triangle w^T(n) H(n) \triangle w(n)$, H(n)은 헤세 행렬 ( H(n) = \triangledown^2 \mathcal{E}(w(n))

 즉, $g(n) + H(n) \triangle w(n) =0$ 일때 에러의 차가 최소가 된다.

$\therefore w(n+1) = w(n) - H^{-1}(n)g(n)$

Gauss-Newton Method

 Todo

The Least Mean Square Algorithm

 에러 함수를 다음과 같이 정의하면

 $\mathcal{E}(w) = \frac{1}{2} e^2(n)$,

 gradient vector는 다음과 같다.

 $ g(n) = \frac{\partial \mathcal{E}(w)}{\partial w} = e(n) \frac{\partial e(n)}{\partial w} = - e(n)x(n)$

 여기서 Steepest Descent를 활용하여 $w$를 업데이트 시키면 다음과 같다.

 $ w(n+1) = w(n) + \eta x(n)e(n)$

LMS 알고리즘은 environment에 대한 정보가 하나도 없어도 적용이 가능하다.

코드로 구현한 내용은 전에 작성한 포스트에 있습니다.

요약

 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 의 책을 스터디한 내용을 정리한 것입니다.

요약

 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$의 확률로 후자를 택하는 방법이다.

요약

 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'상태에 계속 머무르기 위한 '도전'이 됩니다.

Generalization

Generalization의 필요성

 머신러닝에서 학습은 Train Loss를 줄이는 방향으로 진행된다. 하지만 우리가 원하는 것은 Training data에 대한 손실을 최소화하는 것이 아니라, 앞으로 우리의 모델이 마주하게 될 본적 없는 새로운 데이터를 잘 분류하는 것이고, 이를 위해 우리는 우리의 모델을 일반화(Generalization)해야 한다.

 즉, 모델이 Training data에 너무 맞춰지면 본적 없는 데이터에 제대로 대처하지 못한다.

방법

1. 차원을 줄인다.

 필요없는 input feature를 줄임으로써 우리의 모델이 너무 커지는 것(Training data에 민감해지는 것)을 방지한다.

2. Regularize

 $w$의 크기가 너무 커지지 않도록 한다. 전 강의에서 학습한 Gradient Descent를 예로 들면, 일반적으로 $\lvert \vec{w} \rvert$ 는 학습이 진행됨에 따라 커지는데, TrainLoss 이외에도 $\lvert \vec{w} \rvert$ 에 대한 제약을 줌으로써 $w$의 크기를 조절한다. ($min_\vec{w} (TrainLoss(\vec{w}) + \frac{\lambda}{2} \lvert \vec{w} \rvert^2)$)

 Gradient Descent는 다음과 같이 진행한다.

 $\vec{w} = \vec{w} - \eta(\triangledown_\vec{w} Loss(\vec{w,y,w}) + \lambda \lvert \vec{w} \rvert) $

 이러한 방식을 L2 Regularization이라 한다.

3. Training data로 부터 일부를 떼어 Validation data로 활용한다.

 Test data를 활용하지 않으면서, 새로운 데이터에 대한 반응을 보기 위하여 Training data 중 일부를 떼어 Validation data로 활용한다.

K mean clustering

Unsupervised learning

 보통 라벨링된 데이터는 구하기 매우 힘들다. 또한 데이터들은 그 자체로 여러가지 특징들을 가지고 있는데, 이러한 특징들을 자동적으로 찾아 분류하는 방법이다.

K mean clustering

 데이터들을 K개의 cluster로 묶는 방법이며, 각 데이터 $\phi(x)$를 cluster $k$의 centroid인 $\mu_k$ 중 centroid가 가장 가까운 cluster에 배정하는 방식이다. 이때 손실이 최소화되는 centroid의 위치를 찾는 방식으로 진행된다. 손실함수는 다음과 같이 모든 data로부터 소속된 cluster의 centroid까지의 거리의 합으로 정의한다.

 $Loss_{kmeans}(z,\mu) = \sum_i \lvert \phi(x) - \mu_{z_i} \rvert ^2$

Python Code

 먼저 클러스터링에 필요한 함수들을 정의합니다.

 클러스터의 개수는 2개로 고정하기로하고, 클러스터들의 첫 centroid는 램덤으로 주게되는데, 여기서는 편의상 (6,0)과 (0,6)으로 하겠습니다. 그러면 각 sample들은 색깔로 표시한 것과 같이 클러스터링 되게 됩니다. 여기까지가 아래 코드의 line4까지가 됩니다. 첫 그림에서는 $y=x$ 그래프를 기준으로 위 아래로 나누어진것을 확인할 수 있습니다.

 line6부터는 새로 할당된 클러스터들에 대하여 centroid를 다시 계산하고 이전의 에러보다 현재의 에러가 작은 경우, 바뀐 centroid를 채택하고 cluster를 다시 배정하게 됩니다.

* K-means 알고리즘에서 중요한 것은, K-means 알고리즘은 항상 local minimum에 도달하긴 하지만, 그곳이 global minimum이라는 보장은 없으며, 초기조건을 바꾸어가며 가장 적절한 centroid들을 찾아야 합니다.

Reference

Stanford CS221 Lecture4