{'fraction_non_alphanumeric': 0.03970857859693139, 'fraction_numerical': 0.014860561613432403, 'mean_word_length': 4.543460818400642, '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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Japanese Zero Pronoun Resolution based on Ranking Rules and Machine Learning

Anaphora resolution is one of the most important research topics in Natural Language Processing. In English, overt pronouns such as she and definite noun phrases such as the company are anaphors that refer to preceding entities (antecedents). In Japanese, anaphors are often omitted, and these omissions are called zero pronouns. There are two major approaches to zero pronoun resolution: the heuristic approach and the machine learning approach. Since we have to take various factors into consideration, it is difficult to find a good combination of heuristic rules. Therefore, the machine learning approach is attractive, but it requires a large amount of training data. In this paper, we propose a method that combines ranking rules and machine learning. The ranking rules are simple and effective, while machine learning can take more factors into account. From the results of our experiments, this combination gives better performance than either of the two previous approaches.


Introduction
Anaphora resolution is an important research topic in Natural Language Processing. For instance, machine translation systems should identify antecedents of anaphors (such as he or she) in the source language to achieve better translation quality in the target language.
We are now studying open-domain question answering systems 1 , and we expect QA systems to benefit from anaphora resolution. Typical QA systems try to answer a user's question by finding relevant phrases from large corpora. When a correct answer phrase is far from the keywords given in the question, the systems will not succeed in finding the answer. If the system can correctly resolve anaphors, it will find keywords or answers represented by anaphors, and the chances of finding the answer will increase. From this motivation, we are developing our system toward the ability to resolve anaphors in full-text newspaper articles.
In Japanese, anaphors are often omitted and these omissions are called zero pronouns. Since they do not give any hints (e.g., number or gender) about antecedents, automatic zero pronoun resolution is difficult. In this paper, we focus on resolving the zero pronoun, which is shortened for simplicity to 'zero. ' Most studies on Japanese zero pronoun resolution have not tried to resolve zeros in full-text newspaper articles. They have discussed simple sentenses (Kameyama, 1986;Walker et al., 1994;Yamura-Takei et al., 2002), dialogues (Yamamoto et al., 1997), stereotypical lead sentences of newspaper articles (Nakaiwa and Ikehara, 1993), intrasentential resolution (Nakaiwa and Ikehara, 1996;Ehara and Kim, 1996) or organization names in newspaper articles (Aone and Bennett, 1995).
There are two approaches to the problem: the heuristic approach and the machine learning ap-proach. The Centering Theory (Grosz et al., 1995) is important in the heuristic approach. Walker et al. (1994) proposed forward center ranking for Japanese. Kameyama (1986) emphasized the importance of a property-sharing constraint. Okumura and Tamura (1996) experimented on the roles of conjunctive postpositions in complex sentences.
However, these improvements are not sufficient for resolving zeros accurately. Murata and Nagao (1997) proposed complicated heuristic rules that take various features of antecedents and anaphors into account. We have to take even more factors into account, but it is difficult to maintain such heuristic rules. Therefore, recent studies employ machine learning approaches. However, it is also difficult to prepare a sufficient number of annotated corpora.
In this paper, we propose a method that combines these two approaches. Heuristic ranking rules give a general preference, while a machine learning method excludes inappropriate antecedent candidates. From the results of our experiments, the proposed method shows better performance than either of the two approaches alone.
Before giving a description of our methodology, we briefly introduce the grammar of the Japanese language here. A Japanese sentence is a sequence of bunsetsus: A bunsetsu is a sequence of content words (e.g., nouns, adjectives, and verbs) followed by zero or more functional words (e.g., particles and auxiliary verbs): A bunsetsu modifies one of the following bunsetsus. A particle (joshi) marks the grammatical case of the noun phrase immediately before it. For example, ga is nominative (subject), wo is accusative (object), ni is dative (object2), and wa marks a topic.
indicates that there are four bunsetsus in this sentence and that the first bunsetsu modifies the fourth bunsetsu and so on. The last bunsetsu modifies no bunsetsu, which is indicated by 3 # . It takes a long time to construct high-quality annotated data, and we want to compare our results with conventional methods. Therefore, we obtained Seki's data (Seki et al., 2002a;Seki et al., 2002b), which are based on the Kyoto University Corpus 2 2.0. These data are divided into two groups: general and editorial. General contains 30 general news articles, and editorial contains 30 editorial articles. According to his experiments, editorial is harder than general. Perhaps this is caused by the difference in rhetorical styles and the lengths of articles. The average number of sentences in an editorial article is 28.7, while that in a general article is 13.9.
However, we found problems in his data. For instance, the data contained ambiguous antecedents like dou-shi (the same person) or dou-sha (the same company) as correct antecedents. We replaced these 'correct answers' with their explicit names. We also removed zeros in quoted sentences because they are quite different from other sentences.
In addition, we decided to use the output of ChaSen 2.2.9 3 and CaboCha 0.34 4 instead of the morphological information and the dependency information provided by the Kyoto Corpus since classification of the joshi (particles) in the Corpus was not satisfactory for our purpose. Since CaboCha was trained by Kyoto Corpus 3.0, CaboCha's dependency output is very similar to that of the Corpus.

Methodology
In this paper, we combine heuristic ranking rules and machine learning. First, we describe how we extract possible antecedents (candidates). Second, we describe the rule-based ranking system and the machine learning system. Finally, we describe how to combine these two methods.
We consider only anaphors for noun phrases following Seki and other studies. We assume that zeros are already detected. We also assume zeros are located at the starting point of a bunsetsu that contains a yougen (a verb, an adjective, or an auxiliary verb). From now on, we use 'verb' instead of 'yougen' for readability. A zero's bunsetsu is a bunsetsu that contains the zero. We further assume that each zero's grammatical case is already determined by a zero detector and represented by corresponding particles.
If a zero is the subject of a verb, its case is represented by the particle ga. If it is an object, it is represented by wo. If it is an object2, it is represented by ni. We consider only these three cases. A zero's particle means such a particle.
Since complex sentences are hard to analyze, each sentence is automatically split at conjunctive postpositions (setsuzoku joshi) (Okumura and Tamura, 1996;Ehara and Kim, 1996). In order to distinguish the original complex sentence and the simpler sentences after the split, we call the former just a 'sentence' and the latter 'post-split sentences'. When a conjunctive postposition appears in a relative clause, we do not split the sentence at that position. In the examples below, we split the first sentence at 'and' but do not split the second sentence at 'and'.
She bought the book and sold it to him. She bought the book that he wrote and sold.
A zero's sentence is the (original) sentence that contains the zero. From now on, 6 stands for a zero and 7 stands for a candidate of 6 's antecedent. 6 's particle is denoted ZP, and CP stands for 7 's next word that is 7 's particle or a punctuation symbol.

Enumeration of possible antecedents
Candidates (possible antecedents) are enumerated on the fly by using the following method.
1. We extract a content word sequence ¡ 8 £ § ¥ ¦ ¥ § ¥ £ as a candidate 7 if it is followed by a case marker (kaku-joshi, e.g., ga, wo), a topic marker (wa or mo), or a period.
4. If 7 is dou-shi (the person), it is replaced by the latest person name. If 7 is dou-sha (the company), it is replaced by the latest organization name. If 7 is dou+suffix, it is replaced by the latest candidate that has the same suffix.
For this task, we use a named entity recognizer (Isozaki and Kazawa, 2002).
The first step extracts a content word sequence from a bunsetsu. The second step excludes verb phrases, adjective phrases, and clauses. As a result, we obtain only noun phrases. The third step excludes adverbial expressions like kotoshi (this year). The forth step resolves anaphors like definite noun phrases in English. We should also resolve pronouns, but we did not because useful pronouns are rare in newspaper articles.
In addition, we register a resolved zero as a new candidate.
In the training phase of the machine learning approach, we consider a correct answer as 7 A . Then, we can remove far candidates from the list.
In this way, our zero resolver creates a 'general purpose' candidate list. However, some of the candidates are inappropriate for certain zeros. A verb usually does not have the same entity in two or more cases (Murata and Nagao, 1997). Therefore, our resolver excludes candidates that are filled in other cases of the verb. When a verb has two or more zeros, we resolve ga first, and its best candidate is excluded from the candidates of wo or ni.

Ranking rules
Various heuristics have been reported in past literature. Here, we use the following heuristics.
1. Forward center ranking (Walker et al., 1994): 2. Property-sharing (Kameyama, 1986): If a zero is the subject of a verb, its antecedent is perhaps a subject in the antecedent's sentence. If a zero is an object, its antecedent is perhaps an object.
3. Semantic constraints (Yamura-Takei et al., 2002;Yoshino, 2001): If a zero is the subject of 'eat,' its antecedent is probably a person or an animal, and so on. We use Nihongo Goi Taikei (Ikehara et al., 1997), which has 14,730 English-to-Japanese translation patterns for 6,103 verbs, to check the acceptability of a candidate. Goi Taikei also has 300,000 words in about 3,000 semantic categories. (See Appendix A for details.) 4. Demotion of candidates in a relative clause (rentai shuushoku setsu): Usually, Japanese zeros do not refer to noun phrases in relative clauses (Ehara and Kim, 1996). (See Appendix B for details.) Since sentences in newspaper articles are often complex and relative clauses are sometimes nested, we refine this rule in the following way.

E
A candidate's relative clause is the inmost relative clause that contains the candidate.

E
A relative clause finishes at the noun modified by the clause.
E If 6 appears before the finishing noun of 7 's relative clause, the clause is still unfinished at 6 . Otherwise, the clause is already finished.

E
A quoted clause (with or without quotation marks " ") indicated by a quotation marker 'to' ('that' in 'He said that she is . . . ') is also regarded as a relative clause.
E We demote 7 after 7 's relative clause finishes.
It is not clear how to combine the above heuristics consistently. Here, we sort the candidates in a lexicographical order based on the above features of candidates. For instance, we can use a lexicographically increasing order defined by Otherwise, Sa is 4. We did not implement empathy because it makes the program more complex, and empathy verbs are rare in newspaper articles.
For instance, The first ranked (lexicographically smallest) candidate is regarded as the best candidate. We employ lexicographical ordering because it seems the simplest way to rank candidates. We put Vi in the first place because Vi was often regarded as a constraint in the past literature. We put Ag before Sa because Kameyama's method was better than Walker's in Okumura and Tamura (1996). Therefore, to be a good ordering. The above ordering is an instance of this.

Machine Learning
Although we can consider various other features for zero pronoun resolution, it is difficult to combine these features consistently. Therefore, we use machine learning. Support Vector Machines (SVMs) have shown good performance in various tasks in Natural Language Processing (Kudo and Matsumoto, 2001;Isozaki and Kazawa, 2002;Hirao et al., 2002). Yoshino (2001) and Iida et al.(2003b) also applied SVM to Japanese zero pronoun resolution, but the usefulness of each feature was not clear. Here, we add features for complex sentences and analyze useful features by examining the weights of features. We use the following features of 7 as well as CP.

CPPOS CP's part-of-speech (POS) tags (rough and detailed).
CPOS The POS tags of the last word of 7 .
Siblings When CP is wa or mo, it is not clear whether 7 is a subject. However, a verb rarely has the same entity in two or more cases. Therefore, if 7 modifies a verb that has a subject, 7 is not a subject. In the next example, hon is an object of katta. In order to learn such things, we use sibling casemarkers that modify the same verb as 7 's features. We also use the following features of 6 as well as ZP.
Conjunct The latest conjunctive postposition in the sentence and its classification (Okumura and Tamura, 1996;Yoshimoto, 1986).
ZSem Semantic categories of the verb that 6 modifies. We use them only when the verb is sahen meishi + 'suru.' Sahen meishi is a kind of noun that can be an object of the verb 'suru' (do) (e.g., 'shopping' in 'do the shopping').
We also use the following relations between 6 and 7 as well as Ag, Vi, and Di.

Relative
Whether 7 is in a relative clause.
Unfinished Whether the relative clause is unfinished at 6 .
Intra (for intrasentential coreference) Whether 7 explicitly appears in 6 's sentence. Sometimes it is difficult to distinguish cataphora from anaphora. Even if an antecedent appears in a preceding sentence, it is sometimes easier to find a candidate after 6 , as illustrated by the case of 'his' in the next English example.
Bob and John separately drove to Charlie's house. . . . Since his car broke down, John made a phone call. Even if Di F holds, Intra does not necessarily hold because we introduce resolved zeros as new candidaites.
Parallel Whether 7 appears in a clause parallel to a clause in which a zero appears. This will be useful for the resolution of a zero as with 'it' in the next English sentence.
He turned on the TV set and she turned it off. Immediate Whether 7 's bunsetsu appears immediately before 6 's. In the following sentence, a candidate ryoushin is located immediately before the zero.
Kare no he+'s / ryoushin wa parents=topic / (6 ga) (Q =subj) ikiteiru to alive+that / shinjiteiru. believe (His parents believe that (6 ) is still alive.) Here, we represent all of the above features by a boolean value: 0 or 1. Semantic categories can be represented by a 0/1 vector whose R -th component corresponds to the R -th semantic category. Similarly, POS tags can be represented by a 0/1 vector whose R -th component corresponds to the R -th POS tag. On the other hand, Di has a non-negative integer value. We also encode the distance by a 0/1 vector whose R -th component corresponds to the fact that the distance is R . The distance has an upper bound maxDi. In this way, we can represent a candidate by a boolean feature vector. A candidate 7 S ' s feature vector is denoted T U S . If a boolean feature appears only once in the given data, we remove the feature from the feature vectors.
The training data comprise the set of pairs By using the training data, SVM finds a decision function T is classified as a correct antecedent.

Combinations
Here, we use the following method to combine the ordering and SVM.
1. Sort candidates by using the lexicographical order.
2. Classify each candidate by using SVM in this order.

Results
We conducted leave-one(-article)-out experiments.
For each article, 29 other articles were used for training. Table 1 compares the scores of the above methods. 'First' picks up the first candidate given by a given lexicographical ordering. The acronym 'vrads' stands for the lexicographical ordering of Best' picks up the best candidate in terms of X ! T & without checking whether it  nik, 1995) while 'svm2' uses a modified SVM for unbalanced data (Morik et al., 1999), which gives a large penalty to misclassification of a minority (= positive) example. 5 In general, svm2 accepts more cadidates than svm1. According to this table, svm1 is too severe to exclude only bad candidates. We also tried the maximum entropy model 6 (mem) and C4.5, but they were also too severe. When we use SVM, we have to choose a good kernel for better performance. Here, we used the linear kernel (a ! T £ 8 c e & i T g c ) for SVM because it was best according to our preliminary experiments. We set maxDi at 3 because it gave the best results.
The table also shows Seki's scores for reference, but it is not fair to compare our scores with Seki's scores directly because our data is slightly different from Seki's. The number of zeros in general in our data is 347, while Seki resolved 355 detected zeros in (Seki et al., 2002a) and 404 in (Seki et al., 2002b). The number of zeros in our editorial is 514, while (Seki et al., 2002a)  Seki used unannotated articles to get co-occurrence statistics. Without the data, their scores degraded about 5 points. We have not conducted experiments that use unannotated corpora; this task is our future work.
As we expected, instances of is the best for general in the table. It is interesting that such a simple ordering gives better performance than SVMs. However, the combination of 'vrads' and 'svm2' (= vrads+svm2) gives even better results. In general, 'e +svm2' is better than 'first' and 'e +svm1.' With SVM, 'davrs+svm2' gave the best result for editorial. Editorial articles sometimes use anthropomorphism (e.g., The report says . . . ) that violates semantic constraints. Therefore, 'vrads' does not work well for such cases.  (Vi), candidate's particle (CP), and distance (Di) are very important features. Our new features Parallel, Unfinished, and Intra also obtained relatively large weights. Semantic categories 'suggestions' and 'report' reflect the fact that some articles use anthropomorphism. These weights will be useful to design better heuristic rules. The fact that Unfinished's weight almost cancels Relative's weight justifies the  Yoshino (2001) used an ordinary SVM with

Discussion
. He tried to find useful features by feature elimination. Since features are not completely independent, removing a heavily weighted feature does not necessarily degrade the system's performance. Hence, feature elimination is more reliable for reducing the number of features. However, feature elimination takes a long time. On the other hand, feature weights can give rough guidance. According to the table, our new features (Parallel, Unfinished, and Intra) obtained relatively large weights. This implies their importance. When we eliminated these three features, vrads+svm2's score for editorial dropped by 4 points. Therefore, combinations of these three features are useful.
Recently, Iida et al. (2003a) proposed an SVMbased tournament model that compares two candidates and selects the better one. We would like to compare or combine their method with our method. For further improvement, we have to make the morphological analyzer and the dependency analyzer more reliable because they make many mistakes when they process complex sentences. SVM has often been criticized as being too slow. However, the above data were small enough for the state-of-the-art SVM programs. The number of examples in each set of training data was about 5,000-6,100, and each training phase took only 5-18 seconds on a 2.4-GHz Pentium 4 machine.

Conclusions
In order to make Japanese zero pronoun resolution more reliable, we have to maintain complicated heuristic rules or prepare a large amount of training data. In order to alleviate this problem, we combined simple lexicographical orderings and SVMs. It turned out that a simple lexicographical ordering performed better than SVM, but their combination gave even better performance. By examining feature weights, we found that features for complex sentences are important in zero pronoun resolution. We confirmed this by feature elimination.