2 Related work

We are interested in extracting the templates as defined at the beginning of Introduction. Although word sequences filling the slots in this article are not necessarily limited to linguistic units, such as NP, VPs and PPs, we want the results to be meaningful linguistically. The templates studied in this article can be considered MWEs with slots, where MWEs are coined (Baldwin and Kim Reference Baldwin, Kim, Indurkhya and Damerau2010), as ‘the split configuration of the verb–particle constructions’. A detailed summary of the acquisition of MWEs is well set out in this reference. In brief, active research in MWEs was triggered by the seminal paper of Sag et al. (Reference Sag, Baldwin, Bond, Copestake and Flickinger2002). In the work that followed, various attempts have been made to acquire MWEs, such as co-detection of English and Japanese templates by statistical methods (Kita et al. Reference Kita, Kato, Omoto and Yano1994), or the extraction of verbs and noun-type idiom candidates (Fazly Reference Fazly2006). Duan et al. (Reference Duan, Lu, Wu, Hu and Tian2006) reapply a method to extract frequent patterns from DNA sequences. Since the basic technique is based on finding longest common subsequences, the method does not handle gaps. Several different methods for extracting MWEs using a bilingual corpus have also been proposed (Zarrießand Kuhn Reference Zarrieß and Kuhn2009; de Medeiros Caseli et al. Reference Caseli, Ramisch, das Graças Volpe Nunes and Villavicencio2010).

In more recent work, (Nagy T. and Vincze Reference István Nagy and Vincze2014) focus on the extraction of verb-particle combinations, each of which has a verb and a particle. Their method can handle gaps, since it is a syntax-based method that uses a parser, but this requires a fully annotated gold standard. A more recent work attempts to extract MWEs without wildcards. Tu and Roth (Reference Tu and Roth2012) study the method to detect phrasal verbs using machine learning techniques. Although slots are considered in this article, the application is limited to six verbs and nineteen prepositions. Some recent studies attempt to extract from grammatically structured data, such as treebank and parsed data. Sangati and van Cranenburgh (Reference Sangati and van Cranenburgh2015) extract MWEs from frequently appearing fragments in the treebank. Since the method is able to exploit a treebank, the accuracy of the method is higher than the unsupervised methods. Another study (Martens Reference Martens2010) attempts to find frequent subtrees from parsed data. Our approach differs from these in that it assumes no grammatical structure in the input.

From the opposite perspective, the proposed method is aimed at discovering the underlying structure in related phrases in an unsupervised manner, and as such it is broadly related to work in the field of unsupervised grammar induction.

In the field of natural language processing, the induction of grammars more complex than regular grammars has been actively studied. In Klein and Manning (Reference Klein and Manning2004), an unsupervised dependency parser was proposed that successfully induced structure from a modest amount of data. The success of this early approach stimulated further research in the field. Headden et al. (Reference Headden, Johnson and McClosky2009) introduced valence frames and lexical information into their induction process, giving rise to a substantial improvement in performance (Gimpel and Smith Reference Gimpel and Smith2012). The method of Klein and Manning (Reference Klein and Manning2004) was improved in Gimpel and Smith (Reference Gimpel and Smith2012) by introducing concave models that could be optimized without the problem of local minima. However, at present the accuracy of the state-of-the-art unsupervised methods evaluated on Penn Treebank text (Marcus, Marcinkiewicz and Santorini Reference Marcus, Marcinkiewicz and Santorini1993) is below seventy per cent when the relative to the state-of-the-art supervised methods achieve over ninety-three percent (Klein and Manning Reference Klein and Manning2004; Gimpel and Smith Reference Gimpel and Smith2012). Therefore, it may be difficult to replace current supervised parsers with unsupervised parsers to use for template extraction.

A template considered in this work has the basic structure of a regular expression (that we will model using automaton-related data-structures), and therefore next we summarize previous work related to regular expression induction that directly concerns template induction. The work can be roughly partitioned into three: heuristics, regular grammar induction and methods related to finite state automata. Many have performed template induction based on heuristics, such as Han, Pei and Yin (Reference Han, Pei and Yin2000), Pei et al. (Reference Pei, Han, Mortazavi-Asl, Pinto, Chen, Dayal and Hsu2001), Cui, Kan and Chua (Reference Cui, Kan and Chua2004), and Kim (Reference Kim2010), just to mention a few. Most of the approaches are original but none are theoretically grounded. The remainder of the previous work related to regular expressions presented here has some mathematical framework as a basis.

