論文の概要: Splitter Orderings for Probabilistic Bisimulation

• arxiv url: http://arxiv.org/abs/2307.08614v1
• Date: Mon, 17 Jul 2023 16:30:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-23 17:25:08.822346
• Title: Splitter Orderings for Probabilistic Bisimulation
• Title（参考訳）: 確率的ビシミュレーションのためのスプリッタ順序付け
• Authors: Mohammadsadegh Mohagheghi, Khayyam Salehi
• Abstract要約: 本稿では,与えられた確率モデルの状態空間をバイシミュレートクラスに分割する反復過程を高速化する手法を提案する。 提案手法はいくつかのケーススタディに基づいて実装され,実行時間を平均1桁削減する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model checking has been proposed as a formal verification approach for analyzing computer-based and cyber-physical systems. The state space explosion problem is the main obstacle for applying this approach for sophisticated systems. Bisimulation minimization is a prominent method for reducing the number of states in a labeled transition system and is used to alleviate the challenges of the state space explosion problem. For systems with stochastic behaviors, probabilistic bisimulation is used to reduce a given model to its minimized equivalent one. In recent years, several techniques have been proposed to reduce the time complexity of the iterative methods for computing probabilistic bisimulation of stochastic systems with nondeterministic behaviors. In this paper, we propose several techniques to accelerate iterative processes to partition the state space of a given probabilistic model to its bisimulation classes. The first technique applies two ordering heuristics for choosing splitter blocks. The second technique uses hash tables to reduce the running time and the average time complexity of the standard iterative method. The proposed approaches are implemented and run on several conventional case studies and reduce the running time by one order of magnitude on average.
• Abstract（参考訳）: モデル検査はコンピュータベースおよびサイバー物理システムを解析するための正式な検証手法として提案されている。 状態空間爆発問題は、このアプローチを洗練されたシステムに適用するための主要な障害である。 バイシミュレーションの最小化はラベル付き遷移系における状態数を減らすための顕著な方法であり、状態空間爆発問題の課題を緩和するために用いられる。 確率的挙動を持つ系では、確率的双シミュレーションは与えられたモデルを最小化された等価なモデルに還元するために用いられる。 近年,確率システムの確率的ビシミュレートを非決定的挙動で計算する反復的手法の時間的複雑さを低減する手法が提案されている。 本稿では,与えられた確率モデルの状態空間をバイシミュレートクラスに分割する反復過程を高速化する手法を提案する。 最初のテクニックは、スプリッターブロックの選択に2つの順序ヒューリスティックを適用する。 第2のテクニックは、ハッシュテーブルを使用して、標準反復法のランニング時間と平均時間複雑さを削減する。 提案手法は, 従来のいくつかのケーススタディで実装, 実行し, 実行時間を平均1桁削減する。

関連論文リスト

• Improving Probabilistic Bisimulation for MDPs Using Machine Learning [0.0]
  本稿では,与えられたモデルの状態空間を確率的ビシミュレーションクラスに分割する新しい手法を提案する。 このアプローチは、最先端のツールと比較して、実行時間を著しく削減できる。
  論文  参考訳（メタデータ） (2023-07-30T12:58:12Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
  論文  参考訳（メタデータ） (2023-03-28T01:30:40Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。 提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。 大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
  論文  参考訳（メタデータ） (2022-11-02T14:35:13Z)
• Learning neural state-space models: do we need a state estimator? [0.0]
  我々は、広範囲な実験と分析に基づいて、ニューラルステートスペーストレーニングアルゴリズムの校正のための洞察を提供する。 初期状態推定の選択と役割に特に焦点をあてる。 動的システムのある種のクラスにおいて高い性能を達成するためには,先進的な初期状態推定手法が本当に必要であることを示す。
  論文  参考訳（メタデータ） (2022-06-26T17:15:35Z)
• Second-order flows for computing the ground states of rotating Bose-Einstein condensates [5.252966797394752]
  2次時間微分を含むいくつかの人工的進化微分方程式は1次であると考えられている。 提案した人工力学は、散逸を伴う新しい二階双曲偏微分方程式である。 新しいアルゴリズムは勾配流に基づく最先端の数値法よりも優れている。
  論文  参考訳（メタデータ） (2022-05-02T10:45:49Z)
• Data-driven Prediction of Relevant Scenarios for Robust Optimization [0.0]
  離散的な不確実性集合を持つロバストな1段階と2段階の問題について検討する。 本稿では,一連の開始シナリオで反復解法をシード化するデータ駆動型計算を提案する。 実験の結果,提案手法によって少数の優れたスタートシナリオを予測しても,反復的手法の時間を大幅に短縮できることがわかった。
  論文  参考訳（メタデータ） (2022-03-30T19:52:29Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• An application of the splitting-up method for the computation of a neural network representation for the solution for the filtering equations [68.8204255655161]
  フィルタ方程式は、数値天気予報、金融、工学など、多くの現実の応用において中心的な役割を果たす。 フィルタリング方程式の解を近似する古典的なアプローチの1つは、分割法と呼ばれるPDEにインスパイアされた方法を使うことである。 我々はこの手法をニューラルネットワーク表現と組み合わせて、信号プロセスの非正規化条件分布の近似を生成する。
  論文  参考訳（メタデータ） (2022-01-10T11:01:36Z)
• COSMIC: fast closed-form identification from large-scale data for LTV systems [4.10464681051471]
  データから離散時間線形時変系を同定するための閉形式法を提案する。 我々は、最適性を保証するアルゴリズムを開発し、軌跡ごとに考慮されるインスタントの数を線形に増加させる複雑性を持つ。 本アルゴリズムは,彗星インターセプタミッション用の低忠実度および機能工学シミュレーションの両方に適用した。
  論文  参考訳（メタデータ） (2021-12-08T16:07:59Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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