Distributed random binning featurization with hybrid two-level parallelism

Patent metadata

Field	Value
Publication number	US-11080228-B2
Application number	US-201715457422-A
Country	US
Kind code	B2
Filing date	Mar 13, 2017
Priority date	Mar 13, 2017
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

A random binning featurization process method, system, and computer program product for a distributed random binning featurization process on one or more multicore systems with a hybrid two-level parallelism, the method including in a training phase, receiving a first data matrix dividing the random binning featurization process into two orthogonal levels, in a high-level generating a randomized number of high-dimension grids and evenly partitioning the grids into nodes in a parallel system, and in a low-level, evenly partitioning dimensions in each grid to construct look-up tables of index vectors and compute a local feature matrix for each node.

First claim

What is claimed is:

1. A computer-implemented random binning featurization process method for a distributed random binning featurization process on one or more multicore systems with a hybrid two-level parallelism, the method comprising:
in a training phase:
receiving a first data matrix;
dividing the random binning featurization process into two orthogonal levels comprising a high-level and a low-level;
in the high-level:
generating a plurality of randomized grids; and
evenly partitioning the generating of grids into nodes in a parallel system; and

in the low-level:
evenly partitioning dimensions in each grid to construct look-up tables of index vectors and compute a local feature matrix for each node,

wherein the hybrid two-level parallelism includes random binning and kernel approximations via featurization,
wherein the random binning has a decomposition of a first form, where a variable in the first form is a grid parameterized by a first function that specifies a width and a bias of a grid with respect to dimensions, and a second variable in the first form is a vector,
wherein, for each grid of the first form, a number of bins is set so a third variable in the first form has only one non-zero entry, and
wherein, in the low-level, a number of threads are launched to simultaneously process attributes of the first data matrix to construct the index vector look-up tables and to compute the local feature matrix,
further comprising:
synchronizing the local feature matrix for each of the nodes to gather global feature offsets; and
generating a global feature matrix from all of the global feature offsets,

wherein the plurality of randomized grids are generated by setting a different random seed to a random number generator, and
wherein the training phase sets up, the hybrid two-level parallelism to achieve advantages of parallel computing. under constraints of data dependency, the advantages including a near-linear speedup in the training phase and a near-linear memory reduction for storing the local feature matrix.

2. The computer-implemented method of claim 1 , further comprising:
in a testing phase:
receiving a second data matrix;
in a high-level of the second data matrix:
generating a plurality of randomized grids; and
evenly partitioning the generating of grids into nodes in a parallel system of the second data matrix; and

in a low-level of the second data matrix:
evenly partitioning dimensions in each grid to search the look-up tables of index vectors and compute a local feature matrix for each nod;

wherein the advantages include the near-linear speedup in the testing phase.

3. The computer-implemented method of claim 2 , further comprising, in each of the training phase and the testing phase:
synchronizing local feature matrices t of respective nodes to gather global feature offsets; and
generating a global feature vector from all of the global feature offsets.

4. The computer-implemented method of claim 2 , wherein a global feature matrix and a global feature vector are generated by gathering different respective local feature index offsets.

5. The computer-implemented method of claim 1 , embodied in a cloud-computing environment.

6. A computer program product for random binning featurization process for a distributed random binning featurization process on one or more multicore systems with a hybrid two-level parallelism, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform:
in a training phase:
receiving a first data matrix;
dividing the random binning featurization process into two orthogonal levels comprising a high-level and a low-level;
in the high-level:
generating a plurality of randomized grids; and
evenly partitioning the generating of grids into nodes in a parallel system; and

in the low-level:
evenly partitioning dimensions in each grid to construct look-up tables of index vectors and compute a local feature matrix for each node,

wherein the hybrid two-level parallelism includes random binning and kernel approximations via featurization, and
wherein the training phase sets up the hybrid two-level parallelism for parallel computing under constraints of data dependency, and
wherein the training phase sets up the hybrid two-level parallelism to achieve advantages of parallel computing under constraints of data dependency, the advantages, including a near-linear speedup in the training phase and a near-linear memory reduction for storing the local feature matrix.

7. The computer program product of claim 6 , wherein the program instructions are executed by the computer to cause the computer to further perform:
in a testing phase:
receiving a second data matrix;
in a high-level of the second data matrix:
generating a plurality of randomized grids; and
evenly partitioning the generating of grids into nodes in a parallel system; and

in a low-level of the second data matrix:
evenly partitioning dimensions in each grid to search the look-up tables of index vectors and compute a local feature matrix for each nod;

wherein the advantages include the near-linear speedup in the testing phase.

8. The computer program product of claim 7 , further comprising, in each of the training phase and the testing phase:
synchronizing local feature matrices t of respective nodes to gather global feature offsets; and
generating a global feature vector from all of the global feature offsets.

9. The computer program product of claim 7 , wherein a global feature matrix and a global feature vector are generated by gathering different respective local feature index offsets.

10. A random binning featurization process system for a distributed random binning featurization process on one or more multicore systems with a hybrid two-level parallelism, said system comprising:
a processor; and
a memory, the memory storing instructions to cause the processor to perform:
in a training phase:
receiving a first data matrix;
dividing the random binning featurization process into two orthogonal levels comprising a high-level and a low-level;
in the high-level:
generating a plurality of randomized grids; and
evenly partitioning the generating of grids into nodes in a parallel system; and

in the low-level:
evenly partitioning dimensions in each grid to construct look-up tables of index vectors and compute a local feature matrix for each node,

wherein the hybrid two-level parallelism includes random binning and kernel approximations via featurization,
wherein the random binning has a decomposition of a first form k RB (x i , x j )=∫ δ p(δ) ϕ Bδ (x i ) T ϕ Bδ (x j )dδ, where B δ is a grid parameterized by δ=(δ 1 , u 1 , . . . , δ d , u d ) that specifies a width and a bias of a grid with respect to d dimensions, and B δ (x) is a vector which has ϕ b (x i ) =1, if b=└(x i (1)−u 1 /δ 1 ┘, . . . , └(x i (d)−u d /δd┘), and ϕ b (x i )=0 otherwise for any b∈B δ ,
wherein, for each grid B δ , a number of bins |B δ | is set so ϕ b (x) has only 1 non-zero entry, and
wherein, in the low-level, a number of threads are launched to simultaneously process attributes of the first data matrix to construct the index vector look-up tables and to compute the local feature matrix,
further comprising:
synchronizing the local feature matrix for each of the nodes to gather global feature offsets; and
generating a global feature matrix from all of the global feature offsets,

wherein the plurality of randomized grids are generated by setting a different random seed to a random number generator,
wherein th

Assignees

• IBM

Inventors

• Fong Liana Liyow
• Tan Wei
• Witbrock Michael
• Wu Lingfei

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F15/76

  Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16) · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06N20/10

  using kernel methods, e.g. support vector machines [SVM] · CPC title

• G06F15/80 Primary

  comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15}) · CPC title