Structured Probabilistic Model

다변수 확률 분포의 복잡성

• 기계 학습 알고리즘을 확률 분포로 생각해보자.
• 굉장히 많은 확률 변수가 관여함에도, 비교적 적은 수의 변수들만 서로간의 직접적인 상호작용을 갖는다.
  • 즉, 대부분은 독립적인 확률변수이고, 몇몇만 종속적이다.
• 이러한 특이성을 가짐에도 확률분포를 하나의 함수로 나타내는 것은 매우 비효율적이다.
• 예를 들어, 확률 변수 a, b, c가 있다하자.
  • a → b: B는 A에 종속
  • b → c: C는 B에 종속
  • a, b는 독립
  • b, c는 독립
• 위와 같은 상황에서 $p(a,b,c)$는 다음과 같이 표현된다.
  • Chain Rule과 독립 사건의 원리를 사용하면 된다.

$$p(a,b,c)=p(a)\cdot p(b|a)\cdot p(c|a,b)=p(a)\cdot p(b|a)\cdot p(c|b)$$

• 위와 같이 다변수 분포를 인수분해할 경우, Parameter의 개수를 줄일 수 있다.
  • 확률 변수의 개수가 줄어들면, 해당 확률 변수를 사용하는 분포의 Parameter를 적게 쓸 수 있다.
  • $p(a,b)$에서 사용하는 Parameter보다 $p(a)$를 서술할 때 필요한 Parameter가 당연히 적게 필요하다.
• 각 인수가 사용하는 Parameter들의 개수는 그 인수에 있는 변수 개수의 곱에 비례한다. 

Parameter개수가 급증하는 이유

$$p(a,b,c)=p(a)\cdot p(b|a)\cdot p(c|b)$$

• $p(a)$
  • 변수 $a$ 에 대한 확률.
  • 예를 들어, a 가 이산형 변수로 $k$ 개의 상태를 가질 수 있다면, 이 확률을 정의하기 위해 $k-1$ 개의 매개변수가 필요합니다.
  • 혹은 연속형 변수라고 하더라도, 어떤 분포를 쓰냐에 따라 파라미터의 개수는 달라질 수 있다.
• $p(b|a)$
  • 이는 $a$ 의 상태에 따라 $b$의 확률이 달라지는 조건부 확률이다.
  • 만약 $a$ 가 $k$ 개의 상태를 가질 수 있고,
  • $b$ 가 $l$ 개의 상태를 가질 수 있다면, $p(b|a)$ 는 각 $a$ 의 상태에 대해 $b$ 의 확률을 정의해야 한다.
  • 따라서 이 경우 필요한 매개변수의 수는 $k\times (l-1)$ 다.
  • 각 상태에 대해 l-1 개의 매개변수를 가지니까, 모든 상태에서 거듭 제곱처럼 증가합니다.
• $p(c|b)$
  • 마찬가지로 $b$의 상태에 따라 $c$의 확률이 달라진다.
  • $b$ 가 $l$ 개의 상태를, $c$ 가 $m$ 개의 상태를 가질 수 있다면, 이 조건부 확률을 표현하려면 $l\times (m-1)$ 개의 매개변수가 필요하다.

구조적 확률 모형

• 이런 인수분해를 Graph로 표현할 수 있다.
• 각 확률 변수를 노드로, 확률 변수간의 상호작용을 간선으로 표현한다.

유향 그래프

• 위의 연쇄 법칙을 통해 다변수 확률 분포를 쪼갰던 것을 생각해보자.
• 특정 확률 변수는, 해당 값이 있기 위한 다른 확률 변수의 조건부 확률이다.
• 다른 말로 하면 $X_i$ 확률 변수에 대한 분포는, 본인에게 영향을 주는, 부모 확률 변수에 대한 조건부 확률로 계산된다.
• $X_i$에 영향을 주는 부모 확률 변수를 $Pa(X_i)$라고 하자.
• 그렇다고 했을 때, 특정 분포는 아래와 같이 표현된다.

$$p(x)=p(x_1,x_2,\cdots ,x_n)=\prod \_{i=1}^{n}p(x_i|Pa(X_i))$$

• 어떻게 보면 연쇄법칙의 표현이라고 생각할 수도 있겠다.
• 그럼 간단한 예시를 보자.
• 확률 변수 $a,b,c,d,e$가 있다고 하자.
• $p(x)$를 연쇄법칙을 써서 쪼개려고 하면, 각 변수들 사이의 관계를 알아야 한다.
• 어찌저찌 쪼갠 결과가 아래라고 하자.

$$p(x)=p(a,b,c,d,e)=p(a)\cdot p(b|a)\cdot p(c|a,b)\cdot p(d|b)\cdot p(e|c)$$

• 이를 그래프의 표현으로 바꾼다면 어떻게 될까?

• 굉장히 직관적이다.
• $a$와 $c$ 는 직접 상호작용하지만, $a$와 $e$는 $c$를 거쳐 간접적으로 상호작용한다.

무향 그래프

• 유향 그래프에서 상호작용은 조건부 확률 분포로 해석되었다.
• 즉, 한 변수의 값이 다른 변수에 의존하여 결정될 때, 조건부 확률 분포로 이 관계를 설명했다.
• 그렇다면 확률 변수 사이에는 해당 관계만 있는 것인가?
• 아니다. 대칭적이고 상호 의존적일수도 있다. 또 단순 함수 관계로 얽혀있을 수도 있다.
• 예를 들어, $X=2Y$와 같은 관계도 가능하고, 쌍방의존 관계도 가능하다.
• 이러한 관계를 표현하기 위해 무향 그래프에서는 그냥 함수로 표현하는 경우가 많다.
• 자, 그럼 특정 예시를 두고 무향 그래프에서의 확률 분포를 계산해보자.

• 위의 그래프에서 $p(x)$를 계산해보자.
• 여기서 파벌(Clique)라는 개념을 사용하면 계산이 매우 유용하다.
• $C_1=(a,b,c),C_2=(b,d),C_3=(c,e)$를 파벌로 묶어보자.
• 이 각각의 Clique에는 얽히는 확률 변수간의 함수와 연관된다. (${\varphi }^i(C^i$)
• 이 관계를 통해, 각 확률 변수끼리의 곱과 같은 방식으로 $p(x)$를 계산하지 않고, Clique를 통해 $p(x)$를 계산할 수 있다.
• 하지만 Clique끼리 계산한다고 했을 때, 문제가 있다.
• 이건 앞서 말한 유향 그래프에서와 같이 관계가 조건부 확률로 정의되지 않았기 때문에, 최종 $p(x)$의 치역의 범위를 맞춰주기 위해 정규화가 필요하다.
  • $p(x)$의 치역은 \[0, 1\]이다. (확률이니까)
• 이 모든 내용을 정리하면 아래와 같다.

$$p(x)=\frac{1}{Z}\prod \_i{\varphi }^i(C^i)$$ $$p(a,b,c,d,e)=\frac{1}{Z}{\varphi }^1(a,b,c)\cdot {\varphi }^2(b,d)\cdot {\varphi }^3(c,e)$$

그래프 표현의 이점

• 그래프 표현은 확률 변수를 표현하는 하나의 방법이다.
• 확실히 직관적으로 이해하기 쉽다.