5.2.1 HMM initializing algorithm

The HMM initializing algorithm estimates the initial parameters of HMM_mx. The algorithm is analogous to Algorithm 1. The main difference between them is the number of observation sequences associated with hidden state sequences. Algorithm 1 relates a certain observation sequence (i.e., a sentence) to a set of hidden state sequences (i.e., a set of XTAG elementary tree sequences). The HMM initializing algorithm, however, discovers the relationship between a set of observation sequences (i.e., a set of MICA elementary tree sequences) and the corresponding set of hidden state sequences (i.e., a set of XTAG elementary tree sequences).

The algorithm runs on the training data described in Section 5.1. For each sentence s in the training data, the algorithm needs to weight pairs of the MICA and XTAG elementary tree sequences (T, T′) associated with s. We will refer to sentence s as s = η(T, T′), where T and T′ are the MICA and XTAG elementary tree sequences assigned to sentence s, respectively. The weights are computed based on the closeness of syntactic interpretations that the sequences provide for their generating sentence s. We will refer to these weights as the syntactic compatibility ratio (or CR for short) between the XTAG and MICA elementary tree sequences.

The two main reasons for introducing the syntactic CR between the sequences of elementary tree are as follows: First, in some cases, the grammars use different tree structures to represent the same syntactic environment. They also use different notations for internal nodes of some elementary trees that model the same syntactic environment of the language. Figure 3, originally presented in Chen (Reference Chen2001), shows two structurally different elementary trees of two LTAGs that represent the same syntactic environment for their anchors.

Fig. 3.

Two structurally different elementary trees of two LTAGs describing the same syntactic environment for their anchors.

Second, the grammars can explain sentences syntactically in different ways. For instance, Figure 4 represents different syntactic explanations for the sentence John is giving books to Mary. The elementary tree sequence T is provided by the MICA grammar, and the T′_is (i = 1, 2, 3) are provided by the XTAG grammar. All of the sequences assign the same elementary trees to the words John, is, book, and Mary. The differences are found in the elementary trees assigned to the words giving and to. The verb giving is classified as a basic transitive verb in T, T′₁, and T′₃, but as a ditransitive verb in T′₂. Both T′₁ and T′₂ suggest that the word to is a preposition depending on a verb to its left side. T′₃, however, suggests that the word to is a preposition depending on a noun to its left side. Similarly, T suggests that the word to is a preposition depending on a noun to its left side but the word is categorized as TO rather than preposition (P) as in the T′₃.

Fig. 4.

Different e-tree sequences associated with the sentence “John is giving books to Mary.” T is a MICA e-tree sequence and T′_i, i = 1, 2, 3 are XTAG e-tree sequences.

In this example, the syntactic CR is expected to give the highest value to the pair (T, T′₃) and the lowest value to the pair (T, T′₂). An accurate estimation of syntactic compatibility requires that many parameters to be taken into consideration (e.g., the structure of the elementary trees, the syntactic category of the words, and the dependency structure that the elementary trees suggest for the words). Another approach is to estimate the syntactic CR between two elementary tree sequences T = (t ₁, . . ., t_n) and T′ = (t′₁, . . ., t_n′) assigned to sentence s = (w ₁, . . ., w_n) based on the relative frequency of seeing the corresponding elementary trees t_r and t′_r together. This is based on the assumption that the elementary trees that often appear together are more likely to be related to the same syntactic environment of the language. We estimate the syntactic CR between T and T′ as a value proportional to the joint probability of the sequences given the HMM_mx. Equation (7) estimates the syntactic CR between T and T′ assigned to sentence s = η(T, T′) respectively. The function ω returns the correctness ratio of its arguments (see Section 5.1).

(7) \begin{equation} CR(s,T,T^{\prime })=\omega (s,T) \omega (s,T^{\prime }) p(T,T^{\prime } \mid \mbox{HMM}_{mx}). \end{equation}

