JPS61114385A - Pattern recognizer - 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] (Industrial Application Field) The present invention provides an input pattern! &! The present invention relates to a pattern recognition device that recognizes and outputs a category string corresponding to an input pattern as a recognition result, and particularly relates to a pattern recognition device that outputs only significant category strings from category string candidates obtained from an input pattern as a recognition result.

(Prior art and its problems) When recognizing an input pattern as a category string, if each category included in the input pattern can be recognized individually and the category string of the recognition result can be used as the recognition result of the input pattern, It can recognize input patterns of arbitrary category strings.

However, it is generally difficult to individually recognize each category in an input pattern. In particular, when the boundaries of the categories in the input pattern are unclear, such as when recognizing continuously uttered speech as a syllable string, 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 methods have been used in the past.

First, multiple category candidates are detected for each part of the input pattern, and each category candidate is given a reliability level as a recognition result. After detecting, those category candidates are arranged to obtain a category sequence candidate corresponding to the input pattern.Among these category sequence candidates, select one that is significant as a recognition result and is a category sequence determined from the reliability. The wgR rate can be improved by setting the category string with the highest possible reliability as the recognition result.

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 required calculations.

However, in the above-mentioned published patent, all category sequence candidates are found at once, 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), it is proposed to obtain a significant and highly reliable category string without obtaining all category string candidates using the method described below. made possible.

This method is based on the heuristic search method (Artificial Intelligence Handbook Vol. 1 PP-6), which is known in the field of artificial intelligence.
7-83, Kyoritsu Shuppan, April 1983).

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, it is possible to find category string candidates 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 significantly 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 entire input pattern is Significance could not be determined until after input. For this reason, there was a drawback that it took a long time from when a human pattern began to be input 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 section, and detects the plurality of category candidates according to their positional information, and determines the mutual positional relationship between the category candidates and when category candidates for other parts of the input pattern are already stored in the candidate graph storage means; Create a candidate graph that maintains the positional relationship with these category candidates and each candidate has a cost representing the reliability,
Candidate graph creation means for storing the candidate graph in the candidate graph storage means, and minimum cost calculation for calculating the minimum cumulative cost up to the current terminal node for the nodes of the candidate graph stored in the candidate graph storage means. means and the first
evaluation value calculation means for calculating an evaluation value for the category string stored in the category string storage means using the minimum cumulative cost and the cost of each candidate; a best category string selecting means for extracting a category string with the best value; a significance determining means for determining the significance of the category string extracted by the best category string selecting means as a recognition result and outputting a significant category string; If the end of the significant category string output by the significance determining means is not the end node of the candidate graph stored in the candidate graph storage means, a new category string candidate is created by adding a new category candidate to the category string. Generally, a plurality of category strings are created and added to the first category string storage means, and 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 stored in the second category string storage means. The process is temporarily stored in the means, and when a new category candidate is added to the candidate graph, the process is restarted to create a new category string and stored in the first category string storage means. and a category string creating means for outputting the category string as a recognition result when the end matches the end of the input pattern.

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

FIG. 31 is a block diagram showing an 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 candidate graph creation unit 10 selects the corresponding category candidate along with the position information in the input pattern.
Send to 2.

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 that is an input pattern is temporarily stored in an input pattern buffer 201. The vowel candidate detecting unit 202 first detects one vowel candidate for the voice stored in the voice stored in the voice 201 . This detection is
This 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, the vowel candidate detection unit 202 selects this as the consonant candidate detection unit 204.
send to One vowel candidate includes at least information on vowel category, reliability, and position in the input pattern. In Japanese, a syllable is composed of a pair of consonants (Q-vowel (1). Therefore, in the input pattern, in an interval of a certain length or less among the intervals narrowed by two vowels, interval) In the CV section 1), the interval from the start of the input pattern to one vowel is less than or equal to a certain length.
There will be one consonant for each.

