Maximizing expected generalization for learning complex query concepts
First Claim
1. A method of learning a user query concept for searching visual images encoded in computer readable storage media comprising:
- providing a multiplicity of respective sample images encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample images and in which respective terms of such respective sample expressions represent respective features of corresponding sample images;
defining a user query concept sample space bounded by a k-CNF expression which models a query concept and by a k-DNF expression;
refining the user query concept sample space by, selecting multiple respective sample images from within the user query concept sample space by selecting respective sample expressions that correspond to such images, wherein respective sample expressions are selected by optimizing a tradeoff between a respective expression'"'"'s having sufficient similarity to the k-CNF expression that a user is likely to indicate that its corresponding sample image is close to the user'"'"'s query concept and such respective expression'"'"'s having sufficient dissimilarity from the k-CNF expression that an indication by the user that its corresponding sample image is close to the user'"'"'s query concept is likely to provide maximum information as to which disjunctive terms of the k-CNF expression do not match the user'"'"'s query concept;
presenting the multiple selected sample images to the user;
soliciting user feedback as to which of the multiple presented sample images are close to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes, refining the k-CNF expression by, identifying respective differences between one or more respective terms of respective sample expressions, corresponding to respective sample images indicated by a user as close to the user'"'"'s query concept, and corresponding respective disjunctive terms of the k-CNF expression;
determining which, if any, respective disjunctive terms of the k-CNF expression to remove from the k-CNF expression based upon the identified differences;
removing from the k-CNF expression respective disjunctive terms determined to be removed;
wherein refining the user query concept sample space further includes, refining the k-DNF expression by, identifying respective differences between one or more respective terms of respective sample expressions, corresponding to respective sample images indicated by a user as not close to the user'"'"'s query concept, and corresponding respective conjunctive terms of the k-DNF expression;
determining which, if any, respective conjunctive terms of the k-DNF to remove from the k-DNF expression based upon the identified differences; and
removing from the k-DNF expression respective conjunctive terms determined to be removed.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of learning user query concept for searching visual images encoded in computer readable storage media comprising: providing a multiplicity of sample images encoded in a computer readable medium; providing a multiplicity of sample expressions that correspond to sample images and in which terms of the sample expressions represent features of corresponding sample images; defining a user query concept sample space bounded by a boundary k-CNF expression and by a boundary k-DNF expression refining the user query concept sample space by, soliciting user feedback as to which of the multiple presented sample images are close to the user'"'"'s query concept; removing from the boundary k-CNF expression disjunctive terms based upon the solicited user feedback; and removing from the boundary k-DNF expression respective conjunctive terms based upon the solicited user feedback.
39 Citations
24 Claims
-
1. A method of learning a user query concept for searching visual images encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample images encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample images and in which respective terms of such respective sample expressions represent respective features of corresponding sample images;
defining a user query concept sample space bounded by a k-CNF expression which models a query concept and by a k-DNF expression;
refining the user query concept sample space by, selecting multiple respective sample images from within the user query concept sample space by selecting respective sample expressions that correspond to such images, wherein respective sample expressions are selected by optimizing a tradeoff between a respective expression'"'"'s having sufficient similarity to the k-CNF expression that a user is likely to indicate that its corresponding sample image is close to the user'"'"'s query concept and such respective expression'"'"'s having sufficient dissimilarity from the k-CNF expression that an indication by the user that its corresponding sample image is close to the user'"'"'s query concept is likely to provide maximum information as to which disjunctive terms of the k-CNF expression do not match the user'"'"'s query concept;
presenting the multiple selected sample images to the user;
soliciting user feedback as to which of the multiple presented sample images are close to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes, refining the k-CNF expression by, identifying respective differences between one or more respective terms of respective sample expressions, corresponding to respective sample images indicated by a user as close to the user'"'"'s query concept, and corresponding respective disjunctive terms of the k-CNF expression;
determining which, if any, respective disjunctive terms of the k-CNF expression to remove from the k-CNF expression based upon the identified differences;
removing from the k-CNF expression respective disjunctive terms determined to be removed;
wherein refining the user query concept sample space further includes, refining the k-DNF expression by, identifying respective differences between one or more respective terms of respective sample expressions, corresponding to respective sample images indicated by a user as not close to the user'"'"'s query concept, and corresponding respective conjunctive terms of the k-DNF expression;
determining which, if any, respective conjunctive terms of the k-DNF to remove from the k-DNF expression based upon the identified differences; and
removing from the k-DNF expression respective conjunctive terms 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, 20, 21)
-
-
22. A method of learning user query concept for searching visual images encoded in computer readable storage media comprising:
-
providing a multiplicity of respective sample images encoded in a computer readable medium;
providing a multiplicity of respective sample expressions encoded in computer readable medium that respectively correspond to respective sample images and in which respective terms of such respective sample expressions represent respective features of corresponding sample images;
defining a user query concept sample space by initially designating an initial set of sample images with at least one sample image from each of multiple pre-clustered sets of sample images as an initial user query concept sample space and by defining a k-CNF expression and a k-DNF expression which, together, encompass an initial set of sample expressions that correspond respectively to the sample images of the initial set of sample images;
wherein the k-CNF expression designates a more specific concept within the user query concept sample space; and
wherein the 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 images from within the user query concept sample space that correspond to respective sample expressions that have a prescribed number of respective terms that contradict corresponding respective terms of the k-CNF expression;
resenting the multiple selected sample images to the user;
soliciting user feedback as to which of the multiple presented sample images are close to the user'"'"'s query concept;
wherein refining the user query concept sample space further includes, refining the k-CNF expression by, identifying respective terms of respective sample expressions that contradict corresponding respective disjunctive terms of the k-CNF expression for those respective sample expressions corresponding to respective sample images indicated by the user as close to the user'"'"'s query concept;
determining which, if any, respective disjunctive terms of the k-CNF expression identified as contradicting corresponding respective terms of sample expressions indicated by the user as close to the user'"'"'s query concept, contradict corresponding respective terms of more than a prescribed number of such sample expressions;
removing from the k-CNF expression respective disjunctive terms that contradict corresponding respective terms of more than the prescribed number of sample expressions;
wherein refining the user query concept sample space further includes, refining the k-DNF expression by, identifying respective terms of respective sample expressions that do not contradict corresponding respective conjunctive terms of the k-DNF expression for those respective sample expressions corresponding to respective sample images indicated by the user as not close to the user'"'"'s query concept;
determining which, if any, respective conjunctive terms of the k-DNF expression identified as not contradicting corresponding respective terms of sample expressions indicated by the user as not close to the user'"'"'s query concept, do not contradict corresponding respective terms of more than a prescribed number of such sample expressions;
removing from the k-DNF expression respective conjunctive terms that do not contradict corresponding respective predicates of more than the prescribed number of sample expressions; and
repeating the steps involved in refining the user query concept sample space. - View Dependent Claims (23, 24)
-
Specification