Deep Learning の次は、TDA 「トポロジカル・データ・アナリシス」 (Topological data analysis) が来る ? ~ その概要と、R言語 / Python言語 実装ライブラリ をちらっと調べてみた

  • 481
    いいね
  • 0
    コメント

人工知能やデータ解析の領域で、膨大な量のデータから、物体概念(物体識別)や音声・体の運動スキーマ概念を自動的・自律的に獲得できる可能性をもった手法として、Deep Learning(ディープ・ラーニング、「深層学習」)と総称される手法が注目を集めています。

こうした中、一部の研究者やベンチャー企業の経営者・エンジニアの中には、このDeep Learningのさらに先をいくデータ解析手法として、TDA:トポロジカル・データ・アナリシス (Topological data analysis) と呼ばれる手法に着目している方たちがいるようです。

Deep Learningと同じく、人間が脳を使って、五感で得た周囲や自分の体についての感覚情報から、どのようにして周囲の環境空間に対する認識イメージや、物体概念、みずからの身体概念を得ているのか?という「問い」に対して、統計学や確率論のアプローチではなく、数学の一領域であるトポロジー(位相幾何学)の知見から応えようとするなかから、生まれてきたようです。

この記事では、Deep Learningのさらにその先をいく(可能性をもつ)データ解析手法としてのTDAについて、概要を解説したウェブサイトと、手元のPCマシンで、実際に R言語 や Python言語 で実データをもとに動作や精度を検証していくための実装環境についての参考ウェブサイトにインデックスを張ってみました。


TDA: トポロジカル・データ・アナリシス とは何か?

(Wikipedia 英語版)

Topological data analysis (TDA) is a new area of study aimed at having applications in areas such as data mining and computer vision. The main problems are:

how one infers high-dimensional structure from low-dimensional representations; and
how one assembles discrete points into global structure.

The human brain can easily extract global structure from representations in a strictly lower dimension, e.g. we infer a 3D environment from a 2D image from each eye. The inference of global structure also occurs when converting discrete data into continuous images, e.g. dot-matrix printers and televisions communicate images via arrays of discrete points.

The main method used by topological data analysis is:

Replace a set of data points with a family of simplicial complexes, indexed by a proximity parameter.
Analyse these topological complexes via algebraic topology — specifically, via the theory of persistent homology.[1]
Encode the persistent homology of a data set in the form of a parameterized version of a Betti number which is called a persistence diagram or barcode.[1]

(試訳)

トポロジカル・データ・アナリシス(TDA)は、データ・マイニング や コンピュータ・ビジョン(CV)の分野での応用を念頭においた新しい研究領域です。

この解析手法が解明しようと取り組んでいる問題は、たとえば、人間が 眼球(網膜)で得た2次元の視覚情報データから、3次元の空間構造認識を形成する際に、どのようにして、低次元のデータ構造で表現される対象(物)から、高次元のデータ構造体を獲得するのか、といった問題です。

上記の例のように、人間の脳は、こともなげに(容易に)低次元のデータ対象から、(高次元で)広域的(global)なデータ構造体を形成する能力を持ちます。この能力は、離散的な(トビトビに互いに離れた)複数の点の集合をみて、連続的な形(輪郭)を帯びた像を認識(イメージ)する際にも発揮されるものです。


似た名称 の 領域 に、「情報幾何学」というものがあるようです。こちらは、「トポロジー」を用いたTDA とは別物のようです。

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

理化学研究所の甘利先生が創始された「情報幾何学」については、以下が参考になります。

riken.PNG

概要

KL-divergence のある種の一般化である Bregman divergence (U-divergence)を用いることによってboosting アルゴリズムを包括的に捉え,その幾何学的意味を考えるための方法論を紹介する.

( 情報幾何学 紹介 以上 )


Topological data analysis という 分 野 がある 。 多 くの 数 値 デ ー タ を point cloud すな わち Euclid 空 間 に 配 置 された 点 の 成 す 離 散集 合 とみなし , それを topological な 道 具 で 調 べることによりその デ ー タ の 持 つ 情 報 を 取 り 出 すことを 研究 する 分 野 , と 言 っ てよい だろう 。
そのような topological な 道 具 として 最 も 有名 なのは persistent homology で ある 。


