論文の概要: Fair Submodular Cover

• arxiv url: http://arxiv.org/abs/2407.04804v1
• Date: Fri, 5 Jul 2024 18:37:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 22:26:54.759069
• Title: Fair Submodular Cover
• Title（参考訳）: フェアサブモジュールカバー
• Authors: Wenjing Chen, Shuo Xing, Samson Zhou, Victoria G. Crawford,
• Abstract要約: フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
• 参考スコア（独自算出の注目度）: 18.37610521373708
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular optimization is a fundamental problem with many applications in machine learning, often involving decision-making over datasets with sensitive attributes such as gender or age. In such settings, it is often desirable to produce a diverse solution set that is fairly distributed with respect to these attributes. Motivated by this, we initiate the study of Fair Submodular Cover (FSC), where given a ground set $U$, a monotone submodular function $f:2^U\to\mathbb{R}_{\ge 0}$, a threshold $\tau$, the goal is to find a balanced subset of $S$ with minimum cardinality such that $f(S)\ge\tau$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(\frac{1}{\epsilon}, 1-O(\epsilon))$. We then present a continuous algorithm that achieves a $(\ln\frac{1}{\epsilon}, 1-O(\epsilon))$-bicriteria approximation ratio, which matches the best approximation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with a number of empirical evaluations that demonstrate the effectiveness of our algorithms on instances of maximum coverage.
• Abstract（参考訳）: サブモジュール最適化は、機械学習における多くのアプリケーションにおいて基本的な問題であり、しばしば性別や年齢などのセンシティブな属性を持つデータセットよりも意思決定が関与する。 このような設定では、これらの属性に対してかなり分散した多様なソリューションセットを作成することが望ましいことが多い。 このことから、FSC (Fair Submodular Cover) の研究が始められ、そこでは単調部分モジュラ函数 $f:2^U\to\mathbb{R}_{\ge 0}$、しきい値 $\tau$ が与えられたとき、$f(S)\ge\tau$ のような最小濃度の S$ の平衡部分集合を見つけることが目的である。 まず、二項近似比を$(\frac{1}{\epsilon}, 1-O(\epsilon))$とするFSCの離散アルゴリズムを導入する。 次に, フェアネス制約のない部分モジュラ被覆の最適近似保証と一致する, $(\ln\frac{1}{\epsilon}, 1-O(\epsilon))$-bicriteria近似比を得る連続アルゴリズムを提案する。 最後に,我々の理論結果を,最大カバレッジの事例におけるアルゴリズムの有効性を示す実験的な評価で補完する。

関連論文リスト

• Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications [0.0]
  我々は、fair $k$submodular問題を研究し、実行時間$mathO(knB)$で$frac13$近似を開発する。 我々は$k$-submodular関数がアクセスできないが、ほぼアクセス可能な場合にのみ近似を保証する。
  論文  参考訳（メタデータ） (2024-11-08T04:20:12Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  適応部分モジュラ函数の最小コスト被覆の問題を考える。 このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
  論文  参考訳（メタデータ） (2022-08-17T15:26:47Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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