論文の概要: A Differentiable Loss Function for Learning Heuristics in A*
- arxiv url: http://arxiv.org/abs/2209.05206v1
- Date: Mon, 12 Sep 2022 12:43:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-13 12:25:53.173673
- Title: A Differentiable Loss Function for Learning Heuristics in A*
- Title(参考訳): A*におけるヒューリスティックス学習のための微分損失関数
- Authors: Leah Chrestien, Tomas Pevny, Antonin Komenda, Stefan Edelkamp
- Abstract要約: 本稿は、絶対値ではなく相対値に依存するため、A*アルゴリズムの高速化につながるとは限らない、と論じる。
緩和策として,A*探索における過度に拡張された状態の上限となるL*損失を提案する。
ソコバンやモーゼなどの迷路ドメインにおける自動計画のための最先端のディープニューラルネットワークの最適化に使用されるL*損失は、解決された問題の割合、確立された計画の品質を大幅に改善し、拡張された状態の数を約50%削減する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimization of heuristic functions for the A* algorithm, realized by deep
neural networks, is usually done by minimizing square root loss of estimate of
the cost to goal values. This paper argues that this does not necessarily lead
to a faster search of A* algorithm since its execution relies on relative
values instead of absolute ones. As a mitigation, we propose a L* loss, which
upper-bounds the number of excessively expanded states inside the A* search.
The L* loss, when used in the optimization of state-of-the-art deep neural
networks for automated planning in maze domains like Sokoban and maze with
teleports, significantly improves the fraction of solved problems, the quality
of founded plans, and reduces the number of expanded states to approximately
50%
- Abstract(参考訳): ディープニューラルネットワークによって実現されるa*アルゴリズムのヒューリスティック関数の最適化は、通常、目標値に対するコストの推定の平方根損失を最小化する。
本稿は、絶対値ではなく相対値に依存するため、A*アルゴリズムの高速化につながるとは限らない、と論じる。
緩和策として,A*探索における過度に拡張された状態の上限となるL*損失を提案する。
ソコバンやモーゼなどの迷路ドメインにおける自動計画のための最先端のディープニューラルネットワークの最適化に使用されるL*損失は、解決された問題の割合、確立された計画の品質を大幅に改善し、拡張された状態の数を約50%削減する。
関連論文リスト
- Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。
我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。
我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
論文 参考訳(メタデータ) (2024-11-21T17:43:51Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Large-scale Optimization of Partial AUC in a Range of False Positive
Rates [51.12047280149546]
ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。
近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。
提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
論文 参考訳(メタデータ) (2022-03-03T03:46:18Z) - Neural network relief: a pruning algorithm based on neural activity [47.57448823030151]
重要でない接続を非活性化する簡易な重要スコア計量を提案する。
MNIST上でのLeNetアーキテクチャの性能に匹敵する性能を実現する。
このアルゴリズムは、現在のハードウェアとソフトウェアの実装を考えるとき、FLOPを最小化するように設計されていない。
論文 参考訳(メタデータ) (2021-09-22T15:33:49Z) - Revisiting Recursive Least Squares for Training Deep Neural Networks [10.44340837533087]
再帰最小二乗法(RLS)アルゴリズムは、その高速収束のため、かつては小規模ニューラルネットワークのトレーニングに広く用いられていた。
従来のRSSアルゴリズムは、計算複雑性が高く、事前条件が多すぎるため、ディープニューラルネットワーク(DNN)のトレーニングには適さない。
本稿では,フィードフォワードニューラルネットワーク,畳み込みニューラルネットワーク,リカレントニューラルネットワークの3つの新しいRSS最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-07T17:43:51Z) - A* Search Without Expansions: Learning Heuristic Functions with Deep
Q-Networks [70.0197695666261]
Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。
我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。
Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
論文 参考訳(メタデータ) (2021-02-08T20:36:41Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳(メタデータ) (2020-12-04T15:46:30Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2020-05-05T18:08:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。