Weighted Conformal Clustering

技術要約：重み付き共形クラスタリング (Weighted Conformal Clustering)

問題の定式化
クラスタリングは、ラベルのないデータから潜在的な構造を明らかにするための基本的なツールであるが、標準的なパイプラインは通常、観測値をクラスターへの「ハード」な割り当てとして結果に示し、割り当ての不確実性を厳密に定量化しない。既存の手法は、ブートストラップ法、グローバルなクラスター存在テスト、またはベイズ信頼集合を通じて不確実性に対処しているが、個々の観測値の割り当てに固有の不確実性を見落としていることが多い。

[11] による最近の研究では、ラベル割り当てを予測問題として扱うことで、クラスタリングのための共形推論（conformal inference）フレームワークを導入した。しかし、決定的な理論的限界が存在する。それは、[11] で使用されている較正ラベルは、真のグラウンドトゥルース・ラベルではなく、データ依存型のクラスタリングアルゴリズムによって生成された合成ラベルであるという点である。その結果、標準的な交換可能性の仮定が満たされず、有効な共形予測（conformal prediction）に必要な条件が損なわれ、カバレッジの不足（undercoverage）を招く可能性がある。課題は、合成ラベルと観測されない潜在的なグラウンドトゥルース・ラベルとの間の分布の不一致にもかかわらず、有限標本でのカバレッジ保証を維持できるクラスター・ラベルの信頼集合を構築することである。

手法
著者らは、この分布の不一致を条件付きラベル分布シフトとして定式化することで、重み付き共形クラスタリング (Weighted Conformal Clustering) フレームワークを提案している。コアとなる手法は以下の3段階で進行する：

1. オラクル重み付き分割共形クラスタリング (Oracle-Weighted Split Conformal Clustering):
   著者らはまず、厳密な有限標本周辺カバレッジを達成する「オラクル」手順を導出する。このアプローチは、合成ラベル分布（クラスタリングアルゴリズムによって誘導される）と真の潜在ラベル分布との間の乖離を補正するために構築された重み付き共形予測を利用する。重みは、真の条件付きラベル密度 $p^*_{Y|X}$ と、クラスタリングアルゴリズムによって生成された合成ラベル確率との尤度比として定義される。これは理論的には健全であるが、すべての較正点およびテスト点に対して、leave-one-out（一つ抜き）拡張データセット上でクラスタリング・ルールを評価する必要があるため、計算量的に実行不可能である。

2. 拡張較正メカニズム (Augmented Calibration Mechanism):
   この手法を計算可能にするために、著者らは新しい拡張較正メカニズムを導入している。較正セットに対してクラスタリングアルゴリズムを個別に適合させ、さらに leave-one-out セットに対して繰り返し適合させる代わりに、アルゴリズムは拡張データセット $D_{aug} = D_{ca} \cup \{x\}$（ここで $D_{ca}$ は較正セット、$x$ はテスト点）に対して一度だけクラスタリングモデルを適合させる。この単一の適合により、合成尤度項が正規化の過程で因数分解され、相殺されるため、重みは点ごとの尤度比の形式へと簡略化される。このメカニズムは、フル共形（full-conformal）と分割共形（split-conformal）のアプローチを橋渡しし、繰り返しの再適合の必要性を排除する。

3. 推定重みの構築 (Estimated-Weight Construction):
   真の条件付き密度 $p^*_{Y|X}$ は未知であるため、手法はオラクル重みを、別のトレーニング・スプリットで訓練されたソフト分類器 $\hat{\pi}$ を用いた推定重みに置き換える。最終的なアルゴリズム（Algorithm 1）は以下の手順を含む：

   • データをトレーニングセットと較正セットに分割する。
   • トレーニングセット上でクラスタリングアルゴリズムを適合させ、ラベルとソフト分類器を生成する。
   • 拡張較正セット ($D_{ca} \cup \{x\}$) 上でクラスタリングアルゴリズムを適合させ、合成ラベルを生成する。
   • 置換 $\hat{\sigma}$ を通じて、合成ラベルをトレーニング・ラベルと整合させる。
   • 適合スコアを計算し、推定された条件付き密度と拡張クラスタリング確率の比から得られる推定重みを用いて、信頼集合を構築する。

主な貢献
本論文の主な貢献は以下の3点である：

1. 新しいフレームワーク： 合成ラベルが条件付きラベル分布シフトを誘発するものとしてモデル化し、非交換的な性質を持つ合成ラベルを扱うために重み付き共形予測を利用した、不確実性定量化のための新しいフレームワークを導入した。
2. 拡張較正： 計算可能な「拡張較正」メカニズムを提案した。この革新的な手法は、leave-one-out の再適合に伴う計算負荷を取り除くと同時に、重み付き共形予測の理論的利点を保持しており、クラスタリング以外の教師なし学習にも適用可能な新しい原理を提示している。
3. 理論的保証： 推定重み手順に関する有限標本カバレッジ境界を確立した。カバレッジの損失は、推定された条件付きラベル分布と真の潜在分布との間の全変動距離（total variation distance）によって明示的に抑えられる。従来のアプローチとは異なり、このフレームワークは「replace-one（一つ置き換え）」の安定性仮定に依存しない。なぜなら、拡張メカニズムがプロセス自体を本質的に安定させるからである。

実験結果
提案手法（Algorithm 1）は、いくつかの設定において、分割共形クラスタリング（[11]）および素朴なカットオフ法と比較して評価されている：

• ガウス混合モデル (GMM): 低次元 ($R^2$) および高次元 ($R^{50}$) の両方の設定において、重み付きアプローチは、情報量の多い（より小さい）信頼集合のサイズを維持しながら、有効なカバレッジを維持する。スペクトルクラスタリングを用いた高次元設定では、分割共形法は過度に大きく情報量の乏しい集合を生成するが、重み付き手法は情報量を維持したまま機能する。
• 非線形クラスタリング: 「three moons」および「two concentric circles」のデータセットを用いた実験では、重み付き手法は、クラスタリングが困難になるにつれて情報量の乏しい集合しか生成できなくなる分割共形法と比較して、より広いノイズレベル（分散）の範囲で情報量の多い集合サイズを維持している。
• MNISTへの適用: MNISTデータセットに対するディープクラスタリングに適用したところ、本手法は不確実性の定量化に成功した。明確なクラスター中心に対しては単一要素の集合を、曖昧な境界領域に対してはより大きな集合を生成し、分類が困難な数字を正確に特定した。

意義と主張
本論文は、本研究を、創始的な共形クラスタリングの分野における実質的な前進として位置づけている。合成ラベルが分布シフトを誘発するものとして扱うことで、著者らは、先行研究（[11]）で検討された滑らかなパラメトリック混合モデルを超えて、共形予測の適用範囲を広げている。本手法は、標準的な共形アプローチが情報量の多い信頼集合を提供することに苦慮する、高次元および非線形クラスタリングのアプリケーションにおいて特に重要である。著者らは、自らのフレームワークが、基礎となるクラスタリングアルゴリズムが複雑であったり、データ分布が非標準的であったりする場合でも、有効なカバレッジ保証を提供し、より厳密で汎用性の高い不確実性定量化のアプローチを提供すると主張している。結論として、拡張較称メカニズムは、クラスタリングという特定の文脈を超えて、教師なし学習における幅広い応用可能性を持つ、より広範な方法論的原理を提示している。