🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

本論文では、K近傍グラフを活用することで、既存の勾配近似手法と同等の精度を維持しつつ、時間およびメモリコストを大幅に削減しながら代表的なデータサブセットを効率的に特定する、軽量なコアセット選択手法であるKNNG-CSを提案する。

原著者： Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

公開日 2026-08-18

📖 1 分で読めます☕ さくっと読める

原著者： Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

機械学習モデルは、写真の顔認識から株価の動向予測に至るまで、多くの現代的なツールの背後にあるエンジンです。これらのタスクを実行する方法を学ぶために、モデルには膨大な量のデータを入力する必要があります。図書館にあるすべての本を学生に与えて教えようとしている場面を想像してみてください。学生は最終的に学習するでしょうが、そのプロセスは非常に遅く、消耗するものです。人工知能の世界において、巨大なデータセットで学習することは、まさにこれが現実です。それには膨大な計算能力とメモリが必要であり、多くの場合、実用的なアプリケーションにとってはコストがかかりすぎたり、時間がかかりすぎたりします。これを解決するために、科学者たちは「コアセット選択（coreset selection）」と呼ばれる手法を用いています。その目的は単純です。図書館全体を使う代わりに、すべての不可欠な教訓が含まれている、小さくて完璧な本のサブセットを見つけることです。もしこの極めて小さく、代表的なサンプルを用いてモデルを訓練できれば、モデルはすべてを読んだ場合と同じくらいよく学習できますが、わずかな時間と、はるかに少ないメモリで実現できるのです。

長年、これら小さくて完璧なサブセットを見つけるための最善の方法は、計算負荷の高い手法に依存してきました。既存のアプローチは、どのデータポイントが互いに最も類似しているかを確認するために、すべてのデータポイント間の距離を測定しようとします。これは、群衆の中から最適な代表者を見つけるために、部屋にいる全員に他の全員との距離を測らせるようなものです。これは機能しますが、特にデータセットが大きくなると、保存や処理が困難な膨大な量のデータを生み出します。西安電子科技大学の研究者とその共同研究者たちは、この「すべてを測定する」というアプローチが非効率であることに気づきました。彼らは、データセットにおける最も有用な代表者は、通常、孤立して立っているものではなく、似たもの同士が集まる密なグループの中央に位置しているものであることを観察しました。多くの他のものに近いサンプルは共通のパターンを表している可能性が高い一方で、孤立したサンプルは大きなグループの代わりを務めるには適していません。

これに対処するため、チームは「KNNG-CS」と呼ばれる新しい手法を開発しました。すべてのアイテムに他のすべてのアイテムとの距離を強制的に測定させる代わりに、彼らは各アイテムを最も近い10個の隣接点にのみ接続するマップを作成しました。これにより、あらゆる可能な接続を計算するという圧倒的な負担を負うことなく、データポイント間の局所的な関係を捉える疎なネットワーク、すなわちグラフが作成されます。このマップが構築されると、研究者たちは、どれだけの数の他のアイテムが自分を隣接点として指し示したか、そしてそれらの隣接点がどれほど近いかに基づいて、各アイテムにスコアを割り当てました。多くの他のアイテムから近い隣接点として頻繁に選ばれたアイテムは、高いスコアを受け取り、非常に重要な代表者であることを示しました。アルゴリズムは、その後、最も高いスコアを得たアイテムを貪欲に選択して、最終的な小さなサブセットを形成しました。高スコアのアイテムが一つ選ばれるごとに、アルゴリズムはそのアイテムとその隣接点をプールから削除し、冗長性なくデータセット全体を効率的にカバーするようにしました。

