Package edu.cmu.tetrad.search

Class Fask

java.lang.Object

edu.cmu.tetrad.search.Fask

public final class Fask
extends Object

Implements the FASK (Fast Adjacency Skewness) algorithm, which makes decisions for adjacency and orientation using a combination of conditional independence testing, judgments of nonlinear adjacency, and pairwise orientation due to non-Gaussianity. The reference is this:

Sanchez-Romero, R., Ramsey, J. D., Zhang, K., Glymour, M. R., Huang, B., and Glymour, C. (2019). Estimating feedforward and feedback effective connections from fMRI time series: Assessments of statistical methods. Network Neuroscience, 3(2), 274-30

Some adjustments have been made in some ways from that version, and some additional pairwise options have been added from this reference:

Hyvärinen, A., and Smith, S. M. (2013). Pairwise likelihood ratios for estimation of non-Gaussian structural equation models. Journal of Machine Learning Research, 14(Jan), 111-152.

This method (and the Hyvarinen and Smith methods) make the assumption that the data are generated by a linear, non-Gaussian causal process and attempts to recover the causal graph for that process. They do not attempt to recover the parametrization of this graph; for this a separate estimation algorithm would be needed, such as linear regression regressing each node onto its parents. A further assumption is made, that there are no latent common causes of the algorithm. This is not a constraint on the pairwise orientation methods, since they orient with respect only to the two variables at the endpoints of an edge and so are happy with all other variables being considered latent with respect to that single edge. However, if the built-in adjacency search is used (FAS-Stable), the existence of latents will throw this method off.

As was shown in the Hyvarinen and Smith paper above, FASK works quite well even if the graph contains feedback loops in most configurations, including 2-cycles. 2-cycles can be detected fairly well if the FASK left-right rule is selected and the 2-cycle threshold set to about 0.1--more will be detected (or hallucinated) if the threshold is set higher. As shown in the Sanchez-Romero reference above, 2-cycle detection of the FASK algorithm using this rule is quite good.

Some edges may be undiscoverable by FAS-Stable; to recover more of these edges, a test related to the FASK left-right rule is used, and there is a threshold for this test. A good default for this threshold (the "skew edge threshold") is 0.3. For more of these edges, set this threshold to a lower number.

It is assumed that the data are arranged so each variable forms a column and that there are no missing values. The data matrix is assumed to be rectangular. To this end, the Tetrad DataSet class is used, which enforces this.

Note that orienting a DAG for a linear, non-Gaussian model using the Hyvarinen and Smith pairwise rules is alternatively known in the literature as Pairwise LiNGAM--see Hyvärinen, A., and Smith, S. M. (2013). Pairwise likelihood ratios for estimation of non-Gaussian structural equation models. Journal of Machine Learning Research, 14(Jan), 111-152. We include some of these methods here for comparison.

Parameters:

depth: -1. # control the size of the conditional set in the independence tests, setting this to a small integer may reduce the running time, but can also result in false positives. -1 means that it will check "all" possible sizes.

score: sem-bic-score

semBicRule: 1 # to set the Chickering Rule, used in the original Fask

penaltyDiscount: 2 # if using sem-bic as independence test (as in the paper). In the paper this is referred as c. Check step 1 and 10 in Algorithm 2 FAS stable.

skewEdgeThreshold: 0.3 # See description of Fask algorithm, and step 11 in Algorithm 1 FASK. Threshold to add edges that may have been non-inferred because there was a positive/negative cycle that result in a non-zero observed relation.

faskLeftRightRule: 1 # this run FASK v1, the original FASK from the paper

faskDelta: -0.3 # See step 1 and 11 in Algorithm 4 (this is the value set in the paper)

orientationAlpha: 0.1 # this was referred in the paper as TwoCycle Alpha or just alpha, the lower it is, the lower the chance of inferring a two cycle. Check steps 17 to 28 in Algorithm 3: 2 Cycle Detection Rule.

structurePrior: 0 # prior on the number of parents. Not used in the paper implementation.

So a run of command line would look like this:

java -jar -Xmx10G causal-cmd-1.4.1-jar-with-dependencies.jar --delimiter tab --data-type continuous --dataset concat_BOLDfslfilter_60_FullMacaque.txt --prefix Fask_Test_MacaqueFull --algorithm fask --faskAdjacencyMethod 1 --depth -1 --test sem-bic-test --score sem-bic-score --semBicRule 1 --penaltyDiscount 2 --skewEdgeThreshold 0.3 --faskLeftRightRule 1 --faskDelta -0.3--orientationAlpha 0.1 -structurePrior 0

This class is configured to respect knowledge of forbidden and required edges, including knowledge of temporal tiers.

This code was cleaned up and rendered compatible with the original implementation on 5-16-2024. jdramsey

Author:

Joseph Ramsey

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	Fask.LeftRight	Enumerates the options left-right rules to use for FASK.

Constructor Summary

Constructors

Constructor	Description
Fask(DataSet dataSet, Score score)	Constructs a new instance of the FaskOrig class with the given DataSet and Score objects.

Method Summary

