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

• arxiv url: http://arxiv.org/abs/2102.04518v2
• Date: Thu, 23 Mar 2023 17:38:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-24 20:02:32.822753
• 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要約: Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。 我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。 Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
• 参考スコア（独自算出の注目度）: 70.0197695666261
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficiently solving problems with large action spaces using A* search has been of importance to the artificial intelligence community for decades. This is because the computation and memory requirements of A* search grow linearly with the size of the action space. This burden becomes even more apparent when A* search uses a heuristic function learned by computationally expensive function approximators, such as deep neural networks. To address this problem, we introduce Q* search, a search algorithm that uses deep Q-networks to guide search in order to take advantage of the fact that the sum of the transition costs and heuristic values of the children of a node can be computed with a single forward pass through a deep Q-network without explicitly generating those children. This significantly reduces computation time and requires only one node to be generated per iteration. We use Q* search to solve the Rubik's cube when formulated with a large action space that includes 1872 meta-actions and find that this 157-fold increase in the size of the action space incurs less than a 4-fold increase in computation time and less than a 3-fold increase in number of nodes generated when performing Q* search. Furthermore, Q* search is up to 129 times faster and generates up to 1288 times fewer nodes than A* search. Finally, although obtaining admissible heuristic functions from deep neural networks is an ongoing area of research, we prove that Q* search is guaranteed to find a shortest path given a heuristic function that neither overestimates the cost of a shortest path nor underestimates the transition cost.
• Abstract（参考訳）: a*検索を用いた大規模行動空間での効率的な問題解決は、人工知能コミュニティにとって何十年も前から重要だった。 これは、A*探索の計算とメモリ要求がアクション空間のサイズとともに線形に増加するためである。 A*探索が深層ニューラルネットワークのような計算コストの高い関数近似器によって学習されたヒューリスティック関数を使用すると、この重荷はさらに明らかになる。 この問題に対処するために,我々は,ノードの子どもの遷移コストとヒューリスティック値の和を,これらの子を明示的に生成することなく単一のフォワードパスで計算できるという事実を生かして,ディープqネットワークを用いた探索アルゴリズムであるq* searchを導入する。 これにより、計算時間を大幅に削減し、イテレーション毎に1ノードだけを生成することができる。 1872年のメタアクションを含む大きなアクション空間を定式化した場合、q*探索を用いてルービックキューブを解き、この157倍のアクション空間の大きさの増大は計算時間を4倍にし、q*探索を行う際に発生するノード数を3倍に増加させる。 さらに、q*検索はa*検索の最大129倍高速であり、a*検索の最大1288倍のノードを生成する。 最後に、深層ニューラルネットワークから許容的ヒューリスティック関数を取得することは、現在進行中の研究分野であるが、最短経路のコストを過大評価せず、遷移コストを過小評価しないヒューリスティック関数により、Q*探索が最短経路を見つけることが保証されていることを証明している。

関連論文リスト

• 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)

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

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