📂통계적분석

신디 알고리즘이란?

알고리즘 ¹

상태공간이 $\mathbb{R}^{n}$ 인 동역학계가 다음과 같이 스무스 함수 $f : \mathbb{R}^{n} \to \mathbb{R}^{n}$ 에 의해 주어진다고 하자. $$ \dot{\mathbf{x}} = f \left( \mathbf{x} \right) $$ 간단히 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 그리고 $\dot{\mathbf{x}} = \left( \dot{x_{1}} , \cdots , \dot{x_{n}} \right)$ 이라고 나타낼 때, $m \in \mathbb{N}$ 개의 시점 $\left\{ t_{k} \right\}_{k=1}^{m}$ 에 대해 다음과 같이 디자인 매트릭스를 구성한다. $$ \begin{align*} X =& \begin{bmatrix} \mathbf{x}^{T} \left( t_{1} \right) \\ \mathbf{x}^{T} \left( t_{2} \right) \\ \vdots \\ \mathbf{x}^{T} \left( t_{m} \right) \end{bmatrix} = \begin{bmatrix} x_{1} \left( t_{1} \right) & x_{2} \left( t_{1} \right) & \cdots & x_{n} \left( t_{1} \right) \\ x_{1} \left( t_{2} \right) & x_{2} \left( t_{2} \right) & \cdots & x_{n} \left( t_{2} \right) \\ \vdots & \vdots & \ddots & \vdots \\ x_{1} \left( t_{m} \right) & x_{2} \left( t_{m} \right) & \cdots & x_{n} \left( t_{m} \right) \end{bmatrix} \\ \dot{X} =& \begin{bmatrix} \dot{\mathbf{x}}^{T} \left( t_{1} \right) \\ \dot{\mathbf{x}}^{T} \left( t_{2} \right) \\ \vdots \\ \dot{\mathbf{x}}^{T} \left( t_{m} \right) \end{bmatrix} = \begin{bmatrix} \dot{x}_{1} \left( t_{1} \right) & \dot{x}_{2} \left( t_{1} \right) & \cdots & \dot{x}_{n} \left( t_{1} \right) \\ \dot{x}_{1} \left( t_{2} \right) & \dot{x}_{2} \left( t_{2} \right) & \cdots & \dot{x}_{n} \left( t_{2} \right) \\ \vdots & \vdots & \ddots & \vdots \\ \dot{x}_{1} \left( t_{m} \right) & \dot{x}_{2} \left( t_{m} \right) & \cdots & \dot{x}_{n} \left( t_{m} \right) \end{bmatrix} \in \mathbb{R}^{m \times n} \end{align*} $$ $X$ 의 독립변수들에 어떤 비선형함수를 취해서 얻는 파생변수로 만든 행렬 $\Theta \left( X \right) \in \mathbb{R}^{m \times p}$ 를 라이브러리^library라 하고, 각 칼럼을 기저^basis 혹은 후보^candidate라 부르기도 한다. $$ \dot{X} = \Theta \left( X \right) \Xi $$ 위의 행렬방정식에 STLSQ을 수행해서 가능한 한 스파스한 $\Xi \in \mathbb{R}^{p \times n}$ 를 구하는 스파스 회귀를 통해 주어진 동역학계의 지배 방정식^{governing equation}을 찾는 알고리즘을 신디^sINDy(Sparse Identification of Nonlinear Dynamical systems) 알고리즘이라 한다.

설명

신디는 주어진 데이터로부터 가능한 한 스파스한 미분방정식을 찾아내서 데이터에서 유도된 모델^{data-driven model}을 찾는 방법 중 하나로써, 2011년 라이^{Ying-Chen Lai} 교수 등이 제안한 압축 센싱을 통한 방법²과 유사하나 과소결정계 대신 과도결정계를 사용하며 노이즈가 있는 데이터에 대해 수치적인 로버스트니스^robustness를 제고한 알고리즘이다.

STLSQ

STLSQ: 풀 랭크인 행렬 $X \in \mathbb{R}^{m \times p}$ 와 $Y \in \mathbb{R}^{m \times n}$ 에 대해 행렬방정식 $$ Y = X B $$ 이 주어졌을 때, 가능한 한 스파스한 $B \in \mathbb{R}^{p \times n}$ 을 찾는 스파스 회귀 문제를 생각해보자. STLSQ^{sequentially Thresholded Least-Squares Algorithm}은 신디^sINDy 알고리즘을 제안한 브런턴^brunton의 논문에서 사용된 메소드으로써, 이름 그대로 순차적으로 최소제곱법을 반복하며 각 성분의 절대값이 주어진 쓰레숄딩 $\lambda$ 이하로 떨어지면 $0$으로 처리하고 해당 칼럼(독립변수)를 제거하는 식으로 이루어진다.

동역학계에서 얻어진 데이터에 STLSQ를 쓰는 것을 신디 알고리즘이라고는 했지만, 실제의 관계를 생각해보면 오히려 신디 알고리즘을 위해서 고안된 방법이 바로 STLSQ다. $$ \begin{align*} \text{STLSQ} \cdots& \text{SINDy} \\ Y =& \dot{X} \\ X =& \Theta (X) \\ B =& \Xi \end{align*} $$

라이브러리

$$ \Theta (X) = \begin{bmatrix} 1 & x & y & z & x^{2} & xy & xz & y^{2} & \cdots & z^{5} \end{bmatrix} $$ 라이브러리 $\Theta (X)$ 는 특별할 것 없이 그냥 위와 같이 다항함수로 채울 수도 있다. 어지간히 간단한 스무스 시스템이라면 충분히 큰 차수를 사용했을 때 스톤-바이어슈트라스 정리에 따라 $X$ 의 다항함수로 $\dot{X}$ 를 근사시킬 수 있음이 수학적으로 보장되고, 삼각함수 $\sin (kx)$ 와 $\cos (kx)$ 들은 푸리에 기저라 불리기도 한다³.

위의 그림은 신디가 실제 구현 상으로 어떻게 작동하는지 아주 잘 설명하고 있다. $$ \begin{align*} {{dx} \over {dt}} =& - \sigma x + \sigma y \\ {{dy} \over {dt}} =& - xz + \rho x - y \\ {{dz} \over {dt}} =& xy - \beta z \end{align*} $$ 로렌츠 어트랙터라고 친다면 이들의 트래젝터리에서 데이터를 샘플링 한 후, 위에서 설명한 방식대로 행렬방정식을 세우고 STLSQ를 사용해서 원래의 ‘미분방정식 자체’를 복원한 것이다. 로렌츠 어트랙터의 도함수들은 보다시피 $x$, $y$, $xz$, $xy$ 같이 2차 이하의 다항함수들로 구성되어 있기 때문에 성공적으로 지배 방정식을 찾을 수 있다.