US 8,898,172 B2Granted

Parallel generation of topics from documents

AssigneeGoogle Inc.

InventorsZhiyuan Liu, Yuzhou Zhang, Edward Y. Chang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for enhanced parallel latent Dirichlet allocation (PLDA+). A PLDA+ system is a system of multiple processors that are configured to generate topics from multiple documents. The multiple processors are designated as two types: document processors and matrix processors. The documents are distributed among the document processors. Generated topics are distributed among the matrix processors. Tasks performed on the document processors and matrix processors are segregated into two types of tasks: computation-bound tasks and communication-bound tasks. Computation-bound tasks are CPU intensive tasks; communication-bound tasks are network intensive tasks. Data placement and pipeline strategies are employed such that the computation-bound tasks and the communication-bound tasks are distributed to the processors in a balanced manner, and performed in parallel.

Claims23

Dependent claims

A method, comprising:

extracting a word-topic matrix from a set of one or more documents using one or more document processors and a plurality of matrix processors, the word-topic matrix including a plurality of topics of the set of one or more documents, wherein:
each of the topics is defined at least in part by one or more words of a word set, each of the one or more words being associated with a respective probability, the word set comprising words from a word index of the set of one or more documents;
the word-topic matrix is defined at least in part by a first dimension corresponding to the one or more topics and a second dimension corresponding to the word set;
words in the word set are allocated to the plurality of matrix processors by:
determining a weight of each word in the word set by determining a number of document processors on which the word resides,
determining a load of each of the plurality of matrix processors,
sorting the words in the word set according to weights of the words, and
iteratively allocating a word having a largest weight to a matrix processor having a least load;
the matrix processors include:
a first matrix processor programmed to store and process a first portion of the word-topic matrix corresponding to a first subset of the word set;
and
a second matrix processor programmed to store and process a second portion of the word-topic matrix corresponding to a second subset of the word set, the second subset of the word set being different from the first subset;
and
each of the one or more document processors is programmed to perform topic extraction operations in parallel to matrix exchange operations, wherein:
the topic extraction operations comprise sampling the set of one or more documents for one or more first topics using the first portion of the word-topic matrix stored at the first matrix processor;
and
the matrix exchange operations comprise at least one of:
fetching, from the second matrix processor, the second portion of the word-topic matrix to be used in sampling the set of one or more documents for one or more second topics;
or
upon extraction of at least one second topic where the extracted second topic corresponds to a word in the second subset, requesting the second matrix processor to update the second portion of the word-topic matrix using the extracted second topic.

17 more elements

A system comprising:

one or more document processors and a plurality of matrix processors, the system configured to perform operations comprising:
extracting a word-topic matrix from a set of one or more documents using the one or more document processors and the plurality of matrix processors, the word-topic matrix including a plurality of topics of the set of one or more documents, wherein:
each of the topics is defined at least in part by one or more words of a word set, each of the one or more words being associated with a probability, the word set comprising words from a word index of the set of one or more documents;
the word-topic matrix is defined at least in part by a first dimension corresponding to the one or more topics and a second dimension corresponding to the word set;
words in the word set are allocated to the plurality of matrix processors by:
determining a weight of each word in the word set by determining a number of document processors on which the word resides,
determining a load of each of the plurality of matrix processors,
sorting the words in the word set according to weights of the words, and
iteratively allocating a word having a largest weight to a matrix processor having a least load;
the matrix processors include:
a first matrix processor programmed to store and process a first portion of the word-topic matrix corresponding to a first subset of the word set;
and
a second matrix processor programmed to store and process a second portion of the word-topic matrix corresponding to a second subset of the word set;
and
each of the one or more document processors is programmed to perform topic extraction operations and matrix exchange operations, the topic extraction operations to be performed in parallel to the matrix exchange operations, wherein:
the topic extraction operations comprise sampling the set of one or more documents for one or more first topics using the first portion of the word-topic matrix stored at the first matrix processor;
and
the matrix exchange operations comprise at least one of:
fetching, from the second matrix processor, the second portion of the word-topic matrix to be used in sampling the set of one or more documents for one or more second topics;
or
upon extraction of at least one second topic where the extracted second topic corresponds to a word in the second subset, requesting the second matrix processor to update the second portion of the word-topic matrix using the extracted second topic.

18 more elements

A computer program product, encoded on a non-transitory computer-readable storage device, operable to cause one or more document processors and a plurality of matrix processors to perform operations comprising:

