Method and apparatus for processing natural language using tape-intersection

• US 20050108000A1
• 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,617,091 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/237 Lexical tools

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 tapes of a first multi-tape automaton (MTA) and a second MTA, with each MTA having a plurality of tapes and a plurality of paths, comprising:

(a) computing a cross-product MTA using the first MTA and the second MTA;

(b) generating string tuples for paths of the cross-product MTA;

(c) for each string tuple generated at (b), evaluating whether the string of a first tape equals the string of a second tape;

(d) for each string tuple evaluated at (c) having equal strings at the first and second tapes, retaining the corresponding string tuple in the cross-product MTA;

(e) for each string tuple evaluated at (c) having unequal strings at the first and second tapes, restructuring the cross-product MTA to remove the corresponding string tuple;

(f) removing redundant strings in the string tuples retained in the cross-product MTA at (d) to produce an output MTA.

2. The method according to claim 1, wherein (f comprises removing redundant strings in the string tuples retained in the cross-product MTA at (d) to produce an output MTA that preserves at least one other tape besides one of the first and second tapes of the cross-product MTA without modification.

3. method according to claim 2, further comprising repeating (a)-(f) in a cascade of a first transduction and a second transduction, wherein at least one of the tapes preserved after completing the first transduction is accessed to perform the second transduction.

4. The method according to claim 3, wherein each MTA has weighted transitions.

5. The method according to claim 4, wherein the weights transitions of each MTA are probabilities.

6. The method according to claim 1, wherein the first MTA encodes strings in a first natural language and the second MTA encodes strings in a second natural language.

7. The method according to claim 6, wherein the output MTA identifies related strings of the first natural language and the second natural language.

8. The method according to claim 1, further comprising repeating (b)-(e) for a first other tape and a second other tape, wherein at least one of the first other tape and the second other tape is not the first tape or the second tape.

9. The method according to claim 1, further comprising performing (a)-(e) in a concurrent series of operations that integrates (a) while performing (b)-(e).

10. The method according to claim 9, wherein the cross-product MTA has at least one epsilon loop along a path defined by the first tape or the second tape.

11. The method according to claim 1, wherein (a)-(f) are performed with a single composition of the first MTA and the second MTA that preserves at least one other tape besides one of the first and second tapes of the cross-product MTA without modification.

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

defining a simulated filter automaton (SFA) that controls how epsilon-transitions are composed along pairs of paths in the first MTA and the second MTA;

building an output MTA by;

(a) creating an initial state from the initial states of the first MTA, the second MTA, and the SFA;

(b) intersecting a selected outgoing transition of the first MTA with a selected outgoing transition of the second MTA, where each outgoing transition has a source state, a target state, and a label;

(c) if the label of the first tape of the selected outgoing transition of the first MTA equals the label of the second tape of the selected outgoing transition of the second MTA, creating (i) a transition in the output MTA whose label results from pairing the labels of the selected outgoing transitions, and (ii) a target state corresponding to the target states of the selected outgoing transitions and the initial state of the SFA;

(d) if an epsilon transition is encountered on the first tape, creating a transition in the output MTA with a target state that is a function of (i) the target state of the outgoing transition of the first MTA, (ii) the source state of the outgoing transition of the second MTA, and (iii) a first non-initial state of the SFA;

(e) if an epsilon transition is encountered on the second tape, creating a transition in the output MTA with a target state that is a function of (i) the source state of the outgoing transition of the first MTA, (ii) the target state of the outgoing transition of the second MTA, and (iii) a second non-initial state of the SFA; and

(f) repeating (b)-(e) for each outgoing transition of the first MTA and the second MTA.

13. The method according to claim 12, further comprising revising the labels of transitions of the output MTA to remove one of its tapes corresponding to either the first tape of the first MTA or the second tape of the second MTA to complete single-tape intersection.

14. The method according to claim 12, further comprising revising the labels of each transition of the output MTA to remove both of its tapes corresponding to the first tape of the first MTA and the second tape of the second MTA to complete classical composition.

15. The method according to claim 12, further comprising performing auto-intersection on the output MTA for two selected tapes, wherein no more than one of the two selected tapes corresponds to the first tape of the first MTA or the second tape of the second MTA.

16. The method according to claim 15, further comprising revising the output MTA to eliminate redundant tapes to complete multi-tape intersection.

17. The method according to claim 12, wherein the output MTA preserves at least one other tape besides one of the first tape of the first MTA and the second tape of the second MTA.

18. The method according to claim 12, further comprising repeating (a)-(f) in a cascade of a first transduction and a second transduction, where at least one of the tapes preserved after completing the first transduction is accessed to perform the second transduction.

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

(a) composing the first MTA and the second MTA by intersecting a first tape of the first MTA with a first tape of the second MTA to produce an output MTA;

the first tape of the first MTA and the first tape of the second MTA corresponding to a first intersected tape and a second intersected tape of the output MTA, respectively; and

(b) removing at least one of the first and the second intersected tapes from the output MTA while preserving all its other tapes without modification.

20. The method according to claim 19, wherein (a) further comprises:

(a1) computing a cross-product MTA using the first MTA and the second MTA;

(a2) generating string tuples for paths of the cross-product MTA;

(a3) for each string tuple generated at (a2), evaluating whether the string of the first intersected tape equals the string of the second intersected tape;

(a4) for each string tuple evaluated at (a3) having equal strings at the first and second intersected tapes, retaining the corresponding string tuple in the cross-product MTA;

(a5) for each string tuple evaluated at (a3) having unequal strings at the first and second intersected tapes, restructuring the cross-product MTA to remove the corresponding string tuple; and

wherein (b) further comprises removing redundant strings in string tuples retained in the cross-product MTA at (a4) to produce the output MTA.

21. The method according to claim 20, further comprising repeating (a2)-(a5) for at least one or both of a second tape of the first MTA and a second tape of the second MTA.

22. The method according to claim 19, further comprising:

intersecting at least one or both of a second tape of the first MTA and a second tape of the second MTA corresponding to a third intersected tape and a fourth intersected tape of the output MTA, respectively; and

removing at (b) at least one of the third and the fourth intersected tapes from the output MTA.

23. The method according to claim 19, wherein the output MTA has weighted transitions.

24. The method according to claim 19, further comprising repeating (a)-(b) in a cascade of a first transduction and a second transduction, where at least one of the tapes preserved after completing the first transduction is accessed to perform the second transduction.

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