FlashNormalize: Programming by Examples for Text Normalization

1 Introduction

Real world text contains words from various domains (like numbers, dates, currency amounts, email addresses, and phone numbers) in non-standard formats [Sproat, 2010]. It is desirable to "normalize" text by replacing such non-standard words (NSWs) with consistently formatted and contextually appropriate variants in several applications including machine translation, topic detection, text-to-speech (TTS) systems, training of automatic speech recognizers and spreadsheet functions.

The traditional technology for normalizing such NSWs involves manually writing down a normalization program, which often consists of a combination of ad hoc translation rules (e.g., for expanding dates or large numbers) along with some lookup tables (e.g., for month names or translation of single or double digit numbers). This process is not only

∗Work done by the author during internships at Microsoft.

Sumit Gulwani

Microsoft Research Redmond, Washington 98052

time-consuming but also error prone since it involves manual programming and often requires to pair up a programmer with the target language expert. Most significantly, such a program is very specific and needs to be written for each domain (e.g., numbers) and the target language of normalization (e.g., English). To make matters worse, there can be multiple normalization formats, even for a given domain and a target language, each of which requires its own program. For instance, "1325" might be normalized into "one thousand three hundred twenty-five", or may also be read as "one three two five" or "thirteen twenty-five" or "thirteen hundred and twenty five" depending on the context. In this paper, we propose automated learning of programs from examples for such tasks. This process is also referred to as inductive synthesis in some communities.

We propose a Programming-by-Examples technology called FlashNormalize for learning normalization programs. We identify an expressive domain-specific programming language (DSL) that offers appropriate abstractions for expressing such programs. This language describes the concept class. Our DSL is structured around four kinds of expressions: parse expressions that extract appropriate substrings from the input string, process expressions that transform the substrings using table lookups or functions provided by the language designer, concat expressions that concatenate various process expressions, and decision lists that allow for conditional behavior. The key technical contribution of the paper is a search algorithm for effectively learning programs in this DSL from input-output examples. Part of FlashNormalize's search algorithm learns parse and process expressions (having learnt appropriate lookup tables) and builds over recent work on inductive synthesis by [Menon et al., 2013] that uses brute-force search to explore programs of increasing size as guided by an underlying DSL. While Menon's approach works only on a single example, we show how to combine this approach with the idea of version-space algebras for inductive synthesis proposed by Lau et al. [Lau et al., 2000] to construct a hypothesis space of all programs that are consistent with all the user provided examples. In addition, we propose novel deductive top-down search algorithms to learn decision lists and concat expressions. Our algorithm for synthesizing decision lists falls into the paradigm of separate-and-conquer learning [F¨urnkranz, 1999]. In order to handle decision lists we identify a key concept of maximal consistent cover (MCC). We show how to synthesize small decision lists when one can compute the MCC for the structure underneath. Therefore our algorithm for learning decision lists is generic and independent of the specific structure appearing below it, which in our case is the concat expression.

Our key contributions are the following:

1. We have designed a rule-based DSL (Section 3) with support for lookup tables that is able to capture a range of Text-Normalization (TN) tasks. This DSL is our hypothesis space.
2. We describe learning algorithms for searching programs (within this hypothesis space) that are consistent with a set of input-output examples. In particular, we present a novel technique for learning decision lists (Section 4.1), and a novel method which combines bottom-up enumerative search (Section 4.2) with top-down deductive search (Section 4.3) for learning branches of the decision lists.
3. We describe strategies (Section 5.1) for helping users provide representative sets of examples and demonstrate their usefulness.
4. Using our techniques we show how FlashNormalize can learn programs for a range of TN tasks such as numbernames for 9 different languages, dates, phone numbers, time and measurements through examples (Section 5.2).

Related Work

Various language-specific techniques have also been proposed for French [Larreur et al., 1989], Russian [Sproat, 2010], Croatian [Beliga and Martincic-Ipsic, 2011]. Machine translation based methods have also been attempted [Schlippe et al., 2010] but these and other statistical translation methods require thousands of examples before they converge on approximately correct solutions. The upside to statistical methods is the ability to capture noisy input data that our methods do not possess. But FlashNormalize is much more useful when the user wants to provide a relatively small sample and can guarantee that it is consistent.

Our methodology of learning programs from examples falls into the broad effort of inductive synthesis. We point the reader to [Flener and Popel´ınsky, 1994] for a classical survey on the topic. For a survey on program synthesis techniques we refer to [Gulwani, 2010], apart from statistical methods they consist of: brute-force enumeration, version space algebras, and logical reasoning based methods. In our case a brute-force enumeration would be nearly impossible due to the large search space dictated by our DSL. We use version space based techniques to synthesize parse and process expressions. Logical reasoning based methods use off the shelf SMT solvers like Z3 [de Moura and Bjørner, 2008], for solving constraints that correspond to the synthesis problem. While every synthesis problem can be posed as checking the validity of second-order formula, SMT solvers are only effective for solving first-order constraints. It is not clear if one can encode our synthesis problem as a first-order formula. Decision lists in the classical sense [Rivest, 1987] are viewed as a boolean classifiers, while we view them as classifiers coupled with transformers (the concat expression), which necessitates the design of new algorithms for learning them.

Comparison with FlashFill: From the technical view point the closest related work is FlashFill [Gulwani, 2011] which focuses on synthesizing spreadsheet programs. We treat text normalization as a string manipulation task, but a more sophisticated one than what has been attempted in FlashFill. Our task requires (a) learning larger programs in a more expressive DSL that is extensible and allows table lookups (b) dealing with more elaborate specification in the form of large number of examples; FlashFill handles tasks that require only a few examples. For (a) we bring forth two key innovations: (i) we combine a deductive (top-down) search with an enumerative (bottom-up) search to achieve an efficient synthesis algorithm. (ii) we present a generic technique for learning conditionals using maximal consistent covers - our technique scales to large number of examples unlike the greedy heuristic used in FlashFill. For (b) the user needs assistance in finding a representative set of examples for which we use two key strategies (i) modularity: wherein sub-procedures are learnt first and used as black-box functions for synthesizing higher level procedures, (ii) active learning: where we prompt the user with intelligent inputs.

2 ProblemMotivation

We begin by describing three typical text normalization tasks and use them to motivate the problem we address in this paper.

Number Translations.

Translating sequence of digits into words representing the cardinal form is a scenario that arises in TTS for various languages. For example in English "72841" is spoken as "seventy two thousand eight hundred and forty one", and in French "1473" is spoken as "mille quatre cent soixantetreize". A TTS system engineer designing a system across various languages would need a a different program for such translations for every single language.

Dates.

Consider the task of normalizing dates. The goal here is to transform a date written in 'MMM dd, yyyy' format to its expanded spoken form. Table 1 presents five representative examples for this scenario.

What is common to all these examples is that we transform the MMM part into the expanded month and convert the dd part into its ordinal form. What is different in all of them is the way the years are written. In most cases (as in the first example) the year yyyy is said in pairs, first two together and the last two together. But if the year is let's say 2006 one obviously would not translate it to 'twenty six', but rather to 'two thousand six' or 'two thousand and six'.

Telephone numbers.

Phone numbers are spoken differently across the globe. North America uses a system where a 10 digit number is spoken in three parts consisting of the area code (3 digits), exchange code (3 digits) and the subscriber number (4 digits). The area code might sometimes be omitted, and one might have optional country code at the beginning. The examples in Table 2 illustrate some of these challenges, along with the additional challenge of variation in the input formats.

2.1 Problem Statement

We want to learn functions that take an input string and output a sequence of strings. The input in the first row in Table 1 is "jan 08, 2065" and the corresponding output is "January", "eighth", "twenty", "sixty", "five". A function g is said to be consistent with a set of input-output examples E if g(σ) = ω for each (σ, ω) ∈ E. Our problem is the following: given a set of such input-output examples, synthesize a function that is consistent with all the examples.

3 Representation

We have identified a domain specific language (DSL) for representing functions in our concept space. The programs in this DSL are both (a) expressive enough to capture a range of normalization tasks and (b) succinct enough to be learnt efficiently.

