論文の概要: Learning General Optimal Policies with Graph Neural Networks: Expressive
Power, Transparency, and Limits
- arxiv url: http://arxiv.org/abs/2109.10129v1
- Date: Tue, 21 Sep 2021 12:22:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-22 18:52:36.423898
- Title: Learning General Optimal Policies with Graph Neural Networks: Expressive
Power, Transparency, and Limits
- Title（参考訳）: グラフニューラルネットワークによる一般最適政策の学習:表現力,透明性,限界
- Authors: Simon St{\aa}hlberg, Blai Bonet, Hector Geffner
- Abstract要約: 我々は、多数のサンプル状態の最適値関数$V*(s)$を近似するために、教師付き方法で単純なGNNを訓練する。
一般的な最適値関数が$C$特徴で定義できるが、より表現力のある$C_3$特徴を必要とする領域では定義できない領域では、一般的な最適ポリシーが得られている。
- 参考スコア（独自算出の注目度）: 18.718037284357834
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It has been recently shown that general policies for many classical planning
domains can be expressed and learned in terms of a pool of features defined
from the domain predicates using a description logic grammar. At the same time,
most description logics correspond to a fragment of $k$-variable counting logic
($C_k$) for $k=2$, that has been shown to provide a tight characterization of
the expressive power of graph neural networks. In this work, we make use of
these results to understand the power and limits of using graph neural networks
(GNNs) for learning optimal general policies over a number of tractable
planning domains where such policies are known to exist. For this, we train a
simple GNN in a supervised manner to approximate the optimal value function
$V^{*}(s)$ of a number of sample states $s$. As predicted by the theory, it is
observed that general optimal policies are obtained in domains where general
optimal value functions can be defined with $C_2$ features but not in those
requiring more expressive $C_3$ features. In addition, it is observed that the
features learned are in close correspondence with the features needed to
express $V^{*}$ in closed form. The theory and the analysis of the domains let
us understand the features that are actually learned as well as those that
cannot be learned in this way, and let us move in a principled manner from a
combinatorial optimization approach to learning general policies to a
potentially, more robust and scalable approach based on deep learning.
- Abstract（参考訳）: 近年、多くの古典的な計画領域の一般的なポリシーは、記述論理文法を用いて、ドメイン述語から定義された特徴のプールを用いて表現し、学習できることが示されている。
同時に、ほとんどの記述論理は、グラフニューラルネットワークの表現力の厳密な特性を示すことが示されている、$k$-variable counting logic (c_k$) の断片に$k=2$に対応する。
本研究では、これらの結果を用いて、グラフニューラルネットワーク(GNN)を用いて、そのようなポリシーが存在することが知られている複数のトラクタブルプランニングドメイン上で最適な汎用ポリシーを学習する能力と限界を理解する。
このため、多数のサンプル状態の最適値関数 $V^{*}(s)$ を近似するために、教師付き方法で単純なGNNを訓練する。
この理論によって予測されるように、一般的な最適値関数が$C_2$特徴で定義できる領域では、より表現力のある$C_3$特徴を必要とする領域では、一般的な最適ポリシーが得られない。
さらに、学習した特徴が閉じた形で$v^{*}$を表現するのに必要な特徴と密接に対応していることが観察される。
ドメインの理論と分析により、実際に学習される機能と、この方法では学べない機能を理解することができ、組合せ最適化アプローチから一般的なポリシーを学ぶための原則的な方法から、ディープラーニングに基づいた潜在的で堅牢でスケーラブルなアプローチに移行することができます。
関連論文リスト
- How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。
GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。
この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
論文 参考訳（メタデータ） (2023-10-08T10:19:56Z) - Optimistic Natural Policy Gradient: a Simple Efficient Policy
Optimization Framework for Online RL [23.957148537567146]
本稿では,オンラインRLのための最適化NPGという,シンプルな効率的なポリシー最適化フレームワークを提案する。
$d$次元線形 MDP の場合、Optimistic NPG は計算効率が良く、$tildeO(d2/varepsilon3)$サンプル内で $varepsilon$-Optimal Policy を学ぶ。
論文 参考訳（メタデータ） (2023-05-18T15:19:26Z) - From Relational Pooling to Subgraph GNNs: A Universal Framework for More
Expressive Graph Neural Networks [8.121462458089141]
メッセージパッシングニューラルネットワークの表現力を向上させるために、ノードにラベルを割り当てる方法を示す。
実験により,本手法は普遍的に互換性があり,任意のベースGNNモデルの表現性を向上させることができることを示した。
私たちの$k,l$-GNNは、多くの合成および実世界のデータセットで優れたパフォーマンスを実現しています。
論文 参考訳（メタデータ） (2023-05-08T18:00:50Z) - Learning Generalized Policies Without Supervision Using GNNs [20.322992960599255]
グラフニューラルネットワークを用いた古典的計画領域の一般政策学習の問題点を考察する。
我々は,単純で汎用的なGNNアーキテクチャを用いて,鮮明な実験結果を得ることを目的としている。
我々は、GNNの表現力と一階述語論理の$C_2$フラグメントの間に確立された関係を利用する。
論文 参考訳（メタデータ） (2022-05-12T10:28:46Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Improving Robustness and Generality of NLP Models Using Disentangled
Representations [62.08794500431367]
スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。
本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。
提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
論文 参考訳（メタデータ） (2020-09-21T02:48:46Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。
提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-03-30T15:37:50Z) - Complete Dictionary Learning via $\ell_p$-norm Maximization [10.82081111170268]
完全な辞書学習問題に対する $ell_p$-norm (p>2,p in mathbbN$) アプローチの族について検討する。
これらの定式化のグローバルな最大化器は、ガウスノイズが存在する場合でも、高い確率で真の辞書に非常に近いことを示す。
実験により、$ell_p$ベースのアプローチは、従来のアプローチよりも高い計算効率とロバスト性を享受できることが示される。
論文 参考訳（メタデータ） (2020-02-24T02:33:01Z) - Estimating Q(s,s') with Deep Deterministic Dynamics Gradients [25.200259376015744]
ここでは、値関数の新たな形式である$Q(s, s')$を紹介します。
最適ポリシを導出するために,この値を最大化する次世代予測を学習するフォワードダイナミクスモデルを開発した。
論文 参考訳（メタデータ） (2020-02-21T19:05:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。