論文の概要: Can Continuous-Time Diffusion Models Generate and Solve Globally Constrained Discrete Problems? A Study on Sudoku

• arxiv url: http://arxiv.org/abs/2601.20363v1
• Date: Wed, 28 Jan 2026 08:26:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.840298
• Title: Can Continuous-Time Diffusion Models Generate and Solve Globally Constrained Discrete Problems? A Study on Sudoku
• Title（参考訳）: 連続時間拡散モデルによる離散問題の生成と解法は可能か?
• Authors: Mariia Drozdova,
• Abstract要約: 完備なSudoku格子を制御されたテストベッドとして使用し、連続緩和空間のサブセットとして扱う。 本研究では, スコアベースサンプリングが連続時間法の中で最も信頼性が高く, DDPM方式の祖先サンプリングが総合的に最も有効であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can standard continuous-time generative models represent distributions whose support is an extremely sparse, globally constrained discrete set? We study this question using completed Sudoku grids as a controlled testbed, treating them as a subset of a continuous relaxation space. We train flow-matching and score-based models along a Gaussian probability path and compare deterministic (ODE) sampling, stochastic (SDE) sampling, and DDPM-style discretizations derived from the same continuous-time training. Unconditionally, stochastic sampling substantially outperforms deterministic flows; score-based samplers are the most reliable among continuous-time methods, and DDPM-style ancestral sampling achieves the highest validity overall. We further show that the same models can be repurposed for guided generation: by repeatedly sampling completions under clamped clues and stopping when constraints are satisfied, the model acts as a probabilistic Sudoku solver. Although far less sample-efficient than classical solvers and discrete-geometry-aware diffusion methods, these experiments demonstrate that classic diffusion/flow formulations can assign non-zero probability mass to globally constrained combinatorial structures and can be used for constraint satisfaction via stochastic search.
• Abstract（参考訳）: 標準連続時間生成モデルは、非常にスパースで大域的に制約された離散集合である分布を表すことができるか? 本研究では, 完了スドク格子を制御されたテストベッドとして利用し, 連続緩和空間のサブセットとして扱う。 我々はガウス確率経路に沿ってフローマッチングとスコアベースモデルを訓練し、決定論的(ODE)サンプリング、確率的(SDE)サンプリング、および同じ連続時間トレーニングに由来するDDPMスタイルの離散化を比較した。 非条件で、確率的サンプリングは決定論的フローを著しく上回り、スコアベースサンプリングは連続時間法の中で最も信頼性が高く、DDPMスタイルの祖先サンプリングは全体として最も有効である。 さらに、同じモデルをガイド生成のために再利用できることを示し、クランプした手がかりの下で繰り返し完了をサンプリングし、制約を満たすと停止することにより、確率的スドク解法として機能する。 これらの実験は、古典的解法や離散幾何学的拡散法よりもはるかにサンプル効率が低いが、古典的拡散/フローの定式化により、非ゼロ確率質量を全世界的に制約された組合せ構造に割り当てることができ、確率探索による制約満足度に利用できることを示した。

関連論文リスト

• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  一般のスコアミスマッチ拡散サンプリング器に対する明示的な次元依存性を持つ最初の性能保証を示す。 その結果, スコアミスマッチは, 目標分布とサンプリング分布の分布バイアスとなり, 目標分布とトレーニング分布の累積ミスマッチに比例することがわかった。 この結果は、測定ノイズに関係なく、任意の条件モデルに対するゼロショット条件付きサンプリングに直接適用することができる。
  論文  参考訳（メタデータ） (2024-10-17T16:42:12Z)
• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  本研究では, ベイズ条件付けを行い, 制約条件下でサンプルを描画する, トラクタブルな確率的手法を提案する。 提案手法はシーケンス全体を考慮し,現行のグリード法よりも大域的に最適に制約された生成を導出する。 提案手法は, 有害な世代からモデル出力を分離し, 脱毒化に対する同様のアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-17T00:49:53Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。 本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。 我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
  論文  参考訳（メタデータ） (2024-10-03T09:07:13Z)
• Stable generative modeling using Schrödinger bridges [0.22499166814992438]
  本稿では,Schr"odinger BridgesとLangevin dynamicsを組み合わせた生成モデルを提案する。 我々のフレームワークは自然に条件付きサンプルを生成し、ベイズ推論問題に拡張することができる。
  論文  参考訳（メタデータ） (2024-01-09T06:15:45Z)
• Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
  連続時間マルコフ連鎖を介して逆過程が認知されるマルコフジャンププロセスを導入することにより、拡散モデルを離散変数に拡張する。 条件境界分布の単純なマッチングにより、偏りのない推定器が得られることを示す。 提案手法の有効性を,合成および実世界の音楽と画像のベンチマークで示す。
  論文  参考訳（メタデータ） (2022-11-30T05:33:29Z)

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

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