論文の概要: Max-Min Diversification with Fairness Constraints: Exact and
Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2301.02053v1
- Date: Thu, 5 Jan 2023 13:02:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-06 14:52:25.134717
- Title: Max-Min Diversification with Fairness Constraints: Exact and
Approximation Algorithms
- Title（参考訳）: 公正制約付き最大最小分散:実測および近似アルゴリズム
- Authors: Yanhao Wang and Michael Mathioudakis and Jia Li and Francesco Fabbri
- Abstract要約: 本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。
実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 17.57585822765145
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Diversity maximization aims to select a diverse and representative subset of
items from a large dataset. It is a fundamental optimization task that finds
applications in data summarization, feature selection, web search, recommender
systems, and elsewhere. However, in a setting where data items are associated
with different groups according to sensitive attributes like sex or race, it is
possible that algorithmic solutions for this task, if left unchecked, will
under- or over-represent some of the groups. Therefore, we are motivated to
address the problem of \emph{max-min diversification with fairness
constraints}, aiming to select $k$ items to maximize the minimum distance
between any pair of selected items while ensuring that the number of items
selected from each group falls within predefined lower and upper bounds. In
this work, we propose an exact algorithm based on integer linear programming
that is suitable for small datasets as well as a
$\frac{1-\varepsilon}{5}$-approximation algorithm for any $\varepsilon \in (0,
1)$ that scales to large datasets. Extensive experiments on real-world datasets
demonstrate the superior performance of our proposed algorithms over existing
ones.
- Abstract（参考訳）: 多様性の最大化は、大きなデータセットから多様で代表的なサブセットを選択することを目的としている。
データ要約、特徴選択、Web検索、レコメンダシステムなどのアプリケーションを見つけるための基本的な最適化タスクである。
しかし、データ項目が性別や人種などのセンシティブな属性に従って異なるグループに関連付けられている場合、このタスクのアルゴリズム的解決策は、未確認のままであれば、そのグループのいくつかを過小評価または過剰表現する可能性がある。
そこで我々は,各群から選択した項目の数が予め定義された下限と上限に収まることを保証しつつ,選択した項目間の最小距離を最大化するために$k$項目を選択することを目的として,フェアネス制約付き「emph{max-min diversification」の問題に取り組む。
本研究では,小さなデータセットに適した整数線形プログラミングに基づく厳密なアルゴリズムと,大規模データセットにスケールする任意の$\varepsilon \in (0, 1)$に対する$\frac{1-\varepsilon}{5}$近似アルゴリズムを提案する。
実世界のデータセットに関する広範囲な実験は、提案するアルゴリズムが既存のものよりも優れた性能を示している。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Multi-objective Binary Coordinate Search for Feature Selection [0.24578723416255746]
大規模特徴選択問題の解法として,二元多目的座標探索(MOCS)アルゴリズムを提案する。
その結果,実世界の5つの大規模データセットにおいて,NSGA-IIよりも提案手法が優れていることが示唆された。
論文 参考訳（メタデータ） (2024-02-20T00:50:26Z) - Achieving Long-term Fairness in Submodular Maximization through
Randomization [16.33001220320682]
人種や性別などのセンシティブな属性を含む可能性のあるデータアイテムを扱う場合、公平性を意識したアルゴリズムを実装することが重要です。
群フェアネス制約を満たしながら単調部分モジュラ函数を最大化する問題について検討する。
論文 参考訳（メタデータ） (2023-04-10T16:39:19Z) - Group Fairness in Non-monotone Submodular Maximization [19.29174615532181]
群フェアネス制約を考慮した非単調部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-02-03T04:51:54Z) - Low Budget Active Learning via Wasserstein Distance: An Integer
Programming Approach [81.19737119343438]
アクティブラーニング(Active Learning)とは、ラベル付きデータプールのコアサブセットをラベルに選択することで、ラベル付きデータでモデルをトレーニングするプロセスである。
本稿では,未ラベルプールからワッサーシュタイン距離を最小化するコアセットを選択するための新しい整数最適化問題を提案する。
我々の戦略は、ラベルのないプールで教師なし学習によって得られる高品質な潜伏的特徴を必要とする。
論文 参考訳（メタデータ） (2021-06-05T21:25:03Z) - Certifiably Polynomial Algorithm for Best Group Subset Selection [0.9667631210393929]
ベストグループサブセットの選択は、応答変数の最良の解釈可能性を達成するために重複しないグループの小さな部分を選択することを目的としている。
有効群を反復的に検出し,無力群を除外するグループスプライシングアルゴリズムを提案する。
提案手法の効率と精度を,合成データセットと実世界のデータセットを比較して検証する。
論文 参考訳（メタデータ） (2021-04-23T03:05:11Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z) - Optimizing Revenue while showing Relevant Assortments at Scale [1.0200170217746136]
リアルタイムアソシエーション最適化は、電子商取引業務において欠かせないものとなっている。
我々は、困難な状況下で最適なアソートを見つける高速で柔軟なアルゴリズムを設計する。
実世界のデータセットを用いた実証検証によると、我々のアルゴリズムは、アイテムの数が以前研究されたよりも105$$大きいインスタンスであっても競争力がある。
論文 参考訳（メタデータ） (2020-03-06T20:16:49Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。