Visual interactive search

• US 10,503,765 B2
• Filed: 05/04/2015
• Issued: 12/10/2019
• Est. Priority Date: 05/15/2014
• Status: Active Grant

• Current Assignee: Evolv Technology Solutions, Inc.
• Original Assignee: Evolv Technology Solutions, Inc.
• Inventors: Duffy, Nigel
• Primary Examiner(s): Spieler, William
• Application Number:
  US15/311,163
• Publication Number:
  US 20170075958A1
• Time in Patent Office: 1,681 Days
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/3328 using graphical result space presentation or visualisation
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Roughly described, a system for user identification of a desired document. A database is provided which identifies a catalog of documents in an embedding space, the database identifying a distance in the embedding space between each pair of documents corresponding to a predetermined measure of dissimilarity between the pair of documents. The system presents an initial collection of the documents toward the user, from an initial candidate space which is part of the embedding space. The system then iteratively refines the candidate space using geometric constraints on the embedding space determined in response to relative feedback by the user. At each iteration the system identifies to the user a subset of documents from the then-current candidate space, based on which the user provides the relative feedback. In an embodiment, these subsets of documents are more discriminative than the average discriminativeness of similar sets of documents in the then-current candidate space.

Claims

1. A method for user identification of a desired document, comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from an initial (i=0) candidate space within the embedding space, the initial collection having fewer documents than the initial candidate space;

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected subset of the documents from the (i−

1)'"'"'th collection of documents, a computer system geometrically constraining the embedding space to identify an i'"'"'th candidate space such that, according to a predefined definition of collective closeness, the documents in the i'"'"'th candidate space are collectively closer in the embedding space to the documents in the i'"'"'th selected subset, than are the documents in the (i−

1)'"'"'th candidate space; and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the i'"'"'th candidate space, Ni being smaller than the number of documents in the i'"'"'th candidate space; and

taking action in response to user selection of a particular subset of documents identified toward the user,

wherein the predefined definition of collective closeness is defined such that a candidate document X is considered closer to a document A than to a document B if the distance identified in the embedding space between document X and document A is shorter than the distance identified in the embedding space between document X and document B.

2. The method of claim 1, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

and wherein the predefined definition of collective closeness is defined further such that the documents in a given candidate space are collectively closer to the documents in a given selected subset, than are the documents in a particular prior candidate space, if the fraction of the documents in the given candidate space which are closer in the embedding space to the farthest document in the given selected subset than to the nearest document in the given non-selected subset, is greater than the fraction of the documents in the particular prior candidate space which are closer in the embedding space to the farthest document in the given selected subset than to the nearest document in the given non-selected subset.

3. The method of claim 1, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

and wherein the predefined definition of collective closeness is defined further such that the documents in a given candidate space are collectively closer to the documents in a given selected subset, than are the documents in a particular prior candidate space, if

the count, over all documents Y in the given candidate space and all pairs of documents (A,B), A in the i'"'"'th selected subset and B in the i'"'"'th non-selected subset, of instances in which d(A,Y)<

d(B,Y),

is less than the count, over all documents X in the particular prior candidate space and all the pairs of documents (A,B), of instances in which d(A,X)<

d(B,X),

each of the counts normalized for any difference between the total number of documents Y in the given candidate space and the total number of documents X in the particular prior candidate space.

4. The method of claim 1, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

and wherein the predefined definition of collective closeness is defined further such that the documents in a given candidate space are collectively closer to the documents in a given selected subset, than are the documents in a particular prior candidate space, if

the fraction of the documents Y in the given candidate space which are closer to the documents A in the i'"'"'th selected subset, averaged over all the documents A in the i'"'"'th selected subset, than they are to the documents B in the i'"'"'th non-selected subset, averaged over all the documents B in the i'"'"'th non-selected subset,

is less than the fraction of the documents X in the particular prior candidate space which are closer to the documents A in the i'"'"'th selected subset, averaged over all the documents A in the i'"'"'th selected subset, than they are to the documents B in the i'"'"'th non-selected subset, averaged over all the documents B in the i'"'"'th non-selected subset.

5. The method of claim 1, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

and wherein the predefined definition of collective closeness is defined further such that the documents in a given candidate space are collectively closer to the documents in a given selected subset, than are the documents in a particular prior candidate space, if

an aggregation, over all documents Y in the given candidate space and all pairs of documents (A,B), A in the i'"'"'th selected subset and B in the i'"'"'th non-selected subset, of penalties associated with each instance in which d(A,Y)≥

d(B,Y),

is less than an aggregation, over all documents X in the particular prior candidate space and all the pairs of documents (A,B), of penalties associated with each instance in which d(A,X)≥

