[Data Mining] Markov Process, Markov Reward Process

이전 포스팅에서 Reinforcement learning을 공부해봤다. Reinforcement learning의 일부로 Markov Decision Process라는 것이 있는데, 이것을 공부해보려고 한다. 그런데 이것을 공부하려면 먼저 Markov Process와 Markov Reward Process를 먼저 공부해야한다. 그래서 이번 포스팅에는 이 두 개를 먼저 설명하고 다음 포스팅에서 Markov Decision Process를 설명하도록 하겠다.

우선 Markov Process이다. 아래와 같은 그래프가 있다고 해보자.

이 그래프를 간략하게 설명하자면... class1에서 class2로 갈 확률이 0.5 페북을 할 확률이 0.5!! 한번 패북을 하면 0.9확률로 계속 페북을 하고.. 뭐 이런 쉬운 그래프이다. 이 그래프에서 여러가지 흐름이 있을 수 있다. 예를 들어서 

흐름1 : Class1 - Class2 - Class3 - Pub - Class2 - Class3 - Pass - Sleep

이런 흐름이 있을 수 있다. Markov Process는 다음 State는 지금의 State에 의해서 결정된다는 이론이다. 무슨 말이냐면... 위의 흐름에서 Pub에서 Class2로 가는 것은 이전에 어떤 흐름을 거쳤든 오로지 Pub→Class2의 확률에 의해 결정된다는 것이다. 이전에 Class1에 있었든 pub에 있었든 페북을 했든 상관이 없고 오로지 현재 Pub에 있다는 사실에 의해 결정된다는 것이다. No History At All!! 이것이 Markov Process이다. 

위의 그래프에서 각각의 State에서 다음 State로 넘어가는 확률을 조건부 확률로 표현할 수 있다. 예를 들어 Class1에서 Class2로 넘어가는 확률은 P(Class2|Class1)으로 나타내고 그 값은 0.5가 된다. 이런 조건부 확률을 아래와 같이 표로 나타낼 수 있다.

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf

Markov Reward Process는 Markov Process에 Reward 개념을 추가한 것이다. 위의 그래프에서 아래와 같이 Reward를 추가해보자.

Markov Reward Process에서는 Value라는 개념이 나온다. 각 State는 각각의 Value를 갖는데, 이 Value는 '값'이 아닌 '가치'의 Value이다. Value와 Reward가 둘다 '좋은 것'이기 때문에 헷깔릴 수 있다. 헷깔리지 말자. Value와 Reward는 다른 것이다. Value는 그 State에 있을 때 최종 목적을 이룰 수 있는 잠재력을 의미한다. 그 State에 있을 때의 당장의 이득(Reward)가 아닌 최종적으로 목적을 이룰 수 있는 잠재력을 의미한다. 예를 들어 아침에 일찍 일어나서 공부를 하는 것은 매우 힘든 일이다. 당장은 몸도 힘들고 그날 하루가 조금 힘들어질 수도 있다. 하지만 장기적으로 봤을 때 아침 일찍 일어나서 공부를 하면 그만큼 성실해지고 그만큼 성공적인 삶을 살 확률도 높아진다. 따라서 '아침공부'라는 State가 있다면 그것은 Reward는 작아도 Value는 클 수 있다는 것이다. 다시 한번 말한다. Value와 Reward는 다르다. 그러면 우리가 Value는 어떻게 구하는지 한번 알아보자. 

 Value Function으로 Value를 구하는데 Value Function에는 gamma라는 파라미터가 들어간다. 이 gamma는 항상 0과 1 사이의 값인데, 0에 가까울 때는 당장의 이득만 쫒아가면서 value를 계산하고, 1에 가까울 때는 멀리보고 value를 계산하게 된다. 식을 보면 이 말이 이해가 된다.

지금(t)에서의 Value는 아래와 같이 계산될 수 있다.

V(t) = Reward(t) + gamma*E( Reward(t+1) * p(state(t+1)|state(t)) )

gamma가 극단적으로 0이면 gamma^1*Reward(t+1)와 이후 부분이 모두 0이 되므로 현재의 Reward인 Reward(t)가 V(t)가 되버린다. 즉 미래에 얻을 Reward는 하나도 생각 안 하겠다는 것이다. 한번 예를 들어서 Value 하나를 계산해보자.

Value(Class3) = Reward(Class3) + gamma*(p(Pub|Class3)*Reward(Pub) + p(PASS|Class3)*Reward(PASS))

Value(Class3) = -2 + gamma*(0.4*1 + 0.6*10)

gamma = 0.9로 놓으면,

Value(Class3) = -2 + 0.9*(0.4*1 + 0.6*10) 

Value(Class3) = -2 + 0.9*(6.4)

Value(Class3) = -2 + 5.76

Value(Class3) = 3.76

이것을 각 state 마다 계속 반복하면 거의 변하지 않는 어떤 상태로 Converge되는데 그 결과는 아래와 같다. 코딩한 것도 같이 업로드했으니 같이 참고해보기 바란다.

# 코드 : state.py

※ value는 최초에는 reward 값으로 초기화된다. 이 값은 Markov Reward Process를 거치면서 업데이트된다.

# 코드 : markov_reward_process.py

# 결과

이게 Markov Reward Process이다. 여기에 Action 개념을 추가한 것이 Markov Decision Process이다. 반대로 말하면 Markov Decision Process에서 Action이 완전히 정해진 것이 Markov Reward Process인데 아무튼 우리는 Markov Decision Process에 대해서는 다음 포스팅에서 더 자세히 공부해보도록 하자.