{'fraction_non_alphanumeric': 0.028736033519553072, 'fraction_numerical': 0.010614525139664804, 'mean_word_length': 5.113340448239061, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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}}
Special Techniques for Constituent Parsing of Morphologically Rich Languages

We introduce three techniques for improving constituent parsing for morphologically rich languages. We propose a novel approach to automatically find an optimal preterminal set by clustering morphological feature values and we conduct experiments with enhanced lexical models and feature engineering for rerankers. These techniques are specially designed for morphologically rich languages (but they are language-agnostic). We report empirical results on the treebanks of five morphologically rich languages and show a considerable improvement in accuracy and in parsing speed as well.


Introduction
From the viewpoint of syntactic parsing, the languages of the world are usually categorized according to their level of morphological richness (which is negatively correlated with configurationality). At one end, there is English, a strongly configurational language while there is Hungarian at the other end of the spectrum with rich morphology and free word order (Fraser et al., 2013). A large part of the methodology for syntactic parsing has been developed for English but many other languages of the world are fundamentally different from English. In particular, morphologically rich languages -the other end of the configurational spectrum -convey most sentencelevel syntactic information by morphology (i.e. at the word level), not by configuration. Because of these differences the parsing of morphologically rich languages requires techniques that differ from or extend the methodology developed for English . In this study, we present three techniques to improve constituent parsing and these special techniques are dedicated to han-dle the challenges of morphologically rich languages.
Constituency parsers have advanced considerably in the last two decades (Charniak, 2000;Charniak and Johnson, 2005;Petrov et al., 2006;Huang, 2008) boosted by the availability of the Penn Treebank (Marcus et al., 1993). While there is a progress on parsing English (especially the Penn Treebank), the treebanks of morphologically rich languages have been attracted much less attention. For example, a big constituent treebank has been available for Hungarian for almost 10 years (Csendes et al., 2005) and to the best of our knowledge our work is the first one reporting results on this treebank. One reason for the moderate level of interest in constituent parsing of morphologically rich languages is the widely held belief that dependency structures are better suited for representing syntactic analyses for morphologically rich languages than constituent representations because they allow non-projective structures (i.e. discontinuous constituents). From a theoretical point of view, Tsarfaty et al. (2010) point out, however, this is not the same as proving that dependency parsers function better than constituency parsers for parsing morphologically rich languages. For a detailed discussion, please see Fraser et al. (2013).
From an empirical point of view, the organizers of the recent shared task on 'Statistical Parsing of Morphologically Rich Languages'  provided datasets only for languages having treebanks in both dependency and constituency format and their cross-framework evaluation -employing the unlabeled TedEval (Tsarfaty et al., 2012) as evaluation procedure -revealed that at 4 out of 9 morphologically rich languages, the results of constituent parsers were higher than the scores achieved by the best dependency parsing system. Based on these theoretical issues and empirical results, we support the conclusion of Fraser et al. (2013) that "... there is no clear evidence for preferring dependency parsing over constituency parsing in analyzing languages with rich morphology and instead argue that research in both frameworks is important." In this study, we propose answers to the two main challenges of constituent parsing of morphologically rich languages, which are finding the optimal preterminal set and handling the huge number of wordforms. The size of the preterminal set in the standard context free grammar environment is crucial. If we use only the main POS tags as preterminals, we lose a lot of information encoded in the morphological description of the tokens. On the other hand, using the full morphological description as preterminal yields a set of over a thousand preterminals, which results in data sparsity and performance problems as well. The chief contribution of this work is to propose a novel automatic procedure to find the optimal set of preterminals by merging morphological feature values. The main novelties of our approach over previous work are that it is very fast -it operates inside a probabilistic context free grammar (PCFG) instead of using a parser as a black box with re-training for every evaluation of a feature combination -and it can investigate particular morphological feature values instead of removing a feature with all of its values.
Another challenge is that because of the inflectional nature of morphologically rich languages the number of wordforms is much higher compared with English.
Hence the number of unknown and very rare tokens -i.e. the tokens that do not appear in the training dataset -is higher here, which hurts the performance of PCFG parsers. Following Goldberg and Elhadad (2013), we enhance the lexical model by exploiting an external lexicon. We investigate the applicabilities of fully supervised taggers instead of unsupervised ones for gathering external lexicons.
Lastly, we introduce novel feature templates for an n-best reranker operating on the top of a PCFG parser. These feature templates are exploiting atomic morphological features and achieve improvements over the standard feature set engineered for English.
We conducted experiments by the above mentioned three techniques on Basque, French, German, Hebrew and Hungarian, five morphologically rich languages. The BerkeleyParser (Petrov et al., 2006) enriched with these three techniques achieved state-of-the-art results on each language.