Algorithm 2 outlines the EM-based HMM initializing algorithm. The algorithm starts by estimating the syntactic CR between all of the XTAG elementary tree sequences T′_i ∈ {T′₁, . . ., T _ks′} and MICA elementary tree sequences T_j ∈ {T ₁, . . ., T _ls} assigned to sentence s = (w ₁, . . ., w_n). In this step, since the algorithm has no clue about the HMM_mx, the probability p(T_j, T′_i∣HMM_mx) in 7 is replaced with the uniform probability distribution. The initial value of HMM_mx is then estimated from the weighted pairs of MICA and XTAG elementary tree sequences. In the EM loop, the CR of the MICA and XTAG elementary tree sequences are updated based on the current value of HMM_mx (expectation), and the new weights are used to estimate the new value of HMM_mx (maximization). The objective function is the likelihood of observing the observation sequences (i.e., MICA elementary tree sequences).

Algorithm 2

The EM-based semi-supervised algorithm for initializing HMM_mx

Both of the transition and observation probabilities of HMM_mx are estimated by the MLE. For each pair of XTAG elementary trees (t′_j, t′_i), the transition probabilities t′_j↦t′_i can be estimated by dividing the frequency of seeing (t′_j, t′_i) by the frequency of seeing t′_j. The frequency of seeing a sub-sequence of XTAG elementary trees x is computed from 8, where the Kronecker delta function δ(x, s, T, T′) is 1 if and only if s = η(T, T′) and x is a subsequence of T′.

(8) \begin{equation} C(x)=\sum _{s}{\sum _{T}{\sum _{T^{\prime }}{CR(s,T,T^{\prime })\delta (x,s,T,T^{\prime }).}}} \end{equation}

For each XTAG elementary tree t′ and MICA elementary tree t, the observation probability p(t∣t′) can also be estimated by dividing the frequency of seeing the pair (t, t′) assigned to the same word by the frequency of seeing t′. The frequency of seeing the pair (t, t′) is computed from 9, where the Kronecker delta function δ is 1 if and only if (1) s = η(T, T′), (2) t is in T and t′ is in T′, and (3) t and t′ refer to the same word in s.

(9) \begin{equation} C(t,t^{\prime })=\sum _{s}{\sum _{T}{\sum _{T^{\prime }}{CR(s,T,T^{\prime })\delta (t,t^{\prime },s,T,T^{\prime }).}}} \end{equation}

The output of Algorithm 2 is the initial value of HMM_mx. This model will then be trained by the Baum–Welch algorithm. The output of the Baum–Welch algorithm would be the desired model to map MICA elementary tree sequences onto the most probable XTAG elementary tree sequences using the HMM decoding algorithm, called the Viterbi algorithm. This process is carried out in the LTAG-mapping phase presented in Figure 2. As shown in Figure 2, the XTAG elementary tree sequences resulting from the LTAG-mapping phase will then be processed in the error-correction phase. The following section details the error-correction phase.

6.1.1 Training sets

The quality of the LTAG-mapping model closely depends on three datasets over which the statistical parts of the model are trained. Table 1 provides some information about the datasets used for training these parts of the model, including the HMM_ex, the HMM_mx, and the word-based model used in the error-correction phase. The HMM_ex and the word-based model are merged into a single row, since both of these models have been trained on the same dataset. HMM_mx Init. and HMM_mx Train give information about the training datasets used for initializing and training HMM_mx, respectively.

Table 1.

Statistical information about the training datasets

All of the sentences in these datasets have been randomly sampled from the set of all sentences in WSJ with a maximum length of 25. The columns Avg Len. and Max Len. show the average and maximum length of the sentences, respectively. The number of sampled sentence (column Sents.) and their maximum length were limited by computational resources available to us for parsing the sentences with the XTAG parser. Information about the computing resources used in this work can be found at the beginning part of this section.

6.1.2 Evaluation of HMM_ex

HMM_ex has been trained using the EM-based HMM training algorithm, presented in Section 5.1. The HMM is used to reduce the ambiguity of the set of XTAG elementary tree sequences by weighting them according to their correctness ratio, as defined in (1). Table 1 describes the training dataset over which the HMM has been trained. On average, 1, 300 XTAG elementary tree sequences were related to each sentence in this dataset, in some cases reaching a peak of 70, 000 elementary tree sequences per sentence.

