Natural-language processing system using a large corpus

• US 7,392,174 B2
• Filed: 03/20/2001
• Issued: 06/24/2008
• Est. Priority Date: 03/20/2000
• Status: Expired due to Fees

• Current Assignee: Robert J. Freeman
• Original Assignee: Robert J. Freeman
• Inventors: Freeman, Robert J.
• Primary Examiner(s): Hudspeth; David R.
• Assistant Examiner(s): Ng; Eunice
• Application Number:
  US10/239,455
• Publication Number:
  US 20040024583A1
• Time in Patent Office: 2,653 Days
• Field of Search: 704/1, 704/4, 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A computer-parsing system using vectors (lists) to represent natural-language elements, providing a robust, distributed way to score grammaticality of an input string by using as a source material a large corpus of natural-language text. The system uses recombining of asymmetric associations of syntactically similar strings to form the vectors. The system uses equivalence lists for subparts of the string to build equivalence lists for longer strings in an order controlled by the potential parse to be scored. The power of recombination of vector elements in building longer strings provides a means of representing collocational complexity. Grammaticality scoring is based upon the number and similarity of the vector elements.

Claims

1. A computer system, using a provided corpus of linear natural-language elements of natural language text string data in a subject language and an input string of natural-language elements in the subject language, for assisting natural-language processing, comprising, in combination:

a) for a first adjoining pair, comprising a first pair element and a second pair element, of such natural-language elements of such input string, finding, from such string data from such corpus, a first listing of each such element syntactically related to such first pair element and a second listing of each such element syntactically related to such second pair element;

b) from matching each such first-listing element with each such second-listing element, making a matched-pairs third listing by finding which matched pairs of said matching are found in such string data from such corpus;

c) for such matched pairs of such matched-pairs third listing, finding, from such string data from such corpus, a recombined fourth listing of each fourth such natural-language element syntactically related to any such matched pair of said third listing; and

d) scoring each such natural-language element of such fourth listing, such scoring comprising scoring each element, as it is related to combinations between other elements.

2. The computer system according to claim 1 further comprising:

a) for such fourth natural-language elements of such fourth listing, finding, from such string data from such corpus, a fifth listing of each such natural-language element syntactically related to any such fourth natural-language element.

3. The computer system according to claim 2 further comprising:

a) scoring each such natural-language element of such fifth listing, such scoring comprising counting the number of occurrences of each such natural-language element of such fifth listing in such string data from such corpus.

4. The computer system according to claim 2 further comprising:

a) for such nth natural-language elements of such nth listing, finding, from such string data from such corpus, an (n+1)th listing of each such natural-language element syntactically related to any such nth natural-language element.

5. The computer system according to claim 4 further comprising:

a) scoring each such natural-language element of such (n+1)th listing, such scoring comprising counting the number of occurrences of each such natural-language element of such (n+1)th listing in such string data from such corpus.

6. The computer system according to claim 1 further comprising:

a) for a second adjoining pair, comprising such first adjoining pair as a second first pair element and another natural-language element adjoining such first adjoining pair as a second second pair element, of such natural-language elements of such input string, finding, from such string data from such corpus, a second first listing of each such element syntactically related to such second first pair element and a second second listing of each such element syntactically related to such second second pair element;

b) from matching each such second first-listing element with each such second second-listing element, making a matched-pairs second third listing by finding which matched pairs of said matching are found in such string data from such corpus;

c) for such matched pairs of such matched-pairs second third listing, finding, from such string data from such corpus, a second fourth listing of each second fourth such natural-language element syntactically related to any such matched pair of such second third listing; and

d) scoring each such natural-language element of such fourth listing, such scoring comprising scoring each element, as it is related to combinations between other elements.

7. The computer system according to claim 6 further comprising:

a) for an (n+1)th adjoining pair, comprising such nth adjoining pair as an (n+1)th first pair element and another natural-language element adjoining such nth adjoining pair as an (n +1)th second pair element, of such natural-language elements of such input string, finding from such string data from such corpus, an (n+1)th first listing of each such element syntactically related to such (n+1)th first pair element and an (n+1)th second listing of each such element syntactically related to such (n+1)th second pair element;

