論文の概要: Maximizing Submodular Functions for Recommendation in the Presence of
Biases
- arxiv url: http://arxiv.org/abs/2305.02806v1
- Date: Wed, 3 May 2023 15:20:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 15:34:17.212010
- Title: Maximizing Submodular Functions for Recommendation in the Presence of
Biases
- Title（参考訳）: ビアーゼ存在下での勧告のための部分モジュラー関数の最大化
- Authors: Anay Mehrotra and Nisheeth K. Vishnoi
- Abstract要約: サブセット選択タスクはシステムや検索エンジンで発生し、ユーザの価値を最大化する項目のサブセットを選択するように要求する。
多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。
公平性制約に基づく介入は,比例表現の確保だけでなく,バイアスの存在下での準最適性も達成できることを示す。
- 参考スコア（独自算出の注目度）: 25.081136190260015
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subset selection tasks, arise in recommendation systems and search engines
and ask to select a subset of items that maximize the value for the user. The
values of subsets often display diminishing returns, and hence, submodular
functions have been used to model them. If the inputs defining the submodular
function are known, then existing algorithms can be used. In many applications,
however, inputs have been observed to have social biases that reduce the
utility of the output subset. Hence, interventions to improve the utility are
desired. Prior works focus on maximizing linear functions -- a special case of
submodular functions -- and show that fairness constraint-based interventions
can not only ensure proportional representation but also achieve near-optimal
utility in the presence of biases. We study the maximization of a family of
submodular functions that capture functions arising in the aforementioned
applications. Our first result is that, unlike linear functions,
constraint-based interventions cannot guarantee any constant fraction of the
optimal utility for this family of submodular functions. Our second result is
an algorithm for submodular maximization. The algorithm provably outputs
subsets that have near-optimal utility for this family under mild assumptions
and that proportionally represent items from each group. In empirical
evaluation, with both synthetic and real-world data, we observe that this
algorithm improves the utility of the output subset for this family of
submodular functions over baselines.
- Abstract（参考訳）: サブセット選択タスクはレコメンデーションシステムや検索エンジンで発生し、ユーザにとっての価値を最大化する項目のサブセットを選択する。
部分集合の値はしばしば減少する戻り値を示し、従って、部分モジュラ函数はそれらをモデル化するために用いられる。
部分モジュラ函数を定義する入力が既知の場合、既存のアルゴリズムを用いることができる。
しかし、多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。
したがって、効用を改善するための介入が望まれる。
先行研究は、線型関数の最大化(部分モジュラー関数の特別な場合)に焦点を当て、公正性制約に基づく介入が比例表現を保証するだけでなく、バイアスの存在下で準最適効用を達成することを示す。
上記の応用で生じる関数をキャプチャするサブモジュラー関数のファミリーの最大化について検討する。
最初の結果は、線形関数とは異なり、制約に基づく介入は、この部分モジュラ函数の族に対する最適ユーティリティの定数を保証できないということである。
第2の結果はサブモジュラー最大化のアルゴリズムである。
このアルゴリズムは、穏やかな仮定の下でこの族に最適に近い効用を持つ部分集合を、各群から比例的に表現する。
経験的評価では、合成データと実世界のデータの両方を用いて、このアルゴリズムはベースライン上のサブモジュール関数の族に対する出力サブセットの有用性を改善する。
関連論文リスト
- Learning Submodular Sequencing from Samples [11.528995186765751]
本稿では,いくつかの複合部分モジュラー関数を最適化するために,シーケンス内の項目の選択とランク付けの問題に対処する。
本稿では,各部分モジュラ関数の曲率に依存する近似比を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-09T01:33:13Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。
本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
論文 参考訳（メタデータ） (2022-10-20T06:00:45Z) - Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
多くの標準部分モジュラーアルゴリズムに対して、単調性比に依存する新しい近似保証を証明できることが示される。
これにより、映画レコメンデーション、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比が向上する。
論文 参考訳（メタデータ） (2022-02-07T10:35:40Z) - Sparsification of Decomposable Submodular Functions [27.070004659301162]
サブモジュール関数は多くの機械学習とデータマイニングタスクの中核にある。
元の関数の根底にある部分モジュラ関数の数がとても多いので、処理に多くの時間が必要で、あるいはメインメモリに収まらない場合もあります。
分解可能部分モジュラ函数に対するスパーシフィケーションの概念を導入し、元の関数の正確な近似を得る目的は、少数の部分モジュラ函数の(重み付けされた)和である。
論文 参考訳（メタデータ） (2022-01-18T20:05:25Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Planning with Submodular Objective Functions [118.0376288522372]
準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。
本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
論文 参考訳（メタデータ） (2020-10-22T16:55:12Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。