公开(公告)号：US12079700B2

公开(公告)日：2024-09-03

申请号：US15793455

申请日：2017-10-25

Applicant: GOOGLE LLC

Inventor： Daniel Holtmann-Rice ,  Sanjiv Kumar ,  Xinnan Yu ,  Krzysztof Marcin Choromanski ,  Ananda Theertha Suresh

IPC: G06N20/10 ,  G06F17/14 ,  G06F17/16 ,  G06F17/17 ,  G06F18/00 ,  G06N20/00

CPC classification number: G06N20/10 ,  G06F17/14 ,  G06F17/16 ,  G06F17/175 ,  G06F18/00 ,  G06N20/00

Abstract: 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 KSORF to the kernel involves a linear transformation matrix WSORF computed 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 WSORF.

公开(公告)号：US20240135254A1

公开(公告)日：2024-04-25

申请号：US18488951

申请日：2023-10-17

Applicant: Google LLC

Inventor： Harikrishna Narasimhan ,  Wittawat Jitkrittum ,  Aditya Krishna Menon ,  Ankit Singh Rawat ,  Sanjiv Kumar

IPC: G06N20/00 ,  G06N5/04

CPC classification number: G06N20/00 ,  G06N5/04

Abstract: Methods, systems, and apparatus, including computer programs encoded on computer storage media, for post-hoc deferral for classification tasks. In particular, a system can perform either post-hoc threshold correction or post-hoc rejector training to account for the cost of deferring model inputs to an expert system for classification.

公开(公告)号：US20240119052A1

公开(公告)日：2024-04-11

申请号：US18474907

申请日：2023-09-26

Applicant: Google LLC

Inventor： Philip Wenjie Sun ,  Ruiqi Guo ,  Sanjiv Kumar

IPC: G06F16/2453 ,  G06F16/953

CPC classification number: G06F16/24545 ,  G06F16/24549 ,  G06F16/953

Abstract: The disclosure is directed towards automatically tuning quantization-based approximate nearest neighbors (ANN) search methods and systems (e.g., search engines) to perform at the speed-recall pareto frontier. With a desired search cost or recall as input, the embodiments employ Lagrangian-based methods to perform constrained optimization on theoretically-grounded search cost and recall models. The resulting tunings, when paired with the efficient quantization-based ANN implementation of the embodiments, exhibit excellent performance on standard benchmarks while requiring minimal tuning or configuration complexity.

公开(公告)号：US11785073B2

公开(公告)日：2023-10-10

申请号：US17502794

申请日：2021-10-15

Applicant: Google LLC

Inventor： Ananda Theertha Suresh ,  Sanjiv Kumar ,  Hugh Brendan McMahan ,  Xinnan Yu

IPC: H04L67/10 ,  G06F17/16 ,  H03M7/30 ,  H03M7/40 ,  G06F17/12 ,  G06N20/00 ,  G06F17/18 ,  G06N7/01 ,  H04L67/01

CPC classification number: H04L67/10 ,  G06F17/12 ,  G06F17/16 ,  G06F17/18 ,  G06N7/01 ,  G06N20/00 ,  H03M7/3059 ,  H03M7/3082 ,  H03M7/40 ,  H04L67/01

Abstract: 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).

公开(公告)号：US11775589B2

公开(公告)日：2023-10-03

申请号：US17001850

申请日：2020-08-25

Applicant: Google LLC

Inventor： Ruiqi Guo ,  David Simcha ,  Quan Geng ,  Felix Chern ,  Sanjiv Kumar ,  Xiang Wu

IPC: G06F16/20 ,  G06F16/906 ,  G06F16/25 ,  H03M7/30 ,  G06F16/2457

CPC classification number: G06F16/906 ,  G06F16/24578 ,  G06F16/258 ,  H03M7/30

Abstract: Generally, the present disclosure is directed to systems and methods of quantizing a database with respect to a novel loss or quantization error function which applies a weight to an error measurement of quantized elements respectively corresponding to the datapoints in the database. The weight is determined based on the magnitude of an inner product between the respective datapoints and a query compared therewith. In contrast to previous work, embodiments of the proposed loss function are responsive to the expected magnitude of an inner product between the respective datapoints and a query compared therewith and can prioritize error reduction for higher-ranked pairings of the query and the datapoints. Thus, the systems and methods of the present disclosure provide solutions to some of the problems with traditional quantization approaches, which regard all error as equally impactful.

