complexity, which is crucial if large numbers of queries have to be evaluated, e.g., in the context of parameter learning. [@Gutmann08] therefore introduces the $k$-probability $P_k(q|T)$, which approximates the success probability by using the $k$-best (that is, the $k$ most likely) explanations instead of all proofs when building the DNF formula used in Equation (\[eq:dnf\]): $$P_k(q|T)  = P\left( \bigvee_{e \in E_k(q) } \, \bigwedge_{b_i \in var(e)} b_i \right)\label{eq:p_k}$$ where $E_k(q)=\{e \in E(q)|P_x(e)\geq P_x(e_k)\}$ with $e_k$ the $k$th element of $E(q)$ sorted by non-increasing probability. Setting $k=\infty$ leads to the success probability, whereas $k=1$ corresponds to the explanation probability provided that there is a single best proof. The branch-and-bound approach used to calculate the explanation probability can directly be generalized to finding the $k$-best proofs; cf. also [@Poole:93].

To illustrate $k$-probability, we consider again our example graph, but this time with query *path$(a,d)$*. This query has four proofs, represented by the conjunctions $ac\wedge cd$, $ab\wedge bc \wedge
cd$, $ac\wedge ce \wedge ed$ and $ab\wedge bc \wedge ce \wedge ed$, with probabilities $0\ldotp72$, $0\ldotp378$, $0\ldotp32$ and $0\ldotp168$ respectively. As $P_1$ corresponds to the explanation probability $P_x$, we obtain $P_1(path(a,d))=0\ldotp72$. For $k=2$, the overlap between the best two proofs has to be taken 