[지능시스템/Intelligent System] 6장. Probability-based learning, Conditional Independence and Factorization

1.Conditional Independence

만약 어떤 event가 다른 event의 확률에 영향을 주지 않고 또한 vice versa 하다면, two events는 서로에게 independent하다고 할 수 있다.

만약 두 event X,Y가 independent하다면,

$$P(X|Y) = P(X)$$

$$P(X,Y) = P(X)P(Y)$$

event간의 full independence는 quite rare하다.

더 자주 발생하는 경우는 두개, 혹은 그 이상의 event 들이 third event가 발생할 경우 independent가 되는 경우이다.

이를 conditional independence라 한다.

두 event X,Y에 대해서, third event Z에 대해 conditionally independent하다고 생각해보자. 그렇다면

$$P(X|Y,Z) = P(X|Z)$$

$$P(X,Y|Z) = P(X|Z)P(Y|Z)$$

이 conditional impedence가 만족하면 chain rule을 다시 적을 수 있다.

원래의 chain rule은 다음과 같았다.

만약 event of the target feature t=l이 발생했을 때 event가 q[1],...,q[m]에 value를 assign한다면, 즉, conditionally independent하다면, 

P(q[2]|q[1],t=l) = P(q[2]|t=l)이고

P(q[3]|q[2],q[1],t=l) = P(q[3]|t=l)이 된다.

따라서 chain rule은 다음과 같이 변형된다.

그러면 Generalized Baye's Theorem을 다음과 같이 변형할 수 있다.

 

2. Factorization

이 Conditional independence는 또한 full joint probability를 좀더 compact하게 나타낼 수 있게 한다.

예를 들어보자.

Meningtis dataset의 joint probability distribution은 다음과 같았다.

descriptive features가 given meningtis에 대해 서로 conditionally independent하다면, 더 간단하게 나타낼 수 있다. P(H,F,V,M) = P(M) * P(H|M) * P(F|M) * P(V|M)이 되고, 모든 feature은 true or false의 binary이므로, 우리는 feature이 true인 경우에만 계산하면 된다.

features간의 conditional independence에 대한 가정은 full joint probability distribution의 factorization을 가능핳게 한다. 따라서, 우리가 계산해야 할 probabilities의 수와 저장해야되는 값들을 줄여준다.

예를들어 1 target과 9개의 descriptive features가 있다고 하자.(all with binary)

원래대로라면 full joint probability distribution은 2^10 = 1024개가 필요하다.

하지만 만약 모든 descriptive features가 conditionally independent given the target feature이라면, 19개 확률에 대해서만 나타내면 된다.

 

예제)

h,f,v가 m이 주어졌을 때 conditionally independent하다고 가정할 경우, 7개의 factor만 계산한다.

그 결과로 ~m을 출력하면 된다. 따라서 MAP prediction의 결과는 MENINGTIS = false이다.

Bayesian prediction model이 reasonable probabilities를 계산할 수 있게 되었다. 

 

3. The Naive Bayes Model

: probability-based ML에서 표준 approach이다.

MAP prediction을 리턴하는데, posterior probabilities for target feature level이 conditional independence에 대한 가정을 바탕으로 계산된다. 

naive bayes model은 train하기 편하다. 

1) 각각의 target level에 대해 prior을 계산한다.

2) given each target level에 대한 각각의 feature 조건부 확률을 계산한다.

 

이 naive bayes model은 categorial prediction task에 대해서는 놀랍게도 accurate하다. 왜냐하면 errors in the calculation of posterior probabilities for different target levels이 prediction errors에 반드시 나타나지는 않기 때문이다.

하지만, Naive Bayes model은 continuous target을 predicting하기에는 알맞지 않다. 왜냐하면 continuous target에서 errors in posterior probabilities는 직접적으로 model의 accuracy에 영향을 미치기 때문이다.

 

그 외의 Naive Bayes Model의 장점

1) curse of dimensionality로 인한 overfitting problem에 robust하다. 또한, small datasets이나 sparse data와 잘 맞는다.

2) training이 상대적으로 빠르고 매우 큰 dataset에 대해 compact representation이 가능하다.

