Method and apparatus for processing natural language using auto-intersection

• US 20050107999A1
• Filed: 05/21/2004
• Published: 05/19/2005
• Est. Priority Date: 11/14/2003
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kempe, Andre, Nicart, Florent, Guingne, Franck
• Granted Patent: US 7,386,441 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30

Abstract

Operations for weighted and non-weighted multi-tape automata are described for use in natural language processing tasks such as morphological analysis, disambiguation, and entity extraction.

Claims

1. In a system for processing natural language, a method for intersecting a first selected tape and a second selected tape of a selected path of a multi-tape automaton (MTA) having a plurality of n tapes and a plurality of paths, comprising:

(a) generating a string tuple <

s₁, . . . , s_n>

having a string s for each of the n tapes of the selected path of the MTA;

(b) comparing the string s_j of the first selected tape with the string s_k of the second selected tape in the string tuple generated at (a);

(c) if the strings s_j and s_k equal at (b), retaining the string tuple in the MTA;

(d) if the strings s_j and s_k do not equal at (b), restructuring the MTA to remove the string tuple while retaining other paths in the MTA;

(e) repeating (a)-(d) for at least another path of the MTA by specifying the one or more paths in turn as the selected path;

(f) outputting the MTA restructured at (d) in which all paths in the MTA are removed except for those having equal strings on the first selected tape and the second selected tape of the string tuples generated at (a).

2. The method according to claim 1, wherein each tape of the MTA comprises elements of at least two natural languages.

3. The method according to claim 1, wherein the MTA at (a) is the cross product of two input multi-tape automata.

4. The method according to claim 3, further comprising repeating (a)-(f) for at least one or both of a third selected tape and a fourth selected tape of the MTA, wherein no more than one is from a set consisting of the first selected tape and the second selected tape of the MTA.

5. The method according to claim 3, further comprising removing redundant strings in the string tuples of the restructured MTA.

6. The method according to claim 1, wherein the MTA has weighted transitions.

7. The method according to claim 6, wherein the weights of the transitions of the MTA are probabilities.

8. The method according to claim 1, wherein restructuring the MTA to remove the string tuple at (d) further comprises removing a transition of the MTA.

9. The method according to claim 1, wherein the MTA has one or more cycles.

10. The method according to claim 1, wherein (a)-(f) is performed to carry out one or more of morphological analysis, part-of-speech tagging, disambiguation, and entity extraction.

11. The method according to claim 1, wherein (a)-(f) is performed by computing a delay between the strings of the two tapes.

12. The method according to claim 11, further comprising using the computed delay to determine whether the MTA is regular.

13. The method according to claim 12, wherein the MTA is regular if the computed delay does not exceed a predetermined limit at any state of the MTA.

14. The method according to claim 12, wherein if the MTA is determined to be regular then the MTA output at (f) is a complete solution, otherwise the MTA output at (f) is a partial solution.

15. In a system for processing natural language, a method for intersecting a first tape and a second tape of an input multi-tape automaton (MTA) having a plurality of tapes and a plurality of paths, comprising:

(a) computing a first limit and a second limit of the input MTA;

(b) constructing an output MTA that intersects the first tape and the second tape using the second limit to delimit its construction;

said constructing removing transitions along paths in the output MTA except for those transitions of paths having similar labels on the first selected tape and the second selected tape;

(c) determining if the output MTA is regular using the first limit;

(d) if the output MTA is determined to be regular at (c), the output MTA being provided as a complete solution to the intersection of the first tape and the second tape of the input MTA;

(e) if the output MTA is determined not to be regular at (c), the output MTA being provided as a partial solution to the intersection of the first tape and the second tape of the input MTA.

16. The method according to claim 15, further comprising computing the first limit by compiling a first maximum delay by traversing the input MTA automaton and measuring delays on all its paths.

17. The method according to claim 16, further comprising computing the second limit by compiling a second maximum delay similar to the first delay while traversing an additional cycle of the input MTA.

18. The method according to claim 15, wherein the MTA is the cross product of a first MTA and a second MTA.

19. The method according to claim 18, further comprising repeating (a)-(e) for at least one or both of a third selected tape and a fourth selected tape of the MTA, wherein no more than one is from a set consisting of the first selected tape and the second selected tape of the MTA.

20. The method according to claim 15, wherein the MTA has weighted transitions.

21. The method according to claim 15, wherein (a)-(e) is performed to carry out one or more of morphological analysis, part-of-speech tagging, disambiguation, and entity extraction.

22. In a system for processing natural language, a method for intersecting a first tape and a second tape of a multi-tape automaton (MTA) having a plurality of n tapes and a plurality of paths, comprising:

(a) generating a string tuple <

s₁, . . . , s_n>

having a string s for each of the n tapes of each path of the MTA;

(b) comparing the string s_j of the first tape with the string s_k of the second tape in the string tuple;

(c) if the strings s_j and s_k equal at (b), retaining the string tuple in the MTA;

(d) if the strings s_j and s_k do not equal at (b), restructuring the MTA to remove the string tuple.

23. The method according to claim 22, further comprising removing redundant strings in the string tuples of the MTA.