[2] PGM Representations: definition of p(x) by converting energy into probability

아래 references의 강의 및 자료들을 공부하고 짧게 정리한 내용입니다! 저도 공부하면서 정리한 내용이라 틀린 것이 있다면 언제든 댓글 달아주신다면 감사하겠습니다~ :D

____

 

 

앞서 PGM 포스팅 1편에서는 probabilistic graphical model의 overview 및 application에 대해 살펴보았다. 이번 포스팅에서는 probabilistic graphical model에서 multivariate distribution p(x) = p(x1, x2, ..., xn)을 어떻게 정의할 것인지 살펴보려고 한다. 

 

PGM에서는 크게 두 가지 경우를 구분하여 probability distribution을 modeling한다:

• graph에 방향성이 없을 때 (undirected GM): Markov Random Fields, Conditional Random Fields
• graph에 방향성이 있을 때 (directed GM): Bayesian Networks

 

사실 graphical model 강의에서는 각각의 경우 복잡한 그래프에서 어떻게 변수 간의 dependency가 정의되는지 분석하는 내용이 많은데, 최근 주로 사용되는 모델들에서는 Transformer처럼 fully-connected로 independence assumpsion을 최소화하거나, diffusion/RL/VAE처럼 복잡한 그래프 대신 markov property 또는 hidden state를 이용하여 최대한 단순하게 conditional probability를 나타내는 경우가 많은 것 같다.

 

따라서 이 포스팅에서는 방향성이 있는 경우와 없는 경우에 각각 어떤 모델들이 있고 어떻게 energy를 기반으로 p(x)를 정의하는지, 이것이 현재 우리가 일반적인 딥러닝 모델에서 사용하는 softmax확률과 어떤 관련이 있는지를 중점으로 적어보려고 한다.

 

1. Undirected Graphical Models

1.1 Markov Random Fields

 

Undirected graphical model은 왼쪽 그림과 같이 각각의 node(random variables)가 방향성이 없는 edge로 연결된 경우이다. 예시로 BERT에서 masking된 임의의 토큰을 주변 토큰들을 이용하여 추론하는데 이 때 각각의 토큰이 연결되어 있지만 방향성은 없다고 볼 수 있다.

 

Undirected graphical model에는 대표적으로 Markov random fields(MRF)가 있다. MRF에서는 random variable x1, ..., xn이 undirected graph G로 표현되며, 이 때 probability distribution p(x)를 다음과 같이 나타낸다:

 

 

먼저 C는 graph G의 cliques set인데, cliques는 G 안의 fully-connected subgraphs를 의미한다. 그래프에서 node가 너무 많은 경우 계산을 효율화하기 위해 이와 같이 cliques를 이용하여 정의하는데, subgraph 내 요소들의 joint pre-probability를 Φc(x_c)를 이용해 구하게 된다. 맨 마지막 Section 3에 language domain에서의 예시를 추가했으니 이를 참조하면 좋을 것 같다.

 

Φc(x_c)는 potential function으로, pre-probabilistic value를 나타내기 위한 임의의 non-negative function이다. 즉 Z로 나누어 0-1사이의 확률값으로 만들기 전 어떤 필요한 값을 구하는 함수로, BERT에서 softmax를 취하기 전 attention blocks를 이용해 구한 logit과 유사하다고 생각하면 되겠다.

 

마지막으로 Z는 partition function으로, 0-1사이의 probability distribution을 만들기 위한 normalizing constant이다. 이렇게 최종적으로 p(x)는 각각의 potential 값을 normalizing constants로 나누어 줌으로써 정의된다.

 

그런데 매번 Φc를 양수가 되도록 constraint를 주는 건 불편하다. 그래서 Φc에 exponential을 취해 다음과 같이 항상 양수가 되도록 만들고, exponential 내부의 ψ를 대신 계산한다:

 

 

