論文の概要: Balancing Utility and Fairness in Submodular Maximization (Technical
Report)
- arxiv url: http://arxiv.org/abs/2211.00980v1
- Date: Wed, 2 Nov 2022 09:38:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 14:40:37.998284
- Title: Balancing Utility and Fairness in Submodular Maximization (Technical
Report)
- Title（参考訳）: 部分モジュラ最大化におけるバランシングユーティリティと公正性(技術報告)
- Authors: Yanhao Wang and Yuchen Li and Francesco Bonchi and Ying Wang
- Abstract要約: 我々は、いかなるグループに対しても有効性を最大化するために、中等ウェルオフグループの福祉を改善することを目指している。
実用性と公正性のバランスを確保するために,emphBi Submodular Maximization (BSM) という問題を提案する。
- 参考スコア（独自算出の注目度）: 27.20340546154524
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Submodular function maximization is central in numerous data science
applications, including data summarization, influence maximization, and
recommendation. In many of these problems, our goal is to find a solution that
maximizes the \emph{average} of the utilities for all users, each measured by a
monotone submodular function. When the population of users is composed of
several demographic groups, another critical problem is whether the utility is
fairly distributed across groups. In the context of submodular optimization, we
seek to improve the welfare of the \emph{least well-off} group, i.e., to
maximize the minimum utility for any group, to ensure fairness. Although the
\emph{utility} and \emph{fairness} objectives are both desirable, they might
contradict each other, and, to our knowledge, little attention has been paid to
optimizing them jointly. In this paper, we propose a novel problem called
\emph{Bicriteria Submodular Maximization} (BSM) to strike a balance between
utility and fairness. Specifically, it requires finding a fixed-size solution
to maximize the utility function, subject to the value of the fairness function
not being below a threshold. Since BSM is inapproximable within any constant
factor in general, we propose efficient data-dependent approximation algorithms
for BSM by converting it into other submodular optimization problems and
utilizing existing algorithms for the converted problems to obtain solutions to
BSM. Using real-world and synthetic datasets, we showcase applications of our
framework in three submodular maximization problems, namely maximum coverage,
influence maximization, and facility location.
- Abstract（参考訳）: サブモジュラー関数最大化は、データ要約、影響最大化、レコメンデーションなど、多くのデータサイエンスアプリケーションにおいて中心となる。
これらの問題の多くにおいて、我々のゴールは、全てのユーザに対するユーティリティの「emph{average}」を最大化するソリューションを見つけることである。
ユーザの人口が複数の人口集団で構成されている場合、別の重要な問題は、そのユーティリティがグループ間でかなり分散しているかどうかである。
部分モジュラ最適化(submodular optimization)の文脈では、任意の群の最小効用を最大化するために \emph{least well-off} 群の福祉を改善し、公平性を確保することを目指す。
emph{utility} と \emph{fairness} の目標はどちらも望ましいが、互いに矛盾する可能性がある。
本稿では,実用性と公正性のバランスをとるために,BSM(emph{Bicriteria Submodular Maximization})と呼ばれる新しい問題を提案する。
具体的には、しきい値以下でないフェアネス関数の値に従えば、ユーティリティ関数を最大化するために固定サイズの解を見つける必要がある。
BSMは一般に任意の定数係数で近似できないため、他の部分モジュラ最適化問題に変換して既存のアルゴリズムを用いてBSMの解を求めることにより、BSMの効率的なデータ依存近似アルゴリズムを提案する。
実世界および合成データセットを用いて,本フレームワークの3つのサブモジュラー最大化問題,すなわち最大カバレッジ,影響最大化,施設配置における応用例を示す。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Maximizing Submodular Functions for Recommendation in the Presence of
Biases [25.081136190260015]
サブセット選択タスクはシステムや検索エンジンで発生し、ユーザの価値を最大化する項目のサブセットを選択するように要求する。
多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。
公平性制約に基づく介入は,比例表現の確保だけでなく,バイアスの存在下での準最適性も達成できることを示す。
論文 参考訳（メタデータ） (2023-05-03T15:20:00Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-07T15:12:02Z) - Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
フェデレーテッド・ラーニング(FL)は、分散した位置データの上で、将来性のあるプライバシ保護機械学習パラダイムである。
FLにおける雑音ラベルの効果を緩和する学習に基づく再重み付け手法を提案する。
提案手法は,複数の実世界のデータセットにおいて,各種ベースラインと比較して優れた性能を示した。
論文 参考訳（メタデータ） (2022-06-11T16:21:17Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Robust Adaptive Submodular Maximization [26.171841086317574]
適応的部分モジュラー最適化問題,すなわち最悪の適応的部分モジュラーとロバストな部分モジュラーの2つの変種について検討する。
我々は,最適な最悪のケースユーティリティに対して,$frac1p+1$制約比を達成する適応的な最悪のケース欲求政策を開発する。
また、プールベースアクティブ学習サブモジュールセットカバーや適応型バイラルマーケティングなど、理論的結果のいくつかの応用についても述べる。
論文 参考訳（メタデータ） (2021-07-23T16:22:50Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Maximizing approximately k-submodular functions [21.881345069785105]
サイズ制約を考慮した$k$-submodular関数の最大化の問題を導入する。
問題は、センサー配置などのタスクでアプリケーションを見つけます。
単純な欲望アルゴリズムは、異なる種類のサイズ制約に対して近似保証を提供する。
論文 参考訳（メタデータ） (2021-01-18T16:48:40Z) - Supervised Hyperalignment for multi-subject fMRI data alignment [81.8694682249097]
本稿では,MVP解析における機能的アライメントを改善するために,SHA(Supervised Hyperalignment)手法を提案する。
マルチオブジェクトデータセットの実験では、SHA法は最大19%の性能がマルチクラス問題に対して達成されている。
論文 参考訳（メタデータ） (2020-01-09T09:17:49Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳（メタデータ） (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。