JP3035261B2 - Japanese parser - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Japanese syntax for automatically assigning a syntax structure to text data of a Japanese sentence including a character string by using a decision tree with a probability for determining a syntax structure. It relates to an analyzer.

[0002]

2. Description of the Related Art Conventionally, a relatively accurate part-of-speech assigning system (hereinafter referred to as a first conventional example) is disclosed in Prior Art Document 1.
“E. Brill et al.,“ Some Advances in Transformation
--Based Part of Speech Tagging ", Proceedings of the
Twelfth National Conferenceon Artificial Intellig
ence, pp.722-727, AAAI, 1994 "and prior art document 2
“B. Merialdo et al.,“ Tagging English Text with a
Probabilistic Model ", Computational Linguistics, 20-
2, pp. 155-171, 1994 ". In this part-of-speech giving system of this conventional example, part-of-speech is given to text data by referring to a dictionary for giving part-of-speech, which describes a set of a word notation and a part-of-speech label taken by the notation.

In the part-of-speech assigning system of the first conventional example, part-of-speech is assigned using a dictionary. Therefore, it is difficult to assign a part-of-speech to an unknown word not described in a dictionary item. There is a problem that processing for an unknown combination with is difficult. Furthermore, there is a problem that it is necessary to maintain the dictionary by changing the part of speech system used. There is also a part-of-speech device that uses heuristics (heuristically or empirically) to assign a part-of-speech label to a word without using a dictionary. However, there is a problem that the accuracy rate of part-of-speech assignment is relatively low.

[0004] In order to solve the above problems, the present applicant has compared the first conventional example without using a dictionary for assigning the part of speech in the patent application of Japanese Patent Application No. Hei 8-232993. A part-of-speech assigning device (hereinafter, referred to as a second conventional example) that can be assigned automatically and accurately. The second conventional example of the part-of-speech providing apparatus includes: (a) a spelling feature of each word, a feature based on how to be used in a sentence,
Using a plurality of attributes including hierarchical classification using mutual information of words, and having a tree structure in a binary tree format that is divided depending on the attribute value of each attribute, Tree that generates a decision tree with frequency probabilities by calculating and assigning frequency probabilities for a plurality of parts of speech to a leaf node that is an undivided node of the generated decision tree. Means, and (b) using the decision tree with frequency probability generated by the decision tree learning means, based on the text data composed of the input word strings, the top among the frequency probabilities assigned to the leaf nodes. A product in which a plurality of n frequency probabilities are selected and given to each word of the text data, and a part of speech having the maximum connection probability in the word string of the text data is determined and output as a correct part of speech. It is characterized in that a supplying means.

[0005] Further, as an English parsing apparatus, a conventional technique 3 "MJ Collins," A new statistical parser b
ased on bigram lexical dependencies ", the 34th Annu
al Meeting of ACL Proceedings, 1996 ”, learn the bigram statistical information of the main words from the text data with the syntactic structure, and perform parsing.
This is referred to as a third conventional example. ) Is disclosed. However, in the third conventional example, there is a problem that information of a detailed syntax structure such as a context-free grammar with a feature structure cannot be added.

[0006] In order to solve the above problems, the present applicant has compared the patent application of Japanese Patent Application No. 9-218522 with the third conventional example without using a dictionary for assigning parts of speech. A parsing device (hereinafter referred to as a fourth conventional example) capable of automatically and accurately assigning a part of speech and adding detailed syntax structure information such as a context-free grammar with a feature structure. is suggesting. This third
The conventional parsing apparatus of (a) uses (a) a spelling characteristic of each word, a characteristic based on how the word is used in a sentence, and a mutual information amount of the word based on the parsed text data composed of a word string. Using multiple attributes, including hierarchical classifications
A leaf tree which has a tree structure of a binary tree format that is divided depending on the attribute value of each attribute and generates a part-of-speech decision tree for giving part-of-speech, and is a node that is not divided by the generated part-of-speech decision tree A part-of-speech decision tree learning means for generating a part-of-speech decision tree with a frequency probability by calculating and assigning the frequency probabilities for a plurality of parts of speech to a node, and (b) based on parsed text data composed of a word string. Using a plurality of attributes including the number of words of the word to be processed, the part of speech of the subject word to be processed, the part of speech of the word immediately before the object of processing, and hierarchical classification using mutual information of words, A node that has a tree structure of a binary tree format that is divided depending on the attribute value of the attribute, generates a grammar rule decision tree for grammar rule assignment, and is an undivided node of the generated grammar rule decision tree. For leaf nodes Grammar rule decision tree learning means for generating a grammar rule decision tree with frequency probability by calculating and assigning frequency probabilities for a plurality of grammar rules, and (c) parsing text data composed of word strings. ,
The number of words to be processed, the part of speech of the subject word to be processed,
Using a plurality of attributes including the part of speech of the word immediately before the processing target, and hierarchical classification using the mutual information of the words, a binary tree format is used which is divided depending on the attribute value of each of the above attributes. Generate a processing direction decision tree for determining a processing direction in each parsing state in the grammar rule assignment processing having a tree structure,
Processing direction decision tree learning for generating a processing direction decision tree with a frequency probability by calculating and assigning frequency probabilities for a plurality of processing directions to leaf nodes that are nodes that are not split and that are generated as described above. Means,
(D) Using the part-of-speech decision tree with frequency probabilities generated by the part-of-speech tree learning means, based on the text data consisting of the input word string to be processed, the frequency probabilities assigned to the leaf nodes In the above, a plurality of upper n frequency probabilities are selected and assigned to each word of the text data, and a part of speech having a maximum connection probability in the word string of the text data is determined as a correct part of speech string,
Using a predetermined stack decoder algorithm, after selecting a purging state having a maximum connection probability for the word string in each purging state in the grammar rule assignment processing, the parsing state generated by the processing direction decision tree learning means is used. The grammar rule with frequency probability generated by the grammar rule decision tree learning means in the parsing state in the determined processing direction is determined by using the processing direction decision tree with frequency probability. A syntactic information adding unit that adds syntactic analysis information by adding a grammar rule to the word string to be processed according to the decision tree and outputs syntactically analyzed text data.

[0007]

However, in the English parsing apparatus of the fourth conventional example, since the English parsing is performed, the delimiter of words is determined by a relatively simple rule using blank characters as clues. I can judge. However, in Japanese, it is difficult to find word breaks. Therefore, in order to use English parsing that analyzes from the state in which word break information is added to Japanese parsing, a mechanism that determines word breaks is necessary. Cannot be processed.

It is an object of the present invention to provide a method of automatically assigning a part of speech more accurately than in the fourth conventional example without using a dictionary for assigning Japanese parts of speech, and a context with a feature structure. An object of the present invention is to provide a Japanese syntax analyzer capable of adding detailed syntax structure information such as free grammar.

[0009]

According to a first aspect of the present invention, there is provided a Japanese-language parsing apparatus, comprising: a spelling feature for each word; Using a plurality of attributes including the characteristics according to how they are used and the hierarchical classification using mutual information of words, the binary tree format is divided depending on the attribute value of each attribute described above. By generating a part-of-speech decision tree having a tree structure for part-of-speech assignment, by calculating and adding frequency probabilities for a plurality of parts of speech to a leaf node that is an undivided node of the generated part-of-speech decision tree, First learning means for generating a part-of-speech decision tree with frequency probabilities of part-of-speech categories;
Based on the text data, a plurality of attributes including a spelling characteristic of each word, a characteristic of a succeeding character, a characteristic of a part of speech connected before, and a hierarchical classification using mutual information of words are used. Generating a word-segmented decision tree for word segmentation having a tree structure in a binary tree format that is segmented depending on the attribute value of each attribute, and the generated word-segmented decision tree is not segmented. A second learning unit that generates a word division decision tree with a frequency probability of a word category by calculating and adding frequency probabilities for words and non-words to a leaf node that is a node, and based on the text data. Using a plurality of attributes including the number of words of the word to be processed, the part of speech of the subject word to be processed, the part of speech of the word immediately before the object of processing, and hierarchical classification using mutual information of words, Attribute value of attribute A grammar rule decision tree for grammar rule assignment is generated having a tree structure of a binary tree format that is dependently divided, and a leaf node that is an undivided node of the generated grammar rule decision tree is generated. By calculating and assigning frequency probabilities for multiple grammar rules,
Third learning means for generating a grammar rule decision tree with frequency probability, based on the text data, the number of words to be processed, the part of speech of the head word to be processed, the part of speech of the word immediately before the processing target, and the word Using a plurality of attributes including a hierarchical classification using mutual information, a tree structure of a binary tree format that is divided depending on the attribute value of each of the above attributes is used in the grammar rule assignment process. Generates a processing direction decision tree for determining a processing direction in each purging state, and calculates and assigns frequency probabilities for a plurality of processing directions to a leaf node that is an undivided node of the generated processing direction decision tree. By doing so, the fourth learning means for generating a processing direction decision tree with a frequency probability and the second learning means based on text data consisting of an input Japanese character string Using the word segmentation decision tree with frequency probabilities of the word categories, selecting the top plural n frequency probabilities among the frequency probabilities of the word categories assigned to the leaf nodes of the word segmentation decision tree, and selecting each of the text data The part-of-speech tree is assigned to a word candidate, and using the part-of-speech tree with frequency probability of the part-of-speech category generated by the first learning means, based on the text data composed of the input character string. Among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of n, a plurality of top n frequency probabilities are selected and assigned to each word candidate of the text data, and the top plural n in the word candidate sequence of the text data are selected. First processing means for outputting a sequence of combinations of words and parts of speech that have been divided into words having a combination probability of n as a plurality of n processing candidates; A predetermined stack decoder algorithm is used until a single sentence is established for each of the processing candidates one by one from the higher processing candidates among the plurality of n processing candidates output from one processing means. Then, in the grammar rule assignment process, after selecting a purging state in which the connection probability for the word string in each purging state has the maximum connection probability, the processing direction decision tree with frequency probability generated by the fourth learning means is used. In the parsing state in the determined processing direction, the grammatical rule is determined according to the grammar rule decision tree with frequency probability generated by the third learning means. Second processing means for adding parsing information by adding to the column and outputting parsed text data. And features.

Further, in the Japanese parsing apparatus according to claim 2, in the Japanese parsing apparatus according to claim 1, each of the decision tree learning means, when dividing in the binary tree format, The attribute having the largest difference (H ₀ −H) between the entropy H ₀ indicating the priority of the validity of the attribute before the attribute and the entropy H after the split is selected as the attribute of the candidate for division, and a predetermined division continuation criterion Is satisfied, the decision tree is updated by dividing in the form of a binary tree.

Further, in the Japanese parsing apparatus according to the third aspect, in the Japanese parsing apparatus according to the second aspect, the division continuation criterion is: (I) entropy when the division is performed based on the selected attribute. (H ₀ −H) is equal to or greater than a predetermined entropy threshold value Hth, and (II) the number of events of the set of the attribute after division based on the selected attribute and its attribute value and part of speech is the predetermined number of events It is characterized by being equal to or more than the threshold value Dth.

Further, the Japanese parsing apparatus according to a fourth aspect of the present invention is the Japanese parsing apparatus according to any one of the first to third aspects, wherein the first processing means is configured to determine the word division. From the frequency probabilities of the word categories assigned to the leaf nodes of the tree, select the top n number of frequency probabilities and assign them to each word candidate of the text data, and to the leaf node of the part-of-speech assignment decision tree After selecting a plurality of top n frequency probabilities from the frequency probabilities of the given part-of-speech categories and adding them to each word candidate of the text data, they are used for a predetermined stack decoder algorithm, and The candidates of the combination of words and parts of speech whose connection probabilities to the word candidate sequence of the text data are equal to or higher than a predetermined connection probability are limited, and the candidates of the combination are limited. A row of combinations of word split word and part of speech having a higher multiple of n joint probability in a string of the text data at the end, and outputs a plurality of n candidate processing.

