[Paper Review] Koopman Operator Dynamical Models: Learning, Analysis and Control

#paper-review #control #dynamical-systems #koopman-operator #system-identification

논문 링크: Koopman Operator Dynamical Models: Learning, Analysis and Control

논문 정보

항목	내용
Venue	Annual Reviews in Control
출판 시점	2021년
저자	Petar Bevanda, Stefan Sosnowski, Sandra Hirche
소속	Chair of Information-oriented Control, Department of Electrical and Computer Engineering, Technical University of Munich

핵심 아이디어

이 논문은 Koopman operator dynamical model을 학습, 해석, 제어 관점에서 정리한 리뷰 논문이다. 핵심 관점은 간단하다.

비선형 상태 dynamics를 직접 선형화하는 대신, observable function이 시간에 따라 어떻게 변하는지를 선형 operator로 본다.

일반적인 nonlinear system은 상태 $x$ 자체의 시간 변화를 본다.

x_{k+1} = F(x_k)

Koopman 관점에서는 상태 $x$ 대신 observable $\psi(x)$ 를 본다. 이때 Koopman operator $\mathcal{K}$ 는 다음처럼 정의된다.

(\mathcal{K}\psi)(x) = \psi(F(x))

$F$ 가 비선형이어도 $\mathcal{K}$ 는 observable function space 위에서 linear operator이다. 즉 비선형성을 없애는 것이 아니라, 비선형성을 더 큰 함수 공간으로 옮겨서 선형 operator로 다루는 것이다.

왜 Koopman Operator가 중요한가

비선형 시스템을 다룰 때 어려운 점은 prediction, analysis, control이 모두 비선형 문제로 바뀐다는 것이다. 특히 model predictive control처럼 최적화가 들어가면 nonlinear dynamics는 계산적으로 부담이 크다.

Koopman 접근은 다음 trade-off를 선택한다.

관점	장점	비용
원래 state dynamics	차원이 낮고 물리적 의미가 직접적이다.	dynamics가 비선형이라 분석과 제어가 어렵다.
Koopman observable dynamics	선형 system 기법을 쓸 수 있다.	일반적으로 infinite-dimensional이다.

따라서 핵심 문제는 다음 질문으로 바뀐다.

어떤 observable 또는 lifting coordinate를 선택하면, 유한 차원에서 Koopman operator를 잘 근사할 수 있는가?

이 논문은 바로 이 질문을 중심으로 기존 방법들을 분류한다.

Koopman Operator 정의

Continuous-time system을 다음과 같이 두자.

\dot{x} = f(x)

이 system의 flow를 $F^t(x)$ 라 하면, Koopman operator semigroup은 observable $\psi$ 에 대해 다음과 같이 작용한다.

(\mathcal{K}^t \psi)(x) = \psi(F^t(x))

Discrete-time에서는 더 단순하다.

x_{k+1}=F(x_k)

이면

(\mathcal{K}\psi)(x) = \psi(F(x))

여기서 중요한 성질은 linearity이다. 두 observable $\psi_1,\psi_2$ 와 scalar $\alpha,\beta$ 에 대해

\mathcal{K}(\alpha \psi_1+\beta \psi_2) = \alpha \mathcal{K}\psi_1 + \beta \mathcal{K}\psi_2

가 성립한다. 이 선형성은 $F$ 가 선형이라서 생기는 것이 아니다. Composition operator가 function에 대해 선형으로 작용하기 때문에 생긴다.

Eigenfunction Coordinate

Koopman operator를 실제 모델로 쓰려면 linearly evolving coordinate가 필요하다. 그 역할을 하는 것이 Koopman eigenfunction이다.

Discrete-time에서 eigenfunction $\phi$ 는 다음을 만족한다.

\mathcal{K}\phi = \lambda \phi

정의에 의해

\phi(F(x)) = \lambda \phi(x)

가 된다. 따라서 trajectory를 따라가면

\phi(x_k) = \lambda^k \phi(x_0)

이다. 즉 원래 상태 $x_k$ 는 비선형으로 움직이더라도, eigenfunction coordinate $\phi(x_k)$ 는 단순히 $\lambda^k$ 로 선형적으로 진화한다.

Continuous-time에서는 generator $\mathcal{G}_{\mathcal{K}}$ 를 사용하여

\mathcal{G}_{\mathcal{K}}\phi = s\phi

라 쓰고,

\phi(x(t)) = e^{st}\phi(x(0))

로 해석할 수 있다.

Observable의 진화

어떤 observable $\psi$ 가 Koopman eigenfunction들의 조합으로 표현된다고 하자.

\psi(x) = \sum_{j=1}^{\infty} v_j \phi_j(x)

여기서 $v_j$ 는 Koopman mode이다. 시간이 지나면

(\mathcal{K}^t\psi)(x) = \sum_{j=1}^{\infty} v_j \lambda_j^t \phi_j(x)

