Topological Data Analysis

Topological data analysis という分野がある。多くの数値データを point cloud すなわち Euclid空間や距離空間に配置された点の成す離散集合とみなし, それを topological な道具で調べることによりそのデータの持つ情報を取り出すことを研究する分野, と言ってよいだろう。最近では TDA と省略して呼ばれるのが普通である。 Chazal と Michel の survey [CM] を読むと概要が掴めるかもしれない。

その登場以来, 様々な応用が発見されている。 例えば, この webpage にまとめがある。

TDA で使われる topological な道具として中心的役割を果しているのは persistent homology である。

• persistent homology

また, point cloud が多様体に近い形をしている場合, 元の幾何学的対象を再構築することも考えられている。 Chazal と Oudot [CO08] は manifold reconstruction と いう言葉を使っている。Manifold learning の方が一般的だろうか。 Boker, Turner, Williams の [BTW] では, Dey らの [CDR05; Dey07; DFW] が参考文献として挙げられている。

• manifold learning

もちろん多様体を復元するのは大変であるが, 多様体の不変量を point cloud から取り出せるとよい, と思う。 例えば, Dey, Fan, Wang [DFW] は point cloud から元の多様体の次元を計算するアルゴリズムを考えている。

ただ, point cloud が多様体に近いという仮定は強すぎる。 普通は特異点があるはずである。つまり, 各 stratum が多様体である stratified space とみなすべきである。 そのような stratified space を point cloud から再構成することを, stratification learning あるいは stratified space learning という。 Skraba と Wang の [SW14] に色々文献が挙げられている。 MathSciNet には収録されていない論文が多いが。 例えば, stratification learning のために, intersection homology や local homology の persistent homology への拡張を Bendich と Harer [BH11] が考えている。

• stratification learning

特異点を持った多様体で最も簡単なのは, graph なので, 具体的な algorithm を考える際には, まず graph を point cloud から再構築できるかを考えるべきだろう。実際, Boker ら [Bok+; BTW] がそのような algorithm を考えている。

よりホモトピー論的な手法として, Blumberg と Mandell [BM13] によるものがある。Persistent homology のようなホモロジーによる不変量で測れないものを, ホモトピー集合を用いて調べることを提案している。 もちろん, ホモトピー集合を計算するのは大変であるが, その代わりに写像空間のホモロジーを調べることにし, 単体的複体の間の写像空間を近似する Hom complex に似た単体的複体を構成している。彼等のアイデアの元になっているのは Gromov の quantitative homotopy theory [Gro99] のようであるが。

• quantitative homotopy theory

Gromov の論文は, 宇宙が単連結かどうか, という話題から始まっている。 そのときに問題になるのが, 光の速度が有限であることである。例え理論的に null homotopic な loop であっても, 1点に縮めるのに光の速度でも \(10^{30}\) 年かかるようなものなら自明でない loop とみなしてよいのではないか, と言っている。

確かに, topological data anaylsis のような現実の問題を扱う際には, 抽象的に定義されたものではなく, 長さや大きさも考慮して定義されたホモトピー不変量を用いた方がよいだろう。

Blumberg と Lesnik は [BL] で filtered topological space の間の homotopy interleaving の概念を導入している。

• homotopy interleaving

彼等は, TDA のホモトピー論的な基礎を目指しているようである。

References

[BH11]

Paul Bendich and John Harer. “Persistent intersection homology”. In: Found. Comput. Math. 11.3 (2011), pp. 305–336. url: http://dx.doi.org/10.1007/s10208-010-9081-1.

[BL]

Andrew J. Blumberg and Michael Lesnick. Universality of the Homotopy Interleaving Distance. arXiv: 1705.01690.

[BM13]

Andrew J. Blumberg and Michael A. Mandell. “Quantitative homotopy theory in topological data analysis”. In: Found. Comput. Math. 13.6 (2013), pp. 885–911. arXiv: 1309.6628. url: https://doi.org/10.1007/s10208-013-9177-5.

[Bok+]

Yossi Bokor, Daniel Grixti-Cheng, Markus Hegland, Stephen Roberts, and Katharine Turner. Stratified Space Learning: Reconstructing Embedded Graphs. arXiv: 1909.12474.

[BTW]

Yossi Bokor, Katharine Turner, and Christopher Williams. Towards Stratified Space Learning: Linearly Embedded Graphs. arXiv: 2101.04375.

[CDR05]

Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos. “Manifold reconstruction from point samples”. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 2005, pp. 1018–1027.

[CM]

Frédéric Chazal and Bertrand Michel. An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists. arXiv: 1710.04019.

[CO08]

Frédéric Chazal and Steve Y. Oudot. “Towards persistence-based reconstruction in Euclidean spaces”. In: Computational geometry (SCG’08). New York: ACM, 2008, pp. 232–241. url: http://dx.doi.org/10.1145/1377676.1377719.

[Dey07]

Tamal K. Dey. Curve and surface reconstruction: algorithms with mathematical analysis. Vol. 23. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2007, pp. xiv+214. isbn: 978-0-521-86370-4; 0-521-86370-8.

[DFW]

Tamal K. Dey, Fengtao Fan, and Yusu Wang. Dimension Detection with Local Homology. arXiv: 1405.3534.

[Gro99]

Mikhael Gromov. “Quantitative homotopy theory”. In: Prospects in mathematics (Princeton, NJ, 1996). Amer. Math. Soc., Providence, RI, 1999, pp. 45–49.

[SW14]

Primoz Skraba and Bei Wang. “Approximating local homology from samples”. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 2014, pp. 174–192. arXiv: 1206.0834. url: https://doi.org/10.1137/1.9781611973402.13.