The quality of this HMM was measured according to the first and third evaluation criteria presented in Section 6.1. Figure 7, which concerns with the first criterion, represents the value of (13) during training of the HMM_ex. The ascending behavior of this diagram is evidence for success of the training algorithm. As shown in this figure, the HMM resulting from each iteration is more likely to model the observation sequences than the other HMMs resulting from previous iterations of the training algorithm.

Fig. 7.

Logarithmic scale of likelihood of observing English sentences.

In terms of the disambiguation of the XTAG elementary tree sequences, the success of the model can be measured according to the quality of the BPTs defined in Section 6.1. Table 2 shows the results of this assessment with respect to the gold parse trees of the Penn Treebank. The table shows the precision, recall, and F ₁-score of the bracketing matches of the unlabeled BPTs built from the elementary tree sequences with the highest correctness ratios. The upper bound, in this table, represents the values for parse trees built by the non-statistical Earley-style parser of the XTAG.

Table 2.

Evaluation of unlabeled best parse trees (BPT) built from the XTAG e-tree sequences with the highest correctness ratios

The upper bound in Table 2 shows that the XTAG grammar can provide parse trees of the same quality for both short and long sentences. Column BPT, however, shows that using the disambiguation algorithm, the parse trees built from the short sequences are better than the parse trees built from the long sequences. This is mainly because the accuracy of the disambiguation algorithm depends on the length of the sequence. In addition, the differences between the values of the BPT and the upper bound show that the disambiguation algorithm could not find the best elementary tree sequences for all sentences. In fact, our experiments confirmed that the BPTs could be built from around 60% of the elementary tree sequences suggested by the disambiguation algorithm. In the remaining sequences, the number of erroneous elementary trees are at most two.

6.1.3 Evaluation of HMM_mx

The quality of HMM_mx obtained from Algorithm 2 was measured according to the first and second evaluation criteria presented in Section 6.1. The experiments have been performed on four series of observation sequences assigned to the sentences described in Table 1. The first series contains the most probable MICA elementary tree sequences, the second contains the second most probable MICA elementary tree sequences, and so on.

Regarding the first criterion, the quality of an HMM can be evaluated through the likelihood of observing the observation sequences. Figure 8 represents the logarithm of likelihood of observing each series of MICA elementary tree sequences, given HMM_mx resulting from each iteration of the HMM initializing algorithm.

Fig. 8.

Logarithmic scale of likelihood of observing MICA elementary tree sequences. Each curve is related to a series of MICA elementary tree sequences including most probable, second most probable, and so on.

As shown, after just four steps, the algorithm converges to a stable state after which the rate of increase falls rapidly. The ascending behavior of the curves shows that the HMM resulting from each iteration of the initializing algorithm is more likely than its predecessors to model the observation sequences. It also confirms that the HMM can satisfactorily model all series of observation sequences. Nevertheless, the figure shows that the results does not preserve the order of the series of observation sequences. For instance, the first category, containing the MICA elementary tree sequences with the highest weights, is placed below the third and fourth series.

The second evaluation criterion deals with the amount of entropy involved in the HMM parameters for tracking the observation sequences. Figure 9 represents the mean value of the entropy of distribution of all XTAG elementary tree sequences given the MICA elementary tree sequences and the earlier HMM resulting from the initializing algorithm. In this figure, the curves are related to the different series of MICA elementary tree sequences with respect to the probability assigned to them by the MICA parser. As shown, unlike the first criterion, this criterion maintains the order of the series of observation sequences.

Fig. 9.

The mean value of entropy of the distribution of all XTAG elementary tree sequences, given a MICA elementary tree sequences.

It can clearly be seen that the HMM resulting from the last iteration is more certain to model the MICA elementary tree sequences than the HMMs resulting from the previous iterations. The descending behavior of the curves is evidence for this claim that the distribution of the MICA elementary trees at each hidden state of the HMM is being skewed toward the most likely MICA elementary trees. This property would make the HMM more powerful than HMMs in which observation sequences are uniformly assigned to the hidden states (Johnson Reference Johnson2007). In addition, unlike the previous criterion, which violates the order of the observation series, this criterion shows that the level of uncertainty regarding the best elementary tree sequences is less than for the other sequences. This means that the observation sequences with the highest weights can be modeled more accurately by the HMM. This behavior of the model is also observable for the other series of observation sequences.