FlashNormalize's DSL consists of a decision list at the top, which is a chained sequence of if-then-else statements. Formally, it is an ordered sequence d = (p1, c1), . . , (pn, cn) where each pi is a Boolean predicate and each ci is a concatenate expression with String → Bool and String → List(String) as their respective types. The final predicate pn is fixed to be true. For an input string σ, the value d(σ) is defined as ci(σ) where i is the least index such that pi(σ) evaluates to true. We use D to denote the set of all decision lists.

A concat expression c is an ordered sequence of process expressions u1, . . , un. A concatenate expression c applied to input σ yields a list of strings c(σ) obtained from concatenating the output values ui(σ) of process expressions in the order they appear in c. We use C to denote the set of all concat expressions.

A process expression u is a program that given an input string transforms it into a list of strings. It is allowed to be either a constant string (independent of the input) or a Table lookup applied to a parse expression. We use Table to indicate a finite sized map with signature String→List(String). Any such table can be thought of as a set of key/value pairs (κ, υ) ∈ String×List(String) with no two of them having the same key. A program can use multiple tables (description of a program includes descriptions of the tables it uses).

In the examples in Figure 1 the substring 'jan' ('apr') needs to converted to 'January' ('April') or the string '8' ('23') should become 'eighth' ('twenty third'). Such transformations can be achieved by an appropriate table, like month and cardinal as used in Figure 1. Most often these tables represent core semantics relationship between substrings of the input and those of the output. These can either be specified by the user, or can even be learned by the system from sufficient examples.

Parse expressions are programs that extract substrings of the input. The space of possible parse expressions is described using a non-recursive grammar. An instance of such a grammar is presented in Listing 1. The reason for preferring a generic grammar to a fixed syntax is that algorithms designed for a grammar easily allow for future extensions without the need to modify the learning algorithm. Formally, a grammar is a 5-tuple (S, Φ, R, s, in) where:

• (a) S is a set of symbols denoting non-terminals. 1
• (b) Φ is a set of functions, where each function f has a specific signature T1, . . , Tk → T where T1, . . , Tk are the types of the input and T is the return type. The semantics of the functions is assumed to be given. A function can also have 0 arguments, in which case it is a constant.
• (c) R is a set of rules where each rule is either of the form A := B or A :=f(B0,..,Bk) where A,B,B0,..,Bk are symbols in S and f ∈ Φ
• (d) a unique start symbol s (S in the sample below)
• (e) a unique symbol in denoting the input variable (v in the sample below). R is not allowed to contain rules going out of this variable.

We explain some of the functions that constitute parse expressions. Consider the expression Split(v,0) used in U1 in Figure 1, it is used to extract 'jan' from the input 'jan 08, 2065'. The expression Split(σ,i) returns the i+1st substring of σ when split by the whitespace delimiter. The operation Dig(σ,i) returns the i+1st substring of σ composed entirely of digits, so Dig(v,0) yields '23' on input 'apr 23, 2006' (used in Figure 1). The operator Substr(σ,i,j) extracts the substring of length j of σ starting at index i. The index i in all these operators is allowed to be negative which is a convention indicating that indexing is to be from right to left. In case of Substr(σ,i,j) if the index i is negative then the substring extracted starts at index ℓ(σ)+i-j+1 and ends at ℓ(σ)+i, where ℓ(σ) is the length of σ . The operator Trim removes all leading zeros from its argument. These and several other operators can be combined in different ways through a grammar. The domain expert is free to extend/limit the capabilities of the parse expressions appropriately for the task in question.

1 Note that we do not have terminals in the grammar, instead parse trees terminate with functions of 0 arity.

string S := B | SubStr(B, k, k); string B := v | Split(v, k) | Dig(v, k); int k := -10 | -9 | .. | 10; string v;

Listing 1: Syntax of a subset of parse expressions presented as a grammar in Backus-Naur form. Each symbol is annotated with a type (eg: string) to denote the return type of the programs associated with it.

A Boolean predicate is a function of the type String→Bool, represented as conjunction of atomic predicates. Listing 2 is an example of atomic predicates described using a grammar. Each atomic predicate decides its truth value based on some feature of the input. For example, the function CountSeq(σ) counts the number of strings obtained by splitting σ with whitespace as delimiter, and the function StrLen(σ) counts the number of characters in σ.