実際に上記のことをライブラリを用いてやってみましょう。位相的データ解析を行えるライブラリはいくつかありますが、今回は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)
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)

【 データとデータの間の類似性(similarity)を、自動的に数値化・定量化(quantify)する手法(アルゴリズム)として紹介されている 】

new.PNG

new2.PNG

【 分類問題(クラスタリング問題)も、位相幾何学の世界の言語で、データ(点)とデータ(点)どうしを連結する(connect)させてつなげることで、つながったデータどうしを分類されたデータ集合(個々のクラスター)であるとみなしている?らしい 】

new3.PNG

new4.PNG

new5.PNG

new6.PNG


(以下、上記からスライドを一部 抜粋)
【 TDA は、クラスタリング手法などと同じ「教師なし学習」に位置づけられるとのこと 】

add1.PNG

add2.PNG

add3.PNG

add4.PNG

add5.PNG

add6.PNG

add7.PNG

add8.PNG

add9.PNG

add10.PNG

add21.PNG


(以下、上記からスライドを一部 抜粋)

【データセット事例】

1.PNG

(データ項目)

2.PNG

データには、20件の「ニュース・グループ」についての属性項目がある

3.PNG

4.PNG

( TDA分析モデルに渡すために、データを以下の流れで加工 )

5.PNG

【 データの「構造」を、数学の位相幾何学の言語で解釈して、表現して得られた結果 】

6.PNG

( 全体像 )

7.PNG

【 位相幾何学構造のなかの「ある特定の領域」が、「ある特定のニュースグループ」のデータが位置している領域 に対応しているらしい 】

8.PNG

( Ayasdi社の「クエリ言語を発行しないでデータ検索できる」DBは、このようにして、データを位相幾何学構造に変換したうえで、その構造体のなかの「特定の領域」=特定抽出条件に絞って得られる目的のデータ部分集合 を得る仕組み?と思われる )

9.PNG

10.PNG

【 上記のPower Point資料には、TDA の精度を向上(enhance)させるために、Deep Learningをつかって、さらに手を加えている模様 】

11.PNG

12.PNG


【 TDA が、機械学習のフレームワークを提供しうることが説明されている 】

キャプチャ.PNG

【 分析領域と分析手法・指標~「統計解析」と「機械学習」と"Geometry"(位相幾何学)との対応関係? 】

キャプチャ2.PNG


( 以下、平岡 PDF より一部を引用して転載 )

hiraoka_1.PNG

hiraoka_2.PNG

( 以下、坂田ほか(東京大学) SlideShareより一部を引用して転載 )

TDA_1.PNG

TDA_2.PNG

TDA_3.PNG

TDA_4.PNG

TDA_5.PNG

TDA_6.PNG

TDA_7.PNG

TDA_8.PNG

TDA_9.PNG

TDA_10.PNG

TDA_11.PNG

TDA_12.PNG

TDA_13.PNG

TDA_14.PNG

TDA_15.PNG


日本国内ベンチャーで、社内勉強会を開いている会社があるらしい

( 会社ウェブサイト )
株式会社ABEJA (アベジャ) ABEJA Inc. (本社:東京港区六本木 / 代表取締役:岡田 陽介 氏)

ABEJA.PNG

( 同社 紹介記事 )
The Wave(2015年4月7日付記事)「国内AIトップ研究者とのタッグで世界最先端狙う26歳経営者 ABEJA岡田陽介氏」

Googleが、ロボット、人工知能、宇宙開発といった、一見突拍子もないような研究を続けるのは優秀な技術者を集めるため。GoogleのCEOのLarry Page氏がそう語っているのを聞いたことがある。高額の給料で引き寄せても、別の会社がより高額な給料を提示すれば、そうした人たちは去っていく。それよりも、ほかではできないような最先端のワクワクする仕事を与えれば、世界中から優秀な技術者が自然と集まってくる。Page氏はそう考えているわけだが、ABEJAに若い技術者が集まるのも同様の理由からなのだろう。

逆に言えば、優秀な人材を集めるには、常に最先端を走り続けなければならない。同社のモットーは、「5歩先の未来を想像し、4歩先を具体的に考え、3歩先の研究をし、2歩先の開発をし、1歩先でだれもが使えるような事業に落としこんでいく」というもの。「テクノロジーの最先端を走り続ければ、優秀な研究者、技術者が集まってくる。そうしたとんでもない技術を事業化できるようなビジネスプロデューサーも集まってくる。重要なものは、人。この仕組みを回していけば、無敵の企業になれるんじゃないかなって思っています」。

