JP3100556B2 - Part-of-speech device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a part-of-speech providing apparatus for automatically providing a part of speech to text data of a sentence including a character string.

[0002]

2. Description of the Related Art Conventionally, a relatively accurate part-of-speech assigning system (hereinafter referred to as a conventional example) has been disclosed in prior art document 1 “E.
ill et al., “Some Advances in Transformation--Base
d Partof Speech Tagging ", Proceedings of the Twelft
h National Conference on Artificial Intelligence, p
p.722-727, AAAI, 1994 "and prior art document 2" B. Meria
ldo et al., “Tagging English Text with a Probabili
stic 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.

[0003]

In the conventional part-of-speech assignment system, the part-of-speech is assigned using a dictionary. Therefore, it is difficult to assign a part-of-speech to an unknown word that is not described in a dictionary item. There is a problem that it is difficult to process an unknown combination with a part of speech label. further,
There was a problem that it was 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.

SUMMARY OF THE INVENTION An object of the present invention is to solve the above problems and to provide a part-of-speech assigning apparatus which can automatically and accurately assign a part-of-speech as compared with a conventional example without using a dictionary for assigning parts of speech. It is in.

[0005]

According to the present invention, there is provided a part-of-speech providing apparatus according to claim 1, wherein a spelling feature of each word, a feature according to a usage in a sentence, and a hierarchy using mutual information of words are used. A first storage device for storing an attribute list having a plurality of attributes including a general classification, a second storage device for storing a part-of-speech list including a plurality of part-of-speech, and a generated decision tree with frequency probability. A third storage device to be stored, and an attribute list stored in the first storage device and a part-of-speech list stored in the second storage device, based on the part-of-speech-attached text data composed of word strings. With reference to the above, a decision tree for giving a part-of-speech having a tree structure of a binary tree form that is divided depending on the attribute value of each attribute is generated, Multiple leaf classes for a leaf node Decision tree learning means for generating a decision tree with frequency probability by storing and adding the probability probability to the third storage device, and a decision tree with frequency probability stored in the third storage device With reference to the attribute list stored in the first storage device and the part-of-speech list stored in the second storage device, based on text data consisting of an input word string, From among the frequency probabilities assigned to the leaf nodes, n higher frequency probabilities are selected and assigned to each word of the text data,
A part-of-speech providing means for determining and outputting a part-of-speech sequence having the maximum connection probability in the word sequence of the text data as a correct part-of-speech sequence.

According to a second aspect of the present invention, in the part-of-speech providing apparatus according to the first aspect, when the decision tree learning unit performs the division in the binary tree format, Difference (H ₀ −H) between entropy H ₀ representing priority of attribute validity and entropy H after division
Is selected as an attribute of a candidate for division, and when a predetermined division continuation criterion is satisfied, the decision tree is updated by dividing in the form of a binary tree.