Regular grammar induction algorithms are able to extract a regular grammar from a set of phrases with similar structure. These techniques have had wide application to sequences in general including the extraction of DNA patterns. (Fernau Reference Fernau2009) suggested a simple bottom-up regular expression induction strategy that we replicated and applied to natural language. Unfortunately, it resulted in a huge number of trivial regular expressions. Moreover, it is not straightforward to apply the method to template extraction since it has no mechanism for slot creation. Most of the previous work discussed so far is based on prefix sharing of similar phrase instances. This, however, generates huge amount of template candidates that have similar infix and suffix structures. The point of phrasal template induction is to identify shared common structures anywhere in the phrases, and abstract them into slots.

Template extraction has a broad range of potential applications. One potential application is to support lexicographers in building/enriching dictionaries for humans and machines. The application can take a dynamic form, for example, by extending the KWIC system (Hunston and Francis Reference Hunston and Francis2000), which shows the words immediately preceding and following the node word, up to a predetermined length. In fact, our work was partly motivated by an idea presented in ‘pattern grammars’ (Hunston and Francis Reference Hunston and Francis2000). The authors assembled the Collins Cobuild Grammar Templates dictionary Francis et al. (Reference Francis, Hunston and Manning1996, Reference Francis, Hunston and Manning1998), and claim that texts are formed of patterns defined as word sequences that may contain slots (and we use the term template to represent this concept hereafter). The patterns allow for parsing any sentence using pattern grammar, as each word in the sentence will occur with its own pattern. Hunston and Francis (Reference Hunston and Francis2000) show this under the heading of ‘pattern flow’. Although the Collins Cobuild English Dictionary was constructed manually, they suggest the possibility of automating the procedure with an extended form of the KWIC system. This work takes a first step to answer this challenge, by means of the SeqBDD. This work was motivated by this fundamental work, but the templates we extract are different from patterns of this Pattern Grammar, in which patterns are defined as sequences of phrase or clause types (e.g., ‘that-clause’, ‘noun phrase’) that are dependent on specific verbs, nouns or adjectives.

Another genre of application, as mentioned in the previous section, relates to social media, which has abundant repetitive patterns and shallow structure. Baldwin et al. (Reference Baldwin, Cook, Lui, Mackinlay and Wang2013) shows these common characteristics threading through social media, through building and analyzing a corpus consisting of various types of social media. This suggests how patterns could be one possible key to information extraction. The identification of patterns would also create a means of compressing the data. This paper will later study the proposed method in the context of these two potential applications: the verb+preposition template extraction as an example toward an extended KWIC method, and pattern acquisition from social media.

3 The sequence BDD

Given a set of linguistic phrases with a similar structure, we want to extract the common structure as a template: a sequence of words and slots. The first attempt of doing this made use of a Trie structure. The Trie, however, does not allow for sharing the infix and suffix. Broadly, for template extraction, we are interested in representations that also allow for the sharing of common structures within infixes and suffixes.

Among the different data structures that allow this type of sharing, we chose the SeqBDD as our basis. The SeqBDD is a descendant of two different formal methods: of BDD and acyclic DFA.Footnote ¹

Therefore, the explanation of SeqBDD has two aspects: SeqBDD as one descendant of BDD; and the other in contrast to DFA. We provide the former in Section 3.1, and the latter in Section 3.2. The basis of the SeqBDD can be found in Loekito, Bailey and Pei (Reference Loekito, Bailey and Pei2010), Denzumi et al. (Reference Denzumi, Yoshinaka, Arimura and Minato2016), and the definitions and algorithms necessary to replicate our method are all provided in this article.

3.1 SeqBDD as a descendant of BDD

SeqBDDs are descendants of BDDs (Bryant Reference Bryant1986) that are graphical structures able to express Boolean functions. For example, consider the Boolean function ‘abc ∨ abc ∨ abc’. The function can be represented as the binary decision tree structure shown in Figure 1(a). Solid edges in the graph represent truth (1-edge), and dashed edges represent falsehood (0-edge). The leaf nodes represent final truth and falsehood as 1 and 0, respectively. It is clear from the figure that the tree contains many common substructures. For example, a node labeled ‘c’ is connected to the 0- and 1-terminal nodes multiple times. The study of BDD has tackled the elimination of such redundancy in binary decision trees (Bryant Reference Bryant1986; Knuth Reference Knuth2009).

