Markov Constraint as Large Language Model Surrogate
作者: Alexandre Bonlarron, Jean-Charles Régin
分类: cs.CL, cs.AI, cs.LG
发布日期: 2024-06-11
备注: To appear at The 33rd International Joint Conference on Artificial Intelligence, IJCAI-24 (in press)
期刊: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence Main Track. Pages 1844-1852. Year 2024
💡 一句话要点
提出NgramMarkov约束，利用大语言模型提升约束编程文本生成效率与质量。
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 约束编程 文本生成 大型语言模型 马尔可夫约束 n-gram模型
📋 核心要点
- 传统约束编程文本生成依赖最大似然估计，缺乏对文本流畅性和语义的有效建模。
- NgramMarkov利用大语言模型提供的n-gram概率分布，约束句子中n-gram概率乘积，提升生成质量。
- 实验表明，该方法能有效减少候选句子数量，提升计算效率，并能使用更小的n-gram解决实际问题。
📝 摘要（中文）
本文提出了一种马尔可夫约束的变体，名为NgramMarkov，专门用于约束编程(CP)中的文本生成。它使用一组n-gram（即n个词的序列），并结合由大型语言模型(LLM)给出的概率。该方法限制了一个句子中n-gram概率的乘积。该约束的传播器可以看作是ElementaryMarkov约束传播器的扩展，它结合了LLM的分布，而不是n-gram的最大似然估计。它使用滑动阈值，即拒绝局部概率过低的n-gram，以保证平衡的解。它还可以与“前瞻”方法结合使用，以消除那些不太可能在固定长度范围内产生可接受句子的n-gram。这个想法基于MDDMarkovProcess约束传播器，但没有显式地使用MDD（多值决策图）。实验结果表明，生成的文本的质量与LLM的困惑度函数相似。使用这种新约束可以显著减少生成的候选句子数量，提高计算速度，并允许使用更大的语料库或更小的n-gram。一个真实世界的问题首次使用4-gram而不是5-gram得到了解决。
🔬 方法详解
问题定义：现有的约束编程文本生成方法通常依赖于n-gram的最大似然估计，这种方法无法充分捕捉语言的复杂性和流畅性，导致生成的文本质量不高。此外，计算复杂度较高，难以处理大规模语料库和长文本生成任务。
核心思路：NgramMarkov的核心思路是将大型语言模型(LLM)的概率分布引入到约束编程的框架中，利用LLM对语言的理解能力来指导文本生成过程。通过约束句子中n-gram概率的乘积，保证生成的文本在LLM看来是合理的，从而提高文本的流畅性和语义连贯性。
技术框架：NgramMarkov约束作为约束编程求解器中的一个约束条件，与其他约束条件共同作用，指导文本生成过程。其主要模块包括：1) n-gram概率获取模块，从预训练的LLM中获取n-gram的概率分布；2) 概率乘积计算模块，计算句子中所有n-gram概率的乘积；3) 阈值判断模块，使用滑动阈值判断n-gram的局部概率是否过低，并进行剪枝；4) 前瞻模块，预测后续n-gram的概率，提前排除不太可能生成合理句子的候选词。
关键创新：NgramMarkov的关键创新在于将LLM的概率分布与约束编程相结合，利用LLM的语言建模能力来指导文本生成。与传统的基于最大似然估计的方法相比，NgramMarkov能够生成更流畅、更符合语义的文本。此外，滑动阈值和前瞻模块的设计进一步提高了算法的效率和生成质量。
关键设计：滑动阈值的设置是关键设计之一，它允许在保证整体概率的前提下，容忍一些局部概率较低的n-gram，从而避免生成过于保守的文本。前瞻模块通过预测后续n-gram的概率，提前排除不太可能生成合理句子的候选词，从而减少搜索空间。具体参数设置包括n-gram的大小、滑动阈值的范围、前瞻的长度等，这些参数需要根据具体的应用场景进行调整。
🖼️ 关键图片
📊 实验亮点
实验结果表明，NgramMarkov能够显著减少生成的候选句子数量，提高计算速度。与传统的基于最大似然估计的方法相比，NgramMarkov生成的文本质量与LLM的困惑度函数相似，表明其能够生成更流畅、更符合语义的文本。此外，该方法首次成功地使用4-gram而不是5-gram解决了实际问题，证明了其在处理大规模语料库和长文本生成任务方面的优势。
🎯 应用场景
该研究成果可应用于多种文本生成任务，如机器翻译、文本摘要、对话生成、代码生成等。通过结合约束编程的灵活性和大型语言模型的强大语言建模能力，可以生成更符合语法、语义和特定约束条件的文本，具有广泛的应用前景和实际价值。未来可进一步探索将该方法应用于更复杂的文本生成场景，并与其他约束条件相结合，实现更精细的文本控制。
📄 摘要（原文）
This paper presents NgramMarkov, a variant of the Markov constraints. It is dedicated to text generation in constraint programming (CP). It involves a set of n-grams (i.e., sequence of n words) associated with probabilities given by a large language model (LLM). It limits the product of the probabilities of the n-gram of a sentence. The propagator of this constraint can be seen as an extension of the ElementaryMarkov constraint propagator, incorporating the LLM distribution instead of the maximum likelihood estimation of n-grams. It uses a gliding threshold, i.e., it rejects n-grams whose local probabilities are too low, to guarantee balanced solutions. It can also be combined with a "look-ahead" approach to remove n-grams that are very unlikely to lead to acceptable sentences for a fixed-length horizon. This idea is based on the MDDMarkovProcess constraint propagator, but without explicitly using an MDD (Multi-Valued Decision Diagram). The experimental results show that the generated text is valued in a similar way to the LLM perplexity function. Using this new constraint dramatically reduces the number of candidate sentences produced, improves computation times, and allows larger corpora or smaller n-grams to be used. A real-world problem has been solved for the first time using 4-grams instead of 5-grams.