logo

ジョモロジアンのアルゴリズム誘導 📂位相データ分析

ジョモロジアンのアルゴリズム誘導

概要

ZomorodianとCarlssonの論文「Computing Persistent Homology」で紹介されたアルゴリズムの導出プロセスを説明する1。抽象的なシンプレクシャルコンプレックスで作られたフィルタードコンプレックスを受け取り、$\mathcal{P}$-インターバルを返す。計算機で扱いにくいパーシステントモジュールの構築を省略し、行列のリダクションにより持続的ホモロジーを計算する。

導出

Part 0. 事前調査

필터드_컴플렉스.png

アルゴリズムの本格的な導出に先立ち、上の図で描写されるパーシステンスコンプレックスが数式的にどのような形式であるかをまず検討する。このプロセスをしっかりと固めておかないと、論文を読むのが非常に苦痛になるだろう。

  • まず、下部にある数字を$\deg$とし、これが$0$から$5$まで増加しながら次のようにフィルタードコンプレックスを形成する。 $$ \left\{ a,b \right\} = K_{0} \subset K_{1} \subset K_{2} \subset K_{3} \subset K_{4} \subset \left( K_{4} \cup \left\{ acd \right\} \right) = K_{5} $$
  • $\deg$とは関係なく、$K$は$2$-シンプレックスとして、ホモロジーを考慮する文脈で次のようなチェインコンプレックスを形成する。 $$ \mathsf{C}_{2} \overset{\partial_{2}}{\longrightarrow} \mathsf{C}_{1} \overset{\partial_{1}}{\longrightarrow} \mathsf{C}_{0} $$

アルゴリズムの目標は、このような$\partial_{2}$と$\partial_{1}$がデータに与える代数的トポロジカル情報、たとえばベッチ数$\beta_{k}$などが、どの$\deg$で現れていつ$\deg$で消えるかを次のように計算することである。 $$ \begin{align*} L_{0} =& \left\{ \left( 0, \infty \right) , \left( 0,1 \right) , \left( 1,1 \right) , \left( 1,2 \right) \right\} \\ L_{1} =& \left\{ \left( 2,5 \right) , \left( 3,4 \right) \right\} \end{align*} $$

20220710_213052.png

$L_{0}$は$\beta_{0}$に該当する情報、つまりコンポーネントがいつ現れて消えるかを示す$\mathcal{P}$-インターバルで構成され、$L_{1}$は$\beta_{1}$に該当する情報、つまり空間で「穴」と呼べるものがいつ現れて消える$\mathcal{P}$-インターバルで構成されている。

Part 1. $\partial_{1}$

論文では、著者たちはその計算が全てのフィールドで可能であると主張しているが、簡単にグレード付きモジュールである$\mathbb{Z}_{2} [t]$-モジュールでどのような計算が行われるかを見てみよう。これから$\mathsf{C}_{k}$の同次基底を$\left\{ e_{j} \right\}$、$\mathsf{C}_{k-1}$の同次基底を$\left\{ \hat{e}_{i} \right\}$と表記することにする。ここで同次とは、$\mathsf{C}_{k}$をグレード付きモジュールと見たとき、項が一つしかないという意味で受け取ってもよく、つまり$t^{2} + t$のようではなく$t^{4}$のような単項形式であると考えても構わないということである。

필터드_컴플렉스2.png

$$ \deg M_{k} (i,j) = \deg e_{j} - \deg \hat{e}_{i} $$ ホモロジー代数にある程度慣れていれば、今度は$\partial_{k}$に対応する境界行列$M_{k}$を上のテーブルと方程式に合わせて構成し、そのスミス標準形$\tilde{M}_{1}$を求めに行く感じがするだろう。まず$k=1$の場合を考えてみると、先に行列の基底が同次であると言ったので、次のように唯一の$M_{1}$を得ることができる。

20220710_202643.png

このように基底を持って行列を構成することは、$\partial_{k}$の一つの役割が$t^{n}$を掛けること（群作用を取ることでグレード付きモジュールで次数が上がること）の逆を行うことだと見ると理解できる。感覚を掴むために、直接計算してみよう。 $$ \begin{align*} \deg M_{1} (2,5) =& \deg ac - \deg c = 3 - 1 = 2 = \deg t^{2} \\ \deg M_{1} (4,5) =& \deg ac - \deg a = 3 - 0 = 3 = \deg t^{3} \\ \deg M_{1} (2,2) =& \deg bc - \deg c = 1 - 1 = 0 = \deg t^{0} = \deg 1 \end{align*} $$

先に言ったように、今度はこのエシュロン形、特にカラムエシュロン形を作

ると次のようになる。

20220710_204107.png

