Package edu.cmu.tetrad.search

Class IcaLingD

java.lang.Object
edu.cmu.tetrad.search.IcaLingD
public class IcaLingD extends Object

Implements the ICA-LiNG-D algorithm as well as a number of ancillary methods for LiNG-D and LiNGAM. The reference is here:

Lacerda, G., Spirtes, P. L., Ramsey, J., & Hoyer, P. O. (2012). Discovering cyclic causal models by independent components analysis. arXiv preprint arXiv:1206.3273.

ICA-LING-D is a method for estimating a possible cyclic linear models graph from a dataset. It is based on the assumption that the data are generated by a linear model with non-Gaussian noise. The method is based on the following assumptions:

  1. The data are generated by a linear model with non-Gaussian noise.
  2. The noise is independent across variables.
  3. The noises for all but possibly one variable are non-Gaussian.
  4. There is no unobserved confounding.

lower bound of the absolute value of the coefficients in the W matrix.

Under these assumptions, the method estimates a matrix W such that WX = e, where X is the data matrix, e is a matrix of noise, and W is a matrix of coefficients. The matrix W is then used to estimate a matrix B Hat, where B Hat is the matrix of coefficients in the linear model that generated the data. The graph is then estimated by finding edges in B Hat.

We use the N Rooks algorithm to find alternative diagonals for permutations of the W matrix. The parameter that N Rooks requires is a threshold for entries in W to be included in possible diagonals, which is the lowest number in absolute value that a W matrix entry can take to be part of a diagonal; the implied permutations is the permutations that permutes rows so that these combination lies along the their respective diagonals in W, which are then scaled, and the separate satisfactory B Hat matrices reported.

ICA-LiNG-D, which takes this W as an impute, is a method for estimating a directed graph (DG) from a dataset. The graph is estimated by finding a permutation of the columns of the dataset so that the resulting matrix has a strong diagonal. This permutation is then used to estimate a DG. The method is an relaxation of LiNGAM, which estimates a DAG from a dataset using independent components analysis (ICA). LiNG-D is particularly useful when the underlying data may have multiple consistent cyclic models.

This class is not configured to respect knowledge of forbidden and required edges.

