MPE inference using an Incremental Build-Infer-Approximate Paradigm

Bayesian Networks (BN) are directed graphical models that provide a compact representation of joint probability distribution over a set of random variables. An important task in bayesian inference is to find the Most Probable Explanation (MPE) given a set of evidence variables. It involves finding a complete assignment for all non-evidence variables that gives the maximum probability. The probability of the MPE assignment is same as the max-marginal obtained after maximizing the joint distribution over all non-evidence variables. Exact methods include variable elimination and max-product belief propagation on join trees followed by a decoding step to get the MPE assignment and integer linear programming (ILP)  [Koller and Friedman, 2009]. However, MPE inference is known to be an NP-complete problem [Shimony and Charniak, 1990, Park and Darwiche, 2004] and exact methods are not viable in most cases.

One approach to get the MPE assignment is to use search based algorithms that traverse the model’s search space. A commonly used framework for graphical models is the AND/OR search tree [Dechter and Mateescu, 2007]. Several search algorithms have been used to find MPE estimates from these models including depth-first Branch and Bound (AOBB) [Marinescu and Dechter, 2005, Marinescu et al., 2014, 2018], best-first (AOBF) [Marinescu and Dechter, 2007, Marinescu et al., 2020], Breadth-Rotating AND/OR Branch and Bound (BRAOBB) [Otten and Dechter, 2012]. These methods use upper bounds of max-marginals computed using different variants of Mini-Bucket Elimination (MBE) to guide the search. Weighted Mini-Bucket elimination improves the accuracy of the bound of traditional MBE using the Holder’s inequality [Liu and Ihler, 2011]. Another technique to tighten the resulting bound is to use cost-shifting schemes. Two such algorithms are Mini-Bucket Elimination with Moment Matching (MBE-MM) [Flerova et al., 2011] and Join Graph Linear Programming (JGLP) [Ihler et al., 2012]. While MBE-MM uses a single pass of cost-shifting locally within the mini-buckets, JGLP performs cost-shifting updates to the entire mini-bucket join graph iteratively.

Another class of methods are based on LP relaxations. LP relaxations based on message passing include tree re-weighted max-product [Wainwright et al., 2005, Kolmogorov, 2005, Werner, 2007, Jojic et al., 2010, Hazan and Shashua, 2010] and max-product linear programming [Globerson and Jaakkola, 2007, Sontag et al., 2008]. The other class of methods are the dual decomposition solvers [Komodakis et al., 2007, Sontag et al., 2011, 2012, Ping et al., 2015, Martins et al., 2015]. The connection between the solutions obtained using two methods is explored in Bauer et al. [2019]

In this work, we propose a different approach for MPE inference. Our method is based on an Incremental Build-Infer-Approximate paradigm (IBIA) that returns a set of bounded clique size partitions of the BN along with the calibrated forest of of clique trees (CTFs) corresponding to each partition [Bathla and Vasudevan, 2022]. Instead of the sum-product calibration used in Bathla and Vasudevan [2022], we use a max-product calibration along with suitable modifications to the Approximate step. Based on this, we propose a single search algorithm for MPE inference with the following features.

1. 1.

   We show that the max-marginal can be estimated by finding the maximum belief from any clique in the max-calibrated CT of the last partition. Based on experiments, we find that our algorithm gives very good estimates with an average error of $\pm 0.27$ in the log probability over 79 benchmarks for which the exact solution is available.

2. 2.

   We propose a single shot algorithm for decoding the MPE assignment. It is an iterative method in which the subset of variables for which an assignment is obtained is guaranteed to increase in every iteration. There are no issues of convergence. Even though it is a single shot algorithm, we were able to get a non-zero probability assignment with accuracy comparable to AOBB in majority of the testcases.

3. 3.

   Our code is written in Python, with Numpy and NetworkX libraries. The runtimes of our algorithm are very competitive and better in some cases, than the compiled C++ code for AOBB.

