通过 HMM 生成可处理的 NFA 约束语言

约束生成旨在从以硬约束为条件的语言模型 (LM) 中进行采样。现有的非确定性有限自动机 (NFA) 约束的约束生成技术要么会扭曲分布，要么会牺牲效率。理论上，此任务简化为计算 NFA (#NFA) 接受的长度 $n$ 序列，并且确切的 #NFA 问题是 #P-complete。最近的工作表明#NFA 承认完全多项式随机近似方案（FPRAS）。受这一结果的启发，我们提出了 NFA-LM，这是一种用于 NFA 约束生成的多项式时间引擎，在温和假设下具有理论保证。实验表明，NFA-LM 可以有效地生成高质量的输出，且近似误差理论上有界。