Complexity of the clique tree is exponential in the tree-width of the network $ \rightarrow $ exact algorithms become infeasible for networks with a large tree-width.
Casting exact inference as an optimization problem.
Given factorized distribution $$ P_{\Phi} (\mathcal{X}) = \frac{1}{Z} \prod_{\phi \in \Phi} \phi(U_\phi) $$
Goal: Answering queries about $ P_{\Phi} $
Recall:
Given a set of beliefs $$ Q = \{ \beta_i : i \in V_{\mathcal{T}} \} \cup \{ \mu_{i,j} : (i-j) \in E_{\mathcal{T}} \} $$
The set of beliefs in $ T $ defines a distribution $ Q $ due to the calibration requirement: $$ \boxed{ Q(\mathcal{X}) = \frac{\prod_{i \in V_{\mathcal{T}}} \beta_i}{\prod_{(i - j) \in E_{\mathcal{T}}} \mu_{i, j}} } $$
Calibration requirement ensures $ Q $ statisfies the marginal consistency constrants: For each $ (i - j) \in E_{\mathcal{T}} $, the beliefs on $ S_{i, j} $ are the marginal of $ B_i $ (and $ B_j $). $$ \mu_{i, j} (S_{i, j}) = \sum_{C_i - S_{i, j}} \beta_i (C_i) = \sum_{C_j - S_{i, j}} \beta_j (C_j) $$
From Theorem 10.4 $$ \beta_i[c_i] = Q(c_i) $$
$$ \mu_{i, j}[s_{i, j}] = Q(s_{i, j}) $$
CTree-Optimize-KL
Find $ Q = \{ \beta_i : i \in V_{\mathcal{T}} \} \cup \{ \mu_{i,j} : (i-j) \in E_{\mathcal{T}} \} $
Maximizing $ - \mathbb{D} (Q || P_\Phi) $
subject to $$ \mu_{i, j} (s_{i, j}) = \sum_{C_i - S_{i, j}} \beta_i (c_i) \quad \forall (i - j) \in E_T, \forall s_{i, j} \in Val(S_{i, j}) $$
$$ \sum_{c_i} \beta_i (c_i) = 1 \quad \forall i \in V_T $$
If $ \mathcal{T} $ is an I-map of $ P_\Phi $, then there is a unique solution to CTree-Optimize-KL.
Goal:
Functions
Functional
$$ \boxed{ \mathbb{D} (Q || P_\Phi) = \ln Z - F[\tilde{P}_\Phi, Q] } $$
where $ F[\tilde{P}_\Phi, Q] $ is the energy functional
$$ \begin{align*} F[\tilde{P}_\Phi, Q] &= E_Q[\ln \tilde{P}(\mathcal{X})] + H_Q(\mathcal{X}) \end{align*} $$
$$ = \sum_{\phi \in \Phi} E_Q [\ln \phi] + H_Q(\mathcal{X}) $$
$$ \mathbb{D} (Q || P_\Phi) = E_Q[\ln Q (\mathcal{X})] - E_Q[\ln P_\Phi (\mathcal{X})] $$
Thus, $$ \mathbb{D} (Q || P_\Phi) = - H_Q (\mathcal{X}) - E_Q \left[ \sum_{\phi \in \Phi} \ln \phi \right] + E_Q[\ln Z] $$
$$ = -F[\tilde{P}_\Phi, Q] + \ln Z $$
Since $ \mathbb{D} (Q || P_\Phi) $,
$$ \ln Z \geq F[\tilde{P}_\Phi, Q] $$
Inference methods that can be viewed as strategies for optimizing the energy functional.
The exact energy functional $$ F[\tilde{P}_\Phi, Q] $$
has terms involving the entropy of an entire joint distribution; thus, it cannot be tractably optimized $ \rightarrow $ factored energy functional
$$ \tilde{F}[\tilde{P}_\Phi, Q] $$
defined in terms of entropies of clusters and sepsets, which can be computed efficiently based purely on local information at the clusters.
The marginal polytope is the set of all cluster (and sepset) beliefs that can be obtained from marginalizing an actual distribution $ P $
$$ Marg[U] = \{ Q_P: P \text{ is a distribution over } \mathcal{X} \} $$
that is
$$ Q_P = \{ P(C_i): i \in V_U \} \cup \{ P(S_{i, j}): (i-j) \in E_U \} $$
$$ \tilde{F}[\tilde{P}_{\Phi}, Q] $$
$$ = \boxed{ \sum_{i \in V_{\mathcal{T}}} E_{C_i \sim \beta_i}[\ln \psi_i] + \sum_{i \in V_{\mathcal{T}}} H_{\beta_i}(C_i) - \sum_{(i-j) \in E_{\mathcal{T}}} H_{\mu_{i,j}}(S_{i,j}) } $$
Thus, $$ \sum_{\phi \in \Phi} E_Q [\ln \phi] = \sum_{i \in V_{\mathcal{T}}} E_{C_i \sim \beta_i}[\ln \psi_i] $$
Recall $$ H_Q (\mathcal{X}) = E_Q \left[ \ln \frac{1} {Q(\mathcal{X})} \right] $$
$$ Q(\mathcal{X}) = \frac{\prod_{i \in V_{\mathcal{T}}} \beta_i}{\prod_{(i - j) \in E_{\mathcal{T}}} \mu_{i, j}} $$
Take the logarithm
$$ \ln Q(\mathcal{X}) = \sum_{i \in V_T} \ln \beta_i(c_i) - \sum_{(i-j) \in E_T} \ln \mu_{i,j}(s_{i,j}) $$
Compute entropy $$ H_Q(\mathcal{X}) = - E_Q \left[ \sum_{i \in V_T} \ln \beta_i(c_i) - \sum_{(i-j) \in E_T} \ln \mu_{i,j}(s_{i,j}) \right] $$
Thus, $$ H_Q (\mathcal{X}) = \sum_{i \in V_{\mathcal{T}}} H_{\beta_i}(C_i) - \sum_{(i-j) \in E_{\mathcal{T}}} H_{\mu_{i,j}}(S_{i,j}) $$
In calibrated clique tree, we get marginal consistency for free, however in a loopy graph, running message passing does not necessarily give calibrated beliefs.
Find $ Q = \{ \beta_i : i \in V_{\mathcal{T}} \} \cup \{ \mu_{i,j} : (i-j) \in E_{\mathcal{T}} \} $
Maximizing $ \tilde{F}[\tilde{P}_{\Phi}, Q] $
subject to $$ \mu_{i, j} [s_{i, j}] = \sum_{C_i - S_{i, j}} \beta_i(c_i) \quad \forall (i - j) \in E_T, \forall s_{i, j} \in Val(S_{i, j}) \quad \text{(Marginal consistency)} $$
$$ \sum_{c_i} \beta_i (c_i) = 1 \quad \forall i \in V_T \quad \text{(Normalization)} $$
$$ \beta_i (c_i) \geq 0 \quad \forall i \in V_T, c_i \in Val(C_i) \quad \text{(Non-negativity)} $$
Goal: Maximizing $ \tilde{F}[\tilde{P}_{\Phi}, Q] $ under consistency constraints.
Abt the Non-negativity constraint: Do not need to enforce this explicitly because the assumption that factors are strictly positive implies the beliefs will be nonnegative.
$ \Rightarrow $ Lagrange multiplier
$$ J = \tilde{F}[\tilde{P}_{\Phi}, Q] $$
$$ -\sum_i \lambda_i \left( \sum_{c_i} \beta_i (c_i) - 1 \right) $$
$$ -\sum_i \sum_{j \in Nb_i} \sum_{s_{i, j}} \lambda_{i \to j} [s_{i, j}] \left( \sum_{c_i \sim s_{i, j}} \beta_i (c_i) - \mu_{i, j} [s_{i, j}] \right). $$
Taking derivatives of $ J $ w.r.t
$$ \frac{\partial J}{\partial \beta_i (c_i)} = \ln \psi_i [c_i] - \ln \beta_i (c_i) - 1 - \sum_{j \in Nb_i} \lambda_{i \to j} [s_{i, j}] $$
$$ \frac{\partial J}{\partial \mu_{i, j} [s_{i, j}]} = \ln \mu_{i, j} [s_{i, j}] + 1 + \lambda_{i \to j} [s_{i, j}] + \lambda_{j \to i} [s_{i, j}] $$
$$ \tilde{F}[\tilde{P}_{\Phi}, Q] $$
$$ = \sum_{i \in V_{\mathcal{T}}} E_{C_i \sim \beta_i}[\ln \psi_i] + \sum_{i \in V_{\mathcal{T}}} H_{\beta_i}(C_i) - \sum_{(i-j) \in E_{\mathcal{T}}} H_{\mu_{i,j}}(S_{i,j}) $$
Recall: $ X \sim P \rightarrow E_{X \sim P} [g(X)] = \sum_x P(x) \cdot g(x) $
the factored energy function becomes $$ \tilde{F} = \sum_{i \in V_T} \sum_{c_i} \beta_i (c_i) \ln \psi_i (c_i) - \sum_{i \in V_T} \sum_{c_i} \beta_i (c_i) \ln \beta_i(c_i) + \sum_{(i, j) \in E_T} \sum_{s_{i, j}} \mu_{i, j} (s_{i, j}) \ln \mu_{i, j} (s_{i, j}) $$
$$ \begin{align*} \delta_{i \rightarrow j}[s_{i,j}] &= \frac{\mu_{i,j}[s_{i,j}]}{\delta_{j \rightarrow i}[s_{i,j}]} \\ &= \frac{\sum_{c_i \sim s_{i,j}} \beta_i(c_i)}{\delta_{j \rightarrow i}[s_{i,j}]} \\ &= \exp \left\{ -\lambda_i - 1 + \frac{1}{2} |Nb_i| \right\} \sum_{c_i \sim s_{i,j}} \psi_i(c_i) \prod_{k \in Nb_i - {j}} \delta_{k \rightarrow i}[s_{i,k}]. \end{align*} $$
A set of beliefs $ Q $ is a stationary point of CTree-Optimize iff there exists a set of factors $ \{ \delta_{i \to j}[S_{i, j}] : (i - j) \in E_T \} $ st
$$ \boxed {\delta_{i \to j} \propto \sum_{C_i - S_{i, j}} \psi_i \left( \prod_{k \in Nb_i - \{ j \} } \delta_{k \to i} \right)} \tag{{11.10}} $$
and moreover, $$ \boxed{ \beta_i \propto \psi_i \left( \prod_{j \in Nb_i} \delta_{j \to i} \right) } $$
$$ \boxed{ \mu_{i, j} = \delta_{j \to i} \cdot \delta_{i \to j} } $$
This theorem characterizes the solution of the optimization problem
In chapter 10, we required that cluster graphs
$ \rightarrow $ clique trees.
This chapter, we remove first assumption, allowing inference to be performed on a loopy cluster graph. However, we still wish to require RIP.
Since this is a cluster graph (loopy), we need to explicitly enforce the uniqueness of RIP.
$ \Rightarrow $ With RIP: BP is principled and gives calibrated beliefs.
In trees, RIP implies that $ S_{i, j} = C_i \cap C_j $.
In graphs, this is no longer true (now $ S_{i, j} \subseteq C_i \cap C_j $).
A cluster graph is calibrated if for each edge $ (i - j) $, connecting the cluster $ C_i $ and $ C_j $: $$ \boxed{ \sum_{C_i - S_{i, j}} \beta_i = \sum_{C_j - S_{i, j}} \beta_j } $$
That is, the two clusters agree on the marginal of variables in $ S_{i, j} $.
However, if a calibrated cluster graph satisfies the RIP, then the marginal of a variable $ X $ is identical in all the clusters that contain it.
So $ X \notin C_2 $, during BP, clusters send messages over their shared variables (sepsets), however, there’s no way for information abt $ X $ to be passed bw $ C_1 $ and $ C_3 $
$ \Rightarrow C_1 $ and $ C_3 $ might converge to different marginals for $ X $.
When RIP is satisfied (+ calibrated)
Now all clusters that contain $ X $ have the same marignal distribution for $ X $. $$ \sum_{C_i - \{ X \}} \beta_i = \sum_{C_j - \{ X \}} \beta_j $$
1. Initialize Cluster Graph
2. While graph is not calibrated, repeat
3. Compute $$ \beta_i (C_i) = \psi_i \cdot \prod_{k \in Nb_i} \delta_{k \to i} $$
Similar to bp in clique tree, the convergence point represents a reparameterization of the original distribution.
Theorem 11.4
$ \tilde{P}_\Phi (\mathcal{X}) $
$$ \boxed{ = \frac{\prod_{i \in V_U} \beta_i[C_i]}{\prod_{(i - j) \in E_U} \mu_{i, j}[S_{i, j}]} } $$
where $ \tilde{P}_\Phi (\mathcal{X}) = \prod \phi $ is the unnormalized distribution defined by $ \Phi $.
Recal: $$ \beta_i = \psi_i \prod_{j \in Nb_i} \delta_{j \to i}. $$
$$ \mu_{i, j} = \delta_{j \to i} \delta_{i \to j}. $$
We now have $$ \begin{align*} \frac{\prod_{i \in V_U} \beta_i[C_i]}{\prod_{(i - j) \in E_U} \mu_{i, j}[S_{i, j}]} &= \frac{ \prod_{i \in V_U} \psi_i[C_i] \prod_{j \in Nb_i} \delta_{j \to i} [S_{i, j}] }{ \prod_{(i - j) \in E_U} \delta_{j \to i} [S_{i, j}] \delta_{i \to j} [S_{i, j}] }\\ &= \prod_{i \in V_U} \psi_i [C_i]\\ &= \prod_{\phi \in \Phi} \phi = \tilde{P}_\Phi (\mathcal{X}) \end{align*} $$
From Theorem 10.4, if a set of calibrated beliefs match the marginals on a tree structure, then it also represents the joint distribution correctly. $$ \beta_i (C_i) = P_\Phi (C_i) $$
However,
The idea is to select subtree $ T $ of general cluster graph $ U $ to investigate belief properties.
The selected subtree $ T $ is a subset of clusters and edges that
Example: In the figure, if we remove one of the clusters and its incident ediges, we are left with a proper cluster tree.
Note: RIP is not ncessarily as easy to achieve in general since removing some edges from the cluster graph may result in a graph that violates RIP relative to a variable $ \rightarrow $ need to remove additional edges, and so on.
Once selected a tree $ T $, we can think of it as defining a distribution $$ P_T (\mathcal{X}) = \frac{\prod_{i \in V_T} \beta_i (C_i)}{\prod_{(i-j) \in E_T} \mu_{i, j} [S_{i, j}]} $$
Tree consistency
In English: the beliefs over $ C_i $ in the tree are the marginal of $ P_T $.
whether and when it converges?
Consider Standard sum-product message update rule $$ \delta^\prime_{i \to j} \propto \sum_{C_i - S_{i, j}} \psi_i \cdot \prod_{k \in (Nb_i - \{ j \})} \delta_{k \to i} $$
BP update operator $ G_{BP}: \Delta \mapsto \Delta $
$$ \boxed{ G_{BP} (\{ \delta_{i \to j} \}) = \{ \delta^\prime_{i \to j} \} } $$
A condition that guarantees convergence
An Operator $ G $ over a metric space $ (\Delta, D) $ is an $ \alpha $-contraction relative to the distance function $ D $ if,
for any $ \delta, \delta^\prime \in \Delta $, $$ \boxed{ D(G(\delta); G(\delta^\prime)) \leq \alpha D(\delta, \delta^\prime) } $$
An op is a contraction if its application to two points in the space is guaranteed to decrease the distance bw them by at least some constant $ \alpha < 1 $.
Let $ G $ be an $ \alpha $-contraction of $ (\Delta, D) $. Then there is a unique fixed-point $ \delta^* $ st $$ \boxed{ \lim_{n \to \infty} G^n (\delta) = \delta^* } $$
TODO: Prove this
The contraction rate $ \alpha $ can be used to provide bounds on the rate of convergence of the algorithm to its unique fixed point: To reach a point that is guaranteed to be within $ \epsilon $ of $ \delta^* $, it suffices to apply $ G $ the following number of times: $$ \log_\alpha \frac{\epsilon}{diameter(\Delta)} $$
When selecting a cluster graph, we have to consider trade-offs bw cost and accuracy.
If we are willing to transform our variables, any distribution can be reformulated as a pairwise Markov network.
TODO: Exercise 11.10
Transformation from Markov Network to Cluster Graph
Limitation the Bethe cluster graph: information between different clusters in the top level is passed through univariate marginal distributions $ \rightarrow $ interactions between variables are lost during propagations.