According to a fifth aspect of the present invention, there is provided a Japanese-language parsing apparatus according to a spelling characteristic of each word and a usage in a sentence based on parsed text data composed of Japanese character strings. Using a plurality of attributes including a feature and a hierarchical classification using mutual information of words, a part-of-speech having a tree structure in a binary tree format that is divided depending on the attribute value of each of the above attributes By generating a part-of-speech decision tree for assignment and calculating and assigning frequency probabilities for a plurality of parts-of-speech to a leaf node that is an undivided node of the generated part-of-speech decision tree, with a part-of-speech category frequency probability First learning means for generating a part-of-speech decision tree, and using the spelling characteristics of each word, the characteristics of the succeeding characters, the characteristics of the part of speech connected before, and the mutual information of the words based on the text data. Had a hierarchical minute And generating a word division decision tree for word division having a tree structure in a binary tree format such that the tree is divided depending on the attribute value of each of the above attributes. Learning means for generating a word division decision tree with frequency probabilities of word categories by calculating and adding frequency probabilities for words and non-words to leaf nodes, which are nodes that are not split, in the word division decision tree And a hierarchical classification using the number of words of the processing target, the part of speech of the subject head word to be processed, the part of speech of the word immediately before the processing target, and the mutual information of the words based on the text data. A grammar rule decision tree for giving a grammar rule having a tree structure in a binary tree format that is divided depending on the attribute value of each of the above attributes, Do not split the decision tree A third learning means for generating a grammar rule decision tree with a frequency probability by calculating and assigning frequency probabilities for a plurality of grammar rules to a leaf node which is a node; Using a plurality of attributes including the number of words of the word, the part of speech of the subject head word to be processed, the part of speech of the word immediately before the processing object, and hierarchical classification using mutual information of words, Generating a processing direction determination tree for determining a processing direction in each parsing state in the grammar rule assignment processing in a tree structure of a binary tree format that is divided depending on a value; Fourth learning means for calculating and assigning frequency probabilities for a plurality of processing directions to a leaf node which is a node that is not split into trees, thereby generating a processing direction decision tree with frequency probabilities;
Assigned to leaf nodes of the word division decision tree using a word division decision tree with frequency probabilities of word categories generated by the second learning means, based on text data consisting of an input Japanese character string The frequency probabilities of the upper plural n are selected from the frequency probabilities of the word categories given and assigned to each word candidate of the text data, and based on the text data composed of the input character string, Using the part-of-speech decision tree with frequency probabilities of the part-of-speech categories generated by the first learning means, a plurality of top n frequency probabilities are selected from the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech decision tree. Then, one word is assigned to each word candidate from the first word candidate of the text data. A row of combinations of word split word and part of speech having a probability, the outputs as processing candidate 1
And a processing candidate output from the first processing means, using a predetermined stack decoder algorithm, to obtain the maximum combination probability for the word string in each parsing state in the grammar rule assignment processing. After selecting the purging state having the connection probability, the processing direction in the word string to be processed is determined using the processing direction decision tree with frequency probability generated by the fourth learning means, and the processing direction in the determined processing direction is determined. In the parsing state, a grammar rule is added to the word string to be processed in accordance with the grammar rule decision tree with frequency probability generated by the third learning means, thereby giving syntactic analysis information and outputting a parsed word. 2 and the processing of the first and second processing means from the beginning of the text data consisting of the input character string. One of each word candidate, is characterized in that a third processing means for controlling so as to repeat until the parsed text data for one sentence of the text data is obtained.

According to a sixth aspect of the present invention, there is provided the Japanese syntax analyzer according to the fifth aspect, wherein each of the decision tree learning means is configured to perform the above-mentioned splitting in a binary tree format. The attribute having the largest difference (H ₀ −H) between the entropy H ₀ indicating the priority of the validity of the attribute before the attribute and the entropy H after the split is selected as the attribute of the candidate for division, and a predetermined division continuation criterion Is satisfied, the decision tree is updated by dividing it in the form of a binary tree.

Further, the Japanese syntax analyzer according to claim 7 is the Japanese syntax analyzer according to claim 6, wherein the division continuation criterion is: (I) entropy when the division is performed based on the selected attribute. (H ₀ −H) is equal to or greater than a predetermined entropy threshold value Hth, and (II) the number of events of the set of the attribute after division based on the selected attribute and its attribute value and part of speech is the predetermined number of events It is characterized by being equal to or more than the threshold value Dth.

According to a further aspect of the present invention, there is provided the Japanese language parsing apparatus according to any one of the fifth to seventh aspects, wherein the first processing means comprises the step of: From the frequency probabilities of the word categories assigned to the leaf nodes of the tree, select the top n number of frequency probabilities and assign them to the word candidates of the text data, and assign them to the leaf nodes of the part-of-speech assignment decision tree After selecting the top n frequency probabilities from among the frequency probabilities of the part-of-speech categories given and assigning them to each word candidate of the above-described text data, using a predetermined stack decoder algorithm, the text being processed is processed. Only the processing candidates of the sequence of the combination of the word and the part-of-speech in which the combination probability of the data to the word candidate sequence is equal to or greater than the predetermined combination probability are limited, and the candidates of the combination are limited. A row of combinations of word split word and part of speech having a joint probability of the top-level in the above text data string Ryoji, and outputs the processed candidate.

[0017]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 shows an embodiment according to the present invention.
1 is a block diagram of a Japanese syntax analysis system including a decision tree learning device 10 and a syntax information providing device 11. FIG. This Japanese parsing system adds detailed parts of the syntax structure, such as context-free grammar with feature structure, to the Japanese text data after adding the parts of speech without referring to the dictionary for the parts of speech. (A) based on the text data with syntax information stored in the text memory 21 with syntax analysis,
By referring to the attribute list stored in the attribute list memory 22 and the part-of-speech list stored in the part-of-speech list memory 23, the part-of-speech determination with frequency probability is performed by learning by executing a part-of-speech determination tree learning process described later in detail. A tree is generated and stored in the part-of-speech decision tree file memory 25. Then, based on the text data with syntax information stored in the text memory 21 with syntax analysis, the attribute list memory 22
List and grammar rule list memory 24
The grammar rule decision tree with the frequency probability is generated by executing the grammar rule decision tree learning process described in detail later with reference to the grammar rule list stored in the grammar rule decision tree file memory 26. The attribute list stored in the attribute list memory 22 and the grammar rule list stored in the grammar rule list memory 24 are stored based on the text data with the syntax information stored in the text memory 21 with the syntax analysis. With reference to the above, a processing direction decision tree learning process, which will be described in detail later, is executed to perform learning, thereby generating a processing direction decision tree with frequency probability and storing it in the processing direction decision tree file memory 27. On the basis of the text data with the syntax information stored in the text memory 21 with the analysis, the attribute list memory 22
By referring to the attribute list stored in the word list and the word list stored in the word list memory 29, a word division decision tree with frequency probability is learned by executing a word division decision tree learning process described later in detail. A decision tree learning device 10 that generates and stores the word tree in the word division decision tree file memory 28;
(B) The stack memory 12 is connected to the syntax information providing apparatus 11, and the part-of-speech decision tree with frequency probability stored in the part-of-speech tree file memory 25, and the grammar rule with frequency probability stored in the grammar rule decision tree file memory 26 Attribute list memory using a decision tree, a processing direction decision tree with frequency probability stored in the processing direction decision tree file memory 27, and a word division decision tree with frequency probability stored in the word division decision tree file memory 28 An attribute list stored at 22;
A part-of-speech list stored in a part-of-speech list memory 23, a grammar rule list stored in a grammar rule list memory 24,
With reference to the word list stored in the word list memory 29, the text data stored and input in the text data memory 30 is subjected to word division and part of speech assignment processing (to be described in detail later) (FIGS. 8 and 9) and grammar. By executing the syntax information providing process including the rule providing process (FIGS. 10 and 11), the part-of-speech is provided and the grammatical rule is provided, the parsed text data is generated, and the parsed text data 31 is generated. And a syntax information providing device 11 for storing. In the present embodiment, the text data is a Japanese sentence composed of a Japanese character string or word string.

First, the knowledge used in the present embodiment will be described. In general, Japanese syntax analyzers often detect dependency relationships, and in the present embodiment, they are described using a context-free grammar with a feature structure. Further, as features used in the decision tree, features of partial character strings constituting words, connection information such as words or parts of speech, and the like are used.

Next, the grammar used in the present embodiment will be described. In the present embodiment, a context-free grammar with a feature structure using 16 types of features is used. The features include a category (cat), a noun type (n_type),
There are verb types (v_type) and the like, and part-of-speech tags are represented by combinations of basic categories, noun and verb types, types of inflections, and inflections (see Table 1), and are about 200.
Range. The grammar is about 1 based on this part of speech tag.
It consists of 00 types of syntactic rules (see Table 2).

[0021]

[Table 1] Example of part of speech tag ─────────────────────────────────── Rule case verb ─────────────────────────────── For example,,,,,,, to, to, to, , Parent, cat, cat p bar 0 pos particle p_type case ───────────────────────────────────

[0022]

