論文の概要: Fair Column Subset Selection
- arxiv url: http://arxiv.org/abs/2306.04489v2
- Date: Tue, 13 Jun 2023 10:19:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 16:47:53.747145
- Title: Fair Column Subset Selection
- Title(参考訳): fair column subset のセレクション
- Authors: Antonis Matakos, Bruno Ordozgoiti, Suhas Thejaswi
- Abstract要約: 既知の結果を拡張するために、元の方法の2倍の列を単純に選択する簡単な解よりは、よい方法がないことを示す。
我々は、決定論的レバレッジスコアサンプリングに基づく既知のアプローチを採用し、適切なサイズのサブセットをサンプリングするだけで、2つのグループが存在する場合、NPハードとなることを示す。
- 参考スコア(独自算出の注目度): 2.1442379717388795
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of fair column subset selection. In particular, we
assume that two groups are present in the data, and the chosen column subset
must provide a good approximation for both, relative to their respective best
rank-k approximations. We show that this fair setting introduces significant
challenges: in order to extend known results, one cannot do better than the
trivial solution of simply picking twice as many columns as the original
methods. We adopt a known approach based on deterministic leverage-score
sampling, and show that merely sampling a subset of appropriate size becomes
NP-hard in the presence of two groups. Whereas finding a subset of two times
the desired size is trivial, we provide an efficient algorithm that achieves
the same guarantees with essentially 1.5 times that size. We validate our
methods through an extensive set of experiments on real-world data.
- Abstract(参考訳): 公平な列部分集合の選択の問題を考える。
特に、2つの群がデータ内に存在すると仮定し、選択された列部分集合は、それぞれのランクk近似に対して両者に良い近似を与える必要がある。
既知の結果を拡張するためには、元の方法の2倍の列を単に選択するという、簡単な解決策以上のことはできない。
我々は、決定論的レバレッジスコアサンプリングに基づく既知のアプローチを採用し、適切なサイズのサブセットをサンプリングするだけで、2つのグループが存在する場合、NPハードとなることを示す。
所望のサイズの2倍のサブセットを見つけることは自明だが、基本的にその1.5倍の大きさで同じ保証を達成する効率的なアルゴリズムを提供する。
本手法は実世界データに対する広範囲な実験を通して検証する。
関連論文リスト
- A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-12-17T04:41:07Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳(メタデータ) (2023-08-13T10:09:25Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳(メタデータ) (2023-05-22T17:43:34Z) - A One-shot Framework for Distributed Clustered Learning in Heterogeneous
Environments [54.172993875654015]
異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。
ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。
厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
論文 参考訳(メタデータ) (2022-09-22T09:04:10Z) - Happiness Maximizing Sets under Group Fairness Constraints (Technical
Report) [16.763245893227758]
データベースから幸福セット(HMS)を見つけることは、多条件意思決定において重要な問題である。
我々は,最小幸福度を最大化するだけでなく,各グループから選択した数値が予め定義された下限と上限に収まることを保証するHMS(FairHMS)の公平な変種を提案し,検討する。
論文 参考訳(メタデータ) (2022-08-13T02:54:29Z) - Certifiably Polynomial Algorithm for Best Group Subset Selection [0.9667631210393929]
ベストグループサブセットの選択は、応答変数の最良の解釈可能性を達成するために重複しないグループの小さな部分を選択することを目的としている。
有効群を反復的に検出し,無力群を除外するグループスプライシングアルゴリズムを提案する。
提案手法の効率と精度を,合成データセットと実世界のデータセットを比較して検証する。
論文 参考訳(メタデータ) (2021-04-23T03:05:11Z) - Partitioned Least Squares [1.0312968200748116]
新たな定式化は凸ではなく,この問題に対処するための2つの代替手法を提供する。
完全性のために、分割数が大きすぎる場合に正確な方法の代わりに使用できる代替分岐および有界アルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-06-29T17:10:32Z) - Self-Representation Based Unsupervised Exemplar Selection in a Union of
Subspaces [27.22427926657327]
表現係数の $ell_1$ ノルムによって測定されたすべてのデータポイントを最もよく再構成する部分集合を探索する新しい指数選択モデルを提案する。
データセットが独立部分空間の和から引き出されるとき、我々の方法は各部分空間から十分な数の代表を選択できる。
また,不均衡なデータに対して頑健で,大規模データに対して効率の良い,模範的なサブスペースクラスタリング手法も開発している。
論文 参考訳(メタデータ) (2020-06-07T19:43:33Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳(メタデータ) (2020-04-23T05:00:21Z) - LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set
Similarity Under Skew [58.21885402826496]
全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。
我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。
LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
論文 参考訳(メタデータ) (2020-03-06T00:06:20Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳(メタデータ) (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。