P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar

• URL: http://arxiv.org/abs/2212.00751v2
• Date: Fri, 2 Dec 2022 08:59:59 GMT
• Title: P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar
• Authors: Urh Primo\v{z}i\v{c} and Ljup\v{c}o Todorovski and Matej Petkovi\'c
• Abstract summary: We show that the problem of calculating the probability of deriving a given expression with a given grammar is undecidable in general. We then present specific grammars for generating linear, rational, and hyperbolic expressions. For those grammars, we design algorithms for calculating the exact probability and efficient approximation with arbitrary precision.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Distribution Semantics for Probabilistic Term Rewriting [0.0]
  We focus on term rewriting, a well-known computational formalism. We consider systems that combine traditional rewriting rules with probabilities. We show how to compute a set of "explanations" for a given reduction.
  arXiv  Detail & Related papers  (2024-10-19T12:00:13Z)
• A Heavy-Tailed Algebra for Probabilistic Programming [53.32246823168763]
  We propose a systematic approach for analyzing the tails of random variables. We show how this approach can be used during the static analysis (before drawing samples) pass of a probabilistic programming language compiler. Our empirical results confirm that inference algorithms that leverage our heavy-tailed algebra attain superior performance across a number of density modeling and variational inference tasks.
  arXiv  Detail & Related papers  (2023-06-15T16:37:36Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• Marginal Inference queries in Hidden Markov Models under context-free grammar constraints [0.348097307252416]
  We address the question of computing the likelihood of context-free grammars (CFGs) in Hidden Models (HMMs) We show that the problem is NP-Hard, even with the promise that CFG has a degree of ambiguity less than or equal to 2. We then propose a fully randomized approximation scheme to approximate the likelihood for the case of ambiguous CFGs.
  arXiv  Detail & Related papers  (2022-06-26T12:44:18Z)
• Proving Equivalence Between Complex Expressions Using Graph-to-Sequence Neural Models [0.0]
  We develop a graph-to-sequence neural network system for program equivalence. We extensively evaluate our system on a rich multi-type linear algebra expression language. Our machine learning system guarantees correctness for all true negatives, and ensures 0 false positive by design.
  arXiv  Detail & Related papers  (2021-06-01T20:45:42Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• Probabilistic Grammars for Equation Discovery [0.0]
  We propose the use of probabilistic context-free grammars in equation discovery. Probability grammars can be used to elegantly and flexibly formulate the parsimony principle.
  arXiv  Detail & Related papers  (2020-12-01T11:59:19Z)
• Learning of Structurally Unambiguous Probabilistic Grammars [7.347989843033034]
  We restrict attention to structurally unambiguous weighted context-free grammars (SUWCFG) We show that SUWCFG can be represented using co-linear multiplicity tree automata (CMTA), and provide a learning algorithm that learns CMTAs. We demonstrate the usefulness of our algorithm in learning PCFGs over genomic data.
  arXiv  Detail & Related papers  (2020-11-15T08:07:04Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• The data-driven physical-based equations discovery using evolutionary approach [77.34726150561087]
  We describe the algorithm for the mathematical equations discovery from the given observations data. The algorithm combines genetic programming with the sparse regression. It could be used for governing analytical equation discovery as well as for partial differential equations (PDE) discovery.
  arXiv  Detail & Related papers  (2020-04-03T17:21:57Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.