How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

Angshul Majumdar による論文「How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals」の詳細な技術的要約を以下に示す。

1. 問題定義

本論文は、有限点集合ではなく、多項式確率密度関数 $f: \mathbb{R}^d \to \mathbb{R}$ 上で直接定式化された連続クラスタリング問題の計算複雑性を調査する。密度閾値 $\theta$ が与えられたとき、多項式によって定義される「ランドスケープ」内に特定のクラスタ構造が存在するかどうかを決定する問題の固有の難しさを明らかにすることを目的としている。

著者は、局所的な幾何学的基準から大域的な位相的性質に至るまで、4 つの自然な決定問題を形式化した。

1. CMRC（連続多領域クラスタリング）: 密度 $f(x) \geq \theta$ となる $k$ 個の、互いに $\delta$ 分離された点が存在するか？
2. VSC（バレー分離クラスタ）: $f(p), f(q) \geq \theta$ となる 2 点 $p, q$ が存在し、かつその中点が厳密に閾値より低い（$f(\frac{p+q}{2}) < \theta$）か？これは幾何学的に 2 つの高密度領域を隔てる「バレー」を証明するものである。
3. CLSC-k（連続レベルセット成分数え上げ）: 超レベルセット $L_\theta = \{x \mid f(x) \geq \theta\}$ は少なくとも $k$ 個の連結成分を持つか？
4. HD（穴検出）: 超レベルセット $L_\theta$ は非自明な第 1 特異ホモロジー群を持つか（すなわち、「穴」を含んでいるか）？

2. 手法

本論文は、計算実代数的幾何学と複雑性理論のツール、特に**実数の存在論（Existential Theory of the Reals, $\exists\mathbb{R}$）**に焦点を当てて用いている。

• 複雑性クラス $\exists\mathbb{R}$: このクラスは、$\exists x_1 \dots \exists x_n \Phi(x_1, \dots, x_n)$ の形式の文の真偽を決定する問題に帰着可能な決定問題から構成される。ここで $\Phi$ は多項式方程式および不等式の量化子なしのブール結合である。標準的な完全問題は Feas（多項式が実根を持つかを決定する問題）である。
• 帰着: 著者は、標準的な $\exists\mathbb{R}$-完全問題である Feas からクラスタリング問題への多項式時間帰着を構築する。
  • 「2 シート」構成: 入力多項式 $r(y)$ の根の存在をクラスタリング問題の幾何学に符号化するために用いられる核心的な代数的ギジェットである。この構成は、根が存在する場合にのみ、2 つの平行な「シート」（例：$s=1$ と $s=-1$）からなる超レベルセットを持つ多項式 $F$ を作成し、根が存在しない場合は空集合となるようにする。
  • 位相的埋め込み: 穴検出については、$r(y)$ の零点集合を単位円（$S^1$）との積の因子として埋め込み、キュネート公式を利用して、根が存在するときにのみ結果として得られる空間が非自明なホモロジーを持つようにする。

3. 主要な貢献と結果

A. 局所的およびバレーベースのクラスタリングの完全性

本論文は、最初の 2 つの問題が $\exists\mathbb{R}$-完全 であることを証明する。

• CMRC: この問題は、$k$ 個の点に対して量化し多項式不等式をチェックすることで実数上の存在文として表現できるため、$\exists\mathbb{R}$ に属することが示される。分離を保証するためのダミー座標を用いた Feas からの帰着により、$\exists\mathbb{R}$-困難であることが証明される。
• VSC: 「バレー」の存在は単一の存在量化子（中点）によって立証できるため、大域的な概念であるにもかかわらず、VSC も $\exists\mathbb{R}$ に属する。困難性の証明では、2 つのシートが $s=0$ におけるバレーによって分離されている「2 シート」構成を用いる。
• 示唆: $\text{NP} \subseteq \exists\mathbb{R}$ であり、その包含関係は厳密であると信じられているため、CMRC および VSC は NP に属さない（$\text{NP} = \exists\mathbb{R}$ でない限り）。これにより、単純な連続クラスタリングさえも、$k$-means などの標準的な NP 完全問題よりも困難であることが確立される。

B. 位相的クラスタリングの困難性と決定可能性

本論文は、純粋に位相的な問題（CLSC-k および HD）の複雑性に取り組む。

• 下限: CLSC-k および HD の両方が $\exists\mathbb{R}$-困難 であることが証明される。CLSC-k（成分数え上げ）には同じ「2 シート」構成が用いられ、HD には円との積構成が用いられる。
• 上限とギャップ: CMRC や VSC と異なり、CLSC-k および HD の $\exists\mathbb{R}$ への所属は不明である。
  • これらの問題は円柱代数分解（CAD）を通じて決定可能であり、実数の一階論理（PSPACE に属する）に位置づけられる。
  • しかし、これらを $\exists\mathbb{R}$ に位置づけるためには、半代数集合の非連結性や非自明なホモロジーに対する多項式サイズの存在証明（certificate）が必要となる。これは実代数的幾何学における有名な未解決問題（Positivstellensatz の次数 bound に関連する）である。
• 結論: これらの問題は、実多項式階層において $\exists\mathbb{R}$ よりも厳密に上位（おそらく $\exists\forall\mathbb{R}$ 内）に位置する可能性が高く、「局所的/バレー」基準から「大域的位相」への複雑性の飛躍を表している。

4. 意義と含意

1. 厳密な複雑性分類: これは、典型的に NP 困難である離散的・有限サンプルの設定を超えて、厳密な連続クラスタリングに対する最初の厳密な複雑性分類を提供するものである。
2. 境界の明確化: 本論文はクラスタリング複雑性における正確な境界を画定する。
   • $\exists\mathbb{R}$-完全: 局所的分離およびバレーベースの分離（幾何学的な証人が存在する）。
   • $\exists\mathbb{R}$ より上位: 連結成分や穴などの大域的位相的特徴（単純な存在証人が存在しない）。
3. 近似の理論的正当性: 連続密度に対する厳密なクラスタリングアルゴリズムが非現実的（intractable）である理由を説明する。これらの問題は NP よりも困難である可能性が高いため、実務において広く用いられる近似、反復、またはサンプリングベースの手法は理論的に正当化される。
4. 実代数的幾何学との関連: 本論文は、教師なし学習と実代数的幾何学の未解決問題との深い関連を浮き彫りにする。位相的クラスタリングが $\exists\mathbb{R}$ に属することを証明するには、半代数分離に対する多項式サイズの証明を見つけるという問題を解決する必要があり、それ自体が大きな飛躍となる。

まとめ

本論文は、厳密な連続クラスタリングは本質的に NP よりも困難である（$\text{NP} \neq \exists\mathbb{R}$ と仮定した場合）ことを示している。局所的およびバレーベースの基準は実数の存在論に対して完全であるが、連結成分の数え上げや穴の検出などの大域的位相的制約を導入すると、半代数幾何学における未解決の問題に依存しつつ、実多項式階層のより高いレベルへと複雑性が押し上げられる。