Patent US5416892A successfully refreshed from Google Patents.
US5416892A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Best first search considering difference between scores
Assignee: Fujitsu Ltd
•
Filing: 1993-08-23
•
Granted: 1995-05-16
•
Expires: 2013-08-23
Abstract
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.
Inventors
- 👤 Kyung-ho Loken-Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:07
CPC Classifications
G; G10; G10L; G10L15/00; G10L15/08; G10L15/14; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9024; G06F18/00; G06F18/20; G06F18/29; G06F18/295; G06V; G06V30/00; G06V30/10; G06V30/32; G06V30/36; G06V30/373
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
226 words
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.
Claim 2
Independent Claim
226 words
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.
Claim 3
Dependent Claim
48 words
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.
Claim 4
Dependent Claim
71 words
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: 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.
Claim 5
Dependent Claim
95 words
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.
Claim 6
Dependent Claim
15 words
A search method as claimed in claim 4, wherein the recognizer is a character recognizer.
Claim 7
Dependent Claim
28 words
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.
Claim 8
Dependent Claim
28 words
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.
Claim 9
Dependent Claim
15 words
A search method as claimed in claim 4, wherein the recognizer is a speech recognizer.
Claim 10
Dependent Claim
36 words
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.
Claim 11
Dependent Claim
113 words
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.
Claim 12
Dependent Claim
93 words
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: 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.
Claim 13
Dependent Claim
83 words
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.
Claim 14
Dependent Claim
15 words
A search method as claimed in claim 12, wherein the recognizer is a character recognizer.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
28 words
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.
Claim 17
Dependent Claim
15 words
A search method as claimed in claim 12, wherein the recognizer is a speech recognizer.
Claim 18
Dependent Claim
36 words
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.
Claim 19
Independent Claim
152 words
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.
Claim 20
Independent Claim
152 words
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.
References Cited (Backward Citations)
US4555796A
Cited
US4596031A
Cited
US4468756A
Cited
US4658429A
Cited
US4718088A
Cited
US4979101A
Cited
US4713777A
Cited
US4718094A
Cited
US4765763A
Cited
US4748670A
Cited
US4783803A
Cited
US4805100A
Cited
US4770843A
Cited
US4899290A
Cited
US5185813A
Cited
US5133012A
Cited
US5067165A
Cited
US5029223A
Cited
US5125022A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-15 | 1998-11-14 | 1999-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-15 | 2002-11-14 | 2003-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-15 | 2006-11-14 | 2007-05-16 | $7700.00 | Window Closed / Lapsed |