論文の概要: Analyzing Value Functions of States in Parametric Markov Chains

• arxiv url: http://arxiv.org/abs/2504.17020v2
• Date: Sat, 26 Apr 2025 05:49:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:53.13145
• Title: Analyzing Value Functions of States in Parametric Markov Chains
• Title（参考訳）: パラメトリックマルコフ鎖における状態の値関数の解析
• Authors: Kasper Engelen, Guillermo A. Pérez, Shrisha Rao,
• Abstract要約: まず、ある状態からの到達可能性確率が他の状態よりも低いかどうかを問うために単調性を低下させる。 後者の特性に対する最近の結果は、同値同値類を崩壊させる効率的なアルゴリズムを示唆している。 まず、崩壊によって既存のベンチマークのサイズが縮小され、いくつかのカスタムベンチマークが大幅に削減されます。
• 参考スコア（独自算出の注目度）: 7.271205677308994
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parametric Markov chains (pMC) are used to model probabilistic systems with unknown or partially known probabilities. Although (universal) pMC verification for reachability properties is known to be coETR-complete, there have been efforts to approach it using potentially easier-to-check properties such as asking whether the pMC is monotonic in certain parameters. In this paper, we first reduce monotonicity to asking whether the reachability probability from a given state is never less than that of another given state. Recent results for the latter property imply an efficient algorithm to collapse same-value equivalence classes, which in turn preserves verification results and monotonicity. We implement our algorithm to collapse "trivial" equivalence classes in the pMC and show empirical evidence for the following: First, the collapse gives reductions in size for some existing benchmarks and significant reductions on some custom benchmarks; Second, the collapse speeds up existing algorithms to check monotonicity and parameter lifting, and hence can be used as a fast pre-processing step in practice.
• Abstract（参考訳）: パラメトリックマルコフ連鎖 (pMC) は未知あるいは部分的に知られている確率を持つ確率系をモデル化するために用いられる。 到達性特性に対する(ユニバーサルな) pMC 検証は coETR 完全であることが知られているが、あるパラメータにおいて pMC が単調かどうかを問うなど、潜在的に容易にチェックできる性質を用いてアプローチする試みがある。 本稿では,まず,与えられた状態からの到達可能性確率が,他の状態よりも低いかどうかを問うため,単調性を低下させる。 後者の特性の最近の結果は、同値同値類を崩壊させる効率的なアルゴリズムを示し、検証結果と単調性を保持する。 第一に、崩壊は既存のベンチマークのサイズを小さくし、いくつかのカスタムベンチマークを著しく削減します。第二に、崩壊はモノトニック性やパラメータリフトをチェックするために既存のアルゴリズムを高速化し、実際は高速な前処理ステップとして使用できます。

関連論文リスト

• Learning Algorithms for Verification of Markov Decision Processes [20.5951492453299]
  マルコフ決定過程(MDP)の検証に学習アルゴリズムを適用するための一般的な枠組みを提案する。 提案するフレームワークは,検証における中核的な問題である確率的到達性に重点を置いている。
  論文  参考訳（メタデータ） (2024-03-14T08:54:19Z)
• Rethinking Classifier Re-Training in Long-Tailed Recognition: A Simple Logits Retargeting Approach [102.0769560460338]
  我々は,クラスごとのサンプル数に関する事前知識を必要とせず,シンプルなロジットアプローチ(LORT)を開発した。 提案手法は,CIFAR100-LT, ImageNet-LT, iNaturalist 2018など,様々な不均衡データセットの最先端性能を実現する。
  論文  参考訳（メタデータ） (2024-03-01T03:27:08Z)
• Learning Hidden Markov Models When the Locations of Missing Observations are Unknown [54.40592050737724]
  本研究では、未知の観測位置を持つデータからHMMを学習する際の一般的な問題について考察する。 我々は、下層の鎖の構造に関する仮定を一切必要としない再構成アルゴリズムを提供する。 適切な仕様の下では、プロセスのダイナミクスを再構築でき、また、見当たらない観測位置が分かっていたとしても、その有効性を示す。
  論文  参考訳（メタデータ） (2022-03-12T22:40:43Z)
• Comparison of Markov chains via weak Poincar\'e inequalities with application to pseudo-marginal MCMC [0.0]
  マルコフ連鎖の平衡への有界収束に対する弱ポアンカーの不等式として知られるある種の機能的不等式の使用について検討する。 本研究では, 独立メトロポリス・ハスティングス・サンプリング法や, 難易度を求める疑似マルジナル手法などの手法に対して, サブ幾何学的収束境界の導出を可能にすることを示す。
  論文  参考訳（メタデータ） (2021-12-10T15:36:30Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。 このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。 複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-09-01T09:52:31Z)
• Incremental Verification of Fixed-Point Implementations of Neural Networks [0.19573380763700707]
  インクリメンタル境界モデル検査(BMC)、満足度変調理論(SMT)、不変推論を用いた新しいシンボル検証フレームワークの開発と評価を行った。 提案手法は,異なる入力画像を考慮した21の試験事例の85.8%,カバー手法に関連する特性の100%を検証・生成することができた。
  論文  参考訳（メタデータ） (2020-12-21T10:03:44Z)
• The Variational Method of Moments [65.91730154730905]
  条件モーメント問題は、観測可能量の観点から構造因果パラメータを記述するための強力な定式化である。 OWGMMの変動最小値再構成により、条件モーメント問題に対する非常に一般的な推定器のクラスを定義する。 同じ種類の変分変換に基づく統計的推測のためのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-12-17T07:21:06Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals [22.77704627076251]
  確率変数(RV)の合同確率の学習は、統計信号処理と機械学習の基盤となる。 近年, 任意の数の RV の結合確率質量関数 (PMF) を3次元境界から復元する研究が提案されている。 正確に3次元の辺縁を推定することは、標本の複雑さの観点からもコストがかかる。 この研究は、ペアの辺りだけを用いて共同PMFを学習するための新しい枠組みを生み出した。
  論文  参考訳（メタデータ） (2020-06-30T15:43:44Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。 問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。 我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
  論文  参考訳（メタデータ） (2020-06-18T17:18:02Z)
• Entropy Regularized Power k-Means Clustering [21.013169939337583]
  本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。 我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
  論文  参考訳（メタデータ） (2020-01-10T14:05:44Z)

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

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