森林被覆タイプ、映画の評価、クレジットカードのデフォルト（債務不履行）など、4つの実世界のデータセットでテストした際、この新手法の結果は驚くべきものでした。この新手法は、機械学習モデルが既存の最良の手法と同等の精度を達成できる小さなトレーニングセットを作成しました。しかし、効率性の違いは劇的でした。新手法は、従来の主要な技術よりも2.3倍から41.2倍速く動作しました。さらに印象的だったのは、メモリ使用量の削減です。古い手法は、数ギガバイトのメモリを消費する可能性のある膨大な距離テーブルの保存を必要としましたが、新しいアプローチは、そのわずか0.3%から7.5%のメモリしか使用しませんでした。実用的な観点から言えば、これは以前は高価でハイエンドなサーバーを必要としていたタスクが、より小さく、よりアクセスしやすいマシンで実行できるようになったことを意味します。研究者たちは、非常に小さなデータサブセットを用いても、モデルが効果的に学習し、フルデータセットで訓練する場合よりもはるかに早く安定した解に収束することを発見しました。

この研究は、局所的な関係に焦点を当てることで、機械学習のためのデータ準備プロセスを劇的に簡素化できることを示しています。この研究は、最も重要なデータポイントを見つけるために、あらゆる可能な距離を計算する必要はないこと、スマートなローカルマップがあれば十分であることを裏付けています。グラフベースの戦略を用いることで、研究者たちは、高品質なモデル訓練が、以前必要と考えられていた時間とリソースのわずかな一部で達成できることを示しました。これは、最終的な結果の質を損なうことなく、計算能力が限られた環境においても、より複雑なモデルの開発と展開を可能にする扉を開くものです。

技術要約：K-最近傍グラフを用いた効率的なコアセット選択

問題定義

コアセット選択は、大規模な訓練セットを小さく代表的なサブセットに置き換えることで、機械学習モデルのトレーニングにおける計算コストとメモリコストを削減することを目的としています。本論文は、**勾配近似（GA）**に基づくコアセット選択に焦点を当てています。このフレームワークにおける目標は、訓練セット $T$ からサイズ $M$ のサブセット $C$ を選択し、全データセットの勾配がそのサブセットによって十分に近似されるようにすることです。この問題は、すべてのデータポイントが選択されたコアセット内の最近傍によって代表されるという、特徴空間における代表誤差（式1）を最小化することへと数学的に還元されます。

CRAIGやFastCoreといった既存のGAベースの手法は、貪欲な選択戦略に依存しています。しかし、これらは重大なスケーラビリティの問題に直面しています。

CRAIGは、高密度のペアワイズ距離行列を事前計算するため、 $O(n^2)$ の空間量と $O(n^2d)$ の時間を必要とし、大規模なデータセットでは実行不可能になります。
FastCoreは、メモリ節約のためにアイテム間の距離をアイテムとクラスターの上界に置き換えますが、精度を維持するために膨大な数のクラスター（数百から数万個）を必要とすることが多く、大規模な境界行列の計算と保存に多大なオーバーヘッドが生じます。

著者らは、特徴空間における代表性は本質的に局所的であることに注目しました。多くの他のサンプルに対して近い近傍として機能するサンプルは、近似誤差の低い、密な局所領域を代表している可能性が高いといえます。既存の手法は、密な構造に依存しているため、この局所性を効率的に活用できていません。

手法：KNNG-CS

本論文では、K-最近傍グラフ（KNNG）に基づく軽量なコアセット選択手法であるKNNG-CSを提案しています。この手法は、主に3つの段階で動作します。

1. 近似KNNGの構築

すべてのペアワイズ距離を計算する代わりに、特徴ベクトルに対して近似的なKNNG $G=(V, E)$ を構築します。各ノード $x_i$ は、自身の $K$ 個の最近傍に接続されます。

効率性: 最先端の近似手法（例：KGraph）を使用することで、構築時間は $O(n^{1.14}d)$ となり、空間計算量は定数 $K$ （実験では10に設定）を用いた線形 $O(nK)$ となります。これにより、密な行列による二次的な空間要件を回避できます。

2. 距離を考慮したノード・スコアリング

核心となるイノベーションは、KNNG内の局所的な近傍構造に基づいて、各ノード（データ項目）の重要度を推定するスコアリング関数です。