5歩先の未来を読むために、勉強は欠かせない。社内で論文の輪読を行っている。難しい論文を理解するのに必要なのは、努力の積み重ねとひらめき。専門的な知識を持った仲間のだれかが、「これはこういうことだ!」とひらめく。それを全員に共有する。輪読を行うことで、効率よく世界の最先端の研究動向を学べるのだという。

「実はわれわれは、既にDeep Learningの次を見ています。次の注目技術はTopological Data Analysis(TDA)です。インストア・マーケティングだけの会社で終るつもりはありません」と岡田氏は言う。TDAとは位相幾何学をベースにした新しい技術で、「計算リソースを少なくして今までの100倍くらいの性能でデータ解析ができるようになったり、従来手法では相関性が見えにくかったところが見えるようになるんです」。

では、果たしてその技術でどのようなことが可能になるのだろうか。どのようなビジネスに発展するのだろうか。

そのビジネス化こそがABEJAの役割だ、と岡田氏は言う。「技術の種からビジネスを作り出して、イノベーションを起こす。それで得た収益をまた研究開発に回して次の技術の種を作る。そのプロセスをぐるぐる回す。それがABEJAとして、やっていきたいことなんです」。

( ABEJA社 最近の動向 )※ アクセス日: 2015/5/31

ABEJA_current.PNG


プログラミング言語実装環境 ~手元で動かして、自分で検証するために

(実装環境 調査レポート)

survey.PNG


(R言語)

{TDA} Package

R_package_TDA.PNG

R_and_TDA.PNG


(Python言語)

daniforld.PNG

What is Python Mapper?

The Mapper algorithm is a method for topological data analysis invented by >Gurjeet Singh, Facundo Mémoli and Gunnar Carlsson. See the Reference [R1] for the publication.
While the Mapper algorithm alone does not constitute a >complete data >analysis tool itself, it is the key part of a processing chain with >(minimally) filter functions, the Mapper algorithm itself and visualization >of the results.

Python Mapper is a realization of this toolchain, written by Daniel Müllner and Aravindakshan Babu. It is open source software and is released under the GNU GPLv3 license.
There is also a company, Ayasdi, which was founded by Gurjeet Singh, Gunnar Carlsson and Harlan Sexton and whose main product, the Ayasdi Iris software, has the Mapper algorithm at its core. Ayasdi also issues academic trial licenses.

As much as Ayasdi covers the commercial uses of the Mapper algorithm with a polished and mature product, the authors of Python Mapper strive to provide the scientific community with a complete, extensible and fast toolchain. Since it is open source, it can be extended and modified by anyone with new ideas. The Python Mapper software also provides a graphical user interface, which hopefully makes it accessible to non-specialists and speeds up the workflow for beginners and experts alike.

To get an idea about the Mapper algorithm, we recommend Gunnar Carlsson’s paper “Topology and Data” [R5] and the original Mapper paper [R1].

(依存モジュール等)

Requirements

Python 2.6 or higher. The GUI needs Python 2 since it depends on wxPython and PyOpenGL; Python Mapper itself can be run under Python 2 and Python 3.

NumPy and SciPy
Matplotlib
Graphviz
Optionally cmappertools. Python Mapper will run without this module, but with limited functionality.
cmappertools need the Boost C++ libraries.

For the GUI:
wxPython
PyOpenGL

(インストール方法)

【 Highly recommended 】
  • fastcluster

This is Daniel Müllner’s C++ library for fast hierarchical clustering, again wrapped as a Python module. If one of the methods below work, this is the quickest way to install fastcluster. Otherwise, please refer to the detailed installation instructions in the fastcluster distribution. You need the Python interface; the R interface can be ignored.

  • (方法1)
Python
easy_install --upgrade --user fastcluster
  • (方法2)
bash
wget https://pypi.python.org/packages/source/f/fastcluster/fastcluster-1.1.13.tar.gz
tar -xf fastcluster-1.1.13.tar.gz
cd fastcluster-1.1.13
python setup.py install --user
cd ..
rm fastcluster-1.1.13.tar.gz
rm -r fastcluster-1.1.13/

