Inducing and applying a subject-targeted context free grammar

• US 10,223,349 B2
• Filed: 02/20/2013
• Issued: 03/05/2019
• Est. Priority Date: 02/20/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Quirk, Christopher B., Choudhury, Pallavi, Ganitkevic, Jurij, Zettlemoyer, Luke S.
• Primary Examiner(s): Patel, Shreyans A
• Application Number:
  US13/771,100
• Publication Number:
  US 20140236571A1
• Time in Patent Office: 2,204 Days
• Field of Search: 704 9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A processing system is described which induces a context free grammar (CFG) based on a set of descriptions. The descriptions pertain to a particular subject. Thus, the CFG targets the particular subject, and is accordingly referred to as a subject-targeted context free grammar (ST-CFG). The processing system can use the ST-CFG to determine whether a new description is a proper description of the subject. The processing system also provides synthesizing functionality for building an ST-CFG based on one or more smaller component ST-CFGs.

Claims

1. A method for inducing a context free grammar, the method comprising:

receiving descriptions that pertain to a defined focus of interest from a set of data;

parsing the descriptions using a first context free grammar (CFG) comprising a set of rules and non-terminal symbols that describe syntactic categories, to provide parsed description information;

providing an unrefined subject-targeted context free grammar (ST-CFG) by retaining a subset of the set rules of the first CFG that is used to parse the descriptions;

refining the unrefined ST-CFG to produce a refined ST-CFG, the refined ST-CFG modeling the descriptions more accurately compared to the unrefined ST-CFG, the refining comprising;

associating features with terms in the parsed description information to produce annotated description information, the features associating the terms in the parsed description with information related to the defined focus of interest;

clustering the annotated description information to generate two or more categories; and

identifying additional rules and additional non-terminal symbols to apply to the unrefined ST-CFG based on said two or more categories, to produce the refined ST-CFG, the additional rules and the additional non-terminal symbols not being in the set of rules and the non-terminal symbols of the first CFG; and

determining that the refined ST-CFG is grammatical; and

based on the determination that the refined ST-CFG is grammatical, enabling access to protected resources.

2. The method of claim 1, further comprising applying the refined ST-CFG by:

receiving a new description of the defined focus of interest;

analyzing the new description using the refined ST-CFG, to produce an analysis result; and

based on the analysis result, determining whether the new description is an appropriate description of the defined focus of interest.

3. The method of claim 1, wherein the defined focus of interest pertains to a target entity.

4. The method of claim 3, wherein the target entity corresponds to one or more entities selected from:

an object;

an event; and

a state.

5. The method of claim 1, wherein the defined focus of interest corresponds to a portion of linguistic information.

6. The method of claim 1, wherein the descriptions correspond to characterizations of stimulus information, the stimulus information representing the defined focus of interest, and wherein the stimulus information is expressed by one or more forms of media content selected from:

video content;

image content; and

audio content.

7. The method of claim 1, further comprising:

generating stimulus information that represents the defined focus of interest; and

presenting the stimulus information to a plurality of human participants, wherein said receiving comprises receiving the descriptions from the human participants, the human participants formulating a description that characterizes the stimulus information.

8. The method of claim 1, wherein the first CFG corresponds to a subject-agnostic CFG that defines a natural language.

9. The method of claim 1, wherein said providing comprises identifying rules in the first CFG that are used to parse the descriptions.

10. The method of claim 1, wherein said parsing and said providing comprise a single operation.

11. The method of claim 1, wherein at least one additional rule added to the refined ST-CFG indirectly specifies a set of linguistic items in a first natural language by identifying a linguistic item in a second natural language, the linguistic item in the second natural language being an appropriate translation of the set of linguistic items in the first natural language.

12. The method of claim 1, further comprising formulating a refined ST-CFG for a new subject by:

determining whether the new subject is decomposable into plural parts, and, if so, identifying those parts;

determining whether a component CFG exists for the plural parts, to provide one or more component CFGs; and

using said one or more component CFGs to produce the refined ST-CFG for the new subject, with or without collecting descriptions for the new subject.

13. A processing system, implemented by one or more computer devices, for inducing a context free grammar, the system comprising:

a stimulus-generating module configured to generate stimulus information that represents a focus of interest;

a description-collection module configured to;

present the stimulus information to a plurality of human participants; and

receive descriptions from the human participants, a human participant formulating a description that characterizes the stimulus information; and

a grammar-inducing module, comprising;

a parsing module configured to parse the descriptions using a first context free grammar (CFG) comprising a set of rules and non-terminal symbols that describe syntactic categories, to provide parsed description information, the parsed description information providing an unrefined subject-targeted context free grammar (ST-CFG) by retaining a subset of the set rules of the first CFG that is used to parse the descriptions;

a refinement module configured to refine the unrefined ST-CFG to produce a refined ST-CFG by associating features with terms in the parsed description information to produce annotated description information, the features associating the terms in the parsed description with information related to the focus of interest, and applying additional rules and additional non-terminal symbols to the unrefined ST-CFG based on the annotated description information, the refined ST-CFG including syntactic categories and the additional rules that model the descriptions more accurately compared to the unrefined ST-CFG, the additional rules and the additional non-terminal symbols not being in the set of rules and the non-terminal symbols of the first CFG; and

an authentication engine configured to;

determining that the refined ST-CFG is grammatical; and

based on the determination that the refined ST-CFG is grammatical, enabling access to protected resources.

14. The processing system of claim 13, further comprising a grammar-checking module configured to:

receive a new description of the focus of interest;

analyze the new description using the refined ST-CFG, to produce an analysis result; and

based on the analysis result, determine whether the new description is an appropriate description of the focus of interest.

15. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing a processing system when executed by one or more processing devices, the computer readable instructions comprising:

receiving descriptions that pertain to a defined focus of interest from a set of data;

parsing the descriptions using a first context free grammar (CFG) comprising a set of rules and non-terminal symbols that describe syntactic categories, to provide parsed description information;

providing an unrefined subject-targeted context free grammar (ST-CFG) by retaining a subset of the set rules of the first CFG that is used to parse the descriptions;

refining the unrefined ST-CFG to produce a refined ST-CFG, the refined ST-CFG modeling the descriptions more accurately compared to the unrefined ST-CFG, the refining comprising;

associating features with terms in the parsed description information to produce annotated description information, the features associating the terms in the parsed description with information related to the defined focus of interest;

clustering the annotated description information to generate two or more categories; and

identifying additional rules and additional non-terminal symbols to apply to the unrefined ST-CFG based on said two or more categories, to produce the refined ST-CFG, the additional rules and the additional non-terminal symbols not being in the set of rules and the non-terminal symbols of the first CFG; and

determining that the refined ST-CFG is grammatical; and

based on the determination that the refined ST-CFG is grammatical, enabling access to protected resources.

16. The computer readable storage medium of claim 15, further comprising:

applying the refined ST-CFG by;

receiving a new description of the defined focus of interest;

analyzing the new description using the refined ST-CFG, to produce an analysis result; and

based on the analysis result, determining whether the new description is an appropriate description of the defined focus of interest.

17. The computer readable storage medium of claim 15, wherein the defined focus of interest pertains to a target entity.

18. The computer readable storage medium of claim 15, wherein the defined focus of interest corresponds to a portion of linguistic information.

19. The computer readable storage medium of claim 15, wherein the descriptions correspond to characterizations of stimulus information, the stimulus information representing the defined focus of interest, and wherein the stimulus information is expressed by one or more forms of media content selected from:

video content;

image content; and

audio content.

20. The computer readable storage medium of claim 15,

wherein the first CFG corresponds to a subject-agnostic CFG that defines a natural language.