[논문 정리] GFlowNet Foundations - 1
Why This Paper?
이번에 연구실에 들어오게 되면서 공동 과제를 받았다. (오자마자 받는건 거의 최초라고 하시더라). 아무래도 같이 하시는 분들이 연구 경험이 나보다 훨신 많으시기 때문에 내가 열심히 해야겠다는 생각이 들었다. 공동 과제를 주도하신 교수님께서 몇몇 논문들을 알려주셨고 나는 그걸 꼼꼼히 정리하면서 읽어보고자 한다. 이 논문이 그 중에 첫 논문이다.
Introduction
GFlowNet은 확률적 분포의 모드를 효율적으로 탐색하고, 보상 함수에 비례한 샘플을 생성한다. MCMC(Monte-Carlo Markov Chain)의 대안으로 긴 탐색 과정 없이 다양한 샘플링 결과를 제공한다. 여기서 MCMC는 시행착오를 통해 확률값을 근사하는 것을 나타낸다. 예를 들어 내가 주사위를 던지는데 각 면이 나올 확률을 모른다고 가정하면 주사위를 계속 굴려서 나온 값으로 확률이 1/6이라는 것을 추측하는 것이다. 아래는 GPT가 비유해준 MCMC와 GFlowNet의 비유이다.
MCMC : 음식점을 무작위로 선택하면서 긴 여정을 반복하여 분포를 점차 학습한다. 같은 음식점을 여러 번 방문하거나 시간이 오래 걸릴 수 있다.
GFlowNet : 지도와 음식점의 평점을 가지고 있다. 평점에 비례한 확률로 해당 음식점을 방문한다.
Flow는 상태 간 확률 분배를 나타내며 상태 간 흐름의 균형을 유지하여 목표 분포를 학습한다. 이를 이요하여 GFlowNet은 확률적 추론 및 샘플링 다양성을 극대화하는 데 적합한 방법론으로 사용된다.
아래는 GFlowNet이 객체를 반복적으로 구성하는 과정을 나타낸 그림이다. 여기서 표기는 일반적인 강화학습에서 사용하는 표기법을 사용했다.
Flow Networks and Markovian Flows
이 부분에서는 우리는 많은 기본 정의를 복습할 것이며 이것들이 flow networks와 GFlowNets의 기반이 될 것이다.
정의 1. 그래프는 튜플 G = (S, A)가 있을 때, S는 상태의 유한한 집합, A는 S X S의 부분 집합이다. A의 구성요소는 s -> s'으로 표시되며 이를 간선 또는 전이라고 부른다. 즉 A는 간선 또는 전이를 나타내는 상태 쌍의 집합이다.
경로는 그래프 상에서 상태 S의 연속적인 시퀀스 $ \gamma = (s_1, ...,s_n)$ 을 나타낸다. 경로 상의 모든 전이 $s_t \rightarrow s_{t+1}$는 $A$ 에 포함된다. $(s_t \rightarrow s_{t+1}\in A)$ 경로의 길이는 간선의 개수로 나타낸다.
DAG $G = (S, A)$와 $s, s' \in S$ 가 주어졌을 때,
$s$에서 $s'$으로 도달하는 경로가 존재하면 $s < s'$로 나타낸다.(이때 $s$와 $s'$은 동일하지 않다.)
$s$에서 $s'$으로 도달하는 경로가 존재하거나 $s$와 $s'$이 동일하면 $s \leq s'$로 나타낸다.
$s$에서 $s'$으로 도달하는 경로가 존재하지 않으면 $s \parallel s'$로 나타낸다.
정의 2. DAG $G = (S, A)$가 주어졌을 때, 상태 s의 부모 집합은 $Par(s)$로 정의하며 상태 s의 직접 부모 상태들의 집합이다. $Par(s) = \{s' \in S : (s',s) \in A\}$,
반대로 상태 s의 자식 집합은 $Child(s)$로 정의하며 상태 s의 직접 자식 상태들의 집합이다. $Child(s) = \{s' \in S : (s,s') \in A\}$ 이다.
정의 3. DAG $G = (S, A)$가 주어졌을 때 $G$가 pointed DAG가 되려면 아래의 두 조건을 만족하는 상태 $s_0$와 $s_f$가 존재해야한다.
$$ \forall s \in S \;\; s_0 < s \;\; and \;\; s < s_f $$
여기서 $s_0$는 모든 상태의 조상 상태이며 시작점의 역할을 한다. source state 혹은 initial state라고 한다.
반대로 $s_f$는 모든 상태의 후손 상태이며 종료점의 역할을 한다. 종료 상태(sink state) 혹은 final state라고 한다.
부모가 종료 상태(sink state)인 상태 s는 Terminationg State라고 부른다.
$$S^{f} = \{s \in S, s \to s_f \in A^f\} = Par(s_f)$$
종료 상태(sink state)로 이어지는 전이(transition)은 Terminating Edge라고 부른다.
$$A^{f} = \{s \to s' \in A, s' = s_f\}$$
반대로 종료 상태로 연결되지 않는 간선들은 Non-Terminating Edge라고 부른다.
$$A^{-f} = \{s \to s' \in A, s' \neq s_f\}$$
아래의 그림은 DAG를 나타내는 그림이다.
정의 4. $P_F$ 는 간선 $(s, s') \in A$에 대해 정의된 비음수 확률 함수이다.
한 상태 s에서 가능한 모든 자식 상태 Child(s)로의 확률 합은 1이라는 뜻이다.
$$\forall s \in S \setminus \{s_f\}, \;\;\;\; \sum_{s' \in Child(s)} P_F(s \to s') = 1$$
반대로 $P_B$ 는 간선 $(s', s) \in A$에 대해 정의된 비음수 확률 함수이다.
한 상태 s에서 가능한 모든 부모 상태 Par(s)로의 확률 합은 1이라는 뜻이다.
$$\forall s \in S \setminus \{s_0\}, \;\;\;\; \sum_{s' \in Par(s)} P_B(s' \to s) = 1$$
정리 5. $G = (S, A)$를 pointed DAG라고 가정하자. $s \in S \setminus \{s_f\} $인 어떤 상태 s에서 $ \mathcal{T} _{s,s_f}\subseteq \mathcal{T} ^{partial}$라고 하는데 여기서 $ \mathcal{T} _{s,s_f}$는 상태 $s$에서 시작하여 종료 상태 $s_f$에서 끝나는 G의 모든 궤적들의 집합을 의미한다. 그리고 $ \mathcal{T} ^{partial}$은 그래프 G 내의 모든 가능한 궤적들의 집합을 의미한다.
반대로 $ \mathcal{T} _{s_0,s}$는 시작 상태 $s_0$에서 시작하여 상태 $s$에서 끝나는 G의 모든 궤적들의 집합을 의미한다.
위에서 나온 $\hat{P_F}$와 $\hat{P_B} $를 $\tau^{partial}$로 다시 정의할 수 있다.
$$\forall \tau = (s_1, ...,s_n) \in \mathcal{T}^{partial} \;\; \hat{P_F(\tau)} := \prod_{t=1}^{n-1}\hat{P}_F(s_{t+1} | s_t)$$
$$\forall \tau = (s_1, ...,s_n) \in \mathcal{T}^{partial} \;\; \hat{P_B(\tau)} := \prod_{t=1}^{n-1}\hat{P}_B(s_t | s_{t+1})$$
위의 수식을 활용하면 아래와 같은 식이 자연스럽게 따라온다.
$$\forall s \in S \setminus \{s_f\} \;\; \sum_{\tau \in \mathcal{T}_{s,f}} \hat{P_F}(\tau) = 1$$
$$\forall s' \in S \setminus \{s_0\} \;\; \sum_{\tau \in \mathcal{T}_{0,s'}} \hat{P_B}(\tau) = 1$$
편의성을 위해 $\mathcal{T}_{s \to s' ,s_f}$ 를 $s \to s'$에서 시작하고 $s_f$에서 끝나는 것을 의미하며
$\mathcal{T}_{0 ,s \to s'}$ 를 $s_0$에서 시작하고 $s \to s'$에서 끝나는 것으로 정의한다. 아래와 같이 쓸 수 있다.
$$\forall s \neq s_f \; \mathcal{T}_{s,f} = \bigcup_{s' \in Child(s)} \mathcal{T}_{s \to s',s_f}, \{\mathcal{T}_{s \to s',s_f}, s' \in Child(s)\}$$
$$\forall s' \neq s_0 \; \mathcal{T}_{0,s'} = \bigcup_{s' \in Par(s')} \mathcal{T}_{0,s \to s'}, \{\mathcal{T}_{0, s \to s'}, s \in Par(s')\}$$
추가적으로 $s \neq s_f$에 대해 $d_{s, f}$를 $\mathcal{T}_{s,f}$에서 제일 긴 경로로 정의한다. 그리고 반대로 $s' \neq s_o$에 대해서 $d_{0,s'}$를 $\mathcal{T}_{0,s}$에서 제일 긴 경로로 정의한다.
만약 $d_{s,f} = 1$이고 $d_{0,s'} = 1$ 이라면 $\mathcal{T}_{s,f} = \{(s \to s_f)\}$ 이고 $\mathcal{T}_{0,s'} = \{(s_0 \to s')\}$이다. 따라서 $s_f$의 child는 오직 s라는 것이고 $s_0$의 parent는 오직 s'이 된다.
Trajectories and Flows
GFlowNet에서 flow는 pointed DAG에서 정의된 함수로, 네트워크를 따라 흐르는 입자의 흐름으로 이해할 수 있다. 각 입자는 출발 지점 $s_0$에서 시작하여 어떤 경로를 따라 이동하고, 최종적으로 $s_f$에서 종료된다. 여기서 특정 경로 $\tau$를 공유하는 입자의 수가 flow $F(\tau)$로 표현된다.
정의 6. pointed DAG가 주어졌을 때 궤적 흐름(Trajectory Flow)는 $F : \mathcal{T} \mapsto \mathbb{R^+}$에서 정의된 비음수 함수이다. $F$는 특정 상태, 간선, 궤적 집합에 대한 확률적 또는 가중치 기반 분석을 가능하게 한다. $F$는 궤적 집합 $\mathcal{T}$의 부분집합 $2^{\mathcal{T}}$에 대해 확장이 가능하다.
$$F(A) = \sum_{\tau \in A} F(\tau)$$
여기서 $(G, F)$의 페어를 flow network라고 부른다. 그리고 여기서 $(T, 2^T, F)$는 measure space로 작동하여 궤적 분포를 수학적으로 다룬다.
정의 7. 상태 s에서의 $F(s)$는 특정 상태 s를 지나는 모든 완성된 궤적들의 Flow로 정의된다.
$$F(s) := F(\{\tau \in \mathcal{T} : s \in \tau\}) = \sum_{\tau \in \mathcal{T}:s \in \tau} F(\tau)$$
간선 $s \to s'$에서의 $(s \to s')$은 특정 간선 $(s \to s')$을 지나는 모든 완성된 궤적들의 Flow로 정의된다.
$$F(s \to s') := F(\{\tau \in \mathcal{T} : s \to s' \in \tau\}) = \sum_{\tau \in \mathcal{T}:s \to s' \in \tau} F(\tau)$$
만약 간선 $(s \to s')$이 DAG $G$에 포함되지 않으면 $F(s \to s') = 0$이 된다. 그리고 $(s \to s_f)$를 지나는 Flow는 종료 전이(Terminationg Flow)라고 합니다.
정리 8. flow network $(G, F)$가 주어졌을 때 state flows와 edge flows는 아래와 같이 정리할 수 있다.
$$\forall s \in S \setminus \{s_f\} \; F(s) = \sum_{s' \in Child(s)} F(s \to s')$$
$$\forall s' \in S \setminus \{s_0\} \; F(s') = \sum_{s' \in Par(s')} F(s \to s')$$
Flow Induced Probability Measures
정의 9. flow network $(G, F)$가 주어졌을 때, total flow $Z$는 완성된 경로들의 flows의 합으로 정의된다.
$$Z := F(\mathcal{T}) = \sum_{\tau \in \mathcal{T}} F(\tau)$$
정리 10. 시작 지점과 종료 지점을 지나는 flow값은 flow $Z$와 동일한 값을 가진다. 왜냐하면 모든 완성된 $\tau$에는 $s_0, s_f$가 포함되기 때문에 아래와 같이 정리가 가능하다.
$$F(s_0) = \sum_{\tau \in \mathcal{T}}F(\tau) = Z$$
$$F(s_f) = \sum_{\tau \in \mathcal{T}}F(\tau) = Z$$
measure space $(T, 2^T, F)$를 나중에 $Z$와 Flow를 이용하여 확률적 공간으로 변환할 수 있다.
정의 11. flow network $(G, F)$가 주어졌을 때, flow probability는 아래와 같이 정의할 수 있다.
$$\forall A \subseteq \mathcal{T} \; P(A) := \frac{F(A)}{F(\mathcal{T})} = \frac{F(A)}{Z}$$
두가지 이벤트 $A, B \subseteq \mathcal{T}$라고 할 때 조건부 확률 P(A | B)는 아래와 같다.
$$P(A|B) := \frac{F(A\cap B)}{F(B)}$$
이것과 비슷하게 flow $F$에서 적용한다면 아래와 같이 식이 나타난다.
$$\forall s \in S \;\;\;\; P(s) := \frac{F(s)}{Z}$$
정의 12. flow network $(G, F)$가 주어졌을 때, forward transition probability operator $P_F$는 S x S의 함수이며, $F$에 의해 유도된 조건부 확률의 특수한 경우를 나타낸다.
$$ \forall s \to s' \in \mathbb{A} \;\; P_F(s'|s) := P(s \to s'|s) = \frac{F(s \to s')}{F(s)} $$
이와 비슷하게 backwards transition probability는 아래와 같이 표현할 수 있다.
$$\forall s \to s' \in \mathbb{A} \;\; P_B(s|s') := P(s \to s'|s') = \frac{F(s \to s')}{F(s')}$$
정의 13. flow network $(G, F)$가 주어졌을 때, terminating state probability $P_T$는 Flow 확률 $P$에 따른 종료 상태($S_f$)의 확률을 나타낸다. (여기서 $S^f = Par(s_f)$를 의미한다.)
$$ \forall s \in S^f \;\; P_T(s) := P(s \to s_f) = \frac{F(s \to s_f)}{Z}$$
정리 14. terminating state probability $P_T$는 각 상태 s에 대해 확률 값이 정의되어 있고 확률 값들의 합이 1이다.
$$\sum_{s \in S^f}P_T(s) = 1$$
위의 식을 증명하기 위해 아래의 식을 활용한다.
$$\sum_{s \in S^f}P_T(s) = \frac{1}{Z} \sum_{s \in S^f} F(s \to s_f) = \frac{1}{Z} \sum_{s \in Par(s_f)} F(s \to s_f) = \frac{F(s_f)}{Z} = 1$$
Markovian Flows
Flow를 정의하려면 가능한 모든 경로 $\tau \in \mathcal{T}$에 대해 음수가 아닌 값을 지정해야 한다. 경로의 수는 그래프의 간선 수에 비례하여 증가하므로 모든 경로에 대해 값을 명시하는 것은 비효율적이다. Markovian Flow는 전체 경로를 직접 정의하지 않고도 효율적으로 모델링할 수 있는 특징을 가지고 있다.
정의 15. flow network $(G, F)$와 flow probability measure $P$가 주어졌을 때, $F$는 Markovian flow라고 불리며, 핵심 조건으로는 s에서 s'으로 가는 확률은 이전 궤적 $\tau$에 의존하지 않는 다는 것이다.(여기서 $\tau = (s_0, ..., s)$)
정리 16. flow network $(G, F)$와 P가 주어졌다고 가정하자. 아래의 3가지는 서로 동등한 관계를 가진다.
1. F가 Markovian flow다. (즉, 확률이 이전 궤적에 의존하지 않는다.)
2. 모든 완전한 궤적 $\tau = (s_0 \to \cdots \to s_{n + 1} = s_f)$에 대해
$$P(\tau) = \prod_{t=1}^{n+1}\hat{P}_F(s_t \to s_{t-1})$$
3. 모든 완전한 궤적 $\tau = (s_0 \to \cdots \to s_{n + 1} = s_f)$에 대해
$$P(\tau) = \prod_{t=1}^{n+1}\hat{P}_B(s_{t-1} \to s_t)$$
결론 17. flow network $(G, F)$와 forward transition probability $P_F$가 주어졌다고 하자. $s_0$에서 시작하여 $s_f$에 도달할 때까지 $P_F(s)$를 활용하여 반복적으로 샘플링을 진행한다. 이 절차를 통해 종료 상태에 도달했을 때, 종료 직전 상태 s의 확률은 $P_T(s)$가 된다.
정리 18. DAG $G = (S, A)$가 주어졌을 때, Markovian flow는 다음 중 하나에 의해 정의된다.
1. 전체 흐름 $Z$와 모든 간선 $s \to s' \in A$에 대한 Forward Transition Probabilities $P_F(s \to s')$의 조합
2. 전체 흐름 $Z$와 모든 간선 $s \to s' \in A$에 대한 Backward Transition Probabilities $P_B(s' \to s)$의 조합
3. 종료 간선(terminating) $s \to s_f \in A^f$에 대한 종료 흐름(terminating flow) $F(s \to s_f)$ 와 비종료 간선 $s \to s' \in A \setminus A^f$에 대한 Backward Transition Probabilities $P_B(s' \to s)$의 조합
Flow Matching Conditions
정의 13에서 우리는 순방향(forward) 및 역방향(backward) 확률 함수를 사용하여 Markovian Flow를 정의했다. 아래서부터는 상태(state)와 간선(edge)의 비음수 함수를 이용하여 Markovian Flow를 정의하는 법을 설명할 것이다.
정리 19. $G = (S,A)$를 pointed DAG라고 하고 $\hat{F}$를 $s \in S$ 또는 전이 $s \to s' \in A$를 입력으로 받는 비음수 함수라고 하자. 그러면 아래와 같은 식이 성립한다.(8번의 정리와 비슷하다.)
$$\forall s' > s_0, \hat{F}(s') = \sum_{s \in Par(s')} \hat{F}(s \to s')$$
$$\forall s' < s_f, \hat{F}(s') = \sum_{s'' \in Child(s')} \hat{F}(s' \to s'')$$
정의 20. pointed DAG $G = (S, A)$가 주어졌을 때, $\hat{P_F}$와 $\hat{P_B}$는 $\hat{F}$를 이용하여 정의할 수 있다.
$$\forall s \to s' \in A \; \hat{P}_F(s'|s) = \frac{\hat{F}(s \to s')}{\sum_{s' \in Child(s)}\hat{F}(s \to s')}, \hat{P}_B(s|s') = \frac{\hat{F}(s \to s')}{\sum_{s'' \in Par(s')}\hat{F}(s'' \to s')}$$
정리 21. $G = (S, A)$가 pointed DAG라고 하자. 비음수 함수 $\hat{F}$, forward transition probability $P_F$, backward transition probability $P_B$가 Flow에 해당하기 위해서는 Detailed Balance 조건을 만족해야 한다.
$$ \forall s \to s' \in A \;\; \hat{F}(s)\hat{P}_F(s'|s) = \hat{F}(s')\hat{P}_B(s|s') $$
Equilvalence Between Flows
여기서부터는 종료 상태에서의 확률 분포를 정의하기 위해 Markovian flow를 근사하는 방법을 논의한다. 경로 흐름 사이의 동등성 관계를 분석하여 Markovian 흐름에 초점을 맞추는 것이 정당한 이유를 설명한다.
주어진 DAG $G = (S, \mathbb{A})$에 대해:
- $\mathcal{F}(G)$는 DAG에서 가능한 모든 흐름의 집합이며, 이는 완전한 경로 집함 $\mathcal{T}$에서 비음수 실수 $\mathbb{R}^+$로 대응하는 함수들의 집합이다.
- $\mathcal{F}_{Markov}(G)$는 $\mathcal{F}(G)$ 내에서 Markovian한 flow들만을 포함하는 부분집합이다.
정의 22. $G = (S, A)$가 pointed DAG라고 하자. 그리고 $F_1, F_2 \in F(G)$인 간선 흐름 함수라고 하자. 모든 간선 $s \to s'$에 대해 $F_1$과 $F_2$의 값이 동일하다면 $F_1$과 $F_2$는 동등하다.
$$\forall s \to s' \in \mathbb{A}, \quad F_1(s \to s') = F_2(s \to s')$$
아래는 pointed DAG의 예시이고 옆에 표는 Flow들의 간선에 대한 값이다.
$F_1$과 $F_2$는 동등하다. 동등한 이유를 각 간선별로 살펴보자.
$s_0 \to s_1$ : $F_1$의 경우 1 + 2 = 3, $F_2$의 경우 6/5 + 9/5 = 3으로 동일하다.
$s_0 \to s_2$ : $F_1$의 경우 1 + 1 = 2, $F_2$의 경우 4/5 + 6/5 = 2으로 동일하다.
$s_1 \to s_2$ : $F_1$의 경우 1 + 2 = 3, $F_2$의 경우 6/5 + 9/5 = 3으로 동일하다.
$s_2 \to s_3$ : $F_1$의 경우 1 + 2 = 3, $F_2$의 경우 6/5 + 9/5 = 3으로 동일하다.
$s_2 \to s_f$ : $F_1$의 경우 1 + 1 = 2, $F_2$의 경우 4/5 + 6/5 = 2으로 동일하다.
$s_3 \to s_f$ : $F_1$의 경우 1 + 2 = 3, $F_2$의 경우 6/5 + 9/5 = 3으로 동일하다.
마찬가지로 계산하면 $F_3$와 $F_4$도 동등하다.
그리고 $F_2$와 $F_4$의 경우 Markovian flow이고 $F_1$과 $F_3$의 경우는 Markovian이 아니다.
만약 Markovian flow가 되려면 각 간선별로 flow값이 동일해야한다. $s_0 \to s_2$의 경우 $F_2$에서는 4/5 + 6/5 = 2라는 값이 나오고 $s_2 \to s_f$의 경우 4/5 + 6/5 = 2라서 첫 번째 경로에서는 동일한 값이 나온다. 그러나 $F_3$에서는 $s_0 \to s_2$의 경우 1 + 2 = 3이라는 값이 나오지만 $s_2 \to s_f$에서는 1 + 1 = 2라는 값이 나와 같은 경로임에도 F 값이 다르게 나온다. 이와 마찬가지로 모든 경로를 계산하면 $F_2, F_4$는 Markovian, $F_1, F_3$는 not Markovian이다.
정리 23. $G = (S, A)$가 pointed DAG라고 하자. 만약 2개의 flow function $F_1, F_2$가 동등하며(동일한 간선 Flow값을 가짐) 둘 다 Markovian이라면 두 함수는 실제로 동일한 함수이다.
GFlowNets: Learning a Flow
GFlowNet을 매개변수화하는 방법이 다양하기 때문에, 우리는 이를 추상적인 방식으로 정의하는 것부터 시작한다. 여기서 $o \in \mathcal{O}$는 하나의 매개변수 구성을 나타내며, $\Pi(o)$는 경로 $\tau \in \mathcal{T}$에 대한 확률 분포를 제공하며 $\mathcal{H}$는 flow $F$를 해당 매개변수 $o$로 변환하는 함수이다.
정의 24. $G = (S, A)$가 pointed DAG이고 , $s_0$와 $s_f$가 존재하며, 목표 보상 함수 $R : S^f \to R^{+}$가 주어졌다고 하자. 여기서 삼중 항 $(\mathcal{O}, \Pi, \mathcal{H})$이 flow parametrization이라고 불리는 조건은 아래와 같다.
1. $\mathcal{O}$는 공집합이 아닌 집합이다.
2. $\Pi$는 각 개체 $o \in \mathcal{O}$를 $\Delta (\mathcal{T})$에 속하는 원소 $\Pi(o)$로 매핑하는 함수이다. 여기서 $\Delta (\mathcal{T})$는 $\mathcal{T}$ 위의 확률 분포 집합을 의미한다.
3. $\mathcal{H}$는 $F_{Markov}(G,R)$에서 $\mathcal{O}$로 가는 단사 함수(injective functional)이다.
4. 임의의 $F \in F_{Markov}(G,R)$에 대해 $\Pi(\mathcal{H}(F))$는 $F$와 연관된 확률 측도(probability measure)를 나타낸다.
각 객체 $o \in \mathcal{O}$에 대해 확률 분포 $\Pi(o)$는 terminating state probability를 아래와 같이 정의한다.
$$\forall s \in S^f \;\; P_T(s) := \sum_{\tau \in \mathcal{T}:s \to s_f \in \tau} \Pi(o)(\tau)$$
여기서 $P_T$ 내의 $o$에 대한 의존성은 명확성을 위해 생략되었다.
여기서 갑자기 $(\mathcal{O}, \Pi, \mathcal{H})$이 도입된 이유는 각 객체에 대해 확률 분포를 정의할 수 있기 때문이다. 그러나 모든 객체가 Markovian Flow를 지키는 것은 아니다. Markovian Flow를 지키는 객체 $o$에 대해 확률 분포 $P_T$는 관심 있는 분포를 나타내며 이는 보상함수 $R(s)$와 비례한다.
GFlowNets는 보상 함수 R 또는 이에 해당하는 에너지 함수로부터 샘플링하여 일반적으로 다루기 어려운 문제를 해결할 수 있다. 에너지 함수는 아래와 같이 정의할 수 있다.
$$\forall \in S^f \;\; \mathcal{E}(s) := -\log R(s)$$
직접적으로 마르코프 흐름 $F$를 근사하는 것은 어려운 문제기 때문에 적절한 객체 집합 $\mathcal{O}$를 선택하여 객체 $o$를 찾는 문제로 변환하면 쉽게 해결할 수 있으며 함수 근사 기법을 사용할 수 있다.
정의 25. GFlowNet은 $(G, R, \mathcal{O}, \Pi, \mathcal{H})$로 정의된다.
- $G = (S, A)$는 pointed DAG이다.
- $R : S^f \to R^+$는 보상 함수이다.
- $( \mathcal{O}, \Pi, \mathcal{H} )$는 $(G, R)$의 flow parametrization이다.
정의 26. $(G, R, \mathcal{O}, \Pi, \mathcal{H})$가 GFlowNet이라고 가정하자. flow matching loss는 다음 조건을 만족하는 함수 $\mathcal{L} : \mathcal{O} \to R^+$를 의미한다.
$$ \forall o \in \mathcal{O} \;\; \mathcal{L}(o) = 0 \Leftrightarrow \exists F \in \mathcal{F}_{Markov}(G, R) \;\; o = \mathcal{H}(F) $$
즉, 손실 함수가 0이 되는 경우, 해당 객체 $o$는 Markovian Flow F에서 변환된 객체 $o = \mathcal{H}(F)$와 일치한다.
손실 함수에는 3가지 분해 속성이 존재한다. 아래부터 1개씩 설명한다.
1. Edge-decomposable(간선 기반 분해 가능)
어떤 함수가 아래를 만족하면 $\mathcal{L}$은 edge-decomposable하다고 한다.
$$ \forall o \in \mathcal{O}, \;\; \mathcal{L}(o) = \sum_{s \to s' \in A} L(o, s \to s')$$
즉, 손실 함수를 각 간선 $s \to s'$에 대해 분해할 수 있는 경우
2. State-decomposable(상태 기반 분해 가능)
어떤 함수가 아래를 만족하면 $\mathcal{L}$은 state-decomposable하다고 한다.
$$ \forall o \in \mathcal{O}, \;\; \mathcal{L}(o) = \sum_{s \in S} L(o, s)$$
즉, 손실 함수를 각 상태 $s$에 대해 분해할 수 있는 경우
3. Trajectory-decomposable(궤적 기반 분해 가능)
어떤 함수가 아래를 만족하면 $\mathcal{L}$은 trajectory-decomposable하다고 한다.
$$ \forall o \in \mathcal{O}, \;\; \mathcal{L}(o) = \sum_{\tau \in \mathcal{T}} L(o, \tau)$$
즉, 손실 함수를 각 상태 $\tau$에 대해 분해할 수 있는 경우
위와 같이 손실 함수를 정의하면 GFlowNet의 최적화 문제를 다음과 같은 손실 함수 최소화 문제로 변환할 수 있다.
$$\min_{o \in \mathcal{O}}\mathcal{L}(o)$$
즉, $\mathcal{L}$이 미분 가능하면 경사 하강법을 이용하여 해결이 가능하다.
여기서 edge-decomposable 손실 함수를 사용할 경우 아래와 같이 변환된다.
$$\min_{o \in \mathcal{O}}\mathbb{E}_{(s \to s') \sim \pi_T}[L(o, s \to s')]$$
즉, 모든 가능한 간선을 샘플링하며 기대값을 최적화하는 방식으로 학습할 수 있다.
내용이 많아서 좀 길어지기 때문에 2편을 만들어서 작성하려고 한다