이번 장은 "사실 지금까지 배웠던 모든 확률적 추론들은 전부 그저 product rule과 sum rule의 활용일 뿐이었다"는 드립으로 포문을 연다. 사실 맞는 말이기는 하고, 이러한 측면에서 확률적 추론들은 도식화가 가능하며, 이러한 도식화는 확률적 추론에 대한 체계적인 분석을 더욱 용이하게 해 준다. 이렇게 도식화된 확률 분포들을 probabilistic graphical models라 부른다.
고등학교 때 다들 간단한 형태의 그래프에 대해서는 배웠을 것 같다. 상기해보자면 그래프의 동그란 부분들을 vertex 혹은 node라 부르며, 그 동그란 부분들의 관계를 표현해 주는 선들을 edge, link 혹은 arc라 부른다. 이러한 edge 들이 방향을 가지고 있으면 해당 그래프를 directed graph라 부르고, 방향을 가지고 있지 않으면 undirected graph라 부르는데, 특히 directed graph는 인과 관계를 표현하는 데 적합하다.
8.1. Bayesian Networks
Graphical model을 사용하면 continuous variable 혹은 discrete variable을 구분하지 않고 광범위한 형태의 probability distribution에 대한 probabilistic statements를 표현해낼 수 있다. 먼저 graphical model의 기본적인 요소들을 짚어 본다. 이번 섹션에서는 directed graph를 상정한다.
두 nodes가 연결되어 있을 때, edge가 가리키는 node를 child node, edge를 뽑아내는(?) node를 parent node라 부른다. 그리고 이러한 parent-child 관계를 conditional distribution의 표현으로 생각할 수 있다. 예컨대 node a 로부터 node b 를 연결하는 edge가 있는 그래프는 를 나타낸다.
또 이런 식으로 모든 node pair에 link가 존재하는 그래프를 fully connected라 한다. 이 때 fully connected directed graph는 node들에 순서를 매겨서, 각각의 node가 자신보다 순서가 높은 모든 node로 연결되는 edge를 가지는 그래프로 생각할 수 있다.
또 여기서 상정하는 directed graph는 어떤 node에서 출발하여 해당 node로 회귀하는 closed path가 존재하지 않는 directed acyclic graph이다.
8.1.1 Example: Polynomial regression
다양한 형태의 probabilistic statements들을 그래프로 표현해본다. 여기서 편의를 위해 plate(set of variables), solid circle(deterministic variable), shaded circle(observed variable) 등의 표현을 소개한다.
8.1.2 Generative models
이번 섹션에서는 ancestral sampling이라는, directed graphical model과 상당히 밀접한 관계를 가지는 sampling method를 소개한다.
Ancestral sampling이라 함은 간단히 말해 directed graphical model로 표현된 probabilistic distribution의 sampling을 위해 위에서 언급한 node의 순서에 따라 sampling을 하는 것이다. 즉 (directed) edge가 conditional relationship을 의미하고, 이에 따라 node의 순서가 dependency를 의미하기 때문에(i.e. 어떤 node는 그보다 낮은 순서의 node들에 dependent 혹은 conditional하다), 순서가 가장 낮은 node부터 표집함으로써 dependency를 해소하며 완전한 distribution에서의 표집이 가능한 것이다. 특정 variable set에 대한 marginal distribution의 sampling이 필요하다면 단순히 나머지 표집된 variable들을 무시하면 그만이다.
통상적으로 graphical model에서 우리가 원하는 결과는 순서가 높은 node들의 값이고, 이러한 측면에서 directed graphical model은 우리가 원하는 결과의 causal process를 modeling한 것이라고 볼 수 있겠다. 이러한 측면에서 이러한 graphical model을 generative model이라고 부르기도 한다고 한다.
8.1.3. Discrete variables
우리가 앞서 배웠던 exponential family의 distribution들은 간단하지만(?) 다른 임의의 복잡한 probability distribution을 형성하는 building block으로서 아주 강력한 역할을 할 수 있다. 그런데 graphical model은 이러한 building process를 도식화하는 데 아주 유용하다고 한다.
특히 directed edge로 연결된 두 node가 conjugacy를 가질 때 형성된 probability distribution은 아주 nice한 특성을 가진다고 하는데, 이러한 측면에서 이번 섹션과 다음 섹션에서는 parent-child nodes가 discrete variable일 때와 Gaussian (continuous) variable일 때에 대해 다룬다.
매우 길고 복잡하게 설명을 해 놓았지만, 간단히 말하자면 graph의 edge의 수를 조절함으로써 graphical model의 model complexity (혹은 parameter의 수)를 조절할 수 있다는 것이다. 예컨대 개의 개의 states를 가지는 discrete variables가 있다고 상정할 때, fully connected graph는 개의 parameter를 가지지만, fully disconnected graph는 개의 parameter를 가진다.
또 다른 model complexity를 조절하는 방법으로는 parameter sharing과 conditional distribution을 parameterized model로써 표현하는 방법 등이 있다고 한다.
8.1.4. Linear-Gaussian models
Multivariate Gaussian 역시 이러한 directed graph로써 표현될 수 있다.
먼저 개의 nodes를 가지는 directed acyclic graph가 있고, 각각의 node가 parent nodes states의 linear combination을 mean으로 가지는 Gaussian variable이라고 하자. 그러면 graph의 log of joint probability를 살펴봄으로써 이러한 graph가 multivariate Gaussian을 표현한다는 것을 알 수 있다.
여기서 각 node의 mean과 variance는 ancestral sampling 때와 마찬가지로 order가 낮은 node부터 recursive하게 구할 수 있다.
이제 위의 섹션과 아주 마찬가지로 edge의 수를 조절함으로써 multivariate Gaussian distribution의 complexity를 조절할 수 있다. 예컨대 fully connected graph의 경우 covariance matrix가 꽉 차 있는 형태의 multivariate Gaussian일 것이고, fully disconnected graph의 경우 diagonal covariance matrix를 가지는 multivariate Gaussian일 것이다.
8.2. Conditional Independence
이번 섹션에서는 conditional independence의 개념을 소개하고, graph의 형태로부터 node간의 conditional independence를 판단할 수 있는 d-separation 방법을 설명한다.
먼저 다음과 같은 관계를 만족하면 와 가 에 대해 conditionally independent 하다고 말하며,
다음과 같이 쓴다.
8.2.1 Three example graphs
먼저 d-separation의 재료가 되는 세 가지 형태의 graph를 소개한다.
첫 번째는 tail-to-tail graph이다. 와 를 잇는 가 각 edge의 tail들로 연결되어 있는 형태이며, 가 관측되지 않은 상태일 때는 path가 unblock 되어 있어 와 가 conditionally dependent 하지만, 가 관측된 상태일 때는 path가 block되어 conditionally independent하다.
두 번째는 head-to-tail graph이다. 와 를 잇는 가 각 edge의 head과 tail로 연결되어 있는 형태이며, 마찬가지로 가 관측되지 않은 상태일 때는 path가 unblock 되어 있어 와 가 conditionally dependent 하지만, 가 관측된 상태일 때는 path가 block되어 conditionally independent하다.
마지막은 head-to-head graph이다. 와 를 잇는 가 각 edge의 head들로 연결되어 있는 형태이며, 위의 두 경우와는 반대로 가 관측되지 않은 상태일 때는 path가 block 되어 있어 와 가 conditionally independent 하지만, 가 관측된 상태일 때는 path가 unblock되어 conditionally dependent하다. 또한 이 경우에는 뿐만 아니라, 의 descendant 중 하나라도 관측될 경우 path가 unblock된다.
8.2.2 D-separation
이제 variable set 가 주어졌을 때, conditional independence 가 성립함을 알 수 있는 d-separation의 조건은 다음과 같다.
•
와 를 연결하는 path의 arrow가 head-to-tail 혹은 tail-to-tail 형태로 node에서 만나고, 이 node가 set 에 속하거나,
•
와 를 연결하는 path의 arrow가 head-to-head 형태로 node에서 만나고, 이 node가 set 에 속하고,
•
모든 path가 block되어 있다.
즉 위의 조건이 성립할 때 와 가 에 대해 d-separate 되었다고 말하며, 이 때 가 성립한다.
8.3. Markov Random Fields
위에서는 directed graphical model을 통한 joint distribution의 factorization을 살펴보았는데, 이번에는 자연스럽게 undirected graphical model을 살펴보고, 이를 통한 factorization과 independence relation을 살펴본다.
8.3.1 Conditional independence properties
D-separation에서 살펴보았듯, directed graphical model에서 conditional dependence를 파악하는 일에는 뭔가 복잡한 일이 발생한다. 바로 parent-child 관계의 불균형으로 인해 head-to-head node에서 어쩐지 미묘함이 발생해버리는 것이다. Undirected graphical model은 edge에 화살표가 없는 그래프를 말하며, 이로 인해 이와 같은 parent-child 관계의 불균형이 사라져 conditional dependence를 파악하는 일이 상당히 용이해진다.
즉 이기 위해서는 와 를 잇는 모든 path가 를 통과하면 모든 경로가 block됨으로써 conditional independence가 성립한다. 한편 단 하나라도 block되어있지 않은 경로가 존재하면, 해당 그래프와 상응하지만 conditional independence를 만족하지 않는 적어도 하나의 그래프가 존재하게 된다.
이에 따라 Markov blanket을 파악하는 것도 상당히 쉬워지는데, 어떠한 node가 그래프로부터 격리되기 위한 (혹은 다른 모든 nodes에 대해 conditionally independent하기 위한) 최소한의 node set은 바로 neighbor node들이다. 당연히 이들을 Markov blanket이라 칭한다.
8.3.2 Factorization properties
이제 위의 conditional independence properties에 따른 undirected graph의 factorization rule을 정의한다. 이러한 properties에 따라, 그래프 내의 임의의 두 nodes 가 주어졌을 때, 두 nodes를 직접적으로 연결하는 edge가 존재하지 않으면, 이 두 nodes는 이 두 nodes 이외의 그래프 내의 다른 모든 nodes가 주어졌을 때 (혹은 발견되었을 때) conditionally independent할 것이다. 다음과 같이 표현할 수 있다.
따라서 undirected graph의 factorization rule에서는, 직접적으로 연결되어 있지 않은 임의의 두 nodes는 서로 다른 인수(factor)에 나타나야 한다는 것을 알 수 있다.
이렇게 직접적으로 연결되어 있지 않은 두 nodes를 서로 다른 집합으로 묶어낼 수 있는 개념이 바로 clique이다. 단순히 clique는 모든 nodes가 서로 직접적으로 연결된 nodes들의 집합이며, 그래프 내의 다른 어떤 node를 추가하더라도 clique가 아니게 되는 clique를 maximal clique라고 한다.
Undirected graph의 factor는 직접적으로 연결되어 있는 node들로만 이루어져야만 한다. Clique는 직접적으로 연결된 node들의 집합이다. 이로써 아주 자연스럽게 undirected graph의 factor를 clique로써 표현할 수 있겠다. 즉, undirected graphical model은 해당 그래프의 clique에 대한 function들의 곱으로 factorization될 수 있다.
이 때 clique를 maximal clique라고 상정해도 되는데, 당연히 임의의 clique는 어떠한 maximal clique의 subset일 것이기 때문이다.
이제 undirected graphical model의 joint distribution을 다음과 같이 표현할 수 있다.
이 때 는 각 clique에 대한 potential function이라 부르고, 는 normalization coefficient의 역할을 하며, partition function이라 불린다. 여기서 directed graphical model에서와는 다르게 potential function은 특정한 확률적인 의미를 가지지 않아도 된다. 다만 이에 따라 자연스럽게 normalization되지 않으므로 따로 partition function이 필요해지는 것이다.
이제 이러한 potential function과 conditional independence와의 관계를 알아보고자 한다. 이를 위해서는 먼저 potential function이 strictly positive하다(즉 0보다 크다)고 가정해야 한다. 이러한 가정 하에 Hammersley-Clifford 정리는 graph separation에 따른 conditional independence를 만족하는 모든 distribution의 집합과 clique factorization으로 표현될 수 있는 모든 distribution의 집합이 동치임을 증명했다고 한다.
또한 potential function이 strictly positive하다고 가정하면, 다음과 같이 potential function을 exponential form으로 표현해낼 수 있다.
이 때 를 energy function이라고 부르는데, 이러한 표현이 가지는 의미는 바로 potential function의 곱으로 표현되던 joint distribution이 energy function의 합으로 표현될 수 있다는 것이다.
8.3.3 Illustration: Image de-noising
위에서 정의한 energy function을 극소화(즉 joint probability를 극대화)함으로써 noised image의 noise를 제거하는 알고리즘을 소개한다. Noised image를 , 원래의 이미지를 라고 한다면, 에 관한 undirected graph가 교재의 그림 8.31 처럼 그려질 것이고, 이러한 그래프의 maximal clique들의 energy function을 iteration을 통해 감소시킴으로써 de-noising을 수행한다. 더 이상의 자세한 설명은 생략한다.
8.3.4 Relation to directed graphs
이제 directed graph, undirected graph에 대해 알아보았으니 두 graphical model 사이의 관계에 대해 조금 알아본다.
가장 먼저 directed graph를 undirected graph로 표현해내는 방법을 소개한다. 이를 위해서는 directed graph에서 conditional dependence를 가진 모든 nodes들을 undirected graph의 clique로 묶어주어야 한다. 그래야 directed graph로 표현되는 conditional dependence statement를 만족할 수 있기 때문이다. 따라서 directed graph에서는 연결되어있지 않던 parent nodes들을 연결해주는 과정이 필요하고, 이를 moralization이라 부른다. 또 이러한 moralization 이후의 그래프를 moral graph라 부른다.
당연하게도 fully connected undirected graph는 모든 directed graph에 대한 trivial한 표현이 되지만, 이러한 변환이 아무짝에도 쓸모없다는 것은 분명하다. Moralization은 최소한의 extra edge를 추가한다는 데 의의가 있다.
한편 undirected graph를 directed graph로 바꾸는 작업은 흔치 않으며, normalization constraint로 인해 심심찮은 문제가 발생한다고 한다.
이러한 directed graph와 undirected graph는 서로 표현할 수 있는 distribution의 공간이 다르다. 즉 directed graph로는 표현되지만 undirected graph로는 표현할 수 없는 distribution이 존재하고, 그 반대의 경우도 존재하며, 두 graph로도 모두 표현하지 못하는 distribution 역시 존재한다. 이를 도식화한 그림이 교재의 그림 8.34에 아주 직관적으로 나타나 있다.
8.4. Inference in Graphical Models
Directed graph와 undirected graph 두 형태의 graphical model을 배웠으니, 이제 이러한 graphical model에서의 inference를 위한 알고리즘을 공부해보자. 특히 graphical model의 구조를 이용하여 정확하면서도 효율적인 알고리즘을 다룬다.
8.4.1 Inference on a chain
가장 먼저 chain에서의 inference 문제를 풀어본다. 개의 node를 가진 Chain에서 각각의 변수가 개의 state를 가지는 discrete variable이라고 하면, joint distribution은 다음과 같이 표현될 수 있다.
총 parameter의 수는 당연히 개이다.
이제 여기서 특정 변수에 대한 marginal distribution 을 찾는다고 하자. Observed node는 없다고 가정한다. Marginal distribution은 joint distribution에서 관계 없는 변수들을 모두 marginalization함으로써 구할 수 있으니, 다음과 같이 표현된다.
위의 식에서 단순히 모든 것을 계산한다면 만큼의 연산이 필요하다. 즉 연산 복잡도가 node의 수에 대해 exponential하게 증가한다. 하지만 조금만 생각해보면 conditional independence로 인해 어떠한 summation이 특정한 변수에만 관련된다는 것을 알 수 있다. 예컨대 에 대한 summation은 에만 관련되며, 따라서 summation 은 이 potential에 대해서만 수행된다.
바로 위의 summation의 결과는 에 대한 함수일 것이고, 이와 이 이 등장하는 유일한 factor이기 때문에 다시 은 이에 대해서만 수행되면 된다. 이런 식으로 순서대로 marginalization이 진행되어 불필요한 연산을 줄일 수 있다. 거꾸로 부터 시작해서 처럼 marginalization이 진행되어도 마찬가지이다. 이는 매 연산마다 앞으로는 등장하지 않는 variable을 식에서 제외하기 때문에 그래프에서 변수를 하나씩 제거하는 관점으로 바라볼 수 있다고 한다.
이에 따라 summation을 관련 있는 potential에 대해서만 수행하기 위해 위의 marginalization을 다음과 같이 재배치할 수 있다.
매우 복잡해보이지만 단순히 만을 남겨두고 앞 뒤에서 위에서 말한 대로 변수를 하나씩 제거해버리는 것을 식으로 표현한 것 뿐이다. 매 summation마다 만큼의 연산이 필요하고, 이 걸 번 하니 총 연산 복잡도는 이다.
또 이러한 inference를 message passing의 관점으로 바라보면 다음 섹션부터 나올 알고리즘을 이해하는 데 도움이 되는데, 그냥 conditional dependence를 가진 node들에게 확률에 대한 message를 전달하고, 수합하고(marginalization 하고), 다시 전달하는 과정에 주목하면 되겠다.
마지막으로 모든 variable에 대한 marginal distribution을 구한다고 하자. 저 과정을 단순히 모든 variable에 대해 반복하면 만큼의 연산이 필요하겠지만, forward message passing( 부터 시작하는 저 것)을 끝까지 수행하고, backward message passing을 끝까지 수행하여 그 중간 결과물들을 모두 저장하면 만큼의 연산이 필요하다.
8.4.2 Trees
위와 같이 local message passing을 이용하여 inference를 효율적으로 수행하는 알고리즘을 보다 일반화하여 적용할 수 있는 그래프의 구조가 바로 트리이다. 그게 바로 뒤에서 배울 sum-product 알고리즘인데, 이번 섹션에서는 tree를 짧게 소개한다.
Undirected graph의 경우 tree는 모든 쌍의 node 사이에 단 하나의 path만이 존재하는 그래프로 정의된다. Directed graph의 경우 tree는 root라고 불리는 부모가 없는(...) 단 하나의 node가 존재하고, 다른 모든 node는 하나의 부모를 가지는 그래프로 정의된다. 만약 directed tree graph를 moralization 한다면 부모가 하나밖에 없기 때문에 그 형태가 그대로 유지될 것임을 알 수 있다. 어쨌거나 이렇게 단 하나의 path만이 존재하는 것이 local message passing을 위한 핵심적인 조건이다.
부모가 둘 이상인 node가 존재하지만 여전히 모든 쌍의 node 사이의 path가 단 하나뿐인 그래프를 polytree라 한다.
8.4.3 Factor graphs
sum-product 알고리즘은 위에서 소개한 directed/undirected tree와 polytree에 적용 가능한데, 여기서 factor graph에 대해 배워두면 문제가 더 간단해진다고 한다.
Directed/undirected graph는 그들을 구성하는 여러 subset(혹은 factor)들의 product로 표현될 수 있는데, factor graph는 이러한 factor를 나타내는 node를 추가함으로써 보다 명시적으로 이러한 decomposition(혹은 factorization)을 표현할 수 있게 된다. 예컨대 directed graph에서의 factor는 local conditional distribution을 나타내고, undirected graph에서의 factor는 maximal clique에 대한 potential function을 나타낸다.
Factor graph는 이렇게 각각의 factor에 대한 node를 그래프에 하나씩 추가하고, factor 마다 해당 factor와 dependency가 있는 node들과의 undirected edge를 추가함으로써 형성할 수 있다. Node들 사이의, 그리고 factor들 사이의 edge는 없는데, 이러한 측면에서 일종의 node-factor 사이의 bipartite graph임을 알 수 있다.
동일한 그래프라도 여러 형태의 factor graph가 존재할 수 있는데, 더 자세한 예시들은 교재를 참고하자.
Directed/undirected tree를 factor graph로 변환하면 그 구조는 다시 tree가 된다. 또한 polytree를 factor graph로 변환하면 그 구조는 놀랍게도 다시 tree가 된다.
8.4.4 The sum-product algorithm
이제 위에서 다룬 내용들을 토대로 tree-structured graph 위에서의 효율적인 inference 알고리즘인 sum-product 알고리즘을 배워본다. 먼저 모든 variable은 discrete하다고 가정하며, 이에 따라 marginalization은 summation이 된다. 하지만 단순히 marginalization을 integration으로 변환함으로써 linear-Gaussian 모델에 대해서도 적용이 가능하다고 한다.
sum-product 알고리즘을 적용하기 위해서는, 그래프의 방향성과 관계 없이 모두 같은 framework를 유지하기 위해 먼저 원 그래프를 factor graph로 변환한다. 알고리즘의 목적은 다음과 같이 두 개이다. 위의 chain에서의 inference 알고리즘을 상기하면 이해가 빠르다.
•
marginal distribution을 빠르고 정확하게 찾는다.
•
중복되는 연산들이 효율적으로 공유될 수 있도록 한다.
Marginal은 다음과 같이 찾고자 하는 variable 외의 variable들을 모두 더함으로써 구할 수 있다.
이제 joint distribution 는 다음과 같은 factor들의 product로 표현될 수 있다. 결국에는 이를 위에 대입하여 연산을 이리 저리 재배치하면 되는 것이다!
이제 joint distribution을 다음과 같이 표현할 수 있음을 이해해보자. 는 node 의 neighbor(직접적으로 연결된 factor node)이며, 는 factor node 에 의해 와 연결된 그래프의 subtree 내의 모든 variable node를 나타내며, 는 그룹 내 와 연결된 factor들의 product이다.
여기서 의 neighbor만으로 어떻게 그래프 전체의 joint distribution을 구할 수 있는가? 하는 의문이 들 수 있는데, 위의 정의는 어느 정도 recursive한 측면이 있어서 - 즉 후술하겠지만 어떠한 node는 다른 모든 이웃으로부터 message(확률 정보)를 전달받아야 다른 node로 message를 전달할 수 있기 때문에 - 이웃으로부터 다른 모든 variable에 대한 확률 정보(message)를 전달받을 수 있기 때문이다.
이제 marginal을 다음과 같이 재배치해보자.
여기서 는 다음과 같이 정의된 함수이며, factor node에서 variable node로 전달하는 message라는 의미를 가진다.
여기서 또 는 다시 subtree에 의해 정해지며, 다시 위와 비슷한 방식으로 factorization된다. 는 와 직접적으로 연결된 모든 variable node이다.
이제 위 식을 대입하여 message 를 다음과 같이 표현할 수 있다.
여기서 는 다음과 같이 정의되며, 마찬가지로 variable node에서 factor node로 전달하는 message라는 의미를 가진다.
이제 위의 식들을 조금 살펴보면, factor node에서 variable node로 전달하는 message는, factor node로 들어오는 모든 message들의 product에 해당 variable node의 factor를 곱한 후 normalization한 것이라는 걸 알 수 있다.
이제 variable node 에서 factor node 로 전달하는 message를 조금 더 살펴보자. 이는 variable node와 연결된 를 제외한 factor node 과 관련된 subtree 들의 product로 표현된다.
이를 다시 위의 식에 대입하여 를 다음과 같이 표현할 수 있다.
즉 variable node에서 factor node로 전달하는 message는 해당 variable로 들어오는 모든 message들의 product이다.
이제 factor node가 variable node로, 그리고 variable node가 factor node로 계속해서 message를 전달하는 과정이 점화식처럼 표현이 되었다. 이를 이용해 추론을 하기 위해서는 당연히 초깃값이 필요한데, 만약 시작하는 leaf node가 variable node면 message의 값을 1로, factor node면 message의 값을 로 간주한다.
그러면 이제 variable 의 marginal 를 구하기 위해, 를 factor graph의 root로 간주하고 모든 leaf로부터 message를 recursive하게 전달해 까지 모든 message를 전달하면 된다. 이 과정에서 message를 전달하기 위해서는 다른 모든 neighbor로부터 message를 전달받아야 한다는 사실을 상기하자.
또 모든 variable의 marginal을 각각 찾고자 한다고 하면, 임의의 root를 잡아 거기까지 모든 message propagation을 진행한다. 그러면 root는 모든 message를 받았으니 다른 어떤 neighbor로도 message를 전달할 수 있고, 그러면 그 neighbor 역시 모든 neighbor로부터 message를 받았으니 다른 모든 neighbor로 message를 전달할 수 있다. 이런 식으로 전부 구하면 된다.
8.4.5 The max-sum algorithm
이제 sum-product 알고리즘을 통해 marginal을 찾을 수 있게 되었는데, 우리의 관심사는 사실 다른 곳에 있었다! 우리가 많은 경우 하고자 하는 일은 1) 최대의 posterior probability 값을 찾는 것과 2) 그 때의 variable setting을 찾는 것이다. 이를 위한 알고리즘이 바로 max-sum 알고리즘인데, 그냥 사실 똑같다.
먼저 위와 같은 setting을 찾기 위해 모든 variable의 marginal을 찾은 뒤 argmax state를 찾으면 되는 것 아닌가, 하는 생각을 할 수 있는데, 이는 joint maximization이 아님에 주의해야 한다. 즉 이렇게 하면 안 된다.
이제 maximum probability를 찾기 위한 식은 다음과 같은데,
이는 sum-product 알고리즘에서의 summation과 아주 똑같은 형태이며, 이에 따라 아주 동일한 재배치가 가능하다는 것을 바로 알 수 있다. 즉 sum-product 알고리즘의 summation을 maximization으로 단순히 대체하면 된다! 이게 바로 max-product 알고리즘이다.
하지만 확률값을 계속 곱하다보면 컴퓨터는 underflow 문제를 일으키게 된다. 이에 따라 확률값들의 product를 logarithm의 summation으로 대체하게 되는데, 이게 바로 max-sum 알고리즘이다. 초깃값은 1과 에서 0과 로 교체하면 된다.
이러한 max-sum 알고리즘을 sum-product 알고리즘과 아주 똑같은 방식으로 적용하여 maximum posterior 값을 찾을 수 있다.
이제 그러면 maximum posterior를 형성하는 variable setting을 찾는 문제를 풀어야 하는데, 이는 dynamic programming을 통해 쉽게 풀 수 있다. 즉 max-sum 알고리즘을 진행하면서 각 variable의 argmax state를 저장해놓고, root node에서의 최적 state를 찾은 후, 다시 leaf로 역행하면서 해당 state에 대한 argmax state를 찾아 설정하면 되는 것이다. 교재의 그림 8.53을 보면 직관적으로 설명되어있다.
8.4.6 Exact inference in general graphs
트리 구조가 아닌 일반적인 그래프에서 exact inference를 수행할 수 있는 junction tree 알고리즘을 소개한다.
8.4.7 Loopy belief propagation
Loop가 있는 그래프에서 효율적인 inference를 진행하기 위해, 그냥 다 모르겠고 어찌되었든 max-sum 알고리즘을 적용하겠다는 것이다. Loop가 있기 때문에 조금은 특수한 message passing schedule이 필요하며, 그래프에 따라 잘 되는 경우도 있고 잘 안 되는 경우도 있다고 한다.
8.4.8 Learning the graph structure
지금까지는 그래프의 형태를 정해 놓고 추론을 수행하는 방법들에 대해 배웠는데, 그래프의 형태를 데이터로부터 학습하려 하는 시도들 역시 꽤 있다고 한다. 하지만 여러모로 쉽지 않다는 듯하다.
정말... 쉽지 않은 챕터였다!
E.O.D.