PROBABILISTIC PARSING

• US 20140250046A1
• Filed: 03/03/2013
• Published: 09/04/2014
• Est. Priority Date: 03/03/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Winn, John Michael, Minka, Thomas
• Granted Patent: US 9,251,467 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Probabilistic parsing is described for calculating information about the structure of text and other ordered sequences of items to enable downstream systems such as machine translation systems, information retrieval systems, document classification systems and others to use the structure information. In various embodiments, a parsing inference component comprises inference algorithm(s) compiled from a probabilistic program which defines a stochastic process for generating text or other ordered sequences of items. In examples, the parsing inference component receives one or more observations or examples of text that are compatible with the stochastic process defined by the probabilistic program. The parsing inference component may apply the inference algorithms to the text to update one or more probability distributions over strings or other values relevant to the parse. In some examples, the parsing inference component uses the inference results to complete partial examples to assist a user with information retrieval tasks.

Claims

1. A method of parsing ordered sequences of items comprising:

accessing, at a processor, a process for generating ordered sequences of items, the process having one or more probability distributions representing possible ordered sequences of items involved in the process;

receiving, at the processor, at least one example of at least part of an ordered sequence of items compatible with the probabilistic process;

updating the one or more probability distributions by carrying out inference using the at least one example; and

outputting information about the one or more probability distributions.

2. A method as claimed in claim 1 where the items are characters and the ordered sequences of items are strings.

3. A method as claimed in claim 1 where the process also comprises at least one uncertain variable of a type selected from any of:

Boolean variables, integer variables, double variables, date variables, compound variables containing multiple properties.

4. A method as claimed in claim 1 where the process comprises one or more operations from a specified plurality of operations for generating an ordered sequence of items;

at least one operation having at least one argument which is itself an operation represented by a probability distribution over an ordered sequence of items.

5. A method as claimed in claim 1 where the process uses one or more stochastic automata to represent the probability distributions and generate the ordered sequence of items.

6. A method as claimed in claim 1 comprising updating the one or more probability distributions by updating stochastic automata using stochastic transducers.

7. A method as claimed in claim 1 wherein accessing the process comprises accessing a compiled probabilistic program comprising message passing algorithms arranged to update the probability distributions by updating stochastic automata using stochastic transducers.

8. A method as claimed in claim 1 comprising using the at least one example and the one or more probability distributions to obtain complete examples of ordered sequences of items compatible with the probabilistic process.

9. A method as claimed in claim 8 comprising updating the one or more probability distributions by carrying out inference using the complete examples.

10. A method as claimed in claim 1 comprising using the updated probability distributions to complete a partial example, the partial example being of an object having a plurality of properties, at least one of which is known and at least one of which is unknown, and where using the updated probability distributions to complete the partial example comprises computing values of at least one of the unknown property values.

11. A method as claimed in claim 10 comprising using the updated probability distributions to compute a certainty of the completed partial example and displaying information about the computed certainty.

12. A method as claimed in claim 1 comprising using the at least one example and the one or more probability distributions to obtain complete examples of ordered sequences of items compatible with the probabilistic process;

and displaying information about sources of the complete examples.

13. A method of parsing strings comprising:

accessing, at a processor, a process for generating strings, the process having one or more probability distributions representing possible strings involved in the process;

receiving, at the processor, at least one partial example;

updating the one or more probability distributions by carrying out inference using the at least one partial example; and

using the updated probability distributions to complete the at least one partial example.

14. A method as claimed in claim 13 comprising obtaining a plurality of complete examples of strings compatible with the process by using the at least one partial example and the probability distributions to retrieve documents from an information retrieval system.

15. A method as claimed in claim 14 comprising extracting the complete examples from the documents by searching the documents for strings compatible with the process.

16. A method as claimed in claim 14 comprising displaying information about one or more of the retrieved documents.

17. A method as claimed in claim 13 comprising obtaining a plurality of complete examples of strings compatible with the process by using the at least one partial example and the updated probability distributions, and updating the one or more probability distributions by carrying out inference using the complete examples.

18. A parsing inference component comprising device executable instructions for generating ordered sequences of items, the process using one or more probability distributions representing possible ordered sequences of items involved in the process;

the parsing inference component having;

an input controller arranged to receive at least one example of at least part of an ordered sequence of items compatible with the probabilistic process; and

where the device executable instructions are arranged to update the one or more probability distributions by carrying out inference using the at least one example.

19. A parsing inference component as claimed in claim 18 comprising a processor arranged to dynamically generate a probabilistic program for generating the ordered sequences of items.

20. A parsing inference component as claimed in claim 18 being at least partially implemented using hardware logic selected from any one or more of:

a field-programmable gate array, a program-specific integrated circuit, a program-specific standard product, a system-on-a-chip, a complex programmable logic device, a graphics processing unit.