Persistence Weighted Gaussian Kernel
for Topological Data Analysis
福水 健次
統計数理研究所 数理・推論研究系／統計的機械学習研究センター（兼）総合研究大学院大学, 物質・材料研究機構

ERATO感謝祭 SeasonIII

2016年8月9-10日 NII1

• 発表内容
Persistence Weighted Gaussian Kernel for Topological Data Analysis

by Genki Kusano, Yasuaki Hiraoka, Kenji Fukumizu
International Conference on Machine Learning (ICML2016), June 2016

草野元紀（東北大,D1）

平岡裕章（東北大）

Acknowledgements:• JST・CREST 現代の数理科学と連携するモデリング手法の構築（総括：坪井俊）「ソフトマター記述言語の創造に向けた位相的データ解析理論の構築」（平岡裕章・代表）• JST・イノベハブ構築事業 物質・材料研究機構 「情報統合型物質・材料開発イニシアティブ（Mi2i）」(拠点長：寺倉清之）
2位相的データ解析 (TDA)• TDA: データの位相的・幾何的情報を抽出するための新しい方法論

キーテクノロジー ＝ パーシステントホモロジー（Edelsbrunner et al 2002; Carlsson 2005)• 背景• データの質の変化．
複雑な幾何的構造を持つデータを扱う必要• 計算トポロジーの発展．
位相的不変量の計算機による計算が実行可能に．
3

TDA: さまざまな応用
複雑な幾何構造を持つデータ  特徴ベクトル／記述子の導入が困難
脳科学

物質・材料科学
生化学

コンピュータビジョン

ガラス相

液相

脳動脈の木構造年齢／性別による構造の違い(Bendich et al. AoAS 2016)

タンパク質の構造変化
構造による機能の違い(Kovacev-Nikolic et al.
SAGMB 2016)

形状の記述(Reininghaus et al. CVPR 2015)

非晶質の記述(Hiraoka et al. PNAS 2016)
4

講演の概要• 位相的データ解析の概要• パーシステント図のデータ解析• 物質科学への応用5

位相≅6トポロジー ＝ 切り貼りせずに連続的に移りあう図形は「同じ」とみなす
代数的位相幾何 ＝ 三角形 単体）による図形の記述  代数的扱い
代数的操作

𝑋≅

代表例： ホモロジー群 𝐻(𝑋)
各次元の本質的に異なる「穴」を捉える．

点，線，三角形の集まりとそのつながり具合を代数的に記述「穴」の個数ホモロジー群の生成元＝ 本質的に異なる「穴」

位相的不変量

≅≅
≅

≅
≅

dim
𝐻0 (𝑋)dim
𝐻1 (𝑋)

連結成分

ringdim
𝐻2 (𝑋)

1001

10101cavity7統計的データへのトポロジーの応用?
真の幾何的構造

半径 𝜀 の球（𝜀 - ball）の和集合を考えることにより真の構造を捉えよう(e.g.多様体学習)

ノイズのある有限個のサンプル

小さい 𝜀  不連続な集合

適切な𝜀（スケール）の設定は難しい！

大きい 𝜀  小さいリングはつぶれてしまう

8パーシステントホモロジー (PH, Edelsbrunner 2002)• すべての 𝜀 を同時に考える．
𝑑,𝑋 = 𝑥𝑖 𝑚⊂
𝐑𝑖=1𝑋𝜀 ≔∪𝑚𝑖=1 𝐵𝜀 (𝑥𝑖 ) （𝜀 球の和集合）

異なるパラメータ 𝐻𝑞 𝑋𝜀𝑖 , 𝐻𝑞 (𝑋𝜀𝑗 ) （𝜀𝑖 < 𝜀𝑗 ）に対し，ホモロジー生成元の関係づけが可能（発生，対応，消滅）  各生成元の発生・消滅時刻が定まる．（数学的な定理）

例： 1次元ホモロジー群 𝐻1 (𝑋) の生成元の発生と消滅

