My data lab

Ref - ReinForcement 2nd Edition.pdf

Richard S. Sutton

일단 해석학과 대수로 고통받던 나날중에 프로젝트를 위해 강화학습을 따로 스터디를 진행하였다.

바이블이라고 하는 Richard Sutton 의 책을 보면서 배운내용을 정리하고자 한다.

다만 수학을 보다가 이쪽 내용을 봐서 그런지 모르겠는데

전체적으로 Markov 전재를 하고 다룬다는 점에서 일반적인 문제를 특수한 경우로 정의하여 다루는 것 같고

일종의 점화식들 : 이렇게 돌리면 최적의 가치함수로 수렴할것 이다 라는 내용이 중간중간에 자주 나오는데

바이블이란 책을 보는데도  이 것들이 이유가 없이 애매하다. 일단 내가 잘몰라서 그런것이라 생각하고 넘어가긴했지만 생각해 볼점이 많을것 같다.

실제로 강화학습이 문제에 잘안쓰이는 이유도 이쪽으로 투영시키기 위해서는 첫번째로 State 로 상태를 정의할수 있는 문제 여야하며 두번째는 수렴성이 명확히 보장되지 않아서가 아닐까 싶다. (아니면 내가 잘 이해못했거나.. 책을 보고도 명확히 이해가 안되는건 역시 문제가 있다. )

chapter 3 MDP 

강화학습 에이전트 란 행동(Action)을 하면서 보상(Reward)을 얻는다. 내부적인 값은 상태(State) 값을 갖는다.

MDP

1. 상태를 갖는다. 상태를 갖음으로써, 즉각적인 보상외에 전이된 상태의 보상, 즉 Delay Reward 를 고려해야한다.

2. 지연된 보상을 고려하기위해서 v* q* 등을 고려한다. 

3. p 는 State-Trainsition Property 로 볼 수 있는데 바로 전 상태에만 영향을 받는다(Markov) 및 MDP 의 Dynmaics 이라고 불리기도한다.

4. 위로 부터 보상의 기대값 r(s,a) = Ra * sigma_s'( p(s',r | s,a)를 구할 수 있다.

5. 장기적 보상을 최대로 갖는 목표(goal)를 갖는다.

6. Policy 정책(pi) 에 대한 가치 함수 ( value function) 를 정책 pi 를 따랏을 경우 예상되는 이득의 기대값으로 정의한다.