Further, the part-of-speech providing apparatus according to claim 3 is
3. The part-of-speech providing apparatus according to claim 2, wherein the division continuation criterion is that (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 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 Dth.

Further, the part-of-speech assigning device according to claim 4 is the part-of-speech assigning device according to claim 1, 2, or 3,
The part-of-speech assigning means selects the top n number of frequency probabilities among the frequency probabilities assigned to the leaf nodes and assigns them to each word of the text data. By using only the part-of-speech candidates whose connection probability to the word string of the text data being processed is equal to or more than the predetermined connection probability, the part-of-speech candidates are limited,
A part-of-speech sequence having the maximum connection probability in the word sequence of the text data at the end of the processing is determined as a correct part-of-speech sequence.

[0009]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram of a part-of-speech providing system including a decision tree learning device and a part-of-speech providing device according to an embodiment of the present invention. This part-of-speech assigning system is a part-of-speech assigning system that assigns parts of speech to English text data without referring to a dictionary for assigning parts of speech. Based on the text data that has been added, the attribute list stored in the attribute list memory 22 and the part-of-speech tag list stored in the part-of-speech tag list memory 23 are referred to to execute a decision tree learning process, which will be described in detail later, to perform learning. By doing so, the decision tree learning device 10 that generates a decision tree with frequency probability and stores it in the decision tree file memory 24 with probability and (b) the decision tree with frequency probability stored in the decision tree file memory 24 with probability. With reference to the attribute list stored in the attribute list memory 22 and the part of speech tag list stored in the part of speech tag list memory 23, The part-of-speech processing is performed on the text data stored and input in the data memory 25 to give the part-of-speech, thereby generating the part-of-speech-added text data and generating the part-of-speech-added text data. And a part-of-speech providing device 11 stored in the storage unit 26. In the present embodiment, the text data is an English sentence composed of an English word string.

[0010] Here, the decision tree learning device 10 determines the spelling characteristics of each word, the characteristics according to the usage in the sentence, and the mutual information amount of the words based on the part-of-speech-added text data composed of the word strings. Using a plurality of attributes including the hierarchical classification used, a 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 generating 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, a decision tree with a frequency probability is generated. Next, the part-of-speech providing apparatus 11 uses the decision tree with frequency probability generated by the decision tree apparatus 10,
Based on text data consisting of input word strings,
A part-of-speech sequence having the maximum combination probability in the word sequence of the text data, selecting the top plural n frequency probabilities from among the frequency probabilities assigned to the leaf nodes and assigning them to each word of the text data. Is determined as a correct part-of-speech sequence and output. Here, when the decision tree learning device 10 performs the division in the form of the binary tree, the difference 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 ( H ₀ -H) is selected as the attribute of the division candidate 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. The part-of-speech assigning device 11 selects a plurality of n higher-order frequency probabilities from the frequency probabilities assigned to the leaf nodes and assigns them to each word of the text data. The algorithm is used to limit the part-of-speech candidates, leaving only the part-of-speech candidates whose connection probability to the word string of the text data being processed is equal to or greater than the predetermined connection probability, and to maximize the connection in the word string of the text data at the end of the processing. A part-of-speech sequence having a probability is determined as a correct part-of-speech sequence.

In the present embodiment, a decision tree having a tree structure in a binary tree format and having a frequency probability for giving a part of speech is generated by a decision tree learning process using knowledge obtained from text data to which the part of speech is added. , Giving the part of speech. The attributes used in the 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 decision tree with frequency probability according to the present embodiment, a dictionary is not used to determine the part of speech of a word, so that the cost of creating and maintaining the dictionary does not matter. The decision tree with frequency probability is constructed by learning using the text with the part of speech. Therefore, if there is text data with the part of speech added, 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 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 attributes,
Hierarchical classification that uses the spelling characteristics of each word, the characteristics according to the usage in the sentence, and the mutual information amount of the words is used. Hereinafter, the part-of-speech providing system of the present embodiment will be described in detail.

In FIG. 1, a decision tree learning device 10 includes an attribute list stored in an attribute list memory 22 and a part-of-speech tag list memory 23 based on text data with a part of speech stored in a text memory 21 with a part of speech. With reference to the part-of-speech tag list stored in the decision tree learning process described later in detail, a decision tree with frequency probability is generated and stored in the decision tree file with probability file memory 24. Then, the part-of-speech providing apparatus 11 uses the decision tree with frequency probability stored in the decision tree file with probability file memory 24 to store the attribute list stored in the attribute list memory 22 and the part of speech stored in the part-of-speech tag list memory 23. With reference to the tag list, the text data memory 25
By executing a part-of-speech assigning process, which will be described in detail later, on the text data stored and input in the part-of-speech, the part-of-speech-assigned text data is generated and stored in the part-of-speech-assigned text data memory 26. .
Here, the generated part-of-speech-added text data may be output to an output device such as a CRT display or a printer.

Here, each of the decision tree learning device 10 and the part of speech giving device 11 is, for example, a CPU that executes each process.
A ROM (read only memory) for storing a program for each process and data necessary for executing the program,
And a RAM (random access memory) used as a working memory for the U. Further, the memories 21 to 26 are configured by, for example, a hard disk memory.

An example of a part-of-speech tag list stored in the part-of-speech tag list memory 23 is shown in Table 1. Table 2 shows an example of the attribute list stored in the attribute list memory 22.

[0015]

[Table 1] Part of speech tag list 品 Part of speech tag meaning ───── ────────────────────────────── NN1INTER-ACT Singular common noun, Interaction NP1CITYNM Proper noun, City name IIIN Preposition INJJVVGINTER-ACT Present participle of adjective usage, mutual action VVGCONSUME present participle, consumption VVGRECEIVE present participle, acceptance .............................. ──────────────────────

[0016]

[Table 2] ─────────────────────────────────── Attribute Attribute value ────────分類 Classification code using mutual information of words Hierarchical classification code Word whose target word is “~ ing” Yes, No Word whose target word is "-ed" Yes, No Length of target word Numerical value of word length (for example, 4 if "word") Value of part of speech attribute of previous word Value of part of speech attribute of current word Part-of-speech attribute value Part-of-speech attribute value End of sentence is “?” Yes, No ……………………………………… ─────────────────────

Here, the part of speech attribute is an attribute roughly classifying the part of speech into 32 types, and the value of the part of speech attribute is, for example,
v (verb), n (noun), determine (article),
punct (symbol). A hierarchical classification code using mutual information of words is described in, for example, Japanese Patent Application No. 8-02 / 98.
7809 Patent Application and Prior Art Document 3 “Akira Ushiod
a, “Hierarchical Clustering of Words”, Proceedings
of COLING'96, The 16th International Conference on
Computational Linguistics, Vol. 2, pp. 1159-1162, 1996
8 is a hierarchical classification code classified using the word classification method disclosed in "August". 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 a text having the number of words T, a vocabulary having the number of words V, and a vocabulary division function π exist. This is a mapping function representing a division mapping (mapping) to a word class set C in the middle. The likelihood L (π) of the bigram class model that generates text data composed of a plurality of words is obtained by the following equation.

[0018]

## 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.

[0020]

(Equation 2)

Here, Pr (C ₁ ) is the probability of occurrence of a word of the first class C ₁ , and Pr (C ₂ ) is the second class C ₂
Pr (C ₁ | C ₂ ) is the conditional probability that a word of the first class C ₁ will appear after a word of the second class C ₂ has appeared, and Pr (C ₁ | C ₂ ) C ₁ , C ₂ ) is the probability that a word of the _first class C _{1 and} a word of the second class C ₂ appear adjacent to each other. Therefore, AMI is different first mutually Class C ₁ word and the second represented by the number 2
The relative frequency of the word class C ₂ is the probability of occurrence adjacent, divided by the product of the above first occurrence probabilities of the words in the classes C ₁ and a second class of C ₂ probability of occurrence of words Represents the ratio of 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 the word class configuration.

