1 Introduction
A grammar induction algorithm must infer sentence structures. If the algorithm is unsupervised, this structure can be discovered by identifying patterns that occur at a higher frequency than pure chance would explain (e.g., by randomly shuffling the texts). A common procedure in unsupervised grammar induction (UGI) (Klein and Manning Reference Klein and Manning2005; Bod Reference Bod2006Reference Bod2007) is to start off from the part-of-speech (PoS) tag sequences assigned to the words in the texts to be parsed. This amounts to preprocessing the texts for PoS tagging – something that can be achieved either in a supervised (achieving approximately 97% accuracy) or, if necessary, an unsupervised manner. We follow the same scheme in this work, so the goal of our method will be to identify statistical patterns of PoS tags that provide us with sufficient clues to infer, to a certain extent, the shape of parse trees.
Parse trees are made of constituents. Each node in the parse tree corresponds to a constituent. The tree leaves identify the PoS tags. Thus, constructing the parse tree of a sentence is equivalent to identifying all its constituents. Constituents corresponding to nodes from which only leaves hang define a class that plays a special role in our algorithm. Accordingly, we will refer to them as base constituents throughout this paper.
Our proposal for unsupervised grammar induction is heuristic. It relies upon a few empirical observations about particular patterns in parse trees which help in the task of identifying constituents. For instance., most sentences exhibit a parse tree that splits off at the root into two main branches. Also, PoS tag patterns corresponding to constituents occur in texts at a frequency higher than they would do in a random sequence of PoS tags. Certain lexical categories of words (which depend on the language we are parsing) appear much more frequently than others at the beginning or at end of the base constituents. Other lexical categories often appear in specific patterns. For instance, two common patterns are EC 1 (or C 1E, depending on the language) or C 1EC 2, where E stands for a PoS tag and C 1 and C 2 for two constituents. The PoS tags E involved in these patterns will prove key to inferring the parse tree.
In order to flesh out these observations, consider the example trees shown in Figures 1–3, extracted from the Wall Street Journal (WSJ) section of the Penn Treebank (Tables 11 and 12 in Appendix A lists the PoS tags used to annotate this corpus and the internal tags appearing in the examples, respectively. We can observe that the pattern DT ⋅⋅⋅ NN*Footnote 1 appears in all three examples. The fact that this pattern occurs at an unusually high frequency in the corpus suggests that it may identify a constituent. Another important observation is that some PoS tags often appear inside these constituents – e.g., JJ* tends to appear between DT and NN* (see Figure 3). Also noticeable is the fact that certain PoS tags tend to divide the sentence into two main parts – e.g., VBD in Figure 1, and VBP in Figure 3. Moreover, some PoS tags – frequently including those that divide sentences – play the role of tag E in constituents with the pattern EC 1. This is the case for VBD in Figure 1 – which appears twice: in the first occurrence it precedes the sequence DT NNP NN VBD NN NNP, and in the second occurrence, the sequence NN NNP, for PRP and VBD in Figure 2, and for VBP in Figure 3. Finally, tags such as CC in Figure 3 are the E in the pattern C 1EC 2.
Parse tree for the sentence Esso said the Whiting field started production Tuesday from the Penn Treebank.
Parse tree for the sentence In September, she pleaded guilty and paid a $ 500 fine from the Penn Treebank.
Parse tree for the sentence Scoring High and Learning Materials are the best-selling preparation tests from the Penn Treebank.
Our approach is based on an iterative procedure. We first detect some constituents by statistical analysis and then use this information to identify PoS tags that are typically found in the kinds of common patterns mentioned above. This in turn helps us detect the remainder constituents. In order to test this procedure, we have applied it to different corpora annotated with PoS tags. More precisely, and for the sake of comparison, we have adopted the Klein and Manning (Reference Klein and Manning2005) evaluation setting for the problem, as well as those of Bod's (Reference Bod2006, Reference Bod2007) approach. As far as we know, these or some of their extensions using the same experimental setting, provide the best results obtained so far for unsupervised grammar induction for constituent grammars using a monolingual corpus and PoS-tagged corpora. As in these two cases, the grammar we obtain does not specify the left-hand side of the rules, only the shape of the tree (i.e., the PoS tag sequences defining constituents). Also similar to them, we have used the Penn Treebank (Marcus, Santorini and Marcinkiewicz Reference Marcus, Santorini and Marcinkiewicz1994) as one of our test corpora, employing the syntactic annotations that it provides only for evaluation purposes.
An important remark is that similar patterns are common to many languages. This means that our approach should (to a large extent) be able to parse sentences irrespective of the language. Accordingly, we have tested our model with different languages belonging to different families and showing different degrees of freedom in word order – namely English, German, Spanish, Italian, Chinese, and Hebrew. The results obtained for all of these are surprisingly good, given the simplicity of the approach, and suggest that searching for statistical patterns may be a powerful tool to infer grammars when little is known about the underlying language.
The rest of the paper is organized as follows. In Section 2, we review some current approaches to unsupervised grammar induction. In Section 3, we propose our approach based on PoS tag patterns to identify PoS tag classes, which will later allow us to parse sentences. In Section 4, we provide the procedure for constructing a parse tree, given the PoS tag classes appearing in the sentence. In Section 5, we report and discuss the results obtained for different languages and compare them to those obtained with other systems. Finally, we put our approach in context and provide directions for future work in Section 6.
2 Related works
The aim of grammar inference is to learn a grammar to model the structure of the sentences of a language. There are two main approaches to this task: supervised and unsupervised. In supervised grammar induction, the grammar and the parsing model are obtained from a treebank of syntactically annotated sentences. There are quite a few works following this approach. In recent works (Petrov Reference Petrov2010), the level of performance has been risen up to 91.8%.
Our work deals with unsupervised empirical grammar induction, though, so we will mainly focus on the work made within this category. An interesting system has been proposed by Carroll and Charniak (Reference Carroll and Charniak1992), who use the Inside-Outside (IO) algorithm to improve the initially calculated estimates of the probabilities of rules, rejecting those with a probability below a small threshold. The authors investigated the reasons for the limited quality of the results achieved and noted that the grammar obtained was very sensitive to the initial estimates for probabilities.
Stolke and Omohundro (Reference Stolcke and Omohundro1994) induced a grammar by incorporating samples as ad hoc rules to a working grammar. Subsequently, elements of the model are merged to achieve generalization and a more compact representation. The choice of what to merge and when to stop is governed by the Bayesian posterior probability of the grammar given the data. The authors conclude that the method requires some refinements to be successfully applied to natural language grammars.
Clark (Reference Clark2000) proposes an algorithm to learn a phrase-structure grammar from tagged text. It clusters sequences of tags together based on local distributional information, and selects clusters that satisfy a mutual information criterion. Sets of tag sequences can be clustered together based on the contexts they appear in. Results show that this criterion selects linguistically plausible constituents.
Klein and Manning (Reference Klein and Manning2005) borrow the main ideas from Carroll and Charniak's (Reference Carroll and Charniak1992) work creating a model called Constituent-Context Model (CCM). The model is intended to be applied to PoS tagged texts without considering punctuation marks, and uses the Expectation-Maximization (EM) algorithm to maximize the likelihood of contiguous subsequences of PoS tags. The system has been tested on English, German, and Chinese Treebanks, but only for sentences of up to ten words. The model relies on the idea that long constituents usually have short equivalents in the same contexts, an idea that is also a cornerstone in our proposal. The system achieves an F-measure of 71.1% for English, 64.2% for German, and 36.8% for Chinese. Recently, Golland, DeNero and Uszkoreit (Reference Golland, DeNero and Uszkoreit2012) have proposed Log-Linear CCM (LLCCM), a log-linear variant of CCM, which aims to avoid a drastic drop in performance for long sentences.
An alternative system for unsupervised parsing is Bod's (Reference Bod2006) Unsupervised Data-Oriented Parsing (U-DOP). Bod (Reference Bod2006) points out that Klein and Manning's (Reference Klein and Manning2005) approach neglects dependencies that are non-contiguous by using an ‘all-substrings’ approach. U-DOP directly models structural as well as lexical context without constraining any dependencies beforehand. Subtrees can model both contiguous and non-contiguous lexical dependencies. Accordingly to Bod (Reference Bod2006), this all-subtrees approach is a generalization of Klein and Manning's (Reference Klein and Manning2005) all-substrings approach. Bod's system (Reference Bod2006) achieves an F-measure of 82.9% for the English corpus WSJ10 used by Klein and Manning (Reference Klein and Manning2005). Since it generates a large amount of subtrees for each phrase, the system becomes impractical for longer sentences. As a result, Bod (Reference Bod2007) describes a method that generates far fewer subtrees for each phrase, but at the cost of lowering the performance. This new method achieves 77.9% on the WSJ10 corpus.
Other related works are those of Magerman and Marcus (Reference Magerman and Marcus1990) and van Zaanen (Reference van Zaanen2000). These works aim to learn a representation of the constituent boundaries of the language. The work by Magerman and Marcus (Reference Magerman and Marcus1990) uses mutual information statistics, while the work by van Zaanen (Reference van Zaanen2000) is based on the alignment of sentences sharing some part.
Seginer (Reference Seginer2007a) has proposed an unsupervised parser from plain text which uses a local, greedy parsing algorithm. The parser is incremental and uses a new link representation for the syntactic structure. This representation allows a prefix of an utterance to be parsed before the full utterance has been read. This parser improves on previously published results for unsupervised parsing from plain text, achieving an F-measure of 75.9% for the English corpus WSJ10.
Recently, Spitkovsky, Alshawi and Jurafsky (Reference Spitkovsky, Alshawi and Jurafsky2011) have achieved significant improvement over their base model for unsupervised dependency parsing by taking the advantage of punctuation marks and capitalization (Spitkovsky et al. Reference Spitkovsky, Alshawi and Jurafsky2012). These results have been taken into account in the design of our method for constituent parsing.
The approach we propose in this work differs in many aspects from the above-described works. To begin with, our algorithm is not constrained to generate binary trees. Furthermore, our method does not rely on any machine learning algorithm, but on a number of heuristics that allow us to extract general patterns present in many languages. Preliminary results of this approach were presented in Santamaría and Araujo (Reference Santamaría and Araujo2010), showing the potential of the method in a restricted version which only uses two of the PoS tag classes that are identified by their role in the patterns (namely, separators and delimiters; see below). Clark's (Reference Clark2000) idea of contexts is close to our idea of separators, and plays a similar role, although these are identified in a different manner. Besides, the clusters of PoS tag sequences determined by a particular context are also somehow related to our idea of delimiter, since they represent the set of PoS tag sequences with the same limits. The current work extends that initial procedure by adding new PoS tag classes (such as those prone to divide sentences into two main parts, and joiners, a particular kind of separators linking two similar sub-structures). We have also enlarged the model by considering punctuation marks. Finally, we have evaluated the model for different languages in order to assess its generality.
3 The PoS tag pattern method for unsupervised parsing
We have used the empirical observations described in the Introduction to elaborate a deterministic procedure to parse sentences of a PoS-tagged text. The procedure is implemented in two algorithms: In the first one a few sets of tags are identified according to their role in different patterns; in the second one these tags are used to produce parse trees. In this section, we will describe how to construct the first algorithm (the pseudocode of which appears in Figure 4). The second algorithm is described in Section 4.
Algorithm for the induction of PoS tag classes. The separator category sec is a set of PoS tags of T beginning with the same letters, if any, or a single separator otherwise. N is the number of sentences in the corpus. sec are the PoS tags in S(separators) sharing the same prefix. This optimization is only applied to those sets in which the PoS tags of each category share the first letter. max is the PoS tag from SC_pred appearing most often immediately following the safe constituent sc.
There are four relevant classes that we need to identify: delimiters, separators, joiners, and punctuation marks. Delimiters and separators are mutually exclusive. Joiners are a subset of separators, and, of course, punctuation marks do not overlap any other class. This classification is not exhaustive. There remain tags that play no special role.
We call delimiter any PoS tag occupying the first or last position of a base constituent. For instance, DT and NN in Figures 1 and 2, and DT and NNS in Figure 3, are delimiters.
A separator is any PoS tag T which appears in patterns of the form TC 1 or C 1T, with C 1 any constituent. Tags such as VBD in Figure 1 (in its two appearances), PRP and VBD in Figure 2, or VBP in Figure 3, are examples of separators. If the separator plays the role of the head of the sentence (i.e., splits the sentence into two main parts), we refer to it as predominant separator; e.g., VBD in Figure 1 or VBP in Figure 3 are predominant separators.
A joiner is any PoS tag T which appears in patterns of the form C 1TC 2, with C 1 and C 2 two arbitrary constituents. A joiner in the trees given in Figures 2 and 3 is CC.
Finally, we interpret any character other than alphanumeric characters as punctuation marks. Its identification is therefore a trivial matter.
The problem we face now is to identify tags that are likely to play the role of delimiters, separators, and joiners in the texts to be parsed.
The cornerstone of our method is to identify at least one sequence of PoS tags that forms a constituent with high probability. We achieve this by looking throughout the corpus for the most frequent pair of PoS tags, LscRsc, to which we refer as the safe constituent (sc). This automatically identifies Lsc and Rsc as two delimiters. This empirical assumption is based on the observation that in all corpora that we have examined, the most common sequence of length two is a noun phrase.
According to Klein and Manning (Reference Klein and Manning2005), long constituents often have short, common equivalents that appear in similar contexts. It is thus reasonable to assume that occurrences of these in the corpus correspond to constituents fitting the pattern Lsc ⋅⋅⋅ Rsc. Certainly not all of them, but our guess is that this happens more often than not. Under this hypothesis we can identify separators and new delimiters in relation to their occurrences relative to these two delimiters.
Actually, following Cohen and Smith (Reference Cohen and Smith2009) we make a small refinement which improves performance: We extend the definition of sc by generalizing its pair of PoS tags to the pair of coarse-grained PoS tag categories which they belong to. For instance, (DT, NN) is usually found to be the most frequent pair of PoS tags in English corpora; thus, sc is generalized to (DT, NN*), i.e., a determiner and any noun. We only do this when the corpus annotations identify the PoS tag categories by assigning (as in this example) the same initial letters to all PoS tags belonging to it (most corpora use this convention). Otherwise we stick to the found pair of most frequent PoS tags.
3.1 Detecting separators and delimiters
Given a PoS tag E, we look for all occurrences of the two pairs ELsc and LscE (likewise ERsc and RscE). Either there is a bias toward one of the two pairs or there is no bias. If ELsc (likewise RscE) appears significantly more often, then we classify E as a separator. If the difference is not significant then we classify E as a delimiter. The rationale for this is as follows. Arguably, most occurrences of Lsc and Rsc in the text will correspond to a constituent of the form Lsc … Rsc. Hence, if ELsc (respectively RscE) appears significantly more often than LscE (respectively ERsc), this means that E tends to form the pattern EC (with C = Lsc … Rsc) that identifies a separator. Delimiters, on the other hand, can be found at any side of Lsc or Rsc because base constituents may be a part of or adjacent to another constituent. So if both sequences, ELsc and LscE (respectively RscE and ERsc), appear a comparable number of times, then it is likely that E is a delimiter.
Most delimiters in English corpora are either determiners (DT) or nouns (NN*), so the sc almost exhausts the delimiter class. There are a few others, though, such as possessive ending (POS). As a matter of illustration, POS is often found in the Penn Treebank ending a base constituent, e.g., (NP (NN today) (POS's)), but sometimes this constituent precedes a noun, e.g., ((NP (NP (DT the) (NNS funds) (POS’) ) (NNS investments)), therefore neither pattern, POS NN* nor NN* POS, is expected to show up more often than the other. This identifies POS as a delimiter.
More formally, the precise procedure we have implemented to assess whether a PoS tag E is a separator or a delimiter is the following. For a given PoS tag E we computeFootnote 2 #(E Lsc), #(Lsc E), #(E Rsc), and #(Rsc E). We refer to ELsc and RscE as the outer pairs, and LscE and ERsc as the inner pairs – implying that Lsc and Rsc are, respectively, the left and right ends of a constituent. We define the determining side of E (denoted ds(E)) as the tag, Lsc or Rsc, showing the largest difference in the number of occurrences between its inner and outer pairs. Finally, the similarity is analyzed by checking whether the ratio
\begin{equation*}
rt = {\#(\text{outer pair of }ds(E))}/{\#(\text{inner pair of }ds(E))}
\end{equation*}
is sufficiently close to unity (more precisely in the interval (3/4, 4/3)).
Now, if 3/4 < rt < 4/3, then we consider that the ‘inner-outer bias’ is not significant (less than 3:4) and thus classify E as a delimiter. If 4/3 < rt, then the bias toward the outer pair is considered significant and we classify E as a separator. Finally, if rt < 3/4, the bias toward the inner pair is significant, meaning that E is just a part of the constituent.
We have checked thresholds as large as 1:2 finding that the results are little affected or not at all regardless of the corpus or the language. Therefore, even though the choice 3:4 looks arbitrary, its precise value is not very relevant. This probably means that whenever there is a bias, it is strong.
In the algorithm (Figure 4) we study the similarity by checking the rt ratio corresponding to each case. We introduce the predicate
\begin{equation*}
sim(E_1, E_2) = \mbox{ \rm true iff } \#(E_1\,E_2)/\#(E_2\,E_1) \in [3/4, 4/3]
\end{equation*}
which is true if the difference in the number of occurrences of the PoS tag pairs E 1E 2 and E 2E 1 is not significant. A tag E is then considered a separator if the predicate
\begin{eqnarray*}
&\displaystyle sep(L_{sc}, E, R_{sc}) = ((ds(E)=L_{sc}) \wedge ( \lnot sim(E, L_{sc}) \wedge \#(E, L_{sc}) > \#(L_{sc}, E))) &\\
& \displaystyle \vee ((ds(E)=R_{sc}) \wedge (\lnot sim(E, R_{sc}) \wedge \#(R_{sc}, E) > \#(E, R_{sc})))&
\end{eqnarray*}
is true, i.e., if the determining side is Lsc, the number of occurrences on both sides of this boundary is not similar, and E appears more often to the left than to the right of Lsc, or if the determining side is Rsc, the number of occurrences on both sides of this boundary is not similar, and E appears more often to the right than to the left of Rsc.
On the other hand, E is considered a delimiter if the predicate
\begin{equation*}
delim(L_{sc}, E, R_{sc}) = ((ds(E)=L_{sc}) \wedge sim(E, L_{sc})) \vee ((ds(E)=R_{sc}) \wedge sim(E, R_{sc}))
\end{equation*}
is true, i.e., if the determining side is Lsc and the number of occurrences of E on both sides of Lsc is similar, or if the determining side is Rsc and the number of occurrences of E on both sides of Rsc is similar.
Repeating this procedure with every PoS tag we have obtained the sets of separators and delimiters for WSJ. They are shown in Table 1. In this case, determiners and nouns are classified as delimiters, and prepositions and verbs are classified as separators. Although this is common to most tested corpora, we have found some differences. For instance, some verbs (VAIMP, VMINF, VMPP) are classified as delimiters in the German corpus NEGRA. On the other hand, other PoS tags are more heterogeneous; e.g., adverbs are in the separator class in the Penn Treebank, but appear distributed between the two classes in the Spanish UAM Treebank.
Separators and delimiters obtained for the WSJ corpus. Others correspond to the remaining PoS tags, excluding punctuation marks
Delimiters can be either right or left delimiters. Left delimiters tend to appear at the first position, whereas right delimiters tend to appear at the last position. To determine the type of delimiter L, we find a tag E such that EL is the most frequent combination and a tag E′ such that LE′ is the most frequent combination. If #(EL) > #(LE′), then L is a right delimiter; otherwise it is a left delimiter. Table 2 shows the results obtained for WSJ10, the type of the delimiter appearing in the last column.
Preferred direction in which each delimiter clusters in WSJ10. The first column corresponds to the delimiter, the second column to the most frequent sequence comprising the delimiter and a tag on its right, the third column to the frequency of this sequence, the fourth column to the most frequent sequence of the delimiter and a tag on its left, the fifth column to its corresponding frequency, and the last column to the resulting direction. For NNP, for which the frequency of the most frequent tag to the right and to the left are the same, we have searched for the second most frequent sequence to choose the grouping direction: (NNP VBZ)(454) and (IN NNP)(540). Accordingly, the direction of preference for NNP is the right
The process to identify delimiters and separators appears at the beginning of the induction algorithm in Figure 4 (lines 4–21).
3.2 Identifying the main parts in sentences
In general, the head of the sentence is a separator because in most cases it triggers new levels of the tree. A sentence may, however, contain more than one separator, so a procedure is needed to discriminate which one acts as head of the sentence. To this end we have introduced a hierarchy among the separators that allows us to decide which one is the main separator of a sentence.
We first define the predominant separator class, SC_pred, as the class of separators (excluding punctuation marks) whose number of occurrences in the corpus is larger than N – the number of sentences in the corpus. Actually, we do not consider separators independently, but group those belonging to the same lexical category (e.g., VB* if we are considering verbs). The number of occurrences of a separator category sec is then counted as
\begin{equation*}
\#sec = \sum _{s \in sec} \#s.
\end{equation*}
Grouping by lexical category is only done for corpora that annotate PoS tags using the same initials if they belong to the same category (most corpora are annotated this way). Otherwise each PoS tag is considered separately. Thus, the predominant separator class is defined as the set SC_pred = {sec: #sec ≥ N}.
As expected, several languages and corpora used in this work do have a predominant separator category. In the English corpus WSJ10, 9,114 out of the 9,799 (93%) occurrences of the category VERB (VB, VBD, VBG, VBN, VBP, and VBZ) are separators. Analogously, in the Spanish corpus UAM10, 466 out of the 497 (93.76%) occurrences of the VERB category (VPAST, VPRES, VPART, VINFINITE, VIMPERFECT, VFUT, VCOND, and VNO) are separators. The same is found in the Italian and the German corpora. On the contrary, for the Hebrew and the Chinese corpora SC_pred is empty, hence this technique cannot be used to identify the head of sentences.
For corpora with a nonempty SC_pred and sentences with only one separator in this class, the head of the sentence is immediately identified as this separator. However, many sentences have more than one predominant separator, so establishing a hierarchy within SC_pred will help decide which one should be identified as the head of the sentence. Again we resort to sc to build this hierarchy.
It is an empirical observation that holds in all analyzed corpora that sc tends to appear before the predominant separators. This makes sense for the English corpus because sc is a noun phrase, but is also valid for other languages. The hierarchy is therefore determined by the frequency of appearance of the elements of SC_pred after sc in the sentences of the corpus – the more frequent a predominant separator, the higher in the hierarchy. Thus, if a sentence contains more than one separator in the SC_pred class, the head of the sentence is that higher in the hierarchy.
There is a small refinement that we still need to deal with. Separators in the SC_pred class may have special PoS tags associated to them. This is the case of auxiliary verbs, for instance. We call these tags partners of the predominant separators. These are detected in two steps. The pseudocode in Figure 5 represents the proccess for identifying partners. In the first step, we find the PoS tags that most frequently appear preceding each separator of SC_pred (lines 1–3). In the second step, we remove from the partners those tags whose appearance may be due just to pure chance. This is ascertained by checking whether the tag also appears before – but not immediately before – the headFootnote 3 of the sentence (lines 4–7).
Identifying partners. T stands for the set of PoS tags.
In the English corpus, EX, MD, PRP, TO, WDT, and WP are the PoS tags that most often precede a predominant separator. Except for TO and MD, these are also found preceding the head of the sentence; therefore the only partners of WSJ are TO and MD.
Partners are included in the hierarchy, along with the predominant separator they accompany, using the same criterion as with the ordinary elements of the SC_pred class – counting the number of occurrences after sc. Table 3 shows the hierarchy obtained for WSJ. Levels in this hierarchy are determined by the order of magnitude of the number of occurrences of the tag after the safe constituent. Level 1 in Table 3 corresponds to hundreds of occurrences, whereas level 2 corresponds to tens.
Hierarchy of predominant separators used to determine the tag that divides sentences. Vx stands for other PoS tags beginning with V at the same level
The process to identify the hierarchy of predominant separators appears in the induction algorithm (Figure 4, lines 22–34).
3.3 Detecting joiners
Joiners are a special type of separators that not only trigger a new level in the tree but also join pieces of information at the same level. This is the case of CC in Figures 2 and 3. We expect to find similar patterns on both sides of a joiner, and this feature identifies them.
We assume that a particular PoS tag is a joiner if it tends to be preceded and succeeded by the same tag. In particular, the algorithm for determining whether tag X is a joiner searches for sequences of three tags of the form YXZ in the corpus and checks whether those with the form YXY are more than 50%. This test appears in the induction algorithm in Figure 4 (lines 35–41).
The set of joiners detected for the English corpus WSJ comprises only CC.
3.4 Punctuation marks
The presence of punctuation marks in sentences can provide important clues to the underlying structure. In fact, Spitkovsky et al. (Reference Spitkovsky, Alshawi and Jurafsky2011) have observed a strong connection between English punctuation and phrase boundaries in the Penn Treebank. They used this link between punctuation and constituent boundaries to approximate parsing by treating inter-punctuation fragments independently, obtaining an important improvement in unsupervised dependency parsing. We have also considered punctuation in our patterns definition.
We distinguish two different groups: Single punctuation marks – such as the comma, semicolon, and colon, and double punctuation marks – such as quotations, parentheses, and brackets. Again, we perform an automatic search for this class of PoS tags. We check for non-alphanumeric symbols appearing in the corpus and mark the positions of the sentence where they appear. For any identified punctuation mark we check whether it has a complement, i.e., another punctuation mark appearing in a similar number of sentences.Footnote 4
The process to identify punctuation marks appears at the end of the induction algorithm (Figure 4, lines 42–47).
The set of punctuation marks detected for the English corpus WSJ is ” “ ’ ‘ # $ . , :.
4 Parsing sentences with PoS tag classes
Once the PoS tags have been classified, they can be used to parse sentences. Parsing a sentence starts with a preprocessing step which chops it into segments. To do this we first check whether the sentence has a head. It does if it contains at least one predominant separator (i.e., a separator in the SC_pred class; see Section 3.2). If there are more than one, the head is the one with the highest rank in the hierarchy defined within the SC_pred class. If there is a head, the part of the sentence from the beginning to the head (excluded) is identified as a segment, and the part from the head (included) to the end as another segment. If there is not a head, this division of the sentence is not applied. On top of that, any sequence of PoS tags appearing between pairs of punctuation marks is also identified as a segment.Footnote 5 Segments are our first constituents, and the parsing proceeds segment-wise.
The parsing algorithm is detailed in Figure 6. We first look for predominant separators (separators in the SC_pred class), including possible partners. If there is one, we identify it as the head of the sentence (lines 1–7). If there is more than one, we resort to the SC_pred hierarchy and identify the top one as the head of the sentence. If the sentence has a head, we divide it into two segments as described above.
Parsing algorithm based on the PoS tag classes, assuming a right-branching structure (separators are expected to appear on the left of the constituents). The approach is also valid if we assume left-branching structure. Segments are sequences of PoS tags that are parsed separately.
In parsing sentences we assume that any PoS tag sequence inside a double punctuation mark is another phrase. In this case we apply the same procedure as for any other sentence. Otherwise, the punctuation marks are ignored. The first two commas, if any, are also considered double punctuation marks, provided the head of the sentence does not appear in between. Accordingly, we check for the presence of paired punctuation marks. Any pair of these identifies a new segment. Segments are parsed separately.
Next, we use the separators to identify further constituents (lines 9–12), which are then refined by identifying the delimiters with left and right preferred directions (lines 13–15). Finally, we identify the joiners and, if necessary, adapt the tree structure to them (lines 16–28).
For each sentence, the algorithm described in Section 3 runs along the sequence of its n PoS tags to detect separators, delimiters, etc. This process requires O(n × |T|) steps, |T| being the size of the PoS tag set. The constituent identification algorithm described in this section takes O(n 2) steps, because for each position in the sentence the algorithm must find the end of the corresponding constituent. The scope of joiners is decided after this constituent identification phase by searching for similar constituents at both sides of the joiner, deleting some previous constituents and forming a new one when necessary. The computational cost of this is O(3n 2). The whole algorithm described in this section is thus O(n 2). Since sentences are usually short (n hardly exceeds 40), the algorithm turns out to be very efficient.
As of space requirements, the algorithm only needs to store the PoS tag sequence, the role of each PoS tag, and the identified constituents. This simply requires an n × n table.
A running example will illustrate how the parsing algorithm works. Consider the sequence of PoS tags corresponding to the WSJ10 sentence The merged firm will carry Norris McLaughlin's name, namely:
DT VBN NN MDVB NNP NNP POS NN
Predominant separators appear in boldface. The SC_pred hierarchy determines that MD Vx – which includes a partner – is above VBN; accordingly, MD is the head of the sentence, and hence the dividing tag:
[DT VBN NN] [MDVB NNP NNP POS NN]
The next step is to find additional separators not in the SC_pred class, if any, and use all separators to further divide the sentence. For instance, VBN yields two new constituents: the sequence from VBN (included) to the end of the segment [VBN NN], and the sequence in between VBN and MD – the next separator – [NN]. The same is done for each separator, so we end up with:
[DT [VBN [NN]]] [MD [VB [NNP NNP POS NN]]]
We next seek the delimiters (underlined in the sentence):
[DT [VBN [NN]]] [MD [VB [NNPNNPPOSNN]]]
In this case, all the delimiters of the last constituent have preferred direction right, according to Table 2. Since NNP belongs to sc, [NNP NNP POS] is identified as a constituent and [NN] as another one. This leads to:
[DT [VBN [NN]]] [MD [VB [[NNP NNP POS] [NN]]]]
Figure 7 compares the tree resulting from applying our algorithm to this sentence with that provided by the Penn Treebank. We can see that both trees are almost identical, with the only exception that our algorithm considers that both The merged firm and merged firm are constituents, while the tree in the Penn Treebank only considers that The merged firm is a constituent.
Parse tree for the sentence The merged firm will carry Norris McLaughlin's name, according to (a) our proposal, and (b) from the Penn Treebank.
5 Experimental results
The system – the code is publicly available at http://nlp.uned.es/~jsant/ – has been evaluated against the gold-standard trees provided by the treebanks. Our constituents are not assigned any class name (e.g., noun phrase, verb phrase, etc.) as in the treebanks. The comparison therefore ignores class labels, considering only groups of tags. The results provided by Klein and Manning (Reference Klein and Manning2005), Bod (Reference Bod2006), and Golland et al. (Reference Golland, DeNero and Uszkoreit2012) have been our reference, as they are also designed for constituent grammars using PoS-tagged corpora. For the sake of comparison, we have evaluated our algorithm with the same corpus, the Penn Treebank, so we can readily test our results against the measures reported in those works.
The most common measures (Abney et al. Reference Abney, Flickenger, Gdaniec, Grishman, Harrison, Hindle, Ingria, Jelinek, Klavans, Liberman, Marcus, Roukos, Santorini and Strzalkowski1991) used to evaluate the quality of an induced grammar or a parsing – and those we have employed in this work – are precision, recall, and their harmonic mean (F-measure). Note that in our case these measures deliberately ignore the labels assigned to the parse tree (which are not a product of our algorithm).
5.1 Evaluation for different languages
For English language, we have used the Wall Street Journal section of the Penn Treebank, containing 49,208 sentences, but we have also applied our algorithm to other corpora in different languages. To be precise, we have tested it with the following:
• The UAM Spanish (Romance language) Treebank (Moreno et al. Reference Moreno, Grishman, Lopez, Sanchez and Sekine2000), containing 1,501 syntactically annotated Spanish sentences collected from the online edition of Spanish newspapers.
• The German (Germanic language) corpus NEGRA (Skut et al. Reference Skut, Krenn, Brants and Uszkoreit1997), with 20,602 sentences from German newspaper texts.
• The Italian (Romance language) corpus TUT (Lesmo, Lombardo and Bosco Reference Lesmo, Lombardo and Bosco2002), containing 2,860 Italian sentences collected from different sources.
• The HTB corpus (Sima’an et al. Reference Sima’an, Itai, Winter, Altman and Nativ2001), a Modern Hebrew (Semitic language) Treebank with 6,501 sentences from Hebrew press sources.
• The Chinese Treebank 7.0 (Xia et al. Reference Xia, Palmer, Xue, Okurowski, Kovarik, dong Chiou, Huang, Kroch and Marcus2000) in Mandarin Chinese (Chinese language family), with 51,447 sentences from Chinese newswires, magazine news, various broadcast news and broadcast conversation programs, web newsgroups, and weblogs.
These languages not only belong to four different families but also present different types of morphology and degrees of freedom in the word order.
Regarding morphology, although all languages are mixed types, some of these fit best into one category than into another. Most Indo-European languages, including Spanish, Italian, and German, are considered synthetic, as they form words by affixing a given number of dependent morphemes to a root morpheme. Chinese is the usual model of analytic language, as it tends to be uninflected. Hebrew grammar is partly analytic, expressing such forms as dative, ablative, and accusative using prepositional particles rather than grammatical cases. However, inflection plays a decisive role in the formation of verbs and nouns. English is moderately analytic (more analytic than other Indo-European languages).
Spanish and Italian word order is much more flexible than that of English. In Spanish, changes in the subject-verb-object order are very frequent and common in every day writing. In German, word order is also less rigid than in English. In main clauses the inflected verb has position 2. In subordinate clauses the verb appears at the very end. The Mandarin Chinese object has a great deal of flexibility. It usually appears after the verb, but other frequent possibilities are before the verb, before the subject, or is even omitted. A specific feature of Chinese is that verbs can become nouns without undergoing any sort of change. In most cases, the order of the words in Hebrew does not affect the meaning. Hebrew sentences do not have to include verbs, and the verb to be in present tense is omitted. Unlike the verb to have in English, none of the possession terms in Hebrew is a verb.
Full corpora were used to extract the statistical patterns for classifying PoS tags. To test the parsing algorithm, though, some experiments were performed on restricted sets containing sentences up to ten words long for the sake of comparison with previous works (Klein and Manning Reference Klein and Manning2005; Bod Reference Bod2006; Bod Reference Bod2007) with a similar experimental setting, i.e., constituent grammars and PoS-tagged corpora. We will refer to these test sets as WSJ10, UAM10, NEGRA10, TUT10, HTB10, and CTB10, respectively. In addition, we also experimented with longer sentences (see Section 5.2). We have followed the convention from other unsupervised systems (Bod Reference Bod2006; Seginer Reference Seginer2007a) of using a test set that is a subset of the training set.
The performance of our model on a given language mainly depends on two factors: One is, of course, how well our underlying assumptions capture real linguistic in the language; but not less important is the particular annotation scheme followed in the analyzed treebanks. Our current model produces trees similar to those in the Penn Treebank (in their size and number of levels), while other treebanks use different conventions.Footnote 6 To be fair, a degrading in precision and recall due to annotation differences cannot be considered a drawback of the model. To circumvent this problem we have resorted to another measure: the average number of crossing brackets (CB) (Abney et al. Reference Abney, Flickenger, Gdaniec, Grishman, Harrison, Hindle, Ingria, Jelinek, Klavans, Liberman, Marcus, Roukos, Santorini and Strzalkowski1991). It counts the number of constituents that violate the boundaries of a constituent in the gold standard. Obtaining a low CB along with a low F-measure is an indication that the annotation scheme differs significantly from ours.
Table 4 shows the results obtained with our algorithm for the subsets of sentences having up to ten words using different corpora. The low CB obtained in all cases indicates a high performance of the proposed approach (on average, more than a half of the constituents do not have any crossing brackets). We observe that with the exception of Spanish, Hebrew, and Chinese, CB rates are below 0.5. In Spanish, the CB rate is slightly higher than 0.5, possibly due to a small corpus size. Still the system obtains good results even for the smallest corpora: Spanish (396) and Italian (563). A slightly lower level of precision for the German corpus (NEGRA) along with a low CB rate hints at differences in the annotation schemes. The second row for this corpus, NEGRA10(2), confirms this fact. It corresponds to the results annotating the verbal group separately in the trees produced by our system: the verb is not included in the verb constituent. We can see that this minor change improves the results significantly.
Performance results, in terms of crossing brackets (CB), unlabeled precision (UP), unlabeled recall (UR), and unlabeled F-measure (UF) obtained for different languages, considering sentences of up to ten words. The last two columns correspond to the average number of constituents per sentence in each data set, according to the gold standard (#C-GS) and as obtained with our method (#C-SEP). The languages are English (WSJ10), German (NEGRA10(1) and NEGRA10(2)), Spanish (UAM10), Italian (TUT10), Hebrew (HTB10), and Mandarin Chinese (CTB10). The second column shows the size of each corpus. In all cases we have considered only sentences with up to ten words from the corresponding corpus. NEGRA10(2) provides the results for NEGRA10 annotating the verbal group separately. Corpora sizes are numbers of kept sentences
Apart from German, which uses an annotation scheme rather different from ours, the poorest results are obtained for Hebrew and Chinese. Higher CBs obtained for these corpora suggest that some of the patterns that we have considered may not be meaningful for these languages. We have delved into these corpora to identify the reasons for these lower results. The first difference that we have found is the number of verbs that have been identified as separators in each corpus. In Hebrew and Chinese this number is smaller than the number of sentences, whereas in the other corpora it is larger. Therefore, the patterns we rely upon to identify heads of sentences are invalid for Hebrew and Chinese.
Another difference lies in the contribution of different patterns, shown in Table 5. In order to study the contribution of each pattern we have evaluated the performance of the system introducing these patterns one by one: first, only separators and delimiters (first column);Footnote 7 punctuation marks are then processed as special tags in addition to separators and delimiters (second column); next we add special processing for joiners (third column); and finally all patterns are introduced, including the predominant separator hierarchy (fourth column). The results for English, German, Spanish, and Italian improve significantly with the introduction of each new pattern – the only exception being the hierarchy of the predominant separator category for Italian. As a matter of illustration, the pattern related to punctuation marks improves the results for WSJ10 from 81.33% to 85.61% , and the pattern for joiners improves the results for TUT10 from 77.59% to 79.97% . These effects are much less noticeable for Hebrew and Chinese. We also observe that the predominant separator hierarchy pattern is not detected for Hebrew and Chinese. This result agrees with the presence of constructions in these languages in which the verb can be omitted.
Contribution to the F-measure of different patterns. The languages are English (WSJ10), German (NEGRA10(1) and NEGRA10(2)), Spanish (UAM10), Italian (TUT10), Hebrew (HTB10), and Chinese (CTB10). For the Hebrew and the Chinese corpora SC_pred is empty, hence this pattern does not apply. The numbers in parentheses indicate the decrease/increase percentage with respect to the original performance (1st column)
All in all, even for the languages with the lowest performance (Hebrew and Chinese), the results improve over those obtained by other models, as we will show below.
5.2 Comparison with other systems
We have compared our results with those obtained for the same corpus by Klein and Manning (Reference Klein and Manning2005) (constituent-context model), KM, Bod's (Reference Bod2006, Reference Bod2007) U-DOP and U-DOP* (a modification of U-DOP that can manage larger subtrees), and Seginer's (Reference Seginer2007a) incremental parser. Table 6 shows the comparison for WSJ10. Our results attain a higher value for the F-measure as well as more balanced recall and precision values.
Results (unlabeled recall, precision, and F-measure) obtained using our separator approach (first row), compared with those of Klein and Manning's (Reference Klein and Manning2005) (second row), Bod's (Reference Bod2006, Reference Bod2007) (third and fourth row), and Seginer (Reference Seginer2007a) (fifth row), for the WSJ10 corpus
We have also evaluated our system on longer sentences. Table 7 compares the unlabeled F-measure obtained using our algorithm with those of Bod's (Reference Bod2006, Reference Bod2007), Seginer (Reference Seginer2007a) , and Golland et al. (Reference Golland, DeNero and Uszkoreit2012) for sentences of up to forty words long. We can see that the longer the sentences, the worse the methods perform, although our method consistently outperforms the others for all lengths.
Unlabeled F-measure obtained for the WSJ corpus as test corpus for different sentence lengths: up to 10, 20, 30, and 40 words. The first row corresponds to our separator approach, the second row corresponds to Bod's (Reference Bod2007), the third row to Seginer's (Reference Seginer2007a), and the fourth row to Golland et al.'s (Reference Golland, DeNero and Uszkoreit2012)
Seginer (Reference Seginer2007a, Reference Seginer2007b) built the Common Cover Links (CCL) parser, an implementation of his proposal for unsupervised incremental parsing based on the common cover link representation of syntactic structure. Its being publicly available has allowed us to compare our results with those obtained with the CCL parser for all corpora that we have considered. Table 8 shows this comparison. For all corpora, our results improve over those of CCL. Furthermore, the improvement persists with increased sentence length. One should realize, though, that the CCL system parses plain text, while our system requires PoS-tagged text. According to Seginer's (Reference Seginer2007a) data, the CCL parser outperforms any other system that also parses plain text and achieves results close to those obtained by systems using PoS-tagged text, including U-DOP and DMV+CCM(PoS)Footnote 8 (Klein and Manning Reference Klein and Manning2004) when parsing WSJ10 and NEGRA10.
F-measure results obtained using Seginer's (Reference Seginer2007a) CCL model and the algorithm described in this paper (Sep.). Results are obtained for different languages – English (WSJ), German (NEGRA), Spanish (UAM), Italian (TUT), Hebrew (HTB), and Chinese (CTB) – and considering a test corpus containing sentences of up to 10, 20, 30, and 40 words long, as well as the whole corpus. The PoS tag classes used to construct our system are extracted from the whole corpus. These classes are then used to parse the sentences of all subsets of the corpus regardless of their length. Figures with only one significant digit have been taken from the Seginer's paper
Our system, implemented in Java on a PC Intel Core 2, parses the sentences efficiently, as shown in Table 9. The table also shows the execution times on the same computer corresponding to the CCL system (Fast Unsupervised Incremental parsing) by Seginer (Reference Seginer2007b), which performs a particularly efficient greedy parsing. We can observe that, although the CCL times are better – about an order of magnitude smaller – the execution time required by our system is still small enough to make the system useful. Our system is capable of parsing the largest corpus in a few minutes. For instance, the complete Chinese corpus CTB is parsed in six minutes and the English corpus WSJ in less than eight minutes.
Execution times for our system (Sep.) and CCL (Seginer Reference Seginer2007a). First column shows the considered corpus, and the number of sentences it is composed of; second column shows our system (Sep.) execution time in seconds; third column shows the number of sentences processed per second in our system; fourth column shows the CCL execution time; and the fifth column shows the CCL number of sentences processed per second
5.3 Analyzing the effect of the PoS tag set
The granularity of the PoS tag set affects the results. To investigate its influence, we have performed some experiments with other tag sets as well.
Table 10 compares the results of using both, a smaller PoS tag set and a set of PoS tags obtained in an unsupervised manner. For the smaller set of PoS tags, we have considered the coarse-grain tag set proposed by Petrov et al. (Das and Petrov Reference Das and Petrov2011; Petrov, Das and McDonald Reference Petrov, Das and McDonald2012) comprising only twelve universal PoS tags. The corresponding results appear in the central three columns of the table. The global F-measure is not very different from the one obtained with the original PoS tag set of each corpus. In some cases, such as English, German, and Spanish, results are slightly worse. In others, such as Italian, results remain nearly the same. Finally, in some cases, such as Chinese and Hebrew, results improve by increasing the PoS tag granularity.
Performance results, in terms of unlabeled precision (UP), unlabeled recall (UR), and unlabeled F-measure (UF) obtained for different sets of PoS tags, considering sentences of up to ten words. The languages are English (WSJ10), German (NEGRA10), Spanish (UAM10), Italian (TUT10), Hebrew (HTB10), and Mandarin Chinese (CTB10). The first three columns show the results for the original PoS tag set of each corpus. The second three columns show the results using Petrov et al.'s (Reference Petrov, Das and McDonald2012) coarse grain PoS tag set. The last three columns show the results for the PoS tag set provided by an unsupervised PoS tagger based on Gibbs (Gao and Johnson Reference Gao and Johnson2008) sampling. In all cases we have considered only sentences with up to ten words from the corresponding corpus
In addition, we evaluated the system using an unsupervised Hidden Markov Model (HMM) PoS tagging, estimated by means of a Gibbs sampling (Gao and Johnson Reference Gao and Johnson2008), which is publicly available.Footnote 9 The corresponding results appear in the last three columns of the table. We can see that, albeit the tagging precision has been significantly lowered because we have performed an unsupervised tagging of the sentences, the results are still valuable and similar to those obtained using Seginer's (Reference Seginer2007a, Reference Seginer2007b) approach, which was specifically designed for parsing plain text. In some cases, such as WSJ10 and NEGRA10, results are slightly worse than Seginer's (Reference Seginer2007a, Reference Seginer2007b), but they are clearly better for the rest of the corpora. These results should improve with the tagging precision.
6 Conclusions and future work
The proposed systems have achieved a competitive performance for different corpus. The upside of our proposal is that it can be applied to any language for which we have a PoS tagger. Another advantage is its efficiency in parsing sentences: Once we have obtained the PoS tag classes from a corpus, the procedure for parsing new sentences only requires identifying the different PoS tag classes that they contain in order to group them into constituents.
There are many directions in which we are planning to extend the present work. We are studying the way of adapting the algorithm to perform dependency parsing. We think that some of the PoS tag classes identified, such as the separators, can be an important clue for doing the transformation. We also consider the way of adapting the behavior of the algorithm to other families of languages. Besides, we are planning to check the results obtained when testing different languages in more similar conditions. This will imply a fully unsupervised configuration, including tagging, and using parallel corpora of the same size for training in all languages, or at least comparable corpora. Other aspect to study is the introduction of indeterminism in the method by considering probabilities in the selection of PoS tag classes. In this line, we could explore possible ways of taking advantage of small treebanks if available. We are also looking for a way to combine our system with the Expectation-Maximization approach to see whether Expectation-Maximization can improve the search of the less likely structures. Another point that can lead to some performance improvements is the introduction of some partial lexicalization, for instance, considering separately each element of some lexical categories, such as prepositions.
Acknowledgments
We would like to thank Prof. Yoav Seginer for making his parsing system publicly available and for supporting us in its use. We want to thank Prof. José A. Cuesta for his assistance with the writing of the manuscript. This work has been supported by the Spanish MICINN project Holopedia (Spanish Ministerio de Ciencia e Innovación (TIN2010-21128-C02) and the Universidad Nacional de Educación a Distancia (UNED) (2013-025-UNED-PROY). We also want to thank UNED's Vicerrectorado de Investigación for the editing service of the final version of the paper.
Appendix Tags used in the Penn Treebank examples
Alphabetical list of part-of-speech tags used in the Penn Treebank, used in our experiments
Internal tags used in the Penn Treebank examples
