Distributed random binning featurization with hybrid two-level parallelism

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.

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 kRB(xi, xj)=∫δp(δ) ϕBδ(xi)TϕBδ(xj)dδ, where Bδ is a grid parameterized by δ=(δ1, u1, . . . , δd, ud) that specifies a width and a bias of a grid with respect to d dimensions, and Bδ(x) is a vector which has ϕb(xi) =1, if b=└(xi(1)−u1/δ1┘, . . . , └(xi(d)−ud/δd┘), and ϕb(xi)=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.