[Table 2] An example of a grammar rule {Rule VP_np + ap} {Description VP_np + ap → NP AP}例 Example [vp [np even you] [if you like ap] ───────────────── {Parent cat v bar 2 pos vp_np + ap n_type V *}子 child 1 cat CAT bar 2 pos V * n_type V * v_type V * a_type A katyouyou V * katyuyoukei V * ─────────────────────────────────── Condition not ((A = unspec) | (CAT = s) ) ───────────────────────────────────

This grammar is considered so as to capture the expression in the conversation data. In the sense of a so-called ordinary grammar, it is also considered so as to be able to process non-sentences. ing.

Next, the nature (characteristics) of the wording will be described. With only the grammatical constraints described above, there are many analysis candidates only for the syntax structure of the morphologically analyzed input.
Furthermore, considering the candidates for morphological analysis, there will be an enormous amount of candidates. In order to select a correct structure from such candidates, it is necessary to make an appropriate selection in the course of processing, and various characteristics are used to make the selection. Features used include (1) words (or phrases,
Clauses) and (2) contextual features (in sentences), which are effectively used at the morpheme and syntax levels according to statistical likelihood.

Next, features relating to words will be described. The characteristics of the word itself, such as its partial spelling, the number of characters, the type of constituent characters, and the like, and after the part-of-speech tag is attached, the value of each feature of the part-of-speech tag is used as the characteristic. When a phrase or a clause is grouped by a grammatical rule instead of a word, the feature value of the parent node of the rule is used as a feature. In addition, what kind of node is used, the number of words forming a phrase or a clause, and the like are also used as features. The characteristics of the vocabulary of the word itself are very useful information for determining a tag for the word, and are also used as information of a head word in a certain range of the syntax structure. The vocabulary information handled in the present embodiment can use information obtained from a dictionary as a headword, but basically, the partial character string or the number of characters constituting the word as described above is used. There is no concept of so-called "unknown word" because it is characterized by the like.
When considering "unknown word" in the present embodiment, it can be considered as a word that does not appear in the learning data from which the feature is extracted.

Next, features relating to the in-sentence context will be described. In addition to the features related to the current processing target, the features of the word immediately before it, the characteristics of the characters to be connected, the features of the word or part of speech two words before the processing target, the features related to the beginning and end of the sentence, the characteristics of the processing target The information of the nearest particle in front, the number of words up to that, and the like are used as features.
As described above, not only information of a certain fixed word but also a feature that a distance is flexibly changed can be used. Whether or not the character string currently being processed appears in the same sentence can also be used as a feature. These features are called "characteristic features", and a framework for describing them is used in the present embodiment.

Further, analysis using a decision tree with probability will be described. Not all "grammatical features" are used in morphemes and parsing. "Characteristics"
Is based on the statistical advantage that appears in the learning corpus,
It is used in the framework of decision trees for efficient use as analytical knowledge. Here, a minimum cost complexity (minimal cost-complexity) algorithm was used for pruning, and a forward-backward (Forward-Backward) algorithm was used for smoothing. The decision tree to be used is a binary tree, and uses “characteristics of language” for judgment at each branch point. However, since it is a binary tree, a feature having three or more values cannot be directly used. Therefore, in order to use the features of the wording having three or more values as information on the branch point of the decision tree, a unique bit string consisting of “0” and “1” is given to each value of the feature, and A specific bit is used as information of one branch point. In addition, branching is performed to determine whether the feature is a valid feature. Whether a feature is valid depends on whether the feature can be determined. For example, when processing the word at the beginning of a sentence, the feature relating to the immediately preceding word cannot be used, and is not a valid feature.

Next, the flow of the analysis process will be described. In order to realize a processing mechanism that integrates morphological analysis and syntax analysis, the following two integration methods are used. (A) [Processing A] Morphological analysis is performed once until the end of the sentence, and syntax analysis is sequentially performed on each candidate. The process A will be described as an embodiment in the following description of the embodiment. (B) [Processing B] Morphological analysis and syntax analysis are performed while processing is performed in character units from left to right. The process B will be described as a modification.

In process A, there is no advantage in integration that syntax information can be effectively used at the time of morphological analysis, and integration in process B is desired. For comparison, in the experiment, the two processing methods were switched and used. In the present embodiment, a decision tree model is adopted as the statistical language model, and the following four types of decision trees are constructed using learning data for analysis processing. (A) [Decision Tree for Word Recognition] A decision tree for determining validity as a word (hereinafter, referred to as a word division decision tree). (B) [decision tree for giving part-of-speech] A decision tree for selecting candidates for part-of-speech tags (hereinafter, referred to as a part-of-speech decision tree). (C) [Decision Tree for Applying Grammar Rules] A decision tree for selecting a syntax rule to be applied (hereinafter, referred to as a grammar rule decision tree). (D) [Processing direction decision tree] A decision tree for selecting a processing direction for a word when a grammar rule is applied (hereinafter, referred to as a processing direction decision tree).

In the analysis processing, these four decision trees are used in the following four states, respectively, and the processing is performed in each state. (A) State of word recognition: It is determined whether the current character string to be processed is valid as a word. If it is appropriate, the state as a word node is set as a part-of-speech state, and a state of word recognition is created in which a character string including the next character is to be processed. If it is determined that it is not appropriate, a state of word recognition is created with the character string containing the next character as a processing target, and the processing of each state is performed. (B) Part-of-speech state: An appropriate part-of-speech tag is assigned to the currently processed word node (when there are a plurality of part-of-speech candidates,
The state for the candidates is created and processing is performed. ), A state of applying the syntax rule as a tag node, and a state of word recognition for the next one character to be processed is created, and processing is performed for each state. (C) Status of application of syntax rules: The current node to be processed refers to the previous node, sets a root node for applicable syntax rules, sets the status of application of syntax rules, and sets the next character. Is made a word recognition state for processing, and processing is performed for each state. (D) Processing direction selection state: A root node is set for the applicable processing direction with reference to the previous node from the current processing target node, and the processing direction is applied. A state of word recognition for one character is created, and processing is performed for each state.

In the word recognition state, a decision tree for determining whether a processing character string is valid as a word is used for creating a word node. The decision tree used here is a “word division decision tree”, and a probability value that appears as a word is calculated, and whether or not it is appropriate is determined based on the value. When a part-of-speech tag is assigned, a “part-of-speech decision tree” is used, and a part-of-speech tag candidate having a certain value or more with a probability is given. Regarding the application of syntax rules, a root node is set for a rule having a value equal to or more than a certain value among rules applicable by a “grammar rule decision tree” for rules applicable grammatically. Further, regarding the selection of the processing direction, a root node is set for a processing direction having a value equal to or more than a certain value among processing directions applicable by the “processing direction decision tree” for rules applicable grammatically. You. In addition, for the processing of a plurality of states, a known stack decoder algorithm is used to improve the processing efficiency.

Next, grammar rules and knowledge used in the syntax analysis system of the present embodiment will be described in detail. First, detailed grammatical rules used in the present embodiment will be described. Many linguistic phenomena appearing in a corpus, which is a learning text database, have linguistic characteristics by being organized as a unit. Also,
This feature is often very useful information for parsing. As the grammar, a context-free grammar with a feature structure is used. This is because it is considered that by giving features that do not appear in the child node of the grammar rule to the parent node, more detailed information can be given and the features of each feature are easy to use.

Various features are used to obtain the correct structure from the structure according to the grammar rules described above. First, the feature of the value of each feature given to the grammar is used. In addition to these features, the vocabulary features of the words themselves and the features of the sentences are used. In various contexts, examining the statistical properties of the values taken by the features of a grammar rule can give an indication of which grammar rule is likely. The characteristics of the vocabulary of the word itself are very effective information for determining a tag for the word, and are also used as information of the first head word in a certain range of the syntax structure. The vocabulary information handled in the present embodiment is not information obtained from the dictionary, but is characterized by the suffix and prefix constituting the word, the number of characters of the word, and the like. The sentence features include the number of words contained in one sentence, punctuation,
Alternatively, it is characterized by whether the same word appears more than once. Further, in order to use contextual information, features related to the immediately preceding word, the end of a sentence, the beginning of a sentence, the first word in the range covered by the grammar rule to be processed, the last word, and the like are also available. To describe various features, grammarists (specialists who generate grammar rules)
Use a framework to describe the characteristics of the grammar.

Next, a statistical parsing method used in this embodiment will be described. In the present embodiment, in order to efficiently use the above-described features, statistical properties are calculated using a learning corpus, and learning is performed as a decision tree with probability.
In the decision tree used in this method, a minimum cost-complexity algorithm was used for pruning, and a forward-backward algorithm was used for smoothing.
This decision tree is a binary tree. Therefore, the above-mentioned features cannot be directly used as the information of the branch point of the decision tree. Therefore, a unique bit string of “0” and “1” is given to each feature value, and specific bits are used. In addition, branching is performed to determine whether the feature is a valid feature. Here, for example, when processing the word at the beginning of the sentence, the feature related to the immediately preceding word cannot be used.

The syntax analysis of the present method is regarded as a process of continuously constructing a state representing a partial parse tree. To move from one state to the next, one of the following processes is performed. The above-described decision tree is formed for each process. (A) After assigning tags to words and determining syntactic features,
Determine semantic features. (B) Determine whether the current processing target is the end of the component. (C) Add a grammar rule to the current component to be processed. There are several possibilities for the order of these processes. In the present embodiment, first, all words are tagged with parts of speech, and the analysis is performed from left to right in a bottom-up manner. I have. The number of candidates generated from the grammar is very large, and it seems difficult to find the best candidate.However, in this method, the probability depending on the context is estimated using a decision tree.
The efficiency of processing is improved by using a stack decoder algorithm described in detail below.

Next, the configuration and operation of the syntax analysis system shown in FIG. 1 will be described. The decision tree learning device 10 uses the spelling characteristics of each word, the characteristics based on how the words are used in the text, and the characteristics of the words based on the parsed text data composed of the character strings or word strings read from the memory 21. Attribute list memory 22 including hierarchical classification using mutual information
Using a plurality of attributes stored in the above, a part-of-speech decision tree for giving a part-of-speech having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute is generated, By calculating and assigning frequency probabilities for a plurality of parts of speech to a leaf node that is an undivided node of the part of speech decision tree, a part-of-speech decision tree with frequency probabilities is generated and stored in the part-of-speech tree storage file memory 25. Next, the decision tree learning device 10 determines the number of words to be processed, the part-of-speech of the subject word to be processed, the part-of-speech of the subject word to be processed, based on the parsed text data consisting of the character string or word string read from the memory 21. Is divided depending on the attribute value of each attribute, using a plurality of attributes stored in the attribute list memory 22 including the part of speech of the word immediately before, the hierarchical classification using the mutual information amount of the word. A grammar rule decision tree having a tree structure of a binary tree format as described above is generated for assigning a grammar rule, and the frequency of a plurality of grammar rules for a leaf node which is an undivided node of the generated grammar rule decision tree is described. By calculating and assigning probabilities, a grammar rule decision tree with frequency probabilities is generated and stored in the grammar rule decision tree file memory 26.

Further, the decision tree learning device 10 includes a memory 2
1, the number of words to be processed, the part of speech of the head word to be processed, the part of speech of the word immediately before the processing, and the mutual Using a plurality of attributes stored in the attribute list memory 22 including a hierarchical classification using the amount of information, a tree structure in a binary tree format that is divided depending on the attribute value of each attribute is provided. Generate a processing direction decision tree for determining a processing direction in each parsing state in the grammar rule assignment processing, and generate a frequency for a plurality of processing directions with respect to a leaf node which is an undivided node of the generated processing direction decision tree. By calculating and assigning the probabilities, a processing direction decision tree with frequency probability is generated and stored in the processing direction decision tree file memory 27. Further, based on the parsed text data composed of a character string or a word string read from the memory 21, the spelling characteristics of each word, the characteristics according to how the words are used in the text, and the mutual information amount of the words are determined. Using a plurality of attributes including the hierarchical classification used and stored in the attribute list memory 22, the tree structure has a tree structure in a binary tree format that is divided depending on the attribute value of each attribute. By generating a word division decision tree for word division of the word, and calculating and adding frequency probabilities for a plurality of words to a leaf node that is an undivided node of the generated word division decision tree. An attached word division decision tree is generated and stored in the word division decision tree file memory 28.

Here, when the decision tree learning device 10 performs the division in the form of the binary tree, the entropy H ₀ indicating the priority of the validity of the attribute before the division by each attribute and the entropy H after the division are used. The attribute having the largest difference (H ₀ −H) is selected as the attribute of the division candidate, and when a predetermined division continuation criterion is satisfied, the decision tree is updated by division in the form of a binary tree.

Next, the syntax information providing device 11 generates a word with frequency probability of the word category generated by the decision tree learning device 10 based on the text data consisting of a Japanese character string or word string input from the memory 30. Using the split decision tree, the frequency probabilities of the top plurality n among the frequency probabilities of the word categories assigned to the leaf nodes of the word split decision tree are selected and assigned to each word candidate of the text data. And a part of speech assigned to a leaf node of the part of speech tree using a part of speech tree with frequency probability of the part of speech category generated by the decision tree learning device 10 based on the text data composed of the input character string. From the frequency probabilities of the categories, a plurality of n higher frequency probabilities are selected and assigned to each word candidate of the text data. A row of combinations of word split word and part of speech having a higher multiple of n joint probability in word candidate string of text data, and a plurality of n candidate processing.
Next, the syntax information providing device 11 performs a predetermined stack decoder algorithm until a single sentence is established for each of the processing candidates in order from the higher processing candidate among the plurality of n processing candidates. After selecting the purging state in which the connection probability for the word string in each purging state in the grammar rule assignment processing has the maximum connection probability, the processing direction decision tree with frequency probability generated by the decision tree learning device 10 is used. The processing direction in the word string to be processed is determined using the grammar rule according to the grammar rule decision tree with frequency probability generated by the decision tree learning device 10 in the parsing state in the determined processing direction. By adding the parsing information to the column, the parsing information is output and the parsed text data is output.

Here, the syntactic information providing device 11 selects the top n frequency probabilities from among the frequency probabilities of the word categories assigned to the leaf nodes of the word division decision tree, and selects each word candidate of the text data. After selecting the top n frequency probabilities from among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech assignment decision tree and assigning them to each word candidate of the text data Using a predetermined stack decoder algorithm, leaving only processing candidates for a row of word and part-of-speech combinations in which the combining probability of the text data being processed with respect to the word candidate string is equal to or greater than the predetermined combining probability. And the word-segmented word and the part of speech having the upper plural n connection probabilities in the character string or word string of the text data at the end of the processing The combination of the columns, to output a plurality of n candidate processing.

In the present embodiment, a part-of-speech decision tree having a tree structure of a binary tree format and having a frequency probability for giving a part-of-speech is obtained by using a part-of-speech decision tree learning process using knowledge obtained from parsed text data. Generate and give part of speech. The attributes used in the part-of-speech decision tree with frequency probability use linguistic features and statistical features obtained from a corpus. In the conventional part-of-speech assignment, a method is generally used in which part-of-speech candidates are limited by drawing a dictionary, and the most appropriate part-of-speech is selected from the candidates, taking into account the relationship with words that appear before and after. However, there is a problem of the cost for creating and maintaining the dictionary. In addition, special processing is required for words that are not included in dictionary items (unknown words) and words that are used as parts of speech that are not included in dictionary part-of-speech candidates. In the method using the part-of-speech decision tree with frequency probability according to the present embodiment, a dictionary is not used in order to determine the part of speech of a word, so that the cost of creating and maintaining the dictionary does not matter. A part-of-speech decision tree with frequency probabilities is constructed by learning using parsed text. Therefore, if there is text data that has been parsed, it is possible to flexibly cope with the part of speech system. In addition, the priority of the part of speech sequence can be automatically determined using the frequency probability. The part-of-speech decision tree is a tree structure model that classifies a target into an appropriate class from a plurality of attributes and their attribute values. In the part of speech, the object corresponds to each word and the class corresponds to the part of speech. As the attribute, a spelling feature of each word, a feature according to a usage in a sentence, a hierarchical classification using mutual information of words, and the like are used.

In the grammar assignment process in the syntax information assignment device 11, a grammar rule is assigned to a word candidate string to be processed using a grammar rule decision tree and a processing direction decision tree. Here, as attributes of the grammar rule decision tree and the processing direction decision tree, the number of words of the processing target, the part of speech of the head word of the processing target, the part of speech of the word immediately before the processing target, and the mutual information of the words were used. Use hierarchical classification. In the method using the grammar rule decision tree and the processing direction decision tree, a dictionary is not used in order to determine the addition of the grammar rule, so that the cost of creating and maintaining the dictionary does not matter. A grammar rule decision tree with a frequency probability and a processing direction decision tree are constructed by learning using a parsed text. Therefore, if there is parsed text data, it is possible to flexibly cope with the system of sentence rules. Hereinafter, the syntax analysis system of the present embodiment will be described in detail.

In FIG. 1, the decision tree learning device 10 stores an attribute list stored in an attribute list memory 22 and a part-of-speech list memory 23 based on text data with syntax information stored in a syntax-parsed text memory 21. By referring to the stored part-of-speech list and performing learning by executing a part-of-speech decision tree learning process described in detail later, a part-of-speech decision tree with frequency probability is generated and the part-of-speech decision tree file memory 25 is stored.
Then, based on the text data with syntax information stored in the parsed text memory 21, the attribute list stored in the attribute list memory 22 and the grammar rule list stored in the grammar rule list memory 24 , By executing a grammar rule decision tree learning process, which will be described later in detail, to generate a grammar rule decision tree with frequency probability and store it in the grammar rule decision tree file memory 26;
Further, based on the text data with syntax information stored in the parsed text memory 21, referring to the attribute list stored in the attribute list memory 22 and the grammar rule list stored in the grammar rule list memory 24. By executing and learning a processing direction decision tree learning process described in detail later, a processing direction decision tree with frequency probability is generated and stored in the processing direction decision tree file memory 27.
Based on the text data with syntax information stored in the parsed text memory 21, an attribute list memory 22
By referring to the attribute list stored in the word list and the word list stored in the word list memory 29, a word division decision tree with frequency probability is learned by executing a word division decision tree learning process described later in detail. It is generated and stored in the word division decision tree file memory 28.

Next, a stack memory 12 is connected to the syntax information providing device 11, and the syntax information providing device 11
Part-of-speech decision tree with frequency probability stored in part-of-speech tree memory 25, grammar rule decision tree with frequency probability stored in grammar rule decision tree file memory 26, and frequency stored in processing direction decision tree file memory 27 The attribute list stored in the attribute list memory 22 and the attribute list stored in the part-of-speech list memory 23 using the processing direction decision tree with probability and the word division decision tree with frequency probability stored in the word division decision tree file memory 28. With reference to the part-of-speech list, the grammar rule list stored in the grammar rule list memory 24, and the word list stored in the word list memory 29, the text data stored and input in the text data memory 30 is referred to. And a word segmentation and part-of-speech assignment process (FIGS. 8 and 9) and a grammar rule assignment process (FIGS. 10 and 11), which will be described in detail later. By executing the information adding processing, grant part of speech and by applying grammar rules, generate and store the parsed text data to the parsed text data 31. Here, the generated parsed text data may be output to an output device such as a CRT display or a printer.

Here, the decision tree learning device 10 and the syntax information providing device 11 are, for example, CPs for executing the respective processes.
U, a ROM (read only memory) for storing a program for each process and data necessary for executing the program, and C
It comprises a digital computer having a RAM (random access memory) used as a working memory of the PU. Further, the memories 12, 21 to 29, 30, 31
Is composed of, for example, a hard disk memory. Further, the syntax information providing device 11 includes a stack decoder
A stack memory 12 for executing part-of-speech assignment processing and grammar rule assignment processing using an algorithm is connected.

The word list memory 29 stores a plurality of Japanese words. Table 3 shows an example of the part-of-speech list stored in the part-of-speech list memory 23. Table 4 shows an example of the attribute list stored in the attribute list memory 22.
Table 5 shows an example of the grammar rules stored in the grammar rule list memory 24.

[0047]

[Table 3] Part-of-speech list ───────── Part-of-speech 普通 Common noun Sa-variant noun Adjective noun Formal noun Roman alphabet Main verb Auxiliary verb Adjective Case particle …… ────── ───

[0048]

[Table 4] Attribute list for word segmentation and part of speech ─────────────────────────────────── Attribute Attribute value 階層 Hierarchical classification code using mutual information of words Code The word whose target word contains "~ i" Yes, No The target word is all katakana words Yes, No The length of the target word Numeric value of the word length (for example, 3 for "card") The part of speech attribute of the previous word Value The value of the part of speech attribute Is the following character katakana? Yes, No Is the first character of the target word a kanji? Yes, No …… …… ───────────────────────────────────

[0049]

[Table 5] Attribute list for assigning grammar rules ─────────────────────────────────── Attribute Attribute value ──相互 Mutual information of subject words to be processed Hierarchical word classification based on classification code Code (predetermined bit) Processing target is only one word Yes, No Part of speech of head word to be processed is noun Yes, No Part of speech of word just before processing is noun Yes, No ………………………… …………………… ───────────────────────────────────

[0050]

[Table 6] Grammar rule list ─────────────────────────────────── Noun phrase 1: Noun phrase → Noun , Case particle Noun phrase 2: Noun phrase → noun, connecting particle Verb phrase 1: Verb phrase → main verb, auxiliary verb, final particle …… …………… ────────────── ─────────────────────

In the grammar rule list in Table 4, for example,
The first line means that the noun phrase is composed of a noun and a case particle, and the third line means that the verb phrase is composed of a main verb, an auxiliary verb, and a final particle. Although the processing direction is not displayed as a list, in the present embodiment, the processing direction is one of “right”, “left”, and “up”.

Here, the part-of-speech attribute is an attribute that roughly classifies the part of speech into ten types, and the value of the part-of-speech attribute is, for example,
Nouns, verbs and particles. The hierarchical classification code using mutual information of words is described in, for example, Japanese Patent Application No. 8-027.
809 patent application and prior art document 4 “Akira Ushioda,
“Hierarchical Clustering of Words”, Proceedingsof
COLING'96, The 16th International Conference on Com
putational Linguistics, Vol. 2, pp. 1159-1162, 1996.8
This is a hierarchical classification code classified using the word classification method disclosed in "Month". In this word classification method, words having relatively low frequency of occurrence in words in text data are classified based on a criterion of assigning words having a high percentage of adjacent words to the same word to the same class, and then the word classification result is classified into an intermediate layer. , An upper layer, and a lower layer, and using a predetermined average mutual information that is a global (overall) cost function for all words in the text data, , Upper layer, and lower layer.
In the clustering method using mutual information,
It is assumed that there are a text having the number of words T, a vocabulary having the number of words V, and a vocabulary division function π, where the vocabulary division function π is a division map (mapping) from the vocabulary V to the word class set C in the vocabulary. ) Is a mapping function. The likelihood L (π) of the bigram class model that generates text data composed of a plurality of words is obtained by the following equation.