d(B,X),

where each instance in which d(A,W)≥

d(B,W) is satisfied, for a given document W, is pre-associated with a respective penalty value.

6. The method of claim 1, wherein each i'"'"'th collection of documents in the step of identifying toward the user is more discriminative than the average discriminativeness of set size Ni documents in the i'"'"'th candidate space.

7. The method of claim 1, wherein each i'"'"'th collection of documents in the step of identifying toward the user is more discriminative than the discriminativeness of 90% of the sets of size Ni documents in the i'"'"'th candidate space.

8. The method of claim 1, wherein each i'"'"'th collection of documents in the step of identifying toward the user is at least as discriminative as all other sets of size Ni documents in the i'"'"'th candidate space.

9. The method of claim 1, wherein taking action in response to user selection of a particular subset of documents identified toward the user comprises:

a computer system geometrically modifying the then-current candidate space to identify a further candidate space in dependence upon the particular subset selected by the user; and

identifying toward the user a further collection of Nf>

1 candidate documents from the further candidate space, Nf being smaller than the number of documents in the further candidate space; and

taking action in response to user selection of a further subset of documents identified toward the user.

10. The method of claim 1, wherein the embedding space comprises a multi-dimensional vector space, each of the dimensions in the vector space defining a different basis on which documents can differ from each other,

and wherein the database identifies a position for each of the documents in the multi-dimensional vector space.

11. The method of claim 1, wherein the embedding space comprises a metric space.

12. The method of claim 1, wherein identifying toward the user an initial collection of candidate documents comprises presenting the initial collection of candidate documents toward the user in a layout in which the placement of at least some candidate documents in the initial collection relative to each other is indicative of the distances among the at least some candidate documents in the initial candidate space.

13. The method of claim 1, wherein each iteration of the step of identifying toward the user an i'"'"'th collection of candidate documents comprises presenting the i'"'"'th collection of candidate documents toward the user in a layout in which the placement of at least some candidate documents in the i'"'"'th collection relative to each other is indicative of the distances among the at least some candidate documents in the i'"'"'th candidate space.

14. The method of claim 1, wherein providing a database identifying a catalog of documents in an embedding space comprises:

defining a subject domain for documents to be embedded;

identifying one or more first items that are to be considered within the subject domain and one or more second items that are to be considered outside the subject domain;

a computer system learning an embedding in dependence upon training data which includes only documents that are considered to be within the subject domain, the training data including the first items but not including the second items; and

embedding the documents from the catalog of documents into the embedding space in dependence upon the learned embedding,

wherein all of the documents in the catalog of documents are considered to be within the subject domain.

15. The method of claim 1, wherein each iteration of the step of geometrically constraining an embedding space to identify an i'"'"'th candidate space comprises:

identifying a respective i'"'"'th set of geometric constraints on the embedding space; and

for each of at least some particular documents in the embedding space,

determining an aggregation of penalties associated with each of the geometric constraints in the first through i'"'"'th sets of geometric constraints which is not satisfied by the particular document, non-satisfaction of each of the geometric constraints being pre-associated with a respective penalty, and

including in the i'"'"'th candidate space only Ri of the documents from the embedding space, where the aggregate penalty of each of the Ri documents is no higher than the aggregate penalty of any other document in the embedding space for which an aggregation was determined in the step of determining an aggregation.

16. The method of claim 15, wherein Ri is fixed for all iterations i.

17. The method of claim 15, wherein for each given one of the iterations, Ri is the number of documents from the embedding space for which an aggregation was determined and whose aggregate penalty is less than a predetermined value.

18. The method of claim 15, wherein all of the penalties in all of the iterations are equal, and determining an aggregation of penalties consists of summing them.

19. The method of claim 15, wherein the penalty associated with each given one of the geometric constraints is dependent upon the iteration number in which the step of geometrically constraining identified the given geometric constraint.

20. The method of claim 1, wherein the initial (i=0) collection of N0>

1 candidate documents is more discriminative than the average discriminativeness of set size NO documents in the initial (i=0) candidate space.

21. The method of claim 1, wherein identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the initial (i=0) candidate space, comprises;

identifying clusters of similar documents in the initial candidate space; and

choosing the initial collection to include at least one document from each of the identified clusters.

22. The method of claim 21, wherein identifying clusters of similar documents in the initial candidate space comprises using a k-medoids algorithm.

23. The method of claim 21, wherein identifying toward the user an initial collection of candidate documents comprises identifying toward a medoid of each of the clusters.

24. The method of claim 1, wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space comprises identifying a respective i'"'"'th set of geometric constraints on the embedding space.

