異方性ベクトル量子化による大規模推論の加速

トレーニングセット P ⊂ ℝᵈ が与えられたとき、最近傍分類器は任意のクエリポイント q ∈ ℝᵈ を P の最も近いポイントのクラスに割り当てます。これらの分類クエリに答えるために、一部のトレーニングポイントは他のポイントよりも関連性があります。トレーニングポイントが関連性があると言うのは、そのトレーニングセットからの除外が ℝᵈ のいくつかのクエリポイントの誤分類を引き起こす可能性がある場合です。これらの関連ポイントは通常、ボーダーポイントとして知られており、異なるクラスのポイントを分ける P のヴォロノイ図の境界を定義します。このポイントのセットを効率的に計算できることは、最近傍分類器の精度に影響を与えずにトレーニングセットのサイズを削減するために重要です。Clarkson（FOCS'94）による数十年にわたる結果を改善し、Eppstein（SOSA’22）は近年、𝒪(n² + nk²) 時間で P のボーダーポイントのセットを見つけるための出力に敏感なアルゴリズムを提案しました。ここで、k はそのようなセットのサイズです。本論文では、彼らのアルゴリズムの第1フェーズが 𝒪(n²) の時間を必要とすることが不要であることを証明することにより、このアルゴリズムの時間計算量を 𝒪(nk²) に改善します。