大学で学んだ線形代数を思い出してみると、各カラムで一番上にありながら$0$でない、図のように四角で囲んだ部分のようなものをピボットと呼んでいた。ここで次の2つの補助定理を紹介する。

  • (1): カラムエシュロン形の対角成分はスミス標準形の対角成分と同じである。
  • (2): $\tilde{M}_{k}$の$i$行のピボットが$\tilde{M}_{k} (i,j) = t^{n}$であればホモロジーグループ$H_{k-1}$の$\sum^{\deg \hat{e}_{i}} F[t] / t^{n}$に該当し、それ以外は$H_{k-1}$の$\sum^{\deg \hat{e}_{i}} F[t]$に該当する。これは$L_{k-1}$が$\left( \deg \hat{e}_{i} , \deg \hat{e}_{i} + n \right)$と$\left( \deg \hat{e}_{i} , \infty \right)$で構成されることと同値である。

つまり、

  • 補助定理(1)により、持続的ホモロジーを計算する際は行操作が必要なく、列操作だけで良いことになる。
  • 補助定理(2)により、$L_{k-1}$は$\left( \deg \hat{e}_{i} , \deg \hat{e}_{i} + n \right)$と$\left( \deg \hat{e}_{i} , \infty \right)$で構成される。
    • 最初の行のピボットが$t^{1}$であり、$\deg d = 1$であるため、$(1,1+1)$を得る。
    • 2番目の行のピボットが$t^{0}$であり、$\deg c = 1$であるため、$(1,1+0)$を得る。
    • 3番目の行のピボットが$t^{1}$であり、$\deg b = 0$であるため、$(0,0+1)$を得る。
    • 4番目の行にピボットがなく、$\deg a = 0$であるため、$(0,\infty)$を得る。

これは、アルゴリズムを導出する前に言及した$L_{0}$と完全に一致する。 $$ L_{0} = \left\{ \left( 0, \infty \right) , \left( 0,1 \right) , \left( 1,1 \right) , \left( 1,2 \right) \right\} $$

Part 2. $\partial_{2}$

20220710_210216.png

$L_{1}$を得るための$\partial_{2}$の行列形$M_{2}$は上のようである。しかし、次の補助定理で計算を減らし、簡単に進めることができる。

  • (3): $\mathsf{C}_{k+1}$の標準基底と$\mathsf{Z}_{k}$に対する$\partial_{k+1}$を表現するためには、$\tilde{M}_{k}$に対応する行を$M_{k+1}$から単に削除しても良い。

言葉は少し難しく聞こえるが、現在の具体的な状況では、$\tilde{M}_{1}$の$1$-シンプレックス$ab,bc,cd,ad,ac$の中で、$cd,bc,ab$のピボットだけが残っているので、これを単に$M_{2}$から削除しても良いということである。直感的に考えると、これらがすでに$k$次元で使用されたので、$k+1$では見る必要もないという程度に受け取っても構わない。こうしてカラムエシュロン形$\tilde{M}_{2}$を直接構築する過程を省略し、その3つの行を削除してみると、次のように下が切り取られた$\check{M}_{2}$を得る。

20220710_210933.png $$ \begin{align*} z_{2} =& ac - bc - ab \\ z_{1} =& ad - bc - cd - ab \end{align*} $$

再び補助定理(2)に従って計算してみよう。

  • 最初の行のピボットが$t^{1}$であり、 $$ \deg z_{2} = \deg \left( ac - bc - ab \right) = \max \deg \left\{ ac , bc , ab \right\} = 3 $$ であるため、$(3,3+1)$を得る。
  • 2番目の行のピボットが$t^{3}$であり、 $$ \deg z_{1} = \deg \left( ad - bc - cd - ab \right) = \max \deg \left\{ ad , bc , cd , ab \right\} = 2 $$ であるため、$(2,2+3)$を得る。

これは、アルゴリズムを導出する前に言及した$L_{1}$と完全に一致する。 $$ L_{1} = \left\{ \left( 2,5 \right) , \left( 3,4 \right) \right\} $$

このようなプロセスをコンプレックス$K$の次元$\dim K$まで繰り返すと、求めていたアルゴリズムを得ることができる。行列の左右の大きさは$\partial_{k}$に従い、その成分は$\deg$に従って充填されると考えると少し混乱しなくなるだろう。

■

一方、補助定理(1)で列操作だけで十分だということは、これまでの導出で見たように行列表現に固執する理由がないということでもある。また、補助定理(3)により、「過去にすでに計算が終わった」部分に対して大胆に行を捨てるような効率的なプロシージャが含まれており、これにはピボットでないカラムを「マーキング」する能力などが必要である。結果として、実際のアルゴリズムの擬似コードpseudo Codeは、行列をそのまま使用するのではなく、もう少し高度なデータ型、ディクショナリーやデータフレームなどで説明されることになる。これは実際に体験すると非常に戸惑いやすく難しい。

実装

  1. Zomorodian. (2005). Computing Persistent Homology: ch4 ↩︎