論文の概要: Log-Derivative Trick for Parametric Markov Chains

• arxiv url: http://arxiv.org/abs/2610.36655v1
• Date: Tue, 27 Oct 2026 05:18:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 04:15:49.233516
• Title: Log-Derivative Trick for Parametric Markov Chains
• Title（参考訳）: パラメトリックマルコフチェインの対数微分トリック
• Abstract要約: 対数導出トリックの測度論的一般化に基づくスケーラブルなモンテカルロ勾配推定器を提案する。 提案手法は,大域的状態空間の物質化と線形システムの完全解法を回避する。
• 参考スコア（独自算出の注目度）: 0.17205106391379021
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing expected rewards and reachability probabilities in parametric Markov chains (pMCs) is central to the analysis and synthesis of probabilistic systems with loops. While traditional symbolic synthesis approaches--such as parameter lifting and rational function generation--suffer from scalability bottlenecks, gradient-based optimization emerges as an effective alternative. However, existing gradient-based techniques still rely on symbolic gradient computation--such as solving large linear systems--over the global state space, inheriting scalability limits. Finite-horizon approximation is possible but introduces uncontrollable bias. In this paper, we introduce a scalable Monte Carlo gradient estimator based on a measure-theoretic generalization of the log-derivative trick. We prove that our estimator provides unbiased gradient estimates under almost-sure termination and standard regularity conditions. Crucially, our method avoids global state-space materialization and linear system solving entirely: it operates purely along sampled trajectories, requiring only black-box evaluations of local transition probabilities (or densities) and their derivatives. Unlike existing pMC techniques that are fundamentally restricted to finite discrete systems, our measure-theoretic framework naturally extends to continuous and general $σ$-finite state spaces. Empirical evaluations on synthetic discrete pMCs and continuous-state case studies demonstrate that our method scales to state spaces far beyond the reach of existing solvers, significantly reducing execution time without introducing bias.
• Abstract（参考訳）: パラメトリックマルコフ連鎖(pMC)における期待される報酬と到達可能性の最適化は、ループを持つ確率系の解析と合成の中心である。 パラメータリフトや有理関数生成といった従来の記号合成アプローチはスケーラビリティのボトルネックから切り離されているが、勾配に基づく最適化は効果的な代替手段として現れている。 しかし、既存の勾配に基づく手法は、大規模な線形システムの解法など、いまだにシンボリック勾配計算に依存しており、グローバルな状態空間を超越し、スケーラビリティの限界を継承している。 有限ホライゾン近似は可能であるが、制御不能なバイアスをもたらす。 本稿では,対数導出トリックの測度論的一般化に基づくスケーラブルなモンテカルロ勾配推定器を提案する。 我々の推定器は、ほぼ確実な終端条件と標準正則条件の下で、偏りのない勾配推定を提供することを証明している。 本手法は, 局所遷移確率(あるいは密度)とその誘導体のブラックボックス評価のみを要し, サンプル軌道に沿って純粋に動作する。 基本的に有限離散系に制限される既存のpMC技術とは異なり、我々の測度理論フレームワークは自然に連続かつ一般の$σ$-finite状態空間にまで拡張する。 合成離散型PMCと連続状態ケーススタディの実証評価により,本手法は既存の解法の到達範囲をはるかに超えた状態空間にスケールし,バイアスを伴わずに実行時間を著しく短縮することを示した。

関連論文リスト

• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  バイレベル最適化(SBO)は、最近多くの機械学習パラダイムに統合されている。 本稿では,二段階最適化手法の体系的解析について述べる。 結果は再読解を必要とせず、より汎用的な目的関数に適用できる。
  論文  参考訳（メタデータ） (2026-04-05T12:12:58Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• An Empirical Risk Minimization Approach for Offline Inverse RL and Dynamic Discrete Choice Model [8.95720650633184]
  機械学習において、動的選択(DDC)モデル(オフライン最大エントロピー正規化逆強化学習(オフラインMaxEnt-IRL))を推定する問題について検討する。 目的は、オフラインの振舞いデータからエージェントの振舞いを管理する$Q*$関数をリカバリすることである。 線形パラメータ化報酬の制限的仮定を使わずにこれらの問題を解くための大域収束勾配法を提案する。
  論文  参考訳（メタデータ） (2025-02-19T22:22:20Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  勾配アルゴリズムは線形系を解くのに有効な方法である。 最適値に収束しない場合であっても,勾配降下は正確な予測を導出することを示す。 実験的に、勾配降下は十分に大規模または不条件の回帰タスクにおいて最先端の性能を達成する。
  論文  参考訳（メタデータ） (2023-06-20T15:07:37Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く 本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
  論文  参考訳（メタデータ） (2023-05-19T16:24:47Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLEは、局所的、計量的項と大域的、位相的項の両方で損失関数を最小化し、初期埋め込みを補正する次元推論後処理ステップである。 DIPOLEは、UMAP、t-SNE、Isomapといった一般的な手法よりも多くの一般的なデータセットで優れています。
  論文  参考訳（メタデータ） (2021-06-14T17:19:44Z)
• On dissipative symplectic integration with applications to gradient-based optimization [77.34726150561087]
  本稿では,離散化を体系的に実現する幾何学的枠組みを提案する。 我々は、シンプレクティックな非保守的、特に散逸的なハミルトン系への一般化が、制御された誤差まで収束率を維持することができることを示す。
  論文  参考訳（メタデータ） (2020-04-15T00:36:49Z)

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

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