論文の概要: A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks

• arxiv url: http://arxiv.org/abs/2102.04518v1
• Date: Mon, 8 Feb 2021 20:36:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-10 16:57:16.602101
• Title: A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks
• Title（参考訳）: 拡張のないA*検索:深層Q-Networksによるヒューリスティック関数の学習
• Authors: Forest Agostinelli, Alexander Shmakov, Stephen McAleer, Roy Fox, Pierre Baldi
• Abstract要約: A*検索(A* search)は、ノードが拡張される順序を導く関数を使用する情報検索アルゴリズムである。 DeepAQはDeepCubeAアルゴリズムとディープQ-networksをベースにしたディープ強化学習と検索アルゴリズムである。 次にDeepAQはA*検索の新たな変種であるAQ*検索を使用し、深層Qネットワークを用いて検索を誘導する。
• 参考スコア（独自算出の注目度）: 73.12941276331314
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A* search is an informed search algorithm that uses a heuristic function to guide the order in which nodes are expanded. Since the computation required to expand a node and compute the heuristic values for all of its generated children grows linearly with the size of the action space, A* search can become impractical for problems with large action spaces. This computational burden becomes even more apparent when heuristic functions are learned by general, but computationally expensive, deep neural networks. To address this problem, we introduce DeepCubeAQ, a deep reinforcement learning and search algorithm that builds on the DeepCubeA algorithm and deep Q-networks. DeepCubeAQ learns a heuristic function that, with a single forward pass through a deep neural network, computes the sum of the transition cost and the heuristic value of all of the children of a node without explicitly generating any of the children, eliminating the need for node expansions. DeepCubeAQ then uses a novel variant of A* search, called AQ* search, that uses the deep Q-network to guide search. We use DeepCubeAQ to solve the Rubik's cube when formulated with a large action space that includes 1872 meta-actions and show that this 157-fold increase in the size of the action space incurs less than a 4-fold increase in computation time when performing AQ* search and that AQ* search is orders of magnitude faster than A* search.
• Abstract（参考訳）: A*検索は、ノードが拡大される順序を導くためにヒューリスティック関数を使用する情報検索アルゴリズムです。 ノードを拡大し、生成したすべての子供のヒューリスティック値を計算するのに必要な計算は、アクション空間のサイズとともに線形に成長するので、A*探索は大きなアクション空間の問題に対して実用的ではない。 この計算負荷は、ヒューリスティック関数が一般の計算コストが高いディープニューラルネットワークによって学習されるとさらに顕著になる。 この問題に対処するため,DeepCubeAアルゴリズムと深層Q-networksをベースにしたディープ強化学習検索アルゴリズムであるDeepCubeAQを導入する。 DeepCubeAQは、単一のフォワードがディープニューラルネットワークを通過することで、ノードのすべての子供の移行コストとヒューリスティック値の合計を明示的に生成することなく計算し、ノード拡張を不要とするヒューリスティック関数を学習する。 DeepCubeAQは、ディープQネットワークを使用して検索を導くAQ*検索と呼ばれる、A*検索の新しい変種を使用します。 私たちは、DeepCubeAQを使用して、1872のメタアクションを含む大きなアクションスペースで定式化されるとルービックキューブを解決し、アクションスペースのサイズが157倍に拡大すると、AQ*検索を行う際の計算時間が4倍以下になり、AQ*検索がA*検索よりも桁違いに速くなることを示します。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  大規模言語モデルは、高度なプロンプト技術で顕著な推論能力に優れています。 近年の研究では、LLMがより困難な推論タスクを解くために受動的木探索を行えるように、検索ロジックを定義するために外部プログラムを活用することが提案されている。 我々は,LLMの自律木探索能力という新しい概念を提案し,正しい解を求める探索軌跡を含む応答を自動生成する。
  論文  参考訳（メタデータ） (2023-10-14T14:14:38Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• A Differentiable Loss Function for Learning Heuristics in A* [0.0]
  本稿は、絶対値ではなく相対値に依存するため、A*アルゴリズムの高速化につながるとは限らない、と論じる。 緩和策として,A*探索における過度に拡張された状態の上限となるL*損失を提案する。 ソコバンやモーゼなどの迷路ドメインにおける自動計画のための最先端のディープニューラルネットワークの最適化に使用されるL*損失は、解決された問題の割合、確立された計画の品質を大幅に改善し、拡張された状態の数を約50%削減する。
  論文  参考訳（メタデータ） (2022-09-12T12:43:05Z)
• The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems [25.641418039598587]
  A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。 このような問題の多くに対する正確な近似もNPハードであることを示す。
  論文  参考訳（メタデータ） (2022-09-07T18:02:02Z)
• Learning heuristics for A* [9.701208207491879]
  我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。 我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。 その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
  論文  参考訳（メタデータ） (2022-04-11T10:13:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  スパース符号問題としてニューラルアーキテクチャ探索を定式化する。 実験では、CIFAR-10の2段階法では、検索にわずか0.05GPUしか必要としない。 本手法は,CIFAR-10とImageNetの両方において,評価時間のみのコストで最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2020-10-13T04:34:24Z)

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

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