extracting a word-topic matrix from a set of one or more documents, the word-topic matrix including a plurality of topics of the set of one or more documents, wherein:
each of the topics is defined at least in part by one or more words of a word set, each of the one or more words being associated with a probability, the word set being created from a word index of the set of one or more documents;
the word-topic matrix is defined at least in part by a first dimension corresponding to the one or more topics and a second dimension corresponding to the word set;
words in the word set are allocated to the plurality of matrix processors by:
determining a weight of each word in the word set by determining a number of document processors on which the word resides,
determining a load of each of the plurality of matrix processors,
sorting the words in the word set according to weights of the words, and
iteratively allocating a word having a largest weight to a matrix processor having a least load;
the matrix processors include:
a first matrix processor programmed to store and process a first portion of the word-topic matrix corresponding to a first subset of the word set;
and
a second matrix processor programmed to store and process a second portion of the word-topic matrix corresponding to a second subset of the word set;
and
each of the one or more document processors is programmed to perform topic extraction operations and matrix exchange operations, the topic extraction operations to be performed in parallel to the matrix exchange operations, wherein:
the topic extraction operations comprise sampling the set of one or more documents for one or more first topics using the first portion of the word-topic matrix stored at the first matrix processor;
and
the matrix exchange operations comprise at least one of:
fetching, from the second matrix processor, the second portion of the word-topic matrix to be used in sampling the set of one or more documents for one or more second topics;
or
upon extraction of at least one second topic where the extracted second topic corresponds to a word in the second subset, requesting the second matrix processor to update the second portion of the word-topic matrix using the extracted second topic.

17 more elements

A method executed by one or more computers, comprising:

allocating a first portion of a word-topic matrix to a first matrix processor, the word-topic matrix including a plurality of topics of a set of one or more documents, each topic comprising one or more words of a word set, each of the one or more words being associated with a respective probability, the word set comprising words from a word index of the set of one or more documents;
allocating a second portion of the word-topic matrix to a second matrix processor, the second portion of the word-topic matrix being different from the first portion of the word-topic matrix, wherein words in the word set are allocated to the plurality of matrix processors by:
determining a weight of each word in the word set by determining a number of document processors on which the word resides,
determining a load of each of the plurality of matrix processors,
sorting the words in the word set according to weights of the words, and
iteratively allocating a word having a largest weight to a matrix processor having a least load;
performing, on a document processor, topic extraction operations, the document extraction operations comprising sampling the set of one or more documents for one or more first topics using the first portion of the word-topic matrix stored at the first matrix processor;
and
performing, on the document processor, and in parallel to performing the topic extraction operations, matrix exchange operations, the matrix exchange operations comprising at least one of:
fetching, from the second matrix processor, the second portion of the word-topic matrix to be used in sampling the set of one or more documents for one or more second topics;
or
upon extraction of at least one second topic wherein the extracted second topic corresponds to a word in the second subset, requesting the second matrix processor to update the second portion of the word-topic matrix using the extracted second topic.

9 more elements

A computer program product, stored on a non-transitory computer-readable storage device, operable to cause one or more computers to perform operations comprising:

allocating a first portion of a word-topic matrix to a first matrix processor, the word-topic matrix including a plurality of topics of a set of one or more documents, each topic comprising one or more words of a word set, each of the one or more words being associated with a respective probability, the word set comprising words from a word index of the set of one or more documents;
allocating a second portion of the word-topic matrix to a second matrix processor, the second portion of the word-topic matrix being different from the first portion of the word-topic matrix, wherein words in the word set are allocated to the plurality of matrix processors by:
determining a weight of each word in the word set by determining a number of document processors on which the word resides,
determining a load of each of the plurality of matrix processors,
sorting the words in the word set according to weights of the words, and
iteratively allocating a word having a largest weight to a matrix processor having a least load;
performing, on a document processor, topic extraction operations, the document extraction operations comprising sampling the set of one or more documents for one or more first topics using the first portion of the word-topic matrix stored at the first matrix processor;
and
performing, on the document processor, and in parallel to performing the topic extraction operations, matrix exchange operations, the matrix exchange operations comprising at least one of:
fetching, from the second matrix processor, the second portion of the word-topic matrix to be used in sampling the set of one or more documents for one or more second topics;
or
upon extraction of at least one second topic wherein the extracted second topic corresponds to a word in the second subset, requesting the second matrix processor to update the second portion of the word-topic matrix using the extracted second topic.

9 more elements

Dependencies are inferred from the claim text.