論文の概要: Fair Column Subset Selection

• arxiv url: http://arxiv.org/abs/2306.04489v1
• Date: Wed, 7 Jun 2023 15:00:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-08 14:02:43.403283
• 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倍の大きさで同じ保証を達成する効率的なアルゴリズムを提供する。 本手法は実世界データに対する広範囲な実験を通して検証する。

関連論文リスト

• Column and row subset selection using nuclear scores: algorithms and theory for Nyström approximation, CUR decomposition, and graph Laplacian reduction [0.0]
  我々は,高速,効率的,理論的に保証された列選択のための統一手法を開発した。 まず、カーネル近似やCUR分解といったタスクに適用可能な空間分割決定アルゴリズムを導出し、実装する。 次に、保証濃度境界を満たすランダム化スキームに依存する行列自由形式を考案する。
  論文  参考訳（メタデータ） (2024-07-01T18:10:19Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Achieving Long-term Fairness in Submodular Maximization through Randomization [16.33001220320682]
  人種や性別などのセンシティブな属性を含む可能性のあるデータアイテムを扱う場合、公平性を意識したアルゴリズムを実装することが重要です。 群フェアネス制約を満たしながら単調部分モジュラ函数を最大化する問題について検討する。
  論文  参考訳（メタデータ） (2023-04-10T16:39:19Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection [9.649210683629127]
  本稿では,列列選択と行サブセット選択の同時選択の問題に対処する。 実際の列/行のサブセットを選択することで、列/行の最も構造的な情報をキャプチャするための反復的なアプローチが提案されている。 認知無線ネットワークにおける通信路とセンサ選択へのTWSPの適用を実証する。
  論文  参考訳（メタデータ） (2021-06-13T13:16:15Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• 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)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。 我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。 RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
  論文  参考訳（メタデータ） (2020-02-21T00:43:06Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。 近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。 準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
  論文  参考訳（メタデータ） (2020-01-06T23:33:31Z)

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

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