Related Work
Constituent parsing of English is a well researched area. The field has been dominated by data-driven, i.e. treebank-based statistical approaches in the last two decades (Charniak, 2000;Charniak and Johnson, 2005;Petrov et al., 2006). We extend here BerkeleyParser (Petrov et al., 2006), which is a PCFG parser using latent annotations at nonterminals. Its basic idea is to iteratively split each non-terminal into subsymbols thus capturing the different subusage of them instead of manually designed annotations.
The constituent parsing of morphologically rich languages is a much less investigated field. There exist constituent treebanks for several languages along with a very limited number of parsing reports on them. For instance, Petrov (2009) trained BerkeleyParser on Arabic, Bulgarian, French, German and Italian and he reported good accuracies, but there has been previous work on Hebrew (Goldberg and Elhadad, 2013), Korean (Choi et al., 1994) and Spanish (Le Roux et al., 2012) etc. The recently organized 'Statistical Parsing of Morphologically Rich Languages'  addressed the dependency and constituency parsing of nine morphologically rich languages and provides useful benchmark datasets for these languages.
Our chief contribution in this paper is a procedure to merge preterminal labels. The related work for this line of research includes the studies on manual refinement of preterminal sets such as Marton et al. (2010) andLe Roux et al. (2012). The most closely related approach to our proposal is Dehdari et al. (2011), who defines metaheuristics to incrementally insert or remove morphological features. Their approach uses parser -training and parsing -as a black box evaluation of a preterminal set. In contrast, our proposal operates as a submodule of the BerkeleyParser, hence does not require the re-training of the parser for every possible preterminal set candidate, thus it is way more faster.
The most successful supervised constituent parsers contain a second feature-rich discriminative parsing step (Charniak and Johnson, 2005;Huang, 2008;Chen and Kit, 2012) as well. At the first stage they apply a PCFG to extract pos- sible parses. The n-best list parsers keep just the 50-100 best parses according to the PCFG (Charniak and Johnson, 2005). These methods employ a large feature set (usually a few million features) (Collins, 2000;Charniak and Johnson, 2005). These feature sets are engineered for English. In this study, we introduce feature templates for exploiting morphological information and investigate their added value over the standard feature sets.

Experimental Setup
We conducted experiments on the treebanks of the 2013 shared task on 'Statistical Parsing of Morphologically Rich Languages' . We used the train/dev/test splits of the shared task's Basque (Aduriz et al., 2003), French (Abeillé et al., 2003), Hebrew (Sima'an et al., 2001), German (Brants et al., 2002) and Hungarian (Csendes et al., 2005) treebanks. Table 1 shows the basic statistics of these treebanks, for a more detailed description about their annotation schemata, domain, preprocessing etc. please see . As evaluation metrics we employ the PARSE-VAL score (Abney et al., 1991) along with the exact match accuracy (i.e. the ratio of perfect parse trees). We use the evalb implementation of the shared task 1 .