Fig. 1.

A binary decision tree and corresponding BDD structures representing the Boolean function abc ∨ abc ∨ abc.

The minimization of the representation is conducted by exhaustively applying two reduction operations for merging identical subgraphs: (1) node sharing (share all equivalent subgraphs) and (2) node deletion (delete all redundant nodes where both outgoing edges lead to equivalent subgraphs) (Bryant Reference Bryant1986; Knuth Reference Knuth2009). Equivalent subgraphs are defined recursively: two nodes are in equivalent subgraphs if their labels are identical and the heads of their outgoing edges are also in the equivalent subgraphs. For example, in Figure 1(a) the central two nodes labeled ‘c’ are both in equivalent subgraphs that extend down to the leaf nodes. These subgraphs are merged into the left ‘c’ node at the bottom in Figure 1(b) using the node sharing operation.

As for the node deletion, the left-most node labeled ‘c’ in Figure 1(a) is deleted using the node deletion operation (2) since both outgoing edges lead to the 0-terminal node. Its incoming edge (from node ‘b’) is redirected to the shared equivalent subgraph of its children (the 0-terminal node). It is clear that the graph in (b) is considerably more compact than (a).

A SeqBDD (Loekito et al. Reference Loekito, Bailey and Pei2010) is a BDD dedicated to representing a set of sequences. A set of sequences is treated as a Boolean function; the function being True if the sequence is a member of the set, and False otherwise. Since the number of False members are infinite, they are not explicitly shown in SeqBDD. Paths along the solid arrows through the graph encode members of the set. For example, Figure 2(c) represents the set: {ac, abc, aac, acc, abbc},where ‘acc’ is represented by a → a -→ b -→ c → c → 1 (i.e., encode a, then do not encode a, not b, encode c, encode c). Note that a path can include False edges (dashes), but these do not encode elements of the sequence. A symbol in the sequence is generated from the label of the tail of a traversed edge if the edge is a True edge.

Fig. 2.

Equivalent Trie, minDFA and SeqBDD representing: {ac, abc, aac, acc, abbc}.

When building a SeqBDD, it is not necessary to first construct a (potentially huge) binary decision tree and then apply reduction rules to reduce it. Rather, for SeqBDD, the final compact structure is built on-the-fly (Loekito et al. Reference Loekito, Bailey and Pei2010; Denzumi et al. Reference Denzumi, Yoshinaka, Arimura and Minato2016), by merging two SeqBDD graphs, basically composed of node sharing and deletion rules.Footnote ² The obtained SeqBDD graph is minimal, having the minimal number of nodes necessary to accept a given set of input.

4 Relaxed SeqBDD

As will be shown in the evaluation section, a straightforward application of SeqBDD as a means to extract a set of templates leads to a result of low coverage (recall), although the quality of output templates is high. This is a consequence of the strictness of the node sharing operation. The SeqBDD faithfully represents the supplied dataset, but it is not clear whether this data structure is optimal with respect to template extraction.

An example is given in Figure 3, where the w _j are lexical items and x _i are the potential slots. The original SeqBDD can learn the structure in the left figure from just two training examples (i.e., {w ₁x ₁x ₂x ₃w ₂, w ₁x ₄x ₅x ₆w ₂}). To learn the structure shown in the right figure, however, it requires examples of four different forms to appear (i.e., {w ₁x ₁w ₂x ₃w ₃, w ₁x ₁w ₂x ₄w ₃, w ₁x ₂w ₂x ₃w ₃, w ₁x ₂w ₂x ₄w ₃}). If even one of these phrases did not appear in the input set, then the graph structure gets separated, as in for example the structure in the left figure and the potential slot before and after w ₂ cannot be captured. In general, when a template has n slots, a number of corresponding phrases that must be included in the input set grows combinatorially with respect to the variety of the items around the n slots. Although such combination is possible in natural language, the huge number of required occurrences cannot be actually observed in real data.

Fig. 3.

(a) is when two phrases {w ₁x ₁x ₂x ₃w ₂, w ₁x ₄x ₅x ₆w ₂} are given as input. (b) is when four phrases {w ₁x ₁w ₂x ₃w ₃, w ₁x ₁w ₂x ₄w ₃, w ₁x ₂w ₂x ₃w ₃, w ₁x ₂w ₂x ₄w ₃} are given as input.

In order to cope with this strictness, we relax the algorithm given by (Denzumi et al. Reference Denzumi, Yoshinaka, Minato and Arimura2011): We call the proposed graph structure Relaxed SeqBDD and explain it below. Since we cannot expect all examples to occur in reality, we instead look at False phrases represented by the graph. The set of False phrases represented by the SeqBDD include the following two types:

1. (1) Phrases that did not occur.

2. (2) Phrases that should not occur.

In SeqBDD, the (1) is not represented, whereas the latter is omitted: if represented using a less compact form of original BDD, they are connected to 0-terminal nodes. The issue is that possible phrases that did not appear get included in (2) by the standard process of SeqBDD construction.

The idea of the Relaxed SeqBDD is to relax the algorithm so that all the phrases that share 0-terminal nodes get merged during construction. To realize this, only the node sharing rule of the construction algorithm needs to be modified: The node sharing rule for the SeqBDD is described in Section 3.1, and is intuitively depicted in Figure 4. In the figure of original algorithm (a), one can see that nodes are only shared when both their True and False subgraphs are equivalent, which is called zero suppression reduction rule, in the study of BDD. In the proposed Relaxed SeqBDD as shown in Figure 4(b), this rule is replaced by the relaxed version that shares the subgraphs having the common subgraph leading to the 0-terminal node. As a means to satisfy this constraint, the True children are combined using the union operator proposed in Loekito et al. (Reference Loekito, Bailey and Pei2010), where its algorithm is provided in Appendix A. The combination process results in the sharing of the structures of both True children, and is illustrated in Figure 4(b); in the figure, the two True subgraphs of u and v are combined using the union operation.

Fig. 4.

Original and relaxed sharing rules.

Unlike the original node sharing rule, there is danger of creating a cyclic graph with the proposed method (for example, in Figure 3 right figure, a cyclic graph can get generated if node w ₃ was unified with node w ₁). As a consequence sharing is not performed if it would result in a cyclic graph. This new rule allows the BDD structure to represent word sequences that have not occurred in the data. Our hypothesis is that this will make the structure more suitable for template extraction, because observations are necessary to make the generalizations leading to templates.

The idea is formally defined as follows as a modification of the original theory of SeqBDD (Denzumi et al. Reference Denzumi, Yoshinaka, Minato and Arimura2011). In order to show clearly where the modifications are, we follow a similar descriptive form to the algorithms presented in the article. The modification of the definition is shown mathematically first and then we show which part of the algorithm must be modified.

Algorithm 1

Reduce : SeqBDD Reduction algorithm

Algorithm 2

Get_node : Original

Mathematically, a subgraph v is characterized by the tuple 〈v.top, v.0, v.1〉, where v.top denotes the top node of the subgraph v, v.0 and v.1 denote the subgraphs under v, through 1-edge (called True subgraph) and 0-edge (called False subgraph), respectively. In the original (Denzumi et al. Reference Denzumi, Yoshinaka, Minato and Arimura2011), the subgraphs u and v are shared in the SeqBDD when:

where the Relaxed SeqBDD shares u and v when:

Given this simple modification, the algorithm of the Reduce procedure shown in Algorithm 1 (which in fact calls Algorithm 2) can be modified as in Algorithm 3.

The sharing of two graphs occurs by providing a subgraph v to the function Reduce, as in Algorithm 1. The graph reduction process is performed by recursively calling the Reduce function (line 5). The Reduce function uses a Get_node function that implements the graph sharing and zero suppress reduction rule (see Section 3.1). To realize the Relaxed BDD, we only have to modify this Get_node function, where Algorithm 2 shows the original Get_node algorithm and Algorithm 3, the proposed algorithm. The differences are shown in red in Algorithm 3.

Algorithm 3

Get_node : Proposed Relaxed Version

The Get_node function acquires the top node of the subgraph v, and the two subgraphs that are processed by the Reduce function. Until line 4, the two algorithms are the same (for processing the zero suppress reduction rule). Then, the sharing is processed by acquiring the existing common graph as u. The graph is stored in the hash_table, that maintains a table of constructed graphs (as pointers), using node and subgraphs as keys. The key point of the difference of the proposed Algorithm 3 from the original Algorithm 2 lies in this hash_table function. In the original, the hash_table stores a structure given the triplet 〈v.top, v.0, v.1〉, whereas the modified method is only given the pair 〈v.top, v.0〉.

Figure 4 (a) and (b) shows the difference of the sharing rules of the original triplet 〈v.top, v.0, v.1〉 and the relaxed pair 〈v.top, v.0〉. In the original version of Algorithm 2, if a common part u already exists, then, u is returned; if not g ₀ and g ₁ are linked as v.0 and v.1. In the modified version of Algorithm 3, the procedure is the same, but in addition, the cyclic condition is examined (line 6), and if no cycles exists, unification is conducted (line 8). This Union function is a predefined function to unify two subgraphs which is provided in Appendix 8. The operator is exactly the same as that defined in Denzumi et al. (Reference Denzumi, Yoshinaka, Minato and Arimura2011).

In order to show the effect of the Relaxed SeqBDD, Figure 5 illustrates two graphs, a SeqBDD and a Relaxed BDD, generated for the three input sequences {abefi, acegi, adehi}. In (a), the original SeqBDD is shown, where the e in the middle is not merged. With SeqBDD, to create the figure as in (b), the input must be {abefi, abegi, abehi, acegi, acefi, acehi, adegi, adefi, adehi}, where all combinations of prefix {ab, ac, ad} and suffix {fi, gi, hi} should occur. The SeqBDD therefore does not incorporate any unseen but possible input. RelaxedBDD allows the generation of (b), from the three inputs, assuming the possibility of occurrence of six unseen inputs. Of course this is a double-edged sword: the algorithm will certainly decrease the precision of template extraction of aXeYi, but will increase the recall. The effectiveness of this modification can only be verified with real evaluation, which we provide in Sections 6 and 7.

Fig. 5.

Original and Relaxed SeqBDDs for the input data of {abefi, acegi, adehi}.

5 Post-processing of a relaxed SeqBDD to obtain templates

Given a set of word sequences, a Relaxed SeqBDD is constructed by using an on-the-fly algorithm, thus explained. Then, we apply the following procedure to obtain the final templates out of the Relaxed SeqBDD.

The appropriate form of input word sequence depends on the problem as will be shown in the following two evaluation sections. In our work, the input word sequences are labeled with POS tags, and the SeqBDD is constructed based on the POS tags (Σ is the set of POS tags). The words are nevertheless preserved in the nodes as auxiliary information, in the form of lists containing the words at nodes that were contracted through node sharing operations during BDD construction. Let $\mathcal {W}_u$ be the set of words at node u ∈ V, f(w) be the relative frequency of $w \in \mathcal {W}_u$.

Fully constructed SeqBDDs are post-processed as follows.

1. 0. POS-tagging: To build a relaxed SeqBDD, all word sequences must be POS tagged.

2. 1. Delete Falsehood: The 0-edges are simply deleted, since they are no longer necessary.

3. 2. Weight edges: The edges are then weighted by the absolute frequency of the number of phrases that goes through the edge. In order to reduce the complexity of the graph, all edges with frequency one are removed (Figure 7(a)).

4. 3. Obtain paths: Obtain all paths connecting to the starting status of s _start.Footnote ⁴Weight each path with the minimum frequency of the edge included in the path (Figure 7(b)).

5. 4. Find slots: Each node u along a path is labeled as ‘lexical’ if $\max _{w \in \mathcal {W}_u} f(w) \ge \theta$, ‘slot’ otherwise, where θ is set to best suit the problem. This transforms a path into a template with slots (Figure 7(c)).

6. 5. Merge templates: Merge identical templates and weight the final template by the sum of the weights of the merged templates (Figure 7(d)).

The output consists of a frequency-ranked list of templates. For example, Figure 2(c) is transformed into Figure 6 through procedures 1 and 2 above, where the template ‘aXc’ is now readily visible: the output nodes and edges of the real examples are labeled by the weights. Procedure 4 defines which nodes are slots.

Fig. 6.

Post-processed SeqBDD representing: {ac, abc, aac, acc, abbc} same as Figure 2.

The overall procedure above is equivalent to determining the paths by maximal flow (Cormen, Leiserson and Rivest Reference Cormen, Leiserson and Rivest1990). Since the edges e ∈ E of the SeqBDD are weighed by frequency, the maximal flow in every path is naturally limited by the minimum frequency edge (Procedure 3). We believe that this is a natural procedure to extract a template given a SeqBDD graph, but other possible strategies exist and remain future research.

We show how this post-processing proceeds using Figure 7. Let us assume that there are five input phrasesFootnote ⁵ :

Fig. 7.

SeqBDDs post-processing examples.

The Relaxed BDD is constructed and by eliminating unnecessary information through procedures 1 and 2, and the graph would look as that in (a): the graphs are aligned horizontally here (due to space limitations), nodes indicate shared POS, and edges are annotated with frequencies. Examination of paths through procedure 3 gives potential template candidates as in (b). Then lexical/slot nodes are judged with the relative frequency function f as in (c) through procedure 4. Finally, the equivalent templates are merged to obtain the the final results through 5 as in (d).

6 Verb+preposition template extraction

We first present a large-scale experiment that attempts to extract verb templates out of given sentences. A verb+preposition template here is a template that involves a verb, such as ‘regard X as Y’. This test intends to evaluate the performance of the method using a clean dataset, acquired from a dictionary.

For this purpose, the verb+preposition templates were collected by searching Oxford Advanced Learner’s Dictionary for phrasal verbs with slots. This extraction was based on the annotation provided by the Dictionary, for example, ‘regard X as Y’ where X and Y are slots. We considered verbs with multiple slots, only, and excluded verbs that only have one slot. The slots can be located at the end of the template as in ‘regard X as Y’. To collect such instances, a verb list was acquired from the British national corpus, we scanned the Learner’s dictionary for every verb, and extracted the verb+preposition templates with slots using regular expressions. We obtained a set of 976 templates.

For each template, the sentences containing all words in the template were obtained from the English Gigaword Corpus (fifth edition; LDC2011T07), consisting of 180 million sentences lemmatized and POS tagged using the Stanford CoreNLP tools (Manning et al. Reference Manning, Surdeanu, Bauer, Finkel, Bethard and McClosky2014). The sentences that included the verb were obtained and then filtered using regular expressions so that a span between the slots was at most five words. For example, for the template ‘regard X as Y’, all sentences with the words ‘regard’ and ‘as’ were extracted, under the constraint that the number of words between ‘regard’ and ‘as’ was at most five. Similar constraints have often been used in previous work, notably (Baldwin and Kim Reference Baldwin, Kim, Indurkhya and Damerau2010). The proposed method and the parser-based method that we compare with (defined in the following) were then used to discover the templates from these search phrases.

For the proposed method, we extracted ranked lists of template hypotheses from the search phrases, using the method described in Section 5, after the sentences in the search phrases were reduced to sets of subsequences following the main verb. Since there is no established baseline for this task, another plausible method using a parser was created for comparison. This method using a parser is an unfair baseline, since the parser-based method uses vastly more resources, requiring a parser trained on a structurally annotated corpus, whereas our method uses only tagged corpus. In fact, these are two different methods which could even complement each other for the task of phrase structure induction. Hereafter, we call this alternative method to be compared with our method, the parser-based method.

In this parser-based method, first the search phrases for all of the 976 templates being studied were dependency parsed. The parser was the Stanford Parser, based on universal dependencies. The procedure is conducted by providing the whole sentence to the parser. Figure 8(1) shows three such sentences for the template ‘share X with Y’. Figure 8(2) shows the dependencies of the verb in the template. In Figure 8(3), template hypotheses for the parser-based method are created from sentences that contain the same dependencies, for example, the second two sentences in the figure both contain the dependencies: [dobj] and [prep_with] and these give rise to a single template hypothesis with a count of 2. The hypothesis counts reflect the number of sentences that share the same dependencies, and are used to rank the template hypotheses (Figure 8(4)).

Fig. 8.

Extracting parser-based template hypotheses.

The performance was evaluated by mean reciprocal rank (MRR) (Manning, Raghavan and Schütze Reference Manning, Raghavan and Schütze2008) and recall, to judge the quality of the lists of extracted template hypotheses. Recall is the proportion of the correct verb template that were extracted. As for what corresponds to the precision, since the output templates are ranked and the rank must be evaluated, we used MRR. MRR is the average of reciprocal rank of the correct verb+preposition template in the output list. Let Q be the number of test cases, for each of which the procedure extracted a template at rank r _i (i = 1, . . ., Q).

(1) $$\begin{equation} MRR = \frac{1}{Q} \sum _{i=1}^Q \frac{1}{r_i} \end{equation}$$

The results are shown in Figure 9. To observe the effect of dataset size, dataplots show the average MRR and recall of templates that had more than a specific cutoff threshold number of search phrases. The cutoff values used were: 0, 100, 200, 300, 500, 1 k, 2 k, 5 k, and 10 k. These values are annotated only on the ‘SeqBDD(θ = 1.0)’ orange curve on the graph; on all other curves the cutoff variables run in the same manner.

