技術的概要：疎なコンテキスト状態信念伝播による厳密な正規制約付き可変次数マルコフ生成

1. 問題定義

シーケンス生成システムは、しばしば局所的統計的整合性と明示的な大域制御の間で対立に直面する。可変次数マルコフ（VOM）モデルは、前者において優れており、各記号を、継続が観測された履歴の最長の接尾辞に条件付けることで、固定次数モデルの硬直性なしに局所的なスタイルパターンを保持する。しかし、正規制約（例えば、固定位置、禁止部分文字列、韻律パターン）に対する既存の厳密な手法は、信念伝播（BP）を用いた場合、一次マルコフ連鎖に限定されている。

本稿で扱われる核心的な問題は、VOM 生成と正規制約を、以下のいずれの欠点も伴わずに組み合わせる方法である：

1. メモリ性の崩壊：可変次数生成器を一次連鎖に射影すること。これにより異なる履歴が統合され、正しい可変次数確率に必要な特定のコンテキスト情報が失われる。
2. 状態空間の膨張：モデルを密な次数$K$の状態空間（可能なすべての$K$-タプル）に持ち上げること。これは計算的に扱い不可能（$|V|^K$）であり、実際の訓練データの疎性を無視する。

一次 BP の単純な適用を可行性マスクとして用いることは失敗する。なぜなら、それは制約下での「脆弱な」未来（低確率質量）と「豊富な」未来を区別できず、誤った条件付き分布をもたらすからである。

2. 手法

2.1 疎なコンテキスト状態抽象化

本稿は、疎なコンテキスト状態の構築を提案する。最後に放出された記号（一次）または可能なすべての$K$-タプル（密な次数$K$）を使用する代わりに、推論状態は訓練済みモデルで観測されたアクティブなコンテキストとして定義される。

• コンテキスト状態集合（$\mathcal{T}$）：VOM によって保存された観測コンテキストの集合であり、バックオフ規則で要求される接尾辞について閉じている。
• 遷移システム：遷移は、記号$y$を放出し、新しい履歴の最長の接尾辞（$\mathcal{T}$内に存在するもの）にコンテキストを更新することで定義される。
• エッジ重み：遷移の確率は、可変次数条件付き確率$P_{VO}(y|s)$であり、生成時のポリシー（例：シングルトンの回避）によって修正される可能性がある。

2.2 正規制約の統合

本手法は、疎なコンテキストグラフと正規制約オートマトン$\mathcal{A} = (Q, V, \delta, q_0, F)$との間に積オートマトンを構築する。

• 状態空間：推論状態はペア$(s, q)$であり、ここで$s \in \mathcal{T}$はアクティブなコンテキスト、$q \in Q$はオートマトン状態である。
• 信念伝播：標準的なフォワード・バックワード動的計画法がこの積グラフ上で実行される。
  • バックワードメッセージ（$\beta$）：与えられた積状態からホライズンまでの総「受容質量」を計算する。
  • サンプリング：祖先サンプリングは、局所遷移確率と遷移先状態のバックワードメッセージの積に比例してエッジを選択することで実行される。

2.3 生成時ポリシーの処理

本稿は、固定確率源の厳密な条件付けと制約付き生成ポリシー（例：Continuator 風のバックオフ）を区別する。

• 次数選択が固定源定義の一部である場合、BP は厳密な事後分布をもたらす。
• 次数選択が動的ポリシー（例：「シングルトン継続を持つ高次コンテキストをスキップする」）である場合、本稿はこれを、BP が各候補次数内で厳密な未来質量を提供し、ポリシーが最も高い実行可能な次数を選択する逐次プロセスとして形式化する。これには、意味的明瞭さを維持するために、BP 推論とポリシー論理の明示的な分離が必要である。

2.4 可逆的データ拡張

本フレームワークは、変換されたコーパスを具体化することなく、可逆的変換（例：ピッチ転置）をサポートする。変換$g$下でのコンテキスト$s$の計数は、逆引きによって計算される：
$$N_G(s, y) = \sum_{g \in G} N(g^{-1}s, g^{-1}y)$$
これにより、BP 機構は、元の計数テーブルのみを保存しながら、「仮想」拡張源上で動作できる。

3. 主要な貢献

