The Exploring Process and the Evaluation of Candidate Structures

The search method we have described may be applied in combination with any score equivalent function $g$ (for example the AIC, BIC, MDL and BDe scoring functions are score equivalent). An easy (but inefficient) way to integrate our search method with a score equivalent function would be as follows: given an RPDAG $G$ to be evaluated, select any extension $H$ of $G$ and compute $g(H:D)$. We could also use other (non-equivalent) scoring functions, although the score of $G$ would depend on the selected extension.

However, let us consider the case of a decomposable scoring function $g$: the DAG obtained by adding or removing an arc from the current DAG $H$ can be evaluated by modifying only one local score:

$$g(H\cup\{x\rightarrow y\}:D)=g(H:D)-g_D(y, Pa_H(y))+g_D(y, Pa_H(y)\cup\{x\})$$

$$g(H\setminus\{x\rightarrow y\}:D)=g(H:D)-g_D(y, Pa_H(y))+g_D(y, Pa_H(y)\setminus\{x\})$$

Using decomposable scoring functions, the process of selecting, given an RPDAG, a representative DAG and then evaluating it may be quite inefficient, since we would have to recompute the local scores for all the nodes instead of only one local score. This fact can make a learning algorithm that searches in the space of equivalence classes of DAGs considerably slower than an algorithm that searches in the space of DAGs (this is the case of the algorithm proposed by [16]).

Our search method can be used for decomposable scoring functions so that: (1) it is not necessary to transform the RPDAG into a DAG, the RPDAG can be evaluated directly, and (2) the score of any neighboring RPDAG can be obtained by computing at most two local scores. All the advantages of the search methods on the space of DAGs are therefore retained, but a more reduced and robust search space is used.

Before these assertions are proved, let us examine an example. Consider the RPDAG $G$ in Figure 15 and the three neighboring configurations produced by the inclusion of an edge between $x$ and $y$, $G_1$, $G_2$ and $G_3$ (also displayed in Figure 15).

Figure 15: An RPDAG $G$ and three neighboring configurations $G_1$, $G_2$ and $G_3$

The score of each of these RPDAGs is equal to the score of any of their extensions. Figure 16 displays one extension for each neighboring configuration.

Figure 16: Extensions $H_1$, $H_2$ and $H_3$ of the RPDAGs $G_1$, $G_2$ and $G_3$ in Fig. 15

We can therefore write:

$$g(G_1:D)=g(H_1:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,y)+g_D(y,x)+g_D(d,y)$$

$$g(G_2:D)= g(H_2:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,y)+g_D(y,\{xd\})+g_D(d,\emptyset)$$

$$g(G_3:D)= g(H_3:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,\emptyset)+g_D(y,\{xc\})+g_D(d,y)$$

For each extension $H_i$ of any neighboring configuration $G_i$, it is always possible to find an extension $H_{Gi}$ of the current RPDAG $G$ such that the scores of $H_i$ and $H_{Gi}$ only differ in one local score (Figure 17 displays these extensions). We can then write:

$$g(G:D)=g(H_{G1}:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,y)+g_D(y,\emptyset)+g_D(d,y)$$

$$g(G:D)=g(H_{G2}:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,y)+g_D(y,d)+g_D(d,\emptyset)$$

$$g(G:D)=g(H_{G3}:D) = g_D(x,\emptyset)+g_D(a,\{xb\})+g_D(b,c)+g_D(c,\emptyset)+g_D(y,c)+g_D(d,y)$$

Figure 17: Three different extensions $H_{G1}$, $H_{G2}$ and $H_{G3}$ of the RPDAG $G$ in Fig. 15

Taking into account the previous expressions, we obtain:

$$g(G_1:D) = g(G:D)-g_D(y,\emptyset)+g_D(y,x)$$

$$g(G_2:D) = g(G:D)-g_D(y,d)+g_D(y,\{xd\})$$

$$g(G_3:D) = g(G:D)-g_D(y,c)+g_D(y,\{xc\})$$

Therefore, the score of any neighboring configuration may be obtained from the score of $G$ by computing only two local scores. Note that some of these local scores may have already been computed at previous iterations of the search process: for example, $g_D(y,\emptyset)$ had to be used to score the initial empty RPDAG, and either $g_D(y,d)$ or $g_D(y,c)$ could have been computed when the link $y\mbox{-}d$ or $y\mbox{-}c$ was inserted into the structure.

