Maximizing expected generalization for learning complex query concepts

• US 20030065661A1
• Filed: 04/02/2002
• Published: 04/03/2003
• Est. Priority Date: 04/02/2001
• Status: Active Grant

• Current Assignee: VIM Technologies Ltd (MAI Holdings, Inc.)
• Original Assignee: VIM Technologies Ltd (MAI Holdings, Inc.)
• Inventors: Chang, Edward Y., Cheng, Kwang-Ting
• Granted Patent: US 7,158,970 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

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.

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.

2. The method of claim 1 further including:

removing respective sample objects presented to the user from eligibility for presentation to that same user.

3. The method of claim 1 further including:

repeating the steps involved in refining the user query concept sample space.

4. The method of claim 1 further including:

repeating the steps involved in refining the user query concept sample space until the boundary k-DNF expression becomes identical to or more specific than the boundary k-CNF expression.

5. The method of claim 1 further including:

repeating the steps involved in refining the user query concept sample space until the user ends search.

6. The method of claim 1 further including:

dividing the boundary k-CNF into multiple sub-group k-CNF expressions by separating respective predicates that can express each other'"'"'s feature information into different sub-group k-CNF expressions such that such separation of predicates does not result in loss of combinations of feature information due to such dividing;

wherein identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression involves identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of respective sub-group k-CNF expressions; and

wherein determining which, if any, respective predicates of the boundary k-CNF to remove from the boundary k-CNF expression involves determining which respective predicates of the respective sub-group k-CNF expressions identified as contradictory to corresponding respective predicates of sample expressions to remove.

7. The method of claim 1 further including:

dividing the boundary k-CNF into multiple sub-group k-CNF expressions by separating respective predicates that can express each other'"'"'s feature information into different sub-group k-CNF expressions such that such separation of predicates does not result in loss of combinations of feature information due to such dividing;

wherein identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression involves identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of respective sub-group k-CNF expressions; and

wherein determining which, if any, respective predicates of the boundary k-CNF to remove from the boundary k-CNF expression involves determining which respective predicates of the respective sub-group k-CNF expressions identified as different from corresponding respective predicates of sample expressions to remove; and

dividing the boundary k-DNF expression into multiple sub-group k-DNF expressions by separating respective predicates that can express each other'"'"'s feature information into different sub-group k-DNF expressions such that such separation of predicates does not result in loss of combinations of feature information due to such dividing;

wherein identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of the boundary k-DNF expression involves identifying respective predicates of respective sample expressions that are not different from corresponding respective predicates of respective sub-group k-DNF expressions; and

wherein determining which, if any, respective predicates of the boundary k-DNF to remove from the boundary k-DNF expression involves determining which respective predicates of the respective sub-group k-DNF expressions identified as not different from corresponding respective predicates of sample expressions to remove.

8. The method of claim 1,

wherein identifying respective predicates of respective sample expressions that are different from corresponding respective predicates of the boundary k-CNF expression includes,

testing respective sample expression predicates for differences from corresponding respective predicates of the boundary k-CNF expression in a prescribed order such that, for a respective given feature, a respective predicate representing higher resolution of such given respective feature is tested before a respective predicate representing a lower resolution of such given respective feature;

and

not testing such respective predicate representing the lower resolution of such given respective feature if testing of the respective predicate representing a higher resolution of such given respective feature indicates that there is a prescribed difference between the higher resolution sample expression predicate for such given respective feature and a corresponding respective higher resolution predicate of the boundary k-CNF expression.

9. The method of claim 1,

wherein identifying respective predicates of respective sample expressions that contradict corresponding respective predicates of the boundary k-CNF expression includes,

testing respective sample expression predicates for differences from corresponding respective predicates of the boundary k-CNF expression in a prescribed order such that, for a respective given feature, a respective predicate representing higher resolution of such given respective feature is tested before a respective predicate representing a lower resolution of such given respective feature;

and

not testing such respective predicate representing the lower resolution of such given respective feature if testing of a respective predicate representing a higher resolution of such given respective feature indicates that there is a prescribed difference between the higher resolution sample expression predicate for such given respective feature and a corresponding higher resolution predicate of the boundary k-CNF expression; and

wherein identifying respective predicates of respective sample expressions that do not contradict corresponding respective predicates of the boundary k-DNF expression includes,

testing respective sample expression predicates for differences from corresponding respective predicates of the boundary k-DNF expression in a prescribed order such that, for a respective given feature, a respective predicate representing higher resolution of such given respective feature is tested before a respective predicate representing a lower resolution of such given respective feature; and

not testing such respective predicate representing the lower resolution of such given respective feature if the testing of the respective predicate representing the higher resolution of such given respective feature indicates that there is a not a prescribed difference between the higher resolution sample expression predicate for such given respective feature and a corresponding respective higher resolution predicate of the boundary k-DNF expression.

10. The method of claim 1,

wherein determining which, if any, respective predicates of the boundary k-CNF expression to remove includes,

determining which respective predicates of the boundary k-CNF expression are different by at least a prescribed amount from corresponding respective predicates of more than a prescribed number of sample expressions.

11. The method of claim 1,

wherein determining which, if any, respective predicates of the boundary k-CNF expression to remove includes,

determining which respective predicates of the boundary k-CNF expression are different by at least a prescribed amount from corresponding respective predicates of more than a prescribed number of sample expressions;

