論文の概要: A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis

• arxiv url: http://arxiv.org/abs/2112.05745v1
• Date: Fri, 10 Dec 2021 18:56:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-13 14:56:16.861358
• Title: A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis
• Title（参考訳）: 単純かつ効率的なサンプリングに基づく一般到達可能性解析アルゴリズム
• Authors: Thomas Lew, Lucas Janson, Riccardo Bonalli, Marco Pavone
• Abstract要約: 汎用リーチビリティ分析は、ニューラルネットワークの検証から動的システムの安全性分析まで、アプリケーションにおいて非常に難しい問題である。 入力をサンプリングし、真の到達可能なセットで画像を評価し、その$epsilon$padded convex hullをセット推定器として利用することにより、このアルゴリズムは一般的な問題設定に適用でき、実装も簡単である。 この分析はアルゴリズム設計に、高い確率で$epsilon$-close reachable set approximationを得るよう通知する。 ニューラルネットワーク検証タスクでは、このアプローチが以前の作業よりも正確で、はるかに高速であることを示す。
• 参考スコア（独自算出の注目度）: 32.488975902387395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their $\epsilon$-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an $\epsilon$-close reachable set approximation with high probability, provides insights into which reachability problems are most challenging, and motivates safety-critical applications of the technique. On a neural network verification task, we show that this approach is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.
• Abstract（参考訳）: 本研究では,汎用到達可能性解析のための効率的なサンプリングベースアルゴリズムを解析し,ニューラルネットワークの検証から動的システムの安全性解析まで,非常に難しい課題である。 入力をサンプリングし、真の到達可能セットで画像を評価し、その$\epsilon$-padded convex hullをセット推定器として取ることにより、このアルゴリズムは一般的な問題設定に適用され、実装が容易である。 我々の主な貢献は、ランダム集合理論を用いた漸近的および有限サンプル精度保証の導出である。 この解析はアルゴリズム設計に、高い確率で$\epsilon$-close reachable setの近似を得るよう通知し、到達可能性問題が最も困難であることを示す洞察を与え、この技術の安全性クリティカルな応用を動機付ける。 ニューラルネットワーク検証タスクでは、このアプローチが以前の作業よりも正確で、はるかに高速であることを示す。 分析により,ハードウェア実験で実証した堅牢なモデル予測コントローラも設計した。

関連論文リスト

• It Is Time To Steer: A Scalable Framework for Analysis-driven Attack Graph Generation [50.06412862964449]
  アタックグラフ(AG)は、コンピュータネットワークに対するマルチステップ攻撃に対するサイバーリスクアセスメントをサポートする最も適したソリューションである。 現在の解決策は、アルゴリズムの観点から生成問題に対処し、生成が完了した後のみ解析を仮定することである。 本稿では,アナリストがいつでもシステムに問い合わせることのできる新しいワークフローを通じて,従来のAG分析を再考する。
  論文  参考訳（メタデータ） (2023-12-27T10:44:58Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• A Learning-Based Optimal Uncertainty Quantification Method and Its Application to Ballistic Impact Problems [1.713291434132985]
  本稿では、入力(または事前)測度が部分的に不完全であるシステムに対する最適(最大および無限)不確実性境界について述べる。 本研究では,不確実性最適化問題に対する学習基盤の枠組みを実証する。 本手法は,工学的実践における性能証明と安全性のためのマップ構築に有効であることを示す。
  論文  参考訳（メタデータ） (2022-12-28T14:30:53Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Reachability Analysis of Convolutional Neural Networks [10.384532888747993]
  入力領域が与えられたネットワークの正確な到達可能な集合を計算するためのアプローチを提案する。 私たちのアプローチは、出力到達可能なセットが与えられた入力ドメインへのバックトラックも可能です。 到達可能な集合の高速計算を行う高速解析手法も提案されている。
  論文  参考訳（メタデータ） (2021-06-22T21:42:00Z)
• Towards Large Scale Automated Algorithm Design by Integrating Modular Benchmarking Frameworks [0.9281671380673306]
  本稿では,アルゴリズムフレームワークであるParadisEOと,自動アルゴリズム設定ツール irace と実験プラットフォーム IOHknownr の効率性を示す最初の概念実証例を提案する。 パイプラインの主な利点は、高速な評価時間、豊富なデータセットを生成する可能性、そしてサンプリングベースの最適化の非常に幅広いクラスをベンチマークするのに使用できる標準化されたインターフェースである。
  論文  参考訳（メタデータ） (2021-02-12T10:47:00Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

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

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