Inducing and applying a subject-targeted context free grammar
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification