Best first search considering difference between scores

• US 5,416,892 A
• Filed: 08/23/1993
• Issued: 05/16/1995
• Est. Priority Date: 03/07/1990
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Loken-Kim, Kyung-ho
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): DAVIS, GEORGE B
• Application Number:
  US08/110,799
• Time in Patent Office: 631 Days
• Field of Search: 395/51, 381/43, 381/42, 382/10, 382/13, 382/9, 382/19, 382/36
• US Class Current: 706/46
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence

Abstract

A best first search for problem-solving in an artificial intelligence system employing a novel search priority index is disclosed. The search priority index is calculated based on a difference between scores of a node and the next node in breadth. Searching steps required to attain a solution can be reduced by employing the search priority index.

Claims

1. A method of searching a lattice for problem-solving in artificial intelligence using a data processor, the lattice including nodes having present and next nodes each having node scores, and the lattice having depth and breadth, said method comprising the steps of:

(a) inputting pattern data sets using an input device and storing the pattern data sets in a memory;

(b) determining candidate patterns for each of the input pattern data sets;

(c) generating pattern scores for the candidate patterns based on a similarity between the pattern data sets and the candidate patterns using the data processor to determine which candidate patterns are assigned to the nodes of the lattice so that the candidate patterns for each of the pattern data sets are arranged at a specific depth of the lattice in order of the breadth of the lattice according to the respective pattern scores thereof;

(d) calculating differences between the node scores of the nodes with the same depth using the data processor;

(e) calculating a search priority index for each of the nodes corresponding to the candidate patterns having a search priority based on the differences of the node scores of the nodes with the same depth using the data processor; and

(f) searching the lattice according to the search priority indexes and finding patterns corresponding to the pattern data sets using the data processor.

2. A search method as claimed in claim 1, wherein the method comprises the step of calculating mean values of the score differences within each depth, and the search priority indexes are calculated based on the score differences, the mean values, and the breadth, for each of the nodes.

3. A search method as claimed in claim 2, wherein the breadth is defined by breadth i and the search priority index PI of one of the nodes in the breadth i is calculated according to the following equation:

space="preserve" listing-type="equation">PI=0;

for i=1, and PI=(S.sub.i -S.sub.i-1)/(mean value)×

e.sup.Ci ;

for i=2, 3, 4 . . .

wherein

S_i ;

score of the one of the nodes of the breadth i, and

C;

constant.

4. A search method as claimed in claim 3, wherein the one of the nodes is a candidate element for an input element generated by a recognizer connected to the input device which is supplied the input element from the input device, the score, S_i, is a match score of the candidate element generated by the recognizer, the lattice is a candidate lattice including the candidate element having the match score, the depth is the order of the input element, and the breadth is a rank of the candidate element for the input element.

5. A search method as claimed in claim 4, wherein the recognizer is a character recognizer.

6. A search method as claimed in claim 5, wherein the candidate element is a character, and the input element is supplied as a word to the character recognizer.

7. A search method as claimed in claim 5, wherein the candidate element is a character, and the input element is supplied as a sentence to the character recognizer.

8. A search method as claimed in claim 4, wherein the recognizer is a speech recognizer.

9. A search method as claimed in claim 8, wherein the candidate element is a syllable, a word, or a clause, and the input element is supplied as a word or a sentence to the speech recognizer.

10. A search method as claimed in claim 1, wherein the method comprises the steps of:

calculating a mean value of each score difference within each depth; and

grouping the nodes with corresponding search priority indices in groups within each depth according to whether the score differences are greater than the mean value,

in the search priority indexes calculating step (e), the search priority indexes are calculated based on the score differences, the mean value, and the breadth of the lattice, for each of the groups, and

in the searching step (f), the lattice is searched according to the search priority index of one of the groups which one of the nodes belongs to.

11. A search method as claimed in claim 10, wherein the breadth is defined by breadth i and the search priority index PI of the one of the groups in the breadth i is calculated according to the following equation:

space="preserve" listing-type="equation">PI=0;

for i=1, and PI=(ST.sub.i -SF.sub.i-1)/(mean value)×

e.sup.Ci ;

for i=2, 3, 4 . . . ,

wherein

ST_i ;

first score of a top node of a first group of the breadth i,

SF_i ;

second score of a final node of a second group of the breadth i, and

C;

constant.

12. A search method as claimed in claim 11, wherein each of the nodes is a candidate element for an input element generated by a recognizer to which is supplied the input element, the first score is a match score of the candidate element generated by the recognizer, the lattice is a candidate lattice including the candidate element having the match score, the depth is order of the input element, and the breadth is a rank of the candidate element for the input element.

13. A search method as claimed in claim 12, wherein the recognizer is a character recognizer.

14. A search method as claimed in claim 13, wherein the candidate element is a character, and the input element is supplied as a word to the character recognizer.

15. A search method as claimed in claim 13, wherein the candidate element is a character, and the input element is supplied as a sentence to the character recognizer.

16. A search method as claimed in claim 12, wherein the recognizer is a speech recognizer.

17. A search method as claimed in claim 16, wherein the candidate element is a syllable, a word, or a clause, and the input element is supplied as a word or a sentence to the speech recognizer.

18. A method of symbol recognition using a data processor, comprising the steps of:

(a) inputting a pattern data set into the data processor with the pattern data set representing an input symbol to be recognized;

(b) identifying with the data processor candidate patterns for the pattern data set;

(c) generating by the data processor similarity scores for the candidate patterns;

(d) assigning by the data processor the candidate patterns to nodes of a search tree with level depth and left to right position based on the similarity scores;

(e) determining by the data processor score differences between similarity scores of nodes at a same search tree level;

(f) calculating by the data processor search priority indexes according to the score differences; and

(g) determining by the data processor a candidate pattern best matching the pattern data set to recognize the input symbol by searching the search tree using the search priority indexes.