6.2.1 Part-of-speech agreement

In order to compute the POS agreement of the model, we need to annotate the test sets with their desired POS tags and compare them with the POS tags defined by XTAG elementary trees. To this end, the statistical POS tagger introduced by Ratnaparkhi (Reference Ratnaparkhi1996) was used. The tagger uses a tag set which consisting of 45 POS tags defined in the Penn Treebank project. In comparison with the small tag set of the XTAG grammar, which contains 12 POS tags, the relatively large number of POS tags used by the tagger makes it difficult to find the corresponding POS tags in each tag set. This problem is due to the fact that the Penn POS tags are more fine-grained than those defined in the XTAG grammar. In fact, most of the POS tags defined in the XTAG grammar can somehow be considered abstractions of a subset of POS tags used in the Penn tag set. For instance, the POS tag N in the XTAG grammar can be considered an abstraction of all the POS tags NN, NNS, NNPS, and NNP in the Penn tag set.

The main obstacle to finding the corresponding POS tags, however, is the difference between the definition of the POS tags provided by each tag set. As an example, the word to in XTAG grammar can be tagged as CONJ (conjunction), P (preposition), or V (verb), but in the Penn POS tag set, it has its own tag TO regardless of whether it is a preposition or an infinitive marker. The other Penn POS tags that can be mapped onto different XTAG POS tags are IN, WP, and ‘,’. Table 4 summarizes the relationship between the POS tags in each of these tag sets.

Table 4.

The relationship between the Penn and XTAG part-of-speech tags

Table 5 shows the amount of POS tag agreement for each of the test sets, with respect to the POS relationship mentioned in Table 4. The results are related to the output of the HMM-based LTAG-mapping phase, before applying the error-correction phase. In comparison with the values reported in Basirat and Faili (Reference Basirat and Faili2013), the table shows a somewhat smaller value for POS agreement for the DTS-CSL, 92.50% as against 94.84%. This does not however convincingly demonstrate the superiority of the LTAG-mapping model proposed in Basirat and Faili (Reference Basirat and Faili2013) over this other work. This is mainly due to the fact that the POS agreement provides only an estimation of the true quality of the system, and the higher values for this criterion do not necessarily confirm the high quality of the sequences. A better criterion is the parsing ability of the models discussed in Section 6.2.3.

Table 5.

The results for POS agreement

The second row of Table 5 shows the average number of POS errors per sentence. The third row shows the p-value of the significance test for the null hypothesis claiming that the reported averages are true. The table shows that number of errors in the test sets containing the longer sentences is higher than that of the test sets with short sentences. This is because the errors mostly occur in the most frequently used POS tags. Figure 10 shows the distribution of POS agreement errors over the desired POS tags of the words. As shown, most of the errors occur in the syntax categories nouns (NN), adjectives (JJ), and prepositions or subordinating conjunctions (IN), which are considered the most frequently used POS tags.

Fig. 10.

Distribution of POS agreement error over the POS tags.

Figure 11 represents the probability of POS agreement errors given the desired POS of the words. As shown, the distribution of POS errors does not follow a regular pattern in the different test sets. For instance, despite the fact that coordinating conjunctions are the most probable sources of error in the DTS-CSL, they are ranked as the fourth most probable sources of error in the DTS-LNG after the syntax categories RB, JJ, and IN. So, it can be concluded that the HMM-based LTAG-mapping does not show a certain and predictable response to the syntax categories of the words. This failure of the model is mainly caused by the fact that the model does not provide any clear way to benefit from the POS tags of the words for assigning the XTAG elementary trees to words. The only syntactic information the model uses for this assignment is the words themselves, and their related MICA elementary trees. This weakness of the model, however, is compensated in the error-correction phase in which the probability distribution of POS tags is used to detect and correct the erroneous XTAG elementary trees.

Fig. 11.

The probability of part-of-speech agreement errors given the desired POS tags.

6.2.2 Grammar compatibility

