cryptography unit1-1

cryptography 라는 단어의 뜻은 아래와 같다.

symmetric crytosystems

symmetric cryptosystems  에서 symmetric의 사용은 encryption이랑 decryption에서 사용하는 key가 같을때를 의미한다. m은 메시지의 전체 집합 M에서의 부분집합 혹은 원소. 엘리스가 메시지 m을 암호화해서 insecure channel로 흘려 보낼거고 Bob이 이 암호화된 ciphertext를 받아서 decryption 시켜서 plain text로 만들것. E와 D는 역함수 관계. 이 cryptosystem에서 가장 중요한 key이다. encryption algorithm이나 decryption algorithm이 노출 된다고 하더라고 key를 비밀로 한다면 이는 유지가 된다(cipher must not depend on secrecy mechanism it must not matter if it fall into the hands of enemy).

Encryption function은 message m과 key k를 받아서 cipher를 만들고 Decryption function은 cipher c와 key k를 받아서 message m을 다시 만든다. correctness property란 모든 m과 k에 대해 E와 D가 역함수 관계인것.

perfect cipher인 one-time pad 에 대해 알아본다.

여기서 perfect 라는 뜻은 key랑 message를 전혀 노출하지 않는다는 것. 그러나 이 cipher의 문제점은 impractical 하다는 것. 이를 이해하기 위해 XOR("exclusive or" 혹은 위 그림의 오른쪽 끝 기호로 표시) 를 이해하여야 한다. A XOR B 이면 A와 B가 같은 값이면 A XOR B 값은 0이 되고 A 와 B가 서로 다르면 A XOR B는 1이 된다.

XOR은 결합법칙이 성립한다.  곧 X xor Y xor X = X xor X xor Y와 같게 되고 이는 0 xor Y가 되므로 y 값과 동일하게 된다. 여기서 X를 key K로 생각하면 이것이 바로 one-time pad. key가 딱 한번만 사용되기 때문에 one-time pad 라 한다.

예를 들어보면

CS라는 문자열을 message 화 한다. 여기서 message 는 0 혹은 1 인 bits 가 되고 key 역시 마찬가지. C와 S를 python의 ord 함수를 이용해서 10진수화 하고 이를 2진수로 바꾸면 위와같은 숫자의 나열로 되고 key인 k는 random하게 0과1을 생성한다. 그래서 xor 을 이용해서 cipher인 c를 생성.

perfect cipher의 정의를 알아본다.

perfect cipher의 정의는 attacker, 그러니까 insecure line에서 cipher를 훔친 사람에게 그 어떠한 추가적인 정보도 제공하지 않는 cipher를 의미한다. 이를 수식화 하면 아래와 같다. 그림과 같다.

one-time pad가 perfect cipher 라는 것을 증명하는 과정이다. 

perfect cipher를 수식화 하면 위의 조건부 확률과 같게 된다. c를 알고 있다는 조건부 확률이 원래의 확률 P(m=m*) 와 같은 것이 바로 perfect cipher의 조건. one time pad가 위 식을 만족함을 보임으로 perfect cipher가 됨을 증명하는 것이다. 위 퀴즈에서 보듯이 one time pad인 encrypt mechanism을 가지고 message m과 ciphertext c 가 주어졌을 때 m이 c가 되게 하는 key k는 하나밖에 없게 된다. 길이가 1bit인 예와 2bit인 예에서 보듯이 한 m에서 한 k로의 edge, 즉 key는 하나밖에 없음을 보인다. 이 사실을 근거로 조건부 확률의 분모 P(B)를 구하게 되는데 one time pad에서는 P(B) 는 P(Ek(m)=c) 이다. P(Ek(m)=c)는 설명하자면 ciphertext 인 c가 나올 확률을 의미한다. 즉 모든 k와 모든 m가 encrypt mechanism에 의해 c가 될 확률들의 합을 전체 경우의 수 |M|*|K| 로 나누어 준 값이 되겠다. 여기서 모든 k에 대한 시그마, 곧 합은 1 이 되고 시그마m, 모든 m에 대한 합은 |M|이 되서 결국 P(Ek(m)=c) = 1/|K| 이다(이해가 잘 되지 않는다면 1bit 예제를 생각해보자. c가 1이 나올 확률은 모든 m, 곧 0과 1이 모든 key, 즉 0과 1에 의해서 1이 되는 확률은 1/2, 즉 1/|K|가 됨을 볼수 있다). 

위 conditional probability의 분자를 구해보자.

모든 message가 uniformly distribute 되어 있다고 가정하면 두번째 역시 정답이다. 하지만 일반적으로 message는 uniform distribution이 아니다(message가 영어라고 가정하면 특정 알파벳의 조합,즉 단어가 좀더 많은 분포를 차지하는 것을 알 수 있다). 오른쪽 그림과 같이 matrix를 만드는데 y 축은 M이 되겠고 x 축은 K가 되겠다. m=m* 교집합 Ek(m)=c 은 그림에서 빨간색 선과 카키색 선의 교차점이 되겠다(Eki(mi)=c 가 사실 꼭 y=-x 그래프가 되는 것은 아니지만 그렇게 되게끔 matrix를 구성했다고 가정한다). 곧 m*가 특정 m일 확률에 k*가 특정 k가 될 확률의 곱으로 표현된다. m*가 특정 m일 확률은 message가 uniform distribution이 아닌 관계로 P(m=m*)가 되겠고 key의 분포는 uniform distribution이기에 1/|K|이 되므로 이 두 확률의 곱으로 m=m* 교집합 Ek(m)=c 의 확률이 표현된다.

