{'fraction_non_alphanumeric': 0.037585482741909426, 'fraction_numerical': 0.01023100533089225, 'mean_word_length': 5.025957170668397, 'pattern_counts': {'":': 0, '<': 1, '<?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}}
Syntactic Ambiguity Resolution Using A Discrimination and Robustness Oriented Adaptive Learning Algorithm

In this paper, a discrimination and robustness oriented adaptive learning procedure is proposed to deal with the task of syntactic ambiguity resolution. Owing to the problem of insufficient training data and approximation error introduced by the language model, traditional statistical approaches, which resolve ambiguities by indirectly and implicitly using maximum likelihood method, fail to achieve high performance in real applications. The proposed method remedies these problems by adjusting the parameters to maximize the accuracy rate directly. To make the proposed algorithm robust, the possible variations between the training corpus and the real tasks are also taken into consideration by enlarging the separation margin between the correct candidate and its competing members. Significant improvement has been observed in the test. The accuracy rate of syntactic disambiguation is raised from 46.0% to 60.62% by using this novel approach.


Introduction
Ambiguity resolution has long been the focus in natural language processing. Many rule-based approaches have been proposed in the past, However, when applying such approaches to large scale applications, they usually fail to offer satisfactory pertbrmance. As a huge amount of fine-grained knowledge is required to solve the ambiguity problem, it is quite difficult for rule-based approach to acquire the huge and fine-grained knowledge, and maintain consistency among them by human [Su 90a].
Probabilistic approaches attack these problems by providing a more objective measure on the preference to a given interpretation. Then, these approaches acquire huge and fine grained knowledge, or parameters in statistic terms from the corpus automatically. The uncertainty problem in linguistic phenomena is resolved on a more solid basis if a probabilistic approach is adopted. Moreover, the knowledge acquired by the statistical method is always consistent because the knowledge is acquired by jointly considering all the data in the corpus at the same time. Hence, the time for knowledge acquisition and the cost to maintain consistency are significantly reduced by adopting those probabilistic approaches.
To resolve the problems resulting from syntactic ambiguities, a unified statistical approach for ambiguity resolution has been proposed by Su [Su 88,92b]. In that approach, all knowledge sources, including lexical, syntactic and semantic knowledge, are encoded by a unifiedprobabilistic score function with a uniform formulation. This uniform probabilistic score function has been successfully applied in spoken language processing [Su 90b,91b,92a] and machine translation systems [Chen 91] to integrate different knowledge sources for ambiguity resolution.
In implementing this unified probabilistic score function, values of score functions are estimated from the data in the training corpus. However, due to the problem of insufficiency of training data and incompleteness of model knowledge, the statistical variations between the training corpus and the real application are usually not covered by this approach. Therefore, the performance in the testing set sometimes gets poor in the real application.
To enhance the capability of discrimination and robustness of those proposed score function, a discrimination-oriented adaptive learning is proposed in this paper. And then, the robustness of this proposed adaptive learning procedure is enhanced by enlarging the margin between the correct candidate and its confusing candidates to achieve maximum separation between different candidates.
Since the implementation of this adaptive learning procedure is based on the uniform probabilistic score function, we will first briefly review the unified probabilistic score function. Readers who are interested in the details about the uniform probabilistic score function please refer [Chen 91, Su 91b, 92a, 92b].
Next, we assume the information, from the word .sequence w] ~, required for syntactic ambiguity resolution, has percolated to the lexical interpretation Lezj. Also, only little additional information can be provided from w] ~ for the task of disambiguating syntactic interpretation ~yuj after the lexical interpretation Lexj is given. Thus, rite syntactic score can be approximated as shown in t~t. (3): .'~.,~,, (Syn:)= l'(Sy% I Lex~,w'~ ') ~ I'(Sy% I Le%).
Such a formulation "allows us to use both lexical and syntactic knowledge in assigning preference measure m a syntactic tree. in the real computation, log operation is used to convert the operations of multiplication to the operations of addition. The following equation shows the final form in the real application.

