論文の概要: Left Heavy Tails and the Effectiveness of the Policy and Value Networks
in DNN-based best-first search for Sokoban Planning
- arxiv url: http://arxiv.org/abs/2206.14298v1
- Date: Tue, 28 Jun 2022 21:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-30 20:32:19.955652
- Title: Left Heavy Tails and the Effectiveness of the Policy and Value Networks
in DNN-based best-first search for Sokoban Planning
- Title（参考訳）: 左重機とDNNによるソコバン計画ベストファースト探索における政策・価値ネットワークの有効性
- Authors: Dieqiao Feng, Carla Gomes, Bart Selman
- Abstract要約: 本研究では,ソコバン上でのベストファースト検索のポリシーと価値ネットワークの相互作用について検討し,検索の指針としての価値ネットワークが驚くほど有効であることを示す。
はじめに,両立した重尾の存在を示し,これらの尾の外観を実証的に説明できる抽象木モデルを提案する。
- 参考スコア（独自算出の注目度）: 7.9603223299524535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the success of practical solvers in various NP-complete domains such
as SAT and CSP as well as using deep reinforcement learning to tackle
two-player games such as Go, certain classes of PSPACE-hard planning problems
have remained out of reach. Even carefully designed domain-specialized solvers
can fail quickly due to the exponential search space on hard instances. Recent
works that combine traditional search methods, such as best-first search and
Monte Carlo tree search, with Deep Neural Networks' (DNN) heuristics have shown
promising progress and can solve a significant number of hard planning
instances beyond specialized solvers. To better understand why these approaches
work, we studied the interplay of the policy and value networks of DNN-based
best-first search on Sokoban and show the surprising effectiveness of the
policy network, further enhanced by the value network, as a guiding heuristic
for the search. To further understand the phenomena, we studied the cost
distribution of the search algorithms and found that Sokoban instances can have
heavy-tailed runtime distributions, with tails both on the left and right-hand
sides. In particular, for the first time, we show the existence of \textit{left
heavy tails} and propose an abstract tree model that can empirically explain
the appearance of these tails. The experiments show the critical role of the
policy network as a powerful heuristic guiding the search, which can lead to
left heavy tails with polynomial scaling by avoiding exploring exponentially
sized subtrees. Our results also demonstrate the importance of random restarts,
as are widely used in traditional combinatorial solvers, for DNN-based search
methods to avoid left and right heavy tails.
- Abstract（参考訳）: SATやCSPなどのNP完全ドメインでの実践的な問題解決の成功や、Goのような2プレイヤーゲームへの深い強化学習にもかかわらず、PSPACEのハードプランニング問題の一部クラスは未解決のままである。
さらに注意深い設計のドメイン特化解法は、ハードインスタンス上の指数探索空間のために迅速に失敗する。
近年,最優先探索やモンテカルロ木探索,Deep Neural Networks (DNN) のヒューリスティックスといった従来の探索手法と組み合わせた研究は,有望な進歩を示し,特殊な解法を超越した多くのハードプランニングインスタンスを解くことができる。
これらの手法がなぜ機能するのかをより深く理解するため、我々は、DNNによるソコバン上でのベストファースト検索のポリシーと価値ネットワークの相互作用を研究し、さらにバリューネットワークによって強化されたポリシーネットワークの驚くべき効果を示す。
この現象をより深く理解するために,探索アルゴリズムのコスト分布を調べたところ,ソコバンインスタンスは左と右の両方に尾を持つ重尾のランタイム分布を持つことができた。
特に, 初めて \textit{left heavy tails} の存在を示し, これらの尾の出現を経験的に説明できる抽象木モデルを提案する。
これらの実験は, 指数関数的にサイズのサブツリーを探索することを避けることで, 多項式スケーリングによる左重みの増大につながるような, 探索を導く強力なヒューリスティックとして, 政策ネットワークが重要な役割を担っていることを示す。
また,DNNをベースとした探索手法において,従来の組合せ解法で広く用いられているように,ランダム再起動の重要性も示している。
関連論文リスト
- Unleash Graph Neural Networks from Heavy Tuning [33.948899558876604]
グラフニューラルネットワーク(GNN)は、グラフ型データ用に設計されたディープラーニングアーキテクチャである。
本稿では,光チューニングされた粗い探索中に保存されたチェックポイントから学習することで,高性能なGNNを直接生成するグラフ条件付き潜時拡散フレームワーク(GNN-Diff)を提案する。
論文 参考訳（メタデータ） (2024-05-21T06:23:47Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳（メタデータ） (2022-11-26T00:01:01Z) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳（メタデータ） (2022-05-31T10:38:04Z) - Training Quantized Deep Neural Networks via Cooperative Coevolution [27.967480639403796]
本稿では,ディープニューラルネットワーク(DNN)の定量化手法を提案する。
協調的共進化の枠組みでは,分布推定アルゴリズムを用いて低ビット重みの探索を行う。
実験の結果,Cifar-10データセット上で4ビットのResNet-20を,精度を犠牲にすることなくトレーニングできることがわかった。
論文 参考訳（メタデータ） (2021-12-23T09:13:13Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Community detection using low-dimensional network embedding algorithms [1.052782170493037]
我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。
固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
論文 参考訳（メタデータ） (2021-11-04T14:57:43Z) - Combined Depth Space based Architecture Search For Person
Re-identification [70.86236888223569]
個人再識別(ReID)のための軽量で適切なネットワークの設計を目指しています。
本研究では,CDNetと呼ばれる効率的なネットワークアーキテクチャの探索に基づく,複合深さ空間(Componed Depth Space, CDS)と呼ばれる新しい検索空間を提案する。
そこで我々はTop-k Sample Search戦略という低コストの検索戦略を提案し、検索空間をフル活用し、局所的な最適結果のトラップを避ける。
論文 参考訳（メタデータ） (2021-04-09T02:40:01Z) - CATCH: Context-based Meta Reinforcement Learning for Transferrable
Architecture Search [102.67142711824748]
CATCHは、転送可能なarChitecture searcHのための、Context-bAsed meTa強化学習アルゴリズムである。
メタラーニングとRLの組み合わせにより、CATCHは検索空間に依存しないまま、新しいタスクに効率的に適応できる。
また、ImageNet、COCO、Cityscapesの競合ネットワークとしてクロスドメインアーキテクチャサーチを扱うこともできる。
論文 参考訳（メタデータ） (2020-07-18T09:35:53Z) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳（メタデータ） (2020-06-28T23:09:27Z) - Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
グラフ表現学習は、大規模に高品質な候補探索をサポートすることに多くの注目を集めている。
ユーザ・イテム相互作用ネットワークにおけるオブジェクトの埋め込みベクトルの学習の有効性にもかかわらず、連続的な埋め込み空間におけるユーザの好みを推測する計算コストは膨大である。
連続的かつ離散的なコードとを協調的に学習するための,単純かつ効果的な離散表現学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-04T06:59:56Z) - Variational Depth Search in ResNets [2.6763498831034043]
ワンショットのニューラルアーキテクチャサーチにより、ウェイトとネットワークアーキテクチャの合同学習が可能になり、計算コストが削減される。
探索空間を残差ネットワークの深さに制限し、解析的に抽出可能な変分目的を定式化し、1ショットで近似された奥行きの奥行きの偏りを許容する。
MNIST, Fashion-MNIST, SVHNデータセットのネットワーク深度を手動で探索する手法の比較を行った。
論文 参考訳（メタデータ） (2020-02-06T16:00:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。