b) from matching each such (n+1)th first-listing element with each such (n+1)th second-listing element, making a matched-pairs (n+1)th third listing by finding which matched pairs of said matching are found in such string data from such corpus;

c) for such matched pairs of such matched-pairs (n+1)th third listing, finding, from such string data from such corpus, an (n+1)th fourth listing of each (n+1)th fourth such natural-language element syntactically related to any such matched pair of such (n+1)th third listing; and

d) scoring each such natural-language element of such fourth listing, such scoring comprising scoring each element, as it related to combinations between other elements.

8. The computer system according to each of claim 1 further comprising:

a) repeating such steps of claim 1 while considering

i. such original first adjoining pair as a new first pair element in such repeating,

ii. such original fourth listing as a new first listing in such repeating, and

iii. a new natural-language element adjoining, in such input string, such new first pair element as a new second pair element, thereby providing a new first adjoining pair,

iv. thereby providing a new fourth listing in association with such new first adjoining pair.

9. The computer system according claim 8 further comprising:

a) re-performing steps a)i) through a)iv) of claim 8 while considering

i. such new first adjoining pair as a first replacement first pair element in such re-performing,

ii. such new fourth listing as a first replacement first listing in such re-performing, and

iii. a further new natural-language element adjoining, in such input string, such first replacement first pair element as a first replacement second pair element, thereby providing a first replacement first adjoining pair,

iv. thereby providing a first replacement fourth listing in association with such first replacement first adjoining pair.

10. The computer system according claim 9 further comprising:

a) further continuing to perform, for such entire input string, steps a)i) through a)iv) of claim 9 while considering

i. such nth first adjoining pair as an (n+1)th replacement first pair element in such further performing,

ii. such nth fourth listing as an (n+1)th replacement first listing in such further performing, and

iii. a further new natural-language element adjoining, in such input string, such (n+1)th replacement first pair element as an (n+1)th replacement second pair element, thereby providing an (n+1)th replacement first adjoining pair,

iv. thereby providing an (n+1)th replacement fourth listing in association with such (n+1)th replacement first adjoining pair.

11. The computer system according to claim 10 further comprising:

a) for an (n+1)th adjoining pair, comprising such nth adjoining pair as an (n+1)th first pair element and another natural-language element adjoining such nth adjoining pair as an (n +1)th second pair element, of such natural-language elements of such input string, finding, from such string data from such corpus, an (n+1)th first listing of each such element syntactically related to such (n+1)th first pair element and an (n+1)th second listing of each such element syntactically related to such (n+1)th second pair element;

b) from matching each such (n+1)th first-listing element with each such (n+1)th second-listing element, making a matched-pairs (n+1)th third listing by finding which matched pairs of said matching are found in such string data from such corpus;

c) for such matched pairs of such matched-pairs (n+1)th third listing, finding, from such string data from such corpus, an (n+1)th fourth listing of each (n+1)th fourth such natural-language element syntactically related to any such matched pair of such (n+1)th third listing; and

d) scoring each such natural-language element of such (n+1)th fourth listing, such scoring comprising scoring each element, as it is related to combinations between other elements; and

e) wherein such scores for each such natural language element of such (n+1)th fourth listing are added to determine a scoring for a string comprising such (n+1)th replacement first adjoining pair.

12. The computer system according to claim 11 wherein such computer system is applied to possible ordered string subcombinations of at least two potential parses of such natural-language elements of such input string and a highest such scoring among such potential parses is used to determine maximum grammaticality among such potential parses.

13. The computer system according to each of claims 1, 3, 5, 6, 7, and 11 wherein such scoring of each such fourth list element comprises:

a) the product of

i. a statistical measure of the relationship between each such element of such first listing syntactically related to such first pair element and such first pair element;

ii. a statistical measure of the relationship between each such element of such second listing syntactically related to such second pair element and such second pair element;

iii. a statistical measure of the relationship between such first and second pair elements;

iv. a statistical measure of the relationship between each matched pair of such matched-pairs third listing and each fourth such natural-language element of such fourth listing; and

b) a sum of each such product for each same fourth list element in the list of each such third list element.

