US 10,482,392 B2Granted

Robust large-scale machine learning in the cloud

AssigneeGoogle Inc.

InventorsSteffen Rendle, Dennis Craig Fetterly, Eugene J. Shekita, Bor-yiing Su

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present disclosure provides a new scalable coordinate descent (SCD) algorithm and associated system for generalized linear models whose convergence behavior is always the same, regardless of how much SCD is scaled out and regardless of the computing environment. This makes SCD highly robust and enables it to scale to massive datasets on low-cost commodity servers. According to one aspect, by using a natural partitioning of parameters into blocks, updates can be performed in parallel a block at a time without compromising convergence. Experimental results on a real advertising dataset are used to demonstrate SCD's cost effectiveness and scalability.

Claims15

Dependent claims

A computer-implemented method, comprising:

obtaining, by one or more computing machines, a training dataset, the training dataset comprising a plurality of examples, each example comprising entries for a plurality of features;
partitioning, by the one or more computing machines, the plurality of features into a plurality of blocks, wherein at least one of the plurality of blocks contains at least two features, and wherein, for each block, a respective feature subvector for each example has at most one non-zero entry;
learning, by the one or more computing machines using at least some of the plurality of examples of the training dataset, a plurality of model parameters from the plurality of blocks, wherein learning the model parameters comprises performing, by the one or more computing machines, a plurality of iterations, and wherein performing the plurality of iterations comprises processing, by the one or more computing machines, only one of the plurality of blocks per iteration.

A distributed computing system to perform large-scale machine learning, the system comprising:

a master computing machine that includes at least one processing device;
and
a plurality of worker computing machines under control of the master computing machine, wherein each worker computing machine includes at least one processing device;
wherein the system is configured to:
partition a plurality of features of a training dataset into a plurality of blocks, wherein the training dataset comprises a plurality of examples, wherein each example comprises entries for the plurality of features, wherein at least one of the plurality of blocks comprises at least two features, and wherein, for each block, a respective feature subvector for each example has at most one non-zero entry;
and
perform a plurality of iterations of a machine learning technique with respect to at least some of the plurality of examples of the training dataset to learn a plurality of parameters of a model from the plurality of blocks, and wherein the system is configured to process only one of the plurality of blocks per iteration.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/429,216Filed 10 Feb 2017 · us provisional application
Priority: 12 Feb 2016
Published: US 2017/0236072 A117 Aug 2017
Granted: 19 Nov 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G06N 20/00
Machine learning
G06F 3/0644
Organizing or formatting or addressing of data: management of space entities, e.g. partitions, extents, pools
G06F 3/0655
Making use of a particular technique: vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more…
G06F 3/067
Adopting a particular infrastructure: distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Family

Application62/294,683Us provisional application · filed 12 Feb 2016
US 2017/0236072 A1Pre-grant publication · published 17 Aug 2017
US 10,482,392 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key