The grammar compatibility criterion measures the degree of compatibility between the output of the HMM-based LTAG-mapping phase and the word-supertag dictionary provided by the XTAG grammar. According to this criterion, an XTAG elementary tree e assigned to word w is assumed to be correct if e is a member of the set of XTAG elementary trees that the dictionary defines for word w, T_w. This criterion provides an upper estimate of the model’s accuracy and cannot be considered an accurate metric for evaluation of the model. This is mainly because the dictionary only indicates whether or not an elementary tree can be assigned to a word, regardless of the syntactic environment. This problem can be more crucial for words that can be placed in multiple syntactic environments, such as verbs. In fact, it can be expected that the larger the size of the T_w is, the lower the amount of the reliability of the criterion will be for w.

Figure 12 represents the probability of occurrence of grammar compatibility errors for the 20 most frequently observed POS tags, together with the probability of observing the POS tags. The graphs are related to the different test sets described in Table 3, and the POS tags are arranged in ascending order of probability of generating error.

Fig. 12.

The probability of grammar compatibility errors given part-of-speech tag of the words.

As shown in the figure, the most probable sources of error are the POS tags with relatively low frequencies of occurrence. For instance the four most probable sources of error in DTS-LNG are adverbs (RB), personal pronouns (PRP), past participle verbs (VBN), and gerund verbs (VBG), which have frequencies of occurrence of 0.03, 0.01, 0.02, and 0.01, respectively. This confirms the success of the HMM-based LTAG-mapping phase in annotating most of the words in the test sets with the XTAG elementary trees, with reference to the grammar compatibility criterion.

Although the distribution of grammar compatibility errors is not biased toward the most frequently used words, the nature of the errors can make it difficult for the error-correction process to find a proper replacement for the erroneous elementary trees. This is mainly because the errors mostly occurred in the words associated with a large number of elementary trees in the grammar dictionary. Table 6 provides some information about the number of single-anchor elementary trees in the dictionary used by the XTAG grammar. According to this table, one of the most probable sources of error, verbs, can be associated on average with around 45 elementary trees regardless of the syntactic environment. The same situation can be observed for the nouns and adjectives.

Table 6.

Distribution of part-of-speech tags in XTAG word-supertag dictionary

Table 7 summarizes the results achieved by the grammar compatibility evaluation before proceeding to the error-correction phase. The first row of this table shows the amount of grammar compatibility over all of the words observed in the test sets. The second and third rows respectively represent the average number of grammar compatibility errors per sentence and the p-value of the significance test for the null hypothesis claiming the reported averages are true. As shown, the degree of grammar compatibility depends on the length of the sentences.

Table 7.

The results of grammar compatibility

6.2.3 Parsing quality

The quality of parse trees is studied based on three criteria introduced in Section 6.2, full-parse rate, accuracy of parse tree, and parsing speed.

The full-parse rate of the LTAG-mapping model refers to the percentage of the XTAG elementary tree sequences that can result in a parse tree for their sentences. In fact, the full-parse rate measures the amount of consistency between the elementary trees assigned to words of a sentence with respect to the tree attachment operations defined in LTAG formalism, substitution and adjunction. Unlike the POS agreement and grammar compatibility criteria, which assess the elementary trees individually, this criterion attempts to assess the quality of a sequence of elementary trees.

Table 8 represents the full-parse rate of the test sets with respect to parameter n of the error-correction phase. As mentioned before, each of the test sets contains some sentences that cannot be parsed in the XTAG grammar (see Table 3). The column X-P represents the full-parse rate of the sentences that can be parsed in the XTAG grammar. The column All, however, represents the full-parse rates regardless of whether the sentences can be parsed in the XTAG grammar or not. The first row of the table, where n is 0, shows the values for full-parse rate when the error-correction phase is completely bypassed. In this case, output of the HMM-based LTAG-mapping phase would be directly passed onto the LTAG parser. Hence, it would properly measure the quality of the HMM-based LTAG-mapping phase. In order to compare our model with the previous LTAG-mapping, we have also computed the full parse rate values of the LTAG-mapping model introduced in Basirat and Faili (Reference Basirat and Faili2013) (row Model-CSL). The upper bound has also been computed as the percentage of sentences that can be parsed in the XTAG grammar using the original XTAG parser.

