论文标题
P（表达式|语法）：用概率无上下文语法得出代数表达的概率
P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar
论文作者
论文摘要
概率无上下文语法在机器学习和符号回归中用作生成模型的长期记录。当用于符号回归时，它们会产生代数表达式。我们将后者定义为通过语法得出的字符串的等效类别，并解决了计算给定语法的给定表达式的概率的问题。我们表明，这个问题通常是不确定的。然后，我们提出特定的语法来生成线性，多项式和有理表达式，其中存在用于计算给定表达的概率的算法。对于这些语法，我们设计了用于以任意精度计算确切概率和有效近似的算法。
Probabilistic context-free grammars have a long-term record of use as generative models in machine learning and symbolic regression. When used for symbolic regression, they generate algebraic expressions. We define the latter as equivalence classes of strings derived by grammar and address the problem of calculating the probability of deriving a given expression with a given grammar. We show that the problem is undecidable in general. We then present specific grammars for generating linear, polynomial, and rational expressions, where algorithms for calculating the probability of a given expression exist. For those grammars, we design algorithms for calculating the exact probability and efficient approximation with arbitrary precision.
