Algorithms for Weighted Pushdown Automata

• URL: http://arxiv.org/abs/2210.06884v1
• Date: Thu, 13 Oct 2022 10:21:31 GMT
• Title: Algorithms for Weighted Pushdown Automata
• Authors: Alexandra Butoi, Brian DuSell, Tim Vieira, Ryan Cotterell, David Chiang
• Abstract summary: Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks. We develop novel algorithms that operate directly on WPDAs.
• Score: 118.67634716230025
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency parsing. As most existing dynamic programming algorithms are designed for context-free grammars (CFGs), algorithms for PDAs often resort to a PDA-to-CFG conversion. In this paper, we develop novel algorithms that operate directly on WPDAs. Our algorithms are inspired by Lang's algorithm, but use a more general definition of pushdown automaton and either reduce the space requirements by a factor of $|\Gamma|$ (the size of the stack alphabet) or reduce the runtime by a factor of more than $|Q|$ (the number of states). When run on the same class of PDAs as Lang's algorithm, our algorithm is both more space-efficient by a factor of $|\Gamma|$ and more time-efficient by a factor of $|Q| \cdot |\Gamma|$.

Related papers

• A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
  Most popular algorithms for active learning express their performance in terms of a parameter called the disagreement coefficient. We get an algorithm that is competitive with the optimal algorithm for any binary hypothesis class $H$ and distribution $D_X$ over $X$. It is NP-hard to do better than our algorithm's $O(log |H|)$ overhead in general.
  arXiv  Detail & Related papers  (2023-10-28T19:01:16Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. We propose an accelerated primal-dual mirror descent algorithm with variance reduction. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $widetildeO(n2/epsilon)$ for solving OT.
  arXiv  Detail & Related papers  (2023-01-23T19:13:25Z)
• Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
  We introduce a new algorithm for numerical composition of privacy random variables. Our algorithm achieves a running time and memory usage of $mathrmpolylog(k)$ for the task of self-composing a mechanism.
  arXiv  Detail & Related papers  (2022-07-10T04:25:37Z)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  Exact algorithms for computing Optimal Transport can be slow. We introduce a new and very simple approach to find an $varepsilon$approximation of the OT distance. Our algorithm achieves a near-optimal execution time of $O(n2/varepsilon2)$ for computing OT distance.
  arXiv  Detail & Related papers  (2022-03-07T21:40:14Z)
• Private Frequency Estimation via Projective Geometry [47.112770141205864]
  We propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of $k$ and with $n$ users, our $varepsilon$-LDP algorithm has communication cost $lceillogkrceil bits in the private coin setting and $varepsilonlog e + O(1)$ in the public coin setting. In many parameter settings used in practice this is a significant improvement over the O(n+k2)$optimal cost that is achieved by the recent PI-
  arXiv  Detail & Related papers  (2022-03-01T02:49:55Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)

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.