Table 8.

The percentage of parsed sentences

In an overall view, in comparison with the values for Model-CSL, Table 8 shows dramatic improvements in the LTAG-mapping model. This can be seen in both the HMM-based LTAG-mapping phase and the error-correction phase. Hence, it can be concluded that not only the error-correction model, but also the HMM training method could be helpful for this success.

The increase of the full parse rate shown in Table 8 can be considered as evidence for the success of the error-correction phase in rectifying the output of the HMM-based LTAG-mapping phase. As shown, the error-correction phase could significantly compensate the main weakness of the HMM-based LTAG-mapping phase in processing the long sentences. Despite the large differences between the values related to the HMM-based LTAG mapping (first row), the table shows similar results for the test sets after the error-correction phase. In addition, it shows a direct relationship between the parameter n of the error correction and number of parsed sentences.

The accuracy of parse trees is examined with respect to the gold bracketing available in the Penn Treebank. The phrase structure bracketing produced by the XTAG-based parse trees has been compared with the bracketing in the treebank according to the PARSEVAL evaluation technique (Abney et al. Reference Abney, Flickenger, Gdaniec, Grishman, Harrison, Hindle, Ingria, Jelinek, Klavans, Liberman, Marcus, Roukos, Santorini and Strzalkowski1991). This method is based on the precision and recall of the matched brackets. The precision and recall of matched brackets are defined as the total number of bracketing matches M with respect to number of bracketings returned by the XTAG-based parse trees X (M/X) and with respect to the number of treebank bracketings C (M/C), respectively. A merged description of these metrics is their F ₁-score which is defined as (2 × precision × recall)/(precision + recall). Because of the differences between the internal nodes of the elementary trees in the XTAG and MICA grammars, the parse trees have been compared in unlabeled mode.

Table 9 represents the precision, recall, and F ₁-score of the BPTs of the XTAG elementary tree sequences with respect to the gold parse trees in the Penn Treebank. As mentioned in Section 6.1, among the parse trees that can be built from a sequence of elementary trees, the one with the highest F ₁-score is assumed to be the BPT of that sequence. We have also computed the quality of parse trees resulting from the LTAG-mapping model introduced in Basirat and Faili (Reference Basirat and Faili2013) (row Model-CSL). Upper bound represents the accuracy of the BPTs obtained from the original XTAG parser. Since the parser has the ability to generate all parse trees for a given sentence, the accuracy of the best one is considered as the upper bound for parsing in the XTAG grammar.

Table 9.

The precision (p), recall (r), and F ₁-score (f) of the best parse trees (BPT) generated from XTAG elementary tree sequences

As shown in Table 9, the values for recall are remarkably higher than the values for precision. This is mainly because the structures of the XTAG-based parse trees are relatively larger and deeper than those of the Penn bracketing. The table also shows that the error-correction phase could successfully improve the quality of the parse trees generated from the HMM-based LTAG-mapping phase (when n is 0). However, it can be seen that increasing the value of n does not necessarily improves the quality of the parse trees, though it does increase the values for full-parse rate (see Table 8).

The row Model-CSL in the table shows that our model could result in better parse trees than the previous work. However, unlike the full parse rate criterion, which clearly confirms the success of both the HMM-based LTAG-mapping phase and the error-correction phase, Table 9 shows that in some cases (DTS-MED, and DTS-LNG) the parse trees obtained from the HMM-based LTAG-mapping phase are worse than the previous model. This weakness of the HMM-based LTAG-mapping phase is mitigated in the error-correction phase. So, having both the HMM-based LTAG-mapping phase and the error-correction phase, the LTAG-mapping model could outperform the previous LTAG-mapping model with respect to full parse rate and the accuracy of parse trees.

In comparison with the upper bound, surprisingly, it can be seen that in some cases the unlabeled parse trees generated by the LTAG-mapping model are better than the parse trees generated by the XTAG parser. For instance, in DTS-CSL, when n is 15, the F ₁-score is higher than the upper bound. This shows that some of the elementary trees suggested by the LTAG-mapping model are structurally more appropriate for the input words than the set of elementary trees associated with them in the XTAG grammar. This is mainly because of the XTAG grammar’s failure to cover all of the syntactic environments in which the words can appear. Nevertheless, using the word-based model, which relies on the POS tag of the words (see (12)), the LTAG-mapping model could somewhat compensate this weakness of the grammar. In the model, by focusing on the POS tags instead of the grammar rules defined in the grammar dictionary, the model could extend the set of XTAG elementary trees that can be assigned to the word.

