Bayesian Networks and Hidden Markov Models

Bayesian Networks and Hidden Markov Models

세상의 지식은 대개 불완전하거나 불확실하므로, Uncertain information이 주어졌을떄, 합리적으로 행동하는 것이 중요하다. Agents 는 규칙과 사실을 일정 수준의 확률로 확신하고, 이 믿음의 정도? (Degree of belifef) 를 확률, 즉 Probabilites 로 표현한다. 그래서 AI 에서 확률이 중요한 부분인 것.

그리고 이런 확률적인 방법에는 두 가지 접근 법이 있다.

Probabilistic Methods

• Static Environment (without actions) : Bayeisn Networks

• Dynamic Environment (without actions) : Hidden Markov Models

우선 전체적인 확률 이론에 대해 간단하게 짚어보자면…

Probability Theory

Sample Space \(\Omega\)

가능한 모든 결과의 집합이다. 예시로 동전 던지기면 앞면과 뒷면 즉 set = 1

Event Space \(\mathbb{F}\)

\(\Omega\) 의 Powerset 으로, 결과들의 모든 가능한 조합을 포함한다.

Probability Space

다음을 만족하는 함수 \(P\)

• \(P(e_i) \geq 0\) Non-negative$$
• \(P(e_1 \cup e_2 \cup ... ) _ = \sum_i P(e_i). e_i\) 가 Mutually exclusive
• \[sum_{\omega \in \Omega} P(\omega) = 1\]

Random Variable (RV)

Sample space \(\Omega\) 에서 어떤 세트 \(D\) 로의 매핑

\[X : \Omega \rightarrow D\]

Expectation

\[E(x) = \sum_{x \in D_x} x \cdot P(X=x)\]

Join Probability

Event \(X=x\) 와 \(Y=y\) 가 동시에 일어날 확률 \(P\)

\[P((X=x), Y=y)\]

Marginalization

다른 변수들을 합산해서 단일 변수의 확률을 얻는 과정.

\[P(X=x) = \sum_{y \in D_y} P((X=x), (Y=y))\]

Conditional Probability

\(Y=y\) 뒷부분 을 알때 \(X=x\) 앞부분일 확률

\[P((X=x) \lvert (Y=y) ) = \frac{P((X=x), (Y=y))}{P(Y=x)}\]

Bayes Rule

\[P((Y=y) \lvert (X=x)) = \frac{P(X=x \lvert Y=y)P(Y = y)}{\sum_{y \in D_y} P(X=x \lvert Y =y)P(Y=y)}\]

Bayesian Networks (Static Environment)

Bayesian Networks 는 변수 간의 의존 관계를 나타내기 위해 사용되는 Directed Acyclic Graph (DAG)이다. 이는 Episodic environment , Static environment 에서 Actions가 없는 상황을 모델링하는데 특화 되어 있다.

Semantics

각 도느는 Random Variable 에 대응하고, 노드 간의 화살표는 부모 노드로부터 시작된다. 각 노트 \(N_i\) 는 부모 노드에 대한 Conditional Probability Distribution \(P(X_i \lvert Parents(X_i))\) 를 가진다.

전체 결합 확률은 로컬 조건부 확률들의 곱으로 계산된다. 즉, 수식으로 표현하면 체인룰을 사용하고,

\[P(x_1, ..., x_n) = \prod_{i=1}^n P(x_i \lvert parents(X_i))\]

로 표현한다. (Full Joint Distribution)

Compactness

\(n\) 개의 변수가 있고, 각 변수가 최대 \(k\) 개의 부모를 가질때, 전체 결합 확률분포는 \(O(2^n)\) 의 공간이 필요하다. 그러나 Bayesian Network 는 \(O(n \cdot 2^k)\) 의 공간만 피요해서 매우 효율적이다.

Independence 결정 방법 - Moral Graph

두 변수 집합 X, Y 가 증거 Z가 주어졌을때 Conditionally Independent한지 판단하기 위해 다음 단계를 거친다.

Moral Graph

1. Ancestral Subgraph : X, Y, Z와 그 조상 노드들만 남긴 부분 ㄴ그래프를 생성한다.
2. Moral Graph : 같은 자식 노드를 공유하는 부모 노드들 사이에 링크를 추가한다.
3. Undirected GRaph : 모든 방향성 화살표를 무방향 링크로 바꾼다.
4. Path Blocking : X와 Y 사이의 모든 경로가 Z에 의해 차단(Blocked) 되면 조건부독립니다.