Google Inc.

Ananda Theertha Suresh

Sanjiv Kumar

Xinnan Yu

Daniel Holtmann-Rice

Hugh Brendan McMahan

Ruiqi Guo

David Morris Simcha

Ehsan Variani

Mitchel Weintraub

Xiang Wu

Krzysztof Marcin Choromanski

Ankit Singh Rawat

Jiecao Chen

The present disclosure provides systems and methods for communication efficient distributed mean estimation. In particular, aspects of the present disclosure can be implemented by a system in which a number of vectors reside on a number of different clients, and a centralized server device seeks to estimate the mean of such vectors. According to one aspect of the present disclosure, a client computing device can rotate a vector by a random rotation matrix and then subsequently perform probabilistic quantization on the rotated vector. According to another aspect of the present disclosure, subsequent to quantization but prior to transmission, the client computing can encode the quantized vector according to a variable length coding scheme (e.g., by computing variable length codes).

Systems and methods for communication efficient distributed mean estimation

Systems and methods for low bias negative sampling of classes according to the sampled softmax method are described herein. The systems and methods can include training a machine-learned model for classifying inputs into one or more classes of a plurality of classes, each of the plurality of classes having an associated class embedding in a plurality of class embeddings. The systems and methods can include selecting, by the one or more computing devices, one or more negative classes from the plurality of classes based at least in part on a probability distribution approximating a softmax distribution, wherein the probability distribution is determined based at least in part on a Random Fourier Features map.

Sampled softmax with Random Fourier features

Techniques of generating input for a kernel-based machine learning system that uses a kernel to perform classification operations on data involve generating unbiased estimators for gaussian kernels according to a new framework called Structured Orthogonal Random Features (SORF). The unbiased estimator Kto the kernel involves a linear transformation matrix Wcomputed using products of a set of pairs of matrices, each pair including an orthogonal matrix and respective diagonal matrix whose elements are real numbers following a specified probability distribution. Typically, the orthogonal matrix is a Walsh-Hadamard matrix, the specified probability distribution is a Rademacher distribution, and there are at least two, usually three, pairs of matrices multiplied together to form the linear transformation matrix W.

Structured orthogonal random features for kernel-based machine learning

Aspects of the present disclosure enable humanly-specified relationships to contribute to a mapping that enables compression of the output structure of a machine-learned model. An exponential model such as a maximum entropy model can leverage a machine-learned embedding and the mapping to produce a classification output. In such fashion, the feature discovery capabilities of machine-learned models (e.g., deep networks) can be synergistically combined with relationships developed based on human understanding of the structural nature of the problem to be solved, thereby enabling compression of model output structures without significant loss of accuracy. These compressed models provide improved applicability to 'on device' or other resource-constrained scenarios.

Exponential modeling with deep learning features

The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

Multiscale quantization for fast similarity search

Implementations provide an efficient system for calculating inner products between high-dimensionality vectors. An example method includes clustering database items represented as vectors, selecting a cluster center for each cluster, and storing the cluster center as an entry in a first layer codebook. The method also includes, for each database item, calculating a residual based on the cluster center for the cluster the database item is assigned to and projecting the residual into subspaces. The method also includes determining, for each of the subspaces, an entry in a second layer codebook for the subspace, and storing the entry in the first layer codebook and the respective entry in the second layer codebook for each of the subspaces as a quantized vector for the database item. The entry can be used to categorize an item represented by a query vector or to provide database items responsive to a query vector.

Growing community of inventors

New York, NY, United States of America

Ananda Theertha Suresh