Distributed random binning featurization with hybrid two-level parallelism

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 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.

11. The system of claim 10 , wherein the memory further stores instructions to cause the processor to 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 node,

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

12. The system of claim 11 , wherein the memory further stores instructions to cause the processor to perform, 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.

13. The system of claim 11 , wherein a global feature matrix and a global feature vector are generated by gathering different respective local feature index offsets.

14. The system of claim 10 , embodied in a cloud-computing environment.