論文の概要: Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of
Them All?
- arxiv url: http://arxiv.org/abs/2101.10905v1
- Date: Tue, 26 Jan 2021 16:13:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-13 19:34:38.485770
- Title: Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of
Them All?
- Title（参考訳）: 高次元の近くの近所をサンプリング - 誰がすべての最も公正ですか?
- Authors: Martin Aum\"uller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh,
Francesco Silvestri
- Abstract要約: 我々は、個々の公平性の観点からr$-nn問題を研究し、平等な機会を提供する。
クエリから$r$の距離内のすべてのポイントは、返されるのと同じ確率を持つ必要があります。
フェアNN問題の正確かつ近似的な変種に対して,複数の効率的なデータ構造を提案する。
- 参考スコア（独自算出の注目度）: 17.514226416388475
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Similarity search is a fundamental algorithmic primitive, widely used in many
computer science disciplines. Given a set of points $S$ and a radius parameter
$r>0$, the $r$-near neighbor ($r$-NN) problem asks for a data structure that,
given any query point $q$, returns a point $p$ within distance at most $r$ from
$q$. In this paper, we study the $r$-NN problem in the light of individual
fairness and providing equal opportunities: all points that are within distance
$r$ from the query should have the same probability to be returned. In the
low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS
2014). Locality sensitive hashing (LSH), the theoretically strongest approach
to similarity search in high dimensions, does not provide such a fairness
guarantee. In this work, we show that LSH based algorithms can be made fair,
without a significant loss in efficiency. We propose several efficient data
structures for the exact and approximate variants of the fair NN problem. Our
approach works more generally for sampling uniformly from a sub-collection of
sets of a given collection and can be used in a few other applications. We also
develop a data structure for fair similarity search under inner product that
requires nearly-linear space and exploits locality sensitive filters. The paper
concludes with an experimental evaluation that highlights the inherent
unfairness of NN data structures and shows the performance of our algorithms on
real-world datasets.
- Abstract（参考訳）: 類似性探索は基本的なアルゴリズムプリミティブであり、多くのコンピュータサイエンスの分野で広く使われている。
点のセット$S$と半径パラメータ$r>0$が与えられたとき、$r$-near neighbor$r$-NN)問題はデータ構造を求め、任意のクエリポイント$q$が与えられた場合、最大$r$から$q$までの距離内の点$p$を返す。
本稿では、個々の公平性の観点からr$-nn問題を研究し、等しく機会を提供する:クエリからの距離にあるすべてのポイントは、返される確率が同じであるべきである。
低次元の場合、この問題はHu, Qiao, Tao (PODS 2014) によって初めて研究された。
高次元での類似性探索に対する理論的に最強のアプローチである局所性敏感ハッシュ(LSH)は、そのような公平性保証を提供していない。
本研究では、LSHに基づくアルゴリズムを効率を著しく損なうことなく公平にすることができることを示す。
フェアNN問題の正確かつ近似的な変種に対して,複数の効率的なデータ構造を提案する。
このアプローチは、与えられたコレクションの集合のサブコレクションから一様にサンプリングするためにより一般的に機能し、他のいくつかのアプリケーションで使用できる。
また, 内部積の下では, ほぼ線形空間を必要とし, 局所性に敏感なフィルタを利用する, 等価類似性探索のためのデータ構造も開発した。
この論文は、NNデータ構造の本質的な不公平さを強調し、現実世界のデータセットに対するアルゴリズムのパフォーマンスを示す実験的評価で締めくくられる。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - 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) - A Combinatorial Approach to Robust PCA [18.740048806623037]
敵の汚職下でのガウスデータの回復問題について検討する。
ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。
我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
論文 参考訳（メタデータ） (2023-11-28T01:49:51Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Systematically improving existing k-means initialization algorithms at
nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。
与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
論文 参考訳（メタデータ） (2022-02-08T15:56:30Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Better Algorithms for Individually Fair $k$-Clustering [4.936817539835045]
Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
論文 参考訳（メタデータ） (2021-06-23T04:16:46Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Sample Complexity of Adversarially Robust Linear Classification on
Separated Data [41.30425613353595]
対向的堅牢性を伴う学習の複雑さについて考察する。
非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
論文 参考訳（メタデータ） (2020-12-19T22:04:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。