論文の概要: Online Dynamic Programming
- arxiv url: http://arxiv.org/abs/1706.00834v4
- Date: Tue, 08 Jul 2025 20:11:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-13 16:07:24.154222
- Title: Online Dynamic Programming
- Title（参考訳）: オンライン動的プログラミング
- Authors: Holakou Rahmanian, Manfred K. Warmuth, S. V. N. Vishwanathan,
- Abstract要約: 例えば、バイナリ検索ツリーのオンライン学習、Matrix-Chain乗法、$k$-sets、Knapsacks、Rod Cuttings、重み付きインターバルスケジューリングなどがある。
本稿では,各問題に対する動的プログラミングアルゴリズムが,基礎となるマルチDAGにおけるマルチパス学習のオンラインアルゴリズムにつながることを示す。
- 参考スコア（独自算出の注目度）: 9.279833574270784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a general method for combinatorial online learning problems whose offline optimization problem can be solved efficiently via a dynamic programming algorithm defined by an arbitrary min-sum recurrence. Examples include online learning of Binary Search Trees, Matrix-Chain Multiplications, $k$-sets, Knapsacks, Rod Cuttings, and Weighted Interval Schedulings. For each of these problems we use the underlying graph of subproblems (called a multi-DAG) for defining a representation of the solutions of the dynamic programming problem by encoding them as a generalized version of paths (called multipaths). These multipaths encode each solution as a series of successive decisions or components over which the loss is linear. We then show that the dynamic programming algorithm for each problem leads to online algorithms for learning multipaths in the underlying multi-DAG. The algorithms maintain a distribution over the multipaths in a concise form as their hypothesis. More specifically we generalize the existing Expanded Hedge and Component Hedge algorithms for the online shortest path problem to learning multipaths. Additionally, we introduce a new and faster prediction technique for Component Hedge which in our case directly samples from a distribution over multipaths, bypassing the need to decompose the distribution over multipaths into a mixture with small support.
- Abstract（参考訳）: 本稿では、任意のmin-sum繰り返しによって定義される動的プログラミングアルゴリズムを用いて、オフライン最適化問題を効率的に解くことができる組合せオンライン学習問題の一般化手法を提案する。
例えば、バイナリ検索ツリーのオンライン学習、Matrix-Chain Multiplications、$k$-sets、Knapsacks、Rod Cuttings、Weighted Interval Schedulingsなどがある。
これらの問題に対して、我々は、動的プログラミング問題の解の表現を一般化されたパス(マルチパスと呼ばれる)として符号化することで定義するために、サブプロブレムのグラフ(マルチDAGと呼ばれる)を使用する。
これらのマルチパスは、各ソリューションを、損失が線形である連続した決定またはコンポーネントの集合としてエンコードする。
次に、各問題に対する動的プログラミングアルゴリズムは、基礎となるマルチDAGでマルチパスを学習するためのオンラインアルゴリズムにつながることを示す。
アルゴリズムは、その仮説として簡潔な形式でマルチパス上の分布を維持する。
具体的には,オンライン最短経路問題に対して,既存の拡張HedgeアルゴリズムとComponent Hedgeアルゴリズムを一般化する。
さらに我々は,複数パス上の分布から直接サンプルを採取し,複数パス上の分布を小さなサポートの混合に分解する必要性を回避し,コンポーネント・ヘッジの新しい高速な予測手法を導入する。
関連論文リスト
- Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。
我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
論文 参考訳（メタデータ） (2024-05-08T09:25:39Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳（メタデータ） (2021-10-08T07:22:45Z) - Improved Acyclicity Reasoning for Bayesian Network Structure Learning
with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。
本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。
最適ではないにもかかわらず、性能は桁違いに向上することを示す。
結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文 参考訳（メタデータ） (2021-06-23T09:46:11Z) - Multi-layered Network Exploration via Random Walks: From Offline
Optimization to Online Learning [33.450042829375086]
マルチレイヤネットワーク探索(MuLaNE)問題は、多くのアプリケーションから抽象化された重要な問題である。
MuLaNEには複数のネットワーク層があり、各ノードは重みを持ち、各レイヤはランダムウォークによって探索される。
オフライン最適化からオンライン学習まで,この問題を体系的に研究する。
論文 参考訳（メタデータ） (2021-06-09T13:35:39Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳（メタデータ） (2021-04-04T17:12:24Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳（メタデータ） (2020-10-29T06:32:53Z) - Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces [20.101005623256626]
複数のソリューションの存在に消極的であることは、トレーニング能力を著しく損なう可能性がある、と私たちは主張する。
本稿では、既存の予測ネットワークをRL問題に適用し、解乗法を扱う汎用学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-08-27T08:37:01Z) - Physarum Powered Differentiable Linear Programming Layers and
Applications [48.77235931652611]
一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。
本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
論文 参考訳（メタデータ） (2020-04-30T01:50:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。