Learning probability distributions generated by finite-state machines

Learning probability distributions generated by finite-state machines Jorge Castro and Ricard Gavald` a Abstract We review methods for inference of probability distributions generated by probabilistic automata and related models for sequence generation. We focus on methods that can be proved to learn in the inference in the limit and PAC formal models. The methods we review are state merging and state splitting methods for probabilistic deterministic automata and the recently developed spectral method for nondeterministic probabilistic automata. In both cases, we derive them from a high-level algorithm described in terms of the Hankel matrix of the distribution to be learned, given as an oracle, and then describing how to adapt that algorithm to account for the error introduced by a finite sample. 1 Introduction Finite state machines in their many variants are acceptedly one of the most useful and used modeling formalisms for sequential processes. One of the reasons is their versatility: They may be deterministic, nondeterministic, or probabilistic, they may have observable or hidden states, and they may be acceptors, transducers, or generators. Additionally, many algorithmic problems (determinization, minimization, equivalence, set-theoretic or linear-algebraic operations, etc.) are often computationally feasible for these models. Learning from samples or observations of their behavior is one of the most important associated problems, both theoretically and practically, since good methods for the task offer a competitive alternative to expensive modeling by experts. It has been intensely studied in various communities, and particularly in the grammatical inference one. Here we concentrate on learning probabilistic finite automata that generate probabilistic distributions over strings, where more precisely the task is to Jorge Castro and Ricard Gavald` a LARCA Research Group, Universitat Polit` ecnica de Catalunya - BarcelonaTech, Barcelona, Spain, e-mail: {castro,gavalda}@lsi.upc.edu 1 The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-48395-4_5 2 Jorge Castro and Ricard Gavald` a come up with a device generating a similar distribution. We focus on two formal models of learning (the identification in the limit paradigm and the PAC learning models) rather than on heuristics, practical issues, and applications. The main goal of the chapter is to survey known results and to connect the research on merging/splitting methods, mainly by the grammatical inference community, with the recently proposed methods collectively known as “spectral methods”. The latter have emerged from several communities who present them in very different lights, for example as instances of the method of moments, of principal component analysis methods, of tensor-based subspace learning, etc. Our goal is to present it as emerging as a relatively natural extension of the work on automata induction that starts with Angluin’s L?method [3] for DFA and continues with the work by Beimel et al. [11] on learning multiplicity automata from queries. The Hankel matrix representation of functions and the generalization from probabilistic automata to weighted automata are essential ideas here. The chapter is organized as follows. Section 2 presents the preliminaries on languages, probability, finite-state machines, and learning models. Section 3 surveys the existing results on identification-in-the-limit and PAC learning. We discuss the evidence pointing to the hardness of PAC learning probabilistic automata when the only measures of complexity of the target machine are the number of states and alphabet size. We then indicate how PAC learning becomes feasible if other measures of complexity are taken into account. Section 4 introduces the two main notions on which we base the rest of our exposition: the Hankel matrix of a function from strings to real values, and weighted automata, which generalize DFA and probabilistic automata. We present three results that link automata size and properties of the Hankel matrix: the well-known Myhil-Nerode theorem for DFA; a theorem originally due to Sch¨ utzenberger and rediscovered several times linking weighted automata size and rank (in the linear algebraic sense) of the Hankel matrix; and a similar characterization of the size of deterministic weighted automata in terms of the Hankel matrix, which we have not seen stated so far - although it may be known. Section 5 presents a high-level algorithm for learning probabilistic deterministic finite automata using the Hankel matrix which distills the reasoning behind many of the state merging/splitting methods described in the literature. We then present (variants of) the ALERGIA method [13, 14] and of the method by Clark and Thollard [16] building on this formulation; additionally, we describe them using a recently introduced notion of statistical query learning for distributions, which we believe makes for a clearer presentation. Section 6, in analogy with the previous one, presents a high-level algorithm for learning weighted automata using the Hankel matrix. We then derive a formulation of the spectral method as a way of dealing with the effect of finite size samples in that high-level algorithm. We also discuss a few optimizations and extensions in recent woks in Section 6.3. Finally, Section 7 mentions a few open questions for further research. In an Appendix we describe the well-known Baum-Welch heuristics for learning HMM. Learning probability distributions generated by finite-state machines 3 Even though it does not fit into the formal models we discuss, the comparison with the other methods presented is interesting. Since the literature in this topic is large, we have surely omitted many relevant references, either involuntarily or because they were out of our focus (rigorous results in formal models of learning). For example, recent works using Bayesian approaches to learning finite automata have not been covered because, while promising, seem still far from providing formal guarantees. We have also omitted most references to probability smoothing, a most essential ingredient in any implementation of such methods; information on smoothing for automata inference can be found in [16, 23, 36, 42]. The reader is referred to the surveys by Vidal et al. [45, 46], Dupont et al. [24], and the book by de la Higuera [18] for background on the models and results by the grammatical inference community. A good source of information about spectral learning of automata is the thesis of B. Balle [17] and the paper [9]. The 2012 and 2013 editions of the NIPS conference hosted workshops dedicated to spectral learning, including but more general than automata learning. 2 Preliminaries We denote by Σ?the set of all strings over a finite alphabet Σ. Elements of Σ?will be called strings or words. Given x,y∈Σ?we will write xy to denote the concatenation of both strings. We use λto denote the empty string which satisfies λx=xλ=x for all x∈Σ?. The length of x∈Σ?is denoted by |x|. The empty string is the only string with |λ|=0. We denote by Σtthe set of strings of length t. A prefix of a string x∈Σ?is a string usuch that there exists another string vsuch that x=uv. String vis asuffix of x. Hence e.g. uΣ?is the set of all strings having uas a prefix. A subset X of Σ?is prefix-free whenever for all x∈X, if yis a prefix of xand y∈Xthen y=x. Several measures of divergence between probability distributions are considered. Let D1and D2be distributions over Σ?. The Kullback–Leibler (KL) divergence or relative entropy is defined as KL(D1kD2) = ∑ x∈Σ? D1(x)log D1(x) D2(x), where the logarithm is taken to base 2 and by definition log(0/0) = 0. The total variation distance is L1(D1,D2) = ∑x∈Σ?|D1(x)−D2(x)|. The supremum distance is L∞(D1,D2) = maxx∈Σ?|D1(x)−D2(x)|. While KL is neither symmetric nor satisfies the triangle inequality, measures L1and L∞are true distances. We recall Pinsker’s inequality, L1≤√2KL, bounding the total variation distance in terms of the relative entropy. Thus, as L1obviously upperbounds L∞, the relative entropy is, up to a factor, the most sensitive divergence measure among the ones considered here to distribution perturbations, and convergence criteria based on the KL value are most demanding. 4 Jorge Castro and Ricard Gavald` a Frequently, machine descriptions are provided in terms of vectors and matrices of real numbers and computations are defined by matrix products. We use square brackets to denote an specific component of a vector or matrix. For instance, component jof vector αis α[j]. Row xof a matrix Tis denoted by T[x,:]and column y is T[:,y]. Vectors are always assumed to be columns. If αis a vector, a row vector αT is obtained by transposing α. 2.1 Learning Distributions in the PAC Framework We introduce the PAC model for learning distributions, an adaptation of Valiant’s PAC model for concept (function) learning [44]. Let Dbe a class of distributions over some fixed set X. Assume Dis equipped with some measure of complexity assigning a positive number |D|to any D∈D. We say that an algorithm A PAC learns a class of distributions Dusing S(·)examples and time T(·)if, for all 0 <ε,δ<1 and D∈D, with probability at least 1 −δ, the algorithm reads S(1/ε,1/δ,|D|)examples drawn i.i.d. from Dand after T(1/ε,1/δ,|D|)steps outputs a hypothesis b D such that L1(D,b D)≤ε. The probability is over the sample used by Aand any internal randomization. As usual, PAC learners are considered efficient if the functions S(·)and T(·)are polynomial in all of their parameters. Sometimes we will consider the relative entropy instead of the variation distance as a measure of divergence, which creates a different learning problem. Which specific measure we are considering in each PAC result will be clear from the context. Although the majority of PAC statements in the chapter are provided for L1all of them can be also shown for the KL divergence measure, at the cost of longer proofs. As the main proof ideas are the same for both measures, we have chosen mainly L1 versions for simplicity. Concerning the measure of complexity of distributions, standard practice is to fix a formalism for representing distributions, such as finite-state machines, and then consider the smallest, in some sense, representation of a given distribution in that formalism (usually exactly, but possibly approximately). In the case of finite-state machines, a seemingly reasonable measure of “size” is the number states times the number of alphabet symbols, as that roughly measures the size of the transition table, hence of the automaton description. A first objection is that transition tables contain numbers, so this notion does not match well the more customary notion of bit-length complexity. One could refine the measure by assuming rational probabilities (who have reasonable bit-length complexity measures) or by truncating the probabilities to a number of digits that does not distort the probability distribution by more than about ε. We will see however that number of states and symbols alone do not fully determine the learning complexity of probabilistic finite-state machines, and that the bit-length of the probabilities seems irrelevant. This will motivate the (non-standard) introduction of further complexity parameters, some defined in terms of the finite-state machine, and some in terms of the distribution itself. Learning probability distributions generated by finite-state machines 5 2.2 Identification in the Limit Paradigm An alternative framework for learning distributions is the identification in the limit paradigm, originally introduced by Gold [27] for the setting of language learning. Later, the model was adapted in [19] to the learning distributions scenario. Basically, the model demands that with probability 1, given an infinite sample from the target, the learning algorithm with input the first mexamples of the sample exactly identifies the target distribution when mis large enough. We consider here a slightly weaker definition, mainly because we consider state machines defined on real numbers instead of rational ones as in [19]. As before, let Dbe a class of distributions. We say that an algorithm A identifies in the limit a class of distributions Dif for all 0 <ε<1 and D∈D, given an infinite sample x1,x2,... of D 1. With probability 1, there exists m0(ε)such that for all m≥m0(ε)algorithm A with input x1,...,xmoutputs a hypothesis b Dsuch that L1(D,b D)≤ε. 2. Aruns in polynomial time in its input size. It is easy to check that any PAC learning algorithm also achieves identification in the limit: Assume that identification in the limit does not occur. We have that with probability δ>0, there are arbitrarily large values msuch that Awith input x1,...xm outputs a hypothesis b Dsuch that L1(D,b D)>ε. This implies that PAC learning does not hold. 2.3 Probabilistic Automata Aprobabilistic finite automaton (pfa) of size nis a tuple hQ,Σ,τ,α0,α∞iwhere Qis a set of nstates, Σis a finite alphabet, τ:Q×Σ×Q→[0,1]is the transition probability function and α0and α∞are respectively [0,1]nvectors of initial and final probabilities. We require that ∑i∈Qα0[i] = 1 and, for every state i, α∞[i] + ∑a∈Σ,j∈Qτ(i,a,j) = 1. States isuch that α0[i]>0 (α∞[i]>0) are initial (final) sates. To each pfa Dcorresponds an underlying non-deterministic finite automaton (nfa) called the support of D, defined as hQ,Σ,δ,QI,QFiwhere QIand QF are respectively the set of initial and final states, and transition function δis defined as δ(i,a) = {j|τ(i,a,j)>0}. The transition probability function of a pfa Dcan be extended to strings in Σ?. Given x∈Σ?, we define τ(i,xa,j) = ∑k∈Qτ(i,x,k)τ(k,a,j)and τ(i,λ,j) = 1 if i=jand 0 otherwise. A probability mass can be assigned to words in Σdefining: D(x) = ∑ i∈QI,j∈QF α0[i]τ(i,x,j)α∞[j]. Defining transition matrices Tafor each a∈Σas Ta[i,j] = τ(i,a,j)and provided x=x1...xmwhere xt∈Σfor t=1...m, a more convenient expression in terms of 6 Jorge Castro and Ricard Gavald` a matrix products for the probability mass of xis D(x) = αT 0Tx1···Txmα∞ that we write in short by αT 0Txα∞. Note that transition matrices are square |Q|×|Q| and define the transition function. So, an alternative tuple description for a pfa Din terms of transition matrices is hΣ,{Ta}a∈Σ,α0,α∞i. The probability mass induced by Ddefines a semi-distribution in Σ?: it satisfies 0≤∑x∈Σ?D(x)≤1. Whenever from every state ithere is non-zero probability of reaching a final state, Ddefines a true probability distribution, i.e. ∑x∈Σ?D(x) = 1. In the rest of the chapter we will consider only pfas defining true probability functions. More generally, every state iof a pfa Ddefines a probability distribution Di(x) = γT iTxα∞where γiis the i-indicator vector γi[j] = 1 if i=jand 0 otherwise. We have D(x) = ∑i∈Qα0[i]Di[x]. 2.4 Probabilistic Deterministic Automata and Distinguishability Aprobabilistic deterministic finite automaton (pdfa for short) is a pfa whose support is a deterministic finite automaton (dfa). We note that for a pdfa we can assume without loss of generality — in short, w.l.o.g.— that the initial probability vector αT 0is (1,0,0,. . . ,0) and each row of each transition matrix Tahas at most one nonzero component. It is known [24] that pfa cannot exactly compute all probability distributions over Σ?, and that there are pfa computing distributions that cannot be exactly computed by any pdfa. That is, pfa are strictly more expressive than pdfa. The following parameter will be useful to measure the complexity of learning a particular pdfa. It appears in [16] as defined here, although a similar idea is implicit in [36]. Definition 1. We say that distributions D1and D2are µ-distinguishable if µ≤ L∞(D1,D2). A pdfa Dis µ-distinguishable when for each pair of states iand j their corresponding distributions Diand Djare µ-distinguishable. The distinguishability of a pdfa is defined as the supremum over all µfor which the pdfa is µdistinguishable. The distinguishability parameter can sometimes be exponentially small in the number of states. There exists reasonable evidence suggesting that polynomially learnability of pdfa in the number of states alone may not be achievable [30, 41]. However, PAC results have been obtained [16] when the inverse of distinguishability of the target is also considered, as we will see. We will also discuss parameters that play similar roles in pfa learning. Learning probability distributions generated by finite-state machines 7 2.5 Hidden Markov Models Hidden Markov models HMM are representations of choice for Markovian stochastic processes whose latent states are non-observable but their effects are. Visible effects are the observations arising from the process. There are several formal definitions for HMM in the literature, but all of them are equivalent up to a polynomially transformation [24]. Often, observations in HMM are associated to states rather than transitions but for simplicity, we choose a definition closest to that of pfa. An HMM is a tuple hQ,Σ,τ,α0iwhere the four parameters have the same meaning that in the pfa definition. For any state i, it always holds ∑a∈Σ,j∈Qτ(i,a,j) = 1. Thus, one can see a HMM as a pfa having no stopping probabilities, i.e. as an infinite duration process. Transition probability matrices {Ta}a∈Σ are defined as in the pfa case, i. e. Ta[i,j] = τ(i,a,j). An HMM defines, for each integer t≥0, a probability distribution on Σt. The probability mass assigned to string x=x1...xtis αT 0Tx1···Txt1where 1is the allones vector. This is the probability that the machine generates an infinite string of observations whose length-tprefix is x. 2.6 Weighted Automata Weighted automata (wa) are the most general class of finite state machines we consider. They encompass all the models we have introduced before. A weighted automaton Tover Σwith nstates is a tuple hΣ,{Ta}a∈Σ,α0,α∞iwhere Ta∈Rn×n and α0and α∞are vectors in Rn. To each weighted automaton Tcorresponds a real-valued function defined on Σ?. Given x=x1...xm∈Σ?: fT(x) = αT 0Tx1···Txmα∞=αT 0Txα∞. We note that wa can be defined over semirings other than the real numbers, but whether wa are learnable (in any particular learning model) strongly depends on the semiring. For example, the high-level algorithms for real-valued wa that we present in Sections 5.1 and 6.1 work in fact on any field, including finite fields. On the other hand, wa over the boolean semiring (∨,∧,0,1)are at least as expressive as DNF formulas, whose learnability in the PAC [44] or query [3] concept learning models are major open problems in computational learning theory. A weighted automaton is deterministic (in short, a dwa) when rows of its transition matrices have at most one nonzero value and its initial vector αT 0is (1,0,...,0). 8 Jorge Castro and Ricard Gavald` a 3 A Panoramic View of Known Results Around 1970, Baum and Welch described a practical heuristic for learning Hidden Markov Models generating infinite sequences; their properties were studied in [10], where it was shown to perform hill-climbing with respect to maximum likelihood. As such, it cannot be shown to learn in either of the two models we have presented (identification in the limit and PAC) but, even today, it is possibly the most used method in practice. Although it is described in many sources, we state it in our formalism in the Appendix for completeness and for comparison to the other methods we review. Rudich [37] was, to our knowledge, the first to prove that Hidden Markov Models generating infinite sequences are identifiable in the limit. His method seems far from the PAC criterion in the sense that not only there are no bounds on the the error on a finite sample, but even processing each observation involves cycling over all exponentially many possible state structures, hence is very inefficient. A decade later, Carrasco and Oncina [13, 14] described ALERGIA, a practical method for learning pdfa generating distributions on Σ?. We will describe a slight variant of ALERGIA which we name the Red-Blue algorithm in Section 5.2.1. ALERGIA has been highly influential in the grammatical inference community. Some of the (many) works that build on the ideas of ALERGIA to learn pdfa are Section [20, 43, 31]. All these algorithms are efficient in the sense that they work in time polynomial in the size of the sample, although no bounds are given on the number of samples required to reach convergence up to some ε. Apparently independently, [39] proposes the Causal State Splitting Reconstruction algorithm (CSSR) for inferring the structure of deterministic Hidden Markov Models. Although the underlying ideas are similar, their work differs in that the input consists of a single biinfinite string, not a sample of finite strings. Still in the paradigm of identification in the limit, we mention the work by Denis and Esposito [21] who learn Residual Automata, a class strictly more powerful than pdfa but less than general pfa. If we move to the PAC paradigm, the first result to mention on learning pfa is that of Abe and Warmuth [1], who show that they are PAC learnable in polynomial space. The method essentially iterates over all (exponentially many) state structures with a hypothesized number of states n, fitting probabilities in each according to the sample, and producing the one which assigns maximum likelihood to the sample. It can be shown that, for a sample of size polynomial in n,|Σ|, 1/ε, and log(1/δ), this hypothesis satisfies the PAC criterion of learning. The difficulty of learning pfa is thus computation, not information. The same paper [1] shows that it is NP-complete to PAC learn pfa when the size of the alphabet Σis unbounded, which in effect implies that all methods will require time exponential in |Σ|. Kearns et al. [30] showed that the problem may be hard even for 2-letter alphabets. They show that learning pdfa generalizes the noisy parity learning problem, which has received a fair amount of attention and for which all algorithms known so far take exponential time. Furthermore, only a small set of simple probabilities are required in the reduction (say, {i/8|i=0...8}). Terwijn Learning probability distributions generated by finite-state machines 9 [41] showed that indeed the problems of learning HMM and acyclic pdfa are hard under plausible cryptographic assumptions. The previous results paint a rather discouraging panorama with respect to PAC learning of pfa and even pdfa. But note that, critically, these negative results all imply the hardness when the complexity of the target distribution (hence, the polynomiality of the PAC model) is defined to be number of states times alphabet size for the smallest machine generating it. A line of research starting in [36] aims at giving positive results by using other measures of complexity, in particular taking other parameters of the distribution that may not even be directly observable from a generating machine. Alternatively, one can view this line of research as designing sensible algorithms for learning pdfa/pfa, then analyzing their running time in search of the relevant features of the target distribution, instead of deciding, a priori, what the bounds on the running time should look like. To be precise, Ron et al. [36] gave an algorithm for learning acyclic pdfa that can be shown to PAC learn with respect to the KL-divergence in time and sample size polynomial in the inverse of the distinguishability of the target machine, besides the usual parameters. Later, Clark and Thollard [16] extended the result to cyclic automata; they introduce an additional dependence on the expected length of the strings in the distribution, L. We will describe the Clark-Thollard algorithm in detail in Section 5.2.2, under the name of Safe-Candidate algorithm. Extensions and variants of the Clark-Thollard algorithm include the following. Palmer and Goldberg [35] show that the dependence on Lcan be removed if learning only w.r.t. the L1distance is required. In another direction, Guttman et al. [28] show that PAC learning is still possible in terms of L2-distinguishability, which is more restrictive that the L∞-distinguishability we use here. The variations presented in [26] and [15], while retaining the PAC guarantees, aim at being more efficient in practice. In [5] the algorithm is extended to machines whose transitions have random durations, determined by associated probability distribution that must be learned too. In [7], the algorithm is transported to the so-called data stream paradigm, where data (strings) arrive in sequence and the algorithm is required to use sublinear memory and low time per item. In substantial breakthroughs, Mossel and Roch [33], Denis et al. [22], Hsu et al. [29], and Bailly et al. [4] gave algorithms having formal proofs of PAC learning the full class of pfa. The sample size and running times of the algorithms depend polynomially in the inverse of some quantity of a spectral flavor associated to the Hankel matrix of the target distribution. This is, for example, the determinant in [33] and the inverse of its n-th singular value in [29]. Denis et al. [22] do not explicitly state a PAC learning result, but in our opinion they refrain from doing so only because they lack a proper name for the feature of the distribution that determines their algorithms’ running time. 16 Jorge Castro and Ricard Gavald` a Both query types can be easily simulated with high probability with a sample of distribution D. The following result holds. Proposition 1. For any probability distribution D, a statistical query SQD(X,α) can be simulated using O(α−2log(1/δ)) examples from D. A DIFFD ∞(X,Y,α,β) query can be solved using ˜ O(α−2β−2log(1/δ)) examples. In both cases, the error probability is less than δ. 5.2.1 The Red-Blue algorithm State merging algorithms were initially proposed for the regular language inference problem. Gold [27] had shown that regular languages are identifiable in the limit from positive and negative data, but consistency with the input sample was not guaranteed when the sample does not contain some crucial information —the so called characteristic set—. Oncina and Garc´ ıa [34] proposed a state merging algorithm for inferring regular languages that overcomes this drawback. The algorithm always returns a dfa that is data consistent and, provided a complete presentation is given, achieves identification in the limit. Carrasco and Oncina in [14] adapted the dfa state merging learning algorithm to the stochastic setting. The new algorithm, so-called ALERGIA, was shown to identify in the limit any pdfa provided stochastic examples of the target are given. We present here a version of ALERGIA in the query model we have just introduce that considers statistical and L∞-queries. We rename this version as the Red-Blue algorithm. Given an integer mas input, Red-Blue starts by building a prefix tree acceptor representing significant prefixes by calling the Pta function on parameters mand λ, see Figures 2 and 3. On these values, Pta returns a prefix tree dfa whose leaves at level jcorrespond to prefixes of probability at least 2j/m. Thus, the resulting tree dfa has depth at most dlogme. In order to decide whether a prefix has enough probability to be represented, Pta makes statistical queries. Once the the tree acceptor is built, Red-Blue colors the initial state as red and its direct descendants as blue, leaving other states uncolored, and starts merging compatible states. Two states are considered merge-compatible when a call to the DIFFD ∞oracle returns a numerical value not exceeding 1/m, meaning that there is not strong evidence that they define different distributions. Specifically, we define for each state qa prefix free subset H[q]consisting of words xsuch that τ(q0,x) = qand for any prefix yof xit holds x=yor τ(q0,y)6=q. Asking the query DIFFD ∞(H[q1],H[q2],α,α)we get information about how different the distributions defined by states q1and q2are. The merging flow proceeds as follows. For an arbitrarily chosen blue state, either there is a red state that is merge-compatible with it or no red state is. In the first case, both states are merged and the result colored red. This may introduce nondeterministic choices, which are eliminated by further merging in the merge procedure. Note that every merge always involves a blue state. On the other hand, if there is no merge-compatible red state for this blue state, it is promoted to red and new blue Learning probability distributions generated by finite-state machines 17 input: integer m output: pdfa H algorithm Red-Blue H←Pta(m,λ) Red ←{qλ}; Blue ←{τ(qλ,σ),σ∈Σ} Let α←1/m while Blue 6=/0 pick some state b∈Blue if there is r∈Red with DIFFD ∞(H[r],H[b],α,α)≤α H←Merge(r,b,H) else Red ←Red ∪{b} Blue ←Blue −{b}∪{τ(b,σ)|σ∈Σand τ(b,σ)is uncolored} for q∈H γ(q,ξ)←SQD(H[q],α)/SQD(H[q]Σ?,α) for σ∈Σsuch that τ(q,σ)is defined γ(q,σ)←SQD(H[q]σΣ?,α)/SQD(H[q]Σ?,α) return H Fig. 2 Red-Blue algorithm input: integer mand string w∈Σ? output: tree dfa H algorithm Pta Set a initial state qwof H Let α←1/m for each σ∈Σ if SQD(wσΣ?,α)>3α Hσ←Pta(dm/2e,wσ) Set a new transition τ(qw,σ) = qwσ return H Fig. 3 Pta algorithm states are generated from it. When the set of blue states is empty, Red-Blue stops merging and a pdfa is returned by setting transition probabilities of Haccording to prefix probability approximations obtained by issuing statistical queries. Figures 2 and 4 show the Red-Blue and the merge algorithms. Let Hbe the resulting automaton after some iterations of Red-Blue. Red states of Hand transitions between them represent the the part of the graph we trust as correct, based on processed information. An invariant of the algorithm is that non-red states are always roots of trees in Hand blue states are always direct successors of a red state. 18 Jorge Castro and Ricard Gavald` a input: dfa Hand states qand q0of H output: dfa algorithm Merge Replace each occurrence q0in the description of Hby q while Hcontains a nondeterministic transition Let pand p0be target states of a nondeterministic choice Merge(p,p0,H) return H Fig. 4 Merge function Assuming unit time for oracle calls, the complexity of Red-Blue is O(m2). Moreover, if mis large enough that every state or transition of Dhas a counterpart in the tree dfa returned by the Pta algorithm and such that 2/mis less than the distinguishability of the target machine, the algorithm on input mlearns a pdfa hypothesis whose graph agrees with the target graph. As probability estimations of states and transitions will improve as mis larger, we have: Theorem 5. The Red-Blue algorithm learns every pdfa in the identification in the limit paradigm. This result appears (for the equivalent ALERGIA algorithm) in [13, 14]. But from this point it is easy to argue that Red-Blue also learns in the PAC model if the complexity of the target pdfa is taken to number of states times alphabet size times the inverse of the distinguishability. 5.2.2 The Safe-Candidate algorithm We describe a variant of the algorithm in [16], which was the first one to claim any formal PAC guarantee. Our version fits the query framework in [6, 17], which makes the exposition easier and simplifies correctness arguments. The main differences of the presentation below with respect to the description in [16] are two. First, as said, the algorithm gets information on the target distribution asking statistical and L∞-queries defined above instead of analyzing a sample. Second, it guarantees a good L1approximation, a weaker requirement than the good relative entropy approximation guaranteed in [16]. The latter choice avoids some rather subtle points in [16] by the fact that L1is a true distance unlike KL. The Safe-Candidate algorithm works in two stages. In the first one, it builds a transition graph that is isomorphic to the target subgraph formed by important elements —these are sates and transitions whose probability of being visited while generating a random string is above a threshold defined by the input parameters—. The construction uses both statistical and L∞-queries. The second stage consists of converting the learned graph into a pdfa by estimating the transition and stopping Learning probability distributions generated by finite-state machines 19 input: n,µ,Σ,ε, oracles DIFFD ∞and SQD output: A graph H algorithm Safe-Candidate α←µ/2; β←ε/24n|Σ| initialize the graph Hwith a safe qλand candidates qσ λfor σ∈Σ while Hhas candidates choose a candidate qmaximizing SQD(H[q]Σ?,β) foreach safe q0 make a call to the oracle DIFFD ∞(H[q],H[q0],α,β) if the answer is ’?’ remove qfrom the candidate list break if the answer ˆ µ<µ/2 merge qand q0 remove qfrom the candidate list break if qis still a candidate promote qto safe add candidates qσfor each σ∈Σ Fig. 5 Safe-Candidate graph construction probabilities corresponding to each state. This is similar to the estimation step in the Red-Blue algorithm performed once the set of blue states is empty, see Fig. 2. In this stage, only statistical queries are necessary. Figure 5 shows the code for the graph construction stage. The algorithm keeps two set on nodes, the set of safe nodes and the set of candidates. Safe nodes and transitions between them are known to be correct. Initially, there is only a safe state qλ corresponding to the empty word and one candidate qσ λfor each σ∈Σ. Each candidate represents a still unknown transition in the graph H. In each iteration, statistical queries are performed to choose the most informative candidate qand, after that, L∞-queries are issued in order to decide if the candidate is either insignificant at all, it is an already known safe node q0or it is a new safe one. In the latter case, when a candidate is promoted to safe, new candidates are considered representing undefined transitions leaving the new safe node. The algorithm finishes when there are no candidates left. An inductive reasoning proves that the resulting graph is isomorphic to the target subgraph containing significant states and transitions. The following theorem summarizes the performance of Safe-Candidate. Theorem 6. Let M denote an n-state pdfa computing a distribution D over Σ?, L denote the expected length of D, and πbe the smallest nonzero stopping probability in M. Then the execution of Safe-Candidate on a sample from D satisfies: 1. It runs in time poly(n,|Σ|,log(1/π)). 20 Jorge Castro and Ricard Gavald` a 2. It asks O(n2|Σ|2log(n/π)) statistical queries with tolerance ˜ Ω(ε3π2/n3|Σ|3L). 3. It asks O(n2|Σ|)L∞-queries with tolerance Ω(µ)and threshold Ω(ε/n|Σ|). 4. It returns a pdfa H such that L1(D,H)≤ε. A short and complete proof of this theorem is in [17]. A similar theorem without any dependence on Land πis shown in [35] but the proof is more complex. The proof in [16] that shows PAC learnability under the KL-divergence measure is much longer. 6 Learning PFA In this section we discuss algorithms having formal guarantees of learning the whole class of pfa. Similarly to the PDFA case, we first give an algorithm that has access to the target function as oracle, and can exactly learn the class of Weighted Automata when the right set of prefixes and suffixes is provided. Then, we specialize the algorithm to pfa and the case in which the input is a randomly drawn finite sample. We discuss the solutions given by Denis et al. [22] on the one hand and, on the other, by Mossel and Roch [33], Hsu et al. [29], and Bailly et al. [4]. The latter leads to the spectral method, which we expose in more detail following mostly the presentation in [9]. We finally mention a few of the most recent works extending the spectral method in several directions. 6.1 An Oracle Algorithm for Learning WA The algorithm in Figure 6 encapsulates the main idea for learning general Weighted Automata in the oracle model. It resembles the algorithm given by Beimel et. al [11] that learned instead from Evaluation and Equivalence queries. There are two nondeterministic steps in this algorithm: One is the choice of sets X and Y; like for pdfa, we do not discuss how to choose them in the oracle model. The other one is the choice of a factoring QR of H0, which represents the choice of an arbitrary basis for the rows of the Hankel matrix. The construction of the wa in the proof of Theorem 3 is the special case in which R=H0and Qthe identity, but it is easy to see that the correctness of the special case implies the correctness of the general QR case. Indeed, the value of the automaton for any word wis αT 0Twα∞ = (H0[λ,:]R−1)(Q−1H0 w1R−1)(Q−1H0 w2R−1)...(Q−1H0 wmR−1)Q−1H0[:,λ] =H0[λ,:]H0−1H0 w1H0−1H0 w2...H0 wmH0−1H0[:,λ] which is the value computed for R=H0and Qthe identity. The reason for the more general presentation will be clear later. It is also clear that the algorithm runs in time Learning probability distributions generated by finite-state machines 21 1. Choose any two finite sets X,Y⊆Σ?with λ∈X∩Y, in some way not specified by the algorithm; 2. Build the submatrix H=Hf[X∪XΣ,Y]of Hfby asking oracle queries to f; 3. Find two minimal subsets X0⊆X,Y0⊆Ysuch that λ∈X0and H0=H[X0,Y0] has the same rank as H; note that |X0|=|Y0|, say n, and H0has full rank; 4. Let Q,R∈Rn×nbe any two matrices factoring H0, i.e., H0=QR; 5. For each symbol a, let H0 a=Hf[X0a,Y0] = Hf[X0,aY 0]; 6. Build a wa from Q,R, and {Ta}aas follows. αT 0=H0[λ,:]R−1 α∞=Q−1H0[:,λ] Ta=Q−1H0 aR−1 Fig. 6 Learning wa with an oracle polynomial in Σand the sums of lengths of strings in X∪Y. Following the proof of Theorem 3 we have: Theorem 7. Let f be computed by some wa. If the cardinality of X0is at least the rank of Hfthen the wa built in this way computes f . Proof. The algorithm defines matrices Taby H0 a=TaH0; they are uniquely defined as H0has full rank. Furthermore, since the rank of H0is that of the whole Hankel matrix Hof f, these matrices must also satisfy Ha=TaH. Therefore, the automaton constructed by the algorithm is exactly the one built in the proof of Theorem 3, which by the theorem computes f.ut Consider now the adaptation of the algorithm to the case in which fis a probability distribution and we are given a finite sample S. As in the pdfa case, we take X= prefixes(S),Y=suffixes(S), and then create an approximation ˆ Hof Hby ˆ H[x,y]= empirical probability of xy in S. We know that the unperturbed Hhas rank at most n, the number of states of the smallest wa for fbut, because rank is so fragile under perturbations, ˆ Hwill probably have maximal rank, even if |S|is large. The solution taken by [22] can be intuitively described as follows: Compute a subset X0⊆Xsuch that |X0|=nand every row of ˆ H[X,:]is “close to” a linear combination of rows indexed by X0. For sufficiently small choice of “close to” (depending on the distribution), X0will be as in the algorithm above, and lead to a correct solution. The solution taken by e.g., [33, 29, 4], which leads to the spectral method, is less combinatorial and more algebraic, less local and more global, and can be phrased as follows: Let us instead find a matrix H0that 1) is easy to compute 2) has the same dimensions as H, but rank at most n, and 3) is “as close as possible” to ˆ Hunder some metric, with this rank constraint. One particular way of computing such H0 (among, perhaps, other possibilities) is the spectral method described next. 22 Jorge Castro and Ricard Gavald` a 6.2 The Spectral Method An important tool for the spectral method is the Singular Value Decomposition theorem; see e.g. [40]. Theorem 8. (SVD theorem) Let H ∈Rp×q. There are matrices U ∈Rp×p, D ∈Rp×q and V ∈Rq×qsuch that: •H=UDV T •U and V are orthonormal: UTU=I∈Rp×pand V TV=I∈Rq×q •D is a diagonal matrix of non-negative real numbers. The diagonal values of D, denoted σ1,σ2, . . . , are the singular values of H, and column vectors of Uare its left singular vectors. It follows that rank(A) = rank(D)is the number of non-zero singular values. W.l.o.g. by rearranging rows and columns, the diagonal values in Dare nondecreasing, i.e. σ1≥σ2≥.... The SVD decomposition can be computed in time O(pq2). The Frobenius norm of a matrix His kHkF= ∑ i,j H[i,j]2!1/2 . As this norm is invariant by unitary products, the square of the Frobenius norm of H is the sum of the squares of its singular values. It follows that from the singular value decomposition H=UDV of H, we can compute a low rank approximation: Fix n≤rank(H), and define H0 nas H0 n=      u1... un0               σ1 ... σn 0                   v1 . . . vn 0          . The following is the crucial fact: Fact. H0 nhas rank nand minimizes kH−GkFamong all rank-nmatrices G. Now we would like to use H0 nto find a full rank submatrix H0of H, since H0 nwill not in general have full rank and cannot be inverted. Alternatively, there is a notion of pseudoinverse matrix that satisfies what we need for the algorithm, and is easily computable from the SVD decomposition. The Moore-Penrose pseudoinverse of A, denoted A+, admits many different definitions. The most algorithmic one is perhaps: •If A∈Rp×qis a diagonal matrix, A+∈Rq×pis formed by transposing A, and taking the inverse of each non-zero element. Learning probability distributions generated by finite-state machines 23 1. get nand sample S; 2. X=preffixes(S);Y=suffixes(S); 3. define H[X,Y]∈Rp×qand set H[x,y] = empirical probability of xy; 4. define Ha[X,Y]∈Rp×qand set Ha[x,y] = empirical probability of xay; 5. Let QR be a rank-nfactorization of H, that is: •Q∈Rp×nand R∈Rn×q, both having rank n, •H=QR, for instance, take Qto be the first nleft singular vectors of H; 6. output the WA Msuch that αT 0=H[λ,:]R+,α∞=Q+H[:,λ],Ta=Q+HaR+ Fig. 7 Spectral learning of pfa •In the general case, if A=UDV Tthen A+=VD+UT. Some of its many interesting properties are: •In general, AA+6=Iand A+A6=I. •But if Ais invertible, A+=A−1. •If columns of Aare independent, A+A=I∈Rq×q. •If rows of Aare independent, AA+=I∈Rp×p. With this artillery in place, the spectral method for learning probability distributions generated by wa is described in Figure 7. The following PAC result was shown in [29] and reformulated in [9]. Theorem 9. [29, 9] Let S be a sample of a probability distribution D such that HD has rank n. Let σnbe the nth largest singular value of HD, and M the wa produced by the algorithm in Figure 7 on input S. There is a polynomial p such that if |S|≥ p(n,|Σ|,1/σn,1/ε,log(1/δ)), with probability at least 1−δ: ∑ |x|=t|D(x)−M(x)|<ε. Observe that σn6=0 if and only if rank(HP)≥n, so 1/σnmakes sense as a complexity parameter. Observe also that the output of the algorithm is not necessarily a pfa, even under the assumption that Pis a probability distribution. It may assign negative values to some strings, and not add up to exactly 1. However, by the theorem, such oddities tend to disappear as the sample size grows. Converting a wa known to compute (or approximate) a probability distribution to a pfa is, in general, uncomputable. The problem is discussed in detail in [22]. Both [33] and [2] give partial solutions by considering somewhat restricted machine models. 24 Jorge Castro and Ricard Gavald` a 6.3 Variations and Implementation of the Spectral Method Several variations of the spectral method have been introduced in order to improve its sample-efficiency or to extend it to wider settings. We point out below a couple of recent proposals. Let Dbe a distribution on Σ?. Derived from D, we define function Dpassigning to each string xthe probability of the set xΣ?, i.e. Dp(x) = ∑yD(xy). Similarly, we also consider function Dsthat on input xevaluates to the expected number of times x appears in a random string w. It turns out that if any of these three functions has wa, then all three functions have wa. Moreover, wa descriptions can be obtained from original wa parameters of one of them. The following lemma is shown in [17]: Lemma 1. Let h{Tσ}σ∈Σ?,α0,α∞ibe a wa and define S =∑σTσ,˜ α0=αT 0(I−S)−1 and ˜ α∞= (I−S)−1α∞. Then the following are equivalent 1. h{Tσ}σ∈Σ?,α0,α∞icomputes D. 2. h{Tσ}σ∈Σ?,α0,˜ α∞icomputes Dp. 3. h{Tσ}σ∈Σ?,˜ α0,˜ α∞icomputes Ds. Thus, besides using statistics of full strings in order to approximate the Hankel matrix from a sample we can also try to use statistics from prefixes and substrings in order to learn functions Dpand Ds. Experimentally, this yields more sample-efficient algorithms. The use of statistics on prefixes instead of full strings in the spectral method was already proposed by Hsu et al. [29]. Later, Luque et al. [32] take advantage of substring statistics when applying the spectral method to learn non-deterministic split head-automata grammars, a hidden-state formalism for dependency parsing. Recently, the spectral method in combination with matrix completion techniques has been also applied to a more general learning setting [8]. Here, the learning problem is to infer a weighted automaton from a sample of labeled examples but, in contrast with the standard paradigm, the sample is provided according to an arbitrary unknown distribution. Note that, for this type of learning problem, it is not guaranteed that a full approximation of a convenient Hankel submatrix can be achieved. This is because the input sample can lack of information for many submatrix entries and now it can not be assumed that the wa function value must be close to 0 there, as one can in the standard probability setting. In [8], matrix completion techniques are used to fill the gaps in the Hankel submatrix and then the spectral method is used to infer the target wa. They prove formal learning guarantees for some of the completion techniques under mild conditions on the distribution. 7 Future Work Let us mention a few open questions or future lines of research. Concerning the spectral method, it is clearly in an early stage and further extensions and applications Learning probability distributions generated by finite-state machines 25 will keep appearing. Making it generally practical and competitive is certainly of interest. Most spectral methods produce weighted automata with negative transition values when learning pfa; this may somewhat hinder their application in contexts where interpretability of the learned model is important. At a more theoretical level, we would like to find some geometric or algebraic interpretation of pdfa distinguishability; this might explain its role in pdfa learning as a particular case of the spectral values that come up in learning pfa. As mentioned, it is known that pdfa cannot exactly compute all distributions computed by pfa [22]. But, to our knowledge, it is not known whether pdfa can reasonably approximate distributions computed by pfa, say with a number of states polynomial in 1/εfor the desired approximation εin the L1distance (a rather direct result for L∞is given in [26], which extends to every Lpfor p>1). If such approximability is true, then it may be possible to transfer PAC learnability results for pdfa to pfa with a polynomial overhead. Acknowledgements This work is partially supported by MICINN projects TIN2011-27479-C04-03 (BASMATI) and TIN-2007-66523 (FORMALISM), by SGR2009-1428 (LARCA). We thank the chairs of ICGI 2012 for the invitation to present a preliminary version of this work as tutorial. We particularly thank the reviewer of this version for a thorough and useful work. References 1. Naoki Abe and Manfred K. Warmuth. On the computational complexity of approximating distributions by probabilistic automata. Machine Learning, 9:205–260, 1992. 2. Animashree Anandkumar, Daniel Hsu, and Sham M. Kakade. A method of moments for mixture models and hidden Markov models. In 25th Annual Conference on Learning Theory (COLT); Journal of Machine Learning Research - Proceedings Track - COLT 2012, volume 23, pages 33.1–33.34, 2012. 3. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1987. 4. Rapha¨ el Bailly, Franc¸ois Denis, and Liva Ralaivola. Grammatical inference as a principal component analysis problem. In 26th Intl. Conf. on Machine Learning (ICML), page 5. ACM, 2009. 5. Borja Balle, Jorge Castro, and Ricard Gavald` a. Learning pdfa with asynchronous transitions. In 10th Intl. Coll. on Grammatical Inference (ICGI), volume 6339 of Lecture Notes in Computer Science, pages 271–275. Springer, 2010. 6. Borja Balle, Jorge Castro, and Ricard Gavald` a. A lower bound for learning distributions generated by probabilistic automata. In 21st Intl. Conf. on Algorithmic Learning Theory (ALT), volume 6331 of Lecture Notes in Computer Science, pages 179–193. Springer, 2010. 7. Borja Balle, Jorge Castro, and Ricard Gavald` a. Bootstrapping and learning pdfa in data streams. In 11th Intl. Conf. on Grammatical Inference (ICGI), volume 21 of JMLR Workshop and Conf. Proceedings, pages 34–48, 2012.