JPH0570839B2 - - Google Patents

Abstract

PURPOSE:To reduce the time during which the input of an input pattern is started and then the result of recognition is obtained, by carrying out the production of a candidate graph from the input pattern and the detection of a candidate of a significant category train out of the candidate flag. CONSTITUTION:A category train candidate producing part 108 receives a significant category train candidate from a significance deciding part 109 and adds a new category candidate at the termination of the category train candidate for production of plural new category train candidates. These new candidates are added to a category train candidate memory part 106. A new category candidate to be added is obtained from the candidate graphs of a candidate graph memory part 103. Here the category train candidate is stored temporarily to a category train candidate memory part 110 to interrupt the processing in case the coincidence is obtained between the termination of the category train candidate and the termination of a candidate graph. Then the processing is started again when a start signal (a') is received from a candidate graph producing part 102.

Description

Detailed Description of the Invention (Field of Industrial Application) The present invention relates to a pattern recognition device that recognizes an input pattern and outputs a category string corresponding to the input pattern as a recognition result. The present invention relates to a pattern recognition device that outputs only significant category columns from column candidates as recognition results.

(Prior art and its problems) When recognizing an input pattern as a category sequence,
If each category included in an input pattern can be individually recognized and a category string resulting from the recognition can be used as a recognition result of the input pattern, it is possible to recognize an input pattern of an arbitrary category string.

However, it is generally difficult to individually recognize each category in an input pattern. In particular, when the boundaries between categories in an input pattern are unclear, such as when recognizing continuously uttered speech as a string of syllables, it is necessary to uniquely determine the interval in which each category in the input pattern is located. Have difficulty.

Therefore, as shown in Japanese Patent Application Laid-Open No. 58-55995 entitled "Voice Recognition System" (Reference 1), the following method has been conventionally used.

First, a plurality of category candidates are detected for each part of the input pattern, and each category candidate is given a degree of reliability as a recognition result. After detecting category candidates for all parts of the input pattern, these category candidates are arranged to obtain category string candidates corresponding to the input pattern. Among these category sequence candidates, the recognition rate is improved by selecting a category sequence that is significant as a recognition result and has the highest possible reliability as a category sequence determined from the reliability level as a recognition result. be able to.

However, this method requires searching a dictionary of significant category columns and determining the possibility of connection between category columns in order to determine the significance of category columns, which requires a large amount of calculation. It has the disadvantage of requiring

Therefore, in Document 1, the significance of category strings is determined from among all category string candidates obtained from an input pattern, in descending order of reliability as a category string.

This reduces the number of significance determinations and the amount of calculation required.

However, in the above-mentioned published patent, all category sequence candidates are once determined, which has the drawback of requiring a large amount of calculation and storage.

Therefore, in Japanese Patent Application No. 58-214544 "Pattern Recognition System" (Reference 2), a significant and highly reliable category string is obtained by the method described below without obtaining all category string candidates. made possible.

This method is an application of the heuristic search method (Artificial Intelligence Handbook Vol. 1 pp.67-83, Kyoritsu Shuppan, April 1983), which is known in the field of artificial intelligence.

In this method, all category sequence candidates obtained from an input pattern are retained in the form of a candidate graph, and various lengths from the starting node of the candidate graph corresponding to the starting edge of the input pattern to an arbitrary node along the way are stored. For each category string candidate, the reliability of the category string candidate with respect to the entire input pattern is estimated, which is obtained by extending the category string candidate from the terminal end to the terminal node of the candidate graph. Using this estimated reliability, it becomes possible to compare the reliability of category sequence candidates of various lengths. Therefore, category string candidates can be found in descending order of reliability without having to find all category string candidates from the candidate graph, and the amount of calculation and storage can be reduced.

In particular, in Document 2, the reliability estimation is calculated from the actual reliability of the category candidates from the end of the category string candidate to the final node of the candidate graph, so the estimation accuracy is high and the amount of calculation is reduced. It has become possible to drastically reduce the amount of memory.

However, in Document 2, as mentioned above, since the reliability is calculated from the reliability of category candidates for the entire input pattern, after the detection of category candidates for the entire input pattern is completed, the reliability for the entire input pattern is Significance judgment could not be made until after the input was made. For this reason, there was a drawback that it took a long time from the start of inputting an input pattern until the recognition result was output.

(Object of the Invention) An object of the present invention is to eliminate the above-mentioned drawbacks by performing the creation of a candidate graph from an input pattern and the detection of significant category string candidates from the candidate graph in parallel, and to To provide a pattern recognition device that takes less time to obtain recognition results.

(Structure of the Invention) The pattern recognition device of the present invention analyzes an input pattern, detects a plurality of category candidates for each part of the input pattern, and outputs the detected category candidates along with position information and reliability in the input pattern. A category candidate detection means detects the plurality of category candidates according to their positional information, and determines the positional relationship between the category candidates when category candidates for other parts of the input pattern are already stored in the candidate graph storage means. creates a candidate graph that maintains a positional relationship with these category candidates and each candidate has a cost representing the reliability, and stores the candidate graph in the candidate graph storage means; Minimum cost calculation means for calculating the minimum cumulative cost up to the current end node for the node of the candidate graph stored in the storage means; and for the category string stored in the first category string storage means; an evaluation value calculation means for calculating an evaluation value using the minimum cumulative cost and the cost of each candidate; a best category string selection means for extracting a category string with the best evaluation value from the first category string storage means; a significance determining means for determining the significance of the category string retrieved by the best category string selecting means as a recognition result and outputting a significant category string; If it is not the final node of the candidate graph stored in the candidate graph storage means, generally a plurality of new category sequence candidates are created by adding a new category candidate to the category sequence, and the new category sequence candidates are stored in the first category sequence storage means. When the end of the category string is the end node of the candidate graph but not the end of the input pattern, the category string is temporarily stored in the second category string storage means, and a new category candidate is added to the candidate graph. is added, the process is restarted to create a new category string and stored in the first category string storage means, and when the end of the category string matches the end of the input pattern, the recognition result of the category string is and category string creation means for outputting the category string.

(Example 1) Hereinafter, the present invention will be described in detail according to examples with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. This embodiment constitutes a pattern recognition device that uses continuous Japanese speech as an input pattern and outputs a Japanese syllable string as a recognition result.

The category candidate detection unit 101 detects a plurality of category candidates corresponding to each part of the input pattern, and each time the detection of each part is completed, the corresponding category candidate is detected along with the position information in the input pattern. It is sent to the candidate graph creation unit 102.

When the input pattern is Japanese continuous speech, syllables can be considered as the category to be recognized. That is, the category candidate detection unit 101 may be any device that can detect syllable candidates from an input pattern. For this purpose, for example, a category candidate detection section shown in FIG. 2 can be used. In FIG. 2, the voice which is an input pattern is temporarily stored in an input pattern buffer 201. In FIG. 20
1, the vowel candidate detection unit 2
02 first detects one vowel candidate. This detection is performed by matching a part of the input pattern with a standard pattern of each vowel category stored in advance in the vowel dictionary 203. Since the vowel signal is relatively stationary, it is easy to detect. When the vowel candidate detection unit 202 detects one vowel candidate, it sends it to the consonant candidate detection unit 204. 1
Each vowel candidate includes at least information on vowel category, confidence level, and position in the input pattern.
In Japanese, a syllable is composed of a consonant (C)-vowel (V) pair. Therefore, in the input pattern, the section narrowed by two vowels has a length less than or equal to a certain length (this is called a VCV section), and the section from the start of the input pattern to one vowel has a length less than or equal to a certain length. (This is the CV section), there is one consonant in each.

When the consonant candidate detection unit 204 receives a vowel candidate (referred to as V ₁ ) from the vowel candidate detection unit 202 , the consonant candidate detection unit 204 stores this in the vowel candidate storage unit 206 . At the same time, all of the above-mentioned V ₂ CV ₁ section and CV ₁ section are detected from this vowel candidate, another vowel candidate already stored in 206 (referred to as V ₂ ), or the start end of the input pattern. For each of these intervals, consonant dictionary 205
A plurality of consonant candidates are obtained by matching those with matching V ₂ and V ₁ among the VCV and CV standard patterns stored in advance in the .

Combining this consonant candidate and vowel candidate V ₁ ,
A plurality of syllable candidates are output as category candidates for one section of the input pattern. This category candidate includes at least information on syllable category, confidence level, and position in the input pattern.

The above process is repeated to sequentially output all category candidates in the input pattern.

Returning to FIG. 1, when the candidate graph creation unit 102 receives a new category candidate from the category candidate detection unit 101, it adds this new candidate graph to the candidate graph already stored in the candidate graph storage unit 103 through the previous processing. Add category suggestions. The candidate graph holds all the category candidates obtained so far along with their mutual positional relationships, and the branches of the graph represent the category candidates.

As an example of a candidate graph, FIG. 4 shows a candidate graph that holds syllable candidates obtained for the second syllable, that is, the part of "oshi" in the voice uttered "Oshie teita daita." In FIG. 4, the nodes indicated by , . . . represent syllable boundary candidates in the input pattern, and the nodes are the starting ends of the input pattern. The syllable candidates are represented by a combination of a syllable category and a confidence level. For example, there are three syllable candidates for the - branch, one of which is ``u'' and has a confidence level of 72. In this embodiment, the reliability is given by the matching distance between the standard pattern and the input pattern, and the smaller this value is, the higher the reliability is.

After adding a new candidate to the candidate graph storage section 103, the candidate graph creation section 102 sends start signals a, a' to the minimum cumulative cost calculation section 104 and the category string candidate creation section 108.

When the minimum cumulative cost calculation unit 104 receives the start signal a, it calculates the minimum cumulative cost for all nodes of the candidate graph stored in the candidate graph storage unit 103 from the node to the current terminal node of the candidate graph. and grant it. Here, the cumulative cost is given as the sum of the costs of each of the category candidates that make up the candidate sequence for any route in the candidate graph, that is, the candidate sequence. The cost of a category candidate is a value representing the reliability of the candidate, and the smaller the value, the higher the reliability. In this embodiment, the matching distance with respect to the standard pattern previously given to each candidate as the reliability is used as is.

Calculation of the minimum cumulative cost can be performed efficiently by using dynamic programming. In other words, let the nodes of the candidate graph be n (n=1,...,i,...,j,
..., N-K, ..., N) (where 1 is the starting node, N-
K,...,N are the end nodes), the number of edges between nodes i and j is M, and the cost of the candidate for the m-th edge between nodes i and j is d(i, j, m), Node n
The minimum cumulative cost c(n) from to the final node can be found from the following recurrence formula.

c(N-K)=...=c(N)=φ (initial value) c(n)=min [min d(n, j, m)+c(j)] n<j≦N 1≦m≦ M (n=N-K-1, N-K-2,..., 1)...
(1) Each time the minimum cumulative cost calculation unit 104 receives the start signal a from the candidate graph creation unit 102, it calculates the minimum cumulative cost of each node for the candidate graph in the candidate graph storage unit 103. It is not necessary to solve the above recurrence formula (1) for all nodes.
For example, in the candidate graph of Figure 4, when a new - edge and node are added by 102, the calculation for the node , , calculates the minimum cumulative cost of the node with respect to the previous value. By adding the increment, a new minimum cumulative cost can be determined, and calculation efficiency can be further improved.

When the minimum cumulative cost calculation unit 104 completes the calculation, it sends a start signal b to the evaluation value calculation unit 105.

Upon receiving the start signal b, the evaluation value calculation unit 105 calculates and assigns an evaluation value to each of the category sequence candidates stored in the category sequence candidate storage unit 106. As a special case, 106 is empty in the initial state, and no evaluation value is calculated at this time.

The evaluation value of a category string candidate may be any value that can correctly evaluate the reliability of a plurality of category string candidates of various lengths without depending on the difference in length. In this example, a category sequence candidate S(i) that forms a certain path from the starting node of the candidate graph to the intermediate node i
The evaluation value f(S(i)) is calculated using the following formula.

f(S(i))=g(S(i))+h(S(i))...
…(2) Here, g(S(i)) is the category sequence candidate S
This is the cumulative cost of the route from the starting node to the intermediate node i corresponding to (i), that is, the total cost of all category candidates included in this route. h(S
(i)) is the estimated cost of the route from intermediate node i to the current final node. There are multiple routes to this final node, and which route to take in future processing cannot be determined at the evaluation value calculation stage. Therefore, h(S(i)) is calculated using the following equation (3).

h(S(i))=α・c(i)...(3) Here, c(i) is the minimum cumulative cost from node i to the current final node, and is calculated by the minimum cumulative cost calculation unit 104. This is a value that has already been calculated and assigned to the candidate graph. α is a coefficient.

Using f(S(i)) calculated as above,
It is possible to compare the reliability of category string candidates of various lengths.

Note that some category columns for which evaluation values are to be calculated may have already been given evaluation values in previous processing, but the final node of the candidate graph may have changed, so recalculation may be necessary. There is. In this case, the new evaluation value can be easily calculated from the previous evaluation value and the increase in the minimum cumulative cost given to the previous end node from the previous evaluation value calculation stage.

The evaluation value calculation unit 105 stores the category string candidate storage 10.
When evaluation value calculations for all category string candidates in 6 are completed, the best category string candidate selection unit 1
The start signal C is sent at 07.

The best category sequence candidate selection unit 107 selects the evaluation value calculation unit 105 from the category sequence candidate storage unit 106.
The category sequence candidate with the best evaluation value calculated in is extracted and sent to the significance determination unit 109.

The significance determination unit 109 determines the significance of the category sequence candidate received from the best category sequence candidate selection unit 107 as a recognition result, and if significant, sends the category sequence candidate to the category sequence candidate generation unit 108 .

Since the purpose of this embodiment is to recognize Japanese speech, it is determined whether the category string candidate is part or all of a correct Japanese syllable sequence. For this purpose, for example, a significance determining section as shown in the block diagram of FIG. 3 is used. In FIG. 3, a word dictionary 301 holds all words that can appear in the recognition results as syllable sequences. Word connection table 302
holds the possibility of mutual connection between the words included in 301. The determining unit 303 determines that the received category sequence candidate is significant if it is included in 301 and forms part or all of a word sequence that satisfies the connectability of 302, and determines that the category sequence candidate is significant. It is sent to the category string candidate creation unit 108. After a new category candidate is added to the end of the category string candidate in step 108, the significance determination may be performed again. Therefore, by adding the found word string to the category string candidate, it is possible to improve the efficiency of the processing in subsequent significance determinations.

The category string candidate creation unit 108 is the significance determination unit 1
When a significant category string candidate is received from 09, a plurality of new category string candidates are created by adding a new category candidate to the end of the category string candidate, and added to the category string candidate storage section 106. . A new category candidate to be added is obtained from the candidate graph in the candidate graph storage section 103, but if the end of the category string candidate matches the end of the candidate graph, the category string candidate is temporarily stored in the category string candidate storage section. 110 and interrupts the process. Thereafter, the processing is restarted by receiving the start signal a' from the candidate graph creation section. Furthermore, if the end of the category string candidate matches the end of the input pattern, the category string candidate is output as a recognition result.

For example, if the candidate graph shown in FIG. 4 is stored in the candidate graph storage unit 103 and the category sequence candidate generation unit 108 receives the category sequence candidate -W, then the category sequence candidate -W
A new category string candidate - Woozi - is created and added to the category string candidate storage section 106.

As described above, in the pattern recognition device of the present invention, the process of creating a candidate graph from an input pattern,
While performing the process of finding significant category string candidates from the candidate graph in parallel, significant category strings from the beginning to the end of the input pattern are detected and used as recognition results.

(Example 2) In the block diagram of FIG. 1, if a circuit is used as the category candidate detection unit 101 to detect a plurality of candidates for each monosyllable of an input pattern that is inputted separately for each monosyllable. , it is possible to configure a recognition device for speech uttered in units of monosyllables.

(Embodiment 3) In the block diagram of FIG. 1, if a character recognition circuit is used as the category candidate detection unit 101,
A character recognition device can be configured.

(Example 4) In the block diagram of FIG.
In 09, grammatical knowledge of natural languages or formal languages other than Japanese can be used, thereby making it possible to configure a device that recognizes any input pattern other than Japanese.

(Effects of the Invention) As detailed above, according to the present invention, the process of analyzing an input pattern and creating a candidate graph, and the process of determining significant category sequence candidates from the candidate graph can be performed in parallel. This makes it possible to significantly shorten the time from inputting an input pattern to obtaining a recognition result. Furthermore, it is also possible to start the process of finding significant category sequence candidates before the input of the entire input pattern is completed. These effects are particularly effective in cases where high-speed responsiveness is required, such as in real-time recognition devices.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention;
FIG. 2 is a block diagram showing an example of a category candidate detection section, FIG. 3 is a block diagram showing an example of a significance determination section, and FIG. 4 is a diagram showing an example of a candidate graph. In the figure, 101...category candidate detection unit;
102... Candidate graph creation unit, 103... Candidate graph storage unit, 104... Minimum cumulative cost calculation unit,
105... Evaluation value calculation section, 106... Category string candidate storage section, 107... Best category string candidate selection section, 108... Category string candidate creation section, 109...
...Significance determination section, 110...Category string candidate storage section, 201...Input pattern buffer, 202...
Vowel candidate detection unit, 203... Vowel dictionary, 204...
... Consonant candidate detection unit, 205 ... Consonant dictionary, 206
... Vowel candidate storage section, 301 ... Word dictionary, 30
2...word connection table, 303...determination section.

Claims (1)

[Claims] 1 Category candidate detection means that analyzes an input pattern, detects a plurality of category candidates for each part of the input pattern, and outputs the position information and reliability in the input pattern, and the plurality of category candidates. According to the position information, maintain the positional relationship between the category candidates and, if category candidates for other parts of the input pattern are already stored in the candidate graph storage means, maintain the positional relationship with these category candidates. candidate graph creation means for creating a candidate graph in which each candidate has a cost representing the reliability, and storing the candidate graph in the candidate graph storage means; A minimum cost calculation means for calculating the minimum cumulative cost up to the current terminal node, and a category string stored in the first category string storage means, using the minimum cumulative cost and the cost of each candidate. an evaluation value calculation means for calculating an evaluation value; a best category string selection means for taking out the category string with the best evaluation value from the first category string storage means; and a category string taken out by the best category string selection means is recognized. a significance determining means for determining the significance as a result and outputting a significant category string; and a candidate graph whose terminal end of the significant category string output by the significance determining means is stored in the candidate graph storage means. If it is not the terminal node, generally a plurality of new category string candidates are created by adding a new category candidate to the category string and added to the first category string storage means, and the end node of the category string is added to the candidate graph. If it is the terminal node but not the terminal of the input pattern, the category string is temporarily stored in the second category string storage means, and when a new category candidate is added to the candidate graph, the processing is restarted to create a new category. A pattern recognition device comprising: a category sequence creation means for creating a sequence and storing it in the first category sequence storage means, and outputting the category sequence as a recognition result when the end of the category sequence matches the end of the input pattern. .