Please enable JavaScript in your browser.

fltech - 富士通研究所の技術ブログ

富士通研究所の研究員がさまざまなテーマで語る技術ブログ

InriaとのTDAに関する共同研究成果の論文がAISTATS2021に採択されました

f:id:fltech:20210407172401p:plain

こんにちは.富士通研究所人工知能研究所の池祐一と梅田裕平です.富士通研究所では「データの幾何学的形状」をとらえる位相的データ解析(トポロジカルデータアナリシス; TDA)について,フランスの国立研究機関であるInriaと共同研究を行っています.今回は共同研究を通して得られた成果に関する論文がAI分野の主要な国際会議であるAISTATS2021に採択されたので,その内容について概要を説明します.

TDAに関する富士通研究所の研究成果や応用例についてはWEBサイトFujitsu's TDA Technologiesで紹介しています.ご興味ある方はこちらのWEBページも見ていただけますと幸いです.

対象論文

ATOL: Measure Vectorization for Automatic Topologically-Oriented Learning 論文リンク

  • Martin Royer, Frédéric Chazal, Clément Levrard, Yuhei Umeda, and Yuichi Ike
  • The 24rd International Conference on Artificial Intelligence and Statistics (AISTATS 2021)

Inriaとの共同研究の概要

富士通研究所は2017年からフランス国立研究機関InriaのDataShapeチーム,Frederic Chazal教授らとTDAに関する共同研究を行っています.そこでは時系列データに対するTDA技術をはじめとして,産業応用が可能なTDA技術と機械学習の融合について研究を続けてきました.この共同研究の中で2019年の2月・3月にInria研究者のMartin Royer氏が日本の富士通研究所に滞在し,逆に2019年の5月・6月は池がフランスのInria Saclayに滞在するなど,ある意味で交換留学的な仕組みで研究を推進してきました.今回紹介する成果はこれらの活発な共同研究を通して得られたものです.

採択された論文の内容

今回採択された論文"ATOL: Measure Vectorization for Automatic Topologically-Oriented Learning"(プレプリントはこちら)はTDAの出力であるパーシステント図のベクトル化に関わる内容です.以下ではまずTDAとパーシステント図について説明して,そのあとに今回の論文の内容を簡単にまとめます.

位相的データ解析とパーシステント図

位相的データ解析 (Topological Data Analysis, TDA) はデータの「形」,特にトポロジーというものを抽出することができます.例えば点群のデータに大まかにみて連結成分・穴がいくつあるかということを取り出すことができます.しかしながら,データ点の集まりはバラバラな有限集合なので,そのままでは「形」(トポロジー)を取り出すことができません.そこで一つ目のアイデアは下の図1のように各データ点の周りに球を考えて,その和集合の形を調べるということです.

f:id:fltech:20210407173130p:plain
図1:データ点群と各点での球の和集合

しかしながら,次の問題はこの球の半径をどのように設定すれば良いか分からないということです.例えば上の図では左は球の半径が小さすぎてちぎれていて,右側の方が適切な半径の設定に見えますが,この半径の大きさはあらかじめ分かりません.設定した球の半径が小さすぎるとバラバラに見えてしまうし,大きすぎると全部がくっついて穴が見えなくなってしまいます.そこでTDAの二つ目のアイデアは,球の大きさを固定しないで小さいところから大きいところまでを全部考えてトポロジーの変化を追跡するというものです(図2を参照).

f:id:fltech:20210407173240p:plain
図2:半径の変化によるトポロジーの変化

このように考えれば長い時間存在している連結成分や穴がデータの本質的な「形」をあらわしていると思えます.各連結成分や穴といったトポロジー特徴に対して,それが発生する半径と消滅する半径を計算することができます.発生する半径をx軸に,消滅する半径をy軸にプロットして出来る2次元空間内の点集合をパーシステント図と呼びます(図3を参照).このパーシステント図がデータのトポロジーの情報を持っており,TDAではパーシステント図を用いてデータの解析を行います.

f:id:fltech:20210407173441p:plain
図3:トポロジーの変化とパーシステント図

