PGM 2 Bayesian Network Fundamentals

다음 내용은 stanford 대학의 강의이다. https://class.coursera.org/pgm/class/index


Semantics & Factorization

여기서 예를 든 fully parameterized bayesian network 가 아래 그림
다섯가지 random variable에 대한 bayesian network를 그렸다. 참고로 bayesian network란 edge에 방향성이 있는 network를 의미

chain rule은 CPD(conditional probability distribution)을 곱한 것이다.

위의 예제로 chain rule을 적용해 보면

그래서 bayesian network를 정의해보면

그리고 BN이 Legal distribution이라는 걸 증명하는데 두가지를 보인다(즉 확률이라는 것). 그중 한가지가 BN이 확률값이기 때문에 0 이상의 값을 갖는다는 것과 다른 하나는 모든 값의 합이 1이 된다는 것을 보임.


Reasoning Patterns

causal reasoning 

그림처럼 위와같은 BN에서 strong Letter를 얻을 marginal probability를 0.5 구했다고 한다.
하나의 컨디션, 즉 여기서는 Intelligence에 조건을 건다면 이 0.5의 확률이 0.39 로 변하게 된다 (intelligence의 condition이 low intelligence 였다), reasoning goes causal direction으로 가게 된다.

Evidential Reasoning goes from bottom to up.

위그림에서 보듯이 grade에 condition을 잡고 그것의 ancestor인 random variable의 확률을 구하는 것. 그림에서 보듯이 intelligence의 경우 좋은 확률이 0.3 이엿는데 grace가 C 라는 조건에서 intelligence가 좋은 확률은 0.08로 줄어들게 된다.

Intercausal Reasoning
두 node (여기서는 random variable) 가 연결점(edge) 가 없을 때의 reasoning.

위 그림2개를 보자면
intelligence가 좋은 경우,즉 P(i1)은 0.3 이였다. 그런데 evidential reasoning, 즉 grade 가 C라는 조건 g3 아래에서의 intelligence가 좋을 확률은 P(i1|g3) 은 0.08까지 떨어지게 된다. 여기서 intercausal reasoning을 추가 하게 되면, 즉 수업이 어려웠다는 조건 d1을 추가하게 되면 P(i1|g3, d1)의 값은 0.11 살짝 오르게 된다.
두번째 그림을 보게되면 다른 점이 g2, 즉 학점을 B를 맞앗다는 건데, 여기서 보면 P(i1|g2,d1) 값이 상당히 커짐을 알수 있다(심지어 P(i1)보다 크다). 이는 상식적으로 생각해 보면 머리가 좋다면 수업이 어렵건 쉽건 c를 맞을 확률은 적지만 b 는 맞을 수 있기 때문이다.

Intercausal reasoning을 이해하기 위해 다음을 보자 (intercausal reasoning을 두 random variable 간에 edge가 없기때문에 서로 영향이 있다는 것이 이해하기 어려울 수 있기 때문에).

원래는 x1과 x2는 independent 하다. 그러나 y 값이 1 이라는 가정을 두게 되면 더이상은 x1과 x2가 independent 하지 않게 된다. y=1 이기 때문에 위의 표에서 첫 줄(빨간색으로 제거한 줄)은 더이상 의미가 없게 되고 나머지 각 확률은 0.25에서 0.33 으로 바뀌게 된다. 곧 P(x1=1) = 2/3, p(x2=1) = 2/3 가 된다. 그런데 x1=1이 였다든 조건 하에 x2=1일 확률, 곧 P(x2=1|x1=1) 은 0.5 가 된다. 곧 x1의 조건하에 x2의 확률이 변하게 되므로 x1과 x2는 더이상 independent 하지 않게 된다.

다시 처음 예로 들어가서 학생의 추가적인 정보, SAT 점수를 알게 되었다고 한다면 특히나 SAT  점수가 높앗다고 한다면 비록 학점이 c 였지만 똑똑할 확률이 올라가게 되고 그 수업 자체가 어려웠을 확률 역시 올라가게 된다.

Flow of Probabilistic Influence
x 노드가 y 노드에 영향을 줄때, 곧 x에 대한 조건이 y의 belief(=확률)에 영향을 미치는 경우는 아래와 같다. 오지 마지막 경우는 x가 y의 영향을 주지 않는다.

