Persistent Homology - Joeの精進記録

A Persistent Weisfeiler–Lehman Procedure for Graph Classificationを読んでいてPersistent Homologyとは？となったので、調べた内容をまとめる。

Motivation

f:id:xuzijian629:20190720184635p:plain [1]

目標として、データの幾何学的構造を捉えたい。リング状になっているデータ点の集合あったとして、点ごとに見ると、離散的でリングが見えない。点を肥大化していくとリングが現れるが肥大化しすぎるとリングが潰れてしまう。これを、あらゆる肥大化について考えることで（Persistent: 永続的にすることで）、データの幾何学的構造をうまく見つけようというモチベーション。

f:id:xuzijian629:20190720185149p:plain [2]

１つ目の図では肥大化を、その点を中心とする球の大小みたいなイメージで説明したが、別に特定のメトリックならなんでもいい（後述）。２つ目の人っぽいやつの図はどんなメトリックによってresolutionを変えているかわからないけど球の大小みたいなのでなくても大丈夫。いずれにせよresolutionを変えるという表現はかなり適切っぽい。

Filteration

f:id:xuzijian629:20190720185831p:plain [2]

距離が定められた空間において、各点から距離が $h$ 以下になるような距離空間内の点からなる集合を $M_h$ と定めており、距離の増加列 $h_1, \ldots, h_n$ について対応する $M_{h_i}$ の列をfilterationという。

これはまさにMotivationのところで説明した解像度を変えたときのデータの列のことである。

barcode, BD図

各幾何学的特徴（後述；connected components, cycles, voidsなど）について、それらがどのタイミング（どの $h_i$ ）で発生し、どのタイミングで消失したかを表す図。

f:id:xuzijian629:20190720191531p:plain [1]

birthとdeathのペア $(b_i, d_i)$ を二次元平面で表したのがBD図。数直線で表したものがバーコード。BD図は $b_i \lt d_i$ なのですべての点は $y = x$ より上側にある。また、 $y = x$ 付近の特徴はノイズとされることが多い。

f:id:xuzijian629:20190720202029p:plain [3]

幾何学的特徴の見つけ方

これが要するにHomologyらしい。Homologyについての知見が足りなさすぎるのであまり書けることがない。いつかまとめ直すかもしれない

f:id:xuzijian629:20190720201855p:plain [3]

図、わかりにくいかもしれないが黄色は面を表していて、白は空洞だと思う。図では穴が1つ

参考文献

[1] パーシステント図に対する統計的機械学習

[2] パーシステントホモロジーとその応用

[3] Persistent Homology An Introduction and a New Text Representation for Natural Language Processing

感想

調べたら近年のICMLにわりと関連研究があってそれなりに人気っぽい。聞いたことなかったけど。一旦知ってしまうとWL kernelに応用しようとするアイデアはあまりに自然に思えるけどここ数年まったく出なくてこのタイミング突然出てきたのはわりとびっくり。WL kernelが強くなるとGraph Isomorphism Networkが強くなるのでこれの応用が秋のもろもろの学会で大量に出そうな予感がする。