A Bayesian network is a directed acyclic graph (DAG), $\mathcal{G}$. Its nodes represent random variables $\mathcal{Y}=\{X_{1},X_{2},\cdots X_{n}\}$ with associated domains $D=\{D_{1},D_{2},\cdots D_{n}\}$. It has directed edges from a subset of nodes $\textrm{Pa}_{X_{i}}=\{X_{k},k\neq i\}$ to $X_{i}$, representing a conditional probability distribution (CPD) $\phi_{i}=P\{X_{i}|\textrm{Pa}_{X_{i}}\}$. The BN represents the joint probability distribution (JPD) of $\mathcal{Y}$, given by $P(\mathcal{Y})=\prod_{i=1}^{n}\phi_{i}$. Let $E$ denote the set of instantiated or evidence variables, with $\mathcal{Y}=\{\mathcal{X},E\}$. The task is to find the most probable explanation (MPE), defined as

In low treewidth networks, MPE can be obtained using the clique tree (CT) representation, which is a derived undirected graphical model obtained after moralization and chordal completion of the BN. The CT, which is also called the join tree or junction tree, is a hypertree with nodes $\{C_{1},C_{2},\cdots,C_{n}\}$ that are the set of maximal cliques in the chordal graph. An edge between $C_{i}$ and $C_{j}$ is associated with a sepset $S_{i,j}=C_{i}\cap C_{j}$. Each factor $\phi_{i}$ is associated with a single clique $C_{i}$ such that $\textrm{Scope}(\phi_{i})\subseteq\mathcal{C}_{i}$. The task of computing MPE is split into two parts. First, the max-product belief propagation (BP) algorithm [Chapter 10 of Koller and Friedman, 2009] is used to compute the maximum marginal probability, $MaxMarg$, defined as

This algorithm has two rounds of message passing along the edges of the CT, an upward pass (from the leaf nodes to the root node) and a downward pass (from the root node to the leaves). The CT obtained as a result of this algorithm is max-calibrated, which is defined as follows. Let $\beta(C_{i})$, $\beta(C_{j})$ denote the beliefs associated with adjacent cliques $C_{i}$ and $C_{j}$ and $\mu_{ij}$, the belief of the corresponding $S_{ij}$. The CT is said to be max-calibrated if all pairs of adjacent cliques satisfy the following.

The $MaxMarg$ can be simply obtained by finding the maximum clique belief in any clique $C$ in the max-calibrated CT since,

Since a network could have disjoint DAGs, we use the term Clique Tree Forest (CTF) to denote the collection of corresponding CTs. The max-marginal for a BN with multiple DAGs is the product of max-marginals of all CTs $\in CTF$.

Once $MaxMarg$ is computed, the decode step finds an MPE assignment using the max-calibrated CTF. Algorithm 1 has the traceback procedure. Set $S_{u}$ tracks the set of unassigned variables. For each CT in the CTF, any clique can be chosen as the root node ($C_{root}$). To start with all variables in the root clique are unassigned. Since the global MPE assignment also satisfies the local optimality property [Koller and Friedman, 2009], a partial assignment can be obtained by finding the argmax of the clique belief. The overall MPE assignment is updated and all assigned variables are removed from set $S_{u}$. All other cliques are iterated through in a pre-order traversal. For any clique $C$, the state of the variables on the sep-sets with the preceding cliques are known. After reducing belief $\beta(C)$ over the known variable states, we find an assignment of the unassigned variables that maximizes the reduced clique belief.

The IBIA framework has been used to infer the partition function and the prior and posterior marginal probabilities of non-evidence variables in Bathla and Vasudevan [2022]. We have modified this framework for MPE queries. We use an iterative procedure that has the build, infer and approximate steps and a partial decode step that gives an MPE assignment for a subset of variables. In each iteration, the subset for which an assignment is obtained is extended. The iteration is continued until either all variables are assigned or an assignment is not possible. In the following sections, each of the steps are explained in more detail.

Step 1: Incremental Build: The CTF can be built incrementally using either of the algorithms detailed in Flores, Gámez, and Olesen [2002], Bathla and Vasudevan [2022]. We use the approach described in Bathla and Vasudevan [2022] since it works directly with the clique tree model and eliminates the need for computation of any other intermediate representation. Typically, it chooses a smaller graph chosen for re-triangulation than Flores et al. [2002].

Step 2: Inference: We use the two-pass Max-product Belief Propagation algorithm to calibrate the partition CTF. After calibration, all cliques in a CT will have the same maximum probability, and the beliefs of adjacent clique beliefs agree over the common variables [Koller and Friedman, 2009].

Step 3: Approximation:

