{'fraction_non_alphanumeric': 0.029855086511898415, 'fraction_numerical': 0.014152086463432365, 'mean_word_length': 4.77013422818792, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploring the Spinal-STIG Model for Parsing French

We evaluate statistical parsing of French using two probabilistic models derived from the Tree Adjoining Grammar framework: a Stochastic Tree Insertion Grammars model (STIG) and a specific instance of this formalism, called Spinal Tree Insertion Grammar model which exhibits interesting properties with regard to data sparseness issues common to small treebanks such as the Paris 7 French Treebank. Using David Chiangs STIG parser (Chiang, 2003), we present results of various experiments we conducted to explore those models for French parsing. The grammar induction makes use of a head percolation table tailored for the French Treebank and which is provided in this paper. Using two evaluation metrics, we found that the parsing performance of a STIG model is tied to the size of the underlying Tree Insertion Grammar, with a more compact grammar, a spinal STIG, outperforming a genuine STIG. We finally note that a ""spinal"" framework seems to emerge in the literature. Indeed, the use of vertical grammars such as Spinal STIG instead of horizontal grammars such as PCFGs, afflicted with well known data sparseness issues, seems to be a promising path toward better parsing performance.


Introduction
The use of Tree Adjoining Grammar-based formalisms (Joshi, 1987), henceforth TAG, for probabilistic parsing is not a new idea. While the initial intuition of adding probabilities to TAGs was mentioned by Joshi et al. (1975) in their seminal paper, formulations of a TAG probabilistic model were independently proposed in (Schabes, 1992) and (Resnik, 1992). Schabes (1992) proposed a version of the Inside-Outside algorithm for reestimating a Stochastic Lexicalized TAG (LTAG). This algorithm was later used by Hwa (1998) for the unsupervised learning, from partially bracketed data, of a context free variant of TAGs, namely Lexicalized Tree Insertion Grammars (LTIG, (Schabes and Waters, 1995)). Using LTIG allows for the same parsing complexity as pure context-free grammars, while permitting the generation of richer derivational structures. However, none of these works presented the extraction of linguistically motivated TAGs. Indeed, such grammars can be induced from a set of parses using hand written heuristics, such as head percolation and argument adjunct distinction tables, for reconstructing the derivations. This approach was, for instance, followed by (Neumann, 1998;Xia, 1999;Chen and Vijay-Shanker, 2000;Chiang, 2000) to extract various kinds of lexicalized tree grammars to build statistical parsers, supertaggers and so on. Interestingly, another operation, the sister-adjunction, is added to the Stochastic TIG (STIG) framework by Chiang (2000) in order to handle flat structures inher-ent to most treebanks. Furthermore, a special mode of the Chiang's STIG model implementation can lead to the extraction of LTIGs that only contain spines (i.e. lineage from the anchor to its maximal projection), allowing for more compact grammars that can counterbalance data sparseness issues in a highly lexicalized formalism such as LTIG. We call this model SPINAL STIG and we present here an evaluation of its performance on the Paris 7 French Treebank (FTB, (Abeillé et al., 2003)) via the use of the Chiang (2003) STIG parser. This paper is structured as follows: we provide a brief overview of the FTB, then we introduce the STIG and SPINAL STIG models and outline their extraction process. We present various possible parameter setups affecting the spinal grammar probabilistic model. We then provide a comparison between pure STIG and SPINAL STIG models run on different instances of the FTB. Before concluding, we discuss our results compared to previous works.

The French Treebank
Unlike the Penn Treebank (Marcus et al., 1994), the FTB proposes a flat annotation scheme (Abeillé et al., 2003). For instance, there are no VPs for finite verbs and only one sentential level for clauses or sentences regardless of whether or not they are introduced by a complementizer. Only the verbal nucleus (VN) is annotated and comprises the verb, its clitics, auxiliaries, adverbs and surrounding negation. Because of this lack of VP constituent for finite verbs in both treebanks, the distinction between argument and adjunct is not marked by a different structure but rather by functional annotations. We use the treebank variation described in (Crabbé and Candito, 2008) with the CC tagset. All compounds are explicitly marked. We refer to this treebank instance as FTB or FTB-CC wherever the distinction is relevant.

Overview of Lexicalized Tree Adjoining Grammars
A Lexicalized TAG grammar (LTAG) consists of a large lexicon where each lexical entry (i.e., anchor) is associated with a set of elementary trees. Two composition operations are provided: the substitution which is a context free derivation of an elementary tree to a given leaf node of any tree, and the adjunction which inserts a particular kind of tree on a node. The tree being adjoined has one special leaf node, marked by an asterisk and with the same label as the root node of the adjoined tree. Those trees are called auxiliary trees whereas non-auxiliary elementary trees are called initial trees.
As the formalism's basic units are trees, the derivation tree and the derived tree (i.e., the parse tree) are not isomorphic. The derivation tree strictly records the resulting operation leading to a derived tree. Each node of the derivation tree is labeled by a Gorn address 1 telling us where the operation took place in the dominating tree.
A toy grammar and a sketch of derivations for the sentence Jean aime beaucoup Marie/John really likes Mary is shown in Figure 1. Resulting derived and derivation trees 2 are shown in Figure 2. Regarding context free variants of TAG such as TIG, the main differences is that wrapping adjunction of auxiliary trees is not allowed (Schabes and Waters, 1995). This ensures that the weak generative power is strictly the same as in context free grammars and allows for a formalism parsable in cubic time.

Statistical TIG models
In this section, we introduce the Stochastic Tree Insertion Grammar (STIG) variant, introduced by Chiang (2000).

STIG
STIG is a tree rewriting system with three types of elementary trees: initial, predicative auxiliary trees and three composition operations: substitution, adjunction and sister-adjunction. While the first two are well known, being the classical TAG operations introduced above, the sister-adjunction was introduced in (Rambow et al., 1995) and used by Chiang (2000) as a means to derive treebank flat structures. It is a context-free operation only constrained through a probability model that conditions the generation of a modifier tree on a given node upon the root label of the previously generated sister-adjoining tree. As opposed to the induction of CFGs that can be easily extracted from a treebank, the reconstruction of STIG derivations must rely on heuristics stating which nodes will be part of an elementary tree. Following previous works on lexicalized PCFG induction (e.g. (Magerman, 1995;Collins, 1997)), the Chiang's (2000) model makes use of a head-percolation table to distinguish the path from a lexical anchor to its maximal projection. This path is called spine. 3 In the LTAG framework, all elementary trees are extended projections of lexical items and contain all syntactic arguments of a lexical anchor (i.e., the syntactic head). These argument nodes correspond to substitution nodes of elementary trees and in order to properly annotate these nodes, an argument-adjunct distinction table is required (Xia, 1999). Given the non-configurational nature of the French treebank, our rules are based on functional annotations. In Figure 3, we outline the STIG induction process from a parse tree based on the FTB's annotation scheme (1) to the STIG grammar underlying the reconstructed derivations (4).

Spinal STIG
As shown in section 4.1., the conjunction of headpercolation and argument/adjunct rules is essential to extract proper elementary trees from treebank data. Interestingly, having no access to an argument adjunct table leads the Chiang's (2000) STIG model implementation 4 to extract a grammar where all extracted trees have no argument nodes. All of these trees are therefore made of spines and consequently handled by sister-adjunction. This behavior results from an undocumented side effect of the Chiang (2000) model and was noticed during its preliminary adaptation to French. Figure 4 shows the extraction process of such a spinal grammar. We notice that even though the extracted grammars are different and lead to different derivation trees 5 , they 4 Available at www.isi.edu/∼chiang/software/hybrid.tar.gz 5 With respect to the types of the derivations and their respective site nodes.  (1) share the same dependency structure (Fig. 5).  (1) Finally, in order to ease the estimation of the probability model's parameters, the grammar is implicitly split between tree templates and lexical anchors, allowing the probabilistic model to generate first a template, then its anchor (Chiang, 2000). We describe the parameter classes of the STIG models in the next section.

STIG/STAG Parameter classes
Because TIGs are a subset of TAGs that retains the same properties, regardless on constraints used to avoid the generation of wrapping auxiliary trees, a probabilistic model for Stochastic TAGs is also valid for Stochastic TIGs. A Stochastic TAG (Resnik, 1992;Schabes, 1992), henceforth STAG, is an history based model, such as PCFGs, where the probability of a TAG derivation tree is the product of the probabilities of the operations used for its construction. Chiang (2003) describes the parameters of a STAG as follows: Following the usage in the TAG literature, α denotes initial trees, β auxiliary trees, γ any tree and η a node of a tree. P i (α) is the probability of a derivation starting by α, P s (α|η), the probability of a substitution of α on η, P a (β|η), the probability of β adjoining on η and P a (N ON E|η), the probability of having zero adjunction on η.
As we mentioned, the sister-adjunction operation was added by Chiang (2000) to the original STAG model in order to cope with treebanks' flat annotation scheme. Originating from D-tree grammars (Rambow et al., 1995), this operation allows for any initial tree to be inserted as a new daughter of a node. The sister-adjunction also bears some resemblances with the furcation operation as described in (Halber, 1998;Kilger and Poller, 2000). Its capacity to derive multiple initial trees in the same node is also reminiscent of the modifier adjunction of Schabes and Shieber (1994). Its parameter class is the following (Chiang, 2003): Where α denotes initial trees and (η, i) varies over possible sister-adjunction sites. P sa (α) the probability of sister-adjoining α and P sa (ST OP ) the probability of no further sister-adjunction. X is the root label of the previous tree that was closer to the head, to sisteradjoin at the site node (η, i).
The backoff structures of this model are presented in the Appendix, Table 4.

Head rules and argument-adjunct distinction tables
All lexicalized parsers use head propagation tables. Adapting them to the French language requires to design French specific head propagation rules. To this end, we used those described by (Dybro-Johansen, 2004) for extracting a Tree Adjoining Grammar from an early release of the FTB. From this set, we built a set of meta-rules that were automatically derived to match each treebank annotation scheme that will be used in the next two sections. Table 5 (Appendix) provides an example of such a head rule percolation table for the FTB-CC.
As the pure STIG model needs to distinguish between argument and adjunct nodes to extract proper initial trees, we implemented an argument-adjunct distinction table that takes advantage of the function labels annotated in the treebank.

Varying the generating context of the spinal trees
As shown in section 4.3., the probability of an initial tree to sister-adjoin on a site node (η, i) is conditioned on a context X, where X is set by default to the root label of the previous tree that was sister-adjoined on this site node. As this parsing model allows for modifying this setup, and because when run in spinal mode, all trees of the extracted grammar are handled by the sisteradjunction, it is interesting to observe the impact of this context on parsing performance. Thus, in this section we present results from experiments where the context is either a flag stating that the tree to be generated is the first modifier tree to be sister-adjoined (first), the root label of the previous sis-ter¯adjoined tree (root) or no context at all (none). We also test whether generating the modifier trees from the head outward instead of left-to-right has an impact on a treebank as flat as the FTB. The idea is to verify if the parsing of a relatively free word order language such as French 6 can benefit from a generative process less dependent upon a recorded phrase order.
All evaluations are given from the SPINAL STIG parsing of the canonical development section of the FTB-CC with gold part-of-speech supplied for unknown words. The evaluation metrics is PARSEVAL's labeled brackets and POS tagging accuracy (Black et al., 1991). As usual, scores are given for sentences of length less than 41 words.
Results are presented in Table 1 and show that the default setup conditioning the generation of spinal trees upon the previous root label provides by far the best performance when the heads are generated from left to right. Nonetheless, the situation is reversed when the trees are generated from the head outward. 7 One can notice the huge gap between the POS tagging accuracies in the two parts of Table 1. The point is that generating modifier trees from left to right means that their root labels are generated by a first-order Markov process (Chiang, 2003). Thus, we can hypothesize that this process also applies to the label of their pre-terminal nodes (the POS). In fact, conditioning POS with a Markovian process respecting the word order is probably more efficient that conditioning them on a maybe more distant tree that has been sister-adjoined to the head regardless of their relative position on the word stream.
In the remaining part of this paper, we use the "root" context with trees generated from left to right. 6 French exhibits a limited amount of word order variation occurring at different syntactic levels including (i) the word level (e.g., pre or post nominal adjective, pre or post verbal adverbs); (ii) phrase level (e.g., possible alternations between post verbal NPs and PPs). 7 Note that generating modifier trees from the head outward is similar to the way the Collins' model 2 handles modifier non terminal nodes (Bikel, 2004

Grammar size and parsing performance
In (Seddah et al., 2009), a benchmarking between various probabilistic models applied to French treebanks showed that the parsing performance of the spinal STIG models ranks roughly in the middle of lexicalized parsers w.r.t to the classical labeled bracket metrics when evaluated on the FTB. However, it reaches the state of the art regarding unlabeled dependency evaluation.
Here we extend those results by showing that the parsing model performance is bound to the size of the extracted grammar as shown by Table 3.
The same experimental protocol 8 as Seddah et al. (2009) is used on three instances of the FTB with different tagsets ( Table 2). The tagset MIN contains only bare syntactic categories, the tagset CC is the one described in (Crabbé and Candito, 2008) and known to provide the best parsing performance on the FTB, the tagset SCHLU is the one extracted from the Modified French Treebank (Schluter and van Genabith, 2007)  Jointly with the PARSEVAL F 1 labeled bracket metric, we provide results of unlabeled dependency evaluation which is computed using the algorithm described in (Lin, 1995). In order to provide a realistic view of the performance of STIG models, the different FTB test sets are here tagged with the TNT tagger of Brants (2000) trained on the training section of each instance of the FTB.   (Table 3) show that in all cases, a SPINAL STIG model outperforms a genuine STIG using constituency metric, the most compact grammar offering the best performance. However, unlabeled dependencies results are somehow a bit higher on the FTB-SCHLU (i.e., the FTB with the SCHLU tagset) with SPINAL STIG parsing. This tagset was conceived to optimize LFG induction from the MFT and contains more morphological information than the CC tagset. This supplementary amount of data brought to the head-percolation table used for the FTB-SCHLU parsing leads the Lin (1995) dependency extraction process to be less error-prone. This can explain this small difference in these results. We also note that the best results are provided by the more compact grammars. These grammars are extracted from the FTB-CC. This shows that the CC tagset granularity seems to be an advantage for STIG parsing.

Related work and discussion
In (Sangati and Zuidema, 2009), a process of automatically inducing a Lexicalized Tree Subtitution Grammar from a treebank is described. Their goal is to validate the automatic induction of head rules from annotated data. In their process, the first extracted grammar is actually a spinal STIG. Also, note that a spinal version of a PCFG is briefly described in (Post and Gildea, 2009) in order to test the performance of different kinds of binarized grammars. In this approach, each spinal tree corresponds to a set of CFG rules, the root node being considered as a left hand-side nonterminal symbol.
Closer to our goals, a LTAG SPINAL model has been proposed by Shen and Joshi (2005) and developed in (Shen et al., 2008). Their grammar extraction algorithm takes advantage of the PropBank annotations (Palmer et al., 2005) in order to provide much deeper syntactic dependencies than the ones underlying our spinal grammars based only on a simple set of heuristics. Note that the extracted LTAG SPINAL grammar is one order of magnitude less coarse than our own, as it contains 1,224 spinal trees.
Recently, a similar though richer model has been independently proposed in (Carreras et al., 2008) with the purpose of getting a powerful and very sophisticated parsing model that can use non local features. As these models are closely related, we ran the spinal TIG model on the section 23 of the Penn Treebank and obtained 87.79% of PARSEVAL labeled bracket F 1 score with 369 tree templates 10 while Carreras et al. (2008) report very high state-of-the-art results (91.1%). This can be explained by the use of high level machine learning techniques to cope with spine attachment decisions whereas our model is based on a pure generative model.
As opposed to some of the works we briefly presented, we did not try to refine the spinal grammars we extracted, for example we did not discriminate between spinal trees sister-adjoining on the right and those sister-adjoining on the left of an elementary tree.
The idea for us was to see how far we could get using the smallest possible grammar we could induce from a treebank. Indeed, we showed that the parsing performance for French was tied to the grammar size. More compact grammars in the STIG model lead to better results. We believe that refining the model to take into account more context and to split the grammar according to the most probable side of sister-adjoining trees will improve the parsing performance of the SPINAL STIG model. Nonetheless, this is not the main point of dealing with spinal grammars. We think that going from horizontal grammars such as PCFGs to vertical ones as implied by the emerging SPINAL framework is currently one of the best ways to deal with the unavoidable data sparseness issues due to the current average limited size of usual treebanks. 10 On the same PTB section, we obtained 88.69% for the PURE STIG model with 868 templates. All scores are given for sentences of length less than 41.

Conclusion
We reported evaluation parsing results from the extraction of various STIG for French. We showed that the SPINAL STIG model outperforms a genuine STIG model when applied on a less hierarchical treebank such as the FTB. We showed that having more compact grammars leads to better parsing performance for parsing French in a TAG framework. In our future work, we will refine the extraction model in order to extract less coarse grammars.