論文の概要: Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach

• arxiv url: http://arxiv.org/abs/2511.18103v1
• Date: Sat, 22 Nov 2025 16:02:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.62921
• Title: Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach
• Title（参考訳）: ラベル付きマルコフ連鎖の比較:カントール・カントロヴィチのアプローチ
• Authors: Adrien Banse, Alessandro Abate, Raphaël M. Jungers,
• Abstract要約: 最近導入されたカントール・カントロビッチ距離(CK)について検討した。 特に、後者は有限水平全変動距離の割引和として表すことができる。 より正確には、CK距離の正確な計算は#P-hardである。
• 参考スコア（独自算出の注目度）: 53.66196601631798
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Labeled Markov Chains (or LMCs for short) are useful mathematical objects to model complex probabilistic languages. A central challenge is to compare two LMCs, for example to assess the accuracy of an abstraction or to quantify the effect of model perturbations. In this work, we study the recently introduced Cantor-Kantorovich (or CK) distance. In particular we show that the latter can be framed as a discounted sum of finite-horizon Total Variation distances, making it an instance of discounted linear distance, but arising from the natural Cantor topology. Building on the latter observation, we analyze the properties of the CK distance along three dimensions: computational complexity, continuity properties and approximation. More precisely, we show that the exact computation of the CK distance is #P-hard. We also provide an upper bound on the CK distance as a function of the approximation relation between the two LMCs, and show that a bounded CK distance implies a bounded error between probabilities of finite-horizon traces. Finally, we provide a computable approximation scheme, and show that the latter is also #P-hard. Altogether, our results provide a rigorous theoretical foundation for the CK distance and clarify its relationship with existing distances.
• Abstract（参考訳）: ラベル付きマルコフ連鎖(英: Labeled Markov Chains、略して LMC)は、複雑な確率言語をモデル化するために有用な数学的対象である。 中心的な課題は、2つのLCCを比較し、例えば抽象の精度を評価したり、モデルの摂動の影響を定量化することである。 本研究では,最近導入されたカントール・カントロビッチ距離(CK)について検討する。 特に、後者は有限水平トータル変分距離の割引和として表すことができ、これは割引線型距離の例であるが、自然なカントール位相から生じる。 後者の観測に基づいて、計算複雑性、連続性特性、近似の3次元に沿ったCK距離の特性を解析する。 より正確には、CK距離の正確な計算は#P-hardである。 また、2つの LMC 間の近似関係の関数として CK 距離上の上界を提供し、有界 CK 距離が有限水平トレースの確率間の有界誤差を示すことを示す。 最後に、計算可能な近似スキームを提供し、後者も#P-hardであることを示す。 また, CK距離に関する厳密な理論的基礎を提供し, 既存の距離との関係を明らかにする。

関連論文リスト

• Kernel Trace Distance: Quantum Statistical Metric between Measures through RKHS Density Operators [11.899035547580201]
  核共分散作用素のシャッテンノルムを通して比較する測度間の新しい距離を導入する。 この新たな距離は、最大平均離散値(MMD)とワッサーシュタイン距離のフレーム化が可能な積分確率計量であることを示す。
  論文  参考訳（メタデータ） (2025-07-08T14:56:44Z)
• Feature Subset Weighting for Distance-based Supervised Learning through Choquet Integration [2.1943338072179444]
  本稿では,遠隔教師あり学習のための単調測度を用いた特徴量重み付けを提案する。 チョーケ積分は、これらの重みを包含する距離計量を定義するために用いられる。 提案手法は, 重複・強相関の付加により, 距離が影響を受けないことを確実にするものである。
  論文  参考訳（メタデータ） (2025-04-01T10:23:01Z)
• A distance function for stochastic matrices [0.9217021281095907]
  Bhattacharyya角は、マルコフ連鎖の列から始めて、短周期と長期のマルコフ連鎖の実行を比較する自然なツールとして提唱されている。 マルコフ列上のバタチャリア角や新しい行列距離を考えると、モデル間の距離は同じである。
  論文  参考訳（メタデータ） (2024-10-16T15:49:25Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。 フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
  論文  参考訳（メタデータ） (2023-01-10T01:58:15Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Tangent Space and Dimension Estimation with the Wasserstein Distance [10.118241139691952]
  ユークリッド空間の滑らかなコンパクト部分多様体の近くで独立にサンプリングされた点の集合を考える。 我々は、その多様体の次元と接空間の両方を推定するために必要なサンプル点の数について数学的に厳密な境界を与える。
  論文  参考訳（メタデータ） (2021-10-12T21:02:06Z)
• Kernel distance measures for time series, random fields and other structured data [71.61147615789537]
  kdiffは、構造化データのインスタンス間の距離を推定するためのカーネルベースの新しい尺度である。 これはインスタンス間の自己類似性と交差類似性の両方を考慮し、距離分布の低い定量値を用いて定義される。 kdiffをクラスタリングと分類問題のための距離尺度として用いた分離性条件について,いくつかの理論的結果が得られた。
  論文  参考訳（メタデータ） (2021-09-29T22:54:17Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。 本手法は既存の不一致対策よりも高いロバスト性を実現する。
  論文  参考訳（メタデータ） (2020-06-13T06:09:27Z)

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

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