pcalg (version 2.0-3)

gies: Estimate Interventional Markov Equivalence Class of a DAG by GIES

Description

Estimate the interventional essential graph representing the Markov equivalence class of a DAG using the greedy interventional equivalence search (GIES) algorithm of Hauser and Bühlmann (2012).

Usage

gies(p, targets, score, fixedGaps = NULL, 
  turning = TRUE, maxDegree = integer(0), verbose = FALSE, ...)

Arguments

p

Number of variables.

targets

A list of intervention targets (cf. details). A list of vectors, each vector listing the vertices of one intervention target.

score

An instance of a class derived from Score.

fixedGaps

logical symmetric matrix of dimension p*p. If entry [i, j] is TRUE, the result is guaranteed to have no edge between nodes $i$ and $j$.

turning

Logical indicating whether the function should try to augment the score by turning edges (cf. details).

maxDegree

Parameter used to limit the vertex degree of the estimated graph. Possible values:

1. Vector of length 0 (default): vertex degree is not limited.
2. Real number$r$,$0 < r < 1$: degree of vertex$v$is limited to$r \cdot n_v$, whe

verbose

if TRUE, detailed output is provided.

...

Additional arguments for debugging purposes and fine tuning.

Value

• gies returns a list with the following two components:
• essgraph
  An object of class EssGraph containing an estimate of the equivalence class of the underlying DAG.
• repr
  An object of a class derived from ParDAG containing a (random) representative of the estimated equivalence class.

encoding

UTF-8

concept

• greedy interventional equivalence search
• essential graph

Details

This function estimates the interventional Markov equivalence class of a DAG based on a data sample with interventional data originating from various interventions and possibly observational data. The intervention targets used for data generation must be specified by the argument targets as a list of (integer) vectors listing the intervened vertices; observational data is specified by an empty set, i.e. a vector of the form integer(0). As an example, if data contains observational samples as well as samples originating from an intervention at vertices 1 and 4, the intervention targets must be specified as list(integer(0), as.integer(1), as.integer(c(1, 4))). An interventional Markov equivalence class of DAGs can be uniquely represented by a partially directed graph called interventional essential graph. Its edges have the following interpretation:

1. a directed edge$a \longrightarrow b$stands for an arrow that has the same orientation in all representatives of the interventional Markov equivalence class;
2. an undirected edge$a$--$b$stands for an arrow that is oriented in one way in some representatives of the equivalence class and in the other way in other representatives of the equivalence class.

Note that when plotting the object, undirected and bidirected edges are equivalent. GIES (greedy interventional equivalence search) is a score-based algorithm that greedily maximizes a score function (typically the BIC, passed to the function via the argument score) in the space of interventional essential graphs in three phases, starting from the empty graph: [object Object],[object Object],[object Object] GIES cycles through these three phases until no augmentation of the score is possible any more. GIES is an interventional extension of the GES (greedy equivalence search) algorithm of Chickering (2002) which is limited to observational data and hence operates on the space of observational instead of interventional Markov equivalence classes.

References

D.M. Chickering (2002). Optimal structure identification with greedy search. Journal of Machine Learning Research 3, 507--554 A. Hauser and P. Bühlmann (2012). Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research 13, 2409--2464.

See Also

ges, Score, EssGraph

Examples

## Load predefined data
data(gmInt)

## Define the score (BIC)
score <- new("GaussL0penIntScore", gmInt$x, gmInt$targets, gmInt$target.index) 

## Estimate the essential graph
gies.fit <- gies(ncol(gmInt$x), gmInt$targets, score) 

## Plot the estimated essential graph and the true DAG
if (require(Rgraphviz)) {
  par(mfrow=c(1,2))
  plot(gies.fit$essgraph, main = "Estimated ess. graph")
  plot(gmInt$g, main = "True DAG")
}