Fig. 9.

verb+preposition template extraction from the Gigaword corpus.

We first examine the parser-based method and the two variants of the proposed method as follows:

• Parse in black dotted line. The parser-based method.

• SeqBDD (θ = 1.0) in orange dotted line. (For θ, see Section 5.)

• Relaxed SeqBDD (θ = 0.5) in red line with triangles.

It can be seen in Figure 9 that the SeqBDD method is able to achieve higher levels of MRR than the parse-based baseline, but at a cost in terms of its recall. The proposed Relaxed SeqBDD variant is able to achieve considerably higher levels of MRR in all cases than both methods without losing ground in terms of recall. It is impressive how higher MRR was acquired: this is due to the relaxed algorithm that integrates template candidates scattered in the original SeqBDD. We observed that for the Relaxed SeqBDD there is a trade-off between MRR and Recall, however, the Relaxed SeqBDD was able nonetheless able to achieve MRR levels greater than the other methods even when the level of recall was at its maximum value of ninety-five per cent. It is clear from the figure that the baseline and SeqBDD methods depend heavily on the amount of data, whereas the proposed method appears to be far less sensitive to the data set size, and is able to achieve respectable MRR and recall on even the smallest subset of the data used in our experiments. Note, that the parser-based method used a parser trained on a structurally annotated corpus, whereas our method used only a tagged corpus.

The end-to-end runtime performance,Footnote ⁶ from raw text until the final output for the proposed SeqBDD method was 72.1 sec and 866.7 MB per template. The Relaxed SeqBDD method required 247.1 sec for processing and 1.5 GB of memory. The baseline was the fastest, taking only 51.8 sec for processing, but required 2.3 GB of memory due to the resources required for parsing.

7 Template extraction from twitter

In this section, we are concerned with a more real-world application: the extraction of templates from short text messaging. Twitter, for example, is used for commercial objectives, and it is relatively common for the information in tweets to be generated using templates, as in the following examples:

The automatic extraction of such templates will facilitate the analysis and extraction of structured information. The task in this experiment is to output the templates for a given set of tweets. Clearly, this example is output by a machine bot: other more real examples are provided in Appendix B.

For this purpose, we collected corpora of Tweets in English and Japanese.

In the case of English, a set of Twitter accounts was mined starting from a single Twitter account by recursively following the followers of the accounts. A set of tweets was collected for each account traversed. In the case of Japanese, a list of tweet sets for accounts was downloaded directly from the web.Footnote ⁷ Since we are interested in evaluating template extraction, we downloaded the ones which were judged to contain templates by the baseline procedure. Extraction from random data is unlikely to be fruitful, since any extraction algorithm will not work unless many similar expressions are contained in the original data. Therefore, we have to filter the dataset first.

The baseline procedure is based on heuristics of substring matching, described as follows. For a set of tweets for a Twitter account, k-means clustering (Macqueen Reference Macqueen1967) was applied with the similarity between two tweets being the word term frequency multiplied by inverse document frequency (TF-IDF) vector (Deerwester et al. Reference Deerwester, Dumais, Furnas, Landauer and Harshman1990). The procedure partitions the set of tweets into K clusters. Templates were constructed for each cluster as follows. First, the common words that appear in more than half of the tweets were identified and preserved as words in the template; then single slots were created to replace the sequences of remaining words. The most frequent template was output for each cluster, leading to K templates being output for each set. Here, we set the value of the K to 20, that presented the highest F-score in our final evaluation. If any of the templates contained one slot between two lexical items, then the list of tweets for the set was said to contain a template. The length of the expression filling the slot could be longer than five words, different from the previous evaluation task of verb+preposition template.

This baseline was used to produce the baseline output, and also to create the gold standard explained as follows. First, using this baseline, we collected a set of 600 tweet sets (one set per Twitter account) of English tweets, and another set of 600 tweet sets of Japanese tweets: for every set, the template suggested by the baseline contained more than one slot, and we excluded a set that had short templates with only one slot. Then, trivial noisy tweets, such as replies and re-tweets together with those with URLs in the tweets were deleted or replaced automatically by using regular expressions. They are able to form (unwanted noise) templates, and they can affect performance, depending on their frequency of occurrence in the tweets.