Author:
peterspirtes, gustavolacerda, patrickhoyer, josephramsey
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    IcaLingD()
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    static Matrix
    estimateW(DataSet data, int fastIcaMaxIter, double fastIcaTolerance, double fastIcaA)
    Estimates the W matrix using FastICA.
    List<Matrix>
    fit(DataSet D)
    Fits a LiNG-D model to the given dataset using a default method for estimating W.
    List<Matrix>
    fitW(Matrix W)
    Performs the LiNG-D algorithm given a W matrix, which needs to be discovered elsewhere.
    static Matrix
    getScaledBHat(PermutationMatrixPair pair, double bThreshold)
    Returns the BHat matrix, permuted to the variable order of the original data and scaled so that the diagonal consists only of 1's.
    static PermutationMatrixPair
    hungarianDiagonal(Matrix W)
    Finds a column permutation of the W matrix that maximizes the sum of 1 / |Wii| for diagonal elements Wii in W.
    static boolean
    isAcyclic(Matrix scaledBHat)
    Determines whether a BHat matrix parses to an acyclic graph.
    static boolean
    isStable(Matrix bHat)
    Whether the BHat matrix represents a stable model.
    static @NotNull Graph
    makeGraph(Matrix B, List<Node> variables)
    Returns a graph given a coefficient matrix and a list of variables.
    static Matrix
    scale(Matrix M)
    Scales the given matrix M by diving each entry (i, j) by M(j, j)
    void
    setBThreshold(double bThreshold)
    The threshold to use for set small elements to zero in the B Hat matrices.
    void
    setSpineThreshold(double spineThreshold)
    Sets the threshold used to prune the matrix for the purpose of searching for alternative strong diagonals.
    static Matrix
    threshold(Matrix M, double threshold)
    Thresholds the given matrix, sending any small entries in absolute value to zero.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • IcaLingD

      public IcaLingD()
      Constructor.

  • Method Details

    • isAcyclic

      public static boolean isAcyclic(Matrix scaledBHat)
      Determines whether a BHat matrix parses to an acyclic graph.
      Parameters:
      scaledBHat - The BHat matrix..

    • estimateW

      public static Matrix estimateW(DataSet data, int fastIcaMaxIter, double fastIcaTolerance, double fastIcaA)
      Estimates the W matrix using FastICA. Assumes the "parallel" option, using the "exp" function.
      Parameters:
      data - The dataset to estimate W for.
      fastIcaMaxIter - Maximum number of iterations of ICA.
      fastIcaTolerance - Tolerance for ICA.
      fastIcaA - Alpha for ICA.
      Returns:
      The estimated W matrix.

    • makeGraph

      @NotNull public static @NotNull Graph makeGraph(Matrix B, List<Node> variables)
      Returns a graph given a coefficient matrix and a list of variables. It is assumed that any non-zero entry in B corresponds to a directed edges, so that Bij != 0 implies that j->i in the graph.
      Parameters:
      B - The coefficient matrix.
      variables - The list of variables.
      Returns:
      The built graph.

    • hungarianDiagonal

      public static PermutationMatrixPair hungarianDiagonal(Matrix W)
      Finds a column permutation of the W matrix that maximizes the sum of 1 / |Wii| for diagonal elements Wii in W.
      Parameters:
      W - The W matrix, WX = e.
      Returns:
      The model with the strongest diagonal, as a permutation matrix pair.
      See Also:

    • isStable

      public static boolean isStable(Matrix bHat)
      Whether the BHat matrix represents a stable model. The eigenvalues are checked to make sure they are all less than 1 in modulus.
      Parameters:
      bHat - The bHat matrix.
      Returns:
      True iff the model is stable.

    • scale

      public static Matrix scale(Matrix M)
      Scales the given matrix M by diving each entry (i, j) by M(j, j)
      Parameters:
      M - The matrix to scale.
      Returns:
      The scaled matrix.

    • threshold

      public static Matrix threshold(Matrix M, double threshold)
      Thresholds the given matrix, sending any small entries in absolute value to zero.
      Parameters:
      M - The matrix to threshold.
      threshold - The value such that M(i, j) is set to zero if |M(i, j)| < threshold. Should be non-negative.
      Returns:
      The thresholded matrix.

    • getScaledBHat

      public static Matrix getScaledBHat(PermutationMatrixPair pair, double bThreshold)
      Returns the BHat matrix, permuted to the variable order of the original data and scaled so that the diagonal consists only of 1's.
      Parameters:
      pair - The (column permutation, thresholded, column permuted W matrix) pair.
      bThreshold - Valued in the BHat matrix less than this in absolute value are set to 0.
      Returns:
      The estimated B Hat matrix for this pair.
      See Also:

    • fit

      public List<Matrix> fit(DataSet D)
      Fits a LiNG-D model to the given dataset using a default method for estimating W.
      Parameters:
      D - A continuous dataset.
      Returns:
      The BHat matrix, where B[i][j] gives the coefficient of j->i if nonzero.

    • fitW

      public List<Matrix> fitW(Matrix W)
      Performs the LiNG-D algorithm given a W matrix, which needs to be discovered elsewhere. The 'local algorithm' is assumed--in fact, the W matrix is simply thresholded without bootstrapping.
      Parameters:
      W - The W matrix to be used.
      Returns:
      A list of estimated B Hat matrices generated by LiNG-D.

    • setBThreshold

      public void setBThreshold(double bThreshold)
      The threshold to use for set small elements to zero in the B Hat matrices.
      Parameters:
      bThreshold - The threshold, a non-negative number.

    • setSpineThreshold

      public void setSpineThreshold(double spineThreshold)
      Sets the threshold used to prune the matrix for the purpose of searching for alternative strong diagonals.
      Parameters:
      spineThreshold - The threshold, a non-negative number.