끄적끄적

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의 필요없는 가지들을 쳐내는 것이다.

요약

 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

Gradient Discent

 어떤 함수 $f(x)$가 있을 때, $f(x)$가 최소가 되는 $x$ 값을 찾는 방법으로, $f(x)$의 gradient의 반대방향으로 $x$값을 변화시키는 방법이다. (gradient의 방향이 $f(x)$를 최대화시키는 방향을 나타내는데, 우리는 $f(x)$가 최소가 되는 $x$값을 찾고 싶으므로 반대방향으로 움직여야 한다.)

Linear Regression

 Feature $\phi(x)$로 부터 $y$를 예측하는 선형회귀 모델에서 input $x$로부터의 예측값 $f_w(x)$는 다음과 같이 주어진다.

 $f_w(x) = \vec{w} \cdot \phi(x)$

출처 : https://blog.paperspace.com/content/images/2018/05/fastlr.png

 위의 그림은, $z$ 값이 $f_w(x)$가 되며, $x$가 2차원으로 $(x,y)$로 주어지는 경우로, 우리는 점이 찍혀있는 $f_w(x)$ 값이 가장 낮은 점의 $(x,y)$값을 찾기를 원하는 것이다.

Loss

 본강의에서는 Loss를 위의 예측값과 실제 값 $y$의 차의 제곱, 즉 residual의 제곱으로 한다. 즉, 최소제곱법 기반의 최적화를 한다.

 $ Loss(\vec{w}) = \frac{1}{\lvert D_{train} \rvert} \sum (\vec{w} \cdot \phi(x) - y)^2$ 

 따라서 Loss의 gradient는 다음과 같다.

 $ \triangledown_\vec{w} Loss(\vec{w}) = 2\sum(\vec{w} \cdot \phi(x) - y) \cdot \phi(x) $

Training

 위의 Loss를 최소화하는 방향으로 $\vec{w}$를 최소화 시키기 위해, gradient의 반대 방향으로 $\vec{w}$를 갱신해 주면 된다.

 $ \vec{w} = \vec{w} - \eta\triangledown_\vec{w} Loss(\vec{w}) = \vec{w} - 2\eta\sum(\vec{w} \cdot \phi(x) - y) \cdot \phi(x) $

 여기서 $\eta$는 gradient를 따라 얼마나 이동할 것인지를 정하는 값으로, 너무 작으면 학습이 느리고 너무 크면 너무 크게 움직이며 궤도 밖에서 빙빙 돌 수 있으므로 적절한 값을 정해야 한다.

Python Code

def F(w, data):
    return sum(w.dot(x) - y for x,y in data)/len(data)

def dF(w, data):
    return sum(2*(w.dot(x) - y) * x for x,y in data)/len(data)

def gradient_discent(true_w,data,w):
    eta = 0.01
    for i in range(10000):
        w -= eta * dF(w,sample)

w = np.random.randn(d)
gradient_discent(true_w,sample,w)

 F가 loss값이고, dF가 gradient 값이다. 위의 코드에서 true_w는 정답이 되고, sample은 학습시킬 데이터가 되며, w를 학습시키게 되며, 학습이 진행됨에 따라 w가 true_w값에 가까워진다.

Stochastic Gradient Discent

 위의 GD에서의 gradient는 모든 데이터값의 gradient의 평균이었다면, SGD에서는 각각의 데이터(임의의 선택된 데이터)에 대하여 학습을 진행한다. 얼핏 개개의 데이터에 대하여 학습을 진행하면, 결과가 좋지 않을 것 같지만 많은 경우 SGD가 GD보다 더 좋은 결과를 보여준다. 

 위의 GD의 경우 각 스텝마다 모든 데이터에 대하여 학습하므로 속도가 굉장히 느리다.

SGD에서의 Training

 $ Loss(\vec{w}) = \frac{1}{\lvert D_{train} \rvert} \sum_{(x,y)\in \lvert D \rvert} (\vec{w} \cdot \phi(x) - y)^2$

으로 GD와 같지만,

 모든 $(x,y)$에 대해서 각각 학습을 진행해준다.

 $ \vec{w} = \vec{w} - \eta\triangledown_\vec{w} Loss(\vec{w,y,w}) = \vec{w} - 2\eta(\vec{w} \cdot \phi(x) - y) \cdot \phi(x) $

Python Code

def sF(w,data):
    x,y = data
    return w.dot(x) - y
def sdF(w,data):
    x,y = data
    return w*(w.dot(x)-y)*x
def stochastic_gradient_discent(true_w,data,w):
    eta = 0.03
    for i in range(10000):
        for x, y in data:
            w -= eta*sdF(w,(x,y))

w2 = np.random.rand(d)
stochastic_gradient_discent(true_w,sample,w2)​

* 본 포스트는 Stanford의 CS221 강의를 보고 요약 정리한 것입니다.