The above word classification method can generate a tree structure having a balanced binary tree form in that words having similar meanings or syntactic features 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 decision tree and an algorithm of a part of speech adding process will be described.

In the 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 class determination is divided in a binary tree format. Build as a tree structure. 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.

[0025]

(Equation 3)

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

(Equation 5)

(Equation 6)

Here, p (tagall) is the frequency probability or appearance probability of the number of events for all part-of-speech tags before division, and Σ for tagall indicates the sum of all part-of-speech tags before division. . Also, p
₁ is the sum of the frequency probability of the number of part-of-speech tag of events included when divided at the node N _1. Further, p (ta
gN ₁₎ is the number of frequency probability of the event for all of the part-of-speech tag of the node N _1, for tagN ₁ Σ
Indicates the sum for all parts of speech tags of the node N _1. p (tagN ₂₎ is the number of frequency probability events for all parts of speech tags of the node N _2, the Σ of tagn _2, 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 part-of-speech assigning system of the present embodiment, the related art document 4 “LEBaum,“ Aninequality and a
ssociated maximization technique in statistical es
timation for probabilistic functions of a Markov p
rocess ", Inequalities, Vol. 3, pp. 1-8, 1972", using the Forward-Backward algorithm, based on the learning data for smoothing, the probability and determination obtained from the learning data for smoothing. Smoothing is performed so that the difference from the probability obtained from the tree is minimized, and the last frequency probability distribution to be given to the part of speech is corrected. 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
(Global 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 an actual part of speech (part of speech tag level shown in Table 1) 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 assignment processing, 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.

[0030]

(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.

[0032]

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.

[0034]

[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 conventional technology document 5 “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 6" 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.

FIG. 2 is a flowchart showing a decision tree learning process executed by the decision tree learning device of FIG.
In FIG. 2, first, in step S1, the part-of-speech-added text data stored in the part-of-speech-added text data memory 21 is read out, and the RAM in the decision tree learning device 10 is read out.
Write to. Next, in step S2, the frequency probability of the combination of each attribute and the part of speech tag (the above p (tagal)
1), p (tagN ₁ ) and p (tagN ₂ ). ) Is calculated and written in the RAM in the decision tree learning device 10. Furthermore, a decision tree with frequency probability is generated by executing a decision tree creation process in step S3,
The decision tree with probability created in step 4 is output to the memory 24 and stored.

FIG. 3 is a flowchart showing the decision tree creation process (step S3) which is a subroutine of FIG. First, in step S11, the entropy H after division by all the attributes and the entropy H ₀ before division are calculated using Equations 4 and 3, respectively. Next, in step S12, 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 S13 satisfies the division continuation criterion. Here, the division continuation criterion is (I)
The difference (H ₀ −H) in entropy when divided based on the selected attribute is equal to a predetermined entropy threshold Hth
(II) The number of events after division based on the selected attribute is equal to or greater than a predetermined event number threshold Dth. If the division continuation criterion is satisfied in step S13, in step S14, two nodes divided by the attribute value of the selected attribute are created, that is, divided in the form of a binary tree to update the decision tree. . Then, in step S15, the processing returns to step S11, and the processing from step S11 is repeated, with each of the created nodes as a processing target. On the other hand, when the division continuation criterion is not satisfied in step S13, the process returns to the original main routine.

FIG. 6 shows an example of the created decision tree with frequency probability. As shown in FIG. 6, the decision tree with frequency probability has a tree structure divided in the form of a binary tree with each of the attributes 101 to 105, and a frequency probability for each part of speech tag is assigned to the last leaf. . In this example,
When the input sentence is “meeting in London”, the part of speech tag N for the word “meeting”
While N1INTER-ACT (singular common noun, mutual action) is given, a part of speech tag NP1CITYNM (proper noun, city name) is given to the word "London".

FIG. 4 is a flowchart showing the part-of-speech providing process executed by the part-of-speech providing apparatus of FIG. FIG.
First, in step S21, the decision tree file with frequency probability stored in the decision tree file with probability file memory 24 is read and written into the RAM in the part-of-speech providing apparatus 11. Next, at step S22, the text data memory 2
The text data to be analyzed stored in 5 is read out and written to the RAM in the part of speech giving device 11. Further, the part-of-speech assignment analysis processing is executed in step S23 to generate the part-of-speech added text data, and in step S24, the data is output to the part-of-speech assigned text data memory 26 and written.

FIG. 5 is a flowchart showing the part-of-speech assignment analysis processing (step S23) which is a subroutine of FIG. First, in step S31, a word at the beginning of the text data to be analyzed is set as a target word. Then, step S
At 32, the root node at the uppermost position of the decision tree is set as the current node to be processed. Then, in step S33, it is determined whether the current node is a leaf node. If NO, the corresponding child node is set as the current node based on the attribute value of the current node in step S38, and the process returns to step S33. On the other hand, step S33
Is YES, the top n frequency probabilities in the frequency probability list assigned to the leaf node in step S34 (where n is plural, for example, preferably
It is 3 to 6, more preferably 4. ) To give to the target word. Then, in step S35, the part-of-speech tag candidates are limited according to the above-described stack decoder algorithm while leaving the connection probability P equal to or higher than the predetermined connection probability. Further, it is determined whether or not there is a next processing word in step S36. If there is, the next word is set as a target word in step S37, and the process returns to step S32 to repeat the above processing. On the other hand, if there is no next word in step S36, the part-of-speech tag string having the maximum connection probability P is determined as the correct part-of-speech string in step S39, and the process returns to the original main routine.

[0042]

EXAMPLES The present inventor conducted the following experiments using the part-of-speech assignment system configured as described above. In this experiment,
The differences between different parts of speech systems and the differences in how to take the learning text data are compared. Experiments were performed using three different parts of speech systems as shown in Table 3. Where UPe
nn is a system used in tree bank data provided by the University of Pennsylvania.
11 is a tree bank created by the present applicant, and is a system using a part-of-speech system including a semantic category.
Syntax is a part-of-speech system of a subset in which semantic categories in ATR Full are deleted. Experiments were performed on learning text data in a case where the text data was randomly collected in units of sentences (selection in Table 4: sentences) and in a case where the data was randomly collected in units of sentences (selection in Table 4: sentences).

[0043]

[Table 3] Part-of-speech system handled ─────────────────────────────────── Part-of-speech system Total part-of-speech learning data test Data ─────────────────────────────────── UPnn 48 Approx. 1 million words 50,000 words ATR Syntax 441 Approx. 30 10,000 words (400,000 words) 60,000 words (10,000 words) ATR Full 2600 About 300,000 words (400,000 words) 60,000 words (10,000 words) ─────────────── ────────────────────

Here, UPenn text data is
For Wall Street Journal, slightly more than one million words of text data for learning and 50,000 words of test text data were used. ATR Syn
The text data of the tax and the ATR Full use the learning text data of 400,000 words in sentence units and use the test text data of 10,000 words, while the text data of about 300,000 words in sentence units are used. Test text data of 60,000 words was used. Table 4 shows the experimental results.

[0045]

[Table 4] Legitimacy rate of part of speech assignment according to the present embodiment 本 Part of speech system Select ALL KW UW {ALL KT UT} << UPen sentence 96.0 96.7 99.6 61.0 91.9 >> {ATR Syntax sentence 92.6 94.7 95.2 52.2 82.9} ─────────── ATR Syntax sentence 90.8 93.8 94.6 41.2 79.6 ───────────────────── ────────────── ATR Full sentence 76.5 79.4 83. 8.5 63.7 ─────────────────────────────────── ATR Full text 71.8 76.8 81.7 8.2 53.9 ─────────────────────────────────── (Note) KW: Known Word, UW: unknown word, KT: known part of speech, UT: unknown part of speech

In Table 4, the accuracy was separately checked for words that appeared in the learning text data as known words KW and words that did not appear as unknown words UW. In the known word KW, the case where the combination of the word and the correct part of speech appears in the learning text data is defined as the known part of speech KT, and the case where the combination does not appear is defined as the unknown part of speech UT.

As is clear from Table 4, the accuracy as a reference (specifically, the accuracy when the most frequent part of speech assigned to the word in the learning data is assigned) UPnn: sentence selection 89%, ATR Syntax: sentence selection 83% (sentence selection 82%), ATR Full: sentence selection 69% (sentence selection 69%). Also, ATR Syn
In the case of tax and ATR Full, the correct answer rate is lower in the case of a sentence than in the case of a sentence. Although this may be considered as a difference in the amount of learning, there is a set of textual features (distribution of words to be used, wording, etc.), and there is no effect when learning data is selected for each sentence. It is also considered that the difference in characteristics between the data and the test text data has an effect.

In the above embodiment, the English part-of-speech system is described. However, the present invention is not limited to this and can be applied to a Japanese part-of-speech system.

As described above, according to the present embodiment, in order to statistically process the connection relation of parts of speech, the relation between words and parts of speech, and the dependence relation between distant words or parts of speech,
Part of speech can be automatically and uniquely assigned with high precision. 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 the learning is performed using the text data to which the parts of speech are added, it is possible to flexibly deal with many parts of speech systems, for example, by introducing priorities to a plurality of division candidates.

[0050]

As described above in detail, according to the part-of-speech providing apparatus according to the first aspect of the present invention, the spelling characteristics of each word, the characteristics according to the usage in the sentence, and the mutual information amount of the word A first storage device for storing an attribute list having a plurality of attributes including a hierarchical classification using a plurality of attributes, a second storage device for storing a part-of-speech list including a plurality of part-of-speech, and a generated frequency probability A third storage device for storing the attached decision tree, an attribute list stored in the first storage device based on the part-of-speech-attached text data comprising a word string, and an attribute list stored in the second storage device. Referring to the part-of-speech list, a 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, and the generated decision tree is generated. Multiple items for leaf nodes that are not split nodes Means for generating a decision tree with a frequency probability and storing the same in the third storage device by calculating and assigning a frequency probability to the data, and a decision with a frequency probability stored in the third storage device Using a tree, the attribute list stored in the first storage device and the second
With reference to the part-of-speech list stored in the storage device of the above, based on the text data consisting of the input word string, the frequency probabilities assigned to the leaf nodes are selected from among the top n n frequency probabilities. And a part-of-speech assigning means for assigning to each word of the text data, determining a part-of-speech string having the maximum connection probability in the word string of the text data as a correct part-of-speech string, and outputting it. Therefore, since the connection relation of the part of speech, the relation between the word and the part of speech, and the dependency relation between the distant word and the part of speech are statistically processed, the part of speech can be automatically and uniquely assigned with high accuracy. 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 text data to which the part of speech is added, it is possible to flexibly deal with many parts of speech systems, for example, by introducing priorities to a plurality of division candidates.

Further, in the part-of-speech providing apparatus according to claim 2, in the part-of-speech providing apparatus according to claim 1, when the decision tree learning means performs the division in the binary tree format, When the attribute having the largest difference (H ₀ −H) between the entropy H ₀ representing the priority order of the validity of the attribute of the attribute and the entropy H after the division is selected as the attribute of the division candidate and the predetermined division continuation criterion is satisfied Then, the decision tree is updated by dividing in the form of a binary tree. Therefore, since the connection relation between parts of speech, the relation between words and parts 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. 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 text data to which the part of speech is added, it is possible to flexibly deal with many parts of speech systems, for example, by introducing priorities to a plurality of division candidates.

Furthermore, in the part-of-speech providing apparatus according to the third aspect, in the part-of-speech providing apparatus according to the second aspect, the division continuation criterion is defined as: (I) a difference in entropy when dividing based on the selected attribute ( (H ₀ −H) is equal to or greater than a predetermined entropy threshold Hth, and (II) the number of events of a set of the attribute after division based on the selected attribute and its attribute value and part of speech is a predetermined event number threshold Dth or more. Therefore, since the connection relation between parts of speech, the relation between words and parts 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. 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 the learning is performed using the text data to which the parts of speech are added, it is possible to flexibly deal with many parts of speech systems, for example, by introducing priorities to a plurality of division candidates.

Further, in the part-of-speech providing apparatus according to claim 4, in the part-of-speech providing apparatus according to claim 1, 2, or 3, the part-of-speech providing means is higher in the frequency probabilities given to the leaf nodes. After selecting a plurality of n frequency probabilities and assigning them to each word of the text data, using the predetermined stack decoder algorithm, the connection probability for the word string of the text data being processed is determined by the predetermined connection probability. The part-of-speech candidates are limited while leaving only the part-of-speech candidates described above, and the part-of-speech string having the maximum connection probability in the word string of the text data at the end of the process is determined as the correct part-of-speech string. Therefore, the connection between parts of speech, the relation between words and parts of speech,
Furthermore, since the dependency relationship with a distant word or part of speech is statistically processed, the part of speech can be automatically and uniquely assigned. 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 the learning is performed using the text data to which the parts of speech are added, it is possible to flexibly deal with many parts of speech systems, for example, by introducing priorities to a plurality of division candidates.

[Brief description of the drawings]

FIG. 1 is a block diagram of a part-of-speech providing system including a decision tree learning device and a part-of-speech providing device according to an embodiment of the present invention.

FIG. 2 is a flowchart showing a decision tree learning process executed by the decision tree learning device of FIG. 1;

FIG. 3 is a flowchart showing a decision tree creation process (step S3) which is a subroutine of FIG.

FIG. 4 is a flowchart showing a part-of-speech providing process executed by the part-of-speech providing apparatus of FIG. 1;

FIG. 5 is a flowchart showing a part of speech assignment analysis process (step S23) which is a subroutine of FIG.

6 is a diagram illustrating an example of a decision tree in a decision tree file with frequency probability created by the decision tree learning device of FIG. 1;

[Explanation of symbols]

 Reference Signs List 10: Decision tree learning device, 11: Part-of-speech assigning device, 21: Part-of-speech-added text data memory, 22: Attribute list memory, 23: Part of speech tag list memory, 24: Decision tree file memory with probability 26: Text data memory with part of speech added.

Continuation of the front page (72) Inventor Stephen G. Eubank 5 Shiratani, Inaya, Seika-cho, Soraku-gun, Kyoto Pref. 55122 (JP, A) JP-A-4-141717 (JP, A) JP-A-1-137296 (JP, A) Eric Brill, "Transformation-Based Error-Driven Learning and Natural Language Processing: Study in Part -of-Speech Tagging ", Computational Linguistics, Vol. 21, No. 4, p. 543-p. 565 (1995) (58) Field surveyed (Int. Cl. ⁷ , DB name) G06F 17/20-17/30 JICST file (JOIS)

Claims (4)

(57) [Claims] 1. An attribute list including a plurality of attributes including a spelling characteristic of each word, a characteristic according to a usage in a sentence, and a hierarchical classification using mutual information of words. One storage device, a second storage device for storing a part-of-speech list including a plurality of part-of-speech, a third storage device for storing a generated decision tree with frequency probability, and a text-to-speech text data comprising a word string Based on the attribute list stored in the first storage device and the part-of-speech list stored in the second storage device, depending on the attribute value of each attribute. A decision tree for giving a part of speech having a tree structure with a simple binary tree format, 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 decision tree. The decision tree with frequency probability Tree generating means for generating and storing in the third storage device; and an attribute list stored in the first storage device using the decision tree with frequency probability stored in the third storage device And the part-of-speech list stored in the second storage device, and based on the text data consisting of the input word string, the top plurality n of the frequency probabilities assigned to the leaf nodes A part-of-speech assigning means for selecting and assigning a frequency probability to each word of the text data, determining a part-of-speech string having a maximum connection probability in the word string of the text data as a correct part-of-speech string, and outputting the determined part-of-speech string. A part-of-speech providing apparatus characterized by the following. Wherein said decision tree learning means, when splitting in the form of the binary tree, after the division and entropy H ₀ representing the priority of the effectiveness of the attributes before division by the attributes of the entropy H An attribute having the largest difference (H ₀ −H) is selected as an attribute of a candidate for division, and when a predetermined continuation criterion is satisfied, the decision tree is divided and updated in a binary tree format. Item-of-speech providing apparatus according to item 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
Description part-of-speech device. 4. The part-of-speech providing means selects a plurality of top n frequency probabilities from among the frequency probabilities given to the leaf nodes and gives them to each word of the text data. Using the decoder algorithm, the part-of-speech candidates are limited by leaving only the part-of-speech candidates whose connection probability to the word string of the text data being processed is equal to or greater than the predetermined connection probability, and in the word string of the text data at the end of the processing, 4. The part-of-speech sequence having the maximum connection probability is determined as a correct part-of-speech sequence.
Description part-of-speech device.