7.  6 에서 정의한 내용들은 Bellman Equation(3.12), 아래와 같이 가치 함수(s) = 시그마(가치함수(s')* 상태전이확률) 을 만족해야한다. 이때 이후 가치함수를 이용함으로써 현재 가치를 알아내기 때문에 Bootstrap 기법이라고 하기도한다.

8. 6,7의 에 정의한 value Function 에 대해서는 최적 정책함수 (Optimal Value Function) 이 Uniquae 하게 존재 하고, 아래의 최적 Bellman Equation 을 만족해야한다.

7과 비교했을 때, 기대값이 아닌 최대값으로 Update 를 해야 하는것이 중요하다.

v의 경우 action 을 수행한 다음의 얻게될 전이확률 * 보상의 합 (action 수행뒤 다음 State 가 꼭 1개는 아니다)이 최대가 되야한다.

q 의 경우 현재 상태와 액션을 결정 되 있고 (s,a) s' 도 전이확률로써 결정되어있다. 그렇기 때문에 각각의 다음 state s' 에 대해서 취할수 있는 action a' 들 중 최대의 값을 갖는 a' 를 택한다. 즉 다음 State s' 에서 할 수 있는 action 중에서 최대 q* 를 가져와서 업데이트한다.

9. 8에 대해서 풀게되면, v* 또는 q* 를 알 수 있고, 최적정책은 탐욕적으로 결정하면된다.

9. MDP 라는 것은 보통 p 를 알고있다라는 것을 뜻한다. 즉 상태 와 상태전이확률에 대한 이해가 확실하고, MDP 에서 M(markov) 은 p 자체 를 정의 할수 있다는 것을 뜻한다.

2019년, ML 과 수학 공부를 위해 모대학원 수학과에 입학하고

강의 도중 ML 강의의 가장 기본이 된다고 하는 Andrew ng 강의노트를 Study 하고 재밌는 실험을 해보았다.

Andrew Ng 의 강의 노트에서는 머신러닝을 학습하기위해

사용되는 모델들을 Generative 한 모델과 Discriminative 한 모델로 분류 하는데,

Discriminative 한 모델은 판별적인 모델로서, 우리가 가지고 있는 데이타로 특정문제에 대해 답을 직접적으로 찾아내는

보다 직관적인 학습방법을 통해 학습을 진행하고 솔루션을 찾아낸다.

그렇기 떄문에 목적이 있는 클러스터링이나 분류 등 판별문제에 대해서는 강한 면모를 보인다. 

Generative 한 모델은 생성적 모델로서 데이터 자체가 어떤 분포를 가지고 있는지 학습하고, 그 분포에 따라서 

우리가 찾는 문제가 O일지 X지에 대해서 확률적으로 계산한다.

언뜻 보기에는 비슷해보이지만 두 모델은 생각보다 큰 차이를 가진다.  그 내용과 실험등에 대해서 이어서 설명하겠다.

Definition and Examples of Generative

• Generative : providing a model of how the data is actually generated P(X|Y) & P(X)
  

• Generative algorithms : make structural assumption on the model Estimate parameters of P(X|Y), P(X) directly from training data

• Naïve Bayes

• Gaussian mixture models

• Gans - Generative Adversarial Networks

Definition and Examples of Discriminative

• Discriminative : simply providing classification splits P(Y|X)

• Discriminative algorithms : classify points without providing a model of how the points are actually generated

• ‌Logistic regression

• Decision Tree

• Scalar Vector Machine

Generative Model 중 대표적인 Naive Bayes 알고리즘의 경우

P(x | y) 를 위와같이 sum up 한다. (l 은 라플라스 계수이다.) 결국 조건부확률 정의를 이용하여 카운트 하는 방식이다.

그리고 최종적으로 우리가 원하는 P(y | x)를 구해낼 때 Bayes Theorem 을 위와 같이 사용하게된다.

P(y | x) * P (x) = P(x | y) * p (y)  

P(y = T| x) = (P(x | y=T) * P(y=T)) / (p(x | y = T) * P(y=T) + p(x|y=F) * P(y=F))  < 훈련된과 가정을 통해 모두 통해서 모두 구해 낼수 있다.

이 때 모델이 Generative 하다라고 부르는 이유는 p(x|y=F) , p(x | y=T) 이항 들 때문이고, 이것들이 Generative 모델의 핵심이다.,

이 것을 DisCreate Variable 의 X 마다 sumup 을 통해 확률을 지정할 수도 있고,

이 것을 Contininous Variable 의 X 마다 sumup 또는 특정 분포를 따를것이다 라는 가정을 통해 확률을 지정할 수 있다.

반대로 Discriminative model 은 단순하다.

p(y=T | x) 를 구하기 위해서

위와 같은 cost function과 sigmoid function h(x) 를 정의한다.

cost function 을 위와 같이 정의하면 costfunction 은 주어진 x,y 에 대해서 h(x) 가 y 에 가까울 수록 최소가된다.

h(x) 를 결정하는것은 seta 인데 seta 가 결국 우리가 훈련시킬 변수이다.

이 cost function 은 seta 에 대해서 convex 함수이고, 특정 seta 값을 가질때 J(세타) 는 최소점을 가질 것이고,

그점을 찾기위해서

그라디언트 방향으로 세타를 업데이트 시키다보면 , 어느정도에서 수렴하게되는데,

그 점이 주어진 x 에 대해서 y를 얻기 위한 최적의 세타이다.

우리는 다시 주재로 돌아가서, Generative 모델과 Discriminative 모델중 어떤게 더 좋을까? 라는 주제로 돌아가자,

그러기 위해서는 가장 좋은 방법은 여러가지 dataset 들에 대해서 가장 simple 한 로지스틱/나이브베이시안을  돌려보고 비교해볼 것이다.

이것은 까다로운(?) 분포의 dataset 이다. O 와  X 를 분류하는 것이 우리의 목표이다.

위 직선은 로지스틱 레그레이션을 돌린 결과로, 수렴된 세타 값을 통해 분류기준이 어떻게 되었는지 plot 을 해보면,

세타를 normal 로 갖는 직선이될것이다. (공간에서는 plane , 보통 (세티^T)x = b 인 plane 이라고한다.

이 plane 기준으로 o 와 x 를 나누었을때, costfunction 이 최소화 된다. 결과는 0.6정도였던가.

이모델을 좀더 발전시켜서 2차원 poly rogistic Regression 으로 돌릴 수도있다.

그러기위해 가장 간편하게 X 의 dataset 의 차원을 아래와 같이 2차 항 까지 늘려주면된다.

X = { 1, x1, x2 }   >> X = {1, x1, x2 ,  x1^2, x2^2, x1*x2 }

이 문제에 대한 소스는 모두 아래 git 에 올려놓았다.

https://github.com/Sangil55/logregVsNavBayes

반대로 이모델에 Naive Bayesian 을 돌려보자.

일단 data 를 보면 x1,x2 모두 data 자체가 discrete 하다. 그런 dataset 에 대해서 navie bayesian 을 돌리기 위해서는

data 자체를 discrete 하게 만드는 방법과,  p(x|y) 가 특정 분포를 띌 것이라고 assumpt하는 방법이있다.

1.p(x|y) 가 특정 분포를 띌 것이라고 assumption

우리가 받은 dataset 을 통해 Y = true 일때 뮤와 시그마를 구해낼 수 있다. (평균과 분산)

우리는 그 데이타가 가우시안을 띌거라고 assumption 을 하자

그렇게 assumption 을 하면, 미리 구해낸 뮤와 시그마를 통해 

p(x|y=true) 의 분포를 위의 식 모델을 통해 바로 구해낼 수 있는 것이다.!

그렇다면 특정 x 가 들어왔을때 y = true 일 확률을 베이시안을 구해낼 수 있을 뿐더러 

이 모델이 왜 Discriminative 보다 강력한 면이 있는가하면, 위 확률 분포를 통해 특정 점을 sampling 을 할 수 있다는 점이다.

이 개념은 후에 생성적 모델 ( 학습된 결과를 통해 비슷한 data 를 generate)  하는 응용으로 이루어진다.

 아무튼 그가정을 통해 구해낸 평균과 /분산을 통해 문제를 분류해낸 결과는 아래와 같다.

두번째 그림이 Naive Bayesian 을 multinomial normal distribution 을 따른 다고 가정하고,

원래 의 평균/분산이 기존과 다르다고 생각하고 아래그림 처럼 확률분포를 modify 하기도 쉽다.

Naive Baysian 의 경우 좀더 discreate 한 data 에 대해서 좀더 잘 맞기 떄문에

우리는 data 자체를 discretize 하기도 하고, 그방법은 아래와 같이 여러가지이다.

그중에 가장 간단한 Equal width Interval 을 구현해보면

아래와같이 격자무니 data 가 만들어졌다.

소스는 github에 있다.

http://github.com/sangil55

이 결과는 NB-eqaul width discretize 한 결과가 dicision Tree 와 매우 비슷하다는 직관을 불러일으켰다.

그래서 NB vs Dicision Tree 라는 주제로 리서치를 해보았더니,

https://thesai.org/Downloads/Volume4No11/Paper_5-Performance_Comparison_between_Na%C3%AFve_Bayes.pdf

위와같이 누군가가 성능을 비교해노았다.

요역하면 NB 가 낮은 차원에비해 Dicision Tree 급에 높은 성능을 보인다. 라는 결론이다.

결국 결론내자면 NB는 낮은 차원으로도 높은 차원의 Data 도 분석해낼 수 있다는 것이다.

이것이 또한 generative model 의 강점이기도하다.

한편 Andrew ng 도 비슷한주재로 분석해본 페이퍼가있는데,

Andrew Ng

1. Logistic-Regression has lower asymptotic Erro  2.Bayes converges to its asymptotic Error more quickly
   이 페이퍼를 요약하자면, Logistic Regression 이 보다 general 한경우에 더 작은 수렴 error을 갖는다.
   결국 data fit 이 잘된다라는 내용이다., 그리고 NB 의 경우 더작은 data 를 통해서도 좋은 학습률을 갖는다.

Ref - http://ai.stanford.edu/~ang/papers/nips01-discriminativegenerative.pdf

간단히 이번테스트에서 결론을  내보면 아래와 같다.

일종의 머신러닝계의 족보

내가 정리한것보다 그림으로 표시하니 보기 좋네

다만 이것도 대분류로 나눠서그렇지 서로 다들 연관이있기때문에 무슨 의미가 있나 싶다.

data 직업군의 특성상 분류하기를 그냥 좋아함 ㅇㅇ