論文の概要: Ranking with submodular functions on a budget

• arxiv url: http://arxiv.org/abs/2204.04168v1
• Date: Fri, 8 Apr 2022 16:29:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-11 14:07:19.797683
• Title: Ranking with submodular functions on a budget
• Title（参考訳）: 予算上のサブモジュラー機能を持つランキング
• Authors: Guangyi Zhang, Nikolaj Tatti, Aristides Gionis
• Abstract要約: サブモジュラー評価と予算制約を有する項目のランク付けのための新しい定式化を提案する。 基本性およびknapsack型予算制約を持つMSR問題に対して,近似保証付き実用的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 17.877243904657952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular functions has mainly been restricted in the context of selecting a set of items. On the other hand, many real-world applications require a solution that is a ranking over a set of items. The problem of ranking in the context of submodular function maximization has been considered before, but to a much lesser extent than item-selection formulations. In this paper, we explore a novel formulation for ranking items with submodular valuations and budget constraints. We refer to this problem as max-submodular ranking (MSR). In more detail, given a set of items and a set of non-decreasing submodular functions, where each function is associated with a budget, we aim to find a ranking of the set of items that maximizes the sum of values achieved by all functions under the budget constraints. For the MSR problem with cardinality- and knapsack-type budget constraints we propose practical algorithms with approximation guarantees. In addition, we perform an empirical evaluation, which demonstrates the superior performance of the proposed algorithms against strong baselines.
• Abstract（参考訳）: サブモジュラー最大化は、多くの重要な機械学習問題のバックボーンであり、バイラルマーケティング、多様化、センサー配置などに応用されている。 しかしながら、サブモジュラー関数を最大化する研究は、主に一連のアイテムを選択する文脈で制限されている。 一方、現実世界のアプリケーションの多くは、一連のアイテムをランク付けするソリューションを必要としている。 部分モジュラ函数最大化の文脈におけるランク付けの問題はこれまで検討されてきたが、項目選択の定式化よりもはるかに少ない。 本稿では,サブモジュール評価と予算制約を伴うランキング項目の新たな定式化について検討する。 この問題をmax-submodular ranking (msr) と呼ぶ。 より詳しくは、各関数が予算に関連付けられるような、項目の集合と非機能部分関数の集合を与えられたとき、予算制約の下ですべての関数によって達成される値の総和を最大化する項目の集合のランキングを見つけることを目的とする。 濃度とナップサック型予算制約を持つmsr問題に対して,近似保証付き実用的なアルゴリズムを提案する。 さらに,提案アルゴリズムの強いベースラインに対する優れた性能を示す経験的評価を行う。

関連論文リスト

• A consensus set for the aggregation of partial rankings: the case of the Optimal Set of Bucket Orders Problem [46.752018687842344]
  ランクアグリゲーション問題(RAP)では、解は通常、一連の入力順序を一般化するコンセンサスランキングである。 我々は、RAPの解決策として、入力順序に表される嗜好をよりよく説明するためのランキングのセットを提案する。
  論文  参考訳（メタデータ） (2025-02-19T14:32:16Z)
• 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)
• Streaming Adaptive Submodular Maximization [19.29174615532181]
  実用関数の新しいクラス、半政治的な部分モジュラー関数を導入する。 本研究では,ストリームベース環境下での半政治的部分モジュラ関数の最大化に有効なアルゴリズムの開発を行う。
  論文  参考訳（メタデータ） (2022-08-17T02:05:10Z)
• Group Equality in Adaptive Submodular Maximization [13.619980548779687]
  非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。 この問題に対する最初の定数近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-07T15:12:02Z)
• 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)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to a Knapsack Constraint [26.171841086317574]
  ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。 アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。 私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
  論文  参考訳（メタデータ） (2021-04-10T20:11:11Z)
• 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)

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

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