Learning Bayesian Networks with Non-Decomposable Scores

Abstract

Modern approaches for optimally learning Bayesian network structures require decomposable scores. Such approaches include those based on dynamic programming and heuristic search methods. These approaches operate in a search space called the order graph, which has been investigated extensively in recent years. In this paper, we break from this tradition, and show that one can effectively learn structures using non-decomposable scores by exploring a more complex search space that leverages state-of-the-art learning systems based on order graphs. We show how the new search space can be used to learn with priors that are not structure-modular (a particular class of non-decomposable scores). We also show that it can be used to efficiently enumerate the $k$-best structures, in time that can be up to three orders of magnitude faster, compared to existing approaches.

A Proofs for Sect. 4.2

Proof

(Theorem 1 ). The total cost of a path from the root $G_0$ to a leaf $G_n$ is:

$$\begin{aligned}&\sum _{G_i \rightarrow G_j} \mathsf {score}(X_j\mathbf{U}_j \mid \mathcal {D}) - \log \frac{{ Pr}_j(G_j)}{{ Pr}_i(G_i)}\\&=\sum _{G_i \rightarrow G_j} \mathsf {score}(X_j\mathbf{U}_j \mid \mathcal {D}) - \log { Pr}_j(G_j) + \log { Pr}_i(G_i)\\&= \mathsf {score}(X_1 \mathbf{U}_1 \mid \mathcal {D}) - \log { Pr}_1(G_1) + \log { Pr}_0(G_0) {} \\&\quad + \mathsf {score}(X_2\mathbf{U}_2 \mid \mathcal {D}) - \log { Pr}_2(G_2) + \log { Pr}_1(G_1) + \ldots {} \\&\quad + \mathsf {score}(X_n\mathbf{U}_n \mid \mathcal {D}) - \log { Pr}_{n}(G_{n}) + \log { Pr}_{n-1}(G_{n-1})\\&= \mathsf {score}(G \mid \mathcal {D}) - \log { Pr}_n(G_n) \end{aligned}$$

as desired.    $\square$

Proof

(Theorem 2 ).

$$\begin{aligned} h(G_i)&= \min _{G_n: G_i \leadsto G_n} \sum _{X\mathbf{U}\in G_n - G_i} \mathsf {score}(X\mathbf{U}\mid \mathcal {D}) + \min _{G_n: G_i \leadsto G_n} - \log \frac{{ Pr}_n(G_n)}{{ Pr}_i(G_i)}\\&\le \min _{G_n: G_i \leadsto G_n} \Big ( \sum _{X\mathbf{U}\in G_n - G_i} \mathsf {score}(X\mathbf{U}\mid \mathcal {D}) - \log \frac{{ Pr}_n(G_n)}{{ Pr}_i(G_i)} \Big )\\&= \min _{G_n: G_i \leadsto G_n} g(G_n) - g(G_i) \end{aligned}$$

Since heuristic function h lower-bounds the true cost of to a goal node, it is admissible.    $\square$

Below we consider the correctness of Algorithm 1.

Lemma 1

In Algorithm 1:

• 1. all $G_i$ that generate $G_{i + 1}$ are extracted from H before $G_{i + 1}$ is extracted;

• 2. when $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ is extracted from H,

  $$\begin{aligned} f_{i + 1} = \mathsf {score}(G_{i + 1} | \mathcal {D}) - \log \#G_{i + 1} + h(G_{i + 1}), \end{aligned}$$

  and $l_{i + 1}$ is the number of linear extensions of $G_{i + 1}$, i.e., $\#G_{i+1}$.

where $h(G_i) = h_1(G_i) - \sum _{j=i+1}^n \log j$.

Proof

Consider a minimum item $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ extracted from H. Below we show by induction that (1) all $G_i$ such that $G_i$ generates $G_{i + 1}$ are extracted from H before $G_{i + 1}$ (2) $f_{i + 1} = \mathsf {score}(G_{i + 1} | \mathcal {D}) - \log \#G_{i + 1} + h(G_{i + 1})$, and $l_{i + 1}$ is the number of linear extensions of $G_{i + 1}$, which is also the number of paths from $G_0$ to $G_{i + 1}$.

For $i = 0$, clearly (1) and (2) are true. Assume (1) and (2) are true for all $(G_i, f_i, l_i)$. Then when $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ is extracted, $l_{i + 1}$ is the number of paths from $G_0$ to $G_{i + 1}$ that pass the $G_i$ extracted from H before $G_{i + 1}$. To see this, note that l is the number of path from $G_0$ to $G_i$. Moreover, since $l_{i + 1}$ is the number paths from $G_0$ to $G_{i + 1}$ that pass the $G_i$ extracted from H before $G_{i + 1}$, when $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ is in H,

