半径を 1 つに決めない、パーシステントホモロジーとデータの形

点がばらばらに並んだデータから、穴の個数を読みとりたい。点だけでは位相が入らないので、半径を決めて球でつなぎます^[2]。

半径をいくつにするかが問題になります。小さすぎれば点はばらばら、大きすぎれば全部つながって $1$ 点と同じ。

パーシステントホモロジーは、半径を $1$ つに決めません。すべての半径を通して、どの穴がどれだけ長く生き残るかを記録します^[1]。

以下では点群から複体を作る手順、フィルトレーション、バーコード、そして安定性定理と応用までを扱います。

点群から複体を作る

有限個の点の集まりを点群といいます。距離が入っていれば、ユークリッド空間でなくても通ります^[2]。

点そのものには位相の情報がありません。$n$ 個の点は $n$ 個の連結成分を持つだけで、穴も何もない。

そこで距離のしきい値 $\delta$ を決め、近い点どうしを単体でつなぎます。すると単体複体ができ、ホモロジーが計算できます。

ヴィートリス・リップス複体

いちばんよく使われる作り方です。$k$ 個の点の組が、どの $2$ 点も距離 $\delta$ 以内なら、$k-1$ 単体を置きます^[3]。

$${\mathrm{VR}}_{\delta }(X)=\{\sigma \subseteq X\mid \mathrm{diam}(\sigma )\le \delta \}$$

$2$ 点間の距離だけで決まるところが利点です。点がどんな空間に入っているかを知らなくても作れます。

辺さえ決まれば、あとは自動です。三角形は $3$ 辺がそろえば入り、四面体は $6$ 辺がそろえば入ります。

チェック複体との違い

もう $1$ つの作り方が、各点を中心とする半径 $\delta /2$ の球の共通部分を見るものです。共通部分が空でない組に単体を置きます^[3]。

$2$ つは一致しません。正三角形の $3$ 頂点で、$\delta$ を $1$ 辺の長さにとってみます。

どの $2$ 点も距離が $\delta$ 以内なので、リップス複体には三角形が入ります。いっぽう $3$ つの球には共通の点がないので、チェック複体には入りません。

チェック複体のほうが良い被覆の条件をみたし、もとの空間を正しく写します。そのかわり、点が入っている空間に依存し、計算も重い。

$\delta$ を定数倍ずらせば互いに含み合うので、実用ではリップス複体を使います^[3]。

フィルトレーション

$\delta$ を $1$ つに決めない、というところが要点です。$\delta$ を $0$ から大きくしていくと、複体が入れ子に増えていきます^[4]。

$$K_0\subseteq K_1\subseteq \cdots \subseteq K_n$$

この列をフィルトレーションといいます。辺が $1$ 本ずつ増え、三角形が $1$ 枚ずつ入る、という増え方です。

各段でホモロジーをとると、群の列ができます。段を進む写像も付いてくるので、単なる群の並びではありません。

誕生と死

ホモロジー類が初めて現れる段を誕生、消える段を死といいます^[4]。

誕生が $i$、死が $j$ なら、区間 $[i,j)$ がその類の寿命です。長さ $j-i$ を持続といいます。

長く生き残る類は、データの本当の形を表していると考えます。すぐ消える類はノイズと見なします。

しきい値を選ぶ問題が、寿命を測る問題に置き換わりました。

バーコード

寿命の区間を横棒で並べたものをバーコードといいます^[1,4]。次数ごとに $1$ 段ずつ描きます。

誕生と死を平面の点 $(i,j)$ として打つ描き方もあり、こちらは永続図といいます。対角線から遠い点ほど寿命が長い。

どちらも同じ情報です。データの形が、区間の集まり $1$ つに要約されます。

例: 円周上に並んだ点

円周の上に $8$ 点を等間隔に置きます。となりどうしの距離を $d_1$、$1$ つ飛ばしの距離を $d_2$ とします。

$\delta <d_1$ では点がばらばらで、$0$ 次に $8$ 本の棒があります。

