{'fraction_non_alphanumeric': 0.036770363856216334, 'fraction_numerical': 0.011267450807958667, 'mean_word_length': 4.73432083202017, 'pattern_counts': {'":': 1, '<': 2, '<?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': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generalized Abbreviation Prediction with Negative Full Forms and Its Application on Improving Chinese Web Search

In Chinese abbreviation prediction, prior studies are limited on positive full forms. This lab assumption is problematic in realworld applications, which have a large portion of negative full forms (NFFs). We propose solutions to solve this problem of generalized abbreviation prediction. Experiments show that the proposed unified method outperforms baselines, with the full-match accuracy of 79.4%. Moreover, we apply generalized abbreviation prediction for improving web search quality. Experimental results on web search demonstrate that our method can significantly improve the search results, with the search F-score increasing from 35.9% to 64.9%. To our knowledge, this is the first study on generalized abbreviation prediction and its application on web search.


Introduction
Abbreviations increase the ambiguity in a text. Associating abbreviations with their fully expanded forms is important in various natural language processing applications (Pakhomov, 2002;Yu et al., 2006;HaCohen-Kerner et al., 2008). Chinese abbreviations represent fully expanded forms (e.g., the left side of Figure 1) through the use of shortened forms (e.g., the right side of Figure 1). Chinese abbreviations are derived via a generative lexical process. Although native speakers may possess intuitions of the generative process, it cannot be adequately explained by any linguistic theory (Chang and Lai, 2004;Chang and Teng, 2007).
Abbreviation prediction (i.e., predicting abbreviation of a given full form) is important in Chinese natural language processing applications. For example, it is helpful for information retrieval if we can estimate the abbreviation of a query. For  the data of one month's People's Daily, only 17% of the documents contain the full form in Figure 1, while more than 70% of the articles contain only the abbreviation in Figure 1. It is expected that abbreviation prediction can improve the recall in information retrieval. In addition, (Yang et al., 2009b) in speech studies showed that Chinese abbreviation prediction can improve voice-based search quality. The study of Chinese abbreviation prediction is still in an early stage. Chinese abbreviation prediction is quite different from English ones, because of its specific characteristics (Sun et al., 2008;Huang et al., 1994;Chang and Teng, 2007;Yang et al., 2009b;Yang et al., 2009a). For example, Chinese abbreviations are not necessarily from the initials of words. They frequently take non-initial characters from the words in the full form. In addition, the Chinese full form does not have word boundaries.
To our knowledge, all of the prior studies of Chinese abbreviation prediction (Sun et al., 2008;Sun et al., 2009;Sun et al., 2013;Huang et al., 1994;Chang and Teng, 2007;Yang et al., 2009b;Yang et al., 2009a) have focused on positive full forms with valid abbreviations. This implicit lab assumption is quite limited in real-world applications, because real-world Chinese full forms contain a large portion of negative full forms (NFFs), which have no abbreviation at all. Abbreviation prediction becomes more difficult by considering NFFs, because of the strong noise. This difficulty is one of the reason of the lab setting on considering only positive full forms. Another reason is probably the difficulty of data collection. To our knowledge, there is no existing collection of abbreviation prediction data with NFFs.
We aim at solving this abbreviation prediction problem with generalized assumption (hereinafter generalized abbreviation prediction). We manually collected a large dataset for this study, which contains 10,786 entries including NFFs. To deal with the strong noise from NFFs, we propose a variety of solutions. We also apply generalized abbreviation prediction for web search and we show that it can significantly improve web search quality.
2 Proposed Method

Preprocessing
The preprocessing step includes word segmentation and part-of-speech tagging for the input abbreviation prediction full forms. The word segmentation and part-of-speech tagging is done via the tool ICTCLAS 1 .

Simple Heuristic System
The simple heuristic system means always choosing initial characters of words in the segmented full form. This is because the most natural abbreviating heuristic is to produce the first character of each word in the original full form. This is just the simplest baseline.

Unified System
We present a unified system for generalized abbreviation prediction with NFFs. The unified system can conduct the abbreviation prediction with a single step. We cast abbreviation prediction as a sequential labeling task. Following (Sun et al., 2013), each character in the full form is tagged with a label, y ∈ {P, S}, where the label P produces the current character and the label S skips the current character.
As for NFFs, we need a special encoding of labeling E E E to represent "no valid abbreviation". Since there is no prior work, we need to study this "no valid abbreviation" issue. Given a full form F F F , its valid abbreviation A A A should have the character number constraints: 0 < |A A A| < |F F F |. On the other hand, we can assume that a negative full form has an "invalid abbreviation" A A A with |A A A| = 0 1 http://ictclas.org/ or |A A A| = |F F F |. Those two kinds of interpretations actually represent two different answers to the question "why some full forms do not have valid abbreviations": • Assumption-1 with |A A A| = 0: It assumes that a negative full form F is "abbreviated" to nothing, i.e., with the abbreviation A =NULL.
• Assumption-2 with |A A A| = |F F F |: It assumes that a negative full form F is "abbreviated" to itself, i.e., with the abbreviation A = F .
We want to find out which assumption leads to better performance.
With those interpretations, invalid abbreviations are treated as special forms of abbreviations, thus positive and negative full forms can be modeled in a unified framework via sequential labeling. For simplicity, we use the well-known conditional random fields (CRFs) (Lafferty et al., 2001) for sequential labeling. Assuming a feature function that maps a pair of observation sequence x x x (characters of a full form) and label sequence y y y (label encoding based on abbreviations) to a feature vector f f f , the probability function is defined as follows: where w w w is a parameter vector. Given a training set consisting of n labeled sequences, (x x x i , y y y i ), for i = 1 . . . n, parameter estimation is performed by maximizing the objective function, The second term is a regularizer, typically an L 2 (Gaussian) norm, R(w w w) = ||w w w|| 2 2σ 2 . We use features as follows: • Character feature This feature records the input characters x i−1 , x i and x i+1 .
• Numeral Whether or not the x i is a numeral.
• Organization name suffix Whether or not the x i is a suffix of traditional Chinese organization names.
• Location name suffix Whether or not the x i is a suffix of traditional Chinese location names.
• Word segmentation information After the word segmentation step, whether or not the x i is the beginning character of a word.
• Part-of-speech information The part-of-speech tag information of x i .
i denotes the current position for extracting features.
The character unigram and bi-gram feature is to capture character-based information in the abbreviating process. For example, some special characters are more likely to be chosen in abbreviating. The named entity suffix features are used because a named entity suffix character is more likely to be chosen in abbreviating. The word segmentation information is also important because the beginning character of a word is more likely to be chosen in abbreviating.

Label Encoding with Global Information
As a common practice to reduce complexity, only local information based on Markov assumption is used for sequential labeling. Nevertheless, the Chinese abbreviation generation process is highly dependent on global information. An example of global information is the number of characters of the generated abbreviations.
For better performance, we try to model global information to make the system be "aware" of the number of characters being generated. We use a simple, effective, and tractable solution for modeling global information in abbreviation prediction: label encoding with global information (GI) (Sun et al., 2013).
In this approach, the label y i at position i will be encoded with the global information of its previous labels, y 1 , y 2 , . . . , y i−1 . Note that, while directly increasing the Markov order is untractable, the GI label encoding is tractable. More detailed description of the GI method is in (Sun et al., 2013).

Abbreviation Prediction for Web Search
Abbreviation prediction should be helpful for information search, but we find there is almost no prior work on this. It is probably because the traditional abbreviation prediction is not so applicable in real-world data, which includes lots of NFFs.
Since we have solved this problem via generalized abbreviation prediction, we hope to apply generalized abbreviation prediction on improving information search.
In particular, we apply generalized abbreviation prediction for "query expansion" in Chinese web search. In this method, the original queries are treated as full forms (with NFFs) for generating abbreviations. Given a query as an input, the generalized abbreviation prediction system outputs an abbreviation candidate or a NULL string. If the output is an empty string, it means the query is an NFF. Finally, the derived abbreviations, together with the original query terms, are used for web search, and their search results (web pages) are simply added together. For the negative full forms, only the original full forms are used for the web search. The simple architecture of the query expansion system is summarized in Figure 2.
In addition, to make clear the role of the predicted abbreviations in web search, we can remove the full form information in web search and check the difference. In this way, the method turns to a "query alternation" method, which uses the predicted abbreviation to replace the positive full form for the web search. For a negative full form, the query alternation acts the same like the query expansion.

Experiments
Here we describe our collected data for generalized abbreviation prediction. First, we extract long phrases and terms from Chinese natural language processing corpora, including People's Daily cor- The "X" means no valid abbreviation. pora 2 and SIGHAN word segmentation corpora 3 . Then, we classify the collected phrases and terms into positive and negative full forms. For the negative full forms, no further annotation is required. For the positive full forms, their abbreviations are annotated.
We build a dataset containing 10,786 full forms, including 8,015 positive full forms and 2,771 negative full forms. Samples of the data are shown in Figure 3. The dataset is made up of phrases and terms, including noun phrases, verb phrases, organization names, location names, and so on. The distribution is shown in Table 1. For experiments, we randomly sampled 8,629 samples (80% of the full dataset) for training and 2,157 (20% of the full dataset) for testing.
For experiments on web search, we simply use the 2,157 testing samples as query terms for web search. The evaluation is on the news domain 4 of the well-known web search engine "baidu.com" 5 . The Baidu news search engine has two alternative options: "title search" and "full content search". Since abbreviations are more common in news titles, we adopt the option of title search.

Experimental Settings
For evaluating abbreviation prediction quality, the systems are evaluated using the following two metrics: • All-match accuracy (All-Acc): The number of correct outputs (i.e., label strings) generated by the system divided by the total number of full forms in the test set. 6 • Character accuracy (Char-Acc): The number of correct labels (i.e., a classification on a character) generated by the system divided by the total number of characters in the test set.
For evaluating web search quality based on a given query, the following metrics are used: • Precision P : The number of correct search results returned by the query divided by the total number of search results returned by the query.
• Recall R: The number of correct search results returned by the query divided by the total number of existing correct search results based on the query.

Method
Discriminate Acc (%) Overall  For evaluating web search quality based on a set of queries, we use the macro-averaging and microaveraging of the precision, recall, and F-score based on a single query. Hence, we finally have six metrics: macro-precision, macro-recall, macro-Fscore, micro-precision, micro-recall, and micro-Fscore. We use the novel training method, adaptive online gradient descent based on feature frequency information (ADF) (Sun et al., 2012), for fast and accurate training of the CRF model.
To study the performance of other machine learning models, we also implement on other wellknown sequential labeling models, including maximum entropy Markov models (MEMMs) (Mc-Callum et al., 2000) and averaged perceptrons (Perc) (Collins, 2002).

Results on Abbreviation Prediction
The experimental results are shown in Table 2. In the table, the overall accuracy is most important and it means the final accuracy achieved by the systems in generalized abbreviation prediction with NFFs. For the completeness of experimental information, we also show the discriminate accuracy. The discriminate accuracy checks the accuracy of discriminating positive and negative full forms, without comparing the generated abbreviations with the gold-standard abbreviations.
As we can see from Table 2, first, the best system is the system Unified-Assum.1-GI (CRF). Results demonstrate that incorporating global information can always improve the accuracy for the unified methods. Second, the unified system with assumption-1 has better accuracy than the one with assumption-2. This result suggests that assumption-1 works better in practice. It is interesting that assumption-1 is more useful. A probable reason is that those negative full forms have no similar patterns with the real abbreviations. For example, the number of characters in NFFs is very different compared with that of real abbreviations. Also, the NFFs contain more formal word units. Real abbreviations contain much less word units. Thus, assumption-2 will have the inconsistency problem between abbreviations generated from NFFs and real abbreviations. As a result, assumption-2 works worse than assumption-1 which gives no abbreviations. Finally, the CRF model outperforms the MEMM and averaged perceptron models. To summarize, the unified system with assumption-1, global information, and CRF model has the best performance.

Results on Web Search
We use the 2,157 testing samples as query terms for web search. We test the original query terms, the query alternation, and the query expansion methods. Some search results actually do not match the query. For example, given a query abc, some search results do not contain abc, but with the expression "ab . . . c" or "a . . . bc", where ". . . " means other characters. In this case, the search results are incorrect. Since the number of the search results is massive, we need to evaluate the web   search quality in an efficient way. The correctness of the search results is evaluated by an automatic postprocessing scoring system, which crawls the search results from the baidu.com site. Then, the system runs text matching analysis to check if the search query matches the retrieved web pages.
In traditional web search studies, many queries are phrases (e.g., NP+VP) with ambiguous senses. In this case, improving search precision via contextual information is important. However, for abbreviation processing, most abbreviations are from named entities (the data contains phrases but most of them are NFFs), and the major problem of named entities is variational expressions. In this case, the search recall is more important. To calculate the recall rate in web search, we need to estimate the total number of correct web pages N relating to a query Q and its abbreviation A. We can estimate N via summing up the correct web pages of Q and the correct web pages of the goldstandard abbreviation A.
The precision, recall, F-scores are shown in Table 3. As we can see, the query expansion method based on generalized abbreviation prediction achieves significantly better F-scores on web search quality than using the original queries. We find the major improvement is from the recalls. As expected, the query alternation has lower recall rate than the query expansion method, because the full form information is removed. Nevertheless, the query alternation method is also better than using the original queries. This result emphasizes that the abbreviations are helpful in titlebased news search.
Finally, we check the "up-bound" of the performance of generalized abbreviation prediction for web search. The up-bound is achieved by the 100% correct "gold-standard" system, in which gold-standard abbreviations labeled in the data are used. The results are shown in Table 4. As we can see, the up-bound of the micro-F-score and the macro-F-score is 79.81% and 81.04%, respectively. Thus, the web search quality of automatic generalized abbreviation prediction still has a large space to be improved, possibly via a larger training data set in the future.

Conclusions and Future Work
This paper is dedicated on generalized abbreviation prediction and its application on improving web search. Experiments demonstrate that the unified system based on global information outperforms the baselines. Experiments also demonstrate that generalized abbreviation prediction can improve web search qualities. As future work, we try to improve the performance via collecting more training data or via semi-supervised learning methods.