論文の概要: Learning Admissible Heuristics for A*: Theory and Practice

• arxiv url: http://arxiv.org/abs/2509.22626v1
• Date: Fri, 26 Sep 2025 17:51:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.626302
• Title: Learning Admissible Heuristics for A*: Theory and Practice
• Title（参考訳）: A*のための許容的ヒューリスティックスを学ぶ:理論と実践
• Authors: Ehsan Futuhi, Nathan R. Sturtevant,
• Abstract要約: ディープラーニングアプローチは、しばしば許容性を無視し、トレーニングデータ以外の一般化に関して制限された保証を提供する。 本稿では,これら2つの制約に対処する。まず,制約付き最適化問題として学習を行い,学習中に許容度を強制する損失関数であるクロスエントロピー適応性(CEA)を導入する。 ルービックキューブ領域では、圧縮されたパターンデータベース(PDB)のガイダンスよりもはるかに強いほぼ許容値が得られる。
• 参考スコア（独自算出の注目度）: 8.408138419383747
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heuristic functions are central to the performance of search algorithms such as A-star, where admissibility - the property of never overestimating the true shortest-path cost - guarantees solution optimality. Recent deep learning approaches often disregard admissibility and provide limited guarantees on generalization beyond the training data. This paper addresses both of these limitations. First, we pose heuristic learning as a constrained optimization problem and introduce Cross-Entropy Admissibility (CEA), a loss function that enforces admissibility during training. On the Rubik's Cube domain, this method yields near-admissible heuristics with significantly stronger guidance than compressed pattern database (PDB) heuristics. Theoretically, we study the sample complexity of learning heuristics. By leveraging PDB abstractions and the structural properties of graphs such as the Rubik's Cube, we tighten the bound on the number of training samples needed for A-star to generalize. Replacing a general hypothesis class with a ReLU neural network gives bounds that depend primarily on the network's width and depth, rather than on graph size. Using the same network, we also provide the first generalization guarantees for goal-dependent heuristics.
• Abstract（参考訳）: ヒューリスティック関数は、A-starのような検索アルゴリズムのパフォーマンスの中心であり、許容性 – 真の最短パスコストを過大評価しない特性 – は、ソリューションの最適性を保証する。 最近のディープラーニングアプローチは、しばしば許容性を無視し、トレーニングデータ以外の一般化に関して制限された保証を提供する。 本稿はこれらの2つの制限に対処する。 まず,制約付き最適化問題としてヒューリスティック学習を導入し,学習中に許容度を強制する損失関数であるクロスエントロピー適応性(CEA)を導入する。 ルービックキューブ領域では、この方法では圧縮パターンデータベース(PDB)のヒューリスティックよりもはるかに強力なガイダンスで、ほぼ許容可能なヒューリスティックが得られる。 理論的には、学習ヒューリスティックスのサンプル複雑性について検討する。 PDB抽象化とルービックキューブのようなグラフの構造特性を利用することで、A星の一般化に必要なトレーニングサンプルの数に縛られる。 一般的な仮説クラスをReLUニューラルネットワークに置き換えると、グラフのサイズよりもネットワークの幅と深さに依存する境界が与えられる。 同じネットワークを用いて、ゴール依存ヒューリスティックスに対する最初の一般化保証も提供する。

関連論文リスト

• RL for Reasoning by Adaptively Revealing Rationales [36.50924054394857]
  監督された微調整(SFT)は密度の高い地下構造ラベルに依存しており、シーケンスの長さが大きくなるにつれてコストが増大する。 AdaBack(アダプティブ・バックトラック)は,学習中の目標出力の部分的なプレフィックスのみを明らかにする,サンプルごとのカリキュラム学習アルゴリズムである。 部分解に対する適応的なカリキュラムは、そうでなければ難解な問題を確実に解決することを示します。
  論文  参考訳（メタデータ） (2025-06-22T17:46:14Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• Minimum Description Length and Generalization Guarantees for Representation Learning [16.2444595840653]
  本稿では,表現学習アルゴリズムの一般化誤差の上限を導出するフレームワークを提案する。 エンコーダの入力と表現の間の相互情報ではなく、我々の新しい境界は「マルチレター」相対エントロピーを含む。 著者たちの最もよく知る限り、確立された一般化境界は、情報ボトルネック型エンコーダと表現学習のための第一種である。
  論文  参考訳（メタデータ） (2024-02-05T18:12:28Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Learning Non-Vacuous Generalization Bounds from Optimization [8.294831479902658]
  最適化の観点からは、単純だが空でない一般化を示す。 我々は、勾配アルゴリズムによってアクセスされた仮説セットが本質的にフラクタル的であることを利用して、この目標を達成する。 数値解析により,現代のニューラルネットワークにおいて,本手法が有意な一般化を保証することが実証された。
  論文  参考訳（メタデータ） (2022-06-09T08:59:46Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness [33.09831377640498]
  本研究では,1つの決定論的表現に基づく1つのネットワークの不確実性向上手法について検討する。 本稿では,現代のDNNにおける距離認識能力を向上させる簡易な手法として,スペクトル正規化ニューラルガウス過程(SNGP)を提案する。 ビジョンと言語理解のベンチマークスイートでは、SNGPは予測、キャリブレーション、ドメイン外検出において、他の単一モデルアプローチよりも優れている。
  論文  参考訳（メタデータ） (2022-05-01T05:46:13Z)
• Generalization Through The Lens Of Leave-One-Out Error [22.188535244056016]
  本稿では,カーネルシステムにおけるディープニューラルネットワークの一般化能力を推定する方法として,残余誤差が有益であることを示す。 そこで本研究は,カーネルシステムにおけるディープニューラルネットワークの一般化能力を推定する方法として,残余誤差が有益であることを示す。
  論文  参考訳（メタデータ） (2022-03-07T14:56:00Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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