Modifier and Type	Method	Description
static double	corrExp(double[] x, double[] y, double[] z)	Calculates the expected correlation between two arrays of double values where z is positive.
static double	cu(double[] x, double[] y, double[] condition)	Calculates the expected correlation between two arrays of double values where the condition is greater than 0.
static double	E(double[] x, double[] y, double[] z)	Calculates E(xy) for positive values of z.
static boolean	leftRightV2(double[] x, double[] y)	Calculates a left-right judgment using the difference of corrExp values between two arrays of double values.
Graph	search()	Runs the search on the concatenated data, returning a graph, possibly cyclic, possibly with two-cycles.
void	setAlpha(double alpha)	Sets the significance level for making independence judgments.
void	setCutoff(double alpha)	Sets the significance level at which independence judgments should be made.
void	setDelta(double delta)	Sets the delta value for the current instance of the FaskOrig class.
void	setDepth(int depth)	Sets the depth of the search for the Fast Adjacency Search.
void	setExternalGraph(Graph externalGraph)	Sets the initial graph for the FaskOrig class.
void	setExtraEdgeThreshold(double extraEdgeThreshold)	` Sets the extra-edge threshold for the FaskOrig class.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge object for the current instance.
void	setLeftRight(Fask.LeftRight leftRight)	Sets the left-right rule used.
void	setUseFasAdjacencies(boolean useFasAdjacencies)	Sets the flag indicating whether to use Fast Adjacencies (FAS) for the search algorithm.
void	setUseSkewAdjacencies(boolean useSkewAdjacencies)	Sets the flag indicating whether to use skew adjacencies in the FaskOrig class.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Fask

public Fask(DataSet dataSet,
 Score score)

Constructs a new instance of the FaskOrig class with the given DataSet and Score objects.

Parameters:

dataSet - The DataSet object containing the data.

score - The Score object representing the scoring algorithm.

Method Details

cu

public static double cu(double[] x,
 double[] y,
 double[] condition)

Calculates the expected correlation between two arrays of double values where the condition is greater than 0.

Parameters:

x - The data for the first variable.

y - The data for the second variable.

condition - The condition array indicating whether the correlation should be calculated or not.

Returns:

The expected correlation between the two arrays of double values.

corrExp

public static double corrExp(double[] x,
 double[] y,
 double[] z)

Calculates the expected correlation between two arrays of double values where z is positive.

Parameters:

x - The data for the first variable.

y - The data for the second variable.

z - The data for the third variable used in the correlation calculation.

Returns:

The correlation exponent between the two arrays of double values.

E

public static double E(double[] x,
 double[] y,
 double[] z)

Calculates E(xy) for positive values of z.

Parameters:

x - The data for the first variable.

y - The data for the second variable.

z - The data for the third variable used in the correlation calculation.

Returns:

The correlation exponent between the two arrays of double values.

leftRightV2

public static boolean leftRightV2(double[] x,
 double[] y)

Calculates a left-right judgment using the difference of corrExp values between two arrays of double values.

Parameters:

x - The data for the first variable.

y - The data for the second variable.

Returns:

True if the corrExp value of the first variable is greater than the corrExp value of the second variable, false otherwise.

search

public Graph search()
             throws InterruptedException

Runs the search on the concatenated data, returning a graph, possibly cyclic, possibly with two-cycles. Runs the fast adjacency search (FAS, Spirtes et al., 2000) followed by a modification of the robust skew rule (Pairwise Likelihood Ratios for Estimation of Non-Gaussian Structural Equation Models, Smith and Hyvarinen), together with some heuristics for orienting two-cycles.

Returns:

the graph. Some edges may be undirected; some adjacencies may be two-cycles.

Throws:

InterruptedException

setLeftRight

public void setLeftRight(Fask.LeftRight leftRight)

Sets the left-right rule used.

Parameters:

leftRight - The rule.

See Also:

• Fask.LeftRight

setCutoff

public void setCutoff(double alpha)

Sets the significance level at which independence judgments should be made. Affects the cutoff for partial correlations to be considered statistically equal to zero.

Parameters:

alpha - The significance level.

setDepth

public void setDepth(int depth)

Sets the depth of the search for the Fast Adjacency Search.

Parameters:

depth - The depth of the search. A depth of -1 indicates unlimited depth.

setAlpha

public void setAlpha(double alpha)

Sets the significance level for making independence judgments.

Parameters:

alpha - The significance level value.

setKnowledge

public void setKnowledge(Knowledge knowledge)

Sets the knowledge object for the current instance.

Parameters:

knowledge - The Knowledge object containing the information to be set.

setExternalGraph

public void setExternalGraph(Graph externalGraph)

Sets the initial graph for the FaskOrig class.

Parameters:

externalGraph - The initial graph to be set.

setExtraEdgeThreshold

public void setExtraEdgeThreshold(double extraEdgeThreshold)

` Sets the extra-edge threshold for the FaskOrig class.

Parameters:

extraEdgeThreshold - The value to set for the extra-edge threshold.

setUseFasAdjacencies

public void setUseFasAdjacencies(boolean useFasAdjacencies)

Sets the flag indicating whether to use Fast Adjacencies (FAS) for the search algorithm.

Parameters:

useFasAdjacencies - The flag indicating whether to use FAS.

setUseSkewAdjacencies

public void setUseSkewAdjacencies(boolean useSkewAdjacencies)

Sets the flag indicating whether to use skew adjacencies in the FaskOrig class.

Parameters:

useSkewAdjacencies - The flag indicating whether to use skew adjacencies.

setDelta

public void setDelta(double delta)

Sets the delta value for the current instance of the FaskOrig class. The delta value affects the skewness correction of the data during the search algorithm.

Parameters:

delta - The delta value to be set.