The search method we have described may be applied in combination with any score equivalent function (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 to be evaluated, select any extension of and compute . We could also use other (non-equivalent) scoring functions, although the score of would depend on the selected extension.
However, let us consider the case of a decomposable scoring function : the DAG obtained by adding or removing an arc from the current DAG can be evaluated by modifying only one local score:
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 ).
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 in Figure 15 and the three neighboring configurations produced by the inclusion of an edge between and , , and (also displayed in Figure 15).
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.
We can therefore write:
For each extension of any neighboring configuration , it is always possible to find an extension of the current RPDAG such that the scores of and only differ in one local score (Figure 17 displays these extensions). We can then write:
Taking into account the previous expressions, we obtain:
Therefore, the score of any neighboring configuration may be obtained from the score of 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, had to be used to score the initial empty RPDAG, and either or could have been computed when the link or was inserted into the structure.
(1) First, we shall prove that we can construct an extension of and another extension of , such that and differ in only one arc (this arc being ).
Consider the cases (a), (b), and (c), which correspond to the addition of an edge between and : in case (a), and let be an extension of that contains the arc ; in case (b), where , and in case (c), where , let be any extension of (which will contain the arc ). In all three cases, let . We shall prove that is an extension of :
- First, it is obvious that and have the same skeleton.
- Secondly, if (in either case ), then . As is an extension of , then , and this implies that . Therefore, all the arcs in are also arcs in . This result also ensures that every h-h pattern in is also an h-h pattern in .
- Thirdly, if is an h-h pattern in (in either case ), then . Once again, as is an extension of , we can see that , and then . So, and have the same h-h patterns.
is therefore an extension of , according to Definition 2. Note that and .
Let us now consider cases (d) and (e), which correspond to the deletion of an edge between and (either a link or an arc, respectively): in case (d), let be an extension of containing the arc ; in case (e), let be any extension of . In both cases, let . We will prove that is an extension of :
- First, it is clear that and have the same skeleton.
- Secondly, if (note that ), then . As is an extension of , then , and therefore . So, all the arcs in are also arcs in . Moreover, every h-h pattern in is also an h-h pattern in .
- Thirdly, if is an h-h pattern in (and we know that ), then . As is an extension of , then . Therefore, (the removal of the arc cannot destroy any h-h pattern where is not involved). So, and have the same h-h patterns.
In this way, is an extension of . Moreover, we can see that and .
(2) The scores of and are the same as the scores of and respectively, since is score equivalent. Moreover, as is decomposable, we can write
Let us now consider the five different cases:
(a) In this case, we know from Table 2 that
(because we are inserting a link) and
(because is an extension of that contains the arc
). Then, from Proposition 5 we obtain
. So, Eq. (4) becomes
(b) From Table 2 we get or .
If , from Proposition 5 we obtain . Moreover, .
If then (because we are adding the arc ). From Proposition 5 we obtain . Moreover, .
In either case, Eq. (4) becomes
(c) In this case,
. From Proposition 5 we obtain
. Then, Eq. (4) becomes
and is an extension of containing the arc
, from Proposition 5 we get . Moreover,
. In this case Eq. (4) becomes
(e) In this case, as
, Proposition 5 asserts that
. Therefore, Eq. (4) becomes