Markov Decision Process


MDP를 배우기 전에 Markov 하다는 말의 정의와 Markov Chain, Markov Reward Process에 대해 알아보자.


[어떤 S(state), A(action)을 해왔을때(처음 어떠한 상태로부터 현재까지 지속) 현재상태까지 올 확률]


위와 같은 식이 아래와 같은 식으로 표현 된다면 state는 Markov 하다고 할수 있다.


[어떤 S(state), A(action)을 했을때(현재상태 바로 전 상태) 현재상태까지 올 확률]


스타크래프트를 예로 들면 어떤 게임 중간 상황은 그 상황이 일어나기 이전의 모든 상황들에 영향을 받아서 지금의 상황이 된 것이기 때문에,

지금 상황에 이전상황의 모든 정보가 담겨져 있다고 이해할 수 있다.



MDP는 state, action, station probability matrix, reward, discounted factor 로 이루어져 있다.


state 은 agent가 인식하는 자신의 상태를 말한다. 사람으로 치면 '나는 방에 있다' 라고 하면 여기서 '방'이 state이 된다.


action은 agent가 environment에서 특정 state으로 갈때 지시하는 것이다. 어느 쪽으로 움직일때 그것이 action이 되고 agent가 action을 취하면 실재로 오른쪽이나 왼쪽으로 움직이게 된다. 그리고 움직임으로써 state을 변화 시킨다.


State transition probability matrix 는 어떤 action을 취했을 때 state가 결정론적으로 딱 정해지는 것이 아니고 확률적으로 정해지게 되는데, 일종의 noise라고 생각해도 된다.

[state=s, action=a 일 때, state=s' 가 될 확률]


Reward는 agent가 action을 취하면 environment가 그에 따라 주는 보상이다. 게임같은 경우에는 'score', 바둑같은 경우에는 '승/패'가 된다.


[state=s, action=a 일 때, 받는 Reward의 기대값]


어떤 action을 취했을 떄 reward를 받게 됬을 때, 이 때 단순히 받았던 reward를 더해버리면 문제가 생긴다. reward를 각각 0.1, 1을 받는 경우가 있으면 시간이 무한대로 간다면 둘다 최종 reward 값은 무한대가 되므로 두 경우중 어떤 경우가 더 나은 건지 판단할수 없다. 또 한가지는 agent가 어떤 episode를 시작하자마자 1을 받은 경우와, 끝날 때(미래) 1을 받았을 경우, 둘다 최종 reward는 1이기 때문에 어떤 경우가 더 나은 건지를 판단 할 수 없다. 이렇기 때문에 discount factor 라는 개념이 등장한다.


Discount factor는 시간에 따른 reward의 가치를 달라지게 표현하는 방법이다. 보통 discount factor(γ)값은 0하고 1 사이이다. 

이 그림을 보면 이해하기 쉬울 것이다. 한단계씩 시간이 지날때 마다 γ 값의 승수가 늘어난다. 만약 γ 값이 0이라면 미래는 전혀 생각하지 않는 바로 앞 상황만을 보는 reward 값이 나올것이고, γ값이 1이라면 현재의 reward 가치와 미래에 나오는 reward값들의 가치는 같게 판단하므로 상당히 미래지향적이 될 것이다.


Markov Chain

MDP 에서 action과 reward 가 없다고 가정을 하면 state과 state 사이에는 transition matrix(전이 행렬)와 transition probability(전이 확률)가 있다.


이런 그림을 Markov Chain이라고 한다. 각각의 state로 움직일 때의 확률이 나와있고, 이 그림 같은 경우에 시간이 무한대로 흐른다면 모두 'Sleep'으로 수렴하게 될것이다. 그리고 더 이상 변화가 없기 때문에 'stationary distribution' 이라고 말한다. MDP에서는 action을 할 확률과 action을 해서 어떤 state로 갈 확률이 주어지게 된다.


Agent-Environment Interface

agent가 action을 취하고 state를 옮기고 reward를 받고 하면서 environment와 상호작용을 하는 것을 말한다.


agent가 observation을 통해서 자신의 state를 알게되면, 그 state에 맞는 action을 취하게 된다. 학습하지 않았을때는 random한 action을 취한다. 그러면 environment 에서는 agent에게 reward와 다음 state를 알려주게 된다.


Policy

말 그대로 '정책'이다. agent가 어떤 state에 도착하면 action을 결정하는데, 어떤 state에서 어떤 action을 할지 정해주는 것을 policy라고 한다. 결국 강화학습의 목적은 optimal policy(accumulative reward(누적된 보상) = retrun을 최대화 하는 policy)를 찾는 것이다.


[state=s 일 때, action=a를 할 확률]


MDP Graph

아까의 Markov chain 하고는 표현 방법이 다르다. 아까의 Markov chain에서는 state 사이에 transition이 있었지만, MDP Graph에서는 reward로 표현하게 된다.





원래 맥북 에어2012를 사용하여

Tensorflow를 구동했었다.


데스크탑에 리눅스를 설치하기가 너무 귀찮아서


only CPU만 써도 그렇게 속도 차이 많이 안나겠지 했다.



게이트가 하나일때는 속도차이가 있는지 몰랐다.


하지만 밑과 같이


사진에는 안나와있지만


 첫번째 레이어에는 784개의 게이트가 있고

두번째 레이어에서는 500개의 게이트를 넣고

세번째 레이어에 256개

네번쨰 레이어는 128개가 있다.....


1개일때와는 부하가 확실히 많이 걸릴수밖에 없다.



그래서 일단 맥에서 돌려봤다. only CPU


Xavier에다가 dropout 까지 적용시켜 

Mnist 의 정확도가 98%까지 나왔지만

실행시간이 265초나 걸렸다......


진짜 답답해 죽는줄...





그런데 이것들


윈도우 Use GPU 환경(GTX 960/cuda8.0/cudnn5.1)에서 실행시켜봤다.

(출력 포맷이 차이나는건 파이썬 버전차이다)


역시나 정확도는 98% 나왔다.

그.런.데. 실행속도가 40초.


거의 6배가 넘는 속도차이다.


 역시 괜히 머신러닝에서 병렬 컴퓨팅을 이용하는게 아닌거같다.






여러분 저렴한 Nvidia 그래픽카드라도 달아보세요











오늘부터 강화학습에 관한 내용들을 공부하고 있다.


애초에 국내에 머신러닝 강좌들도 많이 없지만,


그중에서도 RL(강화학습)에 관한 내용은 전무한 상황이라고 봐도 될정도다.


그러던 도중 아주 좋은 자료를 찾았고 오늘부터 정리를 하려고 한다.




Reinforcement Learning 


환경과 상호작용을 통한 학습 장법 중에서 computational 하게 접근하 것이 machine learning 이다.

이 ML의 학습 방법중 하나가 RL이다. 물론 DL(Deep Learning)도 ML의 하나이다.

ML 중에서 아이가 걷는것을 배우는 것처럼 처음에 어떻게 행동할 줄 모르지만, 환경과 상호작용을 하면서

걷는 법을 알아가는 것과 같은 학습을 RL이라고 한다.


좀더 자세하게 보면 어떤 Environment을 탐색하는 agent가 현재의 state를 인식하여 어떤 action을 취한다.

그러면 그 agent는 Environment로 부터 reward를 얻게 된다. reward는 양수와 음수 둘다 가능하다. 

강화학습의 알고리즘은 그 agent가 앞으로 누적될 reward를 최대화 하려는 일련의 행동으로 정의되는 policy를 찾는 방법이다.




+ Recent posts