As discussed, the nodes present in the CTF corresponding to a partition can divided into two sets: interface (IV) and non-interface nodes (NIV). The interface nodes are parents of the variables that have not yet been added. Therefore, these are required for building the next partition. We adopt a similar approximation methodology as suggested in Bathla and Vasudevan [2022] to reduce the clique sizes. We also denote the calibrated tree obtained after BP as $CTF_{in}$ and the approximated CTF as $CTF_{a}$. The minimal subgraph of $CTF_{in}$ that connects the interface variables forms the initial $CTF_{a}$. This graph may also contain some non-interface variables. We use a combination of exact and local max-marginalization to reduce the clique sizes to a preset bound $mcs_{im}$. We now discuss both these steps in detail.

1. 1.

   Exact max-marginalization: If a non-interface variable $n$ is present in a single clique, it is simply removed from the clique scope and the belief is modified as: $\beta(C^{{}^{\prime}})=\max\limits_{n.states}\beta(C)$ where, $C^{\prime}=C\setminus n$. On the other hand, if $n$ is present in multiple cliques, the subtree over all containing cliques ($ST_{n}$) is collapsed into a single clique ($C_{c}$). Figure 2(a) shows an example. Cliques $C_{1},C_{2}$ containing $n$ are collapsed to form clique $C_{c}$. Since this step could potentially result in a large clique, this is only performed if the size of the resultant clique $\leq mcs_{im}$. The belief of collapsed clique is computed as shown below.

   $$\beta(C_{c})=\max_{n.states}\left(\frac{\prod_{C\in{ST_{n}}}\beta(C)}{\prod_{SP\in{ST_{n}}}\mu(SP)}\right)$$

   where, $SP$ denotes the sepsets in $ST_{n}$.
   This step preserves the joint beliefs i.e. variables in $CTF_{a}$ have the same belief as in $CTF_{in}$.

2. 2.

   Local max-marginalization: In this step, variables present in cliques with size $>mcs_{im}$ are max-marginalized from individual cliques while ensuring (a) All CTs $\in CTF_{a}$ are valid CTs. (b) A connected CT $\in CTF_{in}$ remains connected in $CTF_{a}$.

   Let, $n$ be a variable present in large cliques. The subgraph of $CTF_{in}$ over all cliques containing $n$ is a connected tree since the input CTF is valid. To ensure that the Running Intersection Property (RIP) [Koller and Friedman, 2009] is satisfied after approximation, $n$ is retained in a connected subtree containing smaller cliques with sizes $\leq mcs_{im}$. It is individually max-marginalized out from all other cliques. Figure 2(b) shows an example where variable $n$ is removed from cliques $C_{1},C_{2}$ and retained in cliques $C_{3},C_{4}$. Local marginalization of $n$ from cliques $C_{i}$ and $C_{j}$, and the corresponding sepset $S_{i,j}$ results in cliques $C_{i}^{\prime}=C_{i}\setminus n$ and $C_{j}^{\prime}=C_{j}\setminus n$ with sepset $S_{i,j}^{\prime}=S_{i,j}\setminus n$. The corresponding beliefs are $\beta(C_{i}^{\prime})=\max\limits_{n.states}\beta(C_{i})$, $\beta(C_{j}^{\prime})=\max\limits_{n.states}\beta(C_{j})$, $\mu(S_{i,j}^{\prime})=\max\limits_{n.states}\mu(S_{i,j})$. While updating the beliefs in this manner preserves the joint beliefs for variables present within the clique, the joint beliefs of variables present in disjoint cliques are approximated.

Once the clique sizes are reduced, we re-assign the clique factors based on calibrated clique and sep-set beliefs.

We discuss the proofs for Propositions 1,  2 in Section 6.

Algorithm 2 shows the overall algorithm. At all points in the method, we remove any non-maximal cliques if generated and re-connect their neighbors. We start by identifying the set of interface and non-interface variables present in $CTF_{in}$. We initialize $CTF_{a}$ as the minimal subgraph of $CTF_{in}$ that connects the interface variables. We first attempt to reduce clique sizes using exact max-marginalization of non-interface variables. NIVs present in a single clique are removed, and the corresponding clique beliefs are max-marginalized. If any resultant clique is non-maximal, it is removed, and the neighbors are re-connected. Wherever possible within the clique size constraints, NIVs present in multiple cliques are max-marginalized after collapsing the cliques (lines 4-7).

