Weighted system of expressing language information using a compact notation

• US 7,974,833 B2
• Filed: 06/21/2005
• Issued: 07/05/2011
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: SDL PLC (RWS Holdings Plc)
• Original Assignee: Language Weaver, Inc. (RWS Holdings Plc)
• Inventors: Marcu, Daniel, Soricut, Radu
• Primary Examiner(s): SAINT CYR, LEONARD
• Application Number:
  US11/158,897
• Publication Number:
  US 20070016400A1
• Time in Patent Office: 2,205 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30

Abstract

A special notation that extends the notion of IDL by weighted operators. The Weighted IDL or WIDL can be intersected with a language model, for example an n-gram language model or a syntax-based language model. The intersection is carried out by converting the IDL to a graph, and unfolding the graph in a way which maximizes its compactness.

Claims

1. A method for expressing language information using compact notation, the method comprising:

executing instructions embodied on a computer readable storage medium to direct a processor to define a compact notation for representing a large set of weighted strings via defined operators that include;

a family of first operators that are probability weighted word choice disjunction operators that allow for multiple word choices which are probabilistically weighted,

a concatenation operator that forces strings within the language to be in an order stated by the operator,

a probabilistically locked interleaving operator that probabilistically defines how arguments of the probabilistic operator are presented in a string;

executing instructions embodied on a computer readable storage medium to direct a processor to convert the expression to a WIDL graph which is a function of beginning and end vertices and edges, a set of vertices and edges, an edge labeling function, and a vertex ranking function.

2. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to use the notation for a text to text application, by finding a highest probability string in the set represented by the notation.

3. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to use the notation for a text to text application, by finding a highest probability string in a set represented by the notation under an intersection of the set with a language model.

4. A method as in claim 3, wherein the language model is an n-gram language model.

5. A method as in claim 3, wherein the language model is a syntax-based language model.

6. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to intersect the WIDL graph with a language model.

7. A method as in claim 6, wherein the language model is an n-gram language model.

8. A method as in claim 6, wherein the language model is a syntax based language model.

9. A method as in claim 8, wherein the efficiently unfolding comprises minimizing a number of parts of the graph that need to be unfolded.

10. A method as in claim 6, wherein the processor intersects the WIDL graph, at least, by forming a graph using the notation, and efficiently unfolding vertices of the graph.

11. A method as in claim 10, wherein the unfolding comprises mapping the graph to a finite state acceptor.

12. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to use the notation to translate a source language sentence into a target language sentence.

13. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to use the notation to automatically summarize a plurality of phrases.

14. A method as in claim 1, further comprising executing instructions embodied on a computer readable storage medium to direct a processor to use the notation for a text to text application.

15. A method for expressing language information using compact notation, the method comprising:

executing instructions embodied on a computer readable storage medium to direct a processor to define a language in a notation that compactly represents a plurality of different expressions in the notation, and weights different alternatives according to a probabilistic interpretation;

executing instructions embodied on a computer readable storage medium to direct a processor to carry out a text-to-text natural language application by intersecting the notation with a language model;

wherein the intersecting comprises converting the notation into a graph indicative of the notation, and intersecting the graph with the language model;

wherein the graph is intersected with an n- gram type language model by implementing the language model as a weighted finite state acceptor, mapping from the ideal graph to the finite state acceptor, and splitting the states to assign weights to transitions using a technique that is linear in the complexity of an input expression.

16. A method as in claim 15, wherein the language model is an n-gram language model.

17. A method as in claim 15, wherein the language model is a syntax-based language model.

18. A method as in claim 15, wherein the converting comprises minimizing a number of parts of the graph that are unfolded.

19. A method as in claim 15, wherein the converting comprises labeling edges of the graph corresponding to cuts of the graph.

20. A method as in claim 15, wherein the converting comprises finding a single source shortest path for a directed graph.

21. A method as in claim 15, wherein the converting comprises unfolding a graph on the fly scoring unfolded paths, and controlling an amount of unfolding based on scores of previous unfolded parts.

22. A method as in claim 21, wherein the controlling comprises determining unlikely parts of the path, and preventing further unfolding of the unlikely parts.

23. A method as in claim 15, wherein the converting comprises incrementally unfolding a path, while maintaining information about unfolded parts.

24. A method as in claim 23, wherein the information is probabilistic information.

25. A method as in claim 15, wherein the converting comprises determining an estimate of a heuristic which represents a cost efficient future conditioning event for specified ones of the operators.

26. A method as in claim 25, wherein the heuristic is used to extract a set of most cost effective future events for each operator.

27. A method as in claim 15, wherein the intersecting comprises finding a realization corresponding to the path of maximum probability.

28. A method as in claim 15, wherein the intersecting comprises finding a probability of a string by multiplying probabilities of each word in the string given n words before it.

29. A method as in claim 28, wherein the obtaining cost estimates comprises evaluating syntax trees.

30. A method as in claim 15, wherein the graph is intersected with a syntax-based language model by unfolding the graph on-the-fly into a finite state acceptor, using heuristics to compute cost estimates for each state in the acceptor, and using the cost estimates to decide what parts of the graph to unfold and in what order.

31. A method as in claim 30, wherein the probability of a hierarchical structure associated with a string is obtained by multiplying probabilities of creating each of the nodes in the hierarchical structure.

32. A system for expressing language information using compact notation, the system comprising:

a computer readable storage medium having instructions embodies thereon; and

a processor for executing instructions embodied on the computer readable storage medium to direct the processor to define a compact notation for representing a large set of weighted strings via defined operators that include;

a family of first operators that are probability weighted word choice disjunction operators that allow for multiple word choices which are probabilistically weighted;

a concatenation operator that forces strings within the language to be in an order stated by the operator,

a probabilistically locked interleaving operator that probabilistically defines how arguments of the probabilistic operator are presented in a string;

wherein the processor also executes instructions embodied on the computer readable storage medium to direct the processor to intersect the set with a language model;

wherein the set is intersected by, at least, converting the expression to a WIDL graph which is a function of beginning and end vertices and edges, a set of vertices and edges, an edge labeling function, and a vertex ranking function.

33. A system as in claim 32, wherein the notation is used for a text-to-text application.

34. A system as in claim 32, wherein the language model is an n-gram language model.

35. A system as in claim 32, wherein the language model is a syntax-based language model.

36. A system as in claim 32, wherein the set is also intersected by unfolding the graph, while minimizing a number of parts of the graph that need to be unfolded.