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 [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 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
. Moreover,
(because we are inserting a link) and
(because
is an extension of
that contains the arc
). Then, from Proposition 5 we obtain
, i.e.
. Moreover,
. 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,
and
. From Proposition 5 we obtain
. Moreover,
. Then, Eq. (4) becomes
(d) As
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
. Moreover,
. Therefore, Eq. (4) becomes