Next, we find the set of large-sized cliques ($L_{c}$) with size $>mcs_{im}$. All variables in these cliques are grouped into NIVs and IVs and stored in $N$. We first try to locally max-marginalize non-interface variables. This is done as follows. First, both sets of variables are individually sorted in the increasing order of the number of containing cliques. Starting with NIVs, we pop a variable ($n$) from this list and identify the subgraph of $CTF_{a}$ over cliques containing this variable ($ST_{n}$). Since the input CTF satisfies RIP, $ST_{n}$ is a connected tree. $ST_{n}$ can be further divided into disjoint subtrees over cliques with size $\leq mcs_{im}$. We choose the largest subtree ($ST_{r}$) and retain the variable $n$ in all cliques in this subtree (lines 13-15). Since we want a connected CT to remain connected, the variable is removed only if no sepset size becomes zero (lines 15-18).

If the clique sizes remain above $mcs_{im}$ after processing NIVs, we start with the IVs. If $n$ is an IV, it must be retained in atleast one clique. Therefore, we ignore interface variables that are only present in large cliques (lines 19-20). Otherwise, we max-marginalize all clique and sep-set beliefs associated with the cliques that are not present in $ST_{r}$. The list $L_{c}$ is updated by removing cliques where the size is now within the preset limit. This process is repeated until either clique list $L_{c}$ or the variable set $N$ becomes empty.

Once clique-sizes are reduced, we reassign the clique factors (lines 26-27). For each clique tree in $CTF_{a}$, we pick a root node and perform a pre-order traversal from the root node to all other nodes in the CT. The factor associated with the root node is the corresponding clique belief. For all other nodes, the factor for an unvisited neighbor $C_{j}$ of clique $C_{i}$ is assigned as $\beta(C_{j})=\frac{\beta(C_{i})}{\mu(S_{ij})}$.

Step 4: Decode: The assignment of variables in the last partition is used as the partial assignment of MPE. This assignment is obtained from the last partition CT using Algorithm 1.

All experiments presented here were carried out on 3.7-GHz Intel i7-8700 Linux system with 64-GB memory. A time limit of one hour was set for each simulation. For comparison, we use methods Weighted Mini-Bucket (WMB) [Liu and Ihler, 2011], Join Graph Linear Programming (JGLP) [Ihler et al., 2012] from the Merlin library and the AND/OR Branch-and-Bound (AOBB) [Dechter and Mateescu, 2007, Marinescu and Dechter, 2009] method from the Daoopt library. The source codes for both libraries written in C++ are publicly available [Marinescu, 2016, Otten, 2010]. Our code has been implemented in Python3 with NetworkX and NumPy libraries. All methods reduce the BN based on inherent determinism and local structure. For a fair comparison, we also simplify the BN based on known evidence states and determinism present in CPDs. We evaluate our approach on three datasets, namely, $Pedigree$, $BN$, $Grid\mbox{-}BN$ Ihler [2006], Dechter [2006] included in the Probabilistic Inference Challenge [Elidan, 2011] and several UAI approximate inference challenges. We evaluated all instances available in each dataset and ignored ones that had a single partition. We use solutions provided by  Ihler [2006] as the exact MPE solution ($X^{*}_{Exact}$).

We denote the MPE assignment obtained using an approximate inference algorithm as $X^{*}_{Alg}$. The probability of a complete assignment is simply the product of the CPDs reduced over the given state. For instances where exact solutions are available, we measure the error in the estimated max-marginals and the probability of the MPE assignment and denote it as,

The runtime parameters used for various codes were as follows. We set $mcs_{p}=20$ and $mcs_{im}=15$ in our code, as a trade-off between run time and accuracy. However, $mcs_{im}$ is soft constraint and its value is decremented until the network can be partitioned successfully. For WMB, JGLP and AOBB, we tried an $ibound$ of 10 and 20. Solutions for larger number of testcases were obtained for WMB with $ibound=20$ and for AOBB with $ibound=10$. Therefore, we used $ibound=20$ for WMB and JGLP. and $ibound=10$ for AOBB. For AOBB, we used the Mini-Bucket Elimination with Moment Matching (MBE-MM) heuristic [Flerova et al., 2011] to estimate bounds and enabled the use of the stochastic greedy ordering scheme.

