A string-to-graph constructive alignment algorithm for discrete and probabilistic language modeling

A string-to-graph constructive alignment algorithm for discrete and probabilistic language modeling Andrei Shcherbakov Ekaterina Vylomova The University of Melbourne Parkville, Victoria 3010, Australia andreas@softwareengineer.pro evylomova@gmail.com Abstract We propose a novel algorithm of graph-to- string alignment that constructs automata from a sample of string sequences. While being a variant of global edit distance, the algorithm also employs graph construction operations in order to form an optimal alignment. It al- lows dynamic insertion of edges and nodes driven by optimization of the best string-to- graph alignment score. The algorithm may be used both to derive discrete non-deterministic acceptor (or a regular expression) and to build a probabilistic generative model of an input language. An outstanding ability to produce accurate approximate models from extremely sparse training sets constitutes the main advan- tage of the technique. 1 Introduction Tasks such as text generation or language mod- elling might require approximate string matching. Often the models are trained on a set of match- ing samples (sometimes augmented with mis- matching, or negative, samples). In most cases, they rely on extrinsic metrics (n-gram similarity (Kondrak, 2005), perplexity (Jelinek et al., 1977), Kolmogorov (Li and Vit´anyi, 2013) or cognitive (Rogers et al., 2013) complexities, Levenshtein distance (Levenshtein, 1966)). An objective func- tion may not directly correspond to any formally proven or intuitively observable reasonable goal. In current paper, we attempt to combine struc- ture awareness of graph-based models with sim- plicity of similarity-based approaches. We train a graph-based model that minimizes modified re- current edit distance1 between each training sam- ple and the path in the graph closest to it. As a graph-based model we propose to use a weighted non-deterministic finite state acceptor (WFSA) to 1Here “recurrent” means that a path may contain loops. enable a compact representation of learned se- quences as well as to allow alternations and rep- etitions of substrings. The approach we consider in the paper is essentially based on the hypoth- esis that sequences that are likely to appear in a language normally form dense clusters around some basic patterns. In other words, the sequences are characterized by relatively low edit distance to some cluster centroid. The proposed tech- nique handles both branching and looping of sub- sequences in a consistent way. As a result, pattern generalization may be carried out without any ex- tra pre- or post-processing.2 2 Architecture We first provide a set of positive (and, option- ally, negative) string samples in order to build a weighted acceptor (WFSA). The training pro- cedure runs as follows. Initially, the acceptor only contains unconnected start and finish (accept- ing) nodes. At each training iteration we com- pute the best possible alignments between the ac- ceptor and a given sample string using Smith– Waterman (Smith et al., 1981) alignment search procedure with the following major differences. First, it allows virtually any automaton edge (even non-existent ones) to be considered for alignment paths.3 In such a way, it enables new candidate edges that should be built in order to improve fit to a …

Content truncated to 500 words