三つ葉結び目は、t-SNEにほどけるのか。Isomapが完璧にほどき、たった1本の偽のつながりで壊れた
約6分で読めます

三つ葉結び目は、t-SNEにほどけるのか。Isomapが完璧にほどき、たった1本の偽のつながりで壊れた

三つ葉結び目(trefoil knot)は、いちばん単純な結び目だ。3D空間の中では、この結び目を切らずにほどいてただの輪にすることは絶対にできない——それが「結ばれている」ということの数学的な意味だ。

ところが、だ。結び目の上を這う虫の立場で考えると、この曲線はただの一本道で、ぐるっと一周すると元の場所に戻る。つまり位相的には、三つ葉結び目はただの円と同じ「1次元のループ」にすぎない。結ばれているのは3D空間への埋め込まれ方であって、曲線そのものではない。

だとすると、データの内在的な構造を取り出すはずの次元削減アルゴリズムたちは、結び目を「ほどいて」円にできるのだろうか。スイスロール、穴あきロールに続く多様体学習シリーズ第3弾は、結び目に挑戦する。

結果: Isomapは完璧にほどいた

結び目に沿って900点をばらまき(位置tを色相で表す。ほどければ虹色の輪になるはず)、PCA・Isomap・t-SNE・UMAPで2次元化した。

4手法の結果。PCAは三つ葉のクローバー型の影(交差が残る)。Isomapは完璧な虹色の円。t-SNEは輪が3つの弧に切れて散らばっている。UMAPは十数個の小さな断片に粉砕されている

  • PCA: 3Dの結び目をそのまま平面に投影した「影絵」。三つ葉のクローバー型で、交差もそのまま残る。ある意味いちばん誠実だが、何もほどけていない
  • Isomap: 完璧な虹色の円。 結び目は完全にほどかれた。kNNグラフ上の測地線距離は「曲線に沿った道のり」を測るので、3D空間でどう絡まっているかは一切関係なくなる。教科書的には分かっていても、実際に完全な円が出てくると感動がある
  • t-SNE: 局所の並び順は保たれているが、輪全体は3つの弧に引きちぎられた。ループを閉じることより局所の詰まり具合を優先する性格がそのまま出ている
  • UMAP: さらに細かく、十数個の断片に粉砕された

「3D空間では絶対にほどけない結び目」が、内在距離の世界ではあっさりほどける。ほどく能力の有無ではなく、そもそも何を保とうとしているかが4手法でこれだけ違う。

糸を太らせると、交差点が「溶接」される

ここからが本番だ。Isomapの完勝は、kNNグラフが結び目の糸に沿ってだけ張られている(交差部で糸をまたぐエッジがない)ことに依存している。ならば、糸を太らせて(ノイズを増やして)、交差部で糸同士が触れるようにしたらどうなるか。

パラメータtの離れた点同士を結ぶエッジを「ショートカット(偽のつながり)」と数えながら、ノイズを0.02から0.44まで増やしてみた。

ノイズに対する輪の復元度(円環相関)とショートカットエッジ数の2軸プロット。ノイズ0.14まではショートカット0本で復元度0.999。0.17で初めて1本のショートカットが生まれ復元度が0.968に揺らぎ、0.20で5本(0.882)、0.23で12本になると0.400へ崩壊する。以降ショートカットは急増し復元度は0.3で底ばいになる

ノイズを増やしながら、左に3Dの結び目、右にIsomapの埋め込みを並べたアニメーション。糸が太るにつれて、完璧だった虹色の輪が揺らぎ、あるところで突然つぶれてクローバー状の塊に崩壊する

数字の推移がドラマチックだった。

  • ノイズ0.14まで: ショートカット0本、復元度0.999。完璧な輪のまま
  • ノイズ0.17: 初めての1本が生まれ、復元度0.968へ
  • ノイズ0.20: 5本で0.882
  • ノイズ0.23: 12本で0.400へ崩壊

4,500本の正しいエッジの中に、偽物が12本混ざっただけで、輪は輪でなくなった。割合にして0.27%だ。測地線距離はグラフの最短路なので、ショートカットが1本あるだけで「本当は遠い2点」の距離が一気に縮む。距離行列の広い範囲が汚染されるから、局所的なノイズが大域的な崩壊を引き起こす。穴あきロールの回では「歪みは穴の周辺に局所化される」ことがIsomapの頑健さの源だったが、今回は逆で、ショートカットの効果は決して局所に留まらない。同じ手法の頑健さと脆さが、壊し方ひとつで裏返った。

手を動かして意外だったこと

いちばん響いたのは「たった1本」の重みだ。0.27%の誤配線で崩壊が始まる。ネットワークの世界で言えば、遠く離れたクラスタ同士を1本の誤リンクがつないでしまえば、「距離」の意味そのものが変質する。組織で言えば、部署間の垣根を越える1本の誤った伝聞が、本来遠かったはずの情報同士を直結させてしまう。つながりは基本的には豊かさだが、偽のつながりは、本物のつながり4,500本分の構造を12本で無効化できる。

そしてもう1つ。t-SNEとUMAPが輪を引きちぎったのは「失敗」とも言い切れない、というのが実験後の実感だ。彼らが保とうとしているのは局所の近傍関係であって、大域のループ構造は最初から契約に入っていない。前回の「手法の流派は壊れ方に出る」と同じで、結局どの道具も、自分が守ると約束したものしか守らない。道具を選ぶとは、何を諦めるかを選ぶことなのだと思う。

まとめ

  • 三つ葉結び目(位相的にはただの輪)の900点をPCA・Isomap・t-SNE・UMAPで2次元化した
  • Isomapは結び目を完璧な円にほどいた(円環相関0.999)。測地線距離は曲線に沿った道のりだけを見るので、3D空間での絡まり方は無関係になる
  • PCAは影絵(交差が残る)、t-SNEは輪を3つの弧に引きちぎり、UMAPは十数個の断片に粉砕した——各手法が「何を保とうとしているか」の違いがそのまま出る
  • 糸を太らせて交差部に偽のつながり(ショートカット)を作ると、1本目(全エッジの0.02%)で復元度が揺らぎ、12本(0.27%)で輪が崩壊した(0.999→0.400)
  • ショートカットは測地線距離の大域を汚染するため、局所の誤配線が大域構造の崩壊を引き起こす——穴あきロールで見た「歪みの局所化」とは正反対の壊れ方

関連記事