Direct-LiNGAM算法理解

无论是ICA-LiNGAM还是Direct-LiNGAM，都是属于LiNGAM，那什么是LiNGAM呢？首先我们要搞懂这个问题。

问题一：什么是LiNGAM？

答：LiNGAM是Linear Non-Gaussian Acyclic Model的缩写，其是一种估计结构方程模型或线性贝叶斯网络的新方法。它假设(a)数据的生成过程是线性的；(b)不存在未观测到的混淆因子；(c)误差项（扰动项 disturbance variables or 噪声项)是方差非0的非高斯分布。

那为什么LiNGAM可以保证在数据服从其假设的条件下可以做到恢复除数据中的因果结构呢？那为了回答这个问题，我们就要看看再LiNGAM假设下，变量间的因果关系要如何定义了。假设x与y之间存在因果关系，并且x是y的原因，那么其因果关系就可以用结构方程定义如下：

$y:=ax+u_{x}$ ,因为LiNGAM中假设了误差项 $u_{x}$ 是非高斯的，所以判断两个变量之间的因果关系方向的时候，因为非高斯具有不对称性，所以利用回归计算两个方向所得的残差时，至少有一个是方向的变量是与残差独立的。举个两个变量的例子，假设真正的因果图如下：

那么对于上面这个因果图和LiNGAM的假设，我们可以得知， $U_1 \perp \!\!\! \perp U_2,X_1 \perp \!\!\! \perp U_2$ 这些独立关系。

那么当然我们一开始无法确定X1与X2之间边的方向，那么LiNGAM是如何利用噪声项的非高斯确定这个方向的呢？

首先我们对于两个方向都做一次回归，也就是说用x1对x2做一次回归，然后再使用x2对x1做一次回归。假设回归方程如下所示：

$x_2=ax_1+{\tilde{u_2}} \\ x_1=bx_2+{\tilde{u_{1}}}$ 那么将ax1与bx2移到左边，那么我们可以得到 $\tilde{u_2},\tilde{u_1}$ ，那么我们只要判断x1与x2是否独立于这两个噪声项就可以确定边的方向，因为在真正的因果图中，x1是于u2独立的，而x2与u1是依赖的，所以由此就可以确定边的方向。

但是说到这里，好像并没有体现噪声项的非高斯性在这里有什么帮助，但其实我们能根据这个残差项与变量间的独立性来判断方向就是因为噪声项的非高斯性。因为有了非高斯性，所以即使我们的因果关系的函数是线性的，但是也不存在可以使用逆函数去表达，因为噪声项的非高斯性具有不对称性。

当然在LiNGAM中，其真正的方法不是我上面写的那样，我上面所写的只是为了说明非高斯的帮助，其真正的算法见：http://www.google.com/url?q=http%3A%2F%2Fwww.cs.helsinki.fi%2Fgroup%2Fneuroinf%2Flingam%2FJMLR06.pdf&sa=D&sntz=1&usg=AFQjCNEzI2JLQIYLqffmZ31t0YHOWBRJDw

在粗略回答了什么是LiNGAM以及其中非高斯的作用是什么后，当然大家可能会想既然非高斯有用，那么非线性大概率也是有帮助的了。的确，非线性也可以为我们识别因果结构提供帮助，这个会在接下来的ANM中讲到。

说完问题一，那么问题二自然就是什么是Direct-LiNGAM咯！

问题二：什么是Direct-LiNGAM？它与LiNGAM有什么区别？

Direct-LiNGAM与LiNGAM的区别就是在于估计下述公式中的B矩阵的方式不同，其本质都是一样的。

$\textbf{x}=B\textbf{x}+\textbf{e}$ ，这个表达式其实就是上面公式的矩阵化表达而已，这个B矩阵其实就是一个系数矩阵。

那么在Direct-LiNGAM中，是如何估计这个矩阵B呢？在说明其估计的算法前，首先要给出一个定理与两个引理。

这个定理讲的就是如果一个变量进行了不同的线性组合的结果不是相互依赖的，那就证明该变量是高斯的。

引理1讲的就是当输入的数据是严格符合LiNGAM的假设时，可以利用两个变量做回归相减后的残差与变量之间独立性检验去寻找一个图中的“可观察的外生变量”（即无父节点，只有子节点的变量）。

引理2讲的就是当输入的数据是严格符合LiNGAM的假设时，利用引理1发现一个“外生变量”后，从图中剔除该外生变量后，LiNGAM的假设对于残差组成的矩阵依然成立。这里的残差r就相当于一开始的变量x。

在了解上面的定理和引理后，下面就可以介绍Direct-LiNGAM识别矩阵B的方法了。下图就是其算法过程

简单的来说就是，首先根据引理1，利用残差与变量的独立性找到图中存在的“外生变量”，然后通过讲残差向量与残差矩阵对变量集合x与数据矩阵X重新赋值来剔除这个外生变量对其余变量的影响。然后不断重复该步骤，直至剩下最后一个变量，这样我们就可以得到一个在某种程度上代表了因果关系放心的Causal Order列表。举个例子，如果现在得到的Causal Order列表是[x1,x3,x2],那么我们就可以认为可能存在这种路径：x1->x3,x1->x2,x3->x2。这就是Causal Order所隐含的意义。

那么再得到Causal Order列表后怎么去估计矩阵B呢？这就很简单了，我们在最开始的数据X上使用Causal Order列表中的前一批变量对后一个变量做回归，然后将回归系数做为矩阵B中元素的值。那么什么叫做用前一批变量对后一个变量做回归呢？还是上面的例子，我们的Causal Order列表为：[x1,x2,x3]，那么B矩阵就为3×3的矩阵，那么首先用x1对x2做回归确定 $b_{21}$ 的值，然后使用x1,x2对x3做回归，确定 $b_{31},b_{32}$ 的值，当然，由于数据中一般都会存在误差，所以在估计完B矩阵后，还有对B矩阵进行剪枝，就是将那些非常小的值置为0，可以认为相应的变量之间不存在因果关系。