x -> y : x가 y의 parent 일때
x <- y : evidential reasoning
x -> w -> y : difficulty->grade->letter
x <- w <- y : difficulty<-grade<-letter
x <- w -> y : intelligence
x -> w <- y : v structure 라고도 함, difficulty랑 intelligence가 grade에 영향을 주는 경우. 클래스의 difficulty에 대한 어떠한 condition도 intelligence의 확률값에 영향이 없다.

곧 v structure 만 없다면 한 노드에서부터 다른 노드까지의 trail이 active, 곧 연결된 random variable 사이에는 influence가 존재한다.

trail 이란건 하나의 edge에 의해 연결되 path.

이번에는 특정 z node에 대한 evidence 가 있을때 x 노드가 y 노드에 영향이 있는지를 알아본다.

위에서 x노드랑 y 노드가 직접 연결되어 있는 경우는 z 노드의 evidence의 유무에 상관없이 영향이 있을것이고, w 노드를 거치는 경우를 생각해보면 w가 z 노드와 동일 할때랑 w와 z 노드랑 동일하지 않은 노드 일 경우로 나누어서 생각하게 될 것이다. 세번째에서 다섯번째의 경우는 z노드의 evidence의 없을 경우(w node가 z 노드가 아닌 경우)는 x가 y에 influence가 있다는 것을 이전에 보았다. 반면에 w 노드가 z 인 경우, 즉 w의 evidence가 있을 경우에는 세번째에서 다섯번째의 경우 x 노드가 y 노드에 영향을 미치지 못하게 된다. 예를 들자면 grade가 정해졌다면(곧, evidence가 있다면) letter 는 순전히 grade에 영향을 받는 것이기 때문에 difficulty가 어떻게 변하던 letter에는 영향을 미치지 못하게 되는 것이다.
여섯번째의 경우에는 w 노드의 evidence가 관측된 경우(w 노드가 z 노드에 포함된 경우) 에는 x 노드가 y 노드에 영향을 주게 된다(intercausal reason). 하지만 w노드의 evidence가 발견되지 않은 경우에는 w 노드와 그 아래 자손 노드들 전부의 evidence가 발견되지 않은 경우에만 x 가 y에 영향을 주지 않는다. 즉 비록 w 노드의 evidence가 발견되지 않았다고 하더라도 z 노드가 w 노드의 자손 노드라면 z 노드에 의해 w 노드가 영향을 받을 것이고 곧 w 노드에는 어느 정도의 evidence가 생기게 되므로 x 노드는 y 노드에 영향을 미치게 된다.

다음은 예제를 통한 어느 노드에 evidence 가 있느냐에 따른 x가 y로의 influence가 있는냐를 본다.

정리하자면 다음과 같다.

Conditional independencies (Preliminaries)

두 event a,b의 independence를 정의한다.

위 그림에서 "ㅑ" 는  satisfy를 의미하며 "ㅗ" 기호는 independence를 의미한다.


예를 보자면 아래와 같다

random variable G 에 대해 marginalize 를 한뒤 또 다시 한번 marginalize 를 한다. I 와 D는 서로 independent 하다는걸 알 수 있다.


그런데 이 indepence는 굉장히 rare 하다. 그래서 좀더 broad 한 개념의 conditional independence를 알아본다.

위 조건은 동등한 조건으로 어느 하나만 만족하면 두 random variable x와 y는 조건 z 아래서 independent 하다는 것. 첫 3개의 조건은 그냥 indepence와 유사하다. 다만 random variable z의 조건이 주어졌다는 조건하에 성립한다는 점만 다르다. 그리고 마지막 조건은 x,y,z의 joint probability가 x,z 라는 factor와 y,z 라는 factor의 곱과 비례하다는 것(이를 통해 normalization과정을 고려하지 않아도 된다).

conditional independence의 예를 들어보자.

두 개의 동전이 있다고 하자. 하나는 fair 한 동전이고 하나는 bias 한 동전으로 앞면이 나올 확률이 90프로라고 하자. 이 동전중에 하나를 뽑고 두번 던진다. 뽑은 동전이 fair 한건지 bias 한건지 모른다고 가정하고 만약에 처음 던졌을때 앞면이 나왔다면 두번째 던졌을때 앞면이 나올 확률은 어떻게 될것인가 생각해보면 아마도 뒷면이 나올 확률보다 높을거라 예상된다. 이는 fair 한 동전을 뽑을 경우에는 반반의 확률이지만 bias 한 동전을 뽑았을 경우에는 앞면이 나올 확률이 훨씬 높기 때문에 뽑은 동전이 무엇인지 모르고 첫번재 나온 면이 앞면 이다라는 사실에서는 두번째 던졌을때 역시 앞면이 나올 확률이 높을 것이라 예상되는 것이다. 그런데 만약에 어떤 동전을 뽑았는지 안다면 첫번째에서 앞면이 나온 사건과 두번째에서 앞면이 나온 사실은 independent 하게 된다(어짜피 각 동전의 앞면이 나올 확률은 알고 있고 각 사건(동전을 던지는 행위)는 서로 영향이 없기 때문에).

