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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSymbolic RegressionSimilar Papers 제목 키워드 기반
A Dictionary of Closed-Form Kernel Mean Embeddings
Kernel mean embeddings -- integrals of a kernel with respect to a probability distribution -- are essential in Bayesian quadrature, but also widely used in other computational tools for numerical integration or for stati…
FormNumerical IntegrationAlgebraic Expression of Subjective Spatial and Temporal Patterns
Universal learning machine is a theory trying to study machine learning from mathematical point of view. The outside world is reflected inside an universal learning machine according to pattern of incoming data. This is …
BIG-bench Machine LearningA Finite Expression Method for Solving High-Dimensional Committor Problems
Transition path theory (TPT) is a mathematical framework for quantifying rare transition events between a pair of selected metastable states $A$ and $B$. Central to TPT is the committor function, which describes the prob…
Multiword Expressions at the Grammar-Lexicon Interface
In this talk, I will outline a range of challenges presented by multiword expressions in terms of (lexicalist) precision grammar engineering, and different strategies for accommodating those challenges, in an attempt to …
Semantic Parsing with Candidate Expressions for Knowledge Base Question Answering
Semantic parsers convert natural language to logical forms, which can be evaluated on knowledge bases (KBs) to produce denotations. Recent semantic parsers have been developed with sequence-to-sequence (seq2seq) pre-trai…
Knowledge Base Question AnsweringQuestion AnsweringSemantic Parsingvalid