In this part, we study the parsing speed of the LTAG-mapping model, which is one of the main contributions of this work. Using the parsing system introduced in Section 4, the amount of time required to parse a sentence is the sum of the time required to perform the three main steps of supertagging, LTAG mapping, and LTAG parsing. The basic algorithms running in the first two steps are (1) the maximum entropy decoder, which is used in the supertagging step, (2) the Viterbi algorithm, and (3) the word-based decoder, which are used in the LTAG mapping step. The most important factor in the time complexity of these algorithms is the sentence length. The LTAG parsing, however, is affected by both the grammar size (i.e., number of elementary trees assigned to the words and maximum number of nodes in an elementary tree) and sentence length. Sentence length is an external factor that an input sentence imposes on the parsing system. We have no control over the sentence length. The grammar size, however, can be controlled by the parameter n of the error-correction phase.

Figure 13 represents the average time required to parse each sentence of the test sets with respect to the parameter n of the error-correction phase. As the figure shows, the sentences of DTS-CSL can almost be parsed in a reasonable time regardless of the values of parameter n. It shows that parameter n has little effect on the parsing speed of small sentences. On the other hand it shows large increases in the parse time of the DTS-MED and DTS-LNG, which contain longer sentences, when the value of parameter n is increased. This is the direct consequence of the fact that increasing the length of the sentences will also increase the probability of occurrence of error. This, in turn, will increase the amount of syntactic lexical ambiguity, the main contributor to parsing speed (Sarkar Reference Sarkar2007).

Fig. 13.

The relative speed of parsing for each sentence.

We have also computed the average time required to parse the test sets using the parsing system introduced in Basirat and Faili (Reference Basirat and Faili2013). In order to preserve the compatibility of this part with the previous discussions, we will refer to this system as Model-CSL. The parser cannot strictly be compared with the parsing system introduced in Section 4 because of two reasons: First, the error-correction phase is not included in the Model-CSL parsing system. The error-correction phase has negative effects on the parsing speed. In addition to the extra step that it imposes on the process of parsing, it increases the size of the grammar that is analyzed by the LTAG parser. So, it would be sensible to expect the Model-CSL parsing system to be faster than the current one, because the input words in the former model are associated with fewer elementary trees. Second, there are many sentences in the test sets that could not be parsed by the Model-CSL parsing system but could by the new model. We have shown in the Table 8 that a large portion of the test sets could not be parsed by the Model-CSL parsing system. The average lengths of these sentences in DTS-CSL, DTS-MED, and DTS-LNG are 10.65, 18.46, and 18.86, respectively.

Given all of this, it can be concluded that the parsing systems are comparable if (1) the error-correction phase is bypassed in the new model (i.e., n is 0), and (2) the test sets only include those sentences that can be parsed by both of the parsing systems. In this situation, the average time required for parsing the sentences in the test sets using the Model-CSL parsing systems is 0.01 which is equal to the new model. From the viewpoint of the end user, however, the models are compared regardless of their internal differences. In this case, the parsing speed in Model-CSL, which is 0.01 for all test sets, can be compared with the parsing speed in the new model, represented in Figure 13. It can be clearly seen that the Model-CSL is faster than new model.

Our experiments confirm that the parsing system introduced in this paper is faster than the original XTAG parser. Using the XTAG parser, the average time required for parsing the sentences in DTS-CSL, DTS-MED, and DTS-LNG is around 900 seconds. As shown in Table 3, the sentence pool contains 1579 sentences with a maximum length of 25 words.

To summarize, according to three evaluation criteria full-parse rate, accuracy of parse trees, and parsing speed, the best result of the LTAG-mapping model is related to values of n between 5 and 15. In fact, in this range, we would have a trade-off between the quality of parse trees and the time required to generate them.