論文の概要: Learning Admissible Heuristics via Cost Partitioning

• arxiv url: http://arxiv.org/abs/2606.04597v1
• Date: Wed, 03 Jun 2026 08:35:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.633601
• Title: Learning Admissible Heuristics via Cost Partitioning
• Title（参考訳）: コスト分割による許容的ヒューリスティックス学習
• Authors: Hugo Barral, Quentin Cappart, Marie-José Huguet, Sylvie Thiébaux,
• Abstract要約: 本稿では,コストパーティショニングと乗算器予測のラグランジアン二重同値性を利用して,許容可能なコストパーティショニングを推定するフレームワークを提案する。 軸方向の自己アテンションとソフトマックス出力層を備えた深いアーキテクチャは、これらの特徴を、構成による分割制約を満たすコスト重みにマッピングする。
• 参考スコア（独自算出の注目度）: 9.42570143543392
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction. Planning states and patterns are encoded as labelled graphs, and an action-centric variant of the Weisfeiler-Leman algorithm extracts structural feature vectors. A deep architecture with axial self-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility. To our knowledge, this is the first machine-learned heuristic guaranteed to be admissible.
• Abstract（参考訳）: 許容的ヒューリスティックスは最適な計画には不可欠であるが、過大評価のリスクのために学習は難しいままである。 コストパーティショニングは、許容性を維持しながら複数の抽象ヒューリスティックを組み合わせるが、最適パーティショニングをオンラインで計算することは高価である。 本稿では,コストパーティショニングと乗算器予測のラグランジアン二重同値性を利用して,許容可能なコストパーティショニングを推定するフレームワークを提案する。 計画状態とパターンはラベル付きグラフとして符号化され、Weisfeiler-Lemanアルゴリズムのアクション中心の変種は構造的特徴ベクトルを抽出する。 軸方向の自己アテンションとソフトマックス出力層を備えた深いアーキテクチャは、これらの特徴を、構成によって分割制約を満たすコストの重みにマッピングし、許容性を保証する。 実験では、厳密な許容性を維持しながら、最適下分割ベースラインと比較してノード拡張が減少することを示した。 私たちの知る限りでは、これが初めて、機械で学習したヒューリスティックである。

関連論文リスト

• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  未知数の線形平面をデータに適合させることは、機械学習の根本的な課題である。 既存のアプローチはしばしば最適な最適化に苦しむか、幾何的整合性に欠ける。
  論文  参考訳（メタデータ） (2026-05-27T14:02:20Z)
• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models [49.67598869075125]
  自己回帰型言語モデリングにおいて、確率回路(PC)はTransformer-based large language model(LLM)より遅れている 構造化分解可能なPCは, 変圧器分離ランクをvtree整列パーティションに合わせることができるが, この容量は固定されたルーティング構造に整列したパーティションに限られる。 さらに、分解可能なPCは構造化された分解可能なPCよりも厳密に表現可能であることを証明していますが、効果的に最適化することはオープンな課題です。
  論文  参考訳（メタデータ） (2026-05-13T03:22:10Z)
• Model Compression with Exact Budget Constraints via Riemannian Manifolds [39.54576236079211]
  トータルコスト予算の下で各NグループにKオプションの1つを割り当てることは、効率的なAIにおいて繰り返し発生する問題である。 我々は、ソフトマックス緩和の下で、予算制約がロジット空間における滑らかなリーマン多様体を異常に単純な幾何学で定義することを示す新しいアプローチを示す。 これらの特性に基づいて、接射影、二分探索リトラクション、運動量輸送を標準とするリーマン制約最適化(RCO)を提案する。
  論文  参考訳（メタデータ） (2026-05-01T13:30:23Z)
• The Theory and Practice of MAP Inference over Non-Convex Constraints [11.058494098615576]
  安全クリティカルな設定では、確率的MLシステムは代数的制約の下で予測を行う必要がある。 これにより、制約された最大値 (MAP) の予測を効率的にかつ確実に行うことができる。 この抽出可能なフラグメントに対して,スケーラブルなメッセージパッシングアルゴリズムを考案する。 そこで我々は,領域を凸可能な領域に分割する一般的なMAP戦略を考案した。
  論文  参考訳（メタデータ） (2026-02-09T14:05:58Z)
• Latent-Space Contrastive Reinforcement Learning for Stable and Efficient LLM Reasoning [16.244366307890832]
  textbfDeepLatent Reasoning(DLR)を提案する。 このフレームワークは、試行錯誤コストを、高価なトークンレベルのフルシーケンス生成から連続潜在多様体へシフトさせる。 実験により、DLRはより安定した訓練収束を実現し、より長い水平推論チェーンをサポートし、推論能力の持続的な蓄積を促進することが示されている。
  論文  参考訳（メタデータ） (2026-01-24T03:18:22Z)
• READER: Retrieval-Assisted Drafter for Efficient LLM Inference [0.0386965802948046]
  自己回帰言語モデルはトークンシーケンスよりも分解された確率をインスタンス化するが、その厳密なシーケンシャルなデコーディングプロセスは、遅延推論に固有の低いバウンドを課す。 このボトルネックは、大規模生成モデルのスケーラブルなデプロイにおける中心的な障害として現れています。 本稿では,補助的ドラフトモデルのトレーニングを回避した投機的復号化フレームワークREADERを提案する。
  論文  参考訳（メタデータ） (2025-08-12T16:47:48Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  ニューロシンボリックアプローチは一般に確率論的目的のファジィ近似を利用する。 トラクタブル回路において,これを効率的に計算する方法を示す。 我々は,Warcraftにおける最小コストパスの予測,最小コスト完全マッチングの予測,スドクパズルの解法という3つの課題に対して,アプローチを検証した。
  論文  参考訳（メタデータ） (2023-02-28T00:04:22Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)

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

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