9• PHの２つの表現法（等価な表現）

パーシステント図（Persistent diagram, PD）

バーコード
各生成元のbirthからdeathまで線分を引く．

𝛼𝜀TDA: データの記述子として使う

安定した構造の「穴」 は長いインターバルで存在するはず

各PH生成元の発生(𝑏)，消滅(𝑑)時刻を，２Dグラフ上の点 (𝑏, 𝑑) で表したもの．

各次元で，バーコード / パースステント図を考える．

• PHの厳密な定義，計算法は本講演では扱わない (Carlsson 2009; 平岡2013）10

位相を超えて• パーシステントホモロジーは，「位相」以外の情報も含んでいる
ＰＨには位置情報などの幾何情報も含まれる

1次元PHのバーコード𝜀𝜀11パーシステント図の統計的データ解析

12• 統計的な位相的データ解析のスキーム（Kusano, Hiraoka, F. 2015; Reininghaus et al CVPR2015; Kwitt et al NIPS2015; Fasy et al 2014）

多くのパーシステント図

多くのデータセットPHの計算どのように行うか？

PD1
PD2

パーシステント図に対するデータ解析

PD3
既存のソフトウエア
e.g. CGAL / PHAT

CGAL: The Computational Geometry Algorithms Library
http://www.cgal.org/
PHAT: Persistent Homology Algorithm Toolbox
https://bitbucket.org/phat-code/phat

記述子として使う
PDn13パーシステント図のベクトル化• 正定値カーネルによるPDのベクトル化• パーシステント図： 𝐷 = 𝑥𝑖 ∪ Δ （点の重複度も考慮）
𝑥𝑖 ∶ 生成・消滅時刻 𝑏, 𝑑 ∈ 𝐑2 𝑑 > 𝑏• PD = 離散測度と思える 𝜇𝐷 ≔𝑥𝑖 ∈𝐷∖Δ 𝛿𝑥𝑖• PDのカーネル埋め込みℇ𝑘 :𝜇𝐷 ↦ ∫ 𝑘 ⋅, 𝑥 𝑑𝜇𝐷 𝑥 =𝑖 𝑘(⋅, 𝑥𝑖 )e.g. ガウスカーネル∈ 𝐻𝑘𝑖 𝛿𝑥𝑖 ↦ベクトル化
𝑖 exp−𝑦−𝑥𝑖 22𝜎2

ベクトルデータに対する多くのデータ解析手法が適用可能 PCA, CCA, etc
カーネル法なので，グラム行列計算に還元（カーネルトリック）．
14

Persistence Weighted Gaussian Kernel：
PD用のカーネル（Kusano, Hiraoka, Fukumizu, 2015）
アイデア：対角線に近い生成元はノイズの可能性が高い 重みを小さくする

𝑘𝑃𝑊𝐺 𝑥, 𝑦 = 𝑤 𝑥 𝑤 𝑦 exp −Pers(x1)𝑦−𝑥 22𝜎2

重み関数 𝑤 𝑥 = 𝑤𝐶,𝑝 𝑥 ≔ arctan 𝐶Pers 𝑥 𝑝(𝐶, 𝑝 > 0)
Pers 𝑥 ≔ 𝑑 − 𝑏𝑥 ∈ { 𝑏, 𝑑 ∈ 𝐑2 |𝑑 ≥ 𝑏}
• Stabilityを有することも示される（𝑝 > 次元）

点集合が距離の意味で微小に動いたとき， のカーネル表現もRKHSノルムの意味で微小にしか動かない．
（ガウスカーネルでは未解決）

Pers15

物質科学への応用

16シリカ(SiO2 )の液相-ガラス相SiO2 を液体から急冷すると，ガラス状態になる．
目的 液相からガラス相に転移する温度を特定したい
データ: SiO2分子動力学（MD）シミュレーション．
温度を変えて，80セットの３次元原子配置データを取得（ある時刻でのスナップショット）• 原子の3次元配置データ（点集合）から，PD図を計算 (Nakamura et al 2015 Nanotechnology)• Si と O 原子では，異なる半径の球を用いた．

• 物理学的方法：エンタルピー曲線を描いて，微分の推定値の不連続点を推定．正確な推定は難しい．

• 提案法：PD図のカーネル埋め込みに対する変化点検出問題として定式化．カーネル変化点検出法（）を利用．

𝑌𝑡𝑡
変化点

17原子配置（ＭＤシミュレーション）
液相

ガラス相

パーシステント図
液相

ガラス相

18

• SiO2の相転移点検出

検出された変化点 = 3100K

Δ𝑡Enthalpyによる方法: [2000K, 3500K]

PSSK: Reininghaus et al. (2015) の類似のカーネル
計算時間，識別能力でPWGKが有利．

19

• 低次元表現： カーネル主成分分析のカーネル埋め込み（ベクトル）に対して，さらにカーネル主成分分析を行い，２次元で表現．
液相
液相-ガラス相は，変化点検出の結果に基づいて色付けした．
スナップショットからの液相-ガラス相判定が可能かは，物理学では未決着．

ガラス相20まとめ• 位相的データ解析• キー技術：パーシステントホモロジー• 複雑な幾何的形状を持つデータに対し，幾何形状に基づく記述子を定める．
• 𝜀 球をすべての 𝜀 について考える• 位相以外の幾何情報も含む．

• 機械学習的アプローチ• 多数のパーシステント図に対する統計的データ解析• カーネル法により，パーシステント図を「ベクトル表現」• パーシステンス重み付きガウスカーネル： ノイズの影響を考慮したカーネル• 多くの標準的データ解析手法が系統的に利用可能• 主成分分析，正準相関分析，判別分析，識別，クラスタリング，• 解析の結果は比較的ブラックボックス
21

参考文献
Kusano, G., Fukumizu, K., Hiraoka, Y. (2016) Persistence weighted Gaussian kernel for topological
data analysis. Proc. 33rd Intern. Conf. Machine Learning (ICML2016), pp. 2004–2013, 2016
http://jmlr.org/proceedings/papers/v48/kusano16.html
Edelsbrunner, H., Letscher, D., and Zomorodian, A. (2002) Topological persistence and simplification. Discrete andComputational Geometry, 28(4):511–533, 2002.
Carlsson, G. (2009) Topology and data. Bull. Amer. Math. Soc., 46(2):255–308. http://dx.doi.org/10.1090/S02730979-09-01249-X .
平岡. タンパク質構造とトポロジー：パーシステントホモロジー群入門. 共立出版, 2013.
Nakamura, T., Hiraoka, Y., Hirata, A., Escolar, E. G., Matsue, K., and Nishiura, Y. (2015) Description of mediumrange order in amorphous structures by persistent homology. Proc. Natl. Acad. Sci. USA. vol. 113 no. 26,7035–7040. doi: 10.1073/pnas.1520877113
Nakamura, T., Hiraoka, Y., Hirata, A., Escolar, E. G., and Nishiura, Y. (2015) Persistent homology and many-bodyatomic structure for medium-range order in the glass. Nanotechnology, 26 (304001).
Reininghaus, J., Huber, S., Bauer, U., and Kwitt, R. (2015) A stable multi-scale kernel for topological machinelearning. Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 4741–4748.
Kwitt, R., Huber, S., Niethammer, M., Lin, W., and Bauer, U. (2015) Statistical topological data analysis - a kernel
perspective. Advances in Neural Information Processing Systems 28, pp. 3052–3060.
Fasy, B. T., Lecci, F., Rinaldo, A., Wasserman, L., Balakrishnan, S., and Singh, A. (2014) Confidence sets for
persistence diagrams. The Annals of Statistics, 42(6):2301–2339.
Harchaoui, Z., Moulines, E., and Bach, F. R. (2009) Kernel change-point analysis. Advances in Neural Information
Processing Systems 22, pp. 609–616.
22