또다른 예를 보자.

위 예에서 보면 intelligence가 나쁘다는 가정이 되면 S 와 G independence 하다는 것을 알수 있다.

오히려 conditioning이 independence를 잃게 하는 경우도 있다.

앞전에 봤듯이 원래는 I 와 D 는 서로 independent 했지만 P(I|g1)과 P(D|g1)을 구해보면 G 가 conditioning 이 되면서 I와 D 더이상 independent 하지 않게 됨을 알 수 있다.

Independencies Bayesian Networks
위에서 알아본 independence가 bayesian network에 어떤식으로 나타나는지 살펴본다.

먼저 어떻게 independence랑 factorization이랑 연관이 있는지 알아본다.

independence의 조건이 곧 두 random variable의 joint probability를 두 factor의 곱으로 표현되는 factorization을 의미한다. 이와 같이 특정 확률분포의 factorization은 그 확률분포 내의 independencies를 의미한다. 마자막 문장이 이번 서브챕터의 핵심. 만약에 확률분포 P가 그래프 G 에서 factorization된다면, 과연 G 의 구조만으로 우리는 P가 만족하는 independencies를 찾을 수 있을까?

먼저 flow of influence와 d-separation의 개념을 소개한다.

위의 경우 오른쪽에 있는 graph는 flow of influence를 나타낸다. G 노드의 observation이 있다는 가정하에서는 v-structure 라도 S->I->G->D로의 probability influence가 있다.

위 theorem의 증명을 x=D, y=S를 예로 보여준다(여기서는 G의 observation이 없다. 곧 v-structure로 인해 flow of influence가 막혔다). S에서 D로의 path는 하나 밖에 없고 그리고 G의 evidence가 없는 관계로 d-sep(D,S|Z) 임을 가정한다. (D,I,G,S,L) 은 P(D)P(I)P(G|D,I)P(S|I)P(L|G) 로 factorization 된다. 그리고 식처럼 marginalization을 통해서 P(D,S)=  factor of D * factor of S 가 됨을 알 수있다. 곧 D와 S가 independent 하게 됨을 보인 것이다. 여기서 중요한 것은 d-sep는 graph 차원의 용어이고 independence는 P 확률차원의 용어이다.

두 노드는 한 노드의 부모 노드가 conditioning이 된 조건하에 서로 non-descendant가 아니면 서로 d-separated 이다.

위에서 S(sat)와 L(letter)를 보자. 두 노드는 서로 non-descendant 하다. letter의 parent 노드인 grade의 정보가 주어졌을때(conditioning) S와 L을 연결하는 그 어떠한 path도 inactive 되어 있다(곧 d-sep(S,L|G) 를 의미). S->I->G->L의 path에서는 G가 정보가 주어졌기 때문에 S와 L은 서로 independent 하게 되며 S->J->L의 경우에는 v-structure로 J의 정보가 없이는 서로 영향을 주지 않게된다.

I-maps (independency maps)

그래프 G내에 있는 d-separation이 확률분포 P에 의해 만족이 된다면(곧 확률분포의 두 변수가 독립이라면) 이 그래프 G는 P의 I-map 이라고 한다. 이는 필요 충분일 필요는 없고 G 내에 있는 d-separation이 P 내에 있는 independence를 만족하기만 하면 된다.

I-map의 예를 보자.

G1은 P1의 I-map 이기는 하나 P2의 I-map은 아니다. P2의 두 변수 I와 D는 dependent 하기 때문에 G1내에 있는 d-separation을 만족시키지 않기 때문이다. 그러나 G2는 그래프 내의 d-separation이 없기 때문에 공집합에 해당하며 이는 P1과 P2에서 모두 만족하기 때문에 G2는 P1과 P2의 I-map에 해당한다.

