Given a context free language G over alphabet Σ and a string s ∈ Σ * , the language edit distance problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert s into a valid member of the language L(G). The well-known dynamic programming algorithm solves this problem in O(n 3 ) time (ignoring grammar size) where n is the string length [Aho, Peterson 1972 , Myers 1985. Despite its numerous applications, to date there exists no algorithm that computes the exact or approximate language edit distance problem in true subcubic time. In this paper we give the first such algorithm that computes language edit distance almost optimally. For any arbitrary > 0, our algorithm runs inÕ( n ω poly( ) ) time and returns an estimate within a multiplicative approximation factor of (1 + ) with high probability, where ω is the exponent of ordinary matrix multiplication of n dimensional square matrices. It also computes the actual edits required. We further solve the local alignment problem; for all substrings of s, we can estimate their language edit distance within (1 ± ) factor inÕ( n ω poly( ) ) time with high probability. Next, we design the very first subcubic (Õ(n ω )) algorithm that given an arbitrary stochastic context free grammar, and a string returns a nearly-optimal maximum likelihood parsing of that string. Stochastic context free grammars significantly generalize hidden Markov models; they lie at the foundation of statistical natural language processing, and have found widespread applications in many other fields. To complement our upper bound result, we show that exact computation of maximum likelihood parsing of stochastic grammars or language edit distance in true subcubic time will imply a truly subcubic algorithm for all-pairs shortest paths, a long-standing open question. This will result in a breakthrough for a large range of problems in graphs and matrices due to subcubic equivalence. By a known lower bound result [Lee 2002] , and a recent development [Abboud et al. 2015] even the much simpler problem of parsing a context free grammar requires Ω(n ω ) time. Therefore any nontrivial multiplicative approximation algorithms for either of the two problems in time o(n ω ) are unlikely to exist. Given a model for data semantics and structures, estimating how well a dataset fits the model is a core question in large-scale data analysis. Formal languages (e.g., regular language, context free language) provide a generic technique for data modeling. The deviation from a model is measured by the least changes required in data to perfectly fit the model. Aho and Peterson studied this basic question more than forty years back to design errorcorrecting parsers for programming languages. Given a context free grammar (CFG) G over alphabet Σ and a string s ∈ Σ * , they proposed the language edit distance problem, which determines the fewest number of edits (insertions, deletions and substitutions) along with an edit script to convert s into a valid member of L(G). Due to its fundamental nature, the language edit distance problem has found many applications in compiler optimization (error-correcting parser [4] Often it is natural to consider a probabilistic generative model, and ask for the most probable derivation/explanation of the observed data according to the model. The stochastic context free grammar (SCFG) model is an example of that. It associates a conditional probability to each production rule of a CFG (see definition in Section I-A) which reflects the likelihood of applying it to generate members of the language. SCFGs significantly generalize hidden Markov models, and several stochastic processes such as Latent Dirichlet Allocation [20] and Galton-Watson branching process [28] . They lie at the foundation of statistical natural language processing, and have found widespread applications as a rich framework for modeling complex phenomena [14] , [19] , [40] , [50] . The most probable
In a recent paper REF , Saha showed that LED can be solved in O( n ω poly( ) ) time if we allow to approximate the exact edit distance by a (1 + )-factor.
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science