Method and apparatus for concept-based classification of natural language discourse

• US 8,055,608 B1
• Filed: 05/29/2006
• Issued: 11/08/2011
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Netbase Solutions, Inc.
• Original Assignee: Netbase Solutions, Inc.
• Inventors: Rehling, John Andrew, Osofsky, Michael Jacob
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Kim T
• Application Number:
  US11/420,782
• Time in Patent Office: 1,989 Days
• Field of Search: 707/101, 707/803, 704/1
• US Class Current: 707/101
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

Pinnacle concepts are not amenable to detection by the use of keywords. A unit of natural language discourse (UNLD) “refers” to a pinnacle concept “C” when that UNLD uses linguistic expressions in such a way that “C” is regarded as expressed, used or invoked by an ordinary reader of “L.” A reference can have a “reference level” value that is proportional to: the “strength” with which the pinnacle concept is referenced, the probability that a pinnacle concept is referenced or both strength and probability. Pinnacle concepts can be divided into Quantifiers and non-Quantifiers. A Quantifier can modify the reference level assigned to a non-Quantifier. A concept “C,” that is determined to be referenced by a UNLD “x,” after application of its Quantifiers, is said to be asserted by “x.” Concept-based classification is the identification of whether a pinnacle concept “C” is asserted by a UNLD. Concept-based classification can be used for concept-based search.

Claims

1. A method, performed by computing hardware and programmable memory, for determining whether a first pinnacle concept is referenced by a first unit of natural language discourse, comprising:

parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

adding at least one concept-value pair, each of which indicates a reference to a same non-Quantifier concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features is approximately complete with respect to the non-Quantifier concept;

adding at least one concept-value pair, each of which indicates a reference to a same Quantifier concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features is approximately complete with respect to the Quantifier concept;

propagating the at least one concept-value pair for the Quantifier concept;

identifying a first node of the first parse structure that has at least one concept-value pair for the non-Quantifier concept and at least one concept-value pair for the Quantifier concept;

determining a first value to be scaled from the least one concept-value pair for the non-Quantifier concept;

determining a first scaling value from the least one concept-value pair for the Quantifier concept;

scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

propagating the at least one concept-value pair for the non-Quantifier concept.

2. The method of claim 1, wherein a sufficient approximation to completeness, for the first set of linguistic features, is determined empirically.

3. The method of claim 1, wherein the first set of linguistic features is determined utilizing machine learning.

4. The method of claim 1, wherein the first set of linguistic features is determined utilizing at least one language-reference tool to find similar additional linguistic features from at least one known linguistic feature.

5. The method of claim 1, wherein the non-Quantifier concept is selected from the group consisting of Bad, Good, Need and Purchase.

6. The method of claim 1, wherein the Quantifier concept is selected from the group consisting of Intensify, Increase, Diminish, Decrease, Negation and Solution.

7. The method of claim 1, wherein the first unit of natural language discourse is a sentence.

8. The method of claim 1, wherein a sub-unit of the first unit of natural language discourse is a lexical unit.

9. The method of claim 1, wherein the first parse structure is a matrix representation.

10. The method of claim 1, wherein the first linguistic feature is comprised of at least one lexical unit.

11. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the non-Quantifier concept further comprises:

keeping separate the propagation of each added concept-value pair that indicates a reference to the non-Quantifier concept.

12. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the non-Quantifier concept further comprises:

propagating a concept-value pair, that indicates a reference to the non-Quantifier concept, from a second node to a third node if there is an edge from the second node to the third node.

13. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the non-Quantifier concept further comprises:

attenuating a value portion, of a concept-value pair that indicates a reference to the non-Quantifier concept, when the concept-value pair propagates from a second node to a third node.

14. The method of claim 13, wherein the step of attenuating further comprises:

multiplying the value portion by an attenuation coefficient.

15. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the Quantifier concept further comprises:

keeping separate the propagation of each added concept-value pair that indicates a reference to the Quantifier concept.

16. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the Quantifier concept further comprises:

propagating a concept-value pair, that indicates a reference to the non-Quantifier concept, from a second node to a third node if an edge, from the second node to the third node, is of a type selected from the group consisting of edges where one node is a verb and the other node is an agent of the verb, edges where one node is a verb and the the other node is a patient of the verb and edges where one node is a modifier and the other node is an object of the modifier.

17. The method of claim 1, wherein the step of propagating the at least one concept-value pair for the Quantifier concept further comprises:

holding a value portion, of a concept-value pair that indicates a reference to the non-Quantifier concept, constant when the concept-value pair propagates from a second node to a third node.

18. The method of claim 1, further comprising the following step:

taking a maximum of a set of values resulting from extracting a value portion of each concept-value pair, at a second node, for the non-Quantifier concept.

19. The method of claim 1, further comprising the following step:

taking a sum of a set of values resulting from extracting a value portion of each concept-value pair, at the first node, for the Quantifier concept.

20. The method of claim 19, further comprising:

using the sum as an exponent to a base value, wherein the base value is dependent on the type of the Quantifier concept.

21. The method of claim 20, wherein the base value is selected from the group consisting of a value less than one, a value greater than one a value of negative one.

22. The method of claim 19, further comprising:

thresholding the value portion, of each concept-value pair, before including it in the sum of the set of values.

23. The method of claim 1, wherein the step of scaling further comprises:

limiting the first scaled value to be less than a maximum value.

24. The method of claim 1, wherein the step of scaling further comprises:

inverting the non-Quantifier concept when the first scaling value indicates that a negation is to be performed.