wherein determining which, if any, respective predicates of the boundary k-DNF expression to remove includes,

determining which respective predicates of the boundary k-DNF expression are not different by a least a prescribed amount from corresponding respective predicates of more than a prescribed number of sample expressions.

12. The method of claim 1,

wherein selecting multiple sample objects from within the user query concept sample space includes,

selecting respective sample objects that correspond to respective sample expressions that have a prescribed number of respective predicates that contradict corresponding respective predicates of the boundary k-CNF expression.

13. The method of claim 1,

wherein selecting multiple sample objects from within the user query concept sample space includes,

selecting respective sample objects 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;

wherein the prescribed number is chosen by balancing a need for a prescribed number that is small enough that a selected sample object is likely to be indicated by the user as being close to the user'"'"'s query concept with a need for a prescribed number that is large enough that a selected sample object indicated by the user to be close to the user'"'"'s query concept is likely to correspond to a sample expression including a predicate that is different from a corresponding predicate of the boundary k-CNF.

14. The method of claim 1,

wherein selecting multiple sample objects from the user query concept sample space includes,

selecting respective sample objects that correspond to respective sample expressions for which ψ

predicates in respective corresponding sample expressions are different from the boundary k-CNF expression;

wherein,

ψ

=1/1n(1/1−

p), and

wherein p represents a probability that a given predicate of the boundary k-CNF expression will be removed from the k-CNF expression in the step of removing from the boundary k-CNF expression respective predicates determined to be removed.

15. The method of claim 1,

wherein selecting multiple sample objects from the user query concept sample space includes,

selecting respective sample objects 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;

wherein the prescribed number is determined empirically by balancing a need for a prescribed number that is small enough that a selected sample object is likely to be indicated by the user as being close to the user'"'"'s query concept with a need for a prescribed number that is large enough that a selected sample object indicated by the user to be close to the user'"'"'s query concept is likely to correspond to a sample expression including a predicate different from a corresponding predicate of the k-CNF.

16. The method of claim 1,

wherein defining the user query concept sample space includes,

selecting an initial set of sample objects by choosing at least one sample object from each of multiple pre-clustered sets of sample objects.

17. The method of claim 1,

wherein selecting multiple sample objects from within the user query concept sample space includes,

respectively selecting objects 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;

wherein determining which, if any, respective predicates of the boundary k-CNF expression to remove includes,

determining which respective predicates of the boundary k-CNF expression are different from corresponding respective predicates of more than a prescribed number of sample expressions; and

wherein removing from the boundary k-CNF expression respective predicates determined to be removed includes,

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.

18. The method of claim 1,

wherein selecting multiple sample objects from within the user query concept sample space includes,

respectively selecting objects 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;

wherein determining which, if any, respective predicates of the boundary k-CNF expression to remove includes,

determining which respective predicates of the boundary k-CNF expression are different from corresponding respective predicates of more than a prescribed number of sample expressions;

wherein removing from the boundary k-CNF expression respective predicates determined to be removed includes,

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; and

wherein determining which, if any, respective predicates of the boundary k-DNF expression to remove includes,

determining which respective predicates of the boundary k-DNF expression are not different from corresponding respective predicates of more than a prescribed number of sample expressions;

wherein removing from the boundary k-DNF expression respective predicates determined to be removed includes,

removing from the boundary k-DNF expression respective predicates that are not different from corresponding respective predicates of more than the prescribed number of sample expressions.

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.

20. The method of claim 19,

wherein determining which, if any, respective predicates of the boundary k-DNF expression to remove includes,

determining which respective predicates of the boundary k-DNF expression are not different from corresponding respective predicates of more than a prescribed number of sample expressions;

wherein removing from the boundary k-DNF expression respective predicates determined to be removed includes,

removing from the boundary k-DNF expression respective predicates that are not different from corresponding respective predicates of more than the prescribed number of sample expressions.

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 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;

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.

23. The method of claim 22,

wherein selecting multiple sample objects from within the user query concept sample space includes,

selecting respective sample objects that correspond to respective sample expressions that have a prescribed number of respective predicates that contradict corresponding respective predicates of the boundary k-CNF expression.

24. The method of claim 22,

wherein selecting multiple sample objects from within the user query concept sample space includes,

selecting respective sample objects 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;

wherein the prescribed number is chosen by balancing a need for a prescribed number that is small enough that a selected sample object is likely to be indicated by the user as being close to the user'"'"'s query concept with a need for a prescribed number that is large enough that a selected sample object indicated by the user to be close to the user'"'"'s query concept is likely to correspond to a sample expression including a predicate that is different from a corresponding predicate of the boundary k-CNF.

25. The method of claim 22,

wherein selecting multiple sample objects from the user query concept sample space includes,

selecting respective sample objects 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;

wherein the prescribed number is determined empirically by balancing a need for a prescribed number that is small enough that a selected sample object is likely to be indicated by the user as being close to the user'"'"'s query concept with a need for a prescribed number that is large enough that a selected sample object indicated by the user to be close to the user'"'"'s query concept is likely to correspond to a sample expression including a predicate different from a corresponding predicate of the k-CNF.

26. The method of claim 22,

wherein defining the user query concept sample space includes,

selecting an initial set of sample objects by choosing at least one sample object from each of multiple pre-clustered sets of sample objects.