位相的データ解析(Topological Data Analysis)について

データ分析部の藤本、今井です。今回は共同で位相的データ解析(Topological Data Analysis)についてのご紹介をしようと思います。

位相的データ解析とはデータの集合をトポロジーと呼ばれる「柔らかい」幾何を用いて解析する手法です。幾何学を使った統計学ですと情報幾何学と呼ばれる分野がありますが、こちらはデータの集合ではなく確率分布に対して微分幾何という「硬い」幾何学を用いた分野です。

位相的データ解析は最近ホットな分野で、ビジネス業界でもこの位相的データ解析に注力している会社のAyasdiが総額100億円近く資金調達しており非常に期待されています。位相的データ解析の実データへの応用としては画像認識などがあります。

さて、「柔らかい」幾何、トポロジーとは何でしょうか?通常、私たちは以下の図形は別のものと見なしますが、トポロジーの世界では図形を伸ばしたりなど変形させたものも同じ図形と見なすため、これらの図形を全て同じものだとします。

top1

ではどういった図形を異なる図形と見なすのでしょうか。トポロジー的に上記と異なる図形の1つの例として、上記の図形に1つ穴を開けた図形(下図参照)は異なると見なします。ただし、穴を空けた図形同士は同じものだと見なします。また、「円が1つ」の図形と「円が2つ」の図形は異なるものだと見なします。

top2

このように円と三角を同じと見なすことでどういった利点があるのでしょうか。1つには余計な情報を落とすことで、図形の本質を見ることができるということがあげられます。例えば、以下の文字を見てください。

top3

私たちはこれら全ての文字をALBERTだという認識できます。フォントによって丸みを帯びたり角ばったりしていますが、文字の認識においては文字の太さや文字が丸いか角ばっているかは本質ではなく、細い線と太い線、円と角を同じものだと思っても問題ありません。ここからも位相的データ解析が画像認識で使えそうだと想像がつくかと思います。

以下の図の左上にある5つの点をデータの集まりだとしましょう。ここから右上のように点の周りに円を作り、その円を少しずつ大きくしていくことを考えましょう。少し大きくしただけだと5つの円がある状態ですが、さらに大きくしていくと左下のように円が重なっていきます(左下は真ん中に穴が1つだけ空いているので、円盤とトポロジー的に同じ図形となります)。そこからさらに大きくすると右下のように全て繋がり、1つの円とトポロジー的に同じ図形となります。

phom1

これを用いて何ができるのでしょうか?まず始めに思い浮かぶことはクラスタ分析のクラスタ数の決定ができそうです(古典的にもSilhouette基準やGap基準など既に色々提案されています)。

例として以下のデータで考えてみましょう。

clust1

この例だと2次元のデータなので可視化すればすぐに3つの集まりだと分かります。位相的データ解析でどうこれを捉えるかというと、データの点の周りに小さい円を描き、その円を大きくしていきます。そうすると円の半径の途中まではそれぞれの色でどんどんくっついていきますが、各色でくっついた後はしばらく3つの塊の状態が続きます。そのままどんどん大きくしていけば最終的には1つの塊になります。この「3つの塊の状態が続く」ことを捉えれば、自動的にクラスター数が決定できそうです。また、このケースでは2次元ですが、位相的データ解析は高次元のデータに対しても適用可能なので、高次元で簡単に可視化できないようなケースで特に活躍できそうです。

実際に上記のことをライブラリを用いてやってみましょう。位相的データ解析を行えるライブラリはいくつかありますが、今回はRのTDAというパッケージを用います。

install.packages("TDA")
library(MASS)
library(TDA)

#データの生成
mu1 <- c(0, 0)
Sigma1 <- matrix(c(1, 0.3, 0.3, 1), 2, 2)
x1 <- mvrnorm(30, mu1, Sigma1)
mu2 <- c(8, 0)
Sigma2 <- matrix(c(1, -0.2, -0.2, 1), 2, 2)
x2 <- mvrnorm(30, mu2, Sigma2)
mu3 <- c(4, 6)
Sigma3 <- matrix(c(1, 0, 0, 1), 2, 2)
x3 <- mvrnorm(30, mu3, Sigma3)
x <- rbind(x1,x2,x3)

#TDAによる計算
Diag <- ripsDiag(X = x, maxdimension = 0, maxscale = 5, library = "Dionysus")

