論文の概要: Non-monotone Sequential Submodular Maximization
- arxiv url: http://arxiv.org/abs/2308.08641v1
- Date: Wed, 16 Aug 2023 19:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-21 18:55:03.054093
- Title: Non-monotone Sequential Submodular Maximization
- Title（参考訳）: 非単調シーケンシャル・サブモジュラー最大化
- Authors: Shaojie Tang and Jing Yuan
- Abstract要約: 我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
- 参考スコア（独自算出の注目度）: 13.619980548779687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study a fundamental problem in submodular optimization,
which is called sequential submodular maximization. Specifically, we aim to
select and rank a group of $k$ items from a ground set $V$ such that the
weighted summation of $k$ (possibly non-monotone) submodular functions $f_1,
\cdots ,f_k: 2^V \rightarrow \mathbb{R}^+$ is maximized, here each function
$f_j$ takes the first $j$ items from this sequence as input. The existing
research on sequential submodular maximization has predominantly concentrated
on the monotone setting, assuming that the submodular functions are
non-decreasing. However, in various real-world scenarios, like diversity-aware
recommendation systems, adding items to an existing set might negatively impact
the overall utility. In response, this paper pioneers the examination of the
aforementioned problem with non-monotone submodular functions and offers
effective solutions for both flexible and fixed length constraints, as well as
a special case with identical utility functions. The empirical evaluations
further validate the effectiveness of our proposed algorithms in the domain of
video recommendations. The results of this research have implications in
various fields, including recommendation systems and assortment optimization,
where the ordering of items significantly impacts the overall value obtained.
- Abstract（参考訳）: 本稿では,部分モジュラー最適化における基本問題である逐次部分モジュラー最大化について検討する。
具体的には、$k$ の部分モジュラ函数 $f_1, \cdots ,f_k: 2^V \rightarrow \mathbb{R}^+$ の重み付け和が最大になるような基底集合 $V$ から$k$ の項目群を選択してランク付けすることを目的としており、各関数 $f_j$ はこの列から最初の$j$ を入力として取る。
シーケンシャルなサブモジュラー最大化に関する既存の研究は、サブモジュラー関数が非減退であると仮定して、モノトーンの設定に集中している。
しかし、多様性を意識したレコメンデーションシステムのような現実世界の様々なシナリオでは、既存のセットにアイテムを追加することは、全体的なユーティリティに悪影響を及ぼす可能性がある。
そこで本研究では, 単調でない部分モジュラー関数の問題点を解明し, フレキシブルと固定長の制約と, 同一の実用機能を持つ特別な場合の両方に対して有効な解を提供する。
ビデオレコメンデーション領域における提案アルゴリズムの有効性を実証的評価により検証した。
本研究は,項目の順序付けが得られた全体的な価値に大きく影響する,推薦システムやアソシエーション最適化など,さまざまな分野に影響を及ぼす。
関連論文リスト
- Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-07-05T18:37:09Z) - Maximizing Submodular Functions for Recommendation in the Presence of
Biases [25.081136190260015]
サブセット選択タスクはシステムや検索エンジンで発生し、ユーザの価値を最大化する項目のサブセットを選択するように要求する。
多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。
公平性制約に基づく介入は,比例表現の確保だけでなく,バイアスの存在下での準最適性も達成できることを示す。
論文 参考訳（メタデータ） (2023-05-03T15:20:00Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Ranking with submodular functions on a budget [17.877243904657952]
サブモジュラー評価と予算制約を有する項目のランク付けのための新しい定式化を提案する。
基本性およびknapsack型予算制約を持つMSR問題に対して,近似保証付き実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-08T16:29:45Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Multi-objective Evolutionary Algorithms are Generally Good: Maximizing
Monotone Submodular Functions over Sequences [44.11102526976392]
本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。
EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。
例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
論文 参考訳（メタデータ） (2021-04-20T10:36:10Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - 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) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。