\[\mathbf{x}=B\mathbf{x}+\mathbf{e}\]

을 다시 보자.

우리가 궁금한 것은 $B$ 행렬이 도대체 무엇이냐인데, 여기서 해는 어떻게 찾을 수 있을까?

머신러닝에서 solution을 찾을 때 iteration을 상당히 많이 사용하는 것을 볼 수 있다. 여기서도 iteration 기법을 사용해 구할 수 있다면 얼마나 좋을까!

LiNGAM 알고리즘은 S. Shimizu, et al.,2006 에서 제안된 알고리즘으로 무려 1,283회나 인용되었다!

한 번 살펴보도록 하자.

A Linear Non-Gaussian Acyclic Model for Causal Discovery

Under what circumstances and in what way can one determine causal structure on the basis of observational data alone?

Assumptions

1. The observed variables $x_i, i \in {1,\dots,m}$ can be arranged in a causal order, such that no later variable causes any earlier variable. We denote such a causal order by $k(i)$. That is, the generating process is recursive, meaning it can be represented graphically by a directed acyclic graph.

   $x_1,\dots,x_m$ 까지 인과관계를 일렬로 세울 수 있고, 변수 수집과정에서 이 인과관계는 바뀌지 않는다.

2. The value assigned to each variable $x_i$ is a linear function of the values already assigned to the earlier variables, plus a ‘disturbance’ (noise) term $e_i$, and plus an optional constant from $c_i$, that is

   \[x_i=\sum_{k(j)<k(i)}b_{ij}x_j+e_i+c_i\]

   $x_i$는 인과에 앞서는 변수들의 선형결합 + 오차항 + 상수항으로 구성된다. 마치 시계열에서 AR 모형의 느낌이 난다.

3. The disturbances $e_i$ are all continuous-valued random variables with non-Gaussian distributions of non-zero variances, and the $e_i$ are independent of each other, that is $p(e_1,\dots,e_m)=\prod_i{p_i(e_i)}$.

   오차항이 정규분포를 따르지 않고, 서로 독립이라고 가정한다! 지금까지 정규분포를 가정하거나, 아예 분포를 가정하지 않는 건 봤어도 정규분포가 아니라고 가정하는 건 처음 보았다. 논문의 저자도 이 점이 다른 논문들과의 중요한 차이점이라고 언급하고 있다. 다른 논문들은 가우시안 분포를 가정하면 공분산 행렬을 통해 다양한 알고리즘을 적용할 수 있다는 것을 보였지만, 저자는 non-Gaussianity가 더 활용가능성이 높다고 말한다. 이 가정이 성립된다면 변수들에 인과순서에 대한 사전정보 없이 추정을 할 수 있기 때문이라고 하는데 좀 더 살펴봐야겠다. 우선 직관적으로는, 정규분포 하에서 공분산 행렬은 symmetric이기 때문에

   \[x_1 \to x_2 \quad \text{vs.} \quad x_2 \to x_1\]

   중에 선호도를 나타낼 수 있는 방법이 없다고만 생각해두자.

그리고 이 세가지 가정을 만족시키는 모델을 Linear Non-Gaussian Acyclic Model(LiNGAM)으로 정의한다.

Model Identification Using Independent Component Analysis

그러고 다시

\[\mathbf{x}=B\mathbf{x}+\mathbf{e}\]

을 보자.

우리가 만약 $k(i)$를 알고 있다면 $B$는 strictly lower triangular matrix가 될 것이다. 그리고 이를 $\mathbf{x}$에 대해 풀면,

\[\mathbf{x}=A\mathbf{e} \quad A=(I-B)^{-1}\]

이 된다. 오차항의 독립성, non-Gaussianity 가정이 있기 때문에 우리는 이 방정식의 solution을 구할 때 Independent Component Analysis(ICA)를 접목할 수 있다. 자세한 설명은 독립 성분 분석 (ICA)을 참고하면 된다.

ICA 역시 non-Gaussianity를 가정하고 있는데, 똑같은 공분산 행렬을 만들어내는 mixing matrix가 너무 많기 때문이라고 한다.

ICA를 통해 $A$ or $W=A^{-1}$를 구하는 것은 해결했지만 아직 남은 문제가 있다. $\mathbf{e}$ 안에서 원소들의 순서를 아직 정해주지 못했다는 것! LiNGAM 모델은 이를 추가적으로 해결해주어야 할 것이다.

또한 스케일링의 문제도 있다고 하는데 ICA와 LiNGAM이 해결하는 방법이 서로 다르다고 한다. 구체적인 알고리즘에 대해서는 다음 글에서 다뤄보도록 하자.

Reference

• A Linear Non-Gaussian Acyclic Model for Causal Discovery