{'fraction_non_alphanumeric': 0.031152084839720415, 'fraction_numerical': 0.010183176669076886, 'mean_word_length': 4.8133099824868655, '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': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Statistical Models for Deep-structure Disambiguation

In this paper, an integrated score function is proposed to resolve the ambiguity of deepstructure, which includes the cases of constituents and the senses of words. With the integrated score function, different knowledge sources, including part-of-speech, syntax and semantics, are integrated in a uniform formulation. Based on this formulation, different models for case identification and word-sense disambiguation are derived. In the baseline system, the values of parameters are estimated by using the maximum likelihood estimation method. The accuracy rates of 56.3% for parse tree, 77.5% for case and 86.2% for word sense are obtained when the baseline system is tested on a corpus of 800 sentences. Afterwards, to reduce the estimation error caused by the maximum likelihood estimation, the Good-Turing's smoothing method is applied. In addition, a robust discriminative learning algorithm is also derived to minimize the testing set error rate. By applying these algorithms, the accuracy rates of 77% for parse tree, 88,9% for case, and 88.6% for sense are obtained. Compared with the baseline system; 17.4% error reduction rate for sense discrimination, 50.7% for case identification, and 47.4% for parsing accuracy are obtained. These results clearly demonstrate the superiority of the proposed models for deep-structure disambiguation.


I Introduction
For many natural language processing tasks, e.g., machine translation, systems usually require to apply several kinds of knowledge to analyze input sentence and represent the analyzed results in terms of a deep structure which identify the thematic roles (cases) of constituents and the senses of words. However, ambiguity and uncertainty exist at the different levels of analysis. To resolve the ambiguity and uncertainty, the related knowledge sources should be properly represented and integrated. Conventional approaches to case identification usually need a lot of human efforts to encode ad hoc rules [1,2,3]. Such a rule-based system is, in general, very expensive to construct and difficult to maintain. In contrast, a statistics-oriented corpus-based approach achieves disambiguation by using a parameterized model, in which the parameters are estimated and tuned from a training corpus. In such a way, the system can be easily scaled up and well trained based on the well-established theories.
However, statistical approaches reported in the literature [4,5,6,7] usually use only surface level information, e.g., collocations and word associations, without taking structure information, such as syntax and thematic role, into consideration. In general, the structure features that characterize long-distance dependency, can provide more relevant correlation information between words. Therefore, word association information can be trained and applied more effectively by considering the structural features. In many tasks, such as natural language understanding and machine translation, deep-structure information other than word sense is often required. Nevertheless, few research was reported to provide both thematic role and word sense information with statistical approach.
Motivated by the above concerns, an integrated score function, which encodes lexical, syntactic and semantic information in a uniform formulation is proposed in this paper. Based on the integrated score function, the lexical score function, the syntactic score function, and the semantic score function are derived. Accordingly, several models encoding structure information in the semantic score formulation are proposed for case identification and word-sense discrimination.
To minimize the number of parameters needed to specify the deep-structure, a deepstructure representation form, called normal form which adopts "predicate-argument" style, is used in our system. By using this normal form representation, the senses of content words and the relationships among constituents in a sentence can be well specified. The normal form used here is quite generalized and flexible; therefore, it is also applicable in other tasks. When the parameters of the proposed score function are estimated with the maximum likelihood estimation (MLE) method, the baseline system achieves parsing accuracy rate of 56.3%, case identification rate of 77.5%, and 86.2% accuracy rate of word sense discrimination. Furthermore, to reduce the estimation error resulting from the MLE, Good-Tudng's smoothing method is applied; significant improvement is obtained with this parameter smoothing method. Finally, a robust discriminative learning algorithm is derived in this paper to minimize the testing set error, and very promising results are obtained with this algorithm. Compared with the baseline system; 17.4% error reduction rate for sense discrimination, 50.7% for case identification, and 47.4% for parsing accuracy are obtained. These results clearly demonstrate the superiority of the proposed models for deep-structure disambiguation.

The Integrated Score Function
The block diagram of the deep-structure disambiguation system is illustrated in Figure 1. As shown, the input word sequence is first tagged with the possible part-of-speech sequences. A word sequence would, in general, correspond to more than one part-of-speech sequence. The parser analyzes the part-of-speech sequences and then produces corresponding parse trees. Afterwards, the parse trees are analyzed by the semantic interpreter, and various interpretations represented by the normal form are generated. Finally, the proposed integrated score function is adopted to select the most plausible normal form as the output. The formulation of the scoring mechanism is derived as follows. The derivations of these score function are addressed as follows.

The Lexical Score
The lexical score for the k-th lexical (part-of-speech) sequence T k associated with the input word sequence W is expressed as follows:

The Syntactic Score
The tree in Figure 2 is used as an example to explain the syntactic score function. The basic derivation of the syntactic score includes the following steps. eFirst, the tree is decomposed into a number of phrase levels, such as /-t,/-2,'", L~ in Fig. 2. • Secondly, the transition between phrase levels is formulated as a context-sensitive rewriting process. With the formulation, each transition probability between two phrase levels is calculated by consulting a finite-length window that comprises the symbols to be reduced and their left and right contexts. .

FIGURE 2. The decomposition of a given syntactic tree X into different phrase levels.
Let the label t i in Fig. 2 be the time index for the i-th state transition, which corresponds to a reduce action, and /~ be the i-th phrase level. Then the syntactic score of the tree L A in Figure 2 is defined as follows [8,9]: where ¢ and $ correspond to the begin-of-sentence and the end-of-sentence symbols, respectively; I i and r~ stand for the left and right contextual symbols to be consulted in the i-th phrase level. If M number of left contextual symbols and N number of right contextual symbols are consulted in computation, the model is said to operate in the LMRN mode.
Note that each pair of phrase levels in the above equation corresponds to a change in the LR parser's stack before and after an input word is consumed by a shift operation. Because the total number of shift actions, equal to the number of product terms in the above equation, is always the same for all alternative syntactic trees, the normalization problem is resolved in such a formulation.
Moreover, the syntactic score formulation provides a way to consider both intra-level contextsensitivity and inter-level correlation of the underlying context-free grammar. With such a formulation, the capability of context-sensitive parsing (in probabilistic sense) can be achieved with a context-free grammar.

T h e S e m a n t i c S c o r e
To simplify the computation of the semantic score, a structure normalization procedure is taken beforehand by the semantic interpreter to convert a parse tree into an intermediate normal form, called normal form one (NF1), which preserves all relevant information for identification of cases and word senses. The implementation of the normalization procedure includes a syntactic normalization procedure and a semantic normalization, procedure.
In the syntactic normalization procedure, many parse trees that are syntactically equivalent should be normalized first. Such syntactic variants may result from a writing convention, function words, or non-discriminative syntactic information, such as punctuation markers. Excessive nodes for identifying the various bar levels in the phrase structure grammar are also deleted or compacted.
Afterwards, different syntactic structures that are semantically equivalent are normalized to the desired normal form (NF) structure. In the NF representation, the tense, modal, voice and type information of a sentence are extracted as features. By taking the sentence "To meet spectrumanalyzer specification, allow a 30-rain warm-up before making any measurement." as an example, the parse tree, NF1, and the desired normal form structure are illustrated in Figure 3.
To compute the semantic score, the normal form is first decomposed into a series of production rules in a top-down and leftmostfirst manner, where each decomposed production rule corresponds to a "case subtree". For instance, the normal form in Figure 3 Similarly, the NF1 structure is also decomposed into another set of production rules, each of which corresponds to a Normal Form One (NF1) subtree. For example, the NF1 structure in Figure 3 In such a way, the semantic score can be defined in terms of the case subtrees and the NF1 subtrees.  I  l  I  I  :  I  I  I  I  I  I  I  I  I  I I  I  I  n  I  I  I  I  quan  n  I  I  [  I  I  I  I  I  I  I  I  I  I  I I  I  \  I  I  I  I  I  \   I  HEAD  HEAD  I  I  I  I  QUANT  HEAD   I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  meet#3 spectrum-specifi-allow#l 30-min warm-up make#2 any measurement analyzer cation  where ~ denotes the possible NF1 structures with respect to N i and Ly. Theoretically, a parse trees may be normalized into more than one NF1 structure; however, this happens seldom in our case. That is, it is almost true that the normalization procedure can be considered as a one-to-one mapping, which indicates P(O}Lj, Tk,W)=I in our task. Under this assumption, the semantic score can be simplified as: Since the normal form comprises the cases of constituents and the senses of content words, Different models for case identification and word-sense disambiguation are further derived below.

• Case Identification Models
To derive the case identification model, it is assumed that the required information for case Again, the number of parameters required to model such a formulation is still too many to afford, unless more assumptions are made.
Since the decomposition of the normal form structures has been carried out in the top-down and lefimost-first manner, the case subtree Ft,,, depends on its previously decomposed case subtrees, which are either the siblings or the ancestors of the subtree Fi, m . Therefore, in addition

Word-sense Disambiguation Model
To make the word-sense score function feasible for implementation, we further assume that the senses of words depend only on the case assigned to the words, the parts-of-speech, and the words themselves only. Therefore, the word sense score function is approximated as follows.

Experimental Setup
A. Corpora: 3,000 sentences in English, extracted from computer manuals and related documents, are collected and are parsed by the BehaviorTran system [10], which is a commercialized Englishto-Chinese machine translation system developed by Behavior Design Corporation (BDC). The correct part-of-speech, parse trees and normal forms for the collected sentences are verified by linguistic experts. The corpus is then randomly partitioned into the training set of 2,200 sentences and the testing set of the remaining 8,00 sentences to eliminate possible systematic biases. The average number of words per sentence for the training set and the testing set are 13.9 and 13.8, respectively. On the average, there are 34.2 alternative parse trees per sentence for the training set, and 31.2 for the testing set.
B. Lexicon: In the lexicon, there are 4,522 distinct words extracted from the corpus. Different sense definitions of these words are extracted from the Longman English-Chinese Dictionary of Contemporary English. For those words which are not included in the Longman dictionary, their sense are defined according to the system dictionary of the BehaviorTran system. In total, there are 12,627 distinct senses for those 4,522 words.

C. Phrase Structure Rules:
The grammar is composed of 1,088 phrase structure rules, expressed in terms of 35 terminal symbols (parts of speech) and 95 nonterminal symbols. D. Case Set: In the current system, the case set includes a total number of 50 cases, which are designed for the next generation BehaviorTran MT system. Please refer to [11] for the details of the case set.
To evaluate the performance of the proposed case identification models, the recall rate and the precision rate of case assignment, defined in the following equations, are used.

Results and Discussions
In the baseline system, the parameters are estimated by using the maximum likelihood estimation (MLE) method. The results of the deep-structure disambiguation system with the AiSo+CD model is summarized in Table 1. For comparison, the performance of the parser, without combined with the semantic interpreter, is also listed in this table. As expected, the accuracy of parse tree selection is improved as the semantic interpreter is integrated. When the error of the baseline system was examined, we found that a lot of errors occur because many events were assigned with zero probability. To eliminate this kind of estimation error, the parameter smoothing method, Good-Turing's formula [12], is adopted to improve the baseline system. The corresponding results are listed in the third column of Table 1, which show that parameter smoothing improves the performance significantly.
In addition, a robust learning algorithm, which has been shown to perform well in our previous work [9], is also applied to the system to minimize the error rate of the testing set. The basic idea for the robust learning algorithm to achieve robustness is to adjust parameters until the score differences between the correct candidate and the competitors exceed a preset margin. The parameters trained in such a way, therefore, provide a tolerance zone for the mismatch between the training and the testing sets. Readers who are interested in details of the learning algorithm are referred to [ 11 ]. When the robust learning algorithm is applied, very encouraging result is obtained. Compared with the baseline system, the error reduction rate is 50.7% for case and 17.4% for sense discrimination, and 47.4% for parsing accuracy. As the parser, before coupling with the semantic interpreter, is considered, the performance is improved from 50.1% to 77.0%, which corresponds to 53.9% error reduction.

Error Analysis
To explore the areas for further improving the deep-structure disambiguation system, the errors for 200 sentences extracted randomly from the training corpus have been examined. It is found that a very large portion of error come from the syntactic ambiguity. More precisely, most syntactic errors result from attachment problems, including prepositional phrase attachment and modification scope for adverbial phrases, adjective phrases and relative clauses. Only less than 10% of errors arise due to incorrect parts-of-speech. Since the normal form cannot be correctly constructed without selecting the correct parse tree, errors of this type deteriorate system performance most seriously.
In addition, errors for case identification is one of the problems that make the deep-smoothing method is also applied. Parameter smoothing is shown to improve the performance significantly. Finally, the parameters are adapted by using the robust discriminative learning algorithm. With this learning algorithm, 17.4% error reduction rate for sense discrimination, 50.7% for case and 47.4% for parsing accuracy are obtained compared with the baseline system. These results clearly demonstrate the superiority of the proposed models for deep-structure disambiguation.