Maximizing expected generalization for learning complex query concepts
First Claim
1. A method of learning user query concept for searching objects encoded in computer readable storage media comprising:
- providing a multiplicity of respective sample objects encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample objects and in which respective predicates of such respective sample expressions represent respective features of corresponding sample objects;
defining a user query concept sample space bounded by a boundary k-CNF expression which designates a more specific concept within the user query concept sample space and by a boundary k-DNF expression which designates a more general concept within the user query concept sample space;
refining the user query concept sample space by, selecting multiple sample objects from within the user query concept sample space;
presenting the multiple selected sample objects to the user;
soliciting user feedback as to closeness of individual ones of the multiple presented sample objects to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes refining the boundary k-CNF expression by identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-CNF expression identified as different from corresponding respective predicates of sample expressions indicated by the user as close to the user'"'"'s query concept to remove from the boundary k-CNF expression;
removing from the boundary k-CNF expression respective predicates determined to be removed;
wherein refining the user query concept sample space further includes, refining the boundary k-DNF expression by, identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as not close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-DNF expression-identified as not different from corresponding respective predicates of sample expressions indicated by the user as not close to the user'"'"'s query concept to remove from the boundary k-DNF expression; and
removing from the boundary k-DNF expression respective predicates determined to be removed.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of learning a user query concept is provided which includes a sample selection stage and a feature reduction stage; during the sample selection stage, sample objects are selected from a query concept sample space bounded by a k-CNF and a k-DNF; the selected sample objects include feature sets that are no more than a prescribed amount different from a corresponding feature set defined by the k-CNF; during the feature reduction stage, individual features are removed from the k-CNF that are identified as differing from corresponding individual features of sample objects indicated by the user to be close to the user'"'"'s query concept; also during the feature reduction stage, individual features are removed from the k-DNF that are identified as not differing from corresponding individual features of sample objects indicated by the user to be not close to the user'"'"'s query concept.
-
Citations
26 Claims
-
1. A method of learning user query concept for searching objects encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample objects encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample objects and in which respective predicates of such respective sample expressions represent respective features of corresponding sample objects;
defining a user query concept sample space bounded by a boundary k-CNF expression which designates a more specific concept within the user query concept sample space and by a boundary k-DNF expression which designates a more general concept within the user query concept sample space;
refining the user query concept sample space by, selecting multiple sample objects from within the user query concept sample space;
presenting the multiple selected sample objects to the user;
soliciting user feedback as to closeness of individual ones of the multiple presented sample objects to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes refining the boundary k-CNF expression by identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-CNF expression identified as different from corresponding respective predicates of sample expressions indicated by the user as close to the user'"'"'s query concept to remove from the boundary k-CNF expression;
removing from the boundary k-CNF expression respective predicates determined to be removed;
wherein refining the user query concept sample space further includes, refining the boundary k-DNF expression by, identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as not close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-DNF expression-identified as not different from corresponding respective predicates of sample expressions indicated by the user as not close to the user'"'"'s query concept to remove from the boundary k-DNF expression; and
removing from the boundary k-DNF expression respective predicates determined to be removed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method of learning user query concept for searching objects encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample objects encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample objects and in which respective predicates of such respective sample expressions represent respective features of corresponding sample objects;
defining a user query concept sample space by initially designating an initial set of sample objects with at least one sample object from each of multiple pre-clustered sets of sample objects as an initial user query concept sample space and by defining a boundary k-CNF expression and a boundary k-DNF expression which, together, encompass an initial set of sample expressions that correspond respectively to the sample objects of the initial set of sample objects;
wherein the boundary k-CNF expression designates a more specific concept within the user query concept sample space; and
wherein the boundary k-DNF expression designates a more general concept within the user query concept sample space;
refining the user query concept sample space by, selecting multiple sample objects from within the user query concept sample space that correspond to respective sample expressions that have a prescribed number of respective predicates that are different from corresponding respective predicates of the boundary k-CNF expression;
presenting the multiple selected sample objects to the user;
soliciting user feedback as to which of the multiple presented sample objects are close to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes, refining the boundary k-CNF expression by, identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-CNF expression identified as different from corresponding respective predicates of sample expressions indicated by the user as close to the user'"'"'s query concept are different from corresponding respective predicates of more than a prescribed number of sample expressions;
removing from the boundary k-CNF expression respective predicates that are different from corresponding respective predicates of more than the prescribed number of sample expressions;
wherein refining the user query concept sample space further includes, refining the boundary k-DNF expression by, identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as not close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-DNF expression identified as not different from corresponding respective predicates of sample expressions indicated by the user as not close to the user'"'"'s query concept to remove from the boundary k-DNF expression;
removing from the boundary k-DNF expression respective predicates determined to be removed; and
repeating the steps involved in refining the user query concept sample space until the user ends the search. - View Dependent Claims (20)
-
-
21. A method of learning user query concept for searching objects encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample objects encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample objects and in which respective predicates of such respective sample expressions represent respective features of corresponding sample objects;
defining a user query concept sample space bounded by a boundary k-DNF expression;
refining the user query concept sample space by, selecting multiple sample objects from within the user query concept sample space;
presenting the multiple selected sample objects to the user;
soliciting user feedback as to closeness of individual ones of the multiple presented sample objects to the user'"'"'s query concept;
identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as not close to the user'"'"'s query concept;
determining which, if any, respective predicates of the boundary k-DNF expression identified as not different corresponding respective predicates of sample expressions indicated by the user as not close to the user'"'"'s query concept to remove from the boundary k-DNF expression;
removing from the boundary k-DNF expression respective predicates determined to be removed; and
repeating the steps involved in refining at least until the user identifies a sample object as being close to the user'"'"'s query concept.
-
-
22. A method of learning user query concept for searching objects encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample objects encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample objects and in which respective predicates of such respective sample expressions represent respective features of corresponding sample objects;
defining a user query concept sample space bounded by a boundary k-CNF expression which designates a more specific concept within the user query concept sample space and by a boundary k-DNF expression which designates a more general concept within the user query concept sample space;
refining a user query concept sample space by, selecting multiple sample objects from within the user query concept sample space;
presenting the multiple selected sample objects to the user;
soliciting user feedback as to closeness of individual ones of the multiple presented sample objects to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes refining the boundary k-CNF expression by identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as close to the user'"'"'s query concept;
removing from the boundary k-CNF expression respective identified predicates;
wherein refining the user query concept sample space further includes, refining the boundary k-DNF expression by, identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression for those respective sample expressions corresponding to respective sample objects indicated by the user as not close to the user'"'"'s query concept; and
removing from the boundary k-DNF expression respective identified predicates. - View Dependent Claims (23, 24, 25, 26)
-
Specification