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

Topological Data Analysis って何

位相的データ解析

Topological Data Analysis (TDA;位相的データ解析)というのがあると思います。でも何だかよくわかりません。
ドーナツの穴といわれても腑に落ちません。しかしトポロジーとかホモロジーとかホモトピーといわれてもわかりません。
関手などの近代数学の応用らしいですが、近代数学を知らないのでヒントになりません。あと関手が変換できません。
ただ何のために何をするのかを知りたいのですが、浅学ゆえに巷の情報から直観を得られないので、考えたいと思います。
自分なりのまとめ
2016-11-26 追記 》スライド2枚でいうと以下。
f:id:cookie-box:20161126161508p:plain:w600

f:id:cookie-box:20161126161604p:plain:w600

  • TDA は、データを特徴付ける「形状」を抜き出したいという願い。「形状」とは「変わらない構造」:
  • TDA では、そのような「形状」とは「データを何らかの方法で図形化したときの、その図形のつながり具合=位相構造」と考える。
    • 1つの入力データ内のつながりの構造というのは、深層学習などで明示的に扱わないところと思われる。
  • 「この図形には1つ穴が開いている」「この図形は3つのパーツに離れている」のような位相構造は、人間の直観には認識が容易でもその数学的定義は難しい。「連結(0次元の穴)」「穴(1次元の穴)」「空洞(2次元の穴)」のような位相的構造の定義は、代数的トポロジーという分野が与えてくれる。つまり、図形をホモロジーという関手(特殊な関数)に入れると、n次元の穴の数がわかる。
    ホモロジーは図形を(例えば)ベクトル空間に対応させるだけでなく、図形の間の連続写像もベクトル空間の間の線型写像に対応させる、という意味で特殊な関数になっている。図形だけをより扱いやすい集合に対応させるだけでなく、写像も対応させることで図形の性質についてもっと調べられるようになる。この関手という概念は近代数学で発展したもの。
  • TDA では、単なるつながり以上の形状も識別できるパーシステント・ホモロジーという応用分野を主なツールとする。パーシステント・ホモロジーでは、対象データについてパラメータ  \varepsilon に依存する図形を構築し、 \varepsilon を動かし、より広範囲で観測できる位相構造をそのデータの性質と認め、狭い範囲でしかみられない位相構造はノイズ、という考え方をする。



TDA について Wikipedia には何て書いてあるの?: Topological data analysis - Wikipedia

  • 「一般に高次元であったりノイズが多かったりするデータは扱いづらいけど、TDA はデータにどんな距離を入れるかに依存せず、次元削減ができて、ノイズにも強い」と。「位相的データ解析」というくらいだから位相を見るのであって、距離は見ないのかもしれません。
    • この記事を拝見すると: 位相的データ解析(Topological Data Analysis)について | ALBERT Official Blog
      • 文字の「A」「L」「B」の穴の数を、それぞれの文字からサンプリングした点群の半径を太らせて行くことで検出しています。なるほどこの方法なら「A」の文字が歪んでいようと、多少くせ字であろうと、隙間があろうと、「穴1つ」と判定してくれることが期待されます。情報を穴の個数に落とせば、グレースケールのピクセル画像よりはるかに低次元です。ただ穴の個数だけだと、他の多くのアルファベットも同一視されてしまいますが。
      • 文字の例の前には、やはり個々のデータ点を太らせていく方法でクラスタ数が3であることを検出しています。データ点全体を図形の芯と捉え、全ての点を太らせていくときに現れる「穴」「連結」という位相的性質をとらえると丸めていいんでしょうか。太らせるという操作に否応なくデータに入れる距離は関わってくるようですが。

  • TDA の背景に、「人間って画像を見てその各ピクセルを処理するのではなくて、もっとずっと低次元な特徴をとらえているんじゃないの?」というのもあるようですね。認知脳科学には暗いのでよくわからないですが。「神経結合をつくればいいんじゃないの?」という深層学習と対比させられて語られるのもその辺りの背景なんでしょうか。まあそれで、低次元な特徴というのは位相で測れるものではないかということですね。