25. The method of claim 24, wherein the step of inverting further comprises:

changing the non-Quantifier concept to a correlative non-Quantifier concept.

26. The method of claim 24, wherein the first scaling value indicates that a negation is to be performed when the first scaling value is less than zero.

27. The method of claim 1, wherein the non-Quantifier concept is a Characteristic concept.

28. A data processing system, made with computing hardware and programmable memory, for determining whether a first pinnacle concept is referenced by a first unit of natural language discourse, comprising the following sub-systems:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish adding at least one concept-value pair, each of which indicates a reference to a same non-Quantifier concept, to at least one node of the the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features is approximately complete with respect to the non-Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish adding at least one concept-value pair, each of which indicates a reference to a same Quantifier concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features is approximately complete with respect to the Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish propagating the at least one concept-value pair for the Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish identifying a first node of the first parse structure that has at least one concept-value pair for the non-Quantifier concept and at least one concept-value pair for the Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish determining a first value to be scaled from the least one concept-value pair for the non-Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish determining a first scaling value from the least one concept-value pair for the Quantifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish propagating the at least one concept-value pair for the non-Quantifier concept.

29. A computer program on a non-transitory computer readable medium, having computer-readable code devices embodied therein, for determining whether a first pinnacle concept is referenced by a first unit of natural language discourse, the computer program comprising

computer readable program code devices configured to accomplish parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

computer readable program code devices configured to accomplish adding at least one concept-value pair, each of which indicates a reference to a same non-Quantifier concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features is approximately complete with respect to the non-Quantifier concept;

computer readable program code devices configured to accomplish adding at least one concept-value pair, each of which indicates a reference to a same Quantifier concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features is approximately complete with respect to the Quantifier concept;

computer readable program code devices configured to accomplish propagating the at least one concept-value pair for the Quantifier concept;

computer readable program code devices configured to accomplish identifying a first node of the first parse structure that has at least one concept-value pair for the non-Quantifier concept and at least one concept-value pair for the Quantifier concept;

computer readable program code devices configured to accomplish determining a first value to be scaled from the least one concept-value pair for the non-Quantifier concept;

computer readable program code devices configured to accomplish determining a first scaling value from the least one concept-value pair for the Quantifier concept;

computer readable program code devices configured to accomplish scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

computer readable program code devices configured to accomplish propagating the at least one concept-value pair for the non-Quantifier concept.

30. A method, performed by computing hardware and programmable memory, for determining whether a concept is referenced by a first unit of natural language discourse, comprising:

parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

adding at least one concept-value pair, each of which indicates a reference to a same first concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features contains many linguistic features;

adding at least one concept-value pair, each of which indicates a reference to a same modifier concept that can modify a reference level assigned to the first concept, to at least one node of the first parse structure, wherein each reference to the modifier concept is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features contains many linguistic features;

propagating the at least one concept-value pair for the modifier concept;

identifying a first node of the first parse structure that has at least one concept-value pair for the first concept and at least one concept-value pair for the modifier concept;

determining a first value to be scaled from the least one concept-value pair for the first concept;

determining a first scaling value from the least one concept-value pair for the modifier concept;

scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

propagating the at least one concept-value pair for the first concept.

33. The method of claim 30, wherein the first set of linguistic features is approximately complete with respect to the first concept and the second set of linguistic features is approximately complete with respect to the modifier concept.

34. The method of claim 30, wherein the first concept is a non-Quantifier concept and the modifier concept is a Quantifier concept.

31. A data processing system, made with computing hardware and programmable memory, for determining whether a concept is referenced by a first unit of natural language discourse, comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish adding at least one concept-value pair, each of which indicates a reference to a same first concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features contains many linguistic features;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish adding at least one concept-value pair, each of which indicates a reference to a same modifier concept that can modify a reference level assigned to the first concept, to at least one node of the first parse structure, wherein each reference to the modifier concept is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features contains many linguistic features;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish propagating the at least one concept-value pair for the modifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish identifying a first node of the first parse structure that has at least one concept-value pair for the first concept and at least one concept-value pair for the modifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish determining a first value to be scaled from the least one concept-value pair for the first concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish determining a first scaling value from the least one concept-value pair for the modifier concept;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish propagating the at least one concept-value pair for the first concept.

32. A data processing system, made with computing hardware and programmable memory, for determining whether a concept is referenced by a first unit of natural language discourse, comprising:

a means for parsing the first unit of natural language discourse into a first parse structure that represents each sub-unit, of the first unit of natural language discourse, by a node;

a means for adding at least one concept-value pair, each of which indicates a reference to a same first concept, to at least one node of the first parse structure, wherein each reference is determined by identifying an occurrence of a first linguistic feature from a first set of linguistic features and the first set of linguistic features contains many linguistic features;

a means for adding at least one concept-value pair, each of which indicates a reference to a same modifier concept that can modify a reference level assigned to the first concept, to at least one node of the first parse structure, wherein each reference to the modifier concept is determined by identifying an occurrence of a second linguistic feature from a second set of linguistic features and the second set of linguistic features contains many linguistic features;

a means for propagating the at least one concept-value pair for the modifier concept;

a means for identifying a first node of the first parse structure that has at least one concept-value pair for the first concept and at least one concept-value pair for the modifier concept;

a means for determining a first value to be scaled from the least one concept-value pair for the first concept;

a means for determining a first scaling value from the least one concept-value pair for the modifier concept;

a means for scaling the first value to be scaled with the first scaling value to produce a first scaled value; and

a means for propagating the at least one concept-value pair for the first concept.