[0053]

## EQU1 ## L (π) =-Hm + I

Here, Hm is the entropy of the word distribution of the monogram, and I is two adjacent words in the text data.
Average mutual information about _two classes C ₁ and C ₂ (Aver
ageMutual Information; Hereinafter, the average mutual information,
Notated as AMI. ) And can be calculated by the following equation.

[0055]

(Equation 2)

Here, Pr (C ₁ ) is the first class C ₁
Is the probability of occurrence of the word of the class, Pr (C ₂ ) is the probability of occurrence of the word of the second class C ₂ , and Pr (C ₁ | C ₂ ) is the probability of occurrence of the word of the second class C ₂ , First class C ₁
Is the conditional probability of occurrence of the word, Pr (C ₁ ,
C ₂ ) is the probability that words of the _first class C ₁ and words of the second class C ₂ will appear adjacent to each other. Therefore, AMI is different the first class C ₁ of a word the probability of a word is the second class C ₂ appearing adjacent word of the first class C ₁ together represented by the number 2 It represents the probability of appearance and percentage of relative frequency divided by the product of the probabilities of occurrence of the second class of C ₂ words. Since the entropy H is a value independent of the mapping function π, the mapping function that maximizes the AMI also maximizes the likelihood L (π) of the text. Therefore,
The AMI can be used as an objective function in class construction of words.

The above word classification method can generate a tree structure having a balanced binary tree form in that words having similar meanings or syntactic characteristics are arranged at close positions. At the end of the process, the path from the root node (root node) to the leaf node (leaf node) is traced, and 0 or 1 representing a leftward branch or a rightward branch, respectively. By assigning one bit to each branch, a bit string (word bit) can be assigned to each word in the vocabulary.

Next, an algorithm of a decision tree learning process for constructing a part-of-speech decision tree, a grammar rule decision tree, a processing direction decision tree, and a word division decision tree, and an algorithm of a syntax information adding process will be described.

In each decision tree learning process, the validity of each attribute is calculated independently of the other attributes, and the classification order based on the efficient attributes for determining the class is determined by dividing the structure divided in the form of a binary tree. Construct as a tree structure having The validity of the attribute is evaluated based on the entropy H after division and classification according to the attribute. The entropy here indicates the priority of the validity of the attribute. That is, when dividing into a node N ₁ and a node N ₂ with a certain attribute B, the entropy H ₀ before the division,
And entropy H after division, the entropy H ₁ for node N _1, and the entropy H ₂ to node N ₂ is expressed by the following equation.

[0060]

(Equation 3)

H = p ₁ H ₁ + (1−p ₁ ) H ₂ where:

(Equation 5)

(Equation 6)

Here, p (tagall) is all part-of-speech tags before division (for a part-of-speech decision tree; a grammar rule tag for a grammar rule decision tree; a processing direction tag for a processing direction decision tree, ie, , “Up,” “left,” and “right.”) Is the frequency or appearance probability of the number of events, and Σ for tagall indicates the sum of all part-of-speech tags before division. P ₁ is the sum of the frequency probabilities of the number of events of the part-of-speech tag included when the node is divided into nodes N ₁ . Furthermore, p (tagN ₁₎ is the number of frequency probability events for all parts of speech tags of the node N _1, the Σ of tagn _1, indicates the sum for all parts of speech tags of the node N _1. p (ta
gN ₂₎ is the number of frequency probability of the event for all of the part-of-speech tag of the node N _2, for tagN ₂ of Σ
Indicates the sum for all parts of speech tags of the node N _2.

In order to calculate the validity, event information (event: hereinafter, referred to as an event) including a set of “attribute, its attribute value, and part of speech” for each word is preliminarily extracted from the text data for learning. Specifically, an attribute that minimizes the entropy H after classification is obtained for a set of all events, and is assigned to the first node. The set of events is divided according to the attribute value of this attribute, and corresponding child nodes are created. A tree structure is constructed by repeating the same process at each child node. The condition for stopping the division is that the number of events included in each node is equal to or less than a certain number, or the effectiveness of the division is equal to or less than a certain reference (here, a predetermined amount having a difference between entropy H after division and entropy H ₀ before division). Is not exceeded.) Here, a node that is not divided is called a leaf. At the leaf of the learned decision tree, the frequency probability of each part of speech is calculated from a given set of events.

Here, in the syntax information adding system according to the present embodiment, the related art document 5 “LEBaum,“ Aninequality a
nd associated maximization technique in statistica
l estimation for probabilistic functions of a Mark
ov process ", Inequalities, Vol. 3, pp. 1-8, 1972".
Backward) algorithm is used to perform smoothing based on the learning data for smoothing so as to minimize the difference between the probability obtained from the learning data for smoothing and the probability obtained from the decision tree. Correct the last frequency probability distribution to be given. Further, in the system of the present embodiment, a two-stage decision tree is created according to the algorithm of the decision tree learning process. The first row shows the parts of speech roughly classified (hereinafter GPOS (G
local Part of Speech). ) (Here, it corresponds to one of the attributes of the actual part of speech, and is classified into, for example, a verb, a noun, an article, etc.). First, a decision tree for determining the actual part of speech (part of speech tag level shown in Table 3) is created. In the present embodiment, a more detailed part-of-speech level name is called a part-of-speech tag. That is, by generating a decision tree by dividing into two stages, 1
Each time, the required storage capacity of the storage device is greatly reduced.