P가 G에 관해서 factorization이 된다면 G는 P의 I-map에 해당한다. 곧 이 말은 그래프 G로 부터 parameter에 상관없이 P의 independence를 확인할 수 있다는 것이다.

위 정리의 역도 성립한다.

그래프 G가 P의 I-map이라면 P 는 G에 대하여 factorization 이 된다. 이게 무슨 말인가 하면 만약에 확률 분포 P의 independence 가 그래프 G에 나타나 있는 d-separation를 만족시킨다면 we can pick that distribution and represent as bayesian network over that graph.
위의 첫 식은 bayesian network의 chain rule이 아닌 단순히 chain rule for probability. 이제 위의 첫 식에서 그래프에 표현되어 있는 independence를 이용하면 두번째 식이 된다(예를 들어 D와 I는 서로 independent 하기 때문에 P(I|D)는 P(I)랑 같은 것이 되고 P(S|D,I,G)는 S의 parent 인 I노드가 conditioning 이 된다면 S의 non-descendant의 노드들 그러니까 D랑 G와 independent 하게 되므로 P(S|D,I,G)는 P(S|I)가 되게 된다). 두번째 식이 바로 P factorization over G.

정리하자면

Naive Bayes
indepence assumption이 굉장히 단순하거나 혹은 naive 하기 때문에 naive bayes model 이라 한다.

x1,x2등은 observation에 해당하고 우리는 이 observation을 통해  class를 추론하는 것. 위 bayesian network 그래프를 통해 C가 conditioning 되어 있다면 observation 노드들은 서로 independent 하다는 것을 알 수 있다. joint probability를 bayesian network의 정보와 chain rule로 표현한 것이 위그림의 식.

이 모델을 좀더 이해하기 위해 ratio를 보자(여기서 joint probability가 아니라 posterior probability 의 ratio인데 오른쪽 식이 joint probability의 식과 동일하다. 그 이유는 P(x1,x2.x3...가 분모 분자가 동일하기 때문에 상쇄된 것)).

posterior probability ratio 는 prior probability ration와 odd ratios 의 곱으로 표현이 가능해 진다.

이 naive bayes model 의 적용을 text classification예로 봐보자. 두 naive bayes model 중에 먼저 Bernoulli naive bayes model을 보자.

여기서 observation node는 갯수는 사전안에 들어 있는 모든 단어의 수가 되겠다. 문서에 특정 단어가 나왔으면 1 값을 나오지 않았으면 0 값을 할당한다(Bernoulli random variable).

두번째 model은 multinomial Naive Bayes model

여기서 observation node의 갯수는 bernoulli 와는 달리 사전에 있는 모든 단어가 아니고 문서에 있는 단어 갯수가 되겠다(주의할 것은 unique 단어 갯수가 아니라 정말 단순 단어 갯수를 의미한다는 것, 왜냐면 w1 노드는 문서내 첫번째 단어의 실제 단어를 값으로 갖는 random variable이 되겠다). 각 observation node의 확률은 해당 위치에서 특정 단어가 나올 확률을 의미하며 이는 multinomial distribution으로 각 위치에서의 모든 확률의 합이 1이 됨을 의미한다.

정리하자면

Application : Diagnosis
bayesian network의 the most common application은 diagnosis이다.

예로 pathfinder를 든다. 이는 헤커만이라는 사람이 박사 학위로 무슨 상을 받았다. Pathfinder look at  a range of difference pieace of evidence in order to help a doctor diagnose a set of diseases.

첫번째 버젼은 bayesian network를 사용하기 전 버젼으로 별로 performance가 좋지 않았다. 두번째 버젼은 모든 observation random variable independent 하다는 가정의 naive bayes를 사용했다.

세번째 버젼 역시 naive bayes를 사용. 그렇기 때문에 절대로 0 probability를 사용할 수 없었다(하나라도 0 값을 갖으면 전체 확률 곱이 0이 되기 때문에). 그러나 knowledge engineering을 통해서 performance를 높였다.

이 버젼은 BN을 디자인한 사람보다도 diagnosis를 잘한다.


CPCS mpdel : 대략 500개의 random variable이 평균 4개 정도의 value를 갖는 model.

Knowledge Engineering Example

실제 network를 보고 CPD는 어떻게 생겼는지 우리는 거기서 어떤 behavior를 얻고 추가적인 사항들을 어떻게 network에 늘려가는지 보자.

UCLA에서 만든 SamIam 이라는 tool을 이용해서 보험 지급금에 관한 문제에 대한 예를 든다