Table 1 shows a detailed comparison of the error in MPE assignments ($\Delta_{MPE}$) and the required runtime for different inference methods for a subset of benchmarks. The results for others are similar. For each testcase, the table also shows the maximum number of partitions and the number of iterations required to obtain a complete MPE assignment with IBIA. We check for accuracy of log probabilities upto two decimal places and report errors $<0.01$ as 0. Testcases for which solutions obtained by all methods were close to the optimal solution are not tabulated here in the interest of space. We divide testcases into two categories based on the results. For benchmarks in Category \@slowromancapi@, all methods achieve a non-zero probability solution. IBIA gives close to optimal solutions for most of the benchmarks in this category. Category \@slowromancapii@ shows testcases where IBIA and AOBB give solutions, but either WMB or JGLP fails. IBIA achieves good estimates in most testcases. For testcases $BN\_74,\leavevmode\nobreak\ pedigree7,\leavevmode\nobreak\ pedigree51$, while IBIA achieves close to the optimal solution in $<11$ seconds, AOBB performs repeated search operations until the timeout constraint is reached. While the error obtained with IBIA is $>1$ in five testcases, in four out of five of these testcases, AOBB also performs repeated search until timeout. IBIA performs better than JGLP in all cases except $pedigree33$. For testcases $pedigree40$ and $pedigree51$, IBIA provides a higher probability solution than other methods.

In Table 2, we compare the logarithm of the MPE probabilities obtained with the different methods for benchmarks where the exact solution is not available. We ignore cases where IBIA, AOBB, and WMB/JGLP give a common solution while tabulation. For testcases in the first category in Table 2, IBIA gives the same solution as AOBB in $<5$ seconds. The estimate obtained in all these cases is better than both WMB and JGLP. For networks in the second category, IBIA performs better than all other methods. While AOBB achieves some non-zero solution in testcases $BN\_70$ and $BN\_73$, the solution obtained with IBIA has a higher probability than the AOBB solution, with the difference being around 10. In all other cases, IBIA is able to find a possible MPE assignment with non-zero probability while all other methods obtain a zero-probability solution within the set time limit.

Since IBIA is written in Python and available tools are written in C++, the runtimes reported here are not directly comparable. That said, the runtime for IBIA is an order of magnitude lower than JGLP and WMB in most cases. They are also better than AOBB in many cases. This is expected since IBIA does not search for solutions. A single partial assignment is obtained in each iteration.

Table 3 summarizes the total number of instances that require multiple partitions and the number of instances that provide non-zero probability assignments within 1hr for different benchmarks. Out of 117 networks, IBIA provides solutions in 100 testcases which is better than JGLP and WMB, but slightly lower than 108 cases solved by AOBB.

The approximate CT obtained after local max-marginalization depends on the choice of variables that are removed to reduce the clique size. For the results in Tables 1 and2, we prioritize variables present in the least number of cliques. A random assignment is chosen in case of ties. The CTF obtained after approximation will be different if a different set of variables is chosen for removal. We tried three other orderings without any prioritization. Although the change in $MaxMarg$ was not much in most cases, there were significant changes in the MPE. The results for the benchmarks where an improvement was obtained are shown in Table 4, which has the best solution obtained. This gives rise to the possibility of searching for a solution over the approximation space. An advantage of this is that the approximation instances are independent of each other and can be run in parallel.

To evaluate the quality of the estimate of max-marginal obtained with our method, we compare it with the final upper bounds achieved with JGLP, WMB, and MBE-MM. Figure 3 shows the histogram of error in estimates obtained with different methods. We observe that the error with IBIA is within $\pm 1$ in 70 instances out of 79 cases. However, the upper bound with all other methods is in this range in slightly more than 40 testcases. The average error in the estimate of max-marginal obtained with IBIA is 0.27 as opposed to 1.12, 1.23, 2.17 for the upper bounds estimated using existing metrics WMB, JGLP, and MBE-MM. Though the estimate of max-marginal obtained with IBIA is not necessarily an upper bound, it provides good estimates when compared to the existing heuristics. Therefore, this method can be used for quick evaluation of different partial assignments in search algorithms like Branch and Bound.

