論文の概要: 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 18:44:13.722778
• 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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つの問題のパラメータ化複雑性を分析する。

関連論文リスト

• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。 具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
  論文  参考訳（メタデータ） (2025-02-22T06:21:56Z)
• Exploring the loss landscape of regularized neural networks via convex duality [42.48510370193192]
  本稿では,正規化ニューラルネットワークのロスランドスケープのいくつかの側面について論じる。 まず、その双対を用いて凸問題の解集合を特徴づけ、さらに全ての定常点を特徴づける。 ソリューションセットの特徴付けと接続結果は、異なるアーキテクチャに拡張可能であることを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:41:38Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  本稿では, ニューラルネットワーク幅の上下境界を定義し, 問題となるデータセットのポリトープ構造から情報を得る。 本研究では,データセットのポリトープ構造を学習したニューラルネットワークから推定できる逆条件を探索するアルゴリズムを開発した。 MNIST、Fashion-MNIST、CIFAR10といった一般的なデータセットは、顔の少ない2つ以上のポリトップを用いて効率的にカプセル化できることが確立されている。
  論文  参考訳（メタデータ） (2024-02-04T08:57:42Z)
• 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)
• Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
  離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。 オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。 我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
  論文  参考訳（メタデータ） (2021-10-29T15:06:15Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Computing Complexity-aware Plans Using Kolmogorov Complexity [0.9137554315375922]
  有限水平決定性有限オートマトンを出力として計算する複雑性を考慮した計画法を提案する。 本稿では,2つのアルゴリズムで低複素性ポリシーを求め,第1のアルゴリズムで低複素性最適ポリシーを求める。 移動ロボットの単純なナビゲーションタスクにおけるアルゴリズムの評価を行い,そのアルゴリズムは直感と一致する低複雑さのポリシーを導出する。
  論文  参考訳（メタデータ） (2021-09-21T16:25:04Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05: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)
• Automated Search for Resource-Efficient Branched Multi-Task Networks [81.48051635183916]
  我々は,多タスクニューラルネットワークにおける分岐構造を自動的に定義する,微分可能なニューラルネットワーク探索に根ざした原理的アプローチを提案する。 本手法は,限られた資源予算内で高い性能の分岐構造を見いだすことができる。
  論文  参考訳（メタデータ） (2020-08-24T09:49:19Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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