論文の概要: Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)

• arxiv url: http://arxiv.org/abs/2208.06553v3
• Date: Sat, 8 Oct 2022 08:46:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-19 10:32:27.340305
• Title: Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)
• Title（参考訳）: グループフェアネス制約下でセットを最大化する幸福度(技術報告)
• Authors: Jiping Zheng and Yuan Ma and Wei Ma and Yanhao Wang and Xiaoyang Wang
• Abstract要約: データベースから幸福セット(HMS)を見つけることは、多条件意思決定において重要な問題である。 我々は,最小幸福度を最大化するだけでなく,各グループから選択した数値が予め定義された下限と上限に収まることを保証するHMS(FairHMS)の公平な変種を提案し,検討する。
• 参考スコア（独自算出の注目度）: 16.763245893227758
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Finding a happiness maximizing set (HMS) from a database, i.e., selecting a small subset of tuples that preserves the best score with respect to any nonnegative linear utility function, is an important problem in multi-criteria decision-making. When an HMS is extracted from a set of individuals to assist data-driven algorithmic decisions such as hiring and admission, it is crucial to ensure that the HMS can fairly represent different groups of candidates without bias and discrimination. However, although the HMS problem was extensively studied in the database community, existing algorithms do not take group fairness into account and may provide solutions that under-represent some groups. In this paper, we propose and investigate a fair variant of HMS (FairHMS) that not only maximizes the minimum happiness ratio but also guarantees that the number of tuples chosen from each group falls within predefined lower and upper bounds. Similar to the vanilla HMS problem, we show that FairHMS is NP-hard in three and higher dimensions. Therefore, we first propose an exact interval cover-based algorithm called IntCov for FairHMS on two-dimensional databases. Then, we propose a bicriteria approximation algorithm called BiGreedy for FairHMS on multi-dimensional databases by transforming it into a submodular maximization problem under a matroid constraint. We also design an adaptive sampling strategy to improve the practical efficiency of BiGreedy. Extensive experiments on real-world and synthetic datasets confirm the efficacy and efficiency of our proposal.
• Abstract（参考訳）: データベースから幸福最大化集合(HMS)を見つける、すなわち、任意の非負の線形効用関数に対して最良のスコアを保持するタプルの小さなサブセットを選択することは、多重基準決定において重要な問題である。 個人からHMSを抽出し、雇用や入社などのデータ駆動型アルゴリズム決定を支援する場合、HMSが偏見や差別のない異なるグループの候補を適切に表現できることは不可欠である。 しかし、HMS問題はデータベースコミュニティで広く研究されたが、既存のアルゴリズムはグループフェアネスを考慮しておらず、いくつかのグループを表現していないソリューションを提供するかもしれない。 本稿では,最小幸福度を最大化するだけでなく,各グループから選択したタプルの数が,予め定義された下限と上限に収まることを保証したHMS(FairHMS)の公正な変種を提案する。 バニラHMS問題と同様に、FairHMSは3次元以上のNPハードであることを示す。 そこで,2次元データベース上でのFairHMSに対して,IntCovと呼ばれる正確な区間被覆に基づくアルゴリズムを提案する。 そこで本研究では,多次元データベース上のfairhmsに対するbigreedyと呼ばれるビコライトリア近似アルゴリズムを提案する。 また,BiGreedyの実用効率を向上させるため,適応型サンプリング戦略を設計する。 実世界および合成データセットに関する広範な実験により,提案手法の有効性と有効性を確認した。

関連論文リスト

• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  大規模データの爆発はシングルマシンシステムの処理能力を上回っている。 分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。 そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-30T13:22:08Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms [17.57585822765145]
  本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。 実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-05T13:02:35Z)
• Balancing Utility and Fairness in Submodular Maximization (Technical Report) [27.20340546154524]
  実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。 BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
  論文  参考訳（メタデータ） (2022-11-02T09:38:08Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Certifiably Polynomial Algorithm for Best Group Subset Selection [0.9667631210393929]
  ベストグループサブセットの選択は、応答変数の最良の解釈可能性を達成するために重複しないグループの小さな部分を選択することを目的としている。 有効群を反復的に検出し,無力群を除外するグループスプライシングアルゴリズムを提案する。 提案手法の効率と精度を,合成データセットと実世界のデータセットを比較して検証する。
  論文  参考訳（メタデータ） (2021-04-23T03:05:11Z)
• Fairness in Streaming Submodular Maximization: Algorithms and Hardness [20.003009252240222]
  本研究では,モノトーン関数と非モノトーン関数の両方に対して,不均一条件下でのサブモジュラーに対する最初のストリーミング近似を開発した。 DPPに基づく映画レコメンデーション,クラスタリングによる要約,ソーシャルネットワークにおける最大カバレッジについて検討した。
  論文  参考訳（メタデータ） (2020-10-14T22:57:07Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Supervised Hyperalignment for multi-subject fMRI data alignment [81.8694682249097]
  本稿では,MVP解析における機能的アライメントを改善するために,SHA(Supervised Hyperalignment)手法を提案する。 マルチオブジェクトデータセットの実験では、SHA法は最大19%の性能がマルチクラス問題に対して達成されている。
  論文  参考訳（メタデータ） (2020-01-09T09:17:49Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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