Basic concept for probability(Definition and How to calcultate it)
Random variable, Joint probability distribution, Joint probability, Marginalization
Conditional probability, Bayes rule, Chain rule, Conditionally independent
Bayesian networks
Characteristics
Model parameters
Prediction / Inference
inference by enumberation
by sampling(BN)
by variable elimination
Learning
Bayesian network를 이해를 위한 확률 공부(Basic concept for probability)
확률변수(random variable)
- 확률 변수(random variable)는 우리가 불확실성을 가질 수 있는 세계의 어떤 측면
- 확률 변수는 표본 공간(sample space) S로 정의된 함수(function)이다.
결합 확률(joint probability)
- 사건 A와 또 다른 사건 하나 이상의 확률이 동시에 발생할 확률
- P(A∩B∩... ) or P(A, B,...)
marginalization Out (Summing Out)
- 결합되지 않는 개별 사건의 확률 P(A) 또는 P(B)를 주변 확률(marginal probability)이라 한다.
- 모든 가능한 주변 확률의 경우의 수를 더해서 구한다.
- 사건 X와 사건 Y가 독립일 때
조건부 확률(conditional probability)
- 사건 A가 일어났다는 전제 하에서 사건 B가 일어날 확률
- 사건 X와 사건 Y가 독립일 때, 사건 X가 일어났다는 전제 하에서 사건 Y와 사건 Z가 일어날 확률
베이즈 정리(Bayes`theorem)
- 어떤 사건이 서로 배반하는 원인 둘에 의해 일어난다고 할 때 실제 사건이 일어났을 때 이것이 두 원인 중 하나일 확률을 구하는 정리
- 조건부 확률의 정의를 바탕으로 유도한다.
연쇄 법칙(chain rule)
- 조건부 확률의 정의로 표현된 결합 분포(joint distribution)이다.
베이지안 네트워크(Bayesian Network)
- 베이지안 네트워크(Bayesian Network)는 조건부 확률을 사용하여 복잡한 모델(결합 분포)을 쉽게 표현하기 위해 그래프로 표현하는 방식으로, 서로 간에 관계가 없는 노드는 조건부 독립(conditionally independent)하다.
- 5가지 변수들이 가진 모든 경우의 수는 5가지에 대한 확률 변수의 joint probability, 즉 P(J, M, A, B, E) 총 2^5 = 32가지의 경우의 수를 분석을 해야 한다. 변수의 수가 조금만 많아져도 상당히 큰 경우의 수를 가지게 된다. 그렇기 때문에 이런 큰 경우의 수를 계산하는 것이 비효율적이기 때문에 베이지안 네트워크을 이용해서 관계가 없는 확률 변수들은 조건부 독립이기 때문에 P(J,M,A,B,E) = P(B)*P(E)*P(A|B, E)*P(J|A)*P(M|A)로 서로 관계있는 확률 변수 간에 조건부 확률(Conditional Probability)로 관계만 따지면 나머지는 조건부 독립으로 관계가 없어진다. 확률의 연쇄 법칙(Chain rule of probability)으로 표현하는 것보다 훨씬 간단하게 표현할 수 있다.
베이시안 네트워크 구성(Constructing Bayesian network)
- 각 노드는 상위 노드에 따라 노드 순서의 이전 노드와 조건부로 독립적이다.
- 이 속성이 유지되도록 각 노드에 대해 상위 항목을 선택해야 한다.
- Xi 노드의 부모는 X1에 있는 모든 노드를 포함해야 한다. Xi-1은 Xi-1은 Xi에 직접적인 영향을 미친다.
1. P(J|M) = P(J) (X)
2. P(A|J, M) = P(A|J) (X)
3. P(A|J,M) = P(A) (X)
4. P(B|A, J, M) = P(B|A) (O)
5. P(E|B, A, J, M) = P(E|A) (X)
Bayesian network configuration : cascading
- cascading은 사건들이 순차적으로 발생하는 확률적인 관계를 갖고 있다. cascade 그래프(선형 구조)의 특징은 중간의 사건이 결정이 되면, 중간 이전에 사건과 중간 이후의 사건은 독립적으로 된다. 예를 들면 중간에 있는 C 사건이 발생하든 안 하든 A사건과 B사건은 서로 독립적인 관계이다.
Bayesian network configuration : common parent
- 공통 부모를 가진 그래프(common parent)는 위에 그림을 예로 들면 C 사건이 A와 B 사건에 영향을 끼친다. C 사건이 발생하면 C사건을 제외한 A와 B사건만 확인하면 된다. C 사건이 발생했는지 안 했는지 결정되면 C 사건을 제외를 한다. 그러면 A와 B 사건은 연결이 없는 독립적인 관계가 된다. 즉 부모 노드가 상태가 결정되면, 자식 노드 간의 관계는 독립이 된다.
Bayesian network configuration : common child
- cascading 그래프와 common parent 그래프와 달리 common child에서는 부모 노드들 간에 의존관계가 발생한다. 예를 들면 C가 발생하지 않는 다면 A와 B의 관계는 독립적이게 된다. 하지만 C가 발생을 한다면? C가 발생하는데 A사건과 B사건, 두 사건이 영향을 받을 수 있다. C가 발생한 상황에서 A와 B 사건 둘 다 발생할 수 있고, 또는 둘 중에 한 사건이 발생할 수 있고 또는 두 사건이 발생하지 않을 수 있다. 이처럼 common child 그래프에서는 발생하지 않을 때에는 독립적인 관계지만 사건이 발생하면 의존관계가 생기게 되는 특별한 구조이다.
D-separated
- X 노드에서 Y 노드에 이르는 모든 경로가 차단된 경우 X와 Y는 D로 구분된다.(X, Y는 독립적이다)
1) R 사건과 B사건은 독립인가? (R⊥B)? -> YES
2) T 사건이 발생하면 R 사건과 B 사건은 독립인가? (R⊥B | T)? -> NO
3) V 사건이 발생하면 R 사건과 B 사건은 독립인가? (R⊥B | V)? -> NO
1) T 사건이 발생하면 L 사건과 V 사건은 독립인가? (L⊥V | T)? -> YES
2) L 사건과 B사건은 독립인가? (L⊥B)? -> YES
3) T 사건이 발생하면 L 사건과 B사건은 독립인가? (L⊥B | T)? -> NO
4) V 사건이 발생하면 L 사건과 B사건은 독립인가? (L⊥B | V)? -> NO
5) T 사건과 R사건이 발생하면 L 사건과 B 사건은 독립인가? (L⊥B | T, R) -> NO
마코프 바구니(Markov Blanket)
- 특정한 A 노드가 Markov blanket(parents, childrend, and children`s parents) 관계가 형성될 때 조건부 독립이 된다.
- 보라색 영역을 제외한 노드를 W라고 하고 보라색 영역을 Blanket이라 부르면 다음 같이 쓸 수 있다.
- A⊥W | Blanket
예측 / 추론 방법 (Prediction / Inference)
알람이 울렸지만 도둑과 지진이 아닌, 존과 메리가 전화했을 확률은? - likelihood
- 도둑과 지진이 확률은 독립적인 관계이기 때문에 단순히 P(~B) * P(~E)에서 A는 알람이 울렸지만 B와 E의 영향이 없기 때문에 B와 E가 둘 다 FALSE인 P(A|~B,~E) = 0.01을 곱해준다. 여기까지 계산하면 마지막으로 A는 존과 메리의 전화에 영향을 받았기 때문에 P(J|A)와 P(M|A)는 TRUE인 0,90 * 0.70을 곱해준다.
열거에 의한 추론(inference by enumeration)
변수(variable)
- 물어보는 변수(query variable) : Q
- 관측된 데이터(evidence variables) : E1,... , Ek = e1,... , ek
- 숨겨진 데이터(hidden variables) : H1,... , Hr
계산 방법(how to calculate)
- step1 : 관측된 데이터를 가지고 entries consistent를 선택한다.
- step 2 : H를 합하여 물어보는 것과 관측된 데이터의 결합 확률을 얻는다.
- step3 : 일반화
P(A = 1 | B= 1, E = 1)에 대해 숨겨진 변수(hidden variable)의 조건부 확률은 얼마인가?-prediction
- 해당 결합 분포 테이블이 주어질 때 우리는 P(L)의 테이블(숨겨진 데이터-hidden variable)을 구하고 싶을 때 밑에 그림처럼 P(R, T, L)에 대한 결합 분포 테이블을 만들어 줘야 한다. - 열거에 의한 추론을 할 경우.
- 위에 예시에서 P(L)에서 결합 분포의 합은 1이 되어야 하는데 그림에서 오타가 발생;;
- 숨겨진 변수를 요약하기 전에 전체의 결합 분포(joint distribution)를 결합(join) 하기 때문에 열거에 의한 추론은 너무 느리다.
- 항상 방법(any improvement)? -> 필요 없는 변수를 삭제하면서 추론(inference by variable elimination)
변수 제거에 의한 추론(inference by variable elimination)
- 처음 join을 할 때 필요하지 않은 부분은 최대한 요약(sum out)을 시켜서 join을 시켜주면 열거에 의한 추론보다 속도 면에서 항상 될 수 있다.
샘플링을 이용한 근사치 추론(approximate inference by sampling)
표본 분포 S에서 N 표본을 추출하다
- step 1 : [0, 1) 이상의 균일한 분포에서 표본 u 가져오기(임의 숫자 가져오기)
- step 2 : 이 샘플 u를 지정된 분포에 대한 결과로 변환
- 대략의 후 확률(approximate posterior probability)을 계산한다. 이 수렴을 실제 확률 P로 나타낸다
- 만약 random number 가 x=0.78 이면 sample C는 blue가 된다.
1. 샘플링(sampling)
- step 1 : [0, 1) 이상의 균일한 분포에서 샘플(sample) u 가져오기
- step 2 : 이 샘플 u를 지정된 분포에 대한 결과로 변환
조건부 분포에 대한 샘플링(sampling for conditional distribution)
- step 1 : [0, 1) 이상의 균일한 분포에서 샘플 u 가져오기
- step 2 : 이 샘플 u를 지정된 분포에 대한 결과로 변환
2. 사전 샘플링(prior sampling)
- 확률 변수에 대해 샘플링 값을 순차적으로 넣어준다. 0.31은 먼저 처음 A에 대한 분포에 대해 분석하여 설정을 한다. 0.31은 +a이다. 다음 0.58은 A와 B가 같이 있는 조건부 확률에서 +a의 기준으로 b를 설정한다. 0.58은 +b이다. 이렇게 순차적으로 확률 변수에 대한 변수를 assign 시켜주면 하나의 데이터가 나오는 것이다.
- 해당 데이터를 모은 샘플들을 갖고 질의(queries)를 답할 수 있다. 첫 번째 질의로 P(+d) 확률을 구하면 샘플들의 전체 데이터(10) 중에서 +d가 몇 개인지 확인해보면, 3/10이 나온다.
- 질의에 물어보는 값이 샘플에 없을 경우 구할 수가 없다.
- 질의에서 필요하지 않은 데이터가 존재할 수 있다. -> 기각 샘플링(Rejection Sampling)
3. 기각 샘플링(Rejection Sampling)
- 질의에서 P(-d|-b)의 값을 물어봤지만 prior sampling을 하다 보면 질의와 상관없이 필요하지 않은 데이터가 샘플링된다.. 위에 값에서 0.58은 +b인데, 질의에서 필요한 값은 -b이다. 그렇다면 이 데이터는 질의에 필요한 데이터가 아니기 때문에 반환(reject)을 해주고 다시 샘플링을 시작한다.
- 하지만 기껏해서 만들어 놓은 샘플링들을 기각(reject)을 시키는 것은 비효율적이다. -> likelihood weighting
*likelihood weighting
- 시간을 들이고 만든 샘플링을 기각(reject)을 시키는 것은 너무 비효율적이기 때문에 기각을 시키지 않고 샘플링에 대해 가중치(weight)를 준다.
- w이라는 가중치를 1을 주고 필요한 조건을 곱해서 가중치를 만들어 준다. (ex w = w * 조건 확률)
- 0.31은 a로 샘플링이 된다. 다음 0.58은 b에 대한 거지만 -b는 되었다 가정하고 다음 0.58은 c에 대해서 확인하면 된다. 그 대신 -b, +d는 되었다고 가정하였기 때문에 가중치를 만들어 준다. 가중치 w = w * 0.2(-b) * (0,2)(-b)= 0.04를 갖는다. 이렇게 반복을 하면 샘플에 대해서 기각(reject)을 시킬 필요가 없어진다.
- 위 예시 표도 오타가 있다...! 발견했다면 당신은 이해한거다.
- likelihood weight에서 가중치를 주고, 샘플링에 대해 기각(reject)을 안 시켜줬다.
4. 깁스 샘플링(Gibbs sampling)
- step1 : 질의에 조건 확률을 고정(fix) 시켜준다.
- step 2 : 다른 변수를 무작위로 assign을 시켜준다.(변수에 대해 assign을 다 시켜주면 하나의 데이터(샘플링이 나온다.)
- step3 : non-evidence 변수 X를 골라서 다른 변수에 대해서 변수 X를 sampling을 시켜준다.(fix)
베이지안 네트워크 학습(bayesian network learning)
- 베이지안 네트워크에서는 주어진 데이트가 조건부 확률 테이블(conditional probability table)이기 때문에 학습을 해야 하는 모델 변수(model parameter)는 조건부 확률 테이블이다.
- 그래프를 알 수 있고 데이터가 완전히 관찰될 경우 - 변수 학습
- 그래프를 알 수 있고, 특정한 데이터만 관찰될 경우 - EM (숨겨진 변수 학습)
빠진 데이터가 있는 베이지안 네트워크 학습 방법 (데이터 H를 빠졌을 경우)
- 만약 빠진 변수가 있을 경우, MLE로 계산할 수 없다.
- X 변수가 관측되고 관측되지 않은 Z가 있을 경우 P(Z|X)를 EM으로 측정할 수 있다.
숨겨진 변수에 대한 베이지안 네트워크 학습하는 방법(Bayesian network learning : hidden variable)
- 관측된 데이터 X(observed variable X) = {A, B}
- 숨겨진 데이터 Z(hidden variable Z) = {H}
