{'fraction_non_alphanumeric': 0.03098887720657407, 'fraction_numerical': 0.007027834652205191, 'mean_word_length': 4.724421919543871, '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}}
Applying Maximum Entropy to Robust Chinese Shallow Parsing

Recently, shallow parsing has been applied to various information processing systems, such as information retrieval, information extraction, question answering, and automatic document summarization. A shallow parser is suitable for online applications, because it is much more efficient and less demanding than a full parser. In this research, we formulate shallow parsing as a sequential tagging problem and use a supervised machine learning technique, Maximum Entropy (ME), to build a Chinese shallow parser. The major features of the ME-based shallow parser are POSs and the context words in a sentence. We adopt the shallow parsing results of Sinica Treebank as our standard, and select 30,000 and 10,000 sentences from Sinica Treebank as the training set and test set respectively. We then test the robustness of the shallow parser with noisy data. The experiment results show that the proposed shallow parser is quite robust for sentences with unknown proper nouns.


Introduction
Parsing is a basic technique in natural language processing; however, a full parser is usually costly and slow. Recently, shallow parsing has been applied to various information processing systems [12]. Compared to the performance of full parsers, a shallow parser is much faster and the parsing result is more useful for various applications, such as information retrieval and extraction, question answering, and automatic document summarization. In this paper, we adopt a machine learning approach to the Chinese shallow parsing problem.
Chinese full parsing is very challenging, [18,22] because it is difficult to achieve high accuracy, and the performance is not suitable for online applications. Shallow parsing of Chinese, on the other hand, is promising and desirable in terms of efficiency. Researchers in Beijing, Harbin, Shenyang, and Hong Kong have also developed related techniques [10,15,16,20,21]. Most of these works use machine learning approaches, instead of the rule-based approach used in full parsing. Popular machine learning methods such as SVM, CRF, and ME, have been tested. The parsing speed of each approach is fast and the parsing accuracy is acceptable.
Currently, there is no standard for Chinese shallow parsing. Li et. al. [9] developed a Chinese shallow parsed treebank to extract Chinese collocations automatically and built a large collocation bank.
There are also some works on a standard for Chinese shallow parsing [9,19,20]. Nevertheless, the POS standard and vocabulary in each approach are different; thus, between simplified Chinese and traditional Chinese, we cannot adopt their standard for simplified Chinese to traditional Chinese.
Instead, we use the first level of the parsing results of Sinica Treebank as our shallow parsing standard [4]. Originally, Sinica Treebank was designed to provide full parsing results, whereby sentences could be labeled with POS tags and the full parsing structure. There are 54,000 sentences in Sinica Treebank, from which we randomly selected 30,000 and 10,000 sentences as the training set and test set respectively.
In this research, we simulate unknown words by adding some noises to the corpus in order to test the robustness of the shallow parser. Since new proper nouns are normally unknown, we design three ways to add noises to the training and testing sets by treating proper nouns as unknown words.

Shallow Parsing Standard
Sinica Treebank provides a full parse tree for each sentence. Here, we use the first-layer parsing results of Sinica Treebank as the standard for shallow parsing. Instead of using all the phrase tags in Sinica Treebank, we annotate five of them for chunking; all other phrases (including single words not in any phrase) are tagged as others (X). The five tags, namely, noun phrase (NP), verb phrase (VP), preposition phrase (PP), geographic phrase (GP), and clause (S), are the major tags in Sinica Treebank, and therefore play significant syntactical roles. Thus, the constituents of the root node of a parse tree are NP, VP, PP, GP, S, and X. Table 1 lists examples of the six types of constituent.

A Maximum Entropy-based Shallow Parser
Parsing is a fundamental technique in natural language processing, the results of which can be used to improve various natural language tasks, such as word-sense disambiguation (WSD) [3] and part-of-speech (POS) tagging [12].
Many natural language processing tasks, such as part-of-speech tagging, named-entity recognition, and shallow parsing, can be viewed as sequence analysis tasks. Shallow parsing identifies the non-recursive core of each phrase type in a text as a precursor to full parsing or information extraction [1, 6]. The paradigmatic shallow parsing problem is called NP chunking, which finds the non-recursive cores of noun phrases called base NPs. Ramshaw and Marcus introduced NP chunking as a machine-learning problem [14].
Machine learning techniques, such as maximum entropy (ME) and conditional random fields (CRF), are quite popular for sequential tagging. We adopt ME to build a robust Chinese shallow parser.

The B-I-O Scheme of Our Shallow Parser
In this work, we regard each word as a token, and consider a test corpus and a set of n phrase categories. Since a phrase can have more than one token, we associate two tags, x: x_begin and x_continue, with each category. In addition, we use the tag others to indicate that a token is not part of a phrase. The shallow parsing problem can then be redefined as a problem of assigning one of 2n + 1 tags to each token. This is called the B-I-O scheme. There are 5 named entity categories and 11 tags: NP_begin, NP_continue, VP_begin, VP_continue, PP_begin, PP_continue, GP_begin, GP_continue, S_begin, S_continue, and X(others).

Maximum Entropy Formula
ME is a flexible statistical model that assigns an outcome to each token based on its history and features [2]. The outcome space is comprised of the tags for an ME formulation. ME computes the probability p(o|h) for any o from the space of all possible outcomes, O, and for every h from the space of all possible histories, H. A history is composed of all the conditioning data that enables one to assign probabilities to the space of outcomes. In shallow parsing, history can be viewed as all the information derived from the test corpus relevant to the current token.
The computation of p(o|h) in ME depends on a set of binary-valued features, which is helpful in making a prediction about the outcome. For instance, one of our features is as follows: when the current token is a verb, it is likely to be the leading character of a verb phrase. More formally, we can represent this feature as Here, Current-token-verb(h) is a binary function that returns the value true if the current token of the history h is a verb.
Given a set of features and a training corpus, the ME estimation process produces a model in which every feature f i has a weight α i . This allows us to compute the conditional probability as follows: where Z(h) is a normalization factor. Intuitively, the probability is the multiplication of the weights of active features (i.e., those f i (h,o) = 1). The weight α i is estimated by means of a procedure called Generalized Iterative Scaling (GIS) [8], which improves the estimation of the weights at each iteration.
The ME estimation technique guarantees that, for every feature f i , the expected value of α i will be equal to the empirical expectation of α i in the training corpus. ME allows the designer to concentrate on finding the features that characterize the problem, while letting the ME estimation routine deal with assigning relative weights to the features.

Decoding
After an ME model has been trained and the proper weight α i has been assigned to each feature

Experiment
By comparing models with and without noisy training data, we can determine whether our Chinese shallow parser is noisy-data-tolerant. In this section, we describe how we add noisy data to maximum entropy models and evaluate the tolerance of our system to Chinese chunking.

Data and Features
Sinica Treebank contains more than 54,000 sentences, from which we randomly extract 30,000 for training and 10,000 for testing. The tokenized results and the corresponding part-of-speech sequences of these sentences are extracted into a feature file, and the top-level chunks of the parsing tree structure can be taken as the standard for training and evaluation. The information in the feature file is translated into machine learning features by ME model in both the training and testing phrases.
The features we adopted are: words, adjacent characters, prefixes of words (1 and 2 characters), suffixes of words (1 and 2 characters), word length, POS of words, adjacent POS tags, and the word's location in the chunk it belongs to.
To analyze the performance of our shallow parser under noisy conditions, we build a standard model and various noisy models. Training data consisting of the tokenization and POS information derived from the manually annotated Sinica Treebank is used as the standard model in our experiments.
The accuracy of chunking in this model is then compared with that of models containing noise to observe the difference.

Noise Model Generation
The most important issue in noisy model generation is how to mix noisy features with correct features as smoothly as in a real parsing system. We design three methods for adding noise to generate different types of models with noisy tokenization and POS sequences.
The first two approaches are based on unknown word replacement. We find that unknown words are one of the major causes of noisy data in real world system processing, because most unknown words are proper nouns. Theoretically, we can pick a certain number of proper nouns in the selected data and substitute them with noisy data to simulate real world input. In our experiment, "Nb" and "Nc", which are defined as "proper nouns" and "proper location nouns" respectively in the Sinica Treebank tagging guideline [5], are chosen as replacement targets. Words with these two target POS are regarded as replacement target strings and replaced by noisy data.
We adopt two types of noisy data for unknown word replacement. The first is the split character sequence of a replacement target string in a sentence. Initially, we extract the correct tokenization results and POS sequences of all data in the Sinica Treebank with "Nb" and "Nc". Then, wherever applicable, we split the replacement target string in a sentence into single Chinese characters. The corresponding POS tag of each split character is re-assigned by selecting the most frequent POS tags of these single characters in Sinica Treebank. For example, "馬來西亞" (Malaysia) would be split into "馬", "來", "西", and "亞", and the original POS tag "Nca" would be replaced by the pos tags of four single characters: "Nab", "Dbab", "Ncda", and "Nca". In this experiment, we control the amount of noisy data in models to observe the relation between the percentage of imprecise data and the chunking performance. The model generated by this approach is called a Type 1 noise model. Another approach, called the Type 2 noise model, tokenizes the replacement target with AUTOTAG, which may produce segmenting boundaries and POS tags that differ from those in Sinica Treebank. The information is then used as noisy features and replaces the target string. For instance, the replacement target string "太白金 星" with POS tag "Nb" would be tagged by AUTOTAG as "太白/Nb" and "金星/Nb". The above noise-adding approaches are used to generate training data, as well as various kinds of noisy information in the test sets.
In addition, we adopt an automatic tool, CKIP AUTOTAG [7], to obtain the tokenization information and POS features for generating models. This is a Chinese tokenizing tool that can deal with word segmentation in both the training and testing sets. CKIP AUTOTAG provides the POS sequences of the sentences. The tokenized sentences and POS sequences produced by AUTOTAG are used to generate feature files for ME processing.

Results and Discussion
In our experiment, we adopt the B-I-O scheme to identify the boundaries of Chinese chunks and the position of each element word in the chunks. In addition, we employ the following four standards when calculating the accuracy of Chinese shallow parsing: evaluation by token, by chunk boundary, by chunk category sequence, and by chunks. Token evaluation is based on the number of Chinese words.
All words in the test data can be verified independently to determine if they have the correct boundaries and belong to the right chunks. Evaluation by chunk boundary only checks the boundaries of each chunk, while evaluation by chunk category sequence only checks if all the chunks in a sentence can be identified successfully and disregards the constituents. By contrast, in chunk evaluation, the basic unit is the whole chunk, and only a chunk with the right constituents and tagged with proper categories can be considered correct. We use an example to demonstrate the evaluation process. The input sentence is "小朋友 換成 你 來 試試看", which consists of five tokens; and the standard parsing result is "小朋 友/NP 換成/VC 你/NP 來-試試看/VP", which contains four chunks. The parsing result we obtain from the system is "小朋友/NP 換成/VC 你/NP 來/Db 試試看/VE", which contains five chunks. In this case, the accuracy of the chunk boundary and the chunk category are both 3/4=0.75, because the first three chunks in the sentence have the correct boundaries and phrase tags, and the last VP chunk is separated by two units. The token number in this sentence is 5 and the last two tokens have incorrect phrase category tags. Therefore, the accuracy of the token is 3/5=0.6. In chunk evaluation, three of the four chunks are identified successfully and the chunk accuracy is 3/4=0.75. We adopt these evaluation methods in all the experiment configurations in Tables 2 to 5. Table 2 shows the accuracy rates using Type 1 noisy models with different scales of noisy data for chunking clean test data. The columns show the percentage of 'Nb' and 'Nc' replaced by single character noisy data in the training model, and the rows indicate the four evaluation methods. We find that the accuracy in this series decreases slightly, while the percentage of single character noisy data increases.  Table 3 shows the accuracy rates using the Type 1 model with different scales of noisy data for chunking test data with single character noise (Type 1). It is quite interesting that the curve is not monotonically increasing or decreasing. This indicates that the accuracy in this series decreases until the percentage of noise reaches 60%, and then it increases. Figures 1 to 4 show the differences between the clean test data and the noisy test data in Tables 2 and 3. We can observe the trends in the experiment results more intuitively.       Table 5 shows the accuracy rates using the model generated by AUTOTAG-parsed data and Sinica Treebank chunking tags. Both the training and the test sets are preprocessed by AUTOTAG. This experiment is designed for open testing; thus, we can use the AUTOTAG program to tokenize any sentence and give it POS tags. However, compared to the standard model, the chunking accuracy is lower. The parsing results of the AUTOTAG-parsed model and the Type 2 noise models are shown in Figure 5.     Table 8 shows the parsing results using AUTOTAG-parsed training data and test data. The results of the first and last sentences are correct, while those of the second and the third sentences are incorrect.

Performance on Noisy Data
We replace the original word segmentation and POS tags of all the sentences with AUTOTAG-parsed word segmentation and POS tags. The word segmentation of the last sentence provided by AUTOTAG is incorrect; however, the chunking result is correct.

Use of Our Shallow Parser on News Articles
For the first application of our shallow parser, we collect some news articles as the test set. The articles did not have standard word segmentation, POS tagging, and parsing results; therefore, we cannot report on the accuracy. However, we find the results interesting. Some examples are given in Table 9. The left column shows the original sentences tokenized and tagged with POS tags by AUTOTAG. The right column shows the shallow parsing results using our system.
One interesting point is that the shallow parser tends to group named entities into a phrase.
Therefore, the shallow parsing result can be used as a feature for boundary detection in named entity recognition (NER). In sentence 1, "中鋼公司" is grouped as one phrase, and in sentence 9, "中鋼公司 88 年盈餘" is grouped as one phrase, without first recognizing that "中鋼公司" is an entity by NER.
Another example, in sentence 2 is that "益華在花蓮的三棟大樓" is grouped as one phrase, without first recognizing that "益華" is a company name.

Conclusion and Future Works
In this paper, we propose a Chinese shallow parser that can chunk Chinese sentences into five chunk types. We test the noise tolerance of the shallow parser and found that the accuracy of data with simulated unknown words only decreases slightly in chunk parsing. We also test our Chinese shallow parser on an open corpus, and found that it yields interesting chunking results.
Tolerance of unknown words is an essential characteristic of a Chinese shallow parser. In this paper, we demonstrate our parser's robustness in handling noisy data from proper nouns. However, we could not verify the robustness of chunking noisy data from other kinds of POS. Thus, adopting other POS systems, such as the Penn Chinese Treebank tagset, for Chinese shallow parsing could prove both interesting and useful. In the future, we will improve our model by adding more types of noise, such as random noise, filled noise, and repeated noise proposed by Osborne [13]. In addition to Sinica Treebank, we will extend our training corpus by incorporating other corpora, such as Penn's Chinese Treebank.