When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

技術的概要：次元分割による次元削減における曖昧なインスタンスの対処

問題定義
次元削減（DR）は高次元データを可視化するための基本的なツールであるが、本質的に損失を伴うプロセスである。既存の文献はマニホールドの引き裂きなど、さまざまな歪みをカタログ化してきたが、本論文は視覚的アーティファクトの以前は見落とされていた発生源を特定する：曖昧なインスタンスである。これらは、高次元空間において、互いに非類似な複数の近傍と極めて類似しているデータ点である。

標準的な DR 手法は、各データインスタンスを視覚空間内の単一の点にマッピングする。その結果、曖昧なインスタンスは、複数の異なる近傍への所属を同時に忠実に表現することができない。それは単一の位置へ強制され、部分的な近傍埋め込みという状態に至る。この状態において、インスタンスは単一の近傍（あるいはいずれの近傍にも）に属しているように見え、他の非類似なグループとの真の関係性が不明瞭になる。このアーティファクトは、正確な近傍構造の理解が不可欠である、説明可能な AI（XAI）や単細胞生物学などのインスタンスレベルの分析において特に問題となる。信頼性や連続性といった既存の指標は、最終的な埋め込みのみを操作し、基礎となるデータの曖昧性にアクセスできないため、部分的な近傍埋め込みを他の歪みと区別することができない。

手法
著者らは、曖昧なインスタンスをそれぞれの近傍内に配置された複数の点へ「分割」することにより、これらの曖昧さを特定し解決するためのグラフベースのアプローチを提案する。手法は、Paulovich らによって導入された 2 フェーズの DR フレームワーク（関係性とマッピング）に従う：

1. グラフ構築とスパース化:

   • 高次元の関係性は、無向重み付きグラフ $G$ としてモデル化される。
   • 意味のある近傍構造を露呈させ、偶発的な近接によって生じる冗長なエッジを除去するため、著者らは Spielman-Srivastava アルゴリズムを用いたスペクトルスパース化を適用する。これにより、元のグラフの構造的および代数的性質を保持しつつ、弱い接続を除去した縮小グラフ $\bar{G}$ が生成される。

2. 曖昧なインスタンスの特定:

   • 曖昧さはトポロジー的に定義される。著者らは**局所節点（LAPs）**の概念を適応する。ある頂点が、局所的な $r$ 段階誘起近傍内の連結成分の数を増加させる場合に、その頂点は LAP とみなされる。
   • インスタンスがスパース化されたグラフ $\bar{G}$ において LAP である場合、そのインスタンスは曖昧であると判定される。これは、そのインスタンスが、そうでなければ分離されるはずの非連結な近傍を接続していることを示す。
   • 計算の最適化には補題 3.1 が利用される：ある半径 $r$ において頂点が LAP でない場合、より大きな半径 $r' > r$ においても LAP になり得ない。

3. 頂点の分割と決定ルール:

   • 曖昧な頂点 $v_i$ が特定されると、$v_i$ が局所近傍から除去された後に残る連結成分の数に相当する $K$ 個のコピーに分割される。
   • 決定ルール: すべての潜在的な分割が実行されるわけではない。アプローチは以下のものをフィルタリングする：
     • LAP-LAP 接続: 2 つの近傍を橋渡しするエッジの両端点がともに LAP である場合、人工的な孤立を避けるため分割は抑制される。
     • 弱い接続: 接続強度と最強の成分との比率であるユーザー定義の閾値 $\tau_w$ により、近傍への接続が意味を持つほど強くない場合の分割をフィルタリングする。これにより、不十分な引力による視覚的に孤立した点の生成を防ぐ。

4. マッピングと可視化:

   • 分割された頂点を含む修正されたグラフは、標準的な局所 DR 手法（例：UMAP または ForceAtlas2）を用いて視覚空間へ投影される。
   • 視覚的符号化: 分割されたインスタンスは、元の位置または互いに破線で接続された区別されたマーカー（例：十字）として描画され、分析者が単一のデータ点の複数の近傍所属を追跡できるようにする。

主要な貢献

• 部分的な近傍埋め込みの定義: 本論文は、曖昧なインスタンスに起因するこの特定のアーティファクトを正式に導入・定義し、一般的な DR の歪みから区別する。
• グラフ理論に基づく検出: スパース化された近傍グラフ上の局所節点を用いて曖昧なインスタンスを特定する手法を提示する。
• 分割メカニズム: 著者らは、投影において複数の近傍所属を反映させるために、曖昧なインスタンスを分割する具体的かつ準線形時間計算量のアプローチを提案する。
• 実証的検証: 手法は多様なデータセット（SVHN、MNIST、テキストコーパス、単細胞 RNA シーケンシング）で実証され、標準的な投影では見えない隠れた近傍所属を明らかにすることを示している。

結果

• 定性的洞察: SVHN データセットにおいて、標準的な UMAP では「7」の近傍にのみ属すると表示されていた誤分類された数字「1」（「7」と予測）が、提案されたアプローチによって分割され、「1」の近傍との同時的な類似性が明らかになった。これにより、分類器の誤りの曖昧さが説明された。同様に、テキストデータにおいて、「毒性学のための ILP 支援モデル」に関する論文は、標準的な投影では不明瞭であった ILP と事例ベース推論（CBR）の両方のクラスターに属していることが示された。
• 定量的分析:
  • スパース化の影響: 保持された $k$ 近傍（$k$NN）を測定する実験により、スペクトルスパース化は、ほとんどのデータセットで比率が 1 に近いことから、元のグラフと同等の局所近傍構造を保持することが示されたが、高内次元の単細胞データではある程度のばらつきが観察された。
  • 指標の限界: 標準的な指標（信頼性と連続性）は、これらの点が指標分布全体で非曖昧な点と類似して分布しているため、曖昧なインスタンスの特定には効果的ではないことが判明した。
  • パラメータ感度: 初期グラフにおける近傍数の増加は、一般的に検出された分割の数を減少させた。これは、増加した接続性が、そうでなければ非連結に見える近傍を橋渡しするためである。

意義と主張
本論文は、DR における微細な局所構造を解釈する上で、曖昧さを認識することが不可欠であると論じる。著者らは、曖昧なインスタンスを考慮しないことが、特にインスタンスレベルの文脈が vital である XAI や生物学などの分野において、不完全または誤った解釈につながる可能性があると主張する。これらのインスタンスを分割することにより、この手法はデータの高次元トポロジーのより忠実な表現を提供し、「以前は隠れていた近傍所属」を明らかにする。この研究は、現在の DR 品質指標がこの特定の種類のアーティファクトには不十分であり、将来の評価フレームワークは、単なるマッピングに起因する不安定性ではなく、データ駆動型の曖昧さを考慮する必要があることを示唆している。