In the part-of-speech giving process, the text data of the input sentence is processed from left to right, and a part-of-speech sequence that maximizes the connection probability is output. The input sentence is composed of a plurality of N words such as w ₁ , w ₂ ,..., W _N , and the part-of-speech sequence {t ₁ , t ₂ ,.
Assuming that _N ｝ (where t _i is the part of speech of the i-th word) is obtained, the connection probability P is represented by the following equation. In addition,
In the present embodiment, the appearance of the part of speech is not treated as a Markov information source, but as an information source depending on the words and parts of speech that have appeared so far. Thus, in a sufficiently long sentence, it is in principle possible to derive the part of speech of the last word depending on the first word of the sentence and its part of speech.

[0065]

(7) P≡p (t ₁ , t ₂ ,..., T _N │w ₁ , w ₂ ,..., W _N )

(Equation 8)

The right side of the above equation (7) represents input sentences w ₁ , w ₂ ,.
When w _N is input, it means the connection probability that a part of speech sequence t ₁ , t ₂ ,..., t _N is given, and the right side of the above equation 8 indicates the input sentence w ₁ , w ₂ , w ₃ ,. w _n , and i given a part-of-speech sequence t ₁ , t ₂ ,..., t _i-1 up to the (i−1) th word
This means the probability obtained by multiplying the probability of the part of speech by i from 1 to n. Here, the symbol of Π represents i as 2
From N to N. Then, using a context-dependent attribute, the leaf leaf of the decision tree
(L) is derived, the frequency probability distribution associated with L is represented by p _L , and approximated as follows using the conditional distribution of the decision tree.

[0067]

L _i ≡ context w ₁ , w ₂ ,..., W _N , t ₁ , t ₂ ,.
Leaf led at t _i-1

P (t _i | w ₁ , w ₂ ,..., W _N , t ₁ , t ₂ ,
..., t _i-1 ) ≒ p _Li (t _i )

The contexts w ₁ , w ₂ ,...
w _N , t ₁ , t ₂ ,..., t _i-1 mean the context of the i-th word w _i . Further, the left side of Expression 10 is the context w ₁ ,
_{w 2, ..., w N,} t 1, t 2, ..., next to the word t _i of t _i-1 represents the frequency probability or occurrence probability come, but it is the right-hand side of the number 10, in the context L _i This means that the probability of taking the part of speech t _i can be approximated. Therefore, the coupling probability P to be maximized is as follows.

[0069]

[Equation 11]

As is apparent from the above equation 11, the connection probability P is represented by the product of the probabilities of the parts of speech t _i obtained depending on the context of each word of the input sentence. Further, in the part of speech processing for each word of the input sentence, the following two-stage processing is performed. (A) Calculate the frequency probability of each part of speech of the GPOS. (B) Using the decision tree corresponding to each part of speech of the GPOS, the frequency probability of the part of speech is calculated.

In the calculation of the frequency probability of each word, it is necessary to consider all possible part-of-speech sequences obtained up to that time. When dealing with a fine part-of-speech system, the search range becomes enormous. Therefore, in this system, the related art document 6 “F. Jelinek,
“A fast sequential decodingalgorithm using a stac
k ", IBM Journal of Research and Development, No. 13, p
p.675-685, 1969 "and prior art document 7" D. Paul, "Alg
orithms for an optimal a * search and linearizing t
he search in the stack decoder ", Proceedingsof the
June 1990 DARPA Speech and Natural Language Work s
hop, 1990 ".
The part-of-speech sequence with the maximum frequency probability or appearance probability is searched for using an algorithm. This algorithm is a kind of graph search algorithm, in which the search range is temporarily limited by a threshold value, and the best evaluation value can be searched. In other words, selecting a part of speech sequence with the highest frequency probability from a plurality of parts of speech that may be given to each word is performed by using a graph that connects each part of speech as a node and nodes attached to adjacent words. The stack decoder algorithm treats a plurality of nodes collectively as a stack structure in a tree-structured path divided in a binary tree format, and searches the stack structure for the optimum path. By changing the range, an optimal route can be efficiently found.

Further, in the present embodiment, the part-of-speech system is extended, and one part of the sentence that is not written is divided into morphemes including the word, and the part-of-speech is added to each word as an input. For one sentence that is not divided by word division, a plurality of division methods can be considered. For example, there are 32 ways to divide "OK". For example, (a) "I understand" (b) "Wa / Kari" (c) "Waka / Rita" ... (d) "Wa / Ka / Ri / Ma / Shi / Ta") The input sentence is scanned one character at a time to form a possible word string and calculate the probability as a word. Assuming that the input sentence is “C1C2C3... Cn”, the probability of one character as a word is calculated when the character C1 is read. Next, when the character C2 is read, the probability of the state of two words and the state of one word with two characters of C1C2 are calculated using the character C2 as one character word. When the next character C3 is read, the state in which the character C3 is a one-character word and the state in which the character C3 is
2 and calculate the probability of a word state. Hereinafter, similarly, the probabilities in a plurality of states are calculated. However, if all the states are calculated, the amount of calculation becomes enormous, and the calculation cannot be performed. Therefore, the calculation is performed using the stack decoder algorithm.

The word probability of the word decision tree for obtaining the word probability is calculated by a decision tree using the following features. (A) Features of spelling (Specific examples are "composed of only katakana." And "the word" -shii. ")
Such. ), (B) the characteristics of the following character (specifically, "the following character is a kanji.", "The subsequent character is" wa ", etc.), and (c) the characteristic of the part of speech that leads to the previous character. (Particularly, the immediately preceding part of speech is not limited.) (Specific examples include "the immediately preceding part of speech is a noun.", "The immediately preceding part of speech is a punctuation mark."
"The previous part of speech is a particle." And (d) Hierarchical classification using mutual information of words. Using these characteristics, the probability that a certain character string is a word is learned from the learning data. To get word probabilities,
For example, in “payment / how / how”, a word division decision tree is constructed by considering a combination of a character string and a word / non-word as follows.

[0074]

[Table 7] 非 Support Nonword Payment Nonword Payment Word is Word Payment is Nonword Which is Nonword Payment Which non-word is which non-word Which payment is non-word ──────────────────────────

FIG. 2 is a flowchart showing a part-of-speech decision tree learning process executed by the decision tree learning device 10 of FIG. In FIG. 2, first, text data composed of syntax-analyzed (part-of-speech-added) sentence with syntax information stored in the syntax-analyzed text data memory 21 is read out in step S 1, and read into the RAM in the decision tree learning device 10. Write. Next, in step S2, the frequency probabilities of the combination of each attribute and the part-of-speech tag (the above p (tagall),
This corresponds to p (tagN ₁ ) and p (tagN ₂ ). ) Is calculated and written in the RAM in the decision tree learning device 10. Further, a part-of-speech decision tree with frequency probability is generated by executing a decision tree creation process in step S3, and the part-of-speech decision tree with probability created in step S4 is output to the memory 24 and stored.

FIG. 3 shows a grammar rule decision tree learning process (step S11) executed by the decision tree learning device 10 of FIG.
3 is a flowchart showing (S14), which is executed similarly to the part-of-speech decision tree learning process of FIG. FIG. 4 is a flowchart showing the processing direction decision tree learning process (steps S21 to S24) executed by the decision tree learning device 10 of FIG. 1, and is executed in the same manner as the part of speech decision tree learning process of FIG. FIG. 5 is a flowchart of the word division decision tree learning process (step S26-) executed by the decision tree learning device 10 of FIG.
3 is a flowchart showing S29), which is executed similarly to the part-of-speech decision tree learning process of FIG. Here, the processing direction is a direction to be processed in each purging state in the grammar rule providing process, and limits how to change a processing target within a range to which the grammar rule is provided. Here, the parsing state refers to a state in which the parsing information is partially analyzed by the syntax information providing apparatus 11 as shown in FIG. 16, and information on a node or a word to be currently processed (specifically, A word, its part of speech information, and which one is to be processed). The goal state is a state in which the final result of parsing is input, and is a parsing state united by a grammar rule that combines one sentence as a sentence.

FIG. 6 shows a decision tree creation process (steps S3, S13, S23, S23) which is a subroutine of FIGS.
It is a flowchart which shows 28). First, step S
31 is the entropy H after division by all the attributes
And the entropy H ₀ before division are given by Equations 4 and 3, respectively.
Calculate using Next, in step S32, the attribute having the largest entropy difference (H ₀ −H) is selected as the attribute of the division candidate, and it is determined whether or not the attribute selected in step S33 satisfies the division continuation determination criterion. Here, the division continuation determination criterion is defined as (I) a difference (H ₀ −H) in entropy at the time of division based on the selected attribute is equal to or greater than a predetermined entropy threshold Hth, and (II) The number of events after division based on the attribute set is not less than a predetermined event number threshold Dth. If the division continuation determination criterion is satisfied in step S33, in step S34 the division is performed based on the attribute value of the selected attribute.
One node is created, that is, divided in the form of a binary tree to update the decision tree. Then, in step S35,
Each of the created nodes is set as a processing target, and step S3
1 and the processing from step S31 is repeated. On the other hand, if the division continuation criterion is not satisfied in step S33, the process returns to the original main routine.

An example of the part-of-speech decision tree, the grammar rule decision tree, and the processing direction decision tree created in these decision tree learning processes will be described. Here, when "payment is performed by card" is used as the text data to be input, "[noun phrase 1 payment_ordinary noun is replaced with _case particle" ]
[Noun phrase 1 card_ordinary noun_case particle]] is output.

FIG. 12 shows an example of the created word division decision tree with frequency probability. As shown in FIG. 12, the word decision tree with frequency probability has attributes 101 to 105
Has a tree structure divided in the form of a binary tree, and a word category, that is, a frequency probability for a distinction between a word and a non-word is given to the last leaf. In this example, when the input sentence is “payment / a / card / with”, 201
As shown in (2), the word “payment” is given a word category “word”, and as shown in 203, the word “card” is given a word category “word”.

FIG. 13 shows an example of a part-of-speech decision tree with frequency probability that has been created. As shown in FIG. 13, the part-of-speech decision tree with frequency probabilities has a tree structure divided in the form of a binary tree by each of the attributes 301 to 305, and a word category, that is, a word / non-word Is given a frequency probability. In this example, when the input sentence is “payment / a / card / in”, the word “payment” is given a part-of-speech category “noun” as shown at 401, while as shown at 403. In addition, "noun" of the part of speech category is given to the word "card".

FIG. 14 shows an example of the grammar rule decision tree with frequency probability created in the above example. As shown in FIG. 14, the grammar rule decision tree with frequency probabilities
Has a tree structure divided in the form of a binary tree by
In the last leaf, the frequency probability for each grammar rule tag is given. In this example, the input sentence is "payment /
When "is", a grammatical tag noun phrase (meaning a noun phrase composed of a noun and a case particle) is given at the leaf node.

FIG. 15 shows an example of a processing direction decision tree with frequency probability created in the above example. As shown in FIG. 15, the processing direction decision tree with the frequency probability has the attribute 501
Has a tree structure divided in the form of a binary tree by
In the last leaf, a frequency probability for each processing direction tag is given. In this example, when the input sentence is "payment / for / card / in", at the leaf node,
The processing direction tag "right" is added and the processing target "payment"
Is added to the right of "", and a new processing object "payment /" is added. Also, "" is added to the right of the processing object "card", and a new processing object "card /" is added. so"
Is performed, and the processing of the grammar assignment decision tree is continued.