TDAはグラフや時系列などの複雑な構造のデータを扱う際に役立つ技術で,機械学習と組み合わせることで有用に使えると期待されます.しかしながら,機械学習の入力は主にベクトルなので,TDAと機械学習とを組み合わせるにはただの点集合であるパーシステント図をベクトル化する必要があります.このベクトル化手法に関しては,パーシステントランドスケープ (Bubenik 2015)・パーシステントイメージ (Adams et al. 2015) といった有限次元のベクトル化や重み付きガウスカーネル (Kusano et al. 2016) といったカーネル法によるベクトル化などが提案されてきました.また,今回採択された論文とは別のInriaとの共同研究成果として,パーシステント図のベクトル化をニューラルネットワークの一つの層として実現するPersLayという手法を提案した論文(Carrière et al. 2020)も昨年のAISTATS2020に採択されています.しかし,カーネル法による手法は大規模データにスケールしないという問題があり,ニューラルネットワークに依存する手法は解釈可能性が低いという問題があります.近年では固定した点に応じたベクトル化手法を学習する手法 (Hofer et al. 2017) やパーシステント図を測度だとみなした際のベクトル化手法の数学的な枠組み (Perea et al. 2019) といった研究があり,今回の我々の提案手法はこれらの研究の延長線上にあります.

今回の論文の内容:ATOLベクトル化

今回の論文で我々はまず任意次元のユークリッド空間内の測度をベクトル化する教師なしの手法を提案しました.これは今回の共同研究者らの研究 (Chazal et al. 2020) に基づくk-平均法的な手法です.あらかじめ設定したパラメータ  b (正の整数)に対して,サンプル測度の平均測度にLloydアルゴリズムを適用することで  b 個の重心  c_1,\dots,c_b を計算します.そして  c_i を中心とするコントラスト関数  \exp(-|x-c_i|_2/\sigma_i) を用いて測度に対して  b 次元のベクトルを対応させます.上記のベクトル化手法を2次元の有限測度であるパーシステント図に用いることでそのベクトル化手法ATOL (Automatic Topologically-Oriented Learning) が得られます.すなわち,パラメータ  b に対してATOLはパーシステント図を  b 次元ベクトルに変換します.我々は論文中でATOLはデータに対して分離性という良い性質を持っていることを理論的に示しました.つまり,データ数と  b が十分大きい場合は,高い確率で同じラベルのパーシステント図同士のATOLベクトル化は近く,異なるラベルのパーシステント図同士のATOLベクトル化は遠いということを証明しました.最後に我々はATOLを用いてグラフ分類(表1・2を参照)と力学系軌道分類の実験を行い,高速かつ解釈可能なベクトル化でありながら最先端の手法と同等の精度を達成することを確認しました.

f:id:fltech:20210408173210p:plain
表1:大規模ソーシャルネットワークのグラフデータセットの分類精度の比較
f:id:fltech:20210408173540p:plain
表2:ケモインフォマティクスおよびバイオインフォマティクス分野におけるグラフデータセットの分類精度の比較

今回提案したATOLベクトル化手法は,(1) 重心を作ってそこからの距離を用いるのでベクトル化の解釈がしやすく,(2) 大規模なデータに対しても計算が早く,(3) 異なるパーシステント図のクラスターを分離することが理論的に保障されているという利点があります.富士通研究所は今後このATOLベクトル化を用いたTDAの産業応用にも取り組む予定です.

おわりに

本記事では,TDAとその出力であるパーシステント図およびAISTATS2021に採択されたATOLベクトル化についてご紹介しました.Inriaと富士通研究所のTDAに関する共同研究では二年連続でのAISTATSへの採択は大変うれしいものでした.今後も共同研究を継続して良い研究を続けていけたらと思います.

論文情報

  1. Martin Royer, Frédéric Chazal, Clément Levrard, Yuhei Umeda, and Yuichi Ike; ATOL: Measure Vectorization for Automatic Topologically-Oriented Learning, in Proceedings of the 24rd International Conference on Artificial Intelligence and Statistics (AISTATS 2021), 論文リンク

  2. Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda; PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, in Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 論文リンク