論文の概要: Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation

• arxiv url: http://arxiv.org/abs/2605.07839v1
• Date: Fri, 08 May 2026 15:05:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.142767
• Title: Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation
• Title（参考訳）: Sparse Context-State Belief Propagationによる厳密な規則制約付き可変次マルコフ生成
• Authors: François Pachet,
• Abstract要約: 我々は、一階マルコフ連鎖に対する信念の伝播を伴う規則的制約を扱うために、既存の正確な手法を拡張した。 可変順序拡張は、ジェネレータが可変順序/バックオフモデルであるときに既存のBP規則機械を走らせる必要がある状態空間を特定する。 固定化された文脈グラフとオートマトン推論は、順序において線型であり、一般には到達可能な積のエッジの数でスパースである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variable-order Markov models generate sequences over a finite alphabet by conditioning each symbol on the longest available suffix of the generated history. Regular constraints, by contrast, describe finite-horizon control requirements by an automaton: fixed positions, forced endings, metrical patterns, and forbidden copied fragments are all special cases. Existing exact methods already handle regular constraints with belief propagation for first-order Markov chains. The contribution here is the variable-order extension: identifying the state space on which the existing BP-regular machinery must be run when the generator is a variable-order/backoff model. A first-order constraint layer can enforce useful support conditions, but it computes future mass after merging histories that a variable-order generator deliberately keeps distinct. We formalize this mismatch and give the sparse construction obtained by replacing the first-order Markov state with the observed context state, then taking the standard product with the regular constraint automaton. For a fixed trained context graph and automaton, inference is linear in the sequence horizon; in general it is polynomial in the number of reachable product edges. This gives the correct variable-order distribution conditioned on regular constraints without expanding to all K-tuples. The same finite-source interface supports reversible data augmentation by inverse count lookup, matching materialized transposition augmentation without storing transformed corpora. We also separate exact BP inference from generation-time backoff policies, such as singleton avoidance, whose stochastic semantics must be made explicit if exactness is claimed.
• Abstract（参考訳）: 可変順序マルコフモデルは、生成された歴史の最も長い接尾辞に各記号を条件付けることによって、有限アルファベット上の列を生成する。 対照的に、通常の制約は、有限水平制御要求をオートマトンで記述する:固定位置、強制エンディング、メートル法パターン、および禁止された複写フラグメントは全て特別なケースである。 既存の正確な方法は、一階マルコフ連鎖に対する信念の伝播に関する規則的な制約を既に処理している。 ここでのコントリビューションは、変数順序拡張である: ジェネレータが可変順序/バックオフモデルであるときに、既存のBP規則機械が実行されなければならない状態空間を特定する。 一階制約層は有用なサポート条件を強制することができるが、可変階ジェネレータが意図的に区別される履歴をマージした後、将来の質量を計算する。 このミスマッチを形式化し、一階マルコフ状態を観測状態に置き換え、次に標準積を正規制約オートマトンに置き換えることで得られるスパース構成を与える。 固定された文脈グラフとオートマトンに対して、推論はシーケンス水平線において線型であり、一般には到達可能な積のエッジの数の多項式である。 これにより、すべてのK-タプルに拡張することなく、正規制約で条件付けられた正しい変数階分布が得られる。 同じ有限ソースインタフェースは、逆カウントルックアップによる可逆データ拡張をサポートし、変換コーパスを格納することなく、物質化トランスポジション拡張に適合する。 また、BPの正確な推論と、シングルトン回避のような世代毎のバックオフポリシーを分離する。

関連論文リスト

• Thinking Out of Order: When Output Order Stops Reflecting Reasoning Order in Diffusion Language Models [26.550350205533217]
  仮設拡散言語モデル(MDLM)は、全てのトークンを並列に洗練し、出力構造から順序を分離する。 本稿では,拡散過程の早い段階で,MDLMが複雑なトークンよりも単純なトークンを安定化することにより,秩序の堅牢性を実現することを示す。
  論文  参考訳（メタデータ） (2026-01-29T17:40:58Z)
• Zonkey: A Hierarchical Diffusion Language Model with Differentiable Tokenization and Probabilistic Attention [0.0]
  Zonkeyは階層的な拡散モデルであり、生文字から文書レベルの表現まで、完全にトレーニング可能なパイプラインを通じて制限に対処する。 コアとなるのは、確率的開始順序(BOS)決定を学習する、差別化可能なトークンである。 Zonkeyは、ノイズからコヒーレントで可変長のテキストを生成し、創発的な階層を示す。
  論文  参考訳（メタデータ） (2026-01-29T14:17:37Z)
• Learning Tractable Distributions Of Language Model Continuations [40.95717348276321]
  隠れマルコフモデル (HMM) のようなトラクタブルなサロゲートは継続よりも分布を近似し、復号時間でモデルの次トーケンロジットを調整する。 そこで我々はLearning to Look Ahead (LTLA)を提案する。これはリッチプレフィックスエンコーディングのための同じベース言語モデルと、正確な継続確率を計算する固定トラクタブルサロゲートモデルとを組み合わせたハイブリッドアプローチである。
  論文  参考訳（メタデータ） (2025-11-20T05:17:19Z)
• Higher-order Linear Attention [59.92962330635185]
  スケールされたドット積の注意の二次コストは、自己回帰言語モデルを長いコンテキストにスケールするための中心的な障害である。 本稿では,高次線形注意(Higher-order Linear Attention, HLA)を提案する。
  論文  参考訳（メタデータ） (2025-10-31T07:54:37Z)
• Bridging Generative and Discriminative Noisy-Label Learning via Direction-Agnostic EM Formulation [26.430145104987982]
  生成雑音ラベル学習のための一段階EMスタイルのフレームワークを提案する。 提案手法は, 最先端の精度, 遷移行列推定誤差の低減, および現在の生成的および識別的ベースラインよりも大幅に少ないトレーニング計算を実現する。
  論文  参考訳（メタデータ） (2023-08-02T14:48:25Z)
• Sequential Recommendation via Stochastic Self-Attention [68.52192964559829]
  Transformerベースのアプローチでは、アイテムをベクトルとして埋め込んで、ドット積の自己アテンションを使用してアイテム間の関係を測定する。 本稿では,これらの問題を克服するための新しいtextbfStochastic textbfSelf-textbfAttention (STOSA) を提案する。 我々は、アイテムと項目の位置関係を列で特徴づける新しいワッサースタイン自己保持モジュールを考案した。
  論文  参考訳（メタデータ） (2022-01-16T12:38:45Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Structured Reordering for Modeling Latent Alignments in Sequence Transduction [86.94309120789396]
  本稿では,分離可能な置換の辺りを正確に推定する効率的な動的プログラミングアルゴリズムを提案する。 結果のSeq2seqモデルは、合成問題やNLPタスクの標準モデルよりも体系的な一般化が優れている。
  論文  参考訳（メタデータ） (2021-06-06T21:53:54Z)
• Conditional Hybrid GAN for Sequence Generation [56.67961004064029]
  本稿では,この問題を解決するための条件付きハイブリッドGAN(C-Hybrid-GAN)を提案する。 我々はGumbel-Softmax法を利用して離散値列の分布を近似する。 提案したC-Hybrid-GANは、文脈条件付き離散値シーケンス生成において既存の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-09-18T03:52:55Z)

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

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