入次数（In-Degree）: 多くのノードから最近傍として指されているノード（高い入次数を持つノード）は、代表性の強い候補となります。
距離の考慮: 入次数だけでは不十分です。本手法は、エッジの距離をソフトマックス関数（式2）を用いて確率に変換することで、距離情報を組み込みます。
スコアリング公式: ノード $v_i$ の重要度スコア $P_i$ は、すべての流入エッジのソフトマックス確率の合計です（式3）：
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
ここで、 $p_{ji}$ は隣接ノード $v_j$ から $v_i$ への正規化された近接重みを表します。これにより、入次数が同じであっても、隣接ノードとの近接度が異なるノードを区別することが可能になります。

3. 冗長性除去を伴う貪欲な選択

選択プロセスは、ワンパスの貪欲アルゴリズムです。

すべてのノードの重要度スコア $P_i$ を計算します。
スコアが最も高いノードを選択し、コアセット $C$ に追加します。
冗長性除去: 選択されたノードと、そのすべての**入隣接ノード（in-neighbors）**をグラフから直ちに削除します。その根拠は、あるノードが選択された場合、その入隣接ノード（そのノードを近い近傍とみなしているもの）は選択されたノードによって代表されるため、自身を選択する必要がないからです。
$M$ 個のアイテムが選択されるまで繰り返します。

このアプローチは、従来の貪欲法における大きなボトルネックであった、繰り返しのベネフィット再計算を回避します。

主な貢献

KNNG-CS アルゴリズム: 高価な密な距離構造を避けるために、疎なK-最近傍グラフを利用した、スケーラブルなGAベースのコアセット選択手法。
新規のスコアリングメカニズム: 密なペアワイズ距離を保持することなく、KNNGから直接、距離を考慮した流入隣接ノード・スコアリングを行う手法。
効率性の向上: 本手法が、コアセットの品質を同等の水準に保ちつつ、選択時間とメモリ使用量を大幅に削減できることを実証した経験的検証。

実験結果

著者らは、4つの実世界のデータセット（CovType、IMDB、Brazil、Card）を用いてKNNG-CSを評価しました。彼らの手法を、ランダムサンプリング、CRAIG、およびFastCoreと比較しました。

有効性（精度）: KNNG-CSは、CRAIGやFastCoreと同等のテスト精度を達成し、ランダムサンプリングよりも有意に優れた結果を示しました。CRAIGは厳密な距離を使用しているため、一部のデータセット（IMDB, Card, Brazil）でわずかに高い精度を示しましたが、KNNG-CSは競争力のある性能を維持しました。
効率性（時間）: KNNG-CSは大幅な高速化を実現しました。
- CRAIGより2.3倍〜41.2倍高速。
- FastCoreより2.3倍〜4.9倍高速。
  この高速化は、効率的なKNNG構築と、行列計算を必要としないワンパスの貪欲選択戦略によるものです。
メモリ使用量: KNNG-CSはピークメモリ消費量を劇的に削減しました。
- CRAIGが使用したピークメモリのわずか0.3%〜3.4%。
- FastCoreが使用したピークメモリのわずか4.1%〜7.5%。
  これは、競合手法が $O(n^2)$ の距離行列や大規模なアイテム・クラスター境界行列を保持するのに対し、KNNG-CSは $O(nK)$ のエッジのみを保持するためです。
収束: 選択されたコアセットでのトレーニングは、フルデータセットでのトレーニングよりも（イテレーション数において）はるかに速く収束しました。コアセットサイズ $M=0.01n$ が、効率性と有効性の良好なバランスを提供しました。

意義と主張

本論文は、KNNG-CSが、密なグローバル距離構造から疎なローカル近傍構造へと転換することで、大規模なコアセット選択に対する実用的な解決策を提供すると主張しています。特徴空間の固有の局所性を活用することで、以下の実現を可能にします。

従来の最先端手法の二次的な複雑性（ $O(n^2)$ ）に対し、線形ストレージ複雑性（$O(nK)$）を実現。
コアセットの品質を損なうことなく、時間とメモリの両方のコストを大幅に削減。
繰り返しの距離計算を不要にする、軽量な選択プロセス。

著者らは、このアプローチにより、従来の勾配近似手法では計算またはメモリの制約により困難であった大規模データセットに対しても、効率的なコアセット選択が可能になると結論付けています。