The consonant candidate detection unit 204 detects vowel candidates (V.

) is taken and stored in the vowel candidate storage unit 206. At the same time, the above V is calculated from this vowel candidate and another vowel candidate already stored in 206 (referred to as Vt) or the starting end of the input pattern.

Detect all CVI sections and CVI sections. For each of these sections, among the vCv and Cv standard patterns stored in advance in the consonant dictionary 205, V, .
Multiple consonant candidates are generated by matching matches of V.

This consonant candidate and vowel candidate V1 are combined to output a plurality of syllable candidates 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.

By repeating the above process, all category candidates in the input pattern are outputted as 81ζ.

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 ■, ■, and ■- represent syllable boundary candidates in the input pattern, and the nodes
is the start of the input pattern. Syllable candidates are represented by pairs of syllable categories and confidence levels. For example, the branch ■-■ has three syllable candidates, one of which is ``tsu'' and has a confidence level of 7.
It is 2. 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 the candidate graph creation section 102 adds a new candidate to the candidate graph storage section 103, it transmits a start signal aa' to the minimum cumulative cost calculation section 104 and the category candidate detection section 1081.

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 final node of the candidate graph. Calculate and give. Here, the cumulative cost is given for any path in the candidate graph, that is, the candidate string, as the sum of the costs of each of the category candidates that make up the candidate string. 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, the nodes of the candidate graph are ``(''''L'-' + j + -* J
H-HN-, -, N) (where 1 is the starting node and N-, -, N is the ending node), the number of edges between nodes i and 1 is M
The cost of the candidate for the m-th edge between nodes 'TJ is d
＜r,''.

m), the minimum cumulative cost C(n) from node n to the final node can be found from the following recurrence formula.

C(g)-K)-・--～-〇α)-φ(initial value)c (
n) = min (min d (n, j, m)
+c (j)) n<j≦N1≦m≦M (n=-1 for N-, -2 for N-, =-, 1)・-・(1
) The minimum cumulative cost calculation unit 104 is the candidate graph creation unit 10
Each time the start signal a is received from 2, the candidate graph storage unit 1
The minimum cumulative cost of each node is calculated for the candidate graph in 03, but each time the above recurrence formula (
There is no need to solve 1). For example, in the candidate graph of Fig. 4, when a new branch of ■-■ and a node ■ are added by 102i, the calculation for the nodes ■, ■, and By adding the increase in the minimum cumulative cost in (2), 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 to the evaluation value calculation unit 105.

When the evaluation value calculation unit 105 receives the start signal, it 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, initially 106 is empty,
At this time, evaluation value calculation is not performed.

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 embodiment, the evaluation value f(S(i)) of the category sequence candidate 5(i) forming a path c from the starting node to an intermediate node i of the candidate graph is calculated using the following equation.

f (S (i)) −g (S (i)) +h (
S (i))---・(2) Here, g<s<r>> is the cumulative cost of the route from the starting node to the intermediate node i corresponding to category sequence candidate 5(1), that is, the total cost of this route. It is the total cost of all included category candidates. 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 the minimum cumulative cost calculation unit 10
4, it is a value that has already been calculated and assigned to the candidate graph. α is a coefficient.

By using f (S (su)) calculated as described above, it is possible to compare the reliabilities of category sequence candidates of various lengths.

Note that some of the category columns for which evaluation values are to be calculated have already been given evaluation values in previous processing.
The final node of the candidate graph may have changed, so recalculation is necessary. 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.

When the evaluation value calculation unit 105 completes evaluation value calculation for all category sequence candidates in the category sequence candidate storage 106, it sends a start signal C to the best category sequence candidate selection unit 107.

The best category string candidate selection section 107 extracts the category string candidate with the best evaluation value calculated by the evaluation value calculation section 105 from the category string candidate storage section 106 and sends it to the significance determination section 109 .

The significance determination unit 109 is the best category sequence candidate selection unit 107
The received category string candidate is judged to be significant as a recognition result, and if significant, the category string candidate is sent to the category string candidate creation section 108.

In this example, since the purpose 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. Third
In Figure E, the word dictionary 301 holds all words that can appear in the g recognition results as syllable sequences. single! 1I
The ta continuation table 302 holds the connection possibilities between the words included in 301. The determining unit 303 determines that the category string 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 the category string candidate is significant. The candidates are sent to the category string candidate creation unit 108I. After three new category candidates are added to the end of the armpit 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 make the processing more efficient in subsequent significance determinations.

Upon receiving a significant category sequence candidate from the significance determination unit 109, the category sequence candidate creation unit 108 creates a plurality of new category sequence candidates by adding a new category candidate to the end of the category sequence candidate. and adds it to the category candidate detection unit 106.

New category candidates to be added are stored in the candidate graph storage unit 103
However, 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 unit 110 and the process is interrupted. After that, a start signal a' is sent from the candidate graph creation section.
The receiver resumes processing by receiving the . Furthermore, if the end of the category string candidate matches the end of the input pattern, the category string candidate is S! 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 column candidate generation unit 108 receives the category column candidate ■−C■ and category column candidate ■−Wu■−G■ are newly created and category column candidate storage unit 1
Added in 06.

As mentioned above, the pattern of the present invention! The IW& device performs the process of creating a candidate graph from the input pattern and the process of finding significant category string candidates from the candidate graph in parallel, and detects and recognizes significant category strings from the beginning to the end of the input pattern. Result.

(Example 2) In the block diagram of FIG.
First, by using a circuit that detects a plurality of candidates for each monosyllable of an input pattern that is inputted in units of monosyllables, it is possible to construct a g recognition device for g-speech that is uttered in monosyllable units. Can be done.

(Embodiment 3) In the block diagram of FIG. 31, the category candidate detection unit 10
First, if a character recognition circuit is used, a character recognition device can be constructed.

(Embodiment 4) In the block diagram of FIG. 1, the significance determination unit 1091 can also use the grammatical knowledge of other natural languages or formal languages other than Japanese, thereby making it possible to use any language other than Japanese. It is possible to configure a device that obtains an input pattern.

(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 an 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 block diagram showing an example of a category candidate detection section. It is a figure which shows an example of a graph. In the figure, 101-category candidate detection unit, 102-candidate graph creation unit, 103-candidate graph storage unit, 104
...Minimum cumulative cost calculation section, 105-FFi 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 unit, 110-Category string candidate storage unit, 201-Manual pattern buffer, 202-Vowel candidate detection unit, 203--Vowel dictionary, 204--Consonant candidate detection unit, 205--Consonant dictionary, 206-- - Vowel candidate storage unit, 30
1-word dictionary, 302--single M connection table, 303--judgment unit. E 1 Figure input pattern 7I-2 Figure O 3 Figure 71-4 Figure

Claims (1)

[Claims] Category candidate detection means for analyzing an input pattern, detecting a plurality of category candidates for each part of the input pattern, and outputting the plurality of category candidates together with position information and reliability in the input pattern; , according to the positional 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 and candidate graph creation means for creating a candidate graph having a cost representing the reliability and storing the candidate graph in the candidate graph storage means; and a minimum cost calculation means for calculating the minimum cumulative cost up to the final node of an evaluation value calculation means for calculating, 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 as a recognition result. a significance determining means for determining significance and outputting a significant category string; and a terminal end of the significant category string outputted by the significance determining means is not a terminal node of the candidate graph stored in the candidate graph storage means. In this case, a plurality of new category string candidates are generally created by adding a new category candidate to the category string, and added to the first category string storage means, and when the end of the category string is the terminal node of the candidate graph. If there is a category string, but it is not the end 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 process is restarted to create a new category string. and storing the category string in the first category string storage means, and outputting the category string as a recognition result when the end of the category string matches the end of the input pattern.