US 8,510,236 B1Granted

Semi-supervised and unsupervised generation of hash functions

AssigneeGoogle Inc.

InventorsSanjiv Kumar, Jun Wang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating hash functions. In one aspect, a method includes generating hash functions by sequentially determining a weight vector for each hash function to maximize an accuracy measure derived from current constraint weights and updating the current constraint weights for use in calculating a weight vector of a next hash function in the sequence. In another aspect, the determined weight vector maximizes an accuracy measure and a variance measure. In still another aspect, a method includes generating an adjusted covariance matrix and generating a sequence of hash functions from the adjusted covariance matrix. In still another aspect, a method includes sequentially generating a sequence of hash functions, where the weight vectors for any previously generated hash functions are used to identify constraints used to generate the weight vector for each next hash function in the sequence.

Claims48

Dependent claims

A system, comprising:

one or more computers configured to perform operations comprising:
storing a plurality of training examples and a plurality of constraints for the training examples, wherein, for one or more constrained training examples in the plurality of training examples, there is at least one constraint in the plurality of constraints, and the constraint either identifies a particular other training example in the plurality of training examples as a neighbor of the constrained training example or identifies a particular other training example in the plurality of training examples as a non-neighbor of the constrained training example;
initializing a current constraint weight for each of the constraints to a respective initial value;
generating an ordered sequence of hash functions, wherein each hash function defines a mapping of features of an item to a bit in a corresponding ordered sequence of bits, wherein the hash function for a particular bit determines the value of the particular bit according to a respective weight vector for the hash function, wherein generating the sequence of hash functions comprises sequentially determining the weight vector for each hash function, and wherein determining the weight vector for a current hash function in the sequence comprises:
determining the weight vector for the current hash function, wherein the determined weight vector maximizes an accuracy measure, wherein the accuracy measure is derived from a number of constraints satisfied by the weight vector and a number of constraints not satisfied by the weight vector and the current constraint weight of each constraint;
and
updating the current constraint weights for use in calculating a weight vector of a next hash function in the sequence, wherein the current constraint weights are updated to increase a magnitude of the current constraint weight of any constraint not satisfied by the determined weight vector for the current hash function;
and
storing the determined weight vectors in a data store.

6 more elements

A computer-implemented method, comprising:

storing a plurality of training examples and a plurality of constraints for the training examples, wherein, for one or more constrained training examples in the plurality of training examples, there is at least one constraint in the plurality of constraints, and the constraint either identifies a particular other training example in the plurality of training examples as a neighbor of the constrained training example or identifies a particular other training example in the plurality of training examples as a non-neighbor of the constrained training example;
initializing, with one or more computers, a current constraint weight for each of the constraints to a respective initial value;
generating, with the one or more computers, an ordered sequence of hash functions, wherein each hash function defines a mapping of features of an item to a bit in a corresponding ordered sequence of bits, wherein the hash function for a particular bit determines the value of the particular bit according to a respective weight vector for the hash function, wherein generating the sequence of hash functions comprises sequentially determining the weight vector for each hash function, and wherein determining the weight vector for a current hash function in the sequence comprises:
determining the weight vector for the current hash function, wherein the determined weight vector maximizes an accuracy measure, wherein the accuracy measure is derived from a number of constraints satisfied by the weight vector and a number of constraints not satisfied by the weight vector and the current constraint weight of each constraint;
and
updating the current constraint weights for use in calculating a weight vector of a next hash function in the sequence, wherein the current constraint weights are updated to increase a magnitude of the current constraint weight of any constraint not satisfied by the determined weight vector for the current hash function;
and
storing the determined weight vectors in a data store.

5 more elements

A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

storing a plurality of training examples and a plurality of constraints for the training examples, wherein, for one or more constrained training examples in the plurality of training examples, there is at least one constraint in the plurality of constraints, and the constraint either identifies a particular other training example in the plurality of training examples as a neighbor of the constrained training example or identifies a particular other training example in the plurality of training examples as a non-neighbor of the constrained training example;
initializing a current constraint weight for each of the constraints to a respective initial value;
generating an ordered sequence of hash functions, wherein each hash function defines a mapping of features of an item to a bit in a corresponding ordered sequence of bits, wherein the hash function for a particular bit determines the value of the particular bit according to a respective weight vector for the hash function, wherein generating the sequence of hash functions comprises sequentially determining the weight vector for each hash function, and wherein determining the weight vector for a current hash function in the sequence comprises:
determining the weight vector for the current hash function, wherein the determined weight vector maximizes an accuracy measure, wherein the accuracy measure is derived from a number of constraints satisfied by the weight vector and a number of constraints not satisfied by the weight vector and the current constraint weight of each constraint;
and
updating the current constraint weights for use in calculating a weight vector of a next hash function in the sequence, wherein the current constraint weights are updated to increase a magnitude of the current constraint weight of any constraint not satisfied by the determined weight vector for the current hash function;
and
storing the determined weight vectors in a data store.

5 more elements

Dependencies are inferred from the claim text.