Week 3: RCoT and LiNGAM

 DirectLiNGAM

I begin to read the original paper for DirectLiNGAM, below are my summary:

• DirectLiNGAM does not need initial guess and hyperparameters, and is guaranteed to converge within a fixed small steps if the data fits the model.
• DirectLiNGAM first finds an exogenous variable, then removes it from the model by eliminating all its effect on other variables. After removing, we have a new model with residuals by removing effect of the exogenous variable, then we keep doing this step until the last variable. At the end we get the estimated causal relations, then we can use LSE to compute the causal effect between variables.
• In order to find exogenous variable, we need to do LSE and test the independence of every variable and their residuals from LSE. This step requires an independence test, and is very time consuming.
• With prior knowledge, we can accelerate the algorithm by finding exogenous directly or more easily.

Continuing Experiment on RCoT

Experiments results are recorded in google doc.

Bug Fix

When running experiments on non-linear relationships, bug occurs that the lgb4 algorithm may produce complex number in intermediate step and cause the program to crash. I fix it by finding the original python code for lgb4 and update the code related.

Searching for Detection Boundary of Linear and Non-linear

The goal of these experiments recorded above is to find what kind of causal relation can RCoT detect, and what kind of relation it can not.

The conclusion of the experiments above are:

• RCoT can easily detect linear causal relationship and correctly classify whether the relation is independent or dependent.
• Even just add in a mild non-linear relationship like square, the error occurs for difficult examples.
• More complex non-linear relationship will cause more errors.
• For common cause structure, it is interesting to find that relation like y = abs(x) ** 1.5 can be detect, while y = x ** 2 can not.

Evaluate the Effect of Parameter R

In RCoT algorithm, the parameter R indicates how many samples are being used for Fourier Features. Intuitively, increasing R will increase the running time but also increase the accuracy.

I modify the code, make R an adjustable parameter and do some experiments on it.

However, in experiments, the results show that:

• The running time will be highly influenced by the value of parameter R, and the relationship is almost O(R^2). One test for conditional dependency when using R=100 will result in less than 1 second, one test when R=500 is likely 6-7s, one test when R=1000 is likely 25s, and one test when R=2000 is likely 110s. Therefore, it is almost impossible to use all samples when the sample size is above 10K.
• It turns out that changing R value will not influence much of the test results. For non-linear relationships, even I increase the R value to 3000, the RCoT algorithm still can not correctly classify whether a conditional relation is dependent or not. For linear relationships, even I decrease the R value to 10, the RCoT algorithm still can give correct results for all tests, and the margin does not have significant decreasing.

Direct Test

I simply modify the code provided for testing the direct algorithm and do some simple test on the currently Pairwise Lingam Algorithm (Hyperbolic Tangent (HT) variant).

The results do not turn out good even I increase the noise to make the relationship less determined.

The algorithm can not give the correct results for A, B, C and N, N2 relationship, which should be very simple examples.

Plan for Next Week

• Integrate RCoT into ProbSpace fully, write appropriate comments and make pull request for it.
• Look into Lingam algorithm, read related papers, examine why it won't work, find other alternate algorithms.