bool A := Equals(N,k) | Equals(S,z) int N := CountSeq(v) | StrLen(B); string z := "0" | "1" | "00";

Example 1 Table 3 provides an instance of a complete program in our DSL that is consistent with examples provided for Dates in Table 1.

4 Synthesis Algorithm

In this section we present our algorithm that takes as input a set of input-output example pairs and generates a program in the DSL such that the program is consistent with the examples. First, we define what it means for a set of examples to be consistent with respect to a class of functions.

Definition 1 Given a class of functions F, a set of examples is said to be F-consistent if there is some function g ∈ F such that the examples are consistent with g. Any such function g is called a witness for the set of examples.

Now, we describe our algorithm. It has two logically distinct phases performed in the following order:

1. A bottom-up learning of process expressions for individual examples.
2. A top-down search for decision lists and concat expressions that are consistent with all the examples.

A complete bottom-up approach is infeasible due to the fact that the number of different concat expressions and decision lists grow exponentially with their length. While designing a complete top-down approach requires knowing the semantics of the constructs and the shape of the grammar apriori, which we can afford for concat expressions and decision lists, but not for parse/process expressions whose structure is defined through a grammar. Hence, we perform a hybrid search as described above.

4.1 Learning decision lists

For a given set of examples we would like to search for the smallest decision list consistent with it, in accordance with Occam's razor. Since this problem is computationally hard we propose a greedy heuristic that deduces a small decision list.

Proposition 1 A decision list (p1, c1), . . , (pn, cn) is consistent with examples E iff there is a partition of E of the form E1, . . ,En such that Ei is the set of those examples in E whose input makes p1, . . , pi-1 false and pi true, and with each Ei being C-consistent (recall that C represents the class of concat expressions) ,with ci as the witness.

First, we identify a key concept called maximal consistent cover that enables us to find small partitions that are Cconsistent as above.

Definition 2 Given a set of examples E, a collection {M1, . . ,Mk} ⊆ 2E , is said to be the maximal F-consistent cover of E if each Mi is F-consistent and for any M ⊆ E, if Mi ⊂M then M is not F-consistent.

Later on in this section we describe how to construct the maximal C-consistent cover with witnesses for its members. Now we show how to use this cover for constructing a small decision list. Observe that each part Ei in Proposition 1 has to be a subset of some member of the MCC cover. We design an iterative algorithm of the separate-and-conquer kind [F¨urnkranz, 1999] to discover a small partition sequence E1, . . ,En. After i iterations we would have produced a list (p1, c1), . . , (pi, ci). The ith iteration eliminates examples Ei. So, at the start of iteration i+1 we would be left with examples Ri+1 = E\(E1∪. . ∪Ei). Our goal in the i+1th iteration is to figure out a set Ei+1 ⊆ Ri+1 and a predicate pi+1 such that Ei+1 is also a subset of some member of the MCC cover and pi+1 distinguishes Ei+1 from Ri+1\Ei+1. The concat expression ci+1 would be obtained from the witnesses of the MCC cover. In order to produce a small decision list we pick Ei+1 as large as possible, while giving preference to members of the MCC cover over proper subsets of the members.

In Algorithm 1 we provide the pseudocode for the procedure LearnProgram which learns decision lists for a given set of examples. It iteratively learns the decision list by invoking LearnBranch on the remaining set of examples until every example is covered. (The notation E↾p is a shorthand for {(σ, ω) ∈ E | p(σ) = true}). The function LearnBranch takes as input a set of examples and produces a pair (p, c) of a predicate p and a concat expression c. This pair is a choice for the first branch of a decision list that explains the example set. In lines 7 to 10 we compute a set of candidates of the form 〈p,M〉 where M is a member of the MCC and p is a conjunctive predicate. This predicate computed by LearnConj is positive on all/most examples in M and negative on all examples in R-M. In lines 11 and 12 we try to pick that candidate 〈p, M〉 whose predicate p can filter out M from the rest of the examples entirely, if not we pick a candidate whose predicate can filter out as many as possible. The chosen predicate p is returned along with the concat expression c(M) that witnesses M in the MCC.

