論文の概要: Group Fairness in Adaptive Submodular Maximization

• arxiv url: http://arxiv.org/abs/2207.03364v1
• Date: Thu, 7 Jul 2022 15:12:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-08 19:46:21.245392
• Title: Group Fairness in Adaptive Submodular Maximization
• Title（参考訳）: 適応部分モジュラー最大化における群フェアネス
• Authors: Shaojie Tang, Jing Yuan
• Abstract要約: 非適応的条件と適応的条件の両方で群フェアネス制約を受ける古典的部分モジュラー問題について検討する。 この問題に対する最初の定数近似アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 19.29174615532181
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the classic submodular maximization problem subject to a group fairness constraint under both non-adaptive and adaptive settings. It has been shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to under- or over-representation some particular groups. This motivates us to study the fair submodular maximization problem, where we aim to select a group of items to maximize a (possibly non-monotone) submodular utility function subject to a group fairness constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint.
• Abstract（参考訳）: 本稿では,非適応的および適応的設定下でのグループフェアネス制約を受ける古典的な部分モジュラー最大化問題について検討する。 データ要約、ソーシャルネットワークにおける影響最大化、パーソナライズされたレコメンデーションなど、多くの機械学習アプリケーションの有用性が、サブモジュラリティの性質を満足していることが示されている。 したがって、様々な制約を受ける部分モジュラ函数の最大化は多くの応用の中心にある。 高レベルでは、サブモジュラー最大化は、最も代表的な項目(例えばデータポイント)のグループを選択することを目的としている。 しかし、既存のほとんどのアルゴリズムの設計は公正性制約を含まないため、特定の群を下限あるいは過剰に表現する。 このことは、群フェアネス制約を受ける部分モジュライティ関数を最大化するために、アイテム群を選択しようという、公平な部分モジュライティ最大化問題の研究を動機付けている。 そこで我々は,この問題に対する最初の定数近似アルゴリズムを開発した。 本アルゴリズムの設計は,より複雑な適応条件下での極大化問題の解法に拡張できるほど頑健である。 さらに、グローバルな濃度制約を組み込むよう研究を拡大する。

関連論文リスト

• Group Fairness in Non-monotone Submodular Maximization [19.29174615532181]
  群フェアネス制約を考慮した非単調部分モジュラー問題について検討する。 この問題に対する最初の定数近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-02-03T04:51:54Z)
• 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)
• Partial-Adaptive Submodular Maximization [28.24164217929491]
  適応部分モジュラー問題に関するほとんどの研究は、完全に適応的な設定に焦点を当てている。 本稿では,バッチ内で複数の選択を同時に行うことができる部分適応部分モジュラーの問題について検討する。 我々のアプローチは、過去の選択から観察を待つ時間を削減するとともに、適応性の利点を享受します。
  論文  参考訳（メタデータ） (2021-11-01T14:48:41Z)
• Robust Adaptive Submodular Maximization [26.171841086317574]
  適応的部分モジュラー最適化問題,すなわち最悪の適応的部分モジュラーとロバストな部分モジュラーの2つの変種について検討する。 我々は,最適な最悪のケースユーティリティに対して,$frac1p+1$制約比を達成する適応的な最悪のケース欲求政策を開発する。 また、プールベースアクティブ学習サブモジュールセットカバーや適応型バイラルマーケティングなど、理論的結果のいくつかの応用についても述べる。
  論文  参考訳（メタデータ） (2021-07-23T16:22:50Z)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to a Knapsack Constraint [26.171841086317574]
  ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。 アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。 私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
  論文  参考訳（メタデータ） (2021-04-10T20:11:11Z)
• Optimization-Inspired Learning with Architecture Augmentations and Control Mechanisms for Low-Level Vision [74.9260745577362]
  本稿では,GDC(Generative, Discriminative, and Corrective)の原則を集約する,最適化に着想を得た統合学習フレームワークを提案する。 フレキシブルな組み合わせで最適化モデルを効果的に解くために,3つのプロパゲーティブモジュールを構築した。 低レベル視覚タスクにおける実験は、GDCの有効性と適応性を検証する。
  論文  参考訳（メタデータ） (2020-12-10T03:24:53Z)
• Planning with Submodular Objective Functions [118.0376288522372]
  準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。 本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
  論文  参考訳（メタデータ） (2020-10-22T16:55:12Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)

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

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