$$\begin{aligned} f_{i + 1} = \mathsf {score}(G_{i + 1} | \mathcal {D}) - \log \sum _{G_i \prec G_{i + 1}} N(G_0 \rightarrow \ldots \rightarrow G_i \rightarrow G_{i + 1}) + h (G_{i + 1}), \end{aligned}$$

where $G_i \prec G_{i + 1}$ denotes that $G_i$ is extracted before $G_{i + 1}$, and $N(G_0 \rightarrow \ldots \rightarrow G_i \rightarrow G_{i + 1})$ denotes the number of paths $G_0 \rightarrow \ldots \rightarrow G_i \rightarrow G_{i + 1}$. Note that $f_{i + 1}$ decreases as more $G_i$ are extracted.

Consider when $(G_i, f_i, l_i)$ and $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ are both in H. Below we show that all $G_i$ that generates $G_{i + 1}$ are extracted from H before $G_{i + 1}$. Consider

$$\begin{aligned} f_i&= \mathsf {score}(G_i | \mathcal {D}) \\&\quad - \log \sum _{G_{i - 1} \prec G_i} N(G_0 \rightarrow \ldots \rightarrow G_{i - 1} \rightarrow G_i) + h_1(G_i) - \sum _{j = i + 1}^n \log j\\ f_{i + 1}&= \mathsf {score}(G_{i + 1} | \mathcal {D}) \\&\quad - \log \sum _{G^\prime _i \prec G_{i + 1}} N(G_0 \rightarrow \ldots \rightarrow G^\prime _i \rightarrow G_{i + 1})+ h_1 (G_{i + 1}) - \sum _{j = i + 2}^n \log j\\ \end{aligned}$$

We simply need to show $f_{i + 1} > f_i$. Since $h_1$ is a consistent heuristic function for learning with $\mathsf {score}$, $\mathsf {score}(G_{i + 1} | \mathcal {D}) + h_1(G_{i + 1}) \ge \mathsf {score}(G_i | \mathcal {D}) + h_1 (G_i)$. Then we only need to show

$$\begin{aligned}&(i + 1) \sum _{G_{i - 1} \prec G_i} N(G_0 \rightarrow \ldots \rightarrow G_{i - 1} \rightarrow G_i) \\&> \sum _{G^\prime _i \prec G_{i + 1}} N(G_0 \rightarrow \ldots \rightarrow G^\prime _i \rightarrow G_{i + 1}) \end{aligned}$$

First, for any pair of DAGs $G_i$ and $G^\prime _i$ that can generate a DAG $G_{i+1}$, there exists a unique DAG $G_{i-1}$ that can generate both $G_i$ and $G^\prime _i$. For each $G^\prime _i$ on the right-hand side, there thus exists a corresponding (and unique) $G_{i-1}$ on the left-hand side that can generate both $G^\prime _i$ and $G_i$. Further, since $G^\prime _i$ was expanded, $G_{i-1}$ must also have been expanded (by induction). For each such $G_{i-1}$, if $G^\prime _i$ has a linear extension count of $L$, then $G_{i-1}$ must have at least a linear extension count of $L/i$, and hence the corresponding $N(G_0 \rightarrow \ldots \rightarrow G_{i-1} \rightarrow G_i)$ is at least $L/i$. On the left-hand side, we the corresponding term is thus at least $(i+1)\cdot L/i > L$. Since this holds for each element of the summation on the right-hand side, the above inequality holds.

Since all $G_i$ that generates $G_{i + 1}$ are extracted from H before $G_{i + 1}$, as a result, $f_{i + 1} = \mathsf {score}(G_{i + 1} | \mathcal {D}) - \log \#G_{i + 1} + h(G_{i + 1})$, and $l_{i + 1}$ is the number of all paths from $G_0$ to $G_{i + 1}$.

Proof

(of Theorem 4 ). To see the correctness of the algorithm, simply note that by Lemma 1, when $(G_{i + 1}, f_{i + 1}, l_{i + 1})$ is extracted from H, i.e. the open list, $f_{i + 1} = f(G_{i + 1})$.

Proof

(of Theorem 3 ). By Lemma 1, Algorithm 1 can count the number of linear extensions.