論文の概要: Improved Search of Relevant Points for Nearest-Neighbor Classification

• arxiv url: http://arxiv.org/abs/2203.03567v1
• Date: Mon, 7 Mar 2022 18:10:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-08 19:21:09.424594
• Title: Improved Search of Relevant Points for Nearest-Neighbor Classification
• Title（参考訳）: 近辺分類における関連点探索の改善
• Authors: Alejandro Flores-Velazco
• Abstract要約: トレーニングセットから除外された場合、トレーニングポイントが$mathbbRd$のクエリポイントの誤分類を引き起こす可能性がある場合、トレーニングポイントは関連していると言います。 出力に敏感なアルゴリズムが提案され、境界点の集合が$P$ in $O(n2 + nk2 )$ time, ここで$k$はそのような集合のサイズである。 本稿では,このアルゴリズムを,O(nk2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(n2)であることを示す。
• 参考スコア（独自算出の注目度）: 91.3755431537592
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a training set $P \subset \mathbb{R}^d$, the nearest-neighbor classifier assigns any query point $q \in \mathbb{R}^d$ to the class of its closest point in $P$. To answer these classification queries, some training points are more relevant than others. We say a training point is relevant if its omission from the training set could induce the misclassification of some query point in $\mathbb{R}^d$. These relevant points are commonly known as border points, as they define the boundaries of the Voronoi diagram of $P$ that separate points of different classes. Being able to compute this set of points efficiently is crucial to reduce the size of the training set without affecting the accuracy of the nearest-neighbor classifier. Improving over a decades-long result by Clarkson, in a recent paper by Eppstein an output-sensitive algorithm was proposed to find the set of border points of $P$ in $O( n^2 + nk^2 )$ time, where $k$ is the size of such set. In this paper, we improve this algorithm to have time complexity equal to $O( nk^2 )$ by proving that the first steps of their algorithm, which require $O( n^2 )$ time, are unnecessary.
• Abstract（参考訳）: トレーニングセット $p \subset \mathbb{r}^d$ が与えられると、最も近いneighbor分類器は、クエリポイント $q \in \mathbb{r}^d$ を最も近いポイントのクラスに$p$ で割り当てる。 これらの分類クエリに答えるために、いくつかのトレーニングポイントは他のものよりも関連性が高い。 トレーニングポイントが、トレーニングセットからの欠落が$\mathbb{r}^d$のクエリポイントの誤分類を引き起こす可能性がある場合、意味があると言う。 これらの関連点は一般に境界点として知られ、異なるクラスの点を分離する$P$のボロノイ図形の境界を定義する。 この点集合を効率的に計算できることは、最寄りの分類器の精度に影響を与えることなく、トレーニングセットのサイズを減らすことが重要である。 クラークソンによる何十年もの結果を改善するために、eppsteinの最近の論文において、出力に敏感なアルゴリズムが提案され、k$がそのような集合のサイズである$o(n^2 + nk^2 )$ time に$p$という境界点の集合を見つける。 本稿では,このアルゴリズムを,$O(nk^2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(nk^2 )$時間であることを示す。

関連論文リスト

• Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
  Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。 本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
  論文  参考訳（メタデータ） (2024-07-15T20:04:06Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
  本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。 高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。 ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
  論文  参考訳（メタデータ） (2023-10-29T16:46:26Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Reducing Nearest Neighbor Training Sets Optimally and Exactly [0.0]
  最寄りの分類では、与えられた分類を持つ$mathbbRd$の点のP$のトレーニングセットが$mathbbRd$のすべての点を$mathbbRd$の点の分類に使用される 関連する点の集合が、もし$P$ が一般的な位置にあるならば、そのような最小濃度削減訓練集合であることが示される。
  論文  参考訳（メタデータ） (2023-02-04T08:48:59Z)
• Finding Relevant Points for Nearest-Neighbor Classification [0.456877715768796]
  最寄りの分類問題では、それぞれ既知の分類を持つ$d$次元の訓練点の集合が与えられ、他の点の未知の分類を推測するために使用される。 トレーニングセットからの離脱がこれらの推論の結果を変える場合、トレーニングポイントが関係する。
  論文  参考訳（メタデータ） (2021-10-12T16:58:29Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Social Distancing is Good for Points too! [91.3755431537592]
  点が近すぎるとFCNNの動作が悪くなることを示す。 そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。 この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
  論文  参考訳（メタデータ） (2020-06-28T16:49:59Z)
• Coresets for the Nearest-Neighbor Rule [78.15296214629433]
  最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。 本稿では,最寄りの分類のためのコアセットの概念を紹介する。 そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-16T19:00:48Z)

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

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