論文の概要: Learning Submodular Sequencing from Samples

• arxiv url: http://arxiv.org/abs/2409.05265v1
• Date: Mon, 9 Sep 2024 01:33:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-10 16:22:22.941330
• Title: Learning Submodular Sequencing from Samples
• Title（参考訳）: サンプルからのサブモジュールシークエンシングの学習
• Authors: Jing Yuan, Shaojie Tang,
• Abstract要約: 本稿では,いくつかの複合部分モジュラー関数を最適化するために,シーケンス内の項目の選択とランク付けの問題に対処する。 本稿では,各部分モジュラ関数の曲率に依存する近似比を求めるアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.528995186765751
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the problem of sequential submodular maximization: selecting and ranking items in a sequence to optimize some composite submodular function. In contrast to most of the previous works, which assume access to the utility function, we assume that we are given only a set of samples. Each sample includes a random sequence of items and its associated utility. We present an algorithm that, given polynomially many samples drawn from a two-stage uniform distribution, achieves an approximation ratio dependent on the curvature of individual submodular functions. Our results apply in a wide variety of real-world scenarios, such as ranking products in online retail platforms, where complete knowledge of the utility function is often impossible to obtain. Our algorithm gives an empirically useful solution in such contexts, thus proving that limited data can be of great use in sequencing tasks. From a technical perspective, our results extend prior work on ``optimization from samples'' by generalizing from optimizing a set function to a sequence-dependent function.
• Abstract（参考訳）: 本稿では, 逐次部分モジュラー最大化の問題に対処し, 複合部分モジュラー関数を最適化するために, 列内の項目の選択とランク付けを行う。 ユーティリティ関数へのアクセスを前提とする以前の作業のほとんどとは対照的に、我々はサンプルのセットのみを与えられると仮定する。 各サンプルは、アイテムとその関連ユーティリティのランダムなシーケンスを含む。 本稿では,2段階の均一分布から得られる多項式的なサンプルを与えられた場合,各部分モジュラ関数の曲率に依存する近似比が得られるアルゴリズムを提案する。 本研究は,オンライン小売プラットフォーム上での製品ランキングなど,実用機能に関する知識の完全化が不可能な,さまざまな現実シナリオに適用した。 我々のアルゴリズムはこのような文脈で経験的に有用な解を与えるので、限られたデータがタスクのシーケンシングに非常に役立つことが証明できる。 技術的観点から、我々の結果は、セット関数の最適化からシーケンス依存関数への一般化により、「サンプルからの最適化」に関する先行研究を拡張した。

関連論文リスト

• 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)
• Achieving Long-term Fairness in Submodular Maximization through Randomization [16.33001220320682]
  人種や性別などのセンシティブな属性を含む可能性のあるデータアイテムを扱う場合、公平性を意識したアルゴリズムを実装することが重要です。 群フェアネス制約を満たしながら単調部分モジュラ函数を最大化する問題について検討する。
  論文  参考訳（メタデータ） (2023-04-10T16:39:19Z)
• Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
  未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。 この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
  論文  参考訳（メタデータ） (2023-03-17T13:32:33Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。 提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
  論文  参考訳（メタデータ） (2020-12-07T14:58:16Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。 標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。 シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-09-08T06:54:11Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T16:40:44Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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