Overview

방향성을 가지지 않는 확률적 그래프 모형이다.

Undirected Graphical Model

Undirected Graphical Model(a.k.a. Markov Random Field)은 방향이 없는 그래프를 이용하여 확률변수 간의 대칭적인 의존관계를 표현하는 확률적 그래프 모형이다.

• 그래프 표현

  $X-Y$

  이는 $X$와 $Y$가 관계가 있지만, 인과관계는 알 수 없다.

• Factorization

  $\displaystyle P(X) = \frac 1 Z \prod_{C \in c'} \psi_C(X_C)$

  • $C$: clique
  • $\psi_C(X_C)$: potential function(잠재 함수)
  • $Z$: partition function(분배 함수)
    • partition function
  • $c'$: 그래프의 clique 집합

• Local Markov Property: 자신의 이웃을 제외한 나머지 노드와 조건부 독립인 성질

  $X_i \perp X_{\text{non-neighbors}} | X_{\text{neighbors}}$

  • 예시

Conditional Random Field

Conditional Random Field(CRF)는 관측된 입력 $X$가 주어졌을 때 출력 $Y$의 전체 구조를 조건부 확률 $P(Y|X)$로 모델링하는 모형이다. 주로 자연어 처리의 품사 태깅, 개체명 인식, sequence labeling에 사용된다.

$X = (X_1, …, X_n), Y = (Y_1, …, Y_n)$라고 할 때,

다른 모델이 $P(Y_i | X_i)$를 각각 계산하여 모델링한다면, CRF는 $P(Y_1, …, Y_n | X_1, …, X_n)$을 직접 모델링한다.

즉, 출력 변수 $Y$ 사이의 관계도 함께 모델링한다.

• 예제: PoS Tagging

• 수학적 표현

  Gibbs Distribution 형태 사용하여 다음과 같이 정리한다.

  $\displaystyle P(Y|X) = \frac 1 {Z(X)} \exp \bigg( \sum_k \lambda_k f_k (X, Y) \bigg)$

  • $f_k(Y, X)$: Feature Function
  • $\lambda_k$: Feature Weight
  • $Z(X)$: Conditional Partition Function

• Feature Function

  입력의 특징과 라벨 간 관계를 feature로 표현하여 조건이 만족되는지를 함수로 나타낼 수 있다.

  • $I$는 주로 indicator function을 사용한다. (아닌 경우도 있다.)

  1. 입력

     $f(Y, X) = I(Y_i = \text{PRON}, X_i = \text{나는})$

     라고 하면, 단어가 "나는"이고 해당 라벨이 PRON인가?를 나타낸다.

  2. 라벨 간 관계

     $f(Y, X) = I(Y_{i-1} = \text{PRON}, Y_i = \text{NOUN})$

     라고 한다면, 이전 라벨이 PRON이고 현재 라벨이 NOUN인가?를 나타낸다.

• Conditional Partition Function

  모든 가능한 label sequence의 확률을 합쳐서 1이 되도록 만드는 정규화 상수이다.

  $\begin{aligned} Z(X) &= \sum_{Y'} \exp \bigg( \sum_k \lambda_k f_k (X, Y') \bigg) \\ &= \sum_{Y'} \exp (Score(X, Y')) \end{aligned}$

  $\displaystyle \therefore P(Y|X) = \frac {\exp (\text{score}(X, Y))} {\sum_{Y'}\exp (\text{score}(X, Y'))}$