論文の概要: Coresets for the Nearest-Neighbor Rule

• arxiv url: http://arxiv.org/abs/2002.06650v3
• Date: Wed, 22 Jul 2020 19:14:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 17:57:16.323970
• Title: Coresets for the Nearest-Neighbor Rule
• Title（参考訳）: 最近傍ルールのコアセット
• Authors: Alejandro Flores-Velazco, David M. Mount
• Abstract要約: 最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。 本稿では,最寄りの分類のためのコアセットの概念を紹介する。 そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 78.15296214629433
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a training set $P$ of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset $R \subseteq P$ such that for every point $p \in P$, $p$'s nearest-neighbor in $R$ has the same label as $p$. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set. This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.
• Abstract（参考訳）: ラベル付きポイントのトレーニングセットが与えられると、最も近いneighborルールは、ラベル付きクエリポイントのクラスを、セット内の最も近いポイントのラベルとして予測する。 分類の時間と空間の複雑さを改善するために、自然な疑問は、最寄りのルールの正確性に大きな影響を及ぼすことなく、トレーニングセットを減らす方法である。 near-neighbor condensation はサブセット $r \subseteq p$ を見つけることで、すべての点に対して$p \in p$、$p$ の最も近いneighbor in $r$ は$p$ と同じラベルを持つ。 これは、コアセットの正確な結果が元の集合上の近似結果に対応するような集合の部分集合として広く定義できるコアセットの概念に関連している。 しかしながら、コアセットの保証は、任意のクエリポイントに対して、トレーニングセットのポイントだけでなく、保持される。 本稿では,最寄り-neighbor分類のためのコアセットの概念を紹介する。 凝縮に用いる既存の基準を拡張し、これらのサブセットを使用する場合、クエリポイントを正しく分類するのに十分な条件を証明します。 さらに,そのような最小濃度部分集合の探索はnpハードであることを証明し,選択した部分集合の大きさで証明可能な上限値を持つ二次時間近似アルゴリズムを提案する。 さらに、これらのアルゴリズムのうちの1つをサブクアクラティックランタイムにする方法を示し、このタイプの凝縮の最初のものである。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
  本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。 高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。 ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
  論文  参考訳（メタデータ） (2023-10-29T16:46:26Z)
• Reducing Nearest Neighbor Training Sets Optimally and Exactly [0.0]
  最寄りの分類では、与えられた分類を持つ$mathbbRd$の点のP$のトレーニングセットが$mathbbRd$のすべての点を$mathbbRd$の点の分類に使用される 関連する点の集合が、もし$P$ が一般的な位置にあるならば、そのような最小濃度削減訓練集合であることが示される。
  論文  参考訳（メタデータ） (2023-02-04T08:48:59Z)
• Improved Search of Relevant Points for Nearest-Neighbor Classification [91.3755431537592]
  トレーニングセットから除外された場合、トレーニングポイントが$mathbbRd$のクエリポイントの誤分類を引き起こす可能性がある場合、トレーニングポイントは関連していると言います。 出力に敏感なアルゴリズムが提案され、境界点の集合が$P$ in $O(n2 + nk2 )$ time, ここで$k$はそのような集合のサイズである。 本稿では,このアルゴリズムを,O(nk2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(n2)であることを示す。
  論文  参考訳（メタデータ） (2022-03-07T18:10:27Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。 $cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。 $mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
  論文  参考訳（メタデータ） (2021-10-19T17:43:50Z)
• Finding Relevant Points for Nearest-Neighbor Classification [0.456877715768796]
  最寄りの分類問題では、それぞれ既知の分類を持つ$d$次元の訓練点の集合が与えられ、他の点の未知の分類を推測するために使用される。 トレーニングセットからの離脱がこれらの推論の結果を変える場合、トレーニングポイントが関係する。
  論文  参考訳（メタデータ） (2021-10-12T16:58:29Z)
• Social Distancing is Good for Points too! [91.3755431537592]
  点が近すぎるとFCNNの動作が悪くなることを示す。 そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。 この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
  論文  参考訳（メタデータ） (2020-06-28T16:49:59Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。