We provide an algorithm for polynomial feature expansion that both operates on and produces a compressed sparse row matrix without any densification. For a vector of dimension D, density d, and degree k the algorithm has time complexity O(dD) where k is the polynomial-feature order; this is an improvement by a factor d over the standard method.
1 INTRODUCTION
Polynomial feature expansion has long been used in statistics to approximate nonlinear functions Gergonne (1974); Smith (1918). The compressed sparse row (CSR) matrix format is a widelyused data structure to hold design matrices for statistics and machine learning applications. However, polynomial expansions are typically not performed directly on sparse CSR matrices, nor on any sparse matrix format for that matter, without intermediate densification steps. This densification not only adds extra overhead, but wastefully computes combinations of features that have a product of zero, which are then discarded during conversion into a sparse format.
We provide an algorithm that allows CSR matrices to be the input of a polynomial feature expansion without any densification. The algorithm leverages the CSR format to only compute products of features that result in nonzero values. This exploits the sparsity of the data to achieve an improved time complexity of O(dkDk) on each vector of the matrix where k is the degree of the expansion, D is the dimensionality, and d is the density. The standard algorithm has time complexity O(Dk). Since 0 ≤ d ≤ 1, our algorithm is a significant improvement. While the algorithm we describe uses CSR matrices, it could be modified to operate on other sparse formats.
2 PRELIMINARIES
Matrices are denoted by uppercase bold letters thus: A. The ithe row of A is written ai. All vectors are written in bold, and a, with no subscript, is a vector.
A compressed sparse row (CSR) matrix representation of an r-row matrix A consists of three vectors: c, d, and p and a single number: the number of columns of A. The vectors c and d contain the same number of elements, and hold the column indices and data values, respectively, of all nonzero elements of A. The vector p has r entries. The values in p index both c and d. The ith entry pi of p tells where the data describing nonzero columns of ai are within the other two vectors: cpi:pi+1 contain the column indices of those entries; dpi:pi+1 contain the entries themselves. Since only nonzero elements of each row are held, the overall number of columns of A must also be stored, since it cannot be derived from the other data.
Scalars, vectors, and matrices are often referenced with the superscript k. This is not to be interpreted as an exponent, but to indicate that it is the analogous aspect of that which procedes it, but in its polynomial expansion form. For example, c2 is the vector that holds columns for nonzero values in A’s quadratic feature expansion CSR representation.
For simplicity in the presentation, we work with polynomial expansions of degree 2, but continue to use the exponent k to show how the ideas apply in the general case. ∗Now at Google †The authors contributed equally important and fundamental aspects of this work.
We do provide an algorithm for third degree expansions, and derive the big-O time complexity of the general case.
We have also developed an algorithm for second and third degree interaction features (combinations without repetition), which can be found in the implementation.
3 MOTIVATION
In this section, we present a strawman algorithm for computing polynomial feature expansions on dense matrices. We then modify the algorithm slightly to operate on a CSR matrix, in order to expose its infeasibility in that context. We then show how the algorithm would be feasible with an added component, which we then derive in the following section.
3.1 DENSE EXPANSION ALGORITHM
A natural way to calculate polynomial features for a matrix A is to walk down its rows and, for each row, take products of all k-combinations of elements. To determine in which column of Aki products of elements in Ai belong, a simple counter can be set to zero for each row of A and incremented efter each polynomial feature is generated. This counter gives the column of Aki into which each expansion feature belongs.
SECOND ORDER (k = 2) DENSE POLYNOMIAL EXPANSION ALGORITHM(A) 1 N = row count of A 2 D = column count of A 3 Ak = empty N × ( D 2 ) matrix 4 for i = 0 to N − 1 5 cp = 0 6 for j1 = 0 to D − 1 7 for j2 = j1 to D − 1 8 Akicp = Aij1 ·Aij2 9 cp = cp + 1
3.2 IMPERFECT CSR EXPANSION ALGORITHM
Now consider how this algorithm might be modified to accept a CSR matrix. Instead of walking directly down rows of A, we will walk down sections of c and d partitioned by p, and instead of inserting polynomial features into Ak, we will insert column numbers into ck and data elements into dk.
INCOMPLETE SECOND ORDER (k = 2) CSR POLYNOMIAL EXPANSION ALGORITHM(A) 1 N = row count of A 2 pk = vector of size N + 1 3 pk0 = 0 4 nnzk = 0 5 for i = 0 to N − 1 6 istart = pi 7 istop = pi+1 8 ci = cistart:istop 9 nnzki = (|ci| 2
) 10 nnzk = nnzk + nnzki 11 pki+1 = p k i + nnz k i
// Build up the elements of pk, ck, and dk
12 pk = vector of size N + 1 13 ck = vector of size nnzk 14 dk = vector of size nnzk 15 n = 0 16 for i = 0 to N − 1 17 istart = pi 18 istop = pi+1 19 ci = cistart:istop 20 di = distart:istop 21 for c1 = 0 to |ci| − 1 22 for c2 = c1 to |ci| − 1 23 dkn = dc0 · dc1 24 ckn =? 25 n = n+ 1
The crux of the problem is at line 24. Given the arbitrary columns involved in a polynomial feature of Ai, we need to determine the corresponding column of Aki . We cannot simply reset a counter for each row as we did in the dense algorithm, because only columns corresponding to nonzero values are stored. Any time a column that would have held a zero value is implicitly skipped, the counter would err.
To develop a general algorithm, we require a mapping from columns of A to a column of Ak. If there are D columns of A and ( D k ) columns of Ak, this can be accomplished by a bijective mapping of the following form:
(j0, j1, . . . , jk−1) pj0j1...ik−1 ∈ {0, 1, . . . , ( D
k
) − 1} (1)
such that 0 ≤ j0 ≤ j1 ≤ · · · ≤ jk−1 < D where (j0, j1, . . . , jk−1) are elements of c and pj0j1...ik−1 is an element of ck.
4 CONSTRUCTION OF MAPPING
Within this section, i, j, and k denote column indices. For the second degree case, we seek a map from matrix indices (i, j) (with 0 ≤ i < j < D ) to numbers f(i, j) with 0 ≤ f(i, j) < D(D−1)2 , one that follows the pattern indicated by x 0 1 3x x 2 4x x x 5
x x x x  (2) where the entry in row i, column j, displays the value f(i, j). We let T2(n) = 12n(n + 1) be the nth triangular number; then in Equation 2, column j (for j > 0) contains entries with T2(j − 1) ≤
e < T2(j); the entry in the ith row is just i + T2(j − 1). Thus we have f(i, j) = i + T2(j − 1) = 1 2 (2i + j
2 − j). For instance, in column j = 2 in our example (the third column), the entry in row i = 1 is i+ T2(j − 1) = 1 + 1 = 2. With one-based indexing in both the domain and codomain, the formula above becomes f1(i, j) = 1 2 (2i+ j
2 − 3j + 2). For polynomial features, we seek a similar map g, one that also handles the case i = j. In this case, a similar analysis yields g(i, j) = i+ T2(j) = 12 (2i+ j 2 + j + 1).
To handle three-way interactions, we need to map triples of indices in a 3-index array to a flat list, and similarly for higher-order interactions. For this, we’ll need the tetrahedral numbers T3(n) =∑n
i=1 T2(n) = 1 6 (n 3 + 3n2 + 2n).
For three indices, i, j, k, with 0 ≤ i < j < k < D, we have a similar recurrence. Calling the mapping h, we have
h(i, j, k) = i+ T2(j − 1) + T3(k − 2); (3) if we define T1(i) = i, then this has the very regular form
h(i, j, k) = T1(i) + T2(j − 1) + T3(k − 2); (4) and from this the generalization to higher dimensions is straightforward. The formulas for “higher triangular numbers”, i.e., those defined by
Tk(n) = n∑ i=1 Tk−1(n) (5)
for k > 1 can be determined inductively.
The explicit formula for 3-way interactions, with zero-based indexing, is
h(i, j, k) = 1 + (i− 1) + (j − 1)j 2 + (6)
(k − 2)3 + 3(k − 2)2 + 2(k − 2) 6 . (7)
5 FINAL CSR EXPANSION ALGORITHM
With the mapping from columns of A to a column of Ak, we can now write the final form of the innermost loop of the algorithm from 3.2. Let the mapping for k = 2 be denoted h2. Then the innermost loop becomes:
for c2 = c1 to |ci| − 1 j0 = cc0 j1 = cc1 cp = h
2(j0, j1) dkn = dc0 · dc1 ckn = cp n = n+ 1
The algorithm can be generalized to higher degrees by simply adding more nested loops, using higher order mappings, modifying the output dimensionality, and adjusting the counting of nonzero polynomial features in line 9.
6 TIME COMPLEXITY
6.1 ANALYTICAL
Calculating k-degree polynomial features via our method for a vector of dimensionality D and density d requires ( dD k ) (with repetition) products. The complexity of the algorithm, for fixed k
dD, is therefore
O
(( dD + k − 1
k
)) = O ( (dD + k − 1)! k!(dD − 1)! ) (8)
= O
( (dD + k − 1)(dD + k − 2) . . . (dD)
k!
) (9)
= O ((dD + k − 1)(dD + k − 2) . . . (dD)) for k dD (10) = O ( dkDk ) (11)
6.2 EMPIRICAL
To demonstrate how our algorithm scales with the density of a matrix, we compare it to the traditional polynomial expansion algorithm in the popular machine library scikit-learn Pedregosa et al. (2011) in the task of generating second degree polynomial expansions. Matrices of size 100× 5000 were randomly generated with densities of 0.2, 0.4, 0.6, 0.8, and 1.0. Thirty matrices of each density were randomly generated, and the mean times (gray) of each algorithm were plotted. The red or blue width around the mean marks the third standard deviation from the mean. The time to densify the input to the standard algorithm was not counted.
The standard algorithm’s runtime stays constant no matter the density of the matrix. This is because it does not avoid products that result in zero, but simply multiplies all second order combinations of features. Our algorithm scales quadratically with respect to the density. If the task were third degree expansions rather than second, the plot would show cubic scaling.
The fact that our algorithm is approximately 6.5 times faster than the scikit-learn algorithm on 100× 5000 matrices that are entirely dense is likely a language implementation difference. What matters is that the time of our algorithm increases quadratically with respect to the density in accordance with the big-O analysis.
7 CONCLUSION
We have developed an algorithm for performing polynomial feature expansions on CSR matrices that scales polynomially with respect to the density of the matrix. The areas within machine learning that this work touches are not en vogue, but they are workhorses of industry, and every improvement in core representations has an impact across a broad range of applications.
This paper proposes an algorithm for polynomial feature expansion on CSR matrices, which reduces the time complexity of the standard method by a factor d^k where d is the density of the sparse matrix. The main contribution of this work is not significant enough. The experiments are incomplete and not convincing.
The background of the problem is not sufficiently introduced. There are only two references in the introduction part (overall only three papers are cited), which are from decades ago. Many more relevant papers should be cited from the recent literature.
The experiment part is very weak. This paper claims that the time complexity of their algorithm is O(d^k D^k), which is an improvement over standard method O(D^k) by a factor d^k. But in the experiments, when d=1, there is still a large gap (~14s vs. ~90s) between the proposed method and the standard one. The authors explain this as "likely a language implementation", which is not convincing. To fairly compare the two methods, of course you need to implement both in the same programming language and run experiments in the same environment. For higher degree feature expansion, there is no empirical experiments to show the advantage of the proposed method.
Some minor problems are listed below.
1) In Section 2, the notation "p_i:p_i+1" is not clearly defined.
2) In Section 3.1, typo: "efter" - "after"
3) All the algorithms in this paper are not titled. The input and output is not clearly listed.
4) In Figure 1, the meaning of the colored area is not described. Is it standard deviation or some quantile of the running time? How many runs of each algorithm are used to generate the ribbons? Many details of the experimental settings are missing.