論文の概要: Learning Partition Trees for Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2607.09909v1
- Date: Fri, 10 Jul 2026 18:59:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 15:40:48.243913
- Title: Learning Partition Trees for Nearest Neighbor Search
- Title（参考訳）: 近傍探索のための分割木学習
- Abstract要約: データ駆動型アルゴリズム設計の観点から、近接探索について検討する。
バランスの取れたハーフスペースツリーのクラスにフォーカスします。
分布的な仮定がなければ、最適なバランスの取れたハーフスペースを見つけることはNPハードであることが示される。
- 参考スコア（独自算出の注目度）: 5.425161484130288
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset \mathbb{R}^d$ of size $n$ and sample access to a query distribution over $\mathbb{R}^d$, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving $o(nd)$ query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over $\mathbb{R}^d \times \mathbb{R}^d$ and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an $α$ fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree $\tilde{O}(1/\varepsilon^2)$ that cuts at most an $O(\sqrt{α+\varepsilon})$ fraction.
- Abstract（参考訳）: データセット$P \subset \mathbb{R}^d$ of size $n$と、クエリ分布へのサンプルアクセスを$\mathbb{R}^d$とすると、その特定の分布から引き出されたクエリに最適化されたデータ構造を学ぶことが目的である。
我々は、局所性に敏感なハッシュのような空間分割フレームワークを自然に抽象化するバランスのとれたハーフスペースツリーのクラスに焦点を当てる。
データセットとクエリ分布のガウス的境界条件を仮定すると、完全木が存在すると仮定して、$o(nd)$クエリ時間を達成する木を学習する効率的なアルゴリズムが提供される。
アルゴリズムアプローチの核となるのは、平衡半空間カット問題であり、そこでは$\mathbb{R}^d \times \mathbb{R}^d$ 上の分布が与えられ、カット対の分数を最小限に抑える平衡半空間を見つけなければならない。
分布的な仮定がなければ、最適な平衡半空間を見つけることはNPハードであることが証明される。
この計算障壁を回避するために、最適半空間がペアの$α$分をカットした場合、我々のアルゴリズムは、少なくとも$O(\sqrt{α+\varepsilon})$分をカットする次数$\tilde{O}(1/\varepsilon^2)$の平衡多項式しきい値関数を出力する。
関連論文リスト
- Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。
我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
論文 参考訳（メタデータ） (2026-05-26T19:07:06Z) - Reliable Learning of Halfspaces under Gaussian Marginals [34.64644162448095]
本稿では,カライらの信頼的無知モデルにおけるPAC学習ハーフスペースの問題について検討する。
我々の主な肯定的な結果は、サンプルおよび計算複雑性を持つ$mathbbRd$上のガウス半空間の信頼性学習のための新しいアルゴリズムである。
論文 参考訳（メタデータ） (2024-11-18T02:13:11Z) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Point Location and Active Learning: Learning Halfspaces Almost Optimally [24.80812483480747]
有限集合 $X の部分集合 mathbbRd$ とバイナリ線型 $c: mathbbRd to 0,1$ が与えられたとき、$c(x)$ という形のクエリは、$X$ のすべての点のラベルを学ぶために何回必要か?
最初のほぼ最適解、深さ$tildeO(dlog(|X|))$のランダム化線形決定木を提供し、以前の$tildeO(dlog(|X))の最高値を改善する。
論文 参考訳（メタデータ） (2020-04-23T18:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。