Syntactic Score Function
To show the computing mechanism for the syntactic score, we take the syntax tree in Fig.1 as an example. The syntax tree is decomposed into a number of phrase levels. Each phrase level (also called a sententialform) consists of a set of symbols (terminal or nontenninal) which can derive all the temfin',d symbols in a sentence. Let label t i in  (9) where syn A is the parse tree, and LI through L 8 represent different phrase levels. Note that the product terms in the last formula correspond to the rightmost derivation sequence in a general LR parser [Su 91c], with left and right contexts taken into account. Therefore, such a formulation is especially useful for a generalized LR parsing algorithm, in which context-sensitive processing power is desirable.
Although the context-sensitive model in the above equation provides the ability to deal with intra-level context-sensitivity, it falls to catch interlevel correlation. In addition, the formulation of Eq.(9) gives rise to the normalization problem for ambiguous syntax trees with different number of nodes. An alternative to relieve this problem is to compact multiple highly correlated phrase levels into one in evaluating the syntactic scores. Tile formulation is expressed as follows [Su 91c In Table 1, the log word-to-category score, log (P (e ] to)), for each word is estimated from the training corpus by calculating their relative frequencies. For exanrple, in the training corpus, the word 'T' is used as pronoun for 60 times, and 40 times as noun. Then, the log word-to-category scores can be calculated as follows.
In this example, there are 2"2"2"1=8 possible different ways to assign lexical categories to the input P(L~,LT,L~ [ L~) × P(Lr~ I L4) x P(L4,L~ I L~) × P(L7 I LQsentence. When these 8 possible lexical ,sequences P(La I Lr,) × P(Ln I L4) × P(L4 I L~) × I' (L~, I Lt) (10) Because thc number of shifts, i.e., the number of terms in Eq.(lO), is always the same for all ambiguous syntax trees, the normalization problem is then resolved. Moreover. it provides a way to consider both intra-level context-sensitivity and inter-level correlation of the underlying context-free grammar. With such a score function, the capability of context-sensitive parsing (in probability sense) can be achieved with a context-free grammar.

Discrimination and Robustness Oriented
Adaptive Learning