1. BP-正規機構の可変次数拡張：本稿は、可変次数生成器に対して既存の BP-正規アルゴリズムを実行するための正しい疎な状態空間（観測コンテキスト）を特定し、一次射影の不一致を回避する。
2. 厳密な疎構築：厳密な制約付き生成が、観測された可変次数コンテキストと制約オートマトンの積上で BP を実行することで達成できることを示す形式的分解。
3. 複雑性解析：推論は、固定された訓練済み積グラフに対してシーケンスホライズンに対して線形であり、次数$K$の指数関数的ではなく、到達可能な積エッジの数に対して多項式である。
4. ポリシーの分離：厳密な BP 推論と生成時次数ポリシー（シングルトン回避など）の明確な区別により、「厳密性」の主張が意味的に正確であることを保証する。
5. 仮想拡張インターフェース：ソースレベルで可逆的データ拡張を処理する方法。具体化されたコーパスを保存することなく、その統計に一致させる。

4. 実験結果

4.1 厳密性の検証（小規模コーパス）

完全な制約付き分布を列挙可能な小規模な整数コーパスを使用：

• 分配関数：BP 計算された分配関数（$Z_{BP}$）は、総当たり列挙（$Z_{brute}$）と完全に一致した（浮動小数点精度の範囲内）。
• 分布精度：BP サンプリャーによって誘発された条件付き確率は、厳密な制約付き分布と一致した。
• 制約満足：サンプリングされたすべてのシーケンスは制約（位置および禁止部分文字列）を満たした。
• 比較：一次サポートマスクは正しい分布を生成できず、コンテキスト状態アプローチの必要性を確認した。

4.2 スケーラビリティ（バッハのプレリュード実験）

バッハのハ長調プレリュード（592 イベント、25 ピッチ）のピッチのみのエンコーディングに対して、ホライズン 32 および MAXORDER 制約（コピーされた 5-グラムを禁止）を用いてスケーラビリティテストを実施。

• 状態空間削減：最大次数$K=6$において、疎な到達可能な積は1,205 状態および83,207 エッジであった。
  • これは、完全な積の上限（約 340 万エッジ）および密な持ち上げられた状態空間（$25^6 \approx 2.4 \times 10^8$状態）よりも桁違いに小さい。
• パフォーマンス：バックワードパス計算は 0.1 秒未満、サンプリングはシーケンスあたり 0.4 ミリ秒未満であった。
• ポリシー動作：制約付き次数スタックポリシーは制約をうまく navigated し、無謀な固定源条件付けが高次でゼロ質量をもたらす状況で、実行可能な継続を見出した。
• 仮想拡張：12 キー転置の実験は、元のコーパスのみを保存しながら、仮想拡張が成功質量および分布において明示的な具体化と一致することを示した。

4.3 実装比較

既存の Continuator 実装（位置制約に限定）と比較：

• 新しい vo-regular-bp 実装は、次数$K \ge 3$においてバックワードメッセージを著しく高速に計算した。
• エンドツーエンドの生成時間は、$K \ge 3$において高速であった。

5. 意義と主張

本稿は、バックオフを魅力的にする可変次数構造を放棄することなく、疎なコンテキスト積上で正規制約情報を厳密に計算できると主張する。

• 正しさ：本手法は、正規制約に条件付けられた正しい可変次数分布を提供し、一次射影（異なる履歴を統合する）および密な持ち上げ（計算的に禁止的）の落とし穴を回避する。
• 実用性：このアプローチは、小規模コーパスおよび特定の制約（例：盗作防止）が重要な創造的領域（音楽など）における対話的・制約付き生成を可能にする。
• 謙虚さ：著者は明示的に、この仕事が新しい正規制約理論や一般の正規言語に対する BP を導入するものではないと述べている。新規性は厳密に可変次数拡張、すなわち既知の機構を正しい疎な状態抽象化に適用することにある。
• 限界：厳密性の主張は、確率源の定義に条件付けられる。生成時ポリシー（シングルトン回避など）がヒューリスティックに適用される場合、結果は厳密な制約付き生成ポリシーであり、必ずしも修正されていない固定次数源の厳密な事後分布ではない。

この研究は、制御された生成システムの設計空間の技術的分解として機能し、可変次数予測と有限ホライズン正規制御を組み合わせるための具体的、厳密、かつスケーラブルな解決策を提供する。