FIG. 7 is a flowchart showing the syntax information adding process executed by the syntax information adding device 11 of FIG. In FIG. 7, first, in step S41, the part-of-speech decision tree file with frequency probability stored in the probable part-of-speech decision tree file memory 25 is read out and written to the RAM in the syntax information providing apparatus 11, and the grammatical rule decision tree with probability is read out. The grammar rule decision tree file with frequency probability stored in the file memory 26 is read out, and the syntax information
And reads the processing direction decision tree file with frequency probability stored in the processing direction decision tree file memory with probability 27 into the RAM in the syntax information providing device 11.
M, and reads out the word-segmented decision tree file with frequency probability stored in the word-segmented decision tree file memory with probabilities 28 and writes it into the RAM in the syntax information providing device 11. Next, in step S42, the text data to be analyzed stored in the text data memory 30 is read and written to the RAM in the syntax information providing device 11. Further, in step S43, word division and part-of-speech assignment processing, which will be described in detail later, is executed to generate word-segmented part-of-speech text data, and then in step S44, the part-of-speech-assigned text data generated in step S43 By executing a grammar rule assignment process for assigning a grammar rule tag to the grammar rule, parsed text data is generated. Then, the parsed text data generated in step S45 is output to the parsed text data memory 31 and written.

FIGS. 8 and 9 are flowcharts showing the word division and part of speech processing (step S43), which are subroutines of FIG. In FIG. 8, first, in step S51, the character at the beginning of the sentence is set as a target character. Next, in step S52, word candidates are set from the target characters,
At 53, the root node of the word decision tree is set as the current node to be processed. Then, in step S54, it is determined whether the current node is a leaf node. If “NO” in the step S54, the child node is set as a current node based on the attribute value of the current node in a step S55, and the process returns to the step S54. When YES is determined in the step S54, the frequency probability of the word category is selected from the frequency probability list assigned to the leaf node in the step S56 and given to the word candidate.

Next, in step S57, the root node of the part of speech decision tree is set as the current node to be processed. Then, in step S58, it is determined whether the current node is a leaf node. If NO in step S58, the process returns to step S58 with the corresponding child node as the current node based on the attribute value of the current node in step S59. When YES is determined in the step S58, the frequency probability of the part of speech category is selected from the frequency probability list assigned to the leaf node in the step S60 and given to the word candidate. Then, it is determined whether or not there is another word candidate in step S61 of FIG. Step S6
If there is another word candidate in step 1, the process returns to step S52,
The above process is repeated. When NO is determined in the step S61, in a step S62, word-segmented candidates having a joint probability equal to or higher than a predetermined joint probability are limited according to a stack decoder algorithm. Then, it is determined in step S63 whether the next character exists. If there is a next character in step S63, the process returns to step S52 with the next character as a target character in step S64, and repeats the above processing. On the other hand, if there is no next character in step S63, the uppermost n pieces of the combination probabilities in the combination sequence of the word and the part of speech divided in word in step S65 are output as processing candidates. Here, as a specific example of a combination sequence of words and parts of speech, “payment (noun) is (case particle) by card (noun) (case particle)” is as shown. This is the end of the word and part of speech assignment analysis processing.

FIGS. 10 and 11 are flowcharts showing the grammar rule assignment process (step S44), which is a subroutine of FIG. First, in step S70 of FIG. 10, the highest one of the top n processing candidates after the word division and part of speech processing is set as the processing target. Next, in step S71,
Generate a parsing state for the first word of the sentence. Next, in step S72, the stack memory 1 determined by the number of processing direction determinations and the number of grammar rule determinations
The purging state generated immediately before is added to the stack in 2. The determined stack means a data structure for recording each purging state. Then, in step S73, the purging state having the maximum connection probability is selected according to the above-described stack decoder algorithm, and in step S64, the processing direction is determined using the processing direction determination tree. Here, when the processing direction is “right”, a purging state in which the next word is to be processed is generated in step S77 via YES in step S75, and the process returns to step S72. If the processing direction is “up” in step S74, steps S75 and S7
6, a purging state is generated in step S78 by adding a grammar rule tag to the processing target node according to the grammar rule decision tree, and then the process proceeds to step S81 in FIG. Here, the processing direction “up” means that processing is performed on the current processing target in step S78 according to the grammar rule decision tree. Further, when the processing direction is "left" in step S74, the parsing in which the range of the node to be processed is extended to the left in step S79 through steps S75 and S76 and a grammar rule tag is added according to the grammar rule decision tree. After generating the state, the process proceeds to step S81 in FIG.

In step S81 of FIG. 11, it is determined whether there is a word that has not been processed. If YES, the process returns to step S72 in FIG. 10, while if NO, the grammar rule is set to one in step S82. It is determined whether the sentence is established as a sentence. If NO, the process proceeds to step S85 in FIG.
On the other hand, when YES is determined, the process proceeds to step S83. In step S83, the current purging state is added to the goal state. In step S84, a predetermined number of predetermined purging states (for example, N when obtaining the top N results) are defined as the goal state. It is determined whether or not
If NO, the process returns to step S72 in FIG. 10, while YES
In this case, the grammar rule assignment process ends, and the process returns to the original main routine.

In the above embodiment, the learning text data that has been parsed by one predetermined grammar rule system is used. However, the present invention is not limited to this. When there is a certain amount of text data obtained, information of another grammar rule system G1 may be used. At this time, the accuracy of syntax analysis can be improved. Here, the grammar rule system to be used is G0. In order to use the information of the grammar rule system G1, a part of the text analyzed by the grammar rule system G1 and a text analyzed by the grammar rule system G0 are created. Grammar rules G0 and G1
Using the same text data analyzed on both sides, a decision tree in which the characteristics of the grammar rule system G1 are reflected in the attributes to be used is learned. By inputting the text analyzed by the grammar rule system G1 using the decision tree reflecting the grammatical features of the grammar rule system G1, analysis using abundant input information becomes possible, and the accuracy of the syntax analysis is improved. Can be improved.

Next, a modification of the embodiment will be described. FIG. 17 is a flowchart showing syntax information addition processing (corresponding to FIG. 7 of the embodiment) executed by the syntax information addition apparatus 11 of the modification, and FIG. FIG. 17 is a flowchart illustrating an example of a purging state and a processing direction during processing (corresponding to FIG. 16 of the embodiment). In the processing of the embodiment described so far, a procedure is shown in which word division and part-of-speech assignment are performed once for one sentence, and grammar information is assigned to the result. As described above, there are several possible order relationships among word division, part of speech assignment, and grammatical rule assignment. In this modified example, when one word is recognized in word division, a part of speech is assigned and a grammar rule is assigned, and the process proceeds.

That is, in the modified example, as shown in FIG. 17, when one word is recognized by word division in steps S43 and S44, the part of speech and grammatical rule are assigned to the word. It is characterized in that the processing is performed for each word up to the end of the sentence by the loop processing from S46 to steps S43 and S44. That is, in the word division and part-of-speech processing in step S43 of the modification, a combination sequence (one set) of the highest word and part-of-speech after the word division and part-of-speech addition processing is output, and based on this, a grammar rule assignment is performed in step S44. The process is executed to give syntactic analysis information (grammar rules), and the processes of steps S43 and S44 are executed for the subsequent words until the end of the sentence. As a result, the entire input Japanese sentence is processed.

More specifically, in step S43, based on the text data consisting of the input Japanese word string, the word division decision tree with frequency probability of the generated word category is used. From the frequency probabilities of the word categories assigned to the leaf nodes of the tree, the top n frequency probabilities are selected and assigned to each word candidate of the text data, and the text consisting of the input word string is selected. Based on the data, using the generated part-of-speech decision tree with frequency probabilities of the generated part-of-speech categories, select the top n multiple frequency probabilities among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech decision tree Then, the top word candidate is assigned to each word candidate from the head word candidate of the text data, and the topmost connection probability in the word string of the text data is added. A row of combinations of word split word and part of speech having outputs as processing candidate. Next, in step S44, the parsing state having the largest joint probability with respect to the word string in each purging state in the grammar rule assigning process is performed on the output process candidate using a predetermined stack decoder algorithm. Is selected, and the processing direction in the word string to be processed is determined using the generated processing direction decision tree with frequency probability. In the parsing state in the determined processing direction, the generated grammar with frequency probability is determined. By adding a grammar rule to the word string to be processed according to the rule decision tree, syntactic analysis information is added and a syntactically analyzed word is output. Then, as shown in FIG.
Steps S43 and S44 are repeated by step S46 so as to repeat one word candidate at a time from the beginning of the text data consisting of the input word string until the parsed text data for one sentence of the text data is obtained. Control.

In the processing of step S43, it is preferable to select a plurality of top n frequency probabilities from among the frequency probabilities of the word categories assigned to the leaf nodes of the word division decision tree, and to select the word probabilities of the text data. Assigned to a candidate, and selects a plurality of n higher-order frequency probabilities among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech assignment decision tree and assigns them to each word candidate of the text data After that, using a predetermined stack decoder algorithm, leaving only the processing candidates of the combination row of words and parts of speech with the combination probability of the word string of the text data being processed being equal to or greater than the predetermined combination probability, The candidates are limited, and the word-segmented word having the highest combination probability in the word string of the text data at the end of the process and the part of speech The columns of the match only, and outputs it as a treatment candidate.

In this modified example, in FIG. 18, as compared with FIG. 16 of the embodiment, as shown in PS7 and PS27, grammatical rules applicable during the analysis are appropriately added, so that the analysis Is characterized by being able to narrow down.

As described above, the order of executing the word division, the part-of-speech assignment, and the grammatical rule assignment may be in several ways. Is given, a word or a part-of-speech sequence that is established as a word but not as a sentence may appear as an analysis candidate. Such candidates are narrowed down by the information of the grammar rule and cannot be final analysis candidates. This candidate can be excluded from analysis candidates by applying grammatical rules when a sequence of words or parts of speech that do not hold as a sentence appears as an analysis candidate, and more likely words and parts of speech can be used as candidates. Can be left.
Therefore, as in the modification, when one word is recognized in word division, part-of-speech assignment and grammatical rule assignment are performed, and by proceeding with the processing, analysis candidates that cannot be narrowed down using only the word division information are analyzed. With the information of the connection and the grammar rule, it is possible to narrow down in the middle of each process, and it is possible to improve the efficiency and accuracy.

As described above, according to the present embodiment and the modification, the connection relation between parts of speech, the relation between words and parts of speech, and the dependency between distant words or parts of speech are statistically processed. It is possible to provide a part-of-speech with unique and high precision and grammar rules with high precision, and to provide a high-precision Japanese syntax analysis system. In addition, since a part of speech label is assigned to a word without using a dictionary, a special process for an unknown word, which is a problem of the related art, is unnecessary. Further, since learning is performed using the parsed text data, it is possible to flexibly cope with many grammar systems. Furthermore, since detailed syntax information can be automatically added, the added syntax information can be used for a translation system, a speech recognition system, or an information search system. Further, since data with syntax structure including detailed information can be automatically generated, a large amount of data with syntax information can be stored.

[0096]