The procedure LearnConj for computing conjunctive predicates is presented in Algorithm 2. It takes as input two sets of examples P and N and produces a set of predicates that are negative on all inputs in N and positive on as many as possible in P . In line 1 it considers those atomic predicates that are positive on many examples in P with ties broken by looking at those that are positive on few examples in N. If any of those atomic predicates already negate all examples in N then those are added to the result (line 4). For every other example a (line 6), it is combined with a new predicate (generated using a recursive call to LearnConj) that would remain positive on many examples in P that a is positive on and negative on all examples in N that a fails to be negative on.

function LearnProgram (E) 1 let R←E, d ←empty list; 2 while R ̸= ∅ do 3 let (p, c) ← LearnBranch (R); 4 d ← d + (p, c); 5 R ← R↾¬p; 6 return d; function LearnBranch (R) 7 Candidates ← ∅; 8 foreach M ∈ MCC(R) do 9 let p ∈ LearnConj (M, R-M) with max size(M↾p); 10 Candidates ← Candidates ∪ {〈p, M〉}; 11 if ∃ 〈p, M〉 ∈ Candidates with R↾p =M then 12 return (p, c(M)); 13 let 〈p, M〉 ∈ Candidates with max size(R↾p); 14 return (p, c(M));

Algorithm 2: Learning conjunctive predicates that pick most examples in P and discard all in N.

function LearnConj(P, N)

1 A← top-k atoms a sorted lexicographically by max size(P↾a) then by min size(N↾a) ; 2 Result ← ∅ ; 3 foreach a ∈ A do 4 if N↾a = ∅ then 5 Result ← Result ∪ {a}; 6 else 7 foreach p ∈ LearnConj(P↾a , N↾a) do 8 Result ← Result ∪ {a ∧ p}; 9 return Result;

4.2 Learning process expressions

We learn process expressions using a dynamic programming technique that builds upon ideas of version space algebra by [Lau et al., 2000] and the idea of bottom-up program enumeration used in [Menon et al., 2013]. The technique we describe is applicable to any language of expressions described as a grammar and not limited to the one that we use in this paper.

Version space was first introduced by [Mitchell, 1982] to denote the set of all hypotheses (in a given hypothesis space) that are consistent with a given sample of labeled data. We use the term version space (VS) to describe a data structure that symbolically represents a partition of the programs. This data structure enjoys two properties:

1. It enables sorting a large number of programs into hierarchical groups with respect to their behavior on a given set of inputs.
2. It allows for an intersection procedure for producing a version space representing the intersection of the sets of

programs associated with different sets of inputs.

Given a non-recursive grammar we will show how to construct the VS data-structure for one input-output example. (Note that the tables and string constants can be treated as a part of the grammar because tables and examples are assumed to be given).

Formally a version space for a grammar (S,Φ,R, s, in) is a triple (V,L,G), where V is a set of vertices, L : V→S is a labelling function assigning a symbol to each vertex, and G ⊆ V×Φ×V ∗ ∪ V×V is a collection of edges. An edge is either a tuple (u, f, v1, . . , vk) such that L(u) := f(L(v1), . . ,L(vk)) ∈ R or a pair (u, v) such that L(u) := L(v) ∈ R. With every vertex u ∈ V we associate a set of programs ˜u, which is defined inductively as follows, for L(u) ̸= in:

and if L(u) = in, then ˜u = {fin} where fin is a function with no arguments that returns the input. This set is well defined because we deal with non-recursive grammars. Now we describe how to build such a data structure VSσ, for a given input σ. In VSσ each vertex v is associated with a value val(v) (unique among all those u with L(v)=L(u)), such that ˜ v represents those programs of L(v) that produce output val(v) when executed on input σ. The way to achieve this is to add the edge (u, f, v1, . . , vk) if and only if f evaluates to val(u) on inputs (val(v1), . . , val(vk)). This gives rise to a dynamic programming algorithm that computes this symbolic representation of sets of programs that produce the same output on the give inputs. We omit a detailed description of this algorithm as it can be derived from the inductive definition above.