We propose a single-shot algorithm for MPE inference based on an Incremental Build-Infer-Approximate paradigm. It is an iterative method in which the subset of variables for which an assignment is obtained is guaranteed to increase in every iteration. In majority of cases, the number of iterations required is $<5$. Even though it is a single shot algorithm, it gives valid assignments in 100 out of 117 testcases. In majority of the testcases, the accuracy is comparable to the branch and bound based technique AOBB. Overall the runtimes are competitive, with significantly lower runtimes than AOBB in several cases. We also show that our method achieves better estimates of the max-marginals when compared to the upper bounds obtained with several mini-bucket methods. Therefore, this approach can possibly be used in search algorithms like Branch and Bound for quick evaluation of different partial assignments. We show some initial experiments to improve the accuracy of the approach by using different heuristics for approximation.

We obtain zero probability solutions in 14 out of a total of 117 benchmarks, calling for a more systematic search over the approximation space. In many of these cases, there were multiple partial assignments, and we chose one of them randomly. A search over these could also possibly give better solutions.

In the following, we use the terms $CTF_{in}$ and $CTF_{a}$ to denote the input and output CTF of Algorithm 2. The line numbers indicated here refer to line numbers of Algorithm 2.

Proof for Proposition 1 $CTF_{a}$ is initialized as the subgraph of $CTF_{in}$ which is valid and max-calibrated (line 2). Each CT $\in CTF_{a}$ obtained after the subsequent steps is valid because of the following reasons.

• •

  It contains only maximal cliques since any non-maximal cliques generated while simplification of $CTF_{a}$ are removed (lines 6,22).

• •

  It contains disjoint trees. This is because neither of exact and local max-marginalization introduce any loops. In the exact max-marginalization step, neighbors of the collapsed and non-maximal cliques are reconnected to $CTF_{a}$, which means that the tree structure of the CT is preserved. In the local max-marginalization step, variables are removed only if no sepset size becomes zero, ensuring that a connected CT remains a connected tree (lines 15-18).

• •

  It satisfies the running intersection property (RIP) [Koller and Friedman, 2009]. This is because

  • –

    During exact max-marginalization, sepsets in the $CTF_{a}$ are preserved while re-connecting the neighbors of the collapsed cliques to the new clique, thereby ensuring that RIP is satisfied. Similarly, since neighbors of non-maximal cliques which are removed are connected to the containing cliques, sepsets are preserved.

  • –

    During local max-marginalization, variables are retained in a single connected component of $CTF_{a}$ (line 14). Therefore, the subgraph of $CTF_{a}$ over any net is connected.

• •

  The re-assignment of factors results in a valid distribution.
  Proof: After exact max-marginalization, all the clique and sepset beliefs are preserved. Therefore, the resultant clique is also calibrated. Let $C_{i}$ and $C_{j}$ be two adjacent cliques in $CTF_{in}$ with sepset $S_{i,j}$. After local max-marginalization of a node $n$, we get the corresponding cliques $C_{i}^{\prime},C_{j}^{\prime}\in CTF_{a}$, with sepset $S_{i,j}^{\prime}$. Since the result is invariant with respect to the order in which variables are maximized over, we have

  	$\displaystyle\max_{{C_{i}}^{\prime}\setminus{S_{i,j}}^{\prime}}\beta(C_{i}^{\prime})$	$\displaystyle=\max_{{C_{i}}^{\prime}\setminus{S_{i,j}}^{\prime}}\max_{n.states}\beta(C_{i})$
  		$\displaystyle=\max_{n.states}\max_{{C_{i}}^{\prime}\setminus{S_{i,j}}^{\prime}}\beta(C_{i})$
  		$\displaystyle=\max_{n.states}\mu(S_{i,j})=\mu(S_{i,j}^{\prime})$

  where $n.states$ denotes the states of $n$. Similarly, $\max_{{C_{j}}^{\prime}\setminus{S_{i,j}}^{\prime}}\beta(C_{j}^{\prime})=\mu(S_{i,j}^{\prime})$. Since this is true for all pairs of adjacent cliques, $CTF_{a}$ is also max-calibrated. Therefore, since re-parameterization is performed using calibrated clique and sepset beliefs, it results in a valid distribution.

Proof for Proposition 2 $CTF_{a}$ is obtained from $CTF_{in}$, which is calibrated. Therefore, all cliques in a CT have the same maximum belief. After exact max-marginalization, the clique beliefs in $CTF_{a}$ are identical to the beliefs in $CTF_{in}$, since the step involves collapsing all containing cliques before max-marginalization of beliefs. Both exact and local max-marginalizations involve maximizing clique beliefs over all states of variable. Thus, the the maximum belief and the within clique beliefs remain unaltered.