18. The computer system according to each of claims 1, 5, 6, 7-10, 11, 12 and 14-16 wherein each such pair element comprises at least one word.

19. The computer system according to each of claims 1, 5, 6, 7-10, 11, 12 and 14-16 wherein each such pair element comprises at least two words.

14. A computer system, using a provided corpus of linear natural-language elements of natural language text string data in a subject language and an input string, to be parsed, of natural-language elements in the subject language, for assisting natural-language parsing, comprising, in combination:

a) for each of at least two natural-language input subcombinations which are potential subparses of such input string, building a recombined list of all corpus strings syntactically related to such each input string subcombination, where the recombination of such recombined list is a paradigmatic recombination of words related by co-occurrence in sequence, representing longer strings using different paradigmatic recombinations of shorter strings;

b) from such recombined lists, in different orders for each potential parse of said input string, building to a final recombined list for each such potential parse of such input string; and

c) from the number and quality of entries in each respective such final recombined list, scoring the grammaticality of such respective potential parse.

15. The computer system according to claim 14 wherein such scoring comprises adding scores for each such entry to obtain a score for such potential parse.

16. A computer system, using a provided corpus of linear natural-language elements of natural language text string data in a subject language and an input string of natural-language elements in the subject language, for assisting natural-language processing, comprising, in combination:

a) for a first adjoining pair, comprising a first pair element and a second pair element, of such natural-language elements of such input string, finding, from such string data from such corpus, a first listing of each such element syntactically related to such first pair element and a second listing of each such element syntactically related to such second pair element; and

b) from matching each such first-listing element with each such second-listing element, making a matched-pairs third listing by finding which matched pairs of said matching are found in such string data from such corpus;

c) wherein at least one of said first adjoining pair comprises at least a pair of natural-language elements and the corresponding listing includes at least some more primitive elements, representing longer strings using different paradigmatic recombinations of shorter strings, where such recombination is a paradigmatic recombination of words related by co-occurrence in sequence.

17. The computer system according to claim 16 wherein:

a) at least one of such first pair element and such second pair element comprises at least a pair of words.

20. A computer-readable medium for a computer system, using a provided corpus of linear natural-language elements of natural language text string data in a subject language and an input string of natural-language elements in the subject language, for assisting in natural-language processing whose contents cause a computer system to determine a grammatical parse by:

a) for each of at least two natural-language input subcombinations which are potential subparses of such input string, building a recombined list of all corpus strings syntactically related to such each input string subcombination, where the recombination of such recombined list is a paradigmatic recombination of words related by co-occurrence in sequence, representing longer strings using different paradigmatic recombinations of shorter strings;

b) from such recombined lists, in different orders for each potential parse of said input string, building to a final recombined list for each such potential parse of such input string; and

c) from the number and quality of entries in each respective such final recombined list, scoring the grammaticality of such respective potential parse.

21. A computer-implemented natural-language system for a computer system, using a provided corpus of linear natural-language elements of natural language text string data in a subject language and an input string of natural-language elements in the subject language, for assisting in natural-language processing comprising:

a) for each of at least two natural-language input subcombinations which are potential subparses of such input string, means for building a recombined list of all corpus strings syntactically related to such each input string subcombination, where the recombination of such recombined list is a paradigmatic recombination of words related by co-occurrence in sequence, representing longer strings using different paradigmatic recombinations of shorter strings;

b) means for building, from such recombined lists, in different orders for each potential parse of said input string, to a final recombined list for each such potential parse of such input string; and

c) means for scoring, from the number and quality of entries in each respective such final recombined list,the grammaticality of such respective potential parse.

22. A method for finding structure in pattern recognition systems, by recombining scores of elements of vectors, lists, network associations, or other method of relating elements, where by “

recombining”

is meant changing scores of individual elements as they are related to combinations of other elements; and

representing combinations of elements using scores of many individual elements;

scoring each element as it is related to combinations between other elements.

23. The method of claim 22, for more than one of several orders of iteration of said recombination, to find a best order, if such exists, whereby the order of iteration of said recombination is meant the order of combining elements to be represented using scores of many individual elements, where “

best”

is defined as the highest total score of individual elements.

24. The method of claim 22, where elements are related by co-occurrence in sequence.