  Exact computation of the partition function is known to be intractable,
necessitating approximate inference techniques. Existing methods for
approximate inference are slow to converge for many benchmarks. The control of
accuracy-complexity trade-off is also non-trivial in many of these methods. We
propose a novel incremental build-infer-approximate (IBIA) framework for
approximate inference that addresses these issues. In this framework, the
probabilistic graphical model is converted into a sequence of clique tree
forests (SCTF) with bounded clique sizes. We show that the SCTF can be used to
efficiently compute the partition function. We propose two new algorithms which
are used to construct the SCTF and prove the correctness of both. The first is
an algorithm for incremental construction of CTFs that is guaranteed to give a
valid CTF with bounded clique sizes and the second is an approximation
algorithm that takes a calibrated CTF as input and yields a valid and
calibrated CTF with reduced clique sizes as the output. We have evaluated our
method using several benchmark sets from recent UAI competitions and our
results show good accuracies with competitive runtimes.