Intersection of two version spaces on the same grammar is performed by taking a cross product, that is (i) for vertices u and v labelled by the same non-terminal we introduce new vertex 〈u, v〉 in the intersection, and (ii) for edges (u, f, v1, . . . , vk) and (u′ , f, v′1 , . . . , v′k ) we add the edge (〈u, u′ 〉, f, 〈v1, v′1 〉, . . . , 〈vk, v′k 〉).

Given examples (σ1, ω1), . . , (σn, ωn) we consider the intersection of VSσ1 , . . ,VSσn and check if it has a vertex v with L(v) = s0 and val(v) = (ω1, . . , ωn). Every program in ˜ v would be consistent with the given examples.

4.3 Learning concat expressions

Now, we describe an algorithm that learns the MCC for a given set of examples as required in learning decision lists. First we see how we synthesize a concat expression consistent with a single example (σ, ω). This amounts to searching for a sequence of process expressions that when applied to σ and concatenated yields ω. For any substring ω′ of ω, we can search for a process expression that produces ω′ by looking for a vertex v with L(v)=s0 in VSσ, such that val(v) = ω′ .

Next, we show how to search for a partition of the output string into substrings, such that for each substring there is a process expression that produces it on input σ. Note that there are exponentially many different partitions of a list, but only O(n2 ) different substrings where n is the length of ω. Hence we can symbolically represent all partitions succinctly as follows: Given input-output pair (σ, ω), consider a directed acyclic graph G(σ,ω)=(U, F, P ) consisting of: vertices U = {0, 1, ··, n} where n = len(ω), set of edges F ⊆ U×U

and an edge labelling function P : F→V mapping edges to vertices in VSσ where P((i, j)) is the vertex that witnesses the inclusion of (i, j) in F. Observe that G(σ,ω) is an acyclic graph in which a path from 0 to n denotes a concat expression that transforms σ to ω. So our problem of finding a concat expression reduces to searching for a path in this graph.

The next step is to use this idea to construct the MCC cover for a set of examples. We consider the directed graphs for each example and perform a parallel depth-first search. In every step of this search we pick an edge in each graph such that there is process expression common to all of them. When we cannot pick an edge for all examples we drop some and proceed along the rest in a greedy fashion. This search gives us concat expressions that explain subsets of examples. We maintain these subsets and use them to preemptively prune future attempts to find concat expression for subsets of examples that we have already found to be C-consistent.

function ConsistentSets ({(σ1,ω1,i1),..,(σn,ωn,in)}) 1 if ∀k : len(ωk) = ik then 2 yield {(σ1,ω1),..,(σn,ωn)}; 3 else 4 foreach S ⊆ {1, .., n} do 5 if ∃u ∀s∈S ∃js u(σs) = (ωs)[is,js] then 6 rec ← {(σs,ωs,js) | s ∈ S}; 7 foreach r ∈ ConsistentSets( rec ) do 8 yield r;

In Algorithm 3 we describe the pseudocode for enumerating subsets of examples that are consistent with a set of input-output examples. The function ConsistentSets takes as input a set of input-output examples each annotated with an index i indicating a position within the output ω. The first call to ConsistentSets is made with all i = 0. Lines 1 and 2, represent the base case in which the outputs of each example is covered. In lines 4 and 5 we enumerate those subsets of examples S for which a process expression u can be found that explains some prefix of each output ωs starting from the respective indices is. In practice we do not go through all subsets but let the enumeration be guided by the process expressions that explain prefix of outputs of the examples. In lines 6 to 8 we do a recursive call that continues the search from the indices js. In order to compute the MCC we just return the maximal subsets from all subsets obtained.

5 Implementation and Evaluation

In this section first we describe implementation strategies that complement our synthesis algorithm, and then the experimental evaluation we performed on real-world data.

5.1 Strategies

The learning algorithm described in Section 4 takes as input a set of representative examples and descriptions of the required tables. In certain cases determining one/both of these can be challenging. The required number of examples may be large, or the tables might not be straightforward to construct. In this subsection we see ways to tackle them which will prove useful in the context of number translations.

Modularity is a software design principle that encourages separation of a program into smaller ones which can then be reused. We employ this idea in synthesizing our programs. We can learn programs that handle certain parts of the output and then use them to learn a complete program. The advantage of this is that the size of all the modular programs put together is smaller than that of a monolithic program. In the case of number translations we learn programs that translate numbers of a particular length and reuse them as user-defined functions in process expressions to learn programs for numbers of larger lengths.