3) categorial target prediction tasks에서 reasonable accuracy results를 보인다. 하지만, 다른 prediction model에 비해서 powerful하지 않을 수 있다.

4) limited data를 이용할 때 baseline accuracy score을 정의하기에 좋다.

 

예제 ) 

naive bayes model을 training시키기 위해서 확률들을 계산해야한다.

이제 Credit History = paid

Gaurantor/Coapplicant = none

Accomodation = rent 가 주어진다.

Fraudulent를 예측해보자.

계산결과 ~fr이 더 크기때문에 , Fraudulent는 falase를 반환한다.

다음은 이 Naive Bayes model에 대한 Potential Problem을 살펴보자.

Credit History = paid,

Gaurantee/CoApllicant = guarantor

Accomodation = free일 때를 예측하면?

계산결과가 둘다 0이기 때문에, 예측을 할 수 없다.

 

이러한 문제를 해결하기 위한 방법이 Smoothing이다.

Smoothing은 events로부터 몇몇 probability mass를 가져와서 events with low probabilities와 share한다. 즉 probability가 큰 놈이 작은 놈에게 값을 조금 나눠주는 것이다. feature 들의 확률의 합은 1.0이어야 한다.(total probability mass)

만약 적절히 smoothing이 수행되었다면, total probability mass는 1.0으로 유지될것이지만 spread of probability across the sets는 smooth하게 될것이다.

위 예제에서, fraud = false일 때 sum across the posterior probability distribution는 1.0이다.

 

확률을 smoothing하는데에는 다양한 방법이 있다. 그중 Laplace smoothing 을 이용할 것이다.

smoothing을 쓰는 가장 주요한 이유는 zero probabilties를 없애는 것이다. 일반적으로 prior probabilties는 smooth하지 않는데 왜냐하면 최소한 하나의 instance는 training data의 각각의 target level에 속해있을 것이기 때문이다.

따라서, 우리는 conditional probabilties를 smoothing하는데에 집중한다.

count(f=v|t)는 target level이 t일 때 event f=v가 얼마나 자주 일어나는가를 나타낸다.

count(f|t)는 target level이 t일 때 feature f가 얼마나 자주 dataset으로부터 어떤 level을 갖는지를 뜻한다.

즉 count(f=v|t)의 총합이다.

|Domain(f)|는 feature f의 level이 몇개나 있는지에 대한 domain을 나타낸다.

k가 커질수록 more smoothing이 발생한다. 일반적으로 k=1,2,혹은 3이다.

그렇다면 위 smoothing을 아까 예제에 다시 적용해보자.

A fraud dataset은 다음과 같다. fr = true일때만 해보자.

P(fr) = true / all = 6 / 20 = 0.3

p(CH = none|fr) = 1 / 6 = 0.1666

p(CH = paid|fr) = 1 / 6 = 0.1666

p(CH = current|fr ) = 3 / 6 = 0.5

p(CH = appears|fr ) = 1 / 6 = 0.1666

 

p(GC = none|fr) = 5 / 6 = 0.8334

p(GC = guarantor|fr) = 1 / 6 = 0.1666

p(GC = coapplicant|fr) = 0

 

p(ACC = own|fr) = 4 / 6 = 0.6666

p(ACC = rent|fr) = 2 / 6 = 0.3333

p(ACC = free|fr) = 0

 

k=3일때,

count(GC|fr) = 6

count(GC = none|fr) = 5

count(GC = guarantor|fr) = 1

count(GC = coapplcant|fr) = 0

이제 smoothing을 시작한다.

P(GC = none|fr) = (5+3) / (6+(3*3)) =  0.5333

P(GC = guarantor|fr) = (1+3) / (6+(3*3)) = 0.2667

P(GC = coapplicant|fr) = (0+3) / (6+(3*3)) = 0.2

나머지에 대해서도 동일하게 수행할 경우 결과는 다음과 같다.

그럼 CH = paid, GC = guarantor, ACC = free일 때의 F값을 예측해보자.

fraudulent = false로 예측된다.

smoothed probabilty를 이용해서, both target levels에 대한 score를 게산할 수 있게 되었다.