論文の概要: Fair Column Subset Selection

• arxiv url: http://arxiv.org/abs/2306.04489v3
• Date: Wed, 10 Jul 2024 11:40:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-11 22:29:23.679153
• Title: Fair Column Subset Selection
• Title（参考訳）: フェアカラムサブセットの選択
• Authors: Antonis Matakos, Bruno Ordozgoiti, Suhas Thejaswi,
• Abstract要約: 行列列を2つの群に分割した設定を考え,その目的は2つの群の最大誤差再構成を最小限に抑える列の部分集合を選択することである。 特定のシナリオでは、各グループごとに列を別々に選ぶことは避けられないため、期待される列数を2倍にする。 フェアセッティングのための決定論的レバレッジスコアサンプリング戦略を提案し、2つのグループが存在する場合、最小サイズのカラムサブセットのサンプリングがNPハードとなることを示す。
• 参考スコア（独自算出の注目度）: 6.004035936737586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of column subset selection asks for a subset of columns from an input matrix such that the matrix can be reconstructed as accurately as possible within the span of the selected columns. A natural extension is to consider a setting where the matrix rows are partitioned into two groups, and the goal is to choose a subset of columns that minimizes the maximum reconstruction error of both groups, relative to their respective best rank-k approximation. Extending the known results of column subset selection to this fair setting is not straightforward: in certain scenarios it is unavoidable to choose columns separately for each group, resulting in double the expected column count. We propose a deterministic leverage-score sampling strategy for the fair setting and show that sampling a column subset of minimum size becomes NP-hard in the presence of two groups. Despite these negative results, we give an approximation algorithm that guarantees a solution within 1.5 times the optimal solution size. We also present practical heuristic algorithms based on rank-revealing QR factorization. Finally, we validate our methods through an extensive set of experiments using real-world data.
• Abstract（参考訳）: 列サブセット選択の問題は、入力行列から列のサブセットを求め、行列は選択された列のスパン内で可能な限り正確に再構成することができる。 自然な拡張は、行列列を2つの群に分割する設定を考えることであり、その目標は、それぞれの最高ランク-k近似に対して、両方の群の最大再構成誤差を最小化する列の部分集合を選択することである。 列サブセット選択の既知の結果をこの公正な設定に拡張することは簡単ではない: あるシナリオでは、各グループごとに列を別々に選択することは避けられない。 フェアセッティングのための決定論的レバレッジスコアサンプリング戦略を提案し、2つのグループが存在する場合、最小サイズのカラムサブセットのサンプリングがNPハードとなることを示す。 これらの否定的な結果にもかかわらず、最適解の1.5倍以内の解を保証する近似アルゴリズムを与える。 また,ランク検索QR因子化に基づく実用的ヒューリスティックアルゴリズムを提案する。 最後に,実世界のデータを用いて実験を行い,本手法の有効性を検証した。

関連論文リスト

• 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)

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

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