가 된다.

이 식은 Koopman model의 핵심을 잘 보여준다.

구성 요소	의미
$\phi_j(x)$	linearly evolving coordinate이다.
$\lambda_j$	decay, growth, oscillation rate를 담는다.
$v_j$	원래 observable을 재구성하는 mode이다.

즉 Koopman decomposition은 nonlinear dynamics를 여러 개의 선형적으로 진화하는 factor로 나누어 보는 방식이다.

Nonlinear System을 보는 방식

Koopman eigenfunction evolution

논문 Figure. Eigenfunction hypersurface가 시간에 따라 어떻게 진화하는지를 보여준다. Koopman 관점에서는 point trajectory 대신 observable surface의 진화를 본다.

일반적인 dynamical system 분석은 state space에서 점 $x$ 의 trajectory를 추적한다. 반면 Koopman 관점은 observable surface가 어떻게 이동하는지를 본다.

이 차이를 직관적으로 쓰면 다음과 같다.

기존 관점	Koopman 관점
점 $x_k$ 의 trajectory를 본다.	함수 $\psi(x_k)$ 의 진화를 본다.
nonlinear map $F$ 를 직접 다룬다.	linear operator $\mathcal{K}$ 를 다룬다.
local linearization을 자주 쓴다.	가능한 경우 global linear representation을 찾는다.

중요한 점은 Koopman model이 단순한 local linearization이 아니라는 것이다. 잘 선택된 observable space에서는 nonlinear system의 global behavior를 선형적으로 표현할 수 있다.

Koopman Mode와 원래 Dynamics

Koopman modes

논문 Figure. Koopman mode는 linearly evolving factor가 원래 coordinate에 어떻게 기여하는지를 나타낸다.

Nonlinear system evolution

논문 Figure. 여러 Koopman mode가 superposition되어 원래 nonlinear evolution을 구성한다.

논문은 nonlinear system의 evolution을 다음과 같은 형태로 설명한다.

F^{(k)}(x) = v_1 \lambda_1^k \phi_1(x) + v_2 \lambda_2^k \phi_2(x) + v_3 \lambda_3^k \phi_3(x)

여기서 $F^{(k)}$ 는 $F$ 를 $k$ 번 반복한 map이다. 이 식은 state evolution을 Koopman eigenfunction과 mode의 조합으로 재구성한다.

교수님 관점에서 보면 이 식의 의미는 다음과 같다.

비선형 trajectory 하나를 직접 예측하는 것이 아니라, 선형적으로 진화하는 coordinate들의 합으로 전체 dynamics를 재구성한다.

Data-driven Koopman Approximation

Koopman operator는 일반적으로 infinite-dimensional이다. 따라서 실제 학습에서는 finite-dimensional approximation이 필요하다.

데이터가 다음처럼 주어졌다고 하자.

X = \begin{bmatrix} x_1 & x_2 & \cdots & x_m \end{bmatrix}

Y = \begin{bmatrix} y_1 & y_2 & \cdots & y_m \end{bmatrix} , \qquad y_i = F(x_i)

Observable dictionary를 $\Psi(x)$ 라 하면, Koopman approximation은 대략 다음 문제로 쓸 수 있다.

\Psi(y_i) \approx K \Psi(x_i)

행렬 형태로는

\Psi_Y \approx K \Psi_X

이고 least squares로

K^\star = \arg\min_K \left\| \Psi_Y - K\Psi_X \right\|_F^2

를 푼다. 이는 EDMD(Extended Dynamic Mode Decomposition) 계열 방법의 기본 형태로 볼 수 있다.

Representation의 분류

논문은 Koopman 기반 representation을 크게 다음 방향으로 정리한다.

방법	핵심 아이디어
`DMD`	state 자체에서 linear evolution을 찾는다.
`EDMD`	미리 정한 observable dictionary로 lifting한다.
Neural Koopman	neural network로 observable 또는 eigenfunction을 학습한다.
Eigenfunction coordinate	Koopman-invariant coordinate를 직접 찾는다.
Time-delay coordinate	trajectory의 delay embedding으로 선형 representation을 만든다.

이 중 가장 중요한 차이는 spectrally indirect와 spectrally direct의 구분이다.

Spectrally indirect 방법은 observable dictionary를 잡고 그 span 위에서 Koopman operator를 근사한다. 반면 spectrally direct 방법은 linearly evolving eigenfunction 자체를 찾으려 한다.

논문은 최근 흐름이 단순히 많은 observable을 쓰는 방향보다, 실제 Koopman-invariant coordinate를 찾는 방향으로 이동하고 있다고 본다.

Analysis 관점

Koopman operator는 prediction만을 위한 도구가 아니다. System analysis에도 연결된다.

특히 eigenvalue와 eigenfunction은 다음 정보를 준다.