Concepts of Adaptive Learning
The general idea of adaptive learning is to adjust the model parameters (in this paper, they are lexical scores and syntactic scores) to achieve the desired criterion (in our case, it is to minimize the error rate). To explain clearly how the adaptive learning works, we take the sentence "1 saw a man." as an example. The lexical category (i.e,, part of speech) and its corresponding log score for each word are listed in Table 1. are parsed, only four of them are accepted by our parser. They are listed as follows: 1. pron vt art n 2. n vt art n 3. pron vi prep n 4. n vi prep n.
The syntactic scores of different parse trees are then calculated according to Eq.(10). A parse tree corresponding to the lexical sequence "[pron vt art n]" is drawn below as an example. According to Eq.(5), the total log integrated score (log Slez+logSsvn) for each parsed sentence hypothesis is calculated. For example, the log lexical score for "I/[pron] saw/[vt] a/[art] man/In]" = (-0.22-0.16-0.02-0)= -0.4. Finally, the log integrated scores for the above grammatical inputs are listed as follows: candidate-1, log integrated score = (-0.40-1. To remedy this error, adaptive learning procedure is adopted to adjust the score values iteratively, including lexical and syntactic scores, until the integrated score of the correct candidate (i.e., candidate 1) raises to the highest rank. In this paper, parameters which are adjusted by adaptive learning procedure are those log scores, including log P (c/q I wi), logP(ek,]ck,-i ~ and logP(LilL~-l). The amount of adjutstment in each iteration depends on the misclassihcation distance. Misclassification distance is defined as the difference between the score of the top candidate and that of the correct one. (In the above example, distance = (score of correct candidate)-(score of top candidate) = (-1.90)-(-1.57)= -0.33). From iteration to iteration, the parameters (both lexical and syntactic scores) are adjusted so that the integrated score of the correct candidate is increased, and the integrated score of the wrong candidate is decreased at the same time.
The learning procedure for a sentence is stopped when the candidate of this sentence is correctly selected. To make the explanation of this adaptive learning procedure clear, we assume lexical scores are unchanged during learning. That is, only the paranteters of the syntactic scores are adjusted. The details of adaptive leanling for adjusting syntactic scores are listed as follows: hdtlal (where * denotes the top candidate, and A denotes the desired candidate) It is clear that after the second iteration, paranaeters have been adjusted so that the desired candidate (i.e., candidate 1) would be selected.

Procedure of Discrimination Learning
Since correct decision only depends upon correct rank ordering of the integrated scores for all ambiguities, not their real value, a discriminationoriented approach should directly pursue correct rank ordering. To derive the discrimination function, the probability scores mentioned above are first jointly considered. Then, a discrimination-oriented function, namely g (.), is defined as a measurement of above mentioned score functions, so that it can well pre~rve the correct rank ordering [Su 91a]. Here,9(')  where .h,, (i) = logP (ckA%; .... 1'), and A,v,, (i) = logP(LdLi-:). Both stand for the log lexical score and the log syntactic score of the i-th word for the k-th syntactic ambiguity, respectively. In addition, Wle z and Wsyn correspond to the weights of lexical and syntactic scores, respectively. If the parse tree of a sentence is misselected, the parameters (i.e., the lexical and the syntactic scores) are adjusted via the proposed adaptive learning procedure. Otherwise, no parameters would be adjusted. When misselection occurs, the misclassification distance, dso is less than zero. This misclassification distance is defined as the difference between the log integrated .score of the correct candidate and that of the top one. A specific term of the syntactic score components in the (t+l)-th itera-A(t+l) lion of the correct candidate, say sv,* (j), would be adjusted as follows:

I=]
" leX tlJ + iOst/n " (15) where do is a constant which stands for a window size, and e is the learning constant for controlling the speed of convergence. The learning rule for adjusting the lexical scores can be represented in a similar manner. Notice that only the parameters of the top candidate and those of the correct candidate would be adjusted when misselections occur. Those parameters of other wrong candidates would not be adjusted in this adaptive leaming procedure. From Eq.(13), (14) and (15), it is clear that the score of the correct candidate will increase and that of wrong candidate will decrease from iteration to iteration until the correct candidate is selected. For the purpose of clarity, the detailed derivations of the above adaptive learning procedure will not be given hem. Interested readers can contact the authors for details.

Robustness Issues
Since it is easy to improve the performance in a training set by adopting a model with a large number of parameters, the error rate measured in the training set frequently turns out to be over-optimistic. Moreover, the parameters estinlated from the training corpus may be quite differ from that obtained from the real applications. These phenomena may occur due to the factors of finite sampling size, style mismatch, or domain mismatch, etc. To achieve a better perlbrmance in the real application, one must deal with the possible mismatch of parameters, or statistical variation between the training corpus and the real application. One way to achieve this goal is to enlarge the inter-class distance to achieve maximum separation [Su 91a] between the cot:ect candidate and the other candidates. That is, this approach provides a tolerance zone between different candidates for allowing possible data scattering in the real application.
Traditional adaptive learning methods [Amar 67, Kata 90] stop adjusting parameters once the input pattern has been correctly classified. However, if we stop adjusting parameters under the condition that the observations are correctly classified in the training corpus, the distance between the correct candidate and other ambiguities may still be too small. Thus, it is vulnerable to deal with possible modeling errors and statistical variations between the training corpus and the real application. Su [Su 91a] has proposed a robust learning procedure which continues to enlarge the margin between the correct candidate and the top one, even if the syntax tree of the sentence has been correctly seleeted. That is, the parameters will not be adjusted only if the distance between the correct candidate and the others has exceeded a given threshold. The learning rules in Eq.(13), (14) are then modified as follows. If dsc _< 6, where 6 is a preset margin, the syntactic score in the (t+l) iteration tor the correct candidate is adjusted according to the following formulas: (,~(t+l) ll)