Enhanced Lexical Models
Before introducing our proposal and experiments with preterminal set optimisation, we have to offer a solution for the out-of-vocabulary (OOV) problem, which -because of the inflectional natureis a crucial problem in morphologically rich lan-1 Available at http://pauillac.inria.fr/ seddah/evalb_spmrl2013.tar.gz. An important change in this version compared to the original evalb is the penalization of unparsed sentences. guages. We follow here Goldberg and Elhadad (2013) and enhance a lexicon model trained on the training set of the treebank with frequency information about the possible morphological analyses of tokens. We estimate the tagging probability P (t|w) of the tag t given the word w by where c(w) is the count of w in the training set, K is predefined constant, P tb (t|w) is the probability estimate from the treebank (the relative frequency with smoothing) and P ex (t|w) is the probability estimate from an external lexicon. We calculate the emission probabilities P (w|t) from the tagging probabilities P (t|w) by applying the Bayesian rule.
The key question here is how to construct the external lexicon. For a baseline, Goldberg and Elhadad (2013) suggest using the uniform distribution over all possible morphological analyses coming from a morphological analyser ('uniform').
Goldberg and Elhadad (2013) also report considerable improvements over the 'uniform' baseline by relative frequencies counted on a large corpus which was automatically annotated in the unsupervised POS tagging paradigm (Goldberg et al., 2008). Here we show that even a supervised morphological tagger without a morphological analyzer can achieve the same level of improvement. We employ MarMot 2 (Mueller et al., 2013) for predicting full morphological analysis (i.e. POS tags and morphological features jointly). MarMot is a Conditional Random Field tagger which incrementally creates forwardbackward lattices of increasing order to prune the sizable space of possible morphological analyses. We used MarMoT with the default parameters. This purely data-driven tagger achieves a tagging accuracy of 97.6 evaluated at full morphological analyses on the development set of the Hungarian treebank, which is competitive with the state-of-the-art Hungarian taggers which employ language-specific rules (e.g. magyarlanc (Zsibrita et al., 2013)). The chief advantage of using Mar-Mot instead of an unsupervised tagger is that the former does not require any morphological lexicon/analyser (which can lists the possible tags for a given word). This morphological lexicon/analyser is language-dependent, usually handcrafted and it has to be compatible with the treebank in question. In contrast, a supervised morphological tagger can build a reasonable tagging model on the training part of the treebanks -especially for morphologically rich languages, where the tag ambiguity is generally low -thus each of these problems is avoided. Table 2 shows the results of various P ex (t|w) estimates on the Hungarian development set. The first row 'BerkeleyParser' is our absolute baseline, i.e. the original implementation of Berke-leyParser 3 defining signatures for OOVs. For the 'uniform' results, we used the morphological analyser module of magyarlanc (Zsibrita et al., 2013). The last two rows show the results achieved by training MarMot on the treebank's training dataset, having tagged the development set plus a huge unlabeled corpus (10M sentences from the Hungarian National Corpus (Váradi, 2002)) with it then having counted relative tag frequencies. We report scores on only using the frequencies from the development set ('dev') and from the concatenation of the development set and the huge corpus ('huge').
After a few preliminary experiments, we set K = 7 and use this value thereafter. Table 2 shows that even 'dev' yields a considerable improvement over the baseline parser and 'uniform'. These results are also in line with the findings of Goldberg and Elhadad (2013), i.e. 'uniform' has some added value and using relative frequencies gathered from automatically tagged corpora contributes more. Although we can see another nice improvement by exploiting unlabeled corpora ('huge'), we will use the 'dev' setting in  the experiments of the next sections as we did not have access to huge, in-domain unlabeled corpora for each language used in this study.