(サード・パーティ企業 リリース分析環境)

Ayasdi_core_1.PNG

Ayasdi_ore_2.PNG

※ ユーザ・インターフェイスは、Tableau を使って操作できる GUI環境 も可能?か

Ayasdi_core_3.PNG

Ayasdi Core is an advanced analytics software application that helps you uncover critical business intelligence from dynamic, large, complex datasets.

Unique in the market, Ayasdi Core simplifies the analysis of complex data by combining topological data analysis (TDA), a technique pioneered by our founders, with the latest machine learning algorithms. We call this approach machine intelligence and it starts with the data - not with an endless string of questions.

Using data as the foundation, Ayasdi Core applies combinations of algorithms - from statistics, geometry and machine learning - to analyze thousands of attributes simultaneously.

Because of the depth and breadth of its algorithmic reach, Ayasdi Core rapidly finds and explains all the significant patterns in your data - something other approaches cannot achieve. Using the geometry of the data, Ayasdi Core creates topological summaries that reveal subtle insights, insights that remain invisible to other approaches.

(Ayasdi社 参考)

Ayasdi社.PNG

Ayasdi (チェロキー族の言葉で「探す」という意味) は、データ解析を行うスタートアップであり、高次元かつ多量のデータ集合から洞察を得る、ある革新的な手法を商業化するために、3人の数学者によって2008年に設立された。Topological Data Analysis(TDA) と呼ばれるこの手法は、国防高等研究計画局(DARPA)とアメリカ国立科学財団(NSF)との資金提供を受け、General Electric、 Merck、 アメリカ食品医薬品局(FDA)、アメリカ疾病予防管理センター(CDC)といった顧客に対して、クエリやアルゴリズムを記述することなく、彼らの持つデータの幾何学的構造を明らかにし、より可視化しやすく対話的に探索しやすい簡潔な要約データを作ることを可能にしている。

背景となる基本的な考え方は、データには形状があり、形状には意味があるということだ。TDAでは、基本的にはデータは空間上の点の大きく有限な集合として表現される。そして、点が互いにどのように関係しているかを説明するために、形状が使われる。

たとえば、形状の単純な観点のひとつである「いくつの部分に分けられるか」あるいは、「どうやってクラスタに分けられるか」ということが、ある現象の、概念的に異なる部分を明らかにできる。また別の観点「ループが存在するか」は、繰り返しや周期性のある振る舞いを表す可能性がある。トポロジは、まさにこの形状についての考え方を研究する数学の一分野であり、TDAは、このように定性的な幾何情報を定義し測定するための数学的な定式化を、大きくてノイズを含む点の集団にまで拡張することを目指している。

城田真琴氏のTweetからたどった英文記事 – 10 Big Data startups to watch(注目すべきビッグデータ関連のスタートアップ企業10)。これはやはり記録しておくべきか、と眠い目をこすりつつ読んだのだが説明文全部は訳せないので(全部は読んでない)、一言説明と顧客企業、競合だけ挙げておく。

2. Ayasdi

癌やその他疾患の予兆発見、新しいエネルギーソースの探索、テロリズム防止、金融詐欺など、複合的な問題を解決するためにビッグデータ分析を用いる。

ユーザ企業:
GE, Citi, Merck, USDA, Mt Sinai Hospital, the Miami Heat, the CDC.
競合:IBM’s Watson, SAS, Skytree


【 追記 】

以下のウェブページに、本記事が紹介されています。

上記の記事 で 引用されている 富士通研究所 における TDA の 利用事例

富士通研究所は判別が困難なほど振れ幅が激しい時系列データでも、高精度解析を可能とするDeep Learning技術を開発した。

富士通研究所は2016年2月16日、人による判別が困難なほど振れ幅が激しい時系列データでも、高精度解析を可能とするDeep Learning技術を開発したと発表した。最先端の数学を活用し、時系列データから「幾何的な特徴」を抽出することで解析を可能にしたとしている。

( 以下、上記 記事から一部を抜粋して転載 )

スクリーンショット 2016-03-10 17.00.36.png

( 中略 )

スクリーンショット 2016-03-10 17.00.47.png


【 その他 】

【 Qiita関連記事 】