Simulations
The following experiments are conducted to ilivestigate the advmltage of the proposed discrimination and robustness oriented adaptive leanfing pro_ cedure. In the experiments, 4,000 sentences, which are extracted from IBM tectmical manuals are first associated with their conesponding correct category sequences and correct parsed trees by linguists. The corpus are then partitioned into a training corpus of 3,2(X) sentences and a test set of 800 sentences. Next, the lexical and syntactic probabilities are estimated from the data in the training corpus. Afterwards, the sentences in the test set a~e used to evaluate rite perlomtance of the proposed algorithm using the estimated lexical and syntactic probabilities. This integrated score timction apploach using the estimated probabilities is considelcd as the baseline system. Performances of discrimination ufi~ ented adaptive learnings with and widtout robustness enhancement are then evaluated. The accuracy rate of the syntactic ambiguity resolution for the training corpus and rile test set are summarized in Table 3. (Note that the top candidate is selected t?om all po~ible parses allowed by tile gmntmars of the system; therefore, the baseline perlonnance is evaluated under a highly ambiguous environment.)  Table 3 shows that syntax tree accuracy ~ate is improved from 46% to 56.88% using the basic version of discrimination oriented adaptive learning procedure. This significant iiuprovement shows the superiority of the adaptive learning procedure for dealing with the disambiguation task. l:unhenuore, when the rt)bust versiou of leanfiug proccdure is adopted, the perfommnce is iml)roved further (flora 56.88% to 60.62%). It means that the rohuslness of the learning procedure is indeed enhanced by enlarging the distance between the correct candidate and other candidates. Moreover, not only the accuracy rate of syntax trec is improved using adaptive learning, but al~ that of lexical sequence is improved. In this paper, a lexical sequence is ~egarded as "correct" only if all the lexical categories in a sentence perfectly match those selected by linguists. In other words, we are measuring "sentence accurac3: rate" in contract tu "word accuracy rate" as adopled ill [Chur 88,Gal~ 87]. Table 4 shows that file basic version of adaptive leaming procedule ilnproves the sentence accuracy rate of lexicol sequences a|xmt 5% (from 77.12% to 82.38%). Again, with the robust version of learning, the accurate rate of lexical sequences is greatly enbanced. The behavior of cach iteration of the adaptive learning process is shown in Figure 2. Through observing this figure, we can conclude that if the robustness issues are not considered during learning, the performance of tile test set would decrease as the training t)~ocess goes on. This is the phenomena of river-tuning, llowever, by h~rcing the learning procedure to continue unlil the separation between the correct candidate and the top one exceeds the desired margin, the performmlce of the test set can be t'utther improved, and no degradation phenomenon is observed.

Summary
Because of insufficient training data, and ap- [Su 88] proximation error introduced by the language model, traditional statistical approaches, which resolve ambiguities by indirectly and implicitly using maximum likelihood method, fail to achieve high performance in real applications. To overcome these [Su 90a] problems, adaptive learning is proposed to pursue the goal of minimizing discrimination error directly. The performance of syntactic ambiguity resolution is significantly improved using the discrimination [Su 90b] oriented analysis. In addition, the sentence accuracy rate of the lexical sequences is also improved. Moreover, the performance is further enhanced by using the robust version of learning procedure, which enlargeds the margin between the correct candidate and its candidates. The final resuits show that using the basic version of learning, [Su 91b] the syntax tree selection accuracy rate is improved about 10% (from 46% to 56.88%), and the total improvement is over 14% using robust version learning. Also, the sentence accuracy rate for lexical sequences is improved from 77.12% to 82.38 and 87.88% using the basic and robust version of leaming procedure, respectively.