論文の概要: Deep imagination is a close to optimal policy for planning in large
decision trees under limited resources
- arxiv url: http://arxiv.org/abs/2104.06339v1
- Date: Tue, 13 Apr 2021 16:31:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-14 17:04:19.020488
- Title: Deep imagination is a close to optimal policy for planning in large
decision trees under limited resources
- Title(参考訳): 資源制限下の大規模意思決定木計画における深い想像力は最適政策に近い
- Authors: Ruben Moreno-Bote and Chiara Mastrogiuseppe
- Abstract要約: 計画エージェントは、その有限探索能力を最適に割り当てるために、幅(ツリーの各レベルで多くのアクションを探索)と深さ(ツリー内の多くのレベルを探索)のバランスをとる必要がある。
一般的に、最適な政策は、深いレベルに到達できるように、レベル毎にサンプルを割り当てることである。
低い環境と低い容量では、深くサンプリングしないコストで広く枝をサンプリングするのが最善である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many decisions involve choosing an uncertain course of actions in deep and
wide decision trees, as when we plan to visit an exotic country for vacation.
In these cases, exhaustive search for the best sequence of actions is not
tractable due to the large number of possibilities and limited time or
computational resources available to make the decision. Therefore, planning
agents need to balance breadth (exploring many actions at each level of the
tree) and depth (exploring many levels in the tree) to allocate optimally their
finite search capacity. We provide efficient analytical solutions and numerical
analysis to the problem of allocating finite sampling capacity in one shot to
large decision trees. We find that in general the optimal policy is to allocate
few samples per level so that deep levels can be reached, thus favoring depth
over breadth search. In contrast, in poor environments and at low capacity, it
is best to broadly sample branches at the cost of not sampling deeply, although
this policy is marginally better than deep allocations. Our results provide a
theoretical foundation for the optimality of deep imagination for planning and
show that it is a generally valid heuristic that could have evolved from the
finite constraints of cognitive systems.
- Abstract(参考訳): 多くの決定は、休暇のためにエキゾチックな国を訪れる計画のように、深い、広い決定木で不確実な行動を選択することを含む。
この場合、最善の一連のアクションの徹底的な探索は、多くの可能性と決定に利用可能な限られた時間や計算資源のため、扱いが難しい。
したがって、計画エージェントは、有限探索能力を最適に割り当てるために、幅(ツリーの各レベルでの多くのアクションを探索する)と深さ(ツリー内の多くのレベルを探索する)のバランスをとる必要がある。
本研究では, 有限サンプリング容量を最大決定木に割り当てる問題に対して, 効率的な解析解と数値解析を提供する。
概して最適な政策は, 深度に到達できるように, サンプルの割り当てを最小限に抑えることであり, 広帯域探索よりも深度を優先することにある。
対照的に、貧弱な環境や低容量の環境では、深くサンプリングしないコストで枝を広範囲にサンプリングすることが最善であるが、この方針は深い割り当てよりも極端に優れている。
以上より,計画計画における深い想像力の最適性に関する理論的基礎を提供し,認知システムの有限制約から進化した,一般に有効なヒューリスティックであることを示す。
関連論文リスト
- Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。
我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。
ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
論文 参考訳(メタデータ) (2024-02-29T15:36:01Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳(メタデータ) (2023-10-03T04:40:38Z) - Optimal Decision Tree Policies for Markov Decision Processes [7.995360025953931]
マルコフ決定過程(MPD)におけるサイズ制限決定木の最適化について検討する。
これは、模倣学習の固有の欠点、すなわち、複雑なポリシーが、サイズ制限木を使って表現できないことによるものである。
一般的に、機械学習モデルの性能と解釈可能性の間にはトレードオフがあるが、OMDTは3の深さに制限され、しばしば最適限に近い性能を示す。
論文 参考訳(メタデータ) (2023-01-30T18:51:02Z) - Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees
with Continuous Features [5.663538370244174]
本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。
提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
論文 参考訳(メタデータ) (2022-06-23T17:19:29Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Growing Deep Forests Efficiently with Soft Routing and Learned
Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。
我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。
MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文 参考訳(メタデータ) (2020-12-29T18:05:05Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳(メタデータ) (2020-08-17T16:56:06Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳(メタデータ) (2020-06-15T19:00:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。