Morphological Feature Values as Preterminals
Finding the optimal set of morphological features incorporating into the perterminal labels is crucial for any PCFG parsers. Removing morphological features might reduce data sparsity problems while it might lead to loss of information for the syntactic parser. In this section, we propose a novel method for automatically finding the optimal set of preterminals then we present empirical results with this method and compare it to various baselines. (a) split the POS tag for the values of the morphological feature 4 (b) recalculating the rule probabilities where there are preterminals in the right-hand side by uniformly distribute the probability mass among subsymbols (c) set the lexical probabilities according to the relative frequencies of morphological values counted on gold standard morphological tags of the treebank (d) running 10 iterations of the Expectation-Maximization procedure on the whole treebank initialized with (b)-(c) (e) constructing a fully connected graph whose nodes are the morphological values of the feature in question (f) for every edge of the graph, calculate the loss in likehood for the merging the two subsymbols (the same way as for BerkeleyParser's merge procedure) 4. removing edges from the entire set of graphs (controlled by the parameter th)

merge the morphological values of the graphs' connected components
Based on these observations we propose a procedure which starts from the full morphological description of a treebank then iteratively merges particular morphological feature values and it handles the same feature at the different POS tags separately. The result of this procedure is a clustering of the possible values of each morphological feature. The removal of a morphological feature is a special case of our approach because if the values of the feature in question form one single cluster it does not have any discriminative function anymore. Hence our proposal can be regarded as a generalisation of the previous approaches.
This general approach requires much more evaluation of intermediate candidate preterminal sets, which is not feasible within the external black-box parser evaluation scenario (training and parsing an average sized treebank by the BerkeleyParser takes more than 1 hour). Our idea here is that retraining a parser for the evaluation of each preterminal set candidates is not necessary. They key objective here is to select among preterminal sets based on their usefulness for the syntactic parser. This is the motivation of the merge procedure of the BerkeleyParser. After randomly splitting nonterminals, BerkeleyParser calculates for each split the loss in likelihood incurred when merging the subsymbols back. If this loss is small, the new annotation does not carry enough useful information and can be removed (Petrov et al., 2006). Our task is the same at the preterminal level. Hence at the preterminal level, -instead of using the automatic subsymbol splits of the BerkeleyParser -we call this merging procedure over the morphological feature values. Algorithm 1 shows our proposal for the preterminal merging procedure.

Baseline Preterminal Set Constructions:
The two basic approaches for preterminal set construction are the use of only the main POS tag set ('mainPOS') and the use of the full morphological description as preterminals ('full'). For Hungarian, we also had access to a linguistically motivated, hand-crafted preterminal set ('manual') which was designed for a morphological tagger (Zsibrita et al., 2013). This manual code set keeps different morphological features at different POS tags and merges morphological values instead of fully removing features hence it inspired our automatic merge procedure introduced in the previous section.
Our last baseline is the repetition of the experiments of Dehdari et al. (2011). For this, we started from the full morphological feature set and completely removed features (from all POS) one-byone then re-trained our parser. We observed the greatest drop in PARSEVAL score at removing the  'Num' feature and the least severe one at removing 'Form'. 'Num' denotes number for verbs and nominal elements (nouns, adjectives and numerals), and since subject-verb agreement is determined by the number and person features of the predicate (the verb) and the subject (the noun), deleting the feature 'Num' results in a serious decline in performance. On the other hand, 'Form' denotes whether a conjunction is single or compound (which is a lexical feature) or whether a number is spelt with letters, Arabic or Roman numbers (which is an orthographic feature). It is interesting to see that their deletion hardly harms the PARSEVAL scores, moreover, it can even improve the exact match scores, which is probably due to the fact that the distinction between different orthographic versions of the same number (e.g. 6 and VI) just confused the parser. On the other hand, members of a compound conjunction are not attached to each other in any way in the parse tree, and behave similar to single compounds, so this distinction might also be problematic for parsing.  The difference between mainPOS and full is surprisingly high, which indicates that the mor-phological information carried in preterminals is extremely important for the constituent parser and the BerkeleyParser can handle preterminal sets of the size of several hundreds. For Hungarian, we found that the full removal of any feature cannot increase the results. This finding is contradictory with Dehdari et al. (2011) in Arabic, where removing 'Case' yielded a gain of 1.0 in PARSEVAL. We note that baselines for Arabic and Hungarian are also totally different, Dehdari et al. (2011) reports basically no difference between mainPOS and full in Arabic.

Results with Various Preterminal Sets:
We report results of our proposed procedure with two different merging thresholds. The th = 0.1 case merges only a few morphological feature values and it can slightly outperform the 'full' setting (statistically significant 5 in exact match.). On the other hand, the th = 0.5 setting is competitive with the 'full' setting in terms of parsing accuracy but it uses only the third of the preterminals used by 'full'. Although it is not statistically better than 'full' in accuracy, it almost halves the running time of parsing 6 . Table 3 summarizes the results achieved by the most important baselines and our approach along with the size of the particular preterminal sets applied. The 'full' results outperform 'main-POS' at each language with a striking difference at Basque and Hungarian. These results show thatcontradictory to the general belief -the detailed morphological description is definitely useful in constituent parsing as well. The last row of the table contains the result achieved by our merger approach. Here we run experiments with several merging threshold th values and show the highest scores for each language.
Our merging proposal could find a better preterminal set than full on French and Hungarian, it found a competitive tag set in terms of accuracies which are much smaller than full on German and Hebrew and it could not find any useful merge at Basque. The output of the merger procedure consists of one sixth of preterminals compared with full. Manually investigating the clusters, we can see that it basically merged every morphological feature except case at nouns and adjectives (but merged case at personal pronouns). This finding is in line with the experimental results of Fraser et al. (2013).
6 Morphology-based Features in n-best Reranking n-best rerankers (Collins, 2000;Charniak and Johnson, 2005) are used as second stage after a PCFG parser and they usually achieve considerable improvement over the first stage parser. They extract a large feature set to describe the n best output of a PCFG parser and they select the best parse from this set (i.e. rerank the parses). Here, we define feature templates exploiting morphological information and investigate their added value for the standard feature sets (engineered for English). We reimplemented the feature templates from Charniak and Johnson (2005) and Versley and Rehbein (2009) excluding the features based on external corpora and use them as our baseline feature set. We used n = 50 in our experiment and followed a 5-fold-cross-parsing (a.k.a. jackknifing) approach for generating unseen parse candidates for the training sentences (Charniak and Johnson, 2005). The reranker is trained for the maximum entropy objective function of Charniak and Johnson (2005), i.e. the sum of posterior probabilities of the oracles. We used a slightly modified version of the Mallet toolkit for reranking (McCallum, 2002) and L2 regularizer with its default value for coefficient.
The feature templates of the baseline feature set frequently incorporate preterminals as atomic feature. As a first step, we investigated which preterminal set is the most useful for the baseline feature set. We took the 50 best output from the parser using the merged preterminal set and used its preterminals ('merged') or only the main POS tag ('mainPOS') as atomic building blocks for the reranker's feature extractor. Table 5 shows that mainPOS outperformed full. This is probably due to data sparsity problems.
Based on this observation, we decided to use mainPOS as preterminal in the atomic building block of the baseline features and designed new feature templates capturing the information in the morphological analysis. We experimented with the following templates: For each preterminal of the candidate parse and for each morphological feature value inside the preterminal we add the pair of wordform and morphological feature value as a new feature. In a similar way, we define a reranker feature from every morphological feature value of the head word of the constituent. For each head-daughter attachment in the candidate parse we add each pair of the morphological feature values from the head words of the attachment's participants. Similarly we take each combination of head word's morphological features values from sister constituents.
The first two templates enable the reranker to incorporate information into its learnt model from the rich morphology of the language at the lexical and constituent levels, while the last two templates might capture (dis)agreement at the morphological level. The motivation for using these features is that because of the free(er) word order of morphologically rich languages, morphological (dis)agreement can be a good indicator of attachment. Table 5 shows the added value of these feature templates over mainPOS ('extended'), which is again statistically significant in exact match. Exploiting the morphological agreement in syntactic parsing has been investigated in previous studies, e.g. the Bohnet parser (Bohnet, 2010) employs morphological feature value pairs similar to our feature templates and Seeker and Kuhn (2013) introduces an integer linear programming framework including constraints for morphological agreement. However, these works focus on dependency parsing and to the best of our knowledge, this is the first study on experimenting with atomic morphological features and their agreement in a constituency parsing.

Results of the Full System
After our investigations focusing on building blocks of our system independently from each other on the development set, we parsed the test sets of the treebanks adding steps one-by-one. Table 6 summarizes our final results. We start from the BerkeleyParser using the full morphological descriptions as preterminal set, then we enrich the lexical model with tagging frequencies gathered from the automatic parsing of the test sets ('+ lexical model'). In the third step we replace the full preterminal set by the output of our preterminal merger procedure ('+ preterminal merger'). We tuned the merging threshold of our method on the development set for each language. The last two rows contain the results achieved by the 50-best reranker with the standard feature set ('+ reranker') and with the feature set extended by morphological features ('+ morph features'). The enhanced lexical model contributes a lot at Basque and considerable improvements are present at German and Hungarian as well while it harmed the results in French. The advance of the preterminal merger approach over the full setting is clear at French and Hungarian, similarly to the development set. It is interesting that an rationalized preterminal set could compensate the loss suffered by a inadequate lexical model at French.
Although the reranking step could further improve the results at each languages we have to note that the gain (0.5 in average) is much smaller here than the gains reported on English (over 1.5). This might be because of the high number of wordforms at morphologically rich languages i.e. most of feature templates are incorporate the words itself and the huge dictionary can indicate data sparsity problems again. Our morphology-based reranking features yielded a moderate improvement at four languages, but we believe there a lots of space for improvement here.

Conclusions
In this study we introduced three techniques for better constituent parsing of morphologically rich languages. We believe that research in constituency parsing is important next to dependency parsing. In general, we report state-of-the-art results with constituent parsers with our entirely language-agnostic techniques.
Our chief contribution here is the preterminal merger procedure. This is a more general approach than previous proposals and still much faster thank to operating on probabilities from a PCFG instead of employing a full train+parse step for evaluating every preterminal set candidate. We found that the inclusion of the rich morphological description into the preterminal level is crucial for parsing morphologically rich languages. Our proposed preterminal merger approach could outperform the full setting at 2 out of 5 languages, i.e. we have reported gains in parsing accuracies by merging morphological feature values. At the other languages, the results with the full preterminal set and our approach are competitive in terms of parsing accuracies while our approach could achieve these scores with a smaller preterminal set, which leads to considerable parsing time advantages.
We also experimented with exploiting external corpora in the lexical model. Here we showed that automatic tagging of an off-the-shelf supervised morphological tagger (MarMot) can contribute to the results. Our last experiment was carried out with the feature set of an n-best reranker. We showed that incorporating feature templates built on morphological information improves the results.