読者です 読者をやめる 読者になる 読者になる

データサイエンティスト(仮)

元素粒子理論屋。いっぱしのデータ分析屋になるために修行中です。

トポロジカルデータアナリシス:ノイズのあるデータへ応用する

トポロジカルデータアナリシス 不定期

導入

不定期でトポロジカルデータアナリシス(TDA)に関する紹介をします。今回は、ノイズをもったデータへのTDAの応用方法を紹介します。

振り返り

データが与えられたとき、それを高次元空間の点の集まりとみなし、それらから図形を見立てる方法を紹介しました。
tekenuko.hatenablog.com

このとき、点の周りにある半径の球を考えたのですが、その半径はよしなにとっていました。半径を変えると、見立てられる図形も変化してしまいます。すると、前回見立てた図形が本当にデータの意味のある情報を取り出していたかが疑問としてでてきます。
f:id:tekenuko:20161013072544j:plain

上の図は大きいリングと小さいリングが1個ずつあるのが真の構造だった場合の例です。実際のデータは、この構造にノイズが上乗せされた状態で観測されます。ここから図形を見立てようとした場合、球の半径を小さくとってしまうと小さいリングの構造は見えますが、大きいリングの構造が見えない、逆に球の半径を大きく取りすぎると小さいリングの構造が見えなくなる、といったことが起こります。つまり、ノイズをもったデータから安定した「構造」を取り出すのは一筋縄ではいかないということです。

この問題に対してTDAはどう答えるのでしょうか。

基本的なアイデア

TDAの考え方の一つに、パーシステントホモロジーというものがあります。これは、大ざっぱに言うと、点の周りの球の半径を連続的に変えていったときの「図形の移り変わり」をまるっと見る考え方です。特定の半径を持つ球から見立てる図形だけでなく、半径を変えていったときのパターンを総合的にみて、データの持つ情報を引き出していきます。パーシステントホモロジーを定式化するためには、様々な前提が必要ですが、ここでは「図形の移り変わりをまるっと見るための量」と思っておきましょう。

半径を変えていったときの移り変わりの様について、図を見ながら考えていきます。
f:id:tekenuko:20161013073656j:plain

先ほどと同じように、大きいリングと小さいリングが1個ずつあるのが真の構造だった場合の例を考えます。データ点の周りに球を考えますが、その半径を一斉に、かつ連続的に大きくしていきます。すると、最初は細かい構造だったものが

  • 小さいリングの構造が見え始める
  • 大きいリングと小さいリングが1個ずつある構造が見える
  • 大きいリングのみの構造が見える
  • 穴がなくなる

と移り変わります。ただし、それぞれの構造は、出現している区間の大きさに違いがあります。TDAでは、半径を大きくしていったときにすぐ構造が変わってしまうものをノイズ的なもの、構造が安定的(長い区間同じ構造を保っている)なものをデータの本質的な情報、といった見方をします。上の例だと、半径を大きくしていったときに、大きいリングと小さいリングが1個ずつある構造が比較的安定して存在していることが見えた場合、この構造が本質であったと判断するわけです。

パーシステント図

構造の移り変わりを構造の「生成」と「消滅」という見方で可視化したものを、パーシステント図といいます。ここでいう構造とは、例えば一次元ホモロジー群の生成元のことを指しますが、これはざっくり「何個かの穴をもったものを表現する量」のことです。

今、球の半径を一斉に、かつ連続的に大きくしていったとします。大きくしていく途中で、新しい構造がでてきた半径(Birth)と、その構造が消えた(つまり別の新しい構造が生まれた)半径(Death)を記録していきます。それらをプロットすると、下の図のようになります。
f:id:tekenuko:20161013075300j:plain

すぐ生成されてすぐ消滅する量は、それぞれの半径の大きさの差が非常に小さくなります。そのため、Death - Birth(寿命)が0に近い、つまり対角線上に近くなります。一方で、長い区間で安定的な構造は、Death - Birthが大きくなるため、対角線上から離れたところに位置します。先ほどの例だと、大きいリングと小さいリングが1個ずつある構造が対角線上から離れた場所にプロットされた場合、この構造が本質であったと判断します。

おわりに

非常にざっくりですが、TDAの考え方の一つであるパーシステントホモロジーの紹介をここではしました。このような考え方の応用先ですが

  • クラスタリング : 最適なクラスタ数を安定的な構造と結びつける
  • 構造解析・画像認識 : ノイズのあるデータから本質的な情報を抽出

といったものが素朴にはありそうです。ただし、実際の応用の事例はまだ多くありません。しかしながら、TDAはデータに対する新しい見方を与えるものであり、これが既存手法と比較してメリットがあることがわかれば、一気に世の中に広まるポテンシャルを秘めていると期待しています。

今回紹介したパーシステントホモロジーは、TDAの考え方の一つにすぎません。例えば、AYASDIというTDAベンチャー企業は、「Mapper」という別の手法を使用しているようです。幸い、パーシステントホモロジーとMapperの両者ともにソフトウェアが存在しています。TDAに関して更に知りたいという方はソフトウェアを使う、Mapperについて論文やAYASDI社の事例を調べてみる、といったことをやってみると良いのかな、と思います。