公开(公告)号：US11676033B1

公开(公告)日：2023-06-13

申请号：US16812160

申请日：2020-03-06

Applicant: Google LLC

Inventor： Aditya Krishna Menon ,  Ankit Singh Rawat ,  Sashank Jakkam Reddi ,  Sanjiv Kumar

IPC: G06N3/04 ,  G06N3/084

CPC classification number: G06N3/084 ,  G06N3/04

Abstract: A method for training a machine learning model, e.g., a neural network, using a regularization scheme is disclosed. The method includes generating regularized partial gradients of losses computed using an objective function for training the machine learning model.

公开(公告)号：US11636384B1

公开(公告)日：2023-04-25

申请号：US16595093

申请日：2019-10-07

Applicant: GOOGLE LLC

Inventor： Jeffrey Pennington ,  Sanjiv Kumar

IPC: G06N20/00 ,  G06N7/00 ,  G06F17/16 ,  G06F17/14

Abstract: Implementations provide for use of spherical random features for polynomial kernels and large-scale learning. An example method includes receiving a polynomial kernel, approximating the polynomial kernel by generating a nonlinear randomized feature map, and storing the nonlinear feature map. Generating the nonlinear randomized feature map includes determining optimal coefficient values and standard deviation values for the polynomial kernel, determining an optimal probability distribution of vector values for the polynomial kernel based on a sum of Gaussian kernels that use the optimal coefficient values, selecting a sample of the vectors, and determining the nonlinear randomized feature map using the sampled vectors. Another example method includes normalizing a first feature vector for a data item, transforming the first feature vector into a second feature vector using a feature map that approximates a polynomial kernel with an explicit nonlinear feature map, and providing the second feature vector to a support vector machine.

公开(公告)号：US20230113984A1

公开(公告)日：2023-04-13

申请号：US18081403

申请日：2022-12-14

Applicant: Google LLC

Inventor： Sashank Jakkam Reddi ,  Sanjiv Kumar ,  Satyen Chandrakant Kale

IPC: G06N3/08 ,  G06F17/16 ,  G06N20/00 ,  G06N3/045

Abstract: Generally, the present disclosure is directed to systems and methods that perform adaptive optimization with improved convergence properties. The adaptive optimization techniques described herein are useful in various optimization scenarios, including, for example, training a machine-learned model such as, for example, a neural network. In particular, according to one aspect of the present disclosure, a system implementing the adaptive optimization technique can, over a plurality of iterations, employ an adaptive learning rate while also ensuring that the learning rate is non-increasing.

公开(公告)号：US20220366260A1

公开(公告)日：2022-11-17

申请号：US17245892

申请日：2021-04-30

Applicant: Google LLC

Inventor： Gayan Sadeep Jayasumana Hirimbura Matara Kankanamge ,  Srikumar Ramalingam ,  Sanjiv Kumar

IPC: G06N3/08 ,  G06N3/04 ,  G06K9/62

Abstract: A method includes receiving, by a computing device, training data to train a neural network, wherein the training data comprises a plurality of inputs and a plurality of corresponding labels. The method also includes mapping, by a representation learner of the neural network, the plurality of inputs to a plurality of feature vectors. The method additionally includes training a kernelized classification layer of the neural network to perform nonlinear classification of an input feature vector into one of a plurality of classes, wherein the kernelized classification layer is based on a kernel which enables the nonlinear classification, and wherein the kernel is selected from a space of positive definite kernels based on application of a nonlinear softmax loss function to the plurality of feature vectors and the plurality of corresponding labels. The method further includes outputting a trained neural network comprising the representation learner and the trained kernelized classification layer.

公开(公告)号：US20210326757A1

公开(公告)日：2021-10-21

申请号：US17227851

申请日：2021-04-12

Applicant: Google LLC

Inventor： Ankit Singh Rawat ,  Xinnan Yu ,  Aditya Krishna Menon ,  Sanjiv Kumar

IPC: G06N20/00 ,  G06F17/16 ,  G06N5/02

Abstract: Generally, the present disclosure is directed to systems and methods that perform spreadout regularization to enable learning of a multi-class classification model in the federated setting, where each user has access to the positive data associated with only a limited number of classes (e.g., a single class). Examples of such settings include decentralized training of face recognition models or speaker identification models, where in addition to the user specific facial images and voice samples, the class embeddings for the users also constitute sensitive information that cannot be shared with other users.