位相って知ってる。ドーナツとコップが同じやつでしょ?

  • それ小学生の前でも同じこと言えるのでしょうか。
    小学生「位相って何?」
    あなた「穴の開いたドーナツと、1つ取っ手の付いたコップが位相的には同じになるんだよ。」
    小学生「いや、位相的に主張できることではなく位相とは何かを訊いているんだけど。あと穴の定義は?」
    これでは近所の小学生もごまかされないに違いありません。ちゃんと確認しましょう。
  • 位相空間  (X, \mathcal{O}) とは:  X の上に "開集合" たち  \mathcal{O} を定義したもの。
    •  \mathcal{O} がどんな性質を満たすとき "開集合" たちと認めるかは、Wikipedia でも参照。 位相空間 - Wikipedia
    •  X \mathbb{R} でも  \{1,2,3,\cdots \} でも \{ ボブ、アリス、クリス \} でも何でもいい。"開集合" を決めればよい。
    • "開集合" をつかってはじめて、連続な写像とは何か、収束とは何かがいえる。なお微分はできない。
      • 開集合の逆像が開集合になるなら連続な写像という。
      • x の任意の近傍に対して、点列 \{x_i\} があるインデックス以降で近傍に入るなら x に収束するという。近傍とは  X の部分集合であって x を含む開集合を包含するもの。
    • 位相空間  (X, \mathcal{O}_X), \;(Y, \mathcal{O}_Y) と、写像  f: X \to Y があった場合、任意の  Y 上の開集合の f による逆像が  X 上でも開集合になっていれば(任意の  Y 上の開集合について下図の一番左のようになっていれば)  f は連続である。左から2番目と3番目の  f は連続ではない。全射単射と連続は関係ない。
    • f全単射であって ff^{-1} も連続であるとき、f同相写像といい、X Y の間に同相写像があるとき X Y を同相という。下図一番右のように、中身が詰まったドーナツの形状をした X \subset \mathbb{R}^3 とコップの形状をした Y \subset \mathbb{R}^3 は同相である。つまり、ドーナツからコップへの全単射が存在し、コップ上の開集合の逆像はドーナツ上の開集合になり、ドーナツ上の開集合の像もコップ上の開集合になる。 f:id:cookie-box:20161119202727p:plain:w700
      ※ わかりやすさのため開集合を両端が白丸の区間のように描いているが、開集合の "姿" は与えた定義による。

じゃあ穴って何なの?

  • 「穴とは何か」について、ドーナツと同相であれば、ドーナツのような穴をもつことは示される。ただ、ドーナツのみから、「ドーナツは穴を1つもつ」を議論するのは難しい。窓のないドーナツ型の水槽の中に住んでいて水槽の外の世界を知らない魚が、「あーこの水槽真ん中に穴開いてんな」と思うのは難しい。
  • ただ、数学には代数的トポロジーという分野がある。代数的位相幾何学 - Wikipedia
    この分野では任意の開集合などを考えず、もっと扱いやすい図形(単体的複体など)を考えて位相構造を議論する。すると穴に代数的な定義(ホモロジー群)が与えられる。ホモロジー (数学) - Wikipedia

Wikipedia の続きには何てあるの?

  • TDA は functorality(=関手性)をもつ」らしい。関手 - Wikipedia
    • 関手は圏(=対象+射)から圏への対応。たとえば写像は対象を対象に対応させるのみだが、関手は対象を対象に対応させるのに加え、射も射に対応させる。

具体的に、どうやってデータから位相構造を調べるの?

  • パーシステント・ホモロジーという応用分野の手法による。
    • 手続きは Wikipedia に詳しい。この資料の最後の方に紹介されている。トポロジーは応用できるか?
    • 下図に一例を示すと、「R」という文字の画像データから点をサンプリングし、個々の点を中心に半径 \varepsilon の円盤を描画する。\varepsilon を大きくしていったとき全体としての図形がどう変遷していくかをみると、穴の数  k_1 は 0 → 1 → 2 → 1 個と移り変わる。この中で最も persistent、つまり、持続していたのは  k_1 = 1 のフェーズである。なので、 k_1 = 1 と判断する。
      f:id:cookie-box:20161120210734p:plain:w400
      \varepsilon\to\to\to\to
      H_10\mathbb{Z}\mathbb{Z} \oplus \mathbb{Z}0
      • 2016-11-23 追記 》不正確であったので追記すると、円盤を重ねたものを「全体としての図形」と言っているのではなく、下図のように「2円が交わったとき辺で結ぶ」「3円が交わったとき面を張る」というルールでつくった図形を「全体としての図形」としており、この図形のホモロジーをみている。
        f:id:cookie-box:20161123171547p:plain:w600
    • Wikipedia だけでももっと別の persistence を見る手法が紹介されているようですが、時間がなかったのでここまで。

参考文献