이렇게 정의된 p(x)를 Boltzmann distribution(=Gibbs distribution, Softmax)이라고 하고, exp 내부의 H(x)를 free energy라고 부른다.

Boltzmann Distribution의 물리적 의미.

위 과정을 들여다보면 딥러닝에서 자연스럽게 사용하는 logit을 구하고 마지막에 softmax를 취하는 방식과 매우 유사한데, 실제로 이 방식의 출발점이기도 하다. logit을 구한 뒤 Z로 나눠 확률값으로 바꿔주는 것 까지는 알겠는데, 갑자기 왜 energy라는 말이 나오는지 궁금할 것이다.

 

고등학교 물리 시간에 상자 안에 기체 분자들이 있고, 상자 안의 온도에 따라 이 분자들이 어떻게 분포되어 있는지 구해봤던 기억이 있을 것이다. 아래 식은 물리에서의 boltzmann distribution 식으로, 기체 분자들에게 온도에 따라 에너지가 어떻게 분배되는지 나타내기 위한 분포이다. p_i는 system이 state i에 있을 확률을, 𝜀_i는 state i에서의 energy, T는 temperature를 뜻한다. k는 boltzmann 상수이다.

 

위 비례식을 확률값으로 나타내보면 다음과 같다:

 

결과적으로는 이 분포가 기체 분자의 entropy를 최대화 하면서 에너지를 할당하는 분포라고 한다. 즉 온도가 주어졌을 때 우주의 자연 법칙을 따르면서 분자에 energy를 할당하는 공식이라고 볼 수 있다. 오른쪽 수식은 temperature scaling만 제외하면 앞서 우리가 정의했던 boltzmann distribution과 매우 유사하다. (language model에서는 위 distribution에서 샘플링할 때 temperature scaling을 통해 정확도와 diversity를 조절하는 것을 기억할 것이다.)

 

딥러닝에서 주로 사용되는 manifold assumption을 생각해보자. manifold assumption이란, 의미 있는 text/images/sounds에 대한 probability distribution은 매우 concentrated 되어있다는 것이다. 만약 uniform noise에서 random하게 text를 뽑으면 왼쪽 그림과 같이 아무 의미 없는 글자가 될 것이고 의미 있는 단어를 찾기 매우 힘들 것이다. 따라서 의미 있는 데이터는 굉장히 일부에 몰려 있으므로, 고차원 데이터를 compact한 저차원에 충분히 mapping할 수 있다는 가정이다.

 

즉 이와 유사하게, 의미를 갖는 data 공간은 한정적이고 이 부분에 다른 곳보다 에너지를 낮게 할당한다면, 실제 text/images/sounds에 대한 probability distribution p(x)를 근사할 수 있을 것이다. 따라서 물리에서 분자에게 에너지를 할당하는 것처럼, 왼쪽 그림과 같이 의미 있는 일부 공간에만 에너지를 낮게 할당하고, 나머지 부분에는 에너지를 높게 할당하여 probability distribution 자체를 모델링하자는 것이다.

