論文の概要: Learning General Policies for Classical Planning Domains: Getting Beyond C$_2$
- arxiv url: http://arxiv.org/abs/2403.11734v1
- Date: Mon, 18 Mar 2024 12:42:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 20:39:33.656164
- Title: Learning General Policies for Classical Planning Domains: Getting Beyond C$_2$
- Title（参考訳）: 古典的なプランニングドメインのための一般的なポリシーを学ぶ: C$_2$を超える
- Authors: Simon Ståhlberg, Blai Bonet, Hector Geffner,
- Abstract要約: 計画領域全体にわたる一般的なポリシーを学ぶためのGNNベースのアプローチは、$C$の表現力によって制限される。
関係GNNのパラメータ化版を導入し、$t$が無限大であるとき、R-GNN[$t$]は埋め込みのための2次空間のみを用いて3ドルGNNを近似する。
t=1 や $t=2 のような $t$ の低い値の場合、R-GNN[$t$] はより少ないメッセージを交換することでより弱い近似を達成する。
- 参考スコア（独自算出の注目度）: 15.574717738100727
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: GNN-based approaches for learning general policies across planning domains are limited by the expressive power of $C_2$, namely; first-order logic with two variables and counting. This limitation can be overcomed by transitioning to $k$-GNNs, for $k=3$, wherein object embeddings are substituted with triplet embeddings. Yet, while $3$-GNNs have the expressive power of $C_3$, unlike $1$- and $2$-GNNs that are confined to $C_2$, they require quartic time for message exchange and cubic space for embeddings, rendering them impractical. In this work, we introduce a parameterized version of relational GNNs. When $t$ is infinity, R-GNN[$t$] approximates $3$-GNNs using only quadratic space for embeddings. For lower values of $t$, such as $t=1$ and $t=2$, R-GNN[$t$] achieves a weaker approximation by exchanging fewer messages, yet interestingly, often yield the $C_3$ features required in several planning domains. Furthermore, the new R-GNN[$t$] architecture is the original R-GNN architecture with a suitable transformation applied to the input states only. Experimental results illustrate the clear performance gains of R-GNN[$1$] and R-GNN[$2$] over plain R-GNNs, and also over edge transformers that also approximate $3$-GNNs.
- Abstract（参考訳）: 計画領域全体にわたる一般的なポリシーを学習するためのGNNベースのアプローチは、C_2$の表現力、すなわち2つの変数を持つ一階述語論理とカウントによって制限される。
この制限は、$k$-GNNs、$k=3$に移行することで克服できる。
しかし、$C_3$の表現力を持つGNNは、$C_2$に制限された$C_3$と$2$-GNNとは違い、メッセージ交換の質的時間と埋め込みのためのキュービックスペースは非現実的だ。
本稿では,リレーショナルGNNのパラメータ化バージョンを紹介する。
t$が無限大であるとき、R-GNN[$t$]は埋め込みのための二次空間のみを用いて3ドルGNNを近似する。
t=1$や$t=2$のような$t$の低い値の場合、R-GNN[$t$]は、より少ないメッセージを交換することで、より弱い近似を実現します。
さらに、新しいR-GNN[$t$]アーキテクチャは、入力状態のみに適切な変換を施した元のR-GNNアーキテクチャである。
実験結果から、R-GNN[$1$]とR-GNN[$2$]は、通常のR-GNNよりも明らかな性能向上を示し、また、300ドルに近いエッジトランスも示している。
関連論文リスト
- Efficient k-Nearest-Neighbor Machine Translation with Dynamic Retrieval [49.825549809652436]
$k$NN-MTはドメイン固有の翻訳知識を保持するために外部データストアを構築する。
適応検索(k$NN-MT-AR)は、$lambda$を動的に推定し、$lambda$が固定しきい値以下であれば$k$NN検索をスキップする。
本稿では,バニラ$k$NN-MTを大幅に拡張した動的検索(k$NN-MT-DR)を提案する。
論文 参考訳（メタデータ） (2024-06-10T07:36:55Z) - Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳（メタデータ） (2024-05-29T14:28:08Z) - Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational
and Temporal Graphs [8.095679736030146]
2つの変数と数量化器を持つ一階述語論理の断片である$mathcalFOC$NNについて検討する。
本稿では,線形時間で実行可能な,前処理ステップに似た単純なグラフ変換手法を提案する。
我々の結果は,グラフ変換によるR$2$-GNNが,合成および実世界のデータセットのベースライン手法よりも優れていることを一貫して示している。
論文 参考訳（メタデータ） (2023-11-03T00:33:24Z) - On the Computational Complexity and Formal Hierarchy of Second Order
Recurrent Neural Networks [59.85314067235965]
2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN)
有界時間でチューリング完備な RNN のクラスが存在することを証明している。
また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
論文 参考訳（メタデータ） (2023-09-26T06:06:47Z) - Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle
Counting Power [27.929167547127207]
グラフニューラルネットワーク(GNN)の特定のグラフサブ構造、特にサイクルをカウントする能力は重要である。
本稿では,GNNの新しいクラスとして$d$-Distance-Restricted FWL(2) GNNを提案する。
我々のモデルは今までで最も効率的なGNNモデルであり、最大6サイクルまで数えることができる。
論文 参考訳（メタデータ） (2023-09-10T06:13:29Z) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳（メタデータ） (2023-06-05T21:35:32Z) - Densely Connected $G$-invariant Deep Neural Networks with Signed
Permutation Representations [6.200483285433661]
有限群$G$,$G$-不変ディープニューラルネットワーク(G$-DNN)アーキテクチャをReLUアクティベーション付きで導入・検討する。
G$-DNNのプリアクティベーションは、Emphsigned permutation representations (signed perm-reps) of $G$で変換できる。
文献からReLUのアクティベーション関数にアクセスできるものよりも、より許容可能な$G$-DNNアーキテクチャが存在することを示す。
論文 参考訳（メタデータ） (2023-03-08T14:35:03Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳（メタデータ） (2021-06-12T07:43:51Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳（メタデータ） (2020-10-15T04:42:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。