As described in detail above, according to the Japanese language parsing apparatus according to the first aspect of the present invention, the spelling of each word is performed based on the parsed text data composed of Japanese character strings. Using multiple attributes including features, features based on how they are used in the text, and hierarchical classification using mutual information of words, the attribute is divided depending on the attribute value of each attribute. Generates a part-of-speech decision tree having a tree structure in the form of a binary tree, and calculates and assigns frequency probabilities for a plurality of parts-of-speech to leaf nodes that are undivided nodes of the generated part of speech decision tree. The first learning means for generating a part-of-speech decision tree with frequency probabilities of the part-of-speech category, based on the text data, the spelling characteristics of each word, the characteristics of the succeeding characters, and the part-of-speech Features and word phases Word segmentation for word segmentation using a plurality of attributes including hierarchical classification using the amount of information and having a tree structure in a binary tree format such that segmentation is performed depending on the attribute value of each attribute. By generating a decision tree and calculating and assigning frequency probabilities for words and non-words to leaf nodes, which are nodes that are not split, on the generated word segmentation decision tree, word segmentation with frequency probabilities of word categories is determined. A second learning unit for generating a tree, based on the text data, uses the number of words to be processed, the part of speech of the subject word to be processed, the part of speech of the word immediately before the processing object, and the mutual information of the words. A grammar rule decision tree for assigning a grammar rule, having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute using a plurality of attributes including Generate and generated above A third learning means for generating a grammar rule decision tree with a frequency probability by calculating and assigning frequency probabilities for a plurality of grammar rules to a leaf node which is a node which is not divided by the legal rule decision tree; Based on the data, using multiple attributes including the number of words to be processed, the part of speech of the subject head word to be processed, the part of speech of the word immediately before the processing object, and hierarchical classification using mutual information of words Generating a processing direction determination tree for determining a processing direction in each parsing state in a grammar rule assignment process having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute, By generating and assigning frequency probabilities for a plurality of processing directions to leaf nodes that are nodes that are not divided, the processing direction decision tree with frequency probabilities is generated. Using the fourth learning means to form and the word division decision tree with frequency probability of the word category generated by the second learning means based on the text data consisting of the input Japanese character string, From the frequency probabilities of the word categories assigned to the leaf nodes of the word segmentation decision tree, the top n number of frequency probabilities are selected and assigned to each word candidate of the text data, and the input character string Using the part-of-speech decision tree with frequency probabilities of the part-of-speech categories generated by the first learning means based on the text data consisting of The top n frequency probabilities are selected and assigned to each word candidate in the text data, and the top plural n A first processing unit that outputs a sequence of combinations of words and parts of speech that have been divided into words having a joint probability of n as a plurality of n processing candidates, and a plurality of n processing candidates output from the first processing unit. Of the parsing states in each parsing state in the grammar rule assignment processing using a predetermined stack decoder algorithm until one sentence is sequentially established for each processing candidate in order from the higher processing candidate. After selecting the purging state in which the connection probability with respect to has the maximum connection probability, the processing direction in the word string to be processed is determined using the processing direction decision tree with frequency probability generated by the fourth learning means, In the parsing state in the determined processing direction, the grammar rule is raised according to the grammar rule decision tree with frequency probability generated by the third learning means. By adding the word string to be processed by applying a parsing information and a second processing means for outputting the parsed text data. Therefore, since the connection relation between parts of speech, the relation between words and parts of speech, and the dependency between distant words or parts of speech are statistically processed, parts of speech can be automatically and uniquely assigned with high precision, and the grammar with high precision Rules can be given, and a high-precision Japanese syntax analyzer can be provided. In addition, since a part of speech label is assigned to a word without using a dictionary, a special process for an unknown word, which is a problem of the related art, is unnecessary. Further, since learning is performed using the parsed text data, it is possible to flexibly cope with many grammar systems. Furthermore, since detailed syntax information can be automatically added, the added syntax information can be used for a translation system, a speech recognition system, or an information search system. Further, since data with syntax structure including detailed information can be automatically generated, a large amount of data with syntax information can be stored.

According to the Japanese syntax analyzer of the second aspect, in the Japanese syntax analyzer of the first aspect, each of the decision tree learning means is configured to divide the binary tree in the form of the binary tree. The attribute having the largest difference (H ₀ −H) between the entropy H ₀ indicating the priority of the validity of the attribute before the division by each attribute and the entropy H after the division is selected as the attribute of the division candidate, and the predetermined division is performed. When the continuation criterion is satisfied, the decision tree is divided and updated in the form of a binary tree. Therefore, the learning process of each decision tree can be executed more efficiently than the conventional example.

Further, according to the Japanese syntax analyzer of the third aspect, in the Japanese syntax analyzer of the second aspect, the division continuation criterion may be such that (I) the division based on the selected attribute Is greater than or equal to a predetermined entropy threshold Hth, and (I ₀ −H)
I) The number of events of a set of the attribute after division based on the selected attribute, the attribute value thereof, and the part of speech is equal to or more than a predetermined event number threshold value Dth. Therefore, the above-described learning process of each decision tree can be executed more efficiently than the conventional example, and the processing cost can be reduced.

According to a fourth aspect of the present invention, in the first aspect, the first processing means may include:
Selecting the top n frequency probabilities from among the frequency probabilities of the word categories assigned to the leaf nodes of the word segmentation decision tree and assigning them to each word candidate of the text data; After selecting n top frequency probabilities among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes and assigning them to each word candidate of the text data, the n is used for a predetermined stack decoder algorithm. In addition, only the processing candidates of a row of a combination of a word and a part-of-speech in which the combination probability of the text data being processed with the word candidate string is equal to or greater than a predetermined combination probability are limited, and the candidates of the combination are limited. In the character string of the data, a sequence of the word-speech combination obtained by dividing the word having a plurality of upper n combining probabilities is output as a plurality of n processing candidates. To. Therefore, the processing of the first processing means can be executed more efficiently than in the conventional example, and the processing cost can be reduced.

According to the Japanese parsing apparatus according to the fifth aspect of the present invention, based on the parsed text data composed of Japanese character strings, the spelling characteristics of each word and the spelling characteristics of each word are used. Using a plurality of attributes including the characteristics of each of them and a hierarchical classification using the mutual information of words, and has a tree structure in a binary tree format that is divided depending on the attribute value of each of the above attributes. By generating a part-of-speech decision tree for giving part-of-speech and calculating and adding frequency probabilities for a plurality of parts-of-speech to leaf nodes which are nodes that are not divided, the frequency of the part-of-speech category is generated. First learning means for generating a part-of-speech decision tree with probability, based on the text data, the spelling characteristics of each word, the characteristics of the succeeding characters, the characteristics of the part of speech connected before, and the mutual information of the words Hierarchy using Using a plurality of attributes including a classification, a word division decision tree for word division having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute, A second method of generating a word division decision tree with frequency probabilities of word categories by calculating and adding frequency probabilities for words and non-words to leaf nodes that are non-divided nodes of the generated word division decision tree. Based on the learning means, based on the text data, the number of words to be processed, the part of speech of the subject head word to be processed, the part of speech of the word immediately before the processing object, and the hierarchical classification using the mutual information of the words. Using a plurality of attributes including, generating a grammar rule decision tree for a grammar rule assignment having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute,
A third learning means for generating a grammar rule decision tree with a frequency probability by calculating and assigning frequency probabilities for a plurality of grammar rules to leaf nodes which are nodes that are not divided, the generated grammar rule decision tree. And a hierarchical classification using the number of words of the processing target, the part of speech of the subject head word to be processed, the part of speech of the word immediately before the processing target, and the mutual information of the words based on the text data. And a processing direction determining tree for determining a processing direction in each parsing state in the grammar rule assigning process using a tree structure of a binary tree format that is divided depending on the attribute value of each attribute using the attribute Is generated, and frequency probabilities for a plurality of processing directions are calculated and assigned to leaf nodes, which are nodes that are not divided, in the generated processing direction decision tree, thereby providing a process with a frequency probability. A fourth learning means for generating a direction decision tree, and a word division decision tree with frequency probability of the word category generated by the second learning means, based on text data consisting of an input Japanese character string. And using the word probabilities of the word categories assigned to the leaf nodes of the word segmentation decision tree to select and assign n higher-order n frequency probabilities to each word candidate of the text data, The frequency of the part-of-speech category assigned to the leaf node of the part-of-speech decision tree using the part-of-speech decision tree with the frequency probability of the part-of-speech category generated by the first learning means based on the text data composed of the character string From among the probabilities, the n top frequency probabilities are selected and assigned to each word candidate from the head word candidate of the text data, and Processing means for outputting, as processing candidates, a sequence of combinations of words and parts of speech having the highest combination probability in the word candidate sequence of the data, and processing candidates output from the first processing means. Then, using a predetermined stack decoder algorithm, after selecting a purging state in which the connection probability with respect to the word string in each purging state in the grammar rule assignment processing has the maximum connection probability, the fourth learning means The processing direction in the word string to be processed is determined using the processing direction decision tree with the frequency probability generated by the above, and in the parsing state in the determined processing direction, the frequency with the frequency probability generated by the third learning means is determined. Parsing by adding parsing information by adding a grammar rule to the above word string to be processed according to a grammar rule decision tree The second processing means for outputting the completed word, and the processing of the first and second processing means are performed by executing one sentence of the text data by one word candidate from the beginning of the text data consisting of the input character string. And a third processing unit for controlling the repetition until the parsed text data is obtained. Therefore, since the part-of-speech connection relation, the relation between words and part-of-speech, and the dependency relation between distant words or parts of speech are statistically processed, parts of speech can be automatically and uniquely assigned with high precision, and grammar with high precision Rules can be granted,
A high-precision Japanese syntax analyzer can be provided.
In addition, since a part of speech label is assigned to a word without using a dictionary, a special process for an unknown word, which is a problem of the related art, is unnecessary. Furthermore, since the learning is performed using the parsed text data to which the parts of speech are added, it is possible to flexibly cope with many parts of speech systems. Furthermore, since detailed syntax information can be automatically added, the added syntax information can be used for a translation system, a speech recognition system, or an information search system. Further, since data with syntax structure including detailed information can be automatically generated, a large amount of data with syntax information can be stored. Furthermore, as compared with the Japanese parsing apparatus according to claim 1, each of the above processes can be executed more efficiently than in the conventional example, processing costs can be reduced, and parsing can be performed with high accuracy. it can.

According to the Japanese syntax analyzer of the sixth aspect, in the Japanese syntax analyzer of the fifth aspect, each of the decision tree learning means is configured to divide the binary tree in the form of the binary tree. The attribute having the largest difference (H ₀ −H) between the entropy H ₀ indicating the priority of the validity of the attribute before the division by each attribute and the entropy H after the division is selected as the attribute of the division candidate, and the predetermined division is performed. When the continuation criterion is satisfied, the decision tree is updated by dividing in the form of a binary tree. Therefore, the learning process of each decision tree can be executed more efficiently than in the conventional example, and the processing cost can be reduced.

Further, according to the Japanese syntax analyzer of the seventh aspect, in the Japanese syntax analyzer of the sixth aspect, the division continuation criterion is determined when (I) the division is performed based on the selected attribute. Is greater than or equal to a predetermined entropy threshold Hth, and (I ₀ −H)
I) The number of events of a set of the attribute after division based on the selected attribute, the attribute value thereof, and the part of speech is equal to or more than a predetermined event number threshold value Dth. Therefore, the learning process of each decision tree can be executed more efficiently than in the conventional example, and the processing cost can be reduced.

According to still another aspect of the present invention, in the Japanese language parsing apparatus according to any one of claims 5 to 7, the first processing means may include:
From the frequency probabilities of the word categories assigned to the leaf nodes of the word segmentation decision tree, select the n top frequency probabilities and assign them to the word candidates of the text data,
In addition, after selecting a plurality of n higher-order frequency probabilities from among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech assignment decision tree and assigning them to each word candidate of the text data, a predetermined stack Using the decoder algorithm, the candidate of the combination of the word and the part of speech having the combination probability of the text data being processed that is equal to or greater than the predetermined combination probability is limited to the candidates of the combination. At the end of the process, a sequence of a word-speech combination having the highest combination probability in the character string of the text data is output as a process candidate. Therefore, the processing of the first processing means can be executed more efficiently than in the conventional example, and the processing cost can be reduced.

[Brief description of the drawings]

FIG. 1 is a block diagram of a Japanese syntax analysis system including a decision tree learning device 10 and a syntax information providing device 11 according to an embodiment of the present invention.

FIG. 2 is a flowchart showing a part-of-speech decision tree learning process executed by the decision tree learning device 10 of FIG.

FIG. 3 is a flowchart showing a grammar rule decision tree learning process executed by the decision tree learning device 10 of FIG. 1;

FIG. 4 is a flowchart showing processing direction decision tree learning processing executed by the decision tree learning device 10 of FIG. 1;

FIG. 5 is a flowchart showing a word division decision tree learning process executed by the decision tree learning device 10 of FIG. 1;