25. The method of claim 24, wherein a particular one of the geometric constraints is defined so as to be satisfied by a particular candidate document in dependence upon the relative distance in the embedding space of the particular candidate document to each of at least two anchor documents in the embedding space.

26. The method of claim 25, wherein the particular geometric constraint is satisfied by the particular candidate document if and only if the distance in the embedding space to a first predetermined one of the anchor documents is less than the distance in the embedding space to a second one of the anchor documents.

27. The method of claim 24, wherein each j'"'"'th one of the geometric constraints identifies a respective pair of documents (Aj,Bj) in the embedding space, and is defined so as to be satisfied by a particular candidate document X if d(Aj,X)<

d(Bj,X).

28. The method of claim 24, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space, in response to user selection of an i'"'"'th selected subset of the documents from the (i−

1)'"'"'th collection of documents, comprises adding a constraint which is defined so as to be satisfied by a particular candidate document if and only if the particular candidate document is closer in the embedding space to a document in the i'"'"'th selected subset than it is to a document in the i'"'"'th non-selected subset of documents.

29. The method of claim 24, wherein those documents in each (i−

1)'"'"'th collection which were identified toward the user but which are not in the i'"'"'th selected subset define an i'"'"'th non-selected subset of documents,

wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space, in response to user selection of an i'"'"'th selected subset of the documents from the (i−

1)'"'"'th collection of documents, comprises adding a plurality of added constraints on the embedding space,

wherein the plurality of added constraints are satisfied by a particular candidate document X if and only if d(A,X)<

d(B,X) for all documents A in the i'"'"'th selected subset and for all documents B in the i'"'"'th non-selected subset of documents.

30. The method of claim 1, wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space comprises updating a hyperplane in the embedding space, the i'"'"'th candidate space being a region of the embedding space which is bounded by the updated hyperplane.

31. The method of claim 1, wherein the embedding space is a metric space,

and wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space comprises updating an m-hyperplane in the embedding space, the i'"'"'th candidate space being a region of the embedding space which is bounded by the updated m-hyperplane.

32. The method of claim 1, wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space comprises treating the i'"'"'th subset of documents selected by the user in a machine learning algorithm as training data to update a hypothesis of the user'"'"'s desired target.

33. The method of claim 1, wherein each occurrence of the step of geometrically constraining the embedding space to identify an i'"'"'th candidate space comprises identifying a respective i'"'"'th set of geometric constraints on the embedding space, further comprising:

maintaining a constraints database identifying at least two of the sets of geometric constraints; and

in response to a user request after a Q'"'"'th one of the iterations to return to a P'"'"'th candidate space, P<

Q, identifying toward the user a set of NP>

1 candidate documents from the P'"'"'th candidate space.

34. The method of claim 33, wherein P=Q−

1, and wherein the user request to return the P'"'"'th candidate space comprises user behavior indicating a Back operation.

35. The method of claim 33, further comprising, in conjunction with each iteration of identifying toward the user a set of Ni>

1 candidate documents from the i'"'"'th candidate space, also identifying toward the user a user-perceptible representation of the candidate spaces corresponding to at least two of the sets of geometric constraints then maintained in the constraints database,

and wherein user request to return the P'"'"'th candidate space comprises user behavior selecting the representation of the P'"'"'th candidate space.

36. The method of claim 33, wherein P<

Q−

1.

37. A system for user identification of a desired document, comprising:

a processor; and

a computer readable medium coupled to the processor, the computer readable medium having stored thereon in a non-transitory manner a plurality of software code portions defining logic for;

a first module to provide in a computer readable medium in a non-transitory manner a database identifying a catalog of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the products represented by the pair of documents,

a second module to identify toward the user an initial (i=0) collection of N0>

1 candidate documents from an initial (i=0) candidate space within the embedding space, the initial collection having fewer documents than the initial candidate space,

a third module to, for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected subset of the documents from the (i−

1)'"'"'th collection of documents, geometrically constrain the embedding space to identify an i'"'"'th candidate space such that, according to a predefined definition of collective closeness, the documents in the i'"'"'th candidate space are collectively closer in the embedding space to the documents in the i'"'"'th selected subset, than are the documents in the (i−

1)'"'"'th candidate space; and

identify toward the user an i'"'"'th collection of Ni>

1 candidate documents from the i'"'"'th candidate space, Ni being smaller than the number of documents in the i'"'"'th candidate space, and

a fourth module to cause action to be taken in response to user selection of a particular subset of documents identified toward the user,

wherein the predefined definition of collective closeness is defined such that a candidate document X is considered closer to a document A than to a document B if the distance identified in the embedding space between document X and document A is shorter than the distance identified in the embedding space between document X and document B.