論文の概要: Polynomial-Time Reachability for LTI Systems with Two-Level Lattice
Neural Network Controllers
- arxiv url: http://arxiv.org/abs/2209.09400v1
- Date: Tue, 20 Sep 2022 01:12:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 18:11:30.848843
- Title: Polynomial-Time Reachability for LTI Systems with Two-Level Lattice
Neural Network Controllers
- Title（参考訳）: 2レベル格子ニューラルネットワーク制御器を用いたLTIシステムの多項式時間到達性
- Authors: James Ferlez and Yasser Shoukry
- Abstract要約: 本稿では,Rectified Linear Unit (ReLU) Two-Level Lattice (TLL) Neural Network (NN) コントローラのサイズで,正確なワンステップ到達可能なセットを時間で計算可能であることを示す。
そこで本研究では,L-TLLBoxと呼ばれる,半エクサビリティと近似リーチビリティの利点を適応的に組み合わせたアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.4620086904601473
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the computational complexity of bounding the
reachable set of a Linear Time-Invariant (LTI) system controlled by a Rectified
Linear Unit (ReLU) Two-Level Lattice (TLL) Neural Network (NN) controller. In
particular, we show that for such a system and controller, it is possible to
compute the exact one-step reachable set in polynomial time in the size of the
size of the TLL NN controller (number of neurons). Additionally, we show that
it is possible to obtain a tight bounding box of the reachable set via two
polynomial-time methods: one with polynomial complexity in the size of the TLL
and the other with polynomial complexity in the Lipschitz constant of the
controller and other problem parameters. Crucially, the smaller of the two can
be decided in polynomial time for non-degenerate TLL NNs. Finally, we propose a
pragmatic algorithm that adaptively combines the benefits of (semi-)exact
reachability and approximate reachability, which we call L-TLLBox. We evaluate
L-TLLBox with an empirical comparison to a state-of-the-art NN controller
reachability tool. In these experiments, L-TLLBox was able to complete
reachability analysis as much as 5000x faster than this tool on the same
network/system, while producing reach boxes that were from 0.08 to 1.42 times
the area.
- Abstract（参考訳）: 本稿では,Rectified Linear Unit (ReLU) Two-Level Lattice (TLL) Neural Network (NN) コントローラによって制御される線形時間不変系(LTI)の到達可能な集合を束縛する計算複雑性について考察する。
特に、そのようなシステムやコントローラでは、tll nnコントローラ(ニューロン数)のサイズの大きさで多項式時間で正確に1ステップ到達可能な集合を計算できることを示す。
さらに、2つの多項式時間法により到達可能な集合のタイトな有界ボックスを得ることができ、一方はTLLの大きさの多項式複雑性を持つもので、もう一方はコントローラのリプシッツ定数の多項式複雑性を持つものである。
重要なことに、これら2つのうちより小さいものは、非退化TLL NNに対して多項式時間で決定できる。
最後に,L-TLLBox と呼ばれる実測到達性と近似到達性の利点を適応的に組み合わせた実用的アルゴリズムを提案する。
我々は,L-TLLBoxを最先端のNNコントローラの到達性ツールと比較した。
これらの実験では、L-TLLBoxは、同じネットワーク/システム上でこのツールよりも5,000倍早く到達可能性解析を完了し、面積の0.08から1.42倍のリーチボックスを生成することができた。
関連論文リスト
- Depth Separation in Norm-Bounded Infinite-Width Neural Networks [55.21840159087921]
無限幅ニューラルネットワークでは,重みの総和$ell$-normで複雑性を制御できる。
本稿では,標準制御深度3ReLUネットワークによる入力次元のサンプル複雑性を学習可能な関数が存在するが,標準制御深度2ReLUネットワークによるサブ指数サンプル複雑性では学習できないことを示す。
論文 参考訳（メタデータ） (2024-02-13T21:26:38Z) - Distributed Inference and Fine-tuning of Large Language Models Over The
Internet [91.00270820533272]
大規模言語モデル(LLM)は、多くのNLPタスクで有用であり、サイズが向上する。
これらのモデルはハイエンドのハードウェアを必要とするため、ほとんどの研究者にはアクセスできない。
本研究では,システムスループットの最大化のためにデバイスを自動的に割り当てるフォールトトレラント推論アルゴリズムとロードバランシングプロトコルを開発する。
論文 参考訳（メタデータ） (2023-12-13T18:52:49Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - MULTIGAIN 2.0: MDP controller synthesis for multiple mean-payoff, LTL and steady-state constraints [41.94295877935867]
コントローラ合成ツールMultiGAINのメジャー拡張であるMultiGAIN 2.0を提案する。
確率論的モデルチェッカー PRISM 上に構築されている。
論文 参考訳（メタデータ） (2023-05-26T08:59:51Z) - Learning Minimally-Violating Continuous Control for Infeasible Linear
Temporal Logic Specifications [2.496282558123411]
本稿では、線形時間論理(LTL)として表される複雑な高次タスクを満たすための目標駆動ナビゲーションの連続時間制御について検討する。
基礎となる力学系が未知である深層強化学習(DRL)を用いたモデルフリー合成フレームワーク(不透明ボックス)を提案する。
論文 参考訳（メタデータ） (2022-10-03T18:32:20Z) - Lightweight and Progressively-Scalable Networks for Semantic
Segmentation [100.63114424262234]
マルチスケール学習フレームワークは,セマンティックセグメンテーションを向上する有効なモデルのクラスと見なされてきた。
本稿では,畳み込みブロックの設計と,複数スケールにわたる相互作用の仕方について,徹底的に解析する。
我々は,軽量で拡張性の高いネットワーク(LPS-Net)を考案した。
論文 参考訳（メタデータ） (2022-07-27T16:00:28Z) - Fast BATLLNN: Fast Box Analysis of Two-Level Lattice Neural Networks [1.6500749121196987]
高速BATLLNNは、2レベル格子(TLL)ニューラルネットワーク(NN)のためのボックスライクな出力制約の高速検証器である
Fast BATLLNNは、最も高速なNN検証器でさえも非常に好意的に比較し、私たちの合成TLLテストベンチは、最も近い競合製品よりも400倍以上高速です。
論文 参考訳（メタデータ） (2021-11-17T18:46:11Z) - Safe-by-Repair: A Convex Optimization Approach for Repairing Unsafe
Two-Level Lattice Neural Network Controllers [1.6500749121196987]
既知の"counterexample"状態における安全でないクローズドループ動作の修復を目指す。
また、別個の検証された状態集合上での安全な閉ループ挙動の概念も保存する。
それぞれの部分問題を解くための十分条件の組が凸実現可能性問題としてキャストできることを示す。
論文 参考訳（メタデータ） (2021-04-06T21:21:24Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Distributed Online Linear Quadratic Control for Linear Time-invariant
Systems [14.924672048447334]
同一線形時間不変系(LTI)に対する分散オンライン線形二次問題(LQ)について検討する。
各エージェントがLTIシステムとしてモデル化されるマルチエージェントネットワークを考える。
オンラインLQアルゴリズムの分散変種を開発し、半定値プログラミング(SDP)にプロジェクションを投射して、分散オンライン勾配降下を実行し、コントローラを生成する。
論文 参考訳（メタデータ） (2020-09-29T03:30:49Z) - Neural Networks are Convex Regularizers: Exact Polynomial-time Convex
Optimization Formulations for Two-layer Networks [70.15611146583068]
我々は、線形整列ユニット(ReLU)を用いた2層ニューラルネットワークのトレーニングの正確な表現を開発する。
我々の理論は半無限双対性と最小ノルム正規化を利用する。
論文 参考訳（メタデータ） (2020-02-24T21:32:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。