@article {212, title = {An analysis of the impact of Kikuchi approximations}, year = {2016}, abstract = {

Factorizations of probabilistic distributions serve as condensed and efficient representations for modeling problems with uncertainty.
In probabilistic graphical models, it is generally assumed that factorizations are consistent with a graphical structure which simplifies the probabilistic structure by exploiting the conditional independences present in the distribution. In this work we focus con Markov networks, a subtype of graphical models where the graphical structure is an undirected graph, and the factorization is characterized over the maximal cliques of the graph, according with the well-known Hammersley-Clifford Theorem. \ When using that factorization, factors may correspond to the maximal cliques and overlappings of a junction tree. The semantics of a junction tree guarantees that if marginals are consistent, whatever the accuracy of the approximation, the factorization will produce a valid probability distribution (e.g. the sum of the values associated by the factorization to all possible states of the system will add to $1$). However, the number of junction trees, and thus the number of (consistent) factorizations that can be obtained from them is relatively small in comparison with all possible products of marginal distributions, including those not necessarily producing valid factorizations.
\ In this work we investigate, from different perspectives, the quality of marginal factorizations as approximations of probability distributions.\ 
\ In particular, our analysis is focused on the Clique-based Kikuchi approximations (CBKA), a particular type of factorization in probability marginals. In this type of factorization, the marginals are completely determined by the independence graph.\ 
\ Our general goal is to identify whether, and under which conditions, the CBKA can produce accurate or acceptable approximations of an original probability distribution.\ 
\ We show that the class of CBKA includes a much larger set of approximations than those derived from junction trees (or equivalently, chordal graphs).\ 
\ Additionally, we show that the quality of CBKA can be measured by using the Kendall tau rank distance, a measure which considers scenarios where the values produced by the factorizations are mainly relevant to compare or rank the configurations of the system. We analyzed the quality of CBKA in terms of the Kendall distance and also in terms of the Kullback-Liebler divergence, and show that both measures are correlated. Our current results show that such correlation depends on the structure of the underlying distribution, and also on the strength of the dependences, e.g., the hyper-parameters of Dirichlet for synthetic distributions.\ 

}, author = {Federico Schl{\"u}ter and Roberto Santana Hermida and Jos{\'e} Antonio Lozano} }