Library

dsep(g::AbstractGraph, u, v, s; verbose = false)

Check whether u and v are d-separated given set s. Algorithm: unrolled https://arxiv.org/abs/1304.1505

cpdag(skel::DiGraph)

Computes CPDAG from a DAG using Chickering's conversion algorithm (equivalent to the PC algorithm with d-seperation as independence test, see pc_oracle.)

Reference: M. Chickering: Learning equivalence classes of Bayesian network structures. Journal of Machine Learning Research 2 (2002). M. Chickering: A Transformational Characterization of Equivalent Bayesian Network Structures. (1995).

Note that the edge order defined there is already partly encoded into the representation of a DiGraph.

vskel(g)

Skeleton and v-structures. (Currently from the first step of the pc-Alg.)

has_recanting_witness(g::AbstractGraph, u, v,  blocked_edges::AbstractGraph) -> Bool

In a causal DAG with edges g, determine whether path-specific effect from vertex u to v with edges in blocked_edges can be can be computed uniquely from the data available to the investigator, which is the case if there is no "recanting witness". Essentially this means that blocked_edges could equivalently be replaced by a blocking only outgoing edges of u.

See Alvin, Shpitser, Pearl (2005): "Identifiability of Path-Specific Effects", https://ftp.cs.ucla.edu/pub/stat_ser/r321-L.pdf.

backdoor_criterion(g::AbstractGraph, u::Integer, v::Integer, Z; verbose = false)

Test that given directed graph g, no node in Z is descendant of u and Z d-separates u from v in the subgraph that only has the backdoors of u left (outgoing edges of u removed)

has_a_path(g::AbstractGraph, U::Vector, V::Vector, exclude_vertices::AbstractVector = T[], nbs=LightGraphs.outneighbors)

Find if there is a path connecting U with V not passing exclude_vertices, where nbs=LightGraphs.outneighbors determines the direction of traversal.

pcalg(n::V, I, par...)
pcalg(g, I, par...)

Perform the PC algorithm for a set of 1:n variables using the tests

I(u, v, [s1, ..., sn], par...)

Returns the CPDAG as DiGraph.

pcalg(t, p::Float64, test::typeof(gausscitest); kwargs...)

run PC algorithm for tabular input data t using a p-value p to test for conditional independeces using Fisher's z-transformation.

pcalg(t::T, p::Float64; cmitest::typeof(cmitest); kwargs...) where{T}

run PC algorithm for tabular input data t using a p-value p to detect conditional independeces using a conditional mutual information permutation test.

orient_unshielded(g, dg, S)

Orient unshielded triples using the seperating sets. g is an undirected graph containing edges of unknown direction, dg is an directed graph containing edges of known direction and both v=>w and w=>vif the direction of Edge(v,w)is unknown.S` are the separating sets of edges.

Returns g, dg.

apply_pc_rules(g, dg)

g is an undirected graph containing edges of unknown direction, dg is an directed graph containing edges of known direction and both v=>w and w=>vif the direction of Edge(v,w)` is unknown.

Returns the CPDAG as DiGraph.

skeleton(n::Integer, I) -> g, S
skeleton(g, I) -> g, S

Perform the undirected PC skeleton algorithm for a set of 1:n variables using the test I. Start with a subgraph g or the complete undirected graph on n vertices. Returns skeleton graph and separating set.

dseporacle(i, j, s, g)

Oracle for the skeleton and pcalg functions using dsep on the true graph g

unshielded(g)

Find the unshielded triples in the cyclefree skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that edges iterates in lexicographical order.

orientable_unshielded(g, S)

Find the orientable unshielded triples in the skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that edges iterates in lexicographical order.

plot_pc_graph(g, df)

plot the output of the PC algorithm.

gausscitest(i, j, s, (C,n), c)

Test for conditional independence of variable no i and j given variables in s with Gaussian test at the critical value c. C is covariance of n observations.

partialcor(i, j, s, C)

Compute the partial correlation of nodes i and j given list of nodes s using the correlation matrix C.

cmitest(i,j,s,data,crit; kwargs...)