Koopman spectral object	해석
$\operatorname{Re}(s)<0$	해당 mode가 decay한다.
$\operatorname{Re}(s)>0$	해당 mode가 grow한다.
$\operatorname{Im}(s)$	oscillation frequency와 관련된다.
eigenfunction level set	invariant set, basin, stability structure와 연결된다.

논문은 Koopman eigenfunction을 이용해 Lyapunov function을 구성할 수 있음을 설명한다.

Koopman Lyapunov function

논문 Figure. Koopman eigenfunction의 제곱합으로 nonlinear system의 Lyapunov function을 구성한 예시이다.

예를 들어 eigenfunction vector를

\phi(x) = \begin{bmatrix} \phi_1(x) & \cdots & \phi_n(x) \end{bmatrix}^{\top}

라고 하면, Lyapunov function을 다음처럼 둘 수 있다.

V(x) = \phi(x)^{\top}P\phi(x)

여기서 $P$ 는 lifted linear system의 Lyapunov equation으로부터 얻는다.

\Lambda^{\top}P\Lambda - P + I = 0

이 식은 Koopman coordinate에서 nonlinear stability problem을 linear stability analysis와 연결한다.

Control 관점

Koopman model이 제어에서 매력적인 이유는 lifted coordinate에서 dynamics가 선형이 되기 때문이다. 일반적인 형태는 다음과 같이 쓰인다.

z_{k+1} = Az_k + Bu_k

여기서

z_k = \Psi(x_k)

이다. 이렇게 되면 nonlinear system에 대해 linear MPC, LQR, observer design 같은 도구를 사용할 수 있다.

하지만 논문은 이 지점에서 주의해야 한다고 말한다. Autonomous system에서는 Koopman operator가 자연스럽게 정의되지만, control input이 들어간 system에서는 이야기가 복잡해진다.

Control-affine system을 보자.

\dot{x} = f(x)+g(x)u

Observable의 시간 변화는 Lie derivative로 표현된다.

\dot{\phi}(x) = \mathcal{L}_f \phi(x) + \mathcal{L}_g \phi(x)u

따라서 lifted coordinate에서 완전한 linear system이 아니라, bilinear structure가 나타날 수 있다.

\dot{z} = Az + uBz

이 점 때문에 단순히

z_{k+1}=Az_k+Bu_k

라고 가정하는 것은 많은 경우 heuristic이다. 논문은 Koopman control model을 쓸 때 이론적 조건과 실제 approximation의 간극을 인식해야 한다고 강조한다.

장점

Nonlinear dynamics를 global linear representation 관점에서 볼 수 있다.
Prediction, stability analysis, control을 하나의 operator framework로 연결한다.
DMD, EDMD, neural representation learning, time-delay embedding을 같은 관점에서 비교할 수 있다.
Koopman eigenfunction은 mode, frequency, decay, invariant structure를 해석하는 데 유용하다.
잘 학습된 lifted model은 nonlinear MPC보다 계산적으로 효율적인 제어를 가능하게 할 수 있다.

한계

가장 큰 한계는 finite-dimensional exact representation이 일반적으로 보장되지 않는다는 점이다. Koopman operator는 본질적으로 infinite-dimensional이므로, 실제 모델은 항상 truncation 또는 approximation을 포함한다.

또한 observable dictionary를 어떻게 고를지에 대한 일반적인 답이 없다. Dictionary가 너무 작으면 dynamics를 표현하지 못하고, 너무 크면 overfitting, ill-conditioning, computation 문제가 생긴다.

Neural network로 observable을 학습하는 방법도 유망하지만, 다음 문제가 남는다.

문제	설명
invariant coordinate 학습	진짜 Koopman-invariant coordinate를 찾는지 보장하기 어렵다.
model order selection	몇 개의 mode가 필요한지 정하기 어렵다.
error certificate	control에 필요한 사전 오차 보장이 부족하다.
controlled system	input이 있을 때 Koopman representation이 단순 선형이 아닐 수 있다.

특히 safety-critical control에서는 prediction error와 robustness에 대한 certificate가 중요하다. 논문은 이 부분이 아직 충분히 해결되지 않았다고 본다.

정리

이 논문은 Koopman operator를 단순한 modeling trick이 아니라, learning, analysis, control을 연결하는 dynamical system representation으로 정리한다.

핵심은 다음 문장으로 요약할 수 있다.

상태는 비선형으로 움직이지만, 잘 선택한 observable은 선형적으로 움직일 수 있다.

다만 이 관점이 실용적인 모델이 되려면 좋은 observable 또는 eigenfunction coordinate를 찾아야 한다. 따라서 Koopman model의 본질적인 어려움은 선형 algebra가 아니라, 비선형 system을 선형적으로 진화하는 coordinate로 어떻게 lift할 것인가에 있다.