Search Algorithms: GES


GES (Greedy Equivalence Search) is a Bayesian algorithm that searches over Markov equivalence classes, represented by patterns, for a data set D over a set of variables V.

A pattern is an acyclic graph that consists whose edges are either directed (-->) or undirected (---) and represents an equivalence class of DAGs, as follows: each directed edge in the pattern is so directed in every DAG in the equivalence class, and for each undirected edge X---Y in the pattern, a DAG exists in the equivalence class with that edge directed as X<--Y and a DAG exists in the equivalence class with that edge directed as X-->Y. To put it differently, a pattern represent the set of edges that can be determined by the search, with as many of these edges oriented as can be, using the available information.

It is assumed (as with PC) that the true causal graph is acyclic and the no common hidden causes exist between pairs of variables in the graph. GES can be run on datasets that are either entirely continuous or entirely discrete (but not directly on graphs using d-separation). In the continuous case, it is assumed that the direct causal influence of any variable into any other is linear, with the distribution of each variable being Normal. Under these assumptions, the algorithm is pointwise consistent.

GES searches over patterns by scoring the patterns themselves. There is a forward sweep in the algorithm and a backward sweep. In the forward sweep, at each step, GES tries to find the edge which, once added, increases the score the most over not adding any edge at all. (After adding each such edge, the pattern is rebuilt by orienting any edge as --- that does not participate in a collider and then applying Meek's PC orientation rules to add any implied orientations.) Once the algorithm gets to the point where there is no edge that can be added that would increase the score, the backward sweep begins. In the backward sweep, GES tries at each step to find the one edge it can remove that will increase the score of the resulting the most over the previous pattern. Once it gets to the point where there is no edge anymore than once removed increases the score, the algorithm stops.

There are some differences in assumptions and expected behavior between this algorithm and the PC algorithm. When, contrary to assumptions, there is actually a latent common cause of two measured variables the PC algorithm will sometimes discover that fact; GES will not.

Information about how precisely GES makes decisions about adding or removing edges can be found in the logs, which can be accessed using the Logging menu.

 

Entering GES parameters

Consider the following example:



When the PC algorithm is chosen from the Search Object combo box, the following window appears:



The parameters that are used by the GES algorithm can be specified in this window. The parameters are as follows:

Execute the search.


Interpreting the output

The GES algorithm returns a partially oriented graph where the nodes represent the variables given as input. In our example, the outcome should be as follows if the sample is representative of the population:



The are basically two types of edges that can appear in GES output:

The absence of an edge between any pair of nodes means they are independent, or that the causal effect of one modelNode in the other is intermediate by other observed variables. Unlike the PC algorithm, no accidental double-directed edges can appear. It does not mean that GES will be immune to the sample variation that caused the unexpected behavior of the PC search. It is a good idea to run both searches and compare the result.

Finally, a triplet of nodes may assume the following pattern:

In other words, in such patterns, A and B are connected by an undirected edge, A and C are connected by an undirected edge, and B and C are not connected by an edge. By the PC search assumptions, this means that B and C cannot both be cause of A. The three possible scenarios are:

In our example, some edges were compelled to be directed: X2 and X3 are causes of X4, and X4 is a cause of X5. However, we cannot tell much about the triplet (X1, X2, X3), but we know that X2 and X3 cannot both be causes of X1.

References:

Chickering (2002). Optimal structure identification with greedy search. Journal of Machine Learning Research.