Test for conditional independence of variables i and j given variables in s with permutation test using nearest neighbor conditional mutual information estimates at p-value crit.

keyword arguments: kwargs...: keyword arguments passed to independence tests

n_ball(n::Number)

Computes the volume of a n-dimensional unit sphere.

kl_entropy(data::Array{Float64, 2}; k=5)

Compute the nearest-neighbor estimate of the differential entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

kl_renyi(data::Array{Float64, 2}, q; k=5)

Compute the nearest-neighbor estimate of the Renyi-alpha entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

kl_mutual_information(x, y; k=5, bias_correction=true)

compute the nearest-neighbor 'KGS' estimate of the mutual information between x and y.

x and y are 2d arrays, with every column representing one data point. For further information, see

"Estimating Mutual Information" Alexander Kraskov, Harald Stoegbauer, and Peter Grassberger Physical Review E https://arxiv.org/pdf/cond-mat/0305641.pdf

"Demystifying Fixed k-Nearest Neighbor Information Estimators" Weihao Gao, Sewoong Oh, Pramod Viswanath EEE International Symposium on Information Theory - Proceedings https://arxiv.org/pdf/1604.03006.pdf

keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

kl_cond_mi(x, y, z; k=5, bias_correction=true)

compute the nearest-neighbor 'KGS' estimate of the conditional mutual information between x and y given z.

x, y, and z are 2d arrays, with every column representing one data point. keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

kl_perm_mi_test(x, y; k=5, B=100, bias_correction=true)

compute permutation test of independence of x and y.

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

kl_perm_cond_mi_test(x, y, z; k=5, B=100, kp=5, bias_correction=true)

compute permutation test of conditional independence of x and y given z.

For further information, see: "Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information" Jakob Runge Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. http://proceedings.mlr.press/v84/runge18a/runge18a.pdf

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

has_marks(dg, v1, v2, t::Tuple{Symbol, Symbol}

test if the edge between node v1 and v2 has the edge markers given by the tuple t (use the arrow macro to simplify use)

Example: has_marks(dg, 1, 2, arrow"o->")

set_marks!(dg, v1, v2, t::Tuple{Symbol, Symbol})

set edge marks between node v1 and v2.

Example: set_marks!(dg, 1, 2, arrow"*->")

is_collider(dg, v1, v2, v3)

check if egde v1, v2 and v3 form a collider

is_parent(dg, v1, v2)

check if v1 is a parent of v2

is_triangle(dg, v1, v2, v3)

check if v1, v2 and v3 form a triangle

is_discriminating_path(dg, path)

check if path is a discriminating path

is_uncovered_circle_path(dg, path)

check if path is an uncovered circle path

is_uncovered_PD_path(dg, path)

check if path is an uncovered potentially directed path

fcialg(n::V, I, par...; augmented=true, verbose=false, kwargs...)

Perform the FCI algorithm for a set of n variables using the test

I(u, v, [s1, ..., sn], par...)

Returns the PAG as a MetaDiGraph

plot_fci_graph(g, node_labels)

plot the output of the FCI algorithm.

digraph(E)

Create DiGraph from edge-list.

vpairs(g)

Return the edge-list as Pairs.

pc_oracle(g)

Compute CPDAG using the PC algorithm using the dseporacle on the DAG g.

skel_oracle(g)

Compute the skeleton using the dseporacle for the DAG g.

randdag(n, alpha = 0.1)

Create random DAG from randomly permuted random triangular matrix with edge probability alpha.

disjoint_sorted(u, v)

Check if the intersection of sorted collections is empty. The intersection of empty collectios is empty.

ordered_edges(dag)

Iterator of edges of a dag, ordered in Chickering order:

Perform a topological sort on the NODES
while there are unordered EDGES in g
    Let y be the lowest ordered NODE that has an unordered EDGE incident into it
    Let x be the highest ordered NODE for which x => y is not ordered
    return x => y 
end

insorted(a, x)

Check if x is in the sorted collection a

removesorted(collection, item) -> contains(collection, item)

Remove item from sorted collection.