After cleaning, we constructed two types of gold standard from this pre-processed data. The two annotatorsFootnote ⁸ manually scanned every tweet set, in which the candidate template is highlighted by the baseline method. First, every Twitter set is annotated with whether it contained a template or not. Second, among those which contained a template, we randomly chose hundred sets and annotated them with the templates; each account was annotated with multiple possible templates, that were found in many tweets included in the account.

This set of hundred sets is defined as Template-annotated corpora, and the rest is defined as Hand-classified corpora. Note that a set of the former always contains a template, whereas an account of the latter does not necessarily have one. Relatedly, since the baseline procedure is used to collect the data, the recall of the baseline system is 1.0.

Each set of tweets from the template-annotated corpora was annotated with a maximum of five templates, created by an independent human annotator (not one of the authors). For example, the set of tweets in the example above was annotated with the template:

A summary of the template-annotated and hand-classified data is shown in Table 1. Typical sources included news, weather and public information feeds. A set of tweets consisted of all tweets from a single source. The total size of the corpora was over three million tweets.

Table 1.

Summary information and statistics for the Twitter data-sets

It can be argued that the dataset is biased in favor of the baseline, since it was created using the baseline. Without use of a tool that gives a hint to human annotators wherein a tweet set contains a template, however, the annotation task was too difficult and time consuming. Since we cannot use the proposed method for this task, we used the baseline, even though the resulting comparison will be in favor of the baseline. However, as will be shown, the proposed method outperforms the baseline even on such data. Therefore, we believe that the evaluation serves to demonstrate the effectiveness of our approach.

We used thus constructed evaluation

Two types of experiment were performed. The first used all the 600 data both in English and Japanese. We call this experiment the Pattern Classification Experiment. The task is a straightforward classification task to identify whether or not templates exist in the tweets, and we therefore used the standard evaluation method of precision/recall/f-score to evaluate the performance. The results are shown in Table 2.

Table 2.

Template extraction results for all the 600 set of data

The precision of the baseline is 0.96 for Japanese and 0.93 for English, indicating that the heuristic used to extract the candidate template data was of high quality. Nonetheless, applying the proposed Relaxed SeqBDD method to this data was able to give respectable gains in both precision and f-score at a small cost in terms of recall. It is also clear from the table that Relaxed BDD is superior to the method based on the original SeqBDD in all respects.

The second experiment evaluated the quality of the templates that were actually extracted, using the Template-annotated corpora (hundred each in English and Japanese). We call this experiment the Pattern Extraction Experiment. Since the baseline outputs K templates, only the best K templates were considered also for SeqBDD methods. Similar to the previous work in Figure 9, these ranked lists were evaluated by MRR of the best ranked correct template appeared in the output list of length K. Here, in formula (1), Q = 200. If there are multiple correct templates extracted, the reciprocal of the best rank is used to obtain the average, and if no correct template was found, then the rank is set as ∞.

The results are shown in Figure 10, English and Japanese altogether. There are three lines: black, orange dashed and red solid, representing the baseline, SeqBDD and Relaxed SeqBDD, respectively. Each line shows the values of MRR and R, while varying K. In all cases, the recall of the Relaxed SeqBDD was considerably higher that the SeqBDD method, this was expected and was caused directly by the relaxation of the algorithm allowing it to be applicable to more cases in the data. There is of course a trade-off with MRR, although this trade-off proved to not to be too detrimental, and in fact for all values of K greater than 3, the Relaxed SeqBDD achieves higher levels of both MRR and recall than the other methods.

Fig. 10.

Extraction of templates from twitter using template-annotated corpora.

The end-to-end runtime performance, from raw text until the final output for the proposed SeqBDD method was 37.3 sec using 836 MB of memory for a single tweet-set, the Relaxed SeqBDD method took 210.5 sec and used 1.4 GB, whereas the baseline took 30.9 sec and used 2.3 GB.

Some example extraction results for the Twitter data are shown in the Appendix B. The patterns are successfully acquired for Twitter examples like B.1 or B.2, where the pattern frame structure is solid, and the length of the expression filling the slot is short.

On the other hand, the algorithm fails to extract the correct patterns when the length of expression filling the slot is large, such as in the example of B.4, due to the fact that the Sequence BDD graph becomes too sparse. For example, patterns such as ‘How to * (URL)’ or ‘Outsourcing Human Resouces * (URL)’ could have very long expression in *. Moreover, if the pre-processing of POS tag fails, then all that follows also fails, as shown in the example of B.3. The development of methods for overcoming these issues remains future work.