論文の概要: Efficient Algorithms for Global Inference in Internet Marketplaces

• arxiv url: http://arxiv.org/abs/2103.05277v1
• Date: Tue, 9 Mar 2021 08:00:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-11 06:37:30.468248
• Title: Efficient Algorithms for Global Inference in Internet Marketplaces
• Title（参考訳）: インターネットマーケットプレイスにおけるグローバル推論の効率的なアルゴリズム
• Authors: Rohan Ramanath, Sathiya Keerthi, Yao Pan, Konstantin Salomatin, Kinjal Basu
• Abstract要約: インターネット市場における供給需要のマッチングは、世界的な推論問題です。 近年まで、LP定式化によるWebスケールデータにおけるそのような問題の解決は難しかった。 最近の研究は、ポリトープの制約が単純であるような問題を解くための双対分解に基づくアプローチを開発した。 この研究では、これらの単純なポリトープを超えて、より複雑な構造化されたポリトープ制約を必要とする現実世界のインターネットマーケットプレイスを示す必要性を動機付けます。
• 参考スコア（独自算出の注目度）: 6.2122699483618
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matching demand to supply in internet marketplaces (e-commerce, ride-sharing, food delivery, professional services, advertising) is a global inference problem that can be formulated as a Linear Program (LP) with (millions of) coupling constraints and (up to a billion) non-coupling polytope constraints. Until recently, solving such problems on web-scale data with an LP formulation was intractable. Recent work (Basu et al., 2020) developed a dual decomposition-based approach to solve such problems when the polytope constraints are simple. In this work, we motivate the need to go beyond these simple polytopes and show real-world internet marketplaces that require more complex structured polytope constraints. We expand on the recent literature with novel algorithms that are more broadly applicable to global inference problems. We derive an efficient incremental algorithm using a theoretical insight on the nature of solutions on the polytopes to project onto any arbitrary polytope, that shows massive improvements in performance. Using better optimization routines along with an adaptive algorithm to control the smoothness of the objective, improves the speed of the solution even further. We showcase the efficacy of our approach via experimental results on web-scale marketplace data.
• Abstract（参考訳）: インターネット市場(eコマース、ライドシェアリング、フードデリバリー、プロフェッショナルサービス、広告)における需要と供給のマッチングは、(数百万の)結合制約と(最大10億の)非結合ポリトープ制約を持つリニアプログラム(lp)として定式化できるグローバルな推論問題である。 近年まで、LP定式化によるWebスケールデータにおけるそのような問題の解決は難しかった。 最近の研究(basu et al., 2020)は、ポリトープの制約が単純である場合にそのような問題を解決するために二重分解に基づくアプローチを開発した。 この研究では、これらの単純なポリトープを超えて、より複雑な構造化されたポリトープ制約を必要とする現実世界のインターネットマーケットプレイスを示す必要性を動機付けます。 我々は、グローバルな推論問題に広く適用可能な新しいアルゴリズムにより、近年の文献を拡大する。 任意のポリトープに投影するポリトープ上の解の性質に関する理論的知見を用いて,効率的なインクリメンタルアルゴリズムを導出し,性能の大幅な向上を示す。 より優れた最適化ルーチンと適応アルゴリズムを使用して、目的の滑らかさを制御し、ソリューションの速度をさらに向上させます。 Webスケールマーケットプレイスデータを用いた実験結果から,本手法の有効性について紹介する。

関連論文リスト

• Efficient Imitation Learning with Conservative World Models [54.52140201148341]
  報酬機能のない専門家によるデモンストレーションから政策学習の課題に取り組む。 純粋な強化学習ではなく、微調整問題として模倣学習を再構成する。
  論文  参考訳（メタデータ） (2024-05-21T20:53:18Z)
• An Improved Artificial Fish Swarm Algorithm for Solving the Problem of Investigation Path Planning [8.725702964289479]
  多集団差分進化(DE-CAFSA)に基づくカオス人工魚群アルゴリズムを提案する。 適応的な視野とステップサイズ調整を導入し、ランダムな動作を2オプト操作に置き換え、カオス理論と準最適解を導入する。 実験結果から、DECAFSAは、異なる大きさの様々な公開データセット上で、他のアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-10-20T09:35:51Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  本稿では,ネットワークにおけるパラメータキャンセル最適化の問題点について考察する。 探索と学習のために実世界でアルゴリズムをデプロイすることは、探索せずにデータによって達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-12T18:36:36Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。 Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
  論文  参考訳（メタデータ） (2022-11-15T03:46:41Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Computation Resource Allocation Solution in Recommender Systems [19.456109814747048]
  限られた計算資源と応答時間でビジネス目標を最大化する計算資源割当ソリューション(CRAS)を提案します。 本手法の有効性はtaobao.comの実データに基づく広範囲な実験により検証された。
  論文  参考訳（メタデータ） (2021-03-03T08:41:43Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。 本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。 このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
  論文  参考訳（メタデータ） (2020-02-20T17:07:08Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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