[그림 출처: https://jaejunyoo.blogspot.com/2018/02/energy-based-generative-adversarial-nets-1.html]

 

Deep Learning에서의 softmax와 연관성.

즉 앞서 boltzmann distribution을 통해 p(x)를 정의했던 내용을 다시 한번 정리하면, 유의미한 data에 대한 energy landscape를 Φc를 통해 유추하고, 이 에너지를 normalization constant Z를 이용하여 probability로 바꾸자는 것이다. 그런데 모든 분자나 data point에 대한 Φc를 구할 수 없으므로 사실상 정확한 Z는 구할 수 없다. 그래서 아래 예시와 같이 Z를 제거하는 trick을 쓰거나, classification model의 경우 data distribution p(x) 대신 label distribution p(y|x) 을 구함으로써 이를 우회하였다. 우리가 평소에 쓰는 softmax는 전체 label class 내에서 구하거나, language model의 경우 모든 token 종류에 대해서 구했던 것을 기억할 것이다. 

 

즉 현재까지 소개한 내용은 unsupervised model(=p(x)를 유추)이며, 뒤 Section 1.3에 나오는 CRF는 MRF를 supervised model (=p(y|x)를 유추)로 바꾼 내용이다.

 

1.2 [Example] Restricted Boltzmann Machine: conditional independence + energy-based model training

Restricted Boltzmann machine은 DNN, CNN같은 모델들과 달리 확률 밀도 함수 p(x) 자체를 모델링하기 위한 것으로, unsupervised learning이다. 여기서는 이 모델이 conditional independence를 어떻게 사용했고, 이 모델을 어떻게 training했는지만 간단히 살펴보도록 하겠다.

Restricted Boltzmann Machine (RBM).

앞서 PGM 포스팅 1편에서 언급했던 condition independence assumption과 같이, RBM에서는 random varibales (그림에서 visible units) x1 ~ xn은 marginally dependent하지만, hidden state h에 conditioned 되는 경우 conditionally independent하다고 가정했다. 즉 아래와 같이 표현할 수 있다:

Training.

RBM training은 iterative한 방식을 사용한다. 즉 gibbs sampling을 이용해 h ~ p(h|x)와 x' ~ p(x|h)를 샘플링하고, 이전 step의 x와 현재 step에서의 x'을 비교한다. 이 때 x와 x'간의 차이가 일정 수준 이하로 수렴할 때까지 이 과정을 반복한다. 이러한 과정을 constrastive divergence라고 한다.

출처: https://angeloyeo.github.io/2020/10/02/RBM.html

 

즉 위 식과 같이 원래 data로 부터 얻은 visible layer v의 free energy F(v)와 샘플링한 데이터로부터 얻은 visible layer v(1)의 free energy F(v(1))간의 차이를 loss로 두고, loss가 0에 가까워질때까지 iterative하게 학습하는 것이다.

 

이렇게 constrastive divergence를 사용하는 이유는 사실상 intractable한 normalizing constant Z를 구하지 않기 위함이라고 한다. 최근 RLHF alignment methods 중 하나로 각광받은 DPO에서도 위와 같이 Z를 구하는 것을 피하기 위해서 constrastive learning 방식을 사용하는데, 이러한 역사가 있었다 (신기...). 이 부분에 대한 내용은 아래 Energy based model 블로그에 자세히 설명되어 있다! 

 

*[참조] 1.2 내용은 아래 블로그들에 더 잘 설명되어 있고, 이 블로그들을 통해 공부했습니다!

RBM: https://angeloyeo.github.io/2020/10/02/RBM.html

Restricted Boltzmann Machine - 공돌이의 수학정리노트 (Angelo's Math Notes)

Energy based model: https://process-mining.tistory.com/215

Energy-based model 설명 (EBM 설명)

 

1.3 Conditional Random Fields (CRF)

MRF에서 p(x)를 모델링했던 것과 달리, CRF에서는 conditional distribution인 p(y|x)를 모델링한다. 이 경우 x가 주어졌을 때 y를 예측하는 distribution이므로 supervised learning이며, x에 condition된 label distribution을 학습하는 것이다.

 

CRF에서는 random variable set의 종류가 x, y 두 가지가 있으므로 p(y|x)는 다음과 같이 정의된다:

 

여기서는 conditional distribution을 계산하므로 joint pre-probability Φc(x_c, y_c)를 계산하는 것을 볼 수 있다. 또한 Z(x)의 경우, x가 주어졌을 때 y의 probability를 계산하는 것이므로 x에 dependent해야 하고 (y는 예측해야 함), 따라서 y에 대해 marginalize하는 것을 볼 수 있다. 맨 마지막 Section 3에 language domain에의 application을 소개하면서, undirected와 directed인 경우 p(x) 모델링의 차이점을 다시 한 번 정리하였다.

 

2. Directed Graphical Models: Bayesian Networks

Bayesian Networks는 왼쪽 그림과 같은 Directed Acyclic Graph (DAG)로 구성된 네트워크로, undirected models와 달리 방향성을 가지고있다. 이러한 경우의 장점은 모델의 generative sampling 과정을 자연스럽게 encoding한다는 것이다. 즉, 각각의 variable은 자신의 parents에만 의존하여 모델링된 distribution으로부터 stochastic하게 샘플링된다.

 

 

Bayesian network에서 p(x)는 다음과 같이 정의된다:

 

 

위 식은 fully connected인 경우로, 이 때 오른쪽 항의 conditional distribution들은 다음과 같이 간소화될 수 있다:

 

x_Ai는 x_i의 ancestor variables이다. PGM 포스팅 1편에서 언급했듯이 만약 각 변수가 d개의 값을 가질 수 있다면, O(d^n)개만큼의 exponential number의 parameter가 필요하다. 하지만 bayesian network를 이용해서 연결성을 정의하면, 만약 각각이 최대 k개만큼의 ancestor를 가진다면 parameter 수를 O(d^k)만큼으로 줄일 수 있다.

3. Extend to language domain application: Hidden Markov Model (Bayesian) vs. Conditional Random Fields

앞서 undirected model에서 p(x)를 energy를 이용해서 정의했었는데, 이 섹션에서는 language domain에서 예시를 통해 undirected인 경우와 directed인 경우 p(x)수식이 어떻게 달라지는지 보고자 한다.

 

token sequence x가 주어지고 여기에 각 토큰의 품사 y를 라벨링하는 task를 생각해보자. 이 경우 우리는 p(y|x)를 모델링해야 한다. 앞서 Section 1.3에서 언급한 CRF를 사용하면 다음과 같이 나타낼 수 있다:

 

출처: https://lovit.github.io/nlp/2018/09/13/crf_based_tagger/

 

위 식에서 λ는 그냥 coefficient고, m은 potential function의 개수, n은 y의 sequence length이다. f는 앞서 언급한 potention function Φc를 의미한다. 수식을 보면 joint pre-probability Φc(x,y)자리에 유사하게 f(x, yi, yi-1)이 들어간다. 또한 단 하나의 boltzmann distribution을 계산하는 것을 볼 수 있는데, 이는 undirected model로 y 간의 방향성을 정의하지 않았기 때문이다. 앞서 언급한 대로 분모의 경우 normalize constant Z(x)를 의미하는데, x에 dependent해야 하므로 y에 대해 marginalize한 것을 볼 수 있다.

 

반면에 directed model의 일종인 hidden markov model 계열 모델을 사용한 경우 p(y|x)는 다음과 같이 모델링된다:

출처: https://lovit.github.io/nlp/2018/09/13/crf_based_tagger/

 

이 경우 exponential 안의 sum이 바깥의 product로 빠진 것을 볼 수 있다. 즉 이 경우 y간에 방향성이 정의되었기 때문에, 각각의 step마다 boltzmann distribution을 통해 p(y_i|y_i-1, x)를 구하고 최종적으로 p(y|x)를 위해 구한 값들을 모두 곱해주는 것을 볼 수 있다.

 

 

이번 포스팅에서는 PGM에서 probabilistic modeling 방법에 대해 살펴보았다. 다음 포스팅에서는 이제 p(x)를 정의했으니, p(x)를 learning하는 방법에 대해 소개할 예정이다!

 

[References]

주요 참고 자료:

https://ermongroup.github.io/cs228-notes/

https://www.cs.cmu.edu/~epxing/Class/10708-20/lectures.html

 

energy based model:

https://jaejunyoo.blogspot.com/2018/02/energy-based-generative-adversarial-nets-1.html

https://process-mining.tistory.com/215

 

RBM:

https://angeloyeo.github.io/2020/10/02/RBM.html

 

HMM/CRF:

https://lovit.github.io/nlp/2018/09/13/crf_based_tagger/