US5424947A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Natural language analyzing apparatus and method, and construction of a knowledge base for natural language analysis
Assignee: International Business Machines Corp
•
Filing: 1991-06-12
•
Granted: 1995-06-13
•
Expires: 2011-06-12
Abstract
Abstract A system for resolving structural ambiguities in syntactic analysis of natural language, which ambiguities are caused by prepositional phrase attachment, relative clause attachment, and other modifier-modifiee relationships in sentences. The system uses instances of dependency (modification relationship) structures extracted from a terminology dictionary as a knowledge base. Structural ambiguity is represented by indicating that a word in a sentence has several words as candidate modifiees. The system resolves such ambiguity by 1) first searching the knowledge base, which contains dependency information in the form of tree structures, for dependencies between the word and each of its possible modifiees, 2) then assigning an order of preference to these dependencies by means of a path search in the tree structures, and 3) finally selecting the most preferable dependency as the modifiee. The sentences can be analyzed by a parser and transformed into dependency structures by the system. The knowledge base can be constructed automatically, since the source of knowledge exists in the form of texts, and knowledge bootstrapping can be realized by adding the outputs of the system to its knowledge base.
Inventors
- 👤 Katashi Nagao
- 👤 Hiroshi Nomiyama
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 07:36
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/205; G06F40/211; G06F40/30
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
254 words
A programmed computer system for natural language analysis, comprising: (a) knowledge base means for storing information representing dependencies among words in sentences and information representing taxonym relationships of words, said dependencies information being in the form of first-type tree structures and said taxonym information being in the form of second-type tree structures; (b) table means, in said knowledge base means and responsive to the entry of a word thereto, for outputting information indicative of 1) a first-type tree structure in which said word appears, 2) node location information of said word in said first-type tree structure, and 3) information indicative of a second-type tree structure in which said word is contained as a hyponym; (c) means for judging structural unambiguity of a sentence input to the system; (d) means for extracting a modifier and modifiee pair of words for each possible dependency in a sentence judged to be structurally ambiguous by said judging means; (e) means for entering said modifier-modifiee pair of words into said table means and determining, on the basis of the information output by said table means, a path for each said modifier-modifiee pair of words with the path having a different word of said modifier-modifiee pair of words at opposite ends and including at least some words in the first-type tree structure; (f) means for calculating the path distance for each said modifier-modifiee pair of words; and (g) means for determining the most preferable dependency on the basis of said path distance calculated for each said modifier-modifee pair of words.
Claim 2
Dependent Claim
254 words
A programmed computer system for natural language analysis, comprising: (a) knowledge base means for storing information representing dependencies among words in sentences and information representing taxonym relationships of words, said dependencies information being in the form of first-type tree structures and said taxonym information being in the form of second-type tree structures; (b) table means, in said knowledge base means and responsive to the entry of a word thereto, for outputting information indicative of 1) a first-type tree structure in which said word appears, 2) node location information of said word in said first-type tree structure, and 3) information indicative of a second-type tree structure in which said word is contained as a hyponym; (c) means for judging structural unambiguity of a sentence input to the system; (d) means for extracting a modifier and modifiee pair of words for each possible dependency in a sentence judged to be structurally ambiguous by said judging means; (e) means for entering said modifier-modifiee pair of words into said table means and determining, on the basis of the information output by said table means, a path for each said modifier-modifiee pair of words with the path having a different word of said modifier-modifiee pair of words at opposite ends and including at least some words in the first-type tree structure; (f) means for calculating the path distance for each said modifier-modifiee pair of words; and (g) means for determining the most preferable dependency on the basis of said path distance calculated for each said modifier-modifee pair of words.
Claim 3
Dependent Claim
48 words
A system for natural language analysis according to claim 1, further comprising; (h) means for storing in said knowledge base means a first-type tree structure for an input sentence including said most preferable dependency determined by said determining means, and for renewing said table means in response thereto.
Claim 4
Dependent Claim
27 words
A system for natural language analysis according to claim 2 wherein said knowledge base means separately stores learned data and context data added by said storing means.
Claim 5
Dependent Claim
39 words
A system for natural language analysis according to claim 2 wherein said calculating means calculates said path distance on the basis of the degree of consistency between the path and a first-type tree structure added by said storing means.
Claim 6
Dependent Claim
24 words
A system for natural language analysis according to claim 1 wherein said table means is separately prepared for learned data and for context data.
Claim 7
Dependent Claim
28 words
A system for natural language analysis according to claim 1 wherein said calculating means calculates said path distance, based on the number of dependencies included in the path.
Claim 8
Dependent Claim
24 words
A system for natural language analysis according to claim 1 wherein said first-type tree structure is provided with semantic case data for each dependency.
Claim 9
Dependent Claim
40 words
A system for natural language analysis according to claim 7 wherein said calculating means calculates said path distance according to the consistency between the case relationship between a modifier and a candidate modifiee and the case relationship for the path.
Claim 10
Dependent Claim
56 words
A system for natural language analysis according to claim 8 wherein said calculating means calculates a dependency distance using the formula: ##EQU2## where n is a real number in the range 0<n<1 and is an heuristic parameter that represents the degree of unimportance of the context, and the other parameters have values of 1 or 0.
Claim 11
Dependent Claim
46 words
A system for natural language analysis according to claim 1 wherein said calculating means calculates said path distance, on the basis of the consistency of co-occurrence of a word included in an input sentence and a word included in said first-type tree structure for the path.
Claim 12
Dependent Claim
62 words
A system for natural language analysis according to claim 1 wherein said second-type tree structure is an isa tree having only two nodes corresponding to a hypernym and a hyponym, and wherein said entering means is responsive to an output of a hypernym of a word forming the pair, to iterate search for an isa tree including said hypernym as a hyponym.
Claim 13
Dependent Claim
20 words
A system for natural language analysis according to claim 1 wherein a synonym relationship is represented by two isa trees.
Claim 14
Dependent Claim
207 words
In a computer system including a knowledge base that stores first-type tree structures representing dependencies among words in sentences and second- type tree structures representing taxonym relationships of words and including a table responsive to the entry of a word for 1) outputting identification data of said first-type tree structure in which said word appears, 2) node location data of said word in said first-type tree structure, and 3) identification data of said second-type tree structure in which said word appears as a hyponym, a computer implemented natural language analysis method comprising the steps of: (a) judging the structural unambiguity of an incoming sentence; (b) extracting a modifier and modifiee pair of two words for each possible dependency in a sentence judged to be structurally ambiguous; (c) entering the two words of each said modifier-modifiee pair into said table means and for each said modifier-modifiee pair determining, on the basis of the output data, a path that has said two words of said modifier-modifiee pair at opposite ends and contains some of the words appearing in said first-type tree structure; (d) calculating the path distance for each pair; and (e) determining the most preferable dependency relationship, the basis of said path distance calculated for each said pair.
Claim 15
Dependent Claim
207 words
In a computer system including a knowledge base that stores first-type tree structures representing dependencies among words in sentences and second- type tree structures representing taxonym relationships of words and including a table responsive to the entry of a word for 1) outputting identification data of said first-type tree structure in which said word appears, 2) node location data of said word in said first-type tree structure, and 3) identification data of said second-type tree structure in which said word appears as a hyponym, a computer implemented natural language analysis method comprising the steps of: (a) judging the structural unambiguity of an incoming sentence; (b) extracting a modifier and modifiee pair of two words for each possible dependency in a sentence judged to be structurally ambiguous; (c) entering the two words of each said modifier-modifiee pair into said table means and for each said modifier-modifiee pair determining, on the basis of the output data, a path that has said two words of said modifier-modifiee pair at opposite ends and contains some of the words appearing in said first-type tree structure; (d) calculating the path distance for each pair; and (e) determining the most preferable dependency relationship, the basis of said path distance calculated for each said pair.
Claim 16
Dependent Claim
45 words
A natural language analysis method according to claim 13 further comprising the step of: (f) storing in said knowledge base a first-type tree structure for an input sentence including said most preferable dependency determined by said step (e) and renewing said table in response thereto.
Claim 17
Dependent Claim
25 words
A natural language analysis method according to claim 14 wherein said knowledge base separately stores learned data and context data added by said step (f).
Claim 18
Dependent Claim
21 words
A natural language analysis method according to claim 14 wherein said table is separately prepared for learned data and context data.
Claim 19
Dependent Claim
28 words
A natural language analysis method according to claim 13 wherein said step (d) calculates said distance, on the basis of the number of dependencies included in the path.
Claim 20
Dependent Claim
23 words
A natural language analysis method according to claim 13 wherein said first-type tree structure is provided with semantic case data for each dependency.
Claim 21
Dependent Claim
38 words
A natural language analysis method according to claim 18 wherein said step (d) calculates said distance according to the consistency between the case relationship of a modifier and a candidate modifiee and the case relationship for the path.
Claim 22
Dependent Claim
41 words
A natural language analysis method according to claim 13 wherein said step (d) calculates said distance according to the co-occurrence consistency of a word included in said input sentence and a word included in said first-type tree structure for the path.
Claim 23
Dependent Claim
35 words
A natural language analysis method according to claim 13 wherein said step (d) calculates said distance according to the degree of consistency between the path and a first-type tree structure added by said step (f).
Claim 24
Dependent Claim
61 words
A natural language analysis method according to claim 13 wherein said second-type tree structure is an isa tree having only two nodes corresponding to a hypernym and a hyponym, and wherein said step (c) is responsive to an output of a hypernym of a word forming the pair, to iterate search for an isa tree including said hypernym as a hyponym.
Claim 25
Dependent Claim
20 words
A natural language analysis method according to claim 13 wherein a synonym relationship is represented by two isa tree structures,
Claim 26
Independent Claim
75 words
A method for constructing a knowledge base in a computer for natural language analysis comprising the computer implemented steps of:. (a) preparing a knowledge base that stores tree structures representing dependencies among words in sentences; (b) determining the most preferable of the possible dependencies for an incoming sentence by using data in said knowledge base; and (c) storing in said knowledge base a tree structure for the incoming sentence that includes said most preferable dependency.
Claim 27
Independent Claim
75 words
A method for constructing a knowledge base in a computer for natural language analysis comprising the computer implemented steps of:. (a) preparing a knowledge base that stores tree structures representing dependencies among words in sentences; (b) determining the most preferable of the possible dependencies for an incoming sentence by using data in said knowledge base; and (c) storing in said knowledge base a tree structure for the incoming sentence that includes said most preferable dependency.
Claim 28
Dependent Claim
27 words
A method for constructing a knowledge base according to claim 24 wherein said knowledge base separately stores learned data and context data added by said step (c).
Claim 29
Independent Claim
119 words
A method of constructing a knowledge base in a computer for natural language analysis comprising the computer implemented steps of: (a) preparing a database for storing tree structures representing dependencies among words in sentences, and preparing a table responsive to the entry of a word for outputting identification data of at least one of said tree structures containing said word and node location data of said word in said tree structure; (b) determining the most preferable of the possible dependencies for an ambiguous sentence by using data in said database and said table; and (c) storing in said database a tree structure for the ambiguous sentence that includes said most preferable dependency and renewing said table in response thereto.
Claim 30
Independent Claim
119 words
A method of constructing a knowledge base in a computer for natural language analysis comprising the computer implemented steps of: (a) preparing a database for storing tree structures representing dependencies among words in sentences, and preparing a table responsive to the entry of a word for outputting identification data of at least one of said tree structures containing said word and node location data of said word in said tree structure; (b) determining the most preferable of the possible dependencies for an ambiguous sentence by using data in said database and said table; and (c) storing in said database a tree structure for the ambiguous sentence that includes said most preferable dependency and renewing said table in response thereto.
Claim 31
Dependent Claim
27 words
A method for constructing a knowledge base according to claim 26 wherein said knowledge base separately stores learned data and context data added by said step (c).
Claim 32
Dependent Claim
24 words
A method for constructing a knowledge base according to claim 26 wherein said table is separately prepared for learned data and for context data.
Claim 33
Dependent Claim
159 words
A programmed computer system for natural language analysis, comprising: means for receiving respective syntactic structures including attachments indicative of ambiguities, derived from natural language sentences to be analyzed, and for converting said syntactic structures into dependency structures indicative of the dependency between words in said sentences; knowledge base means for storing information representing dependencies between words in sentences and information representing taxonym relationships of words, said information being in the form of tree structures; means for extracting dependencies from each dependency structure and producing respective multiple possible candidate dependencies; means for searching said knowledge base means for stored information representing dependencies related to said candidate dependencies and for selecting the most preferable candidate dependency for each dependency structure based on a comparison of dependency distances derived from a path search in said tree structures of said knowledge base means; and means for transforming each dependency structure using such dependency structures most preferable candidate dependency to remove the ambiguities therein.
Claim 34
Dependent Claim
159 words
A programmed computer system for natural language analysis, comprising: means for receiving respective syntactic structures including attachments indicative of ambiguities, derived from natural language sentences to be analyzed, and for converting said syntactic structures into dependency structures indicative of the dependency between words in said sentences; knowledge base means for storing information representing dependencies between words in sentences and information representing taxonym relationships of words, said information being in the form of tree structures; means for extracting dependencies from each dependency structure and producing respective multiple possible candidate dependencies; means for searching said knowledge base means for stored information representing dependencies related to said candidate dependencies and for selecting the most preferable candidate dependency for each dependency structure based on a comparison of dependency distances derived from a path search in said tree structures of said knowledge base means; and means for transforming each dependency structure using such dependency structures most preferable candidate dependency to remove the ambiguities therein.
Claim 35
Dependent Claim
50 words
A system for natural language analysis as in claim 29 wherein said knowledge base comprises table means responsive to the entry of a word for outputting identification data of at least one of said tree structures containing said word and node location data of said word in said tree structure.
Claim 36
Dependent Claim
54 words
A system for natural language analysis as in claim 29 wherein said dependency distances are determined using the formula: ##EQU3## where n is a real number in the range 0<n<1 and is an heuristic parameter that represents the degree of unimportance of the context, and the other parameters have values of 1 or 0.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-06-12 | 1998-12-12 | 1999-06-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-06-12 | 2002-12-12 | 2003-06-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-06-12 | 2006-12-12 | 2007-06-13 | $7700.00 | Window Closed / Lapsed |