$\delta$ が $d_1$ を越えると、となりどうしがつながって成分が $1$ つになります。$7$ 本の棒がここで死に、残る $1$ 本は無限に伸びる。

同時に、輪が閉じて $1$ 次の類が生まれます。

$\delta$ が $d_2$ を越えると対角線もつながり、三角形が埋まって輪が消えます。$1$ 次の棒は $[d_1,d_2)$ という区間になる。

長い棒が $1$ 本だけ出たので、この点群は円周の形をしていると読めます。

例: 2 つの塊

離れた $2$ か所に点が集まっているデータを考えます。

$\delta$ が小さいうちは各塊の中でだけつながり、$0$ 次の棒が減って $2$ 本になります。

塊のあいだの距離を越えると、$2$ 本が $1$ 本に合流します。$2$ 本目の棒の長さが、塊がどれだけ離れているかを表す。

クラスタリングを、しきい値を選ばずに行う方法だと読めます。

構造定理

なぜ区間だけで書けるのか。体を係数にとると、答えが出ます^[1]。

各段のホモロジー群と、段を進む写像の組を持続加群といいます。有限生成なら、この加群は区間の直和に一意に分解します。

分解の成分 $1$ つが、棒 $1$ 本にあたります。バーコードは加群の分解そのもので、勝手に描いた図ではありません。

係数が体でないと分解が崩れます。パーシステントホモロジーで $\mathbb{Z}/2$ 係数をよく使うのは、この事情からです。

安定性定理

データは測るたびに少しずれます。ずれで答えが変わっては使えません。

$2$ つの関数から作った永続図のあいだの距離を、ボトルネック距離で測ります。すると次が成り立ちます^[2]。

$$W_{\infty }(D(f),D(g))\le \Vert f-g{\Vert }_{\infty }$$

入力のずれ以上には、出力がずれません。点を少し動かしても、長い棒は長いまま残ります。

短い棒は現れたり消えたりします。ノイズがノイズとして扱われる、という保証です。

この定理があるので、実データに当てられます。

例: ノイズに強いこと

円周上の $8$ 点を少しずつ動かし、さらに離れた場所に点を $1$ つ足したとします。

$0$ 次には短い棒が $1$ 本増えます。足した点が合流するまでの寿命で、点が近ければ短い。

$1$ 次の長い棒は残ります。誕生と死の値が少し動くだけで、区間の長さはほぼ変わらない。

長さで区切れば、増えた点は自然に落ちます。しきい値を選ぶかわりに、棒の長さで切る。

計算量

計算は行列の掃き出しに帰着します。単体の個数を $m$ とすると、素朴なやり方で $m^3$ に比例する手間がかかります^[1]。

近年は行列の積と同じ程度まで下がる手法も知られています。それでも単体の個数が問題で、点が増えると三角形や四面体が爆発的に増えます。

そこで次数を $1$ か $2$ で打ち切る、点を間引く、といった工夫が入ります。実装の勘所は、複体を小さく保つところにあります。

Mapper

もう $1$ つよく使われる道具です^[2]。

データに参照関数を $1$ つ決め、値の重なる区間ごとにデータを分けます。各区間の中でクラスタリングし、重なりのあるクラスターを辺で結びます。

できるのはグラフで、高次元のデータの形を $1$ 枚の図にまとめたものになります。

古典的なリーブグラフの変形にあたります。関数の値でファイバーをつぶす、という発想は同じです。

応用

生物では、病気の進行や、ウイルスの進化の枝分かれを調べるのに使われます^[2]。

センサー網では、センサーの位置を知らなくても、覆えていない穴があるかどうかを判定できます。$1$ 次の長い棒が、覆い残しにあたります。

画像では、形の特徴づけや超解像顕微鏡の解析に使われます。金融の暴落の予測や、複雑ネットワークの解析にも例があります。

穴の個数を数えるという純粋な問いが、データの形を測る道具になりました。

参考文献