論文の概要: A Structural Complexity Analysis of Hierarchical Task Network Planning

• arxiv url: http://arxiv.org/abs/2401.14174v2
• Date: Wed, 22 Jan 2025 12:41:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 13:28:52.602796
• Title: A Structural Complexity Analysis of Hierarchical Task Network Planning
• Title（参考訳）: 階層型タスクネットワーク計画における構造的複雑度解析
• Authors: Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger,
• Abstract要約: 階層型タスクネットワーク計画の文脈における3つの古典的問題の複雑性理論解析を行う。 プリミティブネットワークの自然クラスにおける3つの問題に対する新しいアルゴリズムと対応する下位境界を求める。 また,プリミティブ・タスク・ネットワークから一般タスク・ネットワークへの解答時間を持ち上げるためのアルゴリズム的メタ理論も取得し,その前提条件が厳密であることを証明した。
• 参考スコア（独自算出の注目度）: 14.845310803203724
• License:
• Abstract: We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems.
• Abstract（参考訳）: 階層型タスクネットワーク計画(英語版)の文脈における3つの古典的問題の複雑性理論解析を行い、与えられた計画の検証、実行可能な計画が存在するかどうか、与えられた状態に到達できるかどうかを検証した。 我々の焦点は、トラクタビリティをもたらす構造的特性の同定である。 プリミティブネットワークの自然なクラスにおける3つの問題に対する新しい多項式アルゴリズムと対応する下界を求める。 また,プリミティブ・タスク・ネットワークから一般タスク・ネットワークへの多項式時間可解性を持ち上げるためのアルゴリズム的メタ理論も取得し,その前提条件が厳密であることを証明した。 最後に、3つの問題のパラメータ化複雑性を分析する。

関連論文リスト

• Exploring the loss landscape of regularized neural networks via convex duality [42.48510370193192]
  本稿では,正規化ニューラルネットワークのロスランドスケープのいくつかの側面について論じる。 まず、その双対を用いて凸問題の解集合を特徴づけ、さらに全ての定常点を特徴づける。 ソリューションセットの特徴付けと接続結果は、異なるアーキテクチャに拡張可能であることを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:41:38Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• A Structural Complexity Analysis of Synchronous Dynamical Systems [33.788917274180484]
  同期力学系における3つの問題について検討する。 これら3つの問題は、古典的な意味では難解であることが知られている。 定常木幅の例においても, いずれも難解であることを示す。
  論文  参考訳（メタデータ） (2023-12-12T10:49:33Z)
• What Planning Problems Can A Relational Neural Network Solve? [91.53684831950612]
  本稿では,計画問題のポリシーを表すリレーショナルニューラルネットワークの回路複雑性解析について述べる。 回路幅と深さの増大に関して,計画問題には3つの一般的なクラスが存在することを示す。 また、政策学習のためのニューラルネットワーク設計におけるこの分析の有用性についても解説する。
  論文  参考訳（メタデータ） (2023-12-06T18:47:28Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  まず、3層ニューラルネットワークがコンパクトな集合上のインジケータ関数を近似するように設計可能であることを示す。 その後、これは単純複体へと拡張され、その位相構造に基づいて幅の上界が導かれる。 トポロジカルアプローチを用いて3層ReLUネットワークの普遍近似特性を証明した。
  論文  参考訳（メタデータ） (2023-05-25T14:17:15Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  本研究では,スカラー値を持つ一層ネットワークのクラスとユークリッドノルムで有界な入力について検討する。 隠蔽層重み行列のスペクトルノルムの制御は、一様収束を保証するには不十分であることを示す。 スペクトルノルム制御が十分であることを示す2つの重要な設定を解析する。
  論文  参考訳（メタデータ） (2022-02-13T07:12:02Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Global Convergence of Three-layer Neural Networks in the Mean Field Regime [3.553493344868413]
  平均場系では、ニューラルネットワークは適切にスケールされ、幅は無限大になる傾向にあり、学習ダイナミクスは平均場限として知られる非線形かつ非自明な動的限界に傾向がある。 最近の研究は、この分析を2層ネットワークに適用し、グローバル収束保証を提供した。 平均場における非正規化フィードフォワード三層ネットワークに対する大域収束結果を示す。
  論文  参考訳（メタデータ） (2021-05-11T17:45:42Z)
• Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach [1.9493449206135296]
  ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。 本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。 両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
  論文  参考訳（メタデータ） (2020-12-22T00:29:54Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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