Proposition 6   Let $G$ be an RPDAG and $G'$ be any RPDAG obtained by applying one of the operators described in Table 2 to $G$. Let $g$ be a score equivalent and decomposable function.

(a)

If the operator is $A\_link(x,y)$ then

$$g(G':D)=g(G:D)-g_D(y,\emptyset)+g_D(y,\{x\})$$

(b)

If the operator is $A\_arc(x,y)$ then

$$g(G':D)=g(G:D)-g_D(y,Pa_G(y))+g_D(y,Pa_G(y)\cup\{x\})$$

(c)

If the operator is $A\_hh(x,y,z)$ then

$$g(G':D)=g(G:D)-g_D(y,\{z\})+g_D(y,\{x,z\})$$

(d)

If the operator is $D\_link(x,y)$ then

$$g(G':D)=g(G:D)-g_D(y,\{x\})+g_D(y,\emptyset)$$

(e)

If the operator is $D\_arc(x,y)$ then

$$g(G':D)=g(G:D)-g_D(y,Pa_G(y))+g_D(y,Pa_G(y)\setminus\{x\})$$

Proof:

(1) First, we shall prove that we can construct an extension $H'$ of $G'$ and another extension $H$ of $G$, such that $H$ and $H'$ differ in only one arc (this arc being $x\rightarrow y$).

$\bullet$ Consider the cases (a), (b), and (c), which correspond to the addition of an edge between $x$ and $y$: in case (a), $G'=G\cup\{x\mbox{-}y\}$ and let $H'$ be an extension of $G'$ that contains the arc $x\rightarrow y$; in case (b), where $G'=G\cup\{x\rightarrow y\}$, and in case (c), where $G'=(G\setminus\{y\mbox{-}z\})\cup\{x\rightarrow y\leftarrow z\}$, let $H'$ be any extension of $G'$ (which will contain the arc $x\rightarrow y$). In all three cases, let $H=H'\setminus\{x\rightarrow y\}$. We shall prove that $H$ is an extension of $G$:

- First, it is obvious that $G$ and $H$ have the same skeleton.

- Secondly, if $u\rightarrow v\in G$ (in either case $u\rightarrow v\neq x\rightarrow y$), then $u\rightarrow v\in G'$. As $H'$ is an extension of $G'$, then $u\rightarrow v\in H'$, and this implies that $u\rightarrow v\in H$. Therefore, all the arcs in $G$ are also arcs in $H$. This result also ensures that every h-h pattern in $G$ is also an h-h pattern in $H$.

- Thirdly, if $u\rightarrow v\leftarrow w$ is an h-h pattern in $H$ (in either case $u\rightarrow v\leftarrow w\neq x\rightarrow y\leftarrow w$), then $u\rightarrow v\leftarrow w\in H'$. Once again, as $H'$ is an extension of $G'$, we can see that $u\rightarrow v\leftarrow w\in G'$, and then $u\rightarrow v\leftarrow w\in G$. So, $G$ and $H$ have the same h-h patterns.

$H$ is therefore an extension of $G$, according to Definition 2. Note that $\forall u\neq y \; Pa_H(u)=Pa_{H'}(u)$ and $Pa_H(y)=Pa_{H'}(y)\setminus\{x\}$.

$\bullet$ Let us now consider cases (d) and (e), which correspond to the deletion of an edge between $x$ and $y$ (either a link or an arc, respectively): in case (d), let $H$ be an extension of $G$ containing the arc $x\rightarrow y$; in case (e), let $H$ be any extension of $G$. In both cases, let $H'=H\setminus\{x\rightarrow y\}$. We will prove that $H'$ is an extension of $G'$:

- First, it is clear that $G'$ and $H'$ have the same skeleton.

- Secondly, if $u\rightarrow v\in G'$ (note that $u\rightarrow v\neq x\rightarrow y$), then $u\rightarrow v\in G$. As $H$ is an extension of $G$, then $u\rightarrow v\in H$, and therefore $u\rightarrow v\in H'$. So, all the arcs in $G'$ are also arcs in $H'$. Moreover, every h-h pattern in $G'$ is also an h-h pattern in $H'$.

- Thirdly, if $u\rightarrow v\leftarrow w$ is an h-h pattern in $H'$ (and we know that $u\rightarrow v\leftarrow w\neq x\rightarrow y\leftarrow w$), then $u\rightarrow v\leftarrow w\in H$. As $H$ is an extension of $G$, then $u\rightarrow v\leftarrow w\in G$. Therefore, $u\rightarrow v\leftarrow w\in G'$ (the removal of the arc $x\rightarrow y$ cannot destroy any h-h pattern where $x\rightarrow y$ is not involved). So, $G'$ and $H'$ have the same h-h patterns.

In this way, $H'$ is an extension of $G'$. Moreover, we can see that $\forall u\neq y \; Pa_{H'}(u)=Pa_H(u)$ and $Pa_{H'}(y)=Pa_H(y)\setminus\{x\}$.

(2) The scores of $G$ and $G'$ are the same as the scores of $H$ and $H'$ respectively, since $g$ is score equivalent. Moreover, as $g$ is decomposable, we can write

$$\begin{array}{r} g(G':D)= g(H':D) = \sum_u g_D(u,Pa_{H'}(u))... ...(y))= \\ g(G:D)- g_D(y,Pa_H(y))+ g_D(y,Pa_{H'}(y)) \end{array}$$ (4)

Let us now consider the five different cases:

(a) In this case, we know from Table 2 that $Pa_G(y)=\emptyset$. Moreover, $Pa_{G'}(y)=\emptyset$ (because we are inserting a link) and $Pa_{H'}(y)\neq\emptyset$ (because $H'$ is an extension of $G'$ that contains the arc $x\rightarrow y$). Then, from Proposition 5 we obtain $\vert Pa_{H'}(y)\vert=1$, i.e. $Pa_{H'}(y)=\{x\}$. Moreover, $Pa_H(y)=Pa_{H'}(y)\setminus\{x\}=\emptyset$. So, Eq. (4) becomes

$$g(G':D)=g(G:D)-g_D(y,\emptyset)+g_D(y,\{x\})$$

(b) From Table 2 we get $Pa_G(y)\neq\emptyset$ or $Pa_G(x)\neq\emptyset$.

If $Pa_G(y)\neq\emptyset$, from Proposition 5 we obtain $Pa_H(y)=Pa_G(y)$. Moreover, $Pa_{H'}(y)=Pa_H(y)\cup\{x\}=Pa_G(y)\cup\{x\}$.

If $Pa_G(y)=\emptyset$ then $Pa_{G'}(y)=\{x\}$ (because we are adding the arc $x\rightarrow y$). From Proposition 5 we obtain $Pa_{H'}(y)=Pa_{G'}(y)=\{x\}=Pa_G(y)\cup\{x\}$. Moreover, $Pa_H(y)=Pa_{H'}(y)\setminus\{x\}=\emptyset=Pa_G(y)$.

In either case, Eq. (4) becomes

$$g(G':D)=g(G:D)-g_D(y,Pa_G(y))+g_D(y,Pa_G(y)\cup\{x\})$$

(c) In this case, $Pa_G(y)=\emptyset$ and $Pa_{G'}(y)=\{x,z\}$. From Proposition 5 we obtain $Pa_{H'}(y)=\{x,z\}$. Moreover, $Pa_H(y)=Pa_{H'}(y)\setminus\{x\}=\{z\}$. Then, Eq. (4) becomes

$$g(G':D)=g(G:D)-g_D(y,\{z\})+g_D(y,\{x,z\})$$

(d) As $Pa_G(y)=\emptyset$ and $H$ is an extension of $G$ containing the arc $x\rightarrow y$, from Proposition 5 we get $Pa_H(y)=\{x\}$. Moreover, $Pa_{H'}(y)=Pa_H(y)\setminus\{x\}=\emptyset$. In this case Eq. (4) becomes

$$g(G':D)=g(G:D)-g_D(y,\{x\})+g_D(y,\emptyset)$$

(e) In this case, as $Pa_G(y)\neq\emptyset$, Proposition 5 asserts that $Pa_H(y)=Pa_G(y)$. Moreover, $Pa_{H'}(y)=Pa_H(y)\setminus\{x\}=Pa_G(y)\setminus\{x\}$. Therefore, Eq. (4) becomes

$$g(G':D)=g(G:D)-g_D(y,Pa_G(y))+g_D(y,Pa_G(y)\setminus\{x\}) \... ...eight 5pt \kern5pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}$$