論文の概要: Reducing Nearest Neighbor Training Sets Optimally and Exactly
- arxiv url: http://arxiv.org/abs/2302.02132v1
- Date: Sat, 4 Feb 2023 08:48:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-07 20:06:59.206750
- Title: Reducing Nearest Neighbor Training Sets Optimally and Exactly
- Title（参考訳）: 最寄りのトレーニングセットを最適かつ正確に削減する
- Authors: Josiah Rohrer and Simon Weber
- Abstract要約: 最寄りの分類では、与えられた分類を持つ$mathbbRd$の点のP$のトレーニングセットが$mathbbRd$のすべての点を$mathbbRd$の点の分類に使用される
関連する点の集合が、もし$P$ が一般的な位置にあるならば、そのような最小濃度削減訓練集合であることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In nearest-neighbor classification, a training set $P$ of points in
$\mathbb{R}^d$ with given classification is used to classify every point in
$\mathbb{R}^d$: Every point gets the same classification as its nearest
neighbor in $P$. Recently, Eppstein [SOSA'22] developed an algorithm to detect
the relevant training points, those points $p\in P$, such that $P$ and
$P\setminus\{p\}$ induce different classifications. We investigate the problem
of finding the minimum cardinality reduced training set $P'\subseteq P$ such
that $P$ and $P'$ induce the same classification. We show that the set of
relevant points is such a minimum cardinality reduced training set if $P$ is in
general position. Furthermore, we show that finding a minimum cardinality
reduced training set for possibly degenerate $P$ is in P for $d=1$, and
NP-complete for $d\geq 2$.
- Abstract（参考訳）: near-neighbor分類では、与えられた分類を持つ$\mathbb{r}^d$のポイントの訓練セットが$\mathbb{r}^d$のすべてのポイントを分類するために使用される。
最近、Eppstein [SOSA'22] は関連するトレーニングポイント、例えば$P$ や $P\setminus\{p\}$ などを検出するアルゴリズムを開発した。
最小濃度低減トレーニングセット $p'\subseteq p$ を見つける問題は、$p$ と $p'$ が同じ分類を誘導するように検討する。
p$ が一般的な位置にある場合、関連する点の集合は最小濃度低減訓練集合であることを示す。
さらに、P$を縮退させる可能性のある最小濃度のトレーニングセットを見つけることは、$d=1$でP、$d\geq 2$でNP完全であることを示す。
関連論文リスト
- 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) - 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) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z) - Coresets for the Nearest-Neighbor Rule [78.15296214629433]
最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。
本稿では,最寄りの分類のためのコアセットの概念を紹介する。
そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-16T19:00:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。