#可視化(バーコードプロット)
D <- Diag[["diagram"]]
n <- nrow(D)
plot(c(min(D[,2]), max(D[,3])-1.5), c(1,n + 1), type="n", xlab = "radius", ylab ="", xlim=c(min(D[,2]), max(D[,3])-1.5), ylim=c(1, n + 1), yaxt ='n')
segments(D[,2], 1:n, sort(D[,3]), 1:n, lwd=2)

 

barcode_plot_H0

上記はバーコードプロットと呼ばれているものです。この図の見方としては、x軸の半径の大きさに対して、そこで縦線を引いた時にバーコードの線がいくつあるかを数えることで、例えば半径の大きさが2.5の時は3つの塊、3.5の時は1つの塊であることが分かります。この図から分かることは、半径が2より少し小さいところから3つの塊になり、そこから半径を大きくしていってもしばらく変化していないので、このデータは3つの塊からできているであろうと予想できます。

上記では塊の数を数えましたが、穴の数を数えるということもできます。穴の数を自動的に数えられれば、例えば「A」「L」「B」という文字を識別する時に、それぞれ穴が1個, 0個, 2個という情報を自動的に取得できるため、文字の識別するための特徴量として使えそうです。また、点の周りに円を描いて各点を大きくしてあげることで、薄れた文字の認識をする時に役立ちそうです。実際に以下のドットの文字を表現したデータから穴の数を計算してみましょう。

image_ALB

library(TDA)

#データの生成
image_A <- cbind(x= c(0,1,2,3,4,5,6,7,8,9,10,3.5,5,6.5) * 0.6 + 2,
 y =c(0,3,6,9,12,15,12,9,6,3,0,6,6,6)*0.55 + 1.25)
image_L <- cbind(x = c(0,0,0,0,0,0,0,0,0,1,0.25,0.5,0.75,1.25,1.5) * 4 + 2 ,
 y = c(0,1,2,3,4,5,6,7,8,0,0,0,0,0,0) + 1.25)
image_B <- cbind(x = c(0,0,0,0,0,0,0,0,0,1,1,1,1.25,1.25,1.5,1.5,1.5,0.25,0.25,0.25,0.5,0.5,0.5,0.75,0.75,0.75,1.25,1.25) * 4 +2,
 y = c(0,1,2,3,4,5,6,7,8,0,4,8,5.3,6.6,1,2,3,0,4,8,0,4,8,0,4,8,3.5,0.5) + 1.25)

#TDAによる計算
Diag_A <- ripsDiag(X = image_A,maxdimension = 1,maxscale = 5)
Diag_L <- ripsDiag(X = image_L,maxdimension = 1,maxscale = 5)
Diag_B <- ripsDiag(X = image_B,maxdimension = 1,maxscale = 5)

#可視化(パーシステント図)
plot(Diag_A$diagram)
plot(Diag_L$diagram)
plot(Diag_B$diagram)

以下が得られた結果となります。(左から「A」「L」「B」の結果となります)

p_ALB

こちらの見方としては、各点の周りの円の半径の大きさを大きくしていった時に、穴が生まれた時(Birth)の半径の大きさと、穴がなくなった時(Death)の半径の大きさをプロットしたものです。この図はパーシステント図と呼ばれています。穴の数は赤い三角で表現されています。ここからすぐにそれぞれの文字の穴の数が1個、0個、2個ということが分かります。

位相的データ解析の実データへの応用としては上記のように画像認識がよく知られていますが、ここでは他に応用できるかを考えてみたいと思います。例えば複数のモデルから複数のデータ集合が生成された時に、生成モデルごとに分類したい場合を考えましょう。この場合、福水先生が提案されているようなカーネル法による分類が応用できそうです。一言で説明すると、一つのパーシステント図にカーネル法で変換した先の再生核ヒルベルト空間の一つの点を対応させ、この再生核ヒルベルト空間上の点の集合について変化点検出を行い、相転移の温度を推定することで分類を行うことが可能となりそうです。

位相的データ解析はまだできたばかりの分野でその実力も未知数ですが、実力次第ではディープラーニングのように一世を風靡する分野になるかもしれません。位相的データ解析を学んでみたくなった人のために以下の文献を挙げておきます。

参考文献
タンパク質構造とトポロジー ―パーシステントホモロジー群入門― (シリーズ・現象を解明する数学) 共立出版 

この本はタンパク質の構造ですが、使用されているパーシステントホモロジーについての入門にもなります。

TOPOLOGY AND DATA

元スタンフォード大の教授で、現在はAyasdiに在籍しているGunnar Carlsonによる解説論文。彼の動画による位相的データ解析の解説もお勧めです。

BARCODES: THE PERSISTENT TOPOLOGY OF DATA

バーコードプロットの良い解説です。