FIG. 6 is a flowchart showing a decision tree creation process (steps S3, S13, S23, S28) which is a subroutine of FIGS. 2 to 5;

FIG. 7 is a flowchart showing a syntax information providing process executed by the syntax information providing apparatus 11 of FIG. 1;

8 is a flowchart showing a first part of the word division and part of speech processing (step S43), which is a subroutine of FIG.

9 is a flowchart showing a second part of the word division and part of speech processing (step S43), which is a subroutine of FIG.

FIG. 10 is a flowchart showing a first part of a grammar rule assignment process (step S44), which is a subroutine of FIG.

FIG. 11 is a flowchart showing a second part of the grammar rule assignment process (step S44), which is a subroutine of FIG.

12 is a diagram showing an example of a word division decision tree in a word division decision tree file memory 28 created by the decision tree learning device 10 of FIG.

FIG. 13 is a diagram showing an example of a part of speech decision tree in a part of speech decision tree file memory 25 created by the decision tree learning device 10 of FIG.

14 is a diagram showing an example of a grammar rule decision tree in a grammar rule decision tree file memory 26 created by the decision tree learning device 10 of FIG.

FIG. 15 is a diagram showing an example of a processing direction decision tree in a processing method decision tree file memory 27 created by the decision tree learning device 10 of FIG.

FIG. 16 is a flowchart showing an example of a parsing state and a processing direction during processing in the syntax information providing apparatus 11 of FIG. 1;

FIG. 17 is a flowchart showing a syntax information adding process executed by a syntax information adding device 11 of a modified example.

FIG. 18 is a flowchart illustrating an example of a parsing state and a processing direction during processing in a syntax information providing apparatus 11 according to a modified example.

[Explanation of symbols]

 10: Decision tree learning device, 11: Syntax information adding device, 21: Parsed text data memory, 22: Attribute list memory, 23: Part of speech list memory, 24: Grammar rule list memory, 25: Part of speech decision tree file memory, 26: grammar rule decision tree file memory, 27: processing direction decision tree file memory, 28: word division decision tree file memory, 29: word list memory, 30: text data memory, 31: parsed text data memory.

──────────────────────────────────────────────────続 き Continued on the front page (56) References David M. See Magerman, "Learning Grammatic Structure Using Statistical Decision-Trees", Lecture Notes in Artificial Intelligence 1147, p. 1-p. 21 (1996) Hidenori Kashioka, Ezra W. Black, Stephen G .; Eubank, "Morphological Analysis by Decision Tree Learning", SIG-SL UD-9603-4, p. 19-p. 24 (1996) (58) Fields surveyed (Int. Cl. ⁷ , DB name) G06F 17/20-17/28 JICST file (JOIS)

Claims (8)

(57) [Claims] Based on parsed text data composed of Japanese character strings, a hierarchical spelling using the spelling characteristics of each word, the characteristics according to the usage in a sentence, and the mutual information of the words. Using a plurality of attributes including a classification, a part-of-speech decision tree for giving a part-of-speech having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute, First learning means for generating a part-of-speech decision tree with a frequency probability of a part-of-speech category by calculating and assigning frequency probabilities for a plurality of parts of speech to a leaf node which is an undivided node of the part-of-speech decision tree; Based on text data, using multiple attributes including spelling characteristics of each word, characteristics of subsequent characters, characteristics of preceding part of speech, and hierarchical classification using mutual information of words , Attributes of each of the above attributes Generates a word-segmented decision tree for word segmentation having a tree structure of a binary tree form that is segmented depending on A second learning unit that calculates and assigns the frequency probabilities for words and non-words to generate a word segmentation decision tree with frequency probabilities of the word categories, based on the text data, Using a plurality of attributes including the part of speech of the subject word to be processed, the part of speech of the word immediately before the processing object, and hierarchical classification using mutual information of words, A grammar rule decision tree for generating a grammar rule having a tree structure in a binary tree format that can be divided is generated. Regulations A third learning means for generating a grammar rule decision tree with a frequency probability by calculating and assigning a frequency probability to the word, and a word number of a word to be processed and a head word of a subject word to be processed based on the text data. A binary tree that is divided depending on the attribute value of each of the above attributes using a plurality of attributes including a part of speech, a part of speech of a word immediately before processing, and a hierarchical classification using mutual information of words. A processing direction decision tree for determining a processing direction in each parsing state in a grammar rule assignment process having a tree structure of a form is generated, and a leaf node which is an undivided node of the generated processing direction decision tree is generated. Fourth learning means for generating a processing direction decision tree with frequency probabilities by calculating and adding frequency probabilities for a plurality of processing directions, and text data comprising an input Japanese character string Using the word division decision tree with frequency probabilities of the word categories generated by the second learning means, based on the frequency probabilities of the word categories assigned to the leaf nodes of the word division decision tree. Of the part-of-speech categories generated by the first learning means based on the text data consisting of the input character string, while selecting the frequency probabilities for each word candidate of the text data. Using the part-of-speech decision tree with probabilities, the frequency probabilities of the top plural n among the part-of-speech categories assigned to the leaf nodes of the part-of-speech tree are selected and assigned to each word candidate of the text data. Then, in the word candidate sequence of the text data, a sequence of a combination of a word and a part of speech having a plurality of n higher-order connection probabilities is represented by a plurality of n A first processing means for outputting as a processing candidate, and a plurality of n processing candidates output from the first processing means, one for each processing candidate sequentially from a higher processing candidate. Until the sentence is established, after using the predetermined stack decoder algorithm to select the purging state having the maximum connection probability for the word string in each purging state in the grammar rule assignment processing, The processing direction in the word string to be processed is determined using the processing direction decision tree with frequency probability generated by the learning means, and in the parsing state in the determined processing direction, the frequency generated by the third learning means is determined. According to the grammar rule decision tree with probabilities, the grammar rule is added to the above-mentioned word string to be processed, so that parsing information is added and parsing is performed. The second to output the text data
Japanese language parsing apparatus, comprising: Wherein each decision tree learning means, when splitting in the form of the binary tree, and the entropy H of the divided entropy H ₀ representing the priority of the effectiveness of the attributes before division by the respective attribute the difference (H ₀ -H) selects the greatest attribute as an attribute of the candidate dividing, when satisfying the predetermined division continue criterion, and updates the decision tree is divided in the form of a binary tree of The Japanese syntax analyzer according to claim 1. 3. The division continuation criterion includes: (I) a difference (H _{0) in} entropy at the time of division based on a selected attribute.
-H) is equal to or greater than a predetermined entropy threshold Hth, and (II) the number of events of the set of the attribute after division based on the selected attribute and its attribute value and part of speech is equal to or greater than a predetermined event number threshold Dth 3. The method according to claim 2, wherein
Japanese parser described. 4. The method according to claim 1, wherein the first processing means selects a plurality of top n frequency probabilities from among the frequency probabilities of the word categories assigned to the leaf nodes of the word division decision tree, and selects each word of the text data. Assigned to a candidate, and selects a plurality of n higher-order frequency probabilities among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech assignment decision tree and assigns them to each word candidate of the text data After that, using a predetermined stack decoder algorithm, leaving only the processing candidate of the word and part-of-speech combination row where the connection probability of the text data being processed to the word candidate string is equal to or higher than the predetermined connection probability And a combination of a word-segmented word and a part-of-speech word having a plurality of upper n combination probabilities in the character string of the text data at the end of the processing. Is output as a plurality of n processing candidates.
Japanese parser according to one of the above. 5. A hierarchical structure using spelling characteristics of each word, characteristics of usage in a sentence, and mutual information of words based on parsed text data composed of Japanese character strings. Using a plurality of attributes including a classification, a part-of-speech decision tree for giving a part-of-speech having a tree structure of a binary tree format that is divided depending on the attribute value of each attribute, A first learning means for calculating a frequency probability for a plurality of parts of speech to a leaf node which is a node which is not divided by the part of speech decision tree, and generating a part of speech tree with a frequency probability of a part of speech category; Based on text data, using multiple attributes including spelling characteristics of each word, characteristics of subsequent characters, characteristics of preceding part of speech, and hierarchical classification using mutual information of words , Attributes of each of the above attributes Generates a word-segmented decision tree for word segmentation having a tree structure of a binary tree form that is segmented depending on A second learning unit that calculates and assigns the frequency probabilities for words and non-words to generate a word segmentation decision tree with frequency probabilities of the word categories, based on the text data, Using a plurality of attributes including the part of speech of the subject word to be processed, the part of speech of the word immediately before the processing object, and hierarchical classification using mutual information of words, A grammar rule decision tree for generating a grammar rule having a tree structure in a binary tree format that can be divided is generated. Regulations A third learning means for generating a grammar rule decision tree with a frequency probability by calculating and assigning a frequency probability to the word, and a word number of a word to be processed and a head word of a subject word to be processed based on the text data. A binary tree that is divided depending on the attribute value of each of the above attributes using a plurality of attributes including a part of speech, a part of speech of a word immediately before processing, and a hierarchical classification using mutual information of words. A processing direction decision tree for determining a processing direction in each parsing state in a grammar rule assignment process having a tree structure of a form is generated, and a leaf node which is an undivided node of the generated processing direction decision tree is generated. Fourth learning means for generating a processing direction decision tree with frequency probabilities by calculating and adding frequency probabilities for a plurality of processing directions, and text data comprising an input Japanese character string And using the word category decision tree with frequency probabilities of the word categories generated by the second learning means on the basis of the frequency categories of the word categories assigned to the leaf nodes of the word category decision tree. Of the part-of-speech categories generated by the first learning means based on the text data consisting of the input character string, while selecting the frequency probabilities for each word candidate of the text data. Using the part-of-speech decision tree with probabilities, the frequency probabilities of the top plural n among the part-of-speech categories assigned to the leaf nodes of the part-of-speech decision tree are selected, and one by one from the top word candidates of the text data. Of word-segmented words having the highest combination probability in the word candidate string of the text data First outputting the columns of the allowed, as processing candidate
Processing means, and processing candidates output from the first processing means,
After using a predetermined stack decoder algorithm to select a purging state having a maximum connection probability for a word string in each purging state in the grammar rule assignment process, the purging state generated by the fourth learning means is selected. The processing direction in the word string to be processed is determined using the processing direction decision tree with frequency probability, and in the parsing state in the determined processing direction, the grammatical rule decision tree with frequency probability generated by the third learning means. Adding a grammar rule to the word string to be processed according to the above, giving syntactic analysis information and outputting a parsed word; and processing the first and second processing means by the input Parsed for one sentence of the above text data, one word candidate at a time from the beginning of the text data consisting of the character string And a third processing means for controlling so as to repeat until text data is obtained. 6. When the decision tree learning means divides in the form of the binary tree, the entropy H ₀ indicating the priority of the validity of the attribute before the division by the attribute and the entropy H after the division are used. the difference (H ₀ -H) selects the greatest attribute as an attribute of the candidate dividing, when satisfying the predetermined division continue criterion, and updates the decision tree is divided in the form of a binary tree of The Japanese syntax analyzer according to claim 5. 7. The division continuation criterion includes: (I) a difference (H _{0) in} entropy at the time of division based on a selected attribute.
-H) is greater than or equal to a predetermined entropy threshold Hth, and (II) the number of events of a set of attributes, their attribute values, and parts of speech based on the selected attribute is greater than or equal to a predetermined event number threshold Dth 7. The method according to claim 6, wherein
Japanese parser described. 8. The word processing apparatus according to claim 1, wherein the first processing means selects a plurality of n frequency probabilities among the frequency probabilities of the word categories assigned to the leaf nodes of the word division decision tree, and selects word candidates of the text data. And a plurality of upper n frequency probabilities are selected from among the frequency probabilities of the part-of-speech categories assigned to the leaf nodes of the part-of-speech assignment decision tree, and assigned to each word candidate of the text data. Then, using a predetermined stack decoder algorithm, leaving only the processing candidates of the word and part-of-speech combination row in which the connection probability of the text data being processed to the word candidate string is equal to or greater than the predetermined connection probability, Restrict candidates,
8. The method according to claim 5, wherein a sequence of a combination of a word and a word class having the highest combination probability in the character string of the text data at the end of the processing is output as a processing candidate. Japanese parser according to one.