【入門者向け】動的モード分解(DMD)の概要解説

2017.11.03
機械学習の手法

この記事の内容はほぼ英語版Wikipediaの邦訳なので英語が読める人はぜひ元記事も参照してもらいたいです。

1. 動的モード分解とは
2. 概要
3. アルゴリズム
- 3.1. The Arnoldi approach
- 3.2. The SVD-based approach
4. まとめ

動的モード分解とは

動的モード分解は流体力学の分野から生まれた手法で、多次元時系列データを周波数と増幅/減衰率の情報を持った個々のmodeに分解することが目的です。

平たく言えば脳波みたいな複雑な形をした波を、sinxやcosxみたいな単純な波の重ね合わせに分解したいよねってことです。

概要

データを以下の行列の形に並べます。

${ V }_{ 1 }^{ N }=\{ v_{ 1 },v_{ 2 },\dots ,v_{ N }\} \quad \cdots \left( \ast \right)$

$v_{i}$ はM次元列ベクトルで、M個の測定点で測ったデータを縦に並べたものです。

それを一定の時間間隔でN回測り、横に並べただけですね。

ここで各データ間に線形性がある、即ち

${ v }_{ i+1 }=A{ v }_{ i }$

が成り立つと仮定すれば上記 $\left( \ast \right)$ は

${ V }_{ 2 }^{ N }=A{ V }_{ 1 }^{ N-1 }+r{ e }_{ N-1 }^{ T }$

と書けます。

ただし

${V}_{1}^{N-1}=\{v_{1},v_{2},\dots ,v_{N-1}\}$

${V}_{2}^{N}=\{v_{2},v_{3},\dots ,v_{N}\}$

${ e }_{ N-1 }=\left\{ 0,0,\cdots ,1 \right\}$

で、 $r{ e }_{ N-1 }^{ T }$ は線形性が成り立たない部分を埋めるための残差項です。

この式の $A$ の固有値と固有ベクトルはそれぞれDMD eigenvalues,DMD modesと呼ばれ、これを求めることがDMDの目的です。

固有値は複素形式で書かれ、各波の周波数と時間的な増幅/減衰率の情報を持ちます。

各固有ベクトルは直交とは限りませんが、むしろそのことが波の柔軟な表現を可能にします。

アルゴリズム

The Arnoldi approach

流体力学の分野では、測定点Mの数が測定回数Nに比べてはるかに大きいことが多く、それ故に $A$ は一意に定まりません。

The Arnoldi approachでは ${V}_{2}^{N}$ のN番目の列ベクトルが ${V}_{1}^{N-1}$ の各列ベクトルの線形結合で書ける、即ち

${ v }_{ N }={ a }_{ 1 }{ v }_{ 1 }+{ a }_{ 2 }{ v }_{ 2 }+\cdots { a }_{ N-1 }{ v }_{ N-1 }+r$

が成り立つような $A$ を選びます。

${V}_{2}^{N}$ はN番目の列ベクトルを除いて ${V}_{1}^{N-1}$ の列ベクトルを1つ左に移動させたものになっているので、上記の線形結合が成り立つことと下式が成り立つことは同値です。

${ V }_{ 2 }^{ N }=A{ V }_{ 1 }^{ N-1 }={ V }_{ 1 }^{ N-1 }S+r{ e }_{ N-1 }^{ T }$

ただし、

$S=\left( \begin{matrix} 0 & 0 & \cdots & 0 & a_{ 1 } \\ 1 & 0 & \cdots & 0 & a_{ 2 } \\ 0 & 1 & \cdots & 0 & { a }_{ 3 } \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & {a}_{ N-1 } \end{matrix} \right)$

各 ${ a }_{ i }$ は残差に関する最小二乗問題を解くことで求めることができます。

この形式で書いた時、DMDはArnoldi法(大規模な行列の固有値を近似的に求める方法、詳細は省略)を使っているので $S$ の固有値は $A$ の固有値の良い近似になっており、 $S$ の固有ベクトルを $y$ とすれば、 ${V}_{1}^{N-1}y$ はAの固有ベクトルの良い近似になっています。

The SVD-based approach

今度はArnoldi法ではなくSVD(特異値分解)を用います。

${ V }_{ 1 }^{ N-1 }$ の特異値分解を ${ V }_{ 1 }^{ N-1 }=U\Sigma { W }^{ T }$ とすると

${ V }_{ 2 }^{ N }=A{ V }_{ 1 }^{ N-1 }+r{ e }_{ N-1 }^{ T }=AU\Sigma { W }^{ T }+r{ e }_{ N-1 }^{ T }$

The SVD-based approachでは ${ V }_{ 2 }^{ N }$ が $U$ の列ベクトルの線形結合で書けるような $A$ を選びます。

これは言い換えれば、PCA(主成分分析)(機械学習的にはPODとも)の基底の重ね合わせで書けるということでもあります。(特異値分解の性質から $U$ の列ベクトルは正規直交基底なので)

要するに ${ V }_{ 1 }^{ N-1 }$ と ${ V }_{ 2 }^{ N }$ が同一の正規直交基底で書けることを仮定しているわけですね。

この条件のもとで残差を最小にするためには残差と上記の基底ベクトルが直交であることが必要で、即ち

${ U }^{ T }r=0$

なので

${ V }_{ 2 }^{ N }=A{ V }_{ 1 }^{ N-1 }+r{ e }_{ N-1 }^{ T }=AU\Sigma { W }^{ T }+r{ e }_{ N-1 }^{ T }$

の両辺に ${ U }^{ T }$ をかけて変形すると

${ U }^{ T }AU={ U }^{ T }{ V }_{ 2 }^{ N }W{ \Sigma }^{ -1 }\equiv \tilde { S }$

$A$ と $\tilde { S }$ は相似変換なので固有値は等しく、 $y$ を $\tilde { S }$ の固有ベクトルとすれば $Uy$ は $A$ の固有ベクトルになります。

まとめ

${ v }_{ i+1 }=A{ v }_{ i }$

という形でデータ間の時間変化に関する式を立てているので、アルゴリズムで求めた $A$ の固有値と固有ベクトルはデータの時間変化を表す量であることをもう1度確認しておきます。

${ v }_{ i+1 }=A{ v }_{ i }={A}^{2}{v}_{i-1}=\cdots$ と順々に ${ v }_{ 1 }$ まで適用していくことをイメージすると分かりやすいですかね。

さて、DMDとは固有値分解を用いて、複雑な波を単純な波に分解する手法でした。

数学的な部分は僕も細かくは追いきれてない部分もあるのでいずれ追記していこうと思います。