Active Learning: Requiring the user to provide all representative examples at the beginning can be too much to ask. Active learning provides a setting which can guide the user in finding the right examples. The DSL designer can encode domain knowledge in the form a learner that suggests inputs on which a synthesized program maybe wrong.

Traditionally, an active learner makes two kinds of queries, (a) membership query, in which the learner presents an input for which it would like to know the output (b) equivalence query, where the learner presents a program and wants to knowwhether it is correct. If incorrect the teacher presents it with a counterexample input-output.

We formulate a third category called test query in which the learner presents an input-output pair and wants to know if it is consistent with the target program. Only a negative answer would lead to a membership query on the same input. In our setting the teacher is the user who is trying to synthesize the right program, and therefore a test query is easier to answer than a membership query which is in turn easier to answer than an equivalence query.

A key advantage of active learning is that one can learn required tables by asking the user for outputs on certain variations of the input. For example consider how 3 digit numbers are spoken in Portuguese: 101 becomes "cento e um", 201 becomes "duzentos e um", 301 becomes "trezentos e um" and so on. Therefore we require a table that maps 1, 2, 3 . . . to cento, duzentos, trezentos and so on. This can be easily done by varying only the left most digit of the input and mapping the input variation to the corresponding variation in the output. We use this strategy in number-translations to synthesize the required tables. Another way to help users figure out counterexamples is through smart inputs. Smart inputs are a maximal set of inputs such that any two of them can be distinguished by the boolean predicates allowed in the DSL. Such inputs try to cover corner cases that might be missed otherwise. We use these ideas to generate examples and tables in an iterative fashion. In Figure 2 we describe how these are put together to obtain a counterexample guided strategy in synthesizing the correct program.

5.2 Experiments

Now, we describe results showing the (a) expressiveness of the programs in our DSL, (b) effectiveness of FlashNormalize's learning algorithms and strategies.

We first consider number translation scenarios as described in Section 2 for 9 different languages. We assume that we are given a table for translating 2 digit numbers, and learn n-digit translators for n ranging from 3 to 6. We employ the idea of modularity and synthesize n-digit translator using translator for smaller lengths. For learning the correct translator it is crucial that the user provides a representative set of examples (training examples). These examples in our experiments were obtained with the aid of an active learning method that interacts with the user. The active learner used is briefly described in Figure 2 and explained in the previous subsection. The n-digit translator synthesized with these examples is correct on all its valid inputs. For instance the 4-digit translator synthesized for any language, correctly produces the right output for all inputs from '1000' to '9999'. Here the synthesis algorithm is not shown all the 9000 valid inputs and their corresponding outputs, but only shown a small set of training examples whose size is reported in column E. In each case the program synthesized is correct on all 9000 valid inputs (test examples). As seen in Table 4 we are able to successfully learn the translators within 2 seconds in all scenarios. In all but two cases (5-digit French and Chinese) the number of equivalence queries required was just one, indicating that the user did not have to manually search for counterexamples in most cases.

Next, we picked 5 TN tasks with examples and tables assumed to be given and our tool synthesized programs that were consistent with all the examples. The results are summarized in Table 5. Once again, we learn the programs on a small training set, which is incrementally constructed by adding one counterexample (randomly chosen) at a time. The final size of this training set and the total number of examples are reported in columns E and A. We are able to successfully and quickly learn each of the tasks.

6 Conclusion

In this paper, we have considered the problem of text normalization. Manually writing programs for such tasks is challenging as it requires both programming and domain expertise, and is complicated by the fact that this exercise would have to be repeated for every language and output format. We have proposed a Programming-by-Examples technology called FlashNormalize to automate this process in which the user only has to provide input-output examples. We show the effectiveness of our technique on real world problems. The core technical idea of the paper is the design of algorithms and strategies for learning programs in our DSL. While heuristic search, VSA methods and active learning have been studied in various communities we bring these complementary ideas together. We believe such a combination might be useful for scaling other synthesis tasks [Gulwani, 2010; 2012].