결론적으로 one-time pad 일때 perfect cipher의 조건부 확률 수식의  분자는 P(m=m*)*1/|K| 가 되겠고 분모는 1/|K| 가 됨으로 결국 P(m=m*) 가 되므로 perfect cipher의 조건부 확률을 만족하게 됨으로 one-time pad 는 perfect cipher가 된다.

그러나 one-time pad에는 심각한 문제가 있다.

한가지가 malleable. active attacker(ciphertext를 modify 하는 사람)가 비록 ciphertext로 부터 어떠한 정보를 얻지는 못하지만 ciphertext를 변형시켜서 Bob이 잘못된 message를 받도록 한다는 것이다. 그리고 또 다른 한가지는 impractical. key의 갯수가 message 만큼 있어야 한다는 것. 

sharmon's theorem : cipher가 완벽하다면 이는 반드시 impractical 하다.

이를 증명하기 위해서 귀류법을 사용. 즉 결론을 부정하여 모순이 되는지를 확인한다. 여기서 결론은 impractical, 즉 |K|가 |M| 보다 크거나 같다라는 결론은 부정한 가정을 이용. |K| < |M|인 perfect encryption 인 E가 있다고 가정한다. cypertext c를 얻게 되면 이를 decryption function을 이용해서 그 모든 key에 대한 합집합인 message Mo를 찾는다. 그런데 합집합인 관계로 decryption해서 나온 |Mo|이 |K| 보다 작거나 같게 된다(물론 one-time pad 일 경우에는 같게 되겠지만). 그리고 이미 가정에서 |K| < |M|이 였기 때문에 |Mo| < |M|이 되고 그 말은 특정 M에 속하는 특정 message는 Mo에 속하지 안을 수 있다는 것. 이때 특정 message의 P(m=m*|Ek(m)=c) = 0이 될것이고 P(m=m*) > 0 이 될 것이므로 이는 perfect cipher의 요건을 만족시키지 않으므로 가정했던 명제는 false가 되고 원래의 명제가 증명이 되는 것.

PGM 3 Template models

Overview

여기서 일반적인 모델인 template model에 대해 알아본다.
예를 드는 것이 예전에 introduction에서 들었던 blood type에 관한 예를 든다.

위 pedigree의 특정 trait(여기서는 blood type)에 관한 bayesian network는 아래와 같이 나타낼 수 있다.

G는 genotype을 의미하고 B는 blood type을 의미한다. 표현형인 B는 오직 genotype에 의해 결정되기 때문에 위와 같은 bayesian network로 표현이 가능하다.
그리고 pedigree가 달라지면 위의 bayesian network도 달라지게 되지만 뭔가 공통되는 model이 존재함을 알 수 있다(sharing between models(서로 다른 pedigree 사이에 존재하는 공통 모델), sharing within models(한 pedigree 안에 존재하는 공통 모델)). 예를 들어 salma의 genotype이  selma의 blood type에 영향을 주듯이 각 개체의 genotype이 blood type에 영향을 주는 모델이라던지, 자식의  genotype은 부모의 genotype에 영향을 받는 모델이 그 예이다.
we like to have some way of constructing model that have this large amount of shared structure that allows us to both construct very large ...   sparse parameterization and also construct the entire families of model from single concise representation.

또 다른 예로 named entity recognition을 위한 (NLP)natural language processing sequence models를 보자.

또다른 예가 아래 그림

결론적으로 

classic model 는 template variable의 instantiation 혹은 duplication으로 나타내어진다. template variable은 위에서 보듯이 시간이나 사람등의 index를 인자로 받아서 나오는 함수 같은 것이다. 

template model은 ground variable,곧 index 변수가 어떻게 template 로 부터 dependency model을 물려받는지(그러니까 index가 어떻게 template variable이 되는지)를 명시한 모델이다. 하나의 concise model로 축약된 모델. 전체 네트워크가 이러한 template variable의 복제로 나타내어 질수 있다. 이러한 모델은 여러 가지 적용, dynamic bayesian network, object-related model 등에 이용된다.

Temporal models

system where evolve over time, 시간에 따라 발전하는 시스템을 표현하기 위한 모델

trajectory (시간 등)에 따른 distribution 을 보자. 이때 먼저 discretize,즉 이산화를 먼저시키는데, 이말은 연속 변수를 작은 단위의 이산 변수로 구분화 한다는 것. 

위의 첫 식은 그냥 chain rule of probability로 어떠한 가정이 없는 일반식이고 두번째 가정 즉 현재 위치에서의 값을 안다고 가정하면 다음 위치의 값은 이전 값들과는 dependency가 없다는 것. 그러면 처음 식은 세번째 식으로 변하게 된다 ((1:t) 가 t로 변함).

그럼 과연 이 가정이 옳은가?  아마도 아닐 것이다. 로봇의 움직임의 예를 들어보자. 현재 위치만 결정되면 다음 시간의 위치에 이전 시간의 값들이 영향을 안준다면 이는 velocity (어느 방향으로 얼마나 빨리 가고 있었나)를 무시하는 것. 곧 markov assumption은 too strong. 이를 보안하는 방법중의 하나는 velocity 라는 변수를 추가하는것. 다른 방법은 adding dependency back in time. 이를 semi-markov model 이라한다.

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을 이용해서 보험 지급금에 관한 문제에 대한 예를 든다