コアセット

計算幾何学および近似アルゴリズムにおいて、コアセットとは、入力点集合の小さな、場合によっては重み付けされた部分集合であり、指定された最適化問題の値を近似的に保持するものです。コアセット上で問題を解くと、そのコストがデータセット全体の最適解に確実に近い解が得られます。コアセットは、理論的な保証を維持しながら計算複雑性を低減するために、幾何最適化、クラスタ分析、データストリーム、大規模機械学習などで広く使用されています。 ^{[ 1 ] [ 2 ]}

多くの幾何学的最適化問題では、近似パラメータεと次元の関数によって制限されるサイズのコアセットが許容されますが、入力サイズには依存しません。このようなコアセットを線形時間またはほぼ線形時間で構築できる場合、多項式時間近似スキーム（PTAS）または効率的な近似アルゴリズムが得られます。

コアセットの概念は、1990年代後半から2000年代初頭にかけて、計算幾何学の分野で、高次元幾何学問題に対する近似手法の開発というより広範な取り組みの一環として登場しました。初期の研究では、コアセットはレンジ空間におけるε近似やεネット、VC次元理論と関連付けられました。その後の研究により、この枠組みはクラスタリング、ストリーミングモデル、分散コンピューティングへと拡張されました。時を経て、コアセットは大規模データ分析、特にクラスタリングや回帰問題において中心的なツールとなりました。これらの問題では、膨大なデータセットに対する厳密な計算は計算上不可能です。

P を有限個の点の集合とし、f(P, x) を P 上で定義された最適化問題に対する候補解 x のコストとします。例えば、k-means クラスタリングでは、x は k 個の中心の集合を表し、f(P, x) は P 内の点から最も近い中心までの距離の二乗の合計を表します。

f に関する P の (強い) ε-コアセットは、すべての候補解 x に対して、(重み付けされる可能性のある) 部分集合 S ⊆ P であり、

${\displaystyle (1-\epsilon )\,f(P,x)\leq f(S,x)\leq (1+\epsilon )\,f(P,x),}$

ここで、ε > 0 はユーザー定義の近似パラメータである。

多くの構成では、S には重み w(p) が備わっており、

${\displaystyle f(S,x)=\sum _{p\in S}w(p)\,c(p,x),}$

ここで、c(p, x)は点pがコストに寄与する度合いを表す。

一部の文献では、以下のように区別している。

• 強力なコアセット：近似保証は、すべての候補解 x に対して一様に成り立ちます。
• 弱いコアセット：保証は最適解に近い解に対してのみ有効です。

コアセットは通常、以下の手法の1つ以上を用いて構築されます。

• 重要度サンプリング：各点は、感度（目的関数に対する相対的な影響の最大値）に比例した確率でサンプリングされます。
• ランダムサンプリングとε近似：VC理論の手法を用いて一様収束を保証する。
• 幾何学的分割：空間を分割し、各領域から代表点を選択する。
• マージ・アンド・リデュース・フレームワーク：ストリーミングや分散環境で、コアセットを長期にわたって維持するために使用されます。

多くの問題において、コアセットのサイズはO(g(ε, d))であり、dは次元であり、この上限は入力サイズnに依存しない。

ストリーミングモデルでは、データポイントは順次到着し、ストレージ容量は限られています。マージ・アンド・リデュース手法では、εと問題パラメータのみに依存する小さなコアセットを維持します。同様に、分散システムでは、構成可能なコアセットにより、各マシンがローカルコアセットを計算し、近似精度を維持しながら中央で結合することができます。

コアセットは以下に関連しています。

• 範囲空間におけるε近似とεネット
• ランダムスケッチ技法
• 次元削減
• 準線形アルゴリズムとストリーミングアルゴリズム