Random Intersection Chains

Drawing inspiration from association rule mining and Random Intersection Trees, we suggest an algorithm that can efficiently detect useful interactions, named Random Intersection Chains. Like other data mining algorithms, frequent itemsets are discovered at first and then confident rules are generated. But instead of scanning the complete database, we adopt random intersections to mine the frequent itemsets, then their frequency and confidence are calculated with the assistant of maximum likelihood estimation or Bayes’ theorem.

The first node of a chain, called the head node, contains the items in a randomly chosen instance. The other nodes in the chain contain the intersection of its previous node and a new randomly chosen instance. We repeatedly choose random instances until the length of a chain reaches the pre-defined threshold, or the number of the items in the last node (named the tail node) is sufficiently small. Finally the itemsets in the tail nodes as well as their subsets are regarded as frequent itemsets. For example, if we want to generate a chain consisting of three nodes, and the chosen instances are $[c_{1},c_{2},c_{3}]$, $[c_{1},c_{2}^{\prime},c_{3}]$, $[c_{1},c_{2},c_{3}^{\prime}]$, where $c_{1}\neq c_{1}^{\prime}$, $c_{2}\neq c_{2}^{\prime}$ and $c_{3}\neq c_{3}^{\prime}$, then the chain is $[C_{1}=c_{1},C_{2}=c_{2},C_{3}=c_{3}]\to[C_{1}=c_{1},C_{3}=c_{3}]\to[C_{1}=c_{1}]$. The procedure of generating $M$ such chains of length $D$ can be seen straightly from Algorithm 1.

The larger frequency a pattern has, the more likely it is to appear in a uniformly chosen instance. Therefore, it’s reasonable to assume the pattern in tail nodes are more frequent than others. After detecting the frequent patterns, Shah and Meinshausen (2014) adopt an estimator based on min-wise hashing to obtain their frequency. Though this estimator enjoys reduced variance compared to that which would be obtained using subsampling, it seems somewhat redundant and unnatural because it’s independent of Random Intersection Trees. However, Random Intersection Chains can estimate frequency by themselves.

For a pattern $s$ with frequency $p_{s}^{(c)}$, denote the number of its appearance in the $m$-th chain for class $c$ by $k_{s,m}^{(c)}$. The likelihood of observing this chain is

where we omit the superscript “$(c)$” to keep notation uncluttered. And we have the likelihood of observing $M$ chains as shown in Equation 4,

where $K_{s}=\sum_{m=1}^{M}k_{s,m}$, $I_{s}=\sum_{m=1}^{M}\mathbbm{1}_{\{k_{s,m}<D\}}$. Thus the log of likelihood is

Setting the derivative of Equation 5 with respect to $p_{s}$ equalling to zero and rearranging, we obtain

where $\bar{k}_{s}=\frac{1}{M}\sum_{m=1}^{M}k_{s,m}$, $\bar{\chi}_{s}=\frac{1}{M}\sum_{m=1}^{M}\mathbbm{1}_{\{k_{s,m}<D\}}$.

Algorithm 2 estimates the frequency of a pattern by maximum likelihood estimation based on Random Intersection Chains. Algorithm 3 provides an estimator of confidence by Bayes’ theorem once the frequency is available.

After the chains are generated, we estimate the frequency of the patterns in the tail nodes. Then the confidence of these patterns is calculated, after which the confident patterns are returned as the useful interactions. We formally describe a basic version of Random Intersection Chains in Algorithm 4, which combines the characteristic of both random intersections and association rule mining.

We now explain Algorithm 4 line by line. There are three parameters in the algorithm, named $D$, $M$ and $\xi$, among which the first two are inherited from random intersections, and the last is from association rule mining. $D$ represents the length of a chain, $M$ stands for the number of chains and $\xi$ is the threshold of confidence.

Line 1 calculates the proportion of each class, where $I^{(c)}$ represents the indices of observations in class $c$, $C$ is the set of class labels. These proportions will be used later to calculate the confidence. Line 2 initializes the set of frequent patterns, which is now an empty set, for each class. For every class, $M$ chains are generated at Line 4, then the patterns in the tail nodes as well as all their subpatterns are added to the sets created at Line 2. The frequency of a pattern in every class is calculated at Line 10, after which the confidence is calculated at Line 11. If the confidence of a pattern is larger than the pre-defined threshold, this pattern will be included in the resulting set at Line 13. Finally the resulting set is returned at Line 17.

The longer a chain is, the harder for a pattern to appear in its tail node. Oppositely, the more chains, the more likely for a pattern to be observed in at least one of their tail nodes. By adjusting $D$ and $M$ carefully, we can control which patterns will be considered as “frequent”. As proven in Theorem 1, there actually exist choices of parameters such that the returned set contains frequent patterns with arbitrarily high probability while including the infrequent ones with probability lower than any given threshold.

From the proof of Algorithm 1, it follows that M and D meet the demand if

where

So we have Corollary 2.

Usually $\eta_{1}$ and $\eta_{2}$ are small, thus $a$ is large and $b$ is small. Assume $a\geq b+1$, then the first item in the braces of Equation 7 is no greater than 0. If $a\geq\frac{1}{2}b$, the second item in the braces of Equation 7 is no less than 0. In this case, Corollary 3 holds.

Compared with Random Intersection Trees, it is more convenient to apply Random Intersection Chains on multi-class classification tasks. The former is originally designed for binary classification, and detects the interesting patterns for one class at a time. But it’s unable to answer which patterns are the most useful ones among different classes. On the contrary, since Random Intersection Chains not only detects the frequent patterns but also estimates their frequency and confidence, we can directly compare the frequency or confidence of patterns in different classes. Thus we can select the patterns from all the classes simultaneously.

Thanks to its abandon of scanning the complete database, the naive version of Random Intersection Chains is more efficient than the traditional methods on large data sets. Another advantage is that it can extract high-order interactions without discovering all lower-order interactions beforehand. However, this characteristic is also where a drawback of Random Intersection Chains comes from.

It is obvious that any subpattern of a frequent pattern is also frequent. Since the pattern in the tail node of a chain may contain many components, there are in fact a huge number of frequent patterns we have obtained. For example, if an interaction in a tail node contains $k$ components, then all the combinations of these components are frequent. So there are $2^{k}-1$ frequent patterns indeed. It’s computationally infeasible to calculate frequency and confidence for every frequent pattern in this sense. And it’s even impossible to pass over all these subpatterns due to its exponential complexity.

Random Intersection Trees (Shah and Meinshausen, 2014) gets over this difficulty by giving priority to the largest frequent patterns. That is, the authors only consider the patterns whose every superset is infrequent. They limit their attention to the patterns of the leaf nodes, but ignore their subpatterns. This may not be a satisfactory solution, since a subpattern is more frequent than the complete pattern, and sometimes can also have higher confidence. Overlooking them may lead to the missing of informative interactions. Fortunately, by taking advantage of a data structure named priority queue, we find an approach that selects the most frequent patterns from the power set of a given interaction in polynomial time.

A priority queue is a data structure for maintaining a set of elements, each with an associated value called a key (Cormen et al., 2009). In a priority queue, an element with high priority is served before an element with low priority. Like many implementations, we prefer the element enqueued earlier if two elements have the same priority. This may seem arbitrary, but is meaningful later in this work. In this paper, we give priority to elements with larger keys, so what we used is exactly a max-priority queue. A series of operations should be supported by such a queue, and the following are required in our method.

• •

  INSERT($S,x,key$): inserts the element $x$ with $key$ into the set $S$, which is equivalent to the operation $S=S\cup\{x\}$;

• •

  EXTRACT-MAX($S$): removes and returns the element with the largest key in $S$;

• •

  COPY($S$): returns a copy of $S$.

We add a new attribute $size$ to a priority queue, which indicates its maximum capacity. In other words, we will discard an element if its $key$ is not the $S.size$ largest, which can be done by removing the element with the smallest key after inserting a new element into a full queue. If $S.size$ is zero, then this priority queue will always be empty.

With priority queues defined above, we come up with Algorithm 5. The main difference between Algorithm 4 and Algorithm 5 lies in the approach of identifying which patterns are frequent or confident. In Algorithm 4, all the patterns in the tail nodes and their subpatterns are considered to be frequent, which may result in heavy computation. On the contrary, Algorithm 5 only takes the $d_{\rm freq}$ most frequent patterns into consideration. What’s more, Algorithm 5 returns the $d_{\rm conf}$ most confident patterns, while Algorithm 4 identifies confident patterns by a pre-defined threshold.

The most important improvement of Algorithm 5 lies in Line 6, where the algorithm named “InsertFreqSubset” is used to select the most frequent subsets among the power set of a given itemset. The algorithm works by selecting frequent itemsets level-wisely. We have known that an itemset can not be more frequent then any of its subsets. So if an itemset fails to be in the priority queue, so do its supersets. For an itemset $s$ consisting of more than one item, it could be uniquely represented by $s=\{a\}\cup(s\setminus\{a\})$, where $a$ is the most frequent item in $s$ (if there are several items having the same frequency, choose the one enqueued earliest, which coincides with the implementation of our priority queue). $\{a\}$ is by definition more frequent than the other singleton subsets of $s\setminus\{a\}$, thus it’s more frequent than $s\setminus\{a\}$. So if we extract the elements from the priority queue in order, $s\setminus\{a\}$ occurs later than $\{a\}$. This sheds some light on the search for frequent $k$-order itemsets. We need first take care of the 1-order itemsets in the priority queue. For each 1-order itemset, we only pay attention to the ($k$-1)-order itemsets that are extracted later than it. If the 1-order itemset and a ($k$-1)-order itemset are disjoint, then their union is a candidate frequent $k$-order itemset. We need only calculate the frequency of these $k$-order itemsets.

The detailed InsertFreqSubset algorithm is given in Algorithm 6. Frequent 1-order itemsets are selected in Line 1-4. This is followed by a for-loop, where the loop index variable $k$ represents the size of the candidate itemsets. Since extracting the elements from a queue will change the queue, we make a copy of the queue at Line 5 and Line 11, then apply the EXTRACT-MAX operation on the replica to prevent unwanted changes. The outer while-loop aims to find 1-order itemsets in the priority queue. For an 1-order itemset, the inner while-loop is conducted to find its frequent $k$-order supersets. ($k$-1)-order itemsets in the remaining queue is caught at Line 15, then a candidate $k$-order itemset is generated by combining the 1- and ($k$-1)-order itemset, whose frequency is estimated at Line 16. After that the candidate itemset is inserted into the resulting queue $S^{(c)}$ at Line 17.

The changes of the queue capacity at Line 9 and 14, as well as INSERT operations at Line 18 and 19 have no effects on the resulting queue. But they can squeeze out the infrequent 1- or ($k$-1)-order itemsets as soon as possible, which reduces the number of candidates and speed up the algorithm.

Most intuitively, a chain can be represented by recording each itemsets at a node. But this not only causes a wastage of space, but also makes it troublesome to generate or check a chain. For example, to compute the intersection, Shah and Meinshausen (2014) check whether each component of the current interaction is in the new observation. Every such check is $O(\log p)$ even if a binary search is adopted. If most of the components are sufficiently frequent, the size of interactions will keep close to $p$, so the time complexity of an intersection can be near $O(p\log p)$. The total time needed to generate a chain of length $D$ is near $O(Dp\log p)$, and the memory required to store this chain is near $O(Dp)$.

It’s worth noting that the itemsets in a chain is descending. That is to say, the itemset in a node (except the head node) must be a subset of its previous node. So rather than record the chain as a series of ordered itemsets, we can view it from the aspect of items. A chain can be represented by two $p$-dimensional vectors, where the first is a copy of the first randomly chosen observation, and the other records how many times the corresponding item occurs in the chain. For instance, the chain $[C_{1}=c_{1},C_{2}=c_{2},C_{3}=c_{3}]\to[C_{1}=c_{1},C_{3}=c_{3}]\to[C_{1}=c_{1}]$ can be represented by {$[C_{1}=c_{1},C_{2}=c_{2},C_{3}=c_{3}]$, [3, 1, 2]}, or simply {$[c_{1},c_{2},c_{3}]$, [3, 1, 2]}. The memory to store a chain is thus $O(p)$, and is independent of its length. The memory required to store $M$ chains is the same as $2M$ observations. For large data sets, the number of observations $N$ can be very huge, thus additional $2M$ observations usually have little influence on the requirement of storage. An item is in the $i$-th node if and only if it occurs at least $i$ times. When adding a new node to the chain, we need only pay attention to the items whose number of occurrences equals to the current length of the chain. If these items also appear in the new randomly chosen observation, then making the intersection can be done simply by adding one to their number of occurrences. In this way, the time complexity of adding a node is $O(p)$, and generating a chain of length $D$ has a time complexity of $O(pD)$. Making use of this representation, we have Theorem 4 and Theorem 5.

From Theorem 4 and Theorem 5 we can conclude that Random Intersection Chains will be efficient when $p_{1}$ is large and $p_{2}$ is small. For the ideal situation where $p_{1}$ approaches 1 and $p_{2}$ tends to 0, $M^{*}$ and $D^{*}$ are near 1, both the space and time complexity of chain generation are linear with the number of features $p$ or the number of different labels in $C$.

As stated earlier in Section 3.2, finding a frequent pattern $s$ means we have actually found $O(2^{|s|})$ frequent patterns, since every subpattern of $s$ is frequent. It’s not realistic to take all of them into consideration, not even to perform a traversal. Algorithm 6 solves this problem with the help of priority queues. We provide Theorem 6 to guarantee the validity and time complexity of Algorithm 6.

If the input priority queue of Algorithm 6 is not empty, e.g. $S^{(c)}=S^{\prime}\neq\emptyset$, then during the running of the algorithm, itemsets with small frequency in $S^{\prime}$ will be squeezed out by the subsets of the input itemset $s$, while itemsets with large frequency in $S^{\prime}$ occupies a position in the priority queue from beginning to end. So at the end of the algorithm, the priority queue $S^{(c)}$ contains the $d_{\rm freq}$ most frequent itemsets in $S^{\prime}\cup Pow(s)$. As a result, after the for-loop in Line 5-7 of Algorithm 5, $S^{(c)}$ contains the $d_{\rm freq}$ most frequent itemsets found by the chains for class $c$.

Click-through rate (CTR) prediction is an important application of machine learning algorithms, which aims to predict the ratio of clicks to impressions of a specific link. The input features associate with either a user or an item, many of which are categorical and of high cardinality. The label indicates the clicks of a user to an item. Usually few items will be clicked by a user, which makes the data unbalanced.

We conduct experiments on two public real-world datasets, named Criteo and Avazu. Criteo data set consists of a portion of Criteo’s traffic over a period of 7 days. There are 45 million users’ clicking records on displayed ads in the data, and the rows are chronologically ordered. It contains 26 categorical features and 13 numerical features. Avazu data set contains the records of whether a displayed mobile ad is clicked by a user or not. Click-through data of 10 days, ordered chronologically, is provided. It has 23 features, all of which are categorical. And the total number of samples is above 40 million.

If one-hot encoding is applied, there will be 998,960 binary features for Criteo data set and 1,544,428 features for Avazu data set, which is obviously unacceptable. We first unify all the uncommon categories into a single category “others”. A category is “uncommon” if the number of its occurrences is less than 10 for Criteo or 5 for Avazu. Then the categorical features are label encoded. As for numerical features, a value $z$ will be transformed to $(\log z)^{2}$ if $z>2$. Finally, each data set is divided into 10 parts, where 8 parts are used for training, 1 part for validation and 1 part for test. This procedure is actually the same as in the work of Song et al. (2019), which is also adopted by Song et al. (2020); Tsang et al. (2020).

As analyzed in Section 4 and Section 5, the more chains are generated, the more time and memory are needed, but the more accurate estimations of frequency and confidence are obtained. We apply Random Intersection Chains on both data sets with $M$ from 100 to 15,000 for each part in the training set. The running time is shown in Figure 1(a). As for memory requirements, the additional space cost caused by Random Intersection Chains is at most the same as $2\times(15,000\times 8)=240,000$ observations, which is very small when compared with the original 40 million observations. To show the consistency of Random Intersection Chains, we adopt the Jaccard-index as the criterion of similarity between two sets $S$ and $S^{\prime}$, which is defined as

We calculate the Jaccard-index for interactions found by $M$=15000 and the interactions found by smaller values of $M$, and the results are exhibited in Figure 1(b). As can be seen from Figure 1(a), the running time is linear with the number of chains, and it’s relatively small considering the rather large size of the data sets. Figure 1(b) indicates that the returns of Random Intersection Chains are very similar for large $M$, which verifies the consistency.

One of the advantages of the interactions defined in this paper is their interpretability. Since the Avazu data set contains non-anonymized features, we list the 10 most confident interactions with their estimated or accurate frequency and confidence in Table 1, where we only list out the name of features, and omit the specific value for each feature to keep notation uncluttered. We can conclude that “banner_pos” plays an important role in advertising. This observation coincides with the intuition that an advertisement is more likely to be clicked if it’s exhibited in a good position. Many interactions have a feature associated with “app” and a feature about “device”, which indicates the relationship between an item and a user. Also the estimations of frequency and confidence are pretty good, the RMSE of the estimations are $1.2\times 10^{-3}$, $1.9\times 10^{-3}$ and $1.1\times 10^{-3}$ for Frequency(-), Frequency(-) and Confidence, respectively. What’s more, the corresponding Pearson correlation coefficient are 0.9987, 0.9977 and 0.9879, which means the numerical order of frequency or confidence is well preserved. Thus the patterns found by Random Intersection Chains is likely to be the most frequent and confident ones.

Finally, the interactions are used as binary features, based on which several popular CTR prediction models are trained. We adopt 5 models, namely Wide&Deep (Cheng et al., 2016), DeepFM (Guo et al., 2017), xDeepFM (Lian et al., 2018), Deep&Cross (Wang et al., 2017) and AutoInt (Song et al., 2019), to test whether adding the interactions to the input is helpful. The results are shown in Table 2, where the performance of GLIDER, an interaction detection methods proposed by Tsang et al. (2020), is also presented as a comparison. We can see that in most cases, adding the interactions found by Random Intersection Chains leads to a significant improvement. In fact, an improvement as small as 0.001 is desirable for the Criteo data set (Cheng et al., 2016; Guo et al., 2017; Wang et al., 2017; Song et al., 2019; Tsang et al., 2020), and Random Intersection Chains lives up to this expectation. Perhaps due to the better learning rate we used, our baseline is better than GLIDER. Despite the difference between baselines, Random Intersection Chains makes a comparable improvement to GLIDER. But according to Tsang et al. (2020), it will take several hours and more than 150 GB memory to perform GLIDER, while the requirement of Random Intersection Chains is much lower.

Tic-Tac-Toe endgame data set (Matheus and Rendell, 1989; Aha et al., 1991) encodes the complete set of possible board configurations at the end of tic-tac-toe games. There are 958 instances and 9 categorical features in the data set. The possible values for each feature are “x”, “o” and “b”, which stand for “black”, “white” and “blank”, respectively. There are 8 possible ways to win for both players (3 horizontal lines, 3 vertical lines and 2 diagonal lines). Our target is to learn these rules that determine which player wins the game.

This is an ideal data set to test the effectiveness of Random Intersection Chains, since all the features are categorical and the label is intrinsically determined by some rules. As the result of an ending game is completely determined by some rules, we can make an accurate prediction if we find all the interesting rules. So we make an effort to extract the total 16 valid rules, with different $d_{\rm freq}$.

We set $K$=4 and $d_{\rm conf}$=10, so only the 10 most confident patterns for each player are kept. The range of $d_{\rm freq}$ we adopted is [20, 1000], and the number of found interesting rules is given in Figure 2. At the beginning, there are more interesting patterns can be found as $d_{\rm freq}$ grows. Actually for $d_{\rm freq}$ larger than 400, all the interesting patterns corresponding to x’s victory are found, while there is one missing pattern for “o”. We check the list of the found patterns, and found that the missing pattern is “a3=o, b3=o, c3=o”. Its support is 32/958=0.0334, indeed a very small value. When $d_{\rm freq}$ is too large, not only the missing pattern doesn’t occur, but also some already found patterns disappear. This is because some uncommon patterns have high confidence coincidentally. For example, “a1=x, b1=o, b3=b” occurs 30 times in the database, and all the instances containing this pattern happen to be in positive class. Since the number of the remained patterns are limited, these occasional patterns squeeze out the interesting ones.

The results indicate that the size of priority queue influences the extracted patterns in two ways. On the one hand, small $d_{\rm freq}$ may lead to a neglect of some meaningful patterns. On the other hand, if it’s too large, some occasionally confident patterns will be chosen, which can be treated as the “overfitting” phenomenon of Random Intersection Chains.

The Reuters RCV1 text data contains the tf-idf (term frequency-inverse document frequency) weighted presence of 47,148 word-stems in each document (Lewis et al., 2004).

Lewis et al. (2004) used a data set consisting of 23,149 documents as the training set. Like the processing approach adopted by Shah and Meinshausen (2014), we only consider word-stems appearing in at least 100 documents and the topics that contain at least 200 documents. This leaves 2484 word-stems as predictor variables and 52 topics as prediction targets. Also, tf-idf is transformed to a binary version, using 1 or 0 to represent whether it is positive. In this work, we split the original training data into a smaller training set and a test set. The first 13,149 instances are used for training and the rest for testing.

For each topic $c$, the target is to predict whether a document belongs to this topic. Setting $d_{\rm freq}$=400, $d_{\rm conf}$=200 and $K$=4, $M$=300, we apply Random Intersection Chains on the training set. Then we evaluate the interactions in two different ways. The first method, labeled by “Best-Rule”, is classifying the instances by the best rule directly. The “best” rule is defined as the most confident one among the rules with supports larger than $p^{(c)}$/10, which is the same as what is used by Shah and Meinshausen (2014). The other method is treating the rules as selected features for a linear model, which is called “Rules+LR”. We also fit a linear model on the total 2484 features as a comparison, labeled as “LR”. The precision and recall for the models are given in Figure 3, where the best rules found by Random Intersection Chains are shown in the right side of the figure.

We can see that “Best-Rule” sometimes gives good precision or recall, but its performance is usually the worst among the three models. This is not surprising because the information in a single rule is limited, and it’s unreasonable to ask a rule to be both general and reliable on a complicated data set. “Rules+LR” yields similar precision but generally smaller recall when compared with “LR”. At a first glance, it seems Random Intersection Chains brings few benefits. But noticing that the input dimension of the linear model in “Rules+LR” is 200, while the number is 2484 in “LR”. It rapidly reduces the data size and the computational burden, while the precision and recall only fall slightly. Also, the interpretability is enhanced since few features are used.

We also apply Random Intersection Chains on the two data sets used by Shah (2016). The first is Communities and Crime Unnormalized Data Set, “CCU” for short, which contains crime statistics for the year 1995 obtained from FBI data, and national census data from 1990. We take violent crimes per capita as our response, which makes it a regression task. We process the data in the same way as Shah (2016). This leads to a data set consisting of 1903 observations and 101 features.

The second data set is “ISOLET”, which consists of 617 features based on the speech waveforms generated from utterances of each letter of the English alphabet. We consider classification on the notoriously challenging E-set consisting of the letters “B”, “C”, “D”, “E”, “G”, “P”, “T”, “V” and “Z”. And finally we have 2700 observations spread equally among 9 classes.

We use the $l_{1}$-penalised linear regression as the base regression procedure, and penalised multinomial regression for the classification example. The regularization coefficient is determined by 5-fold cross-validation. To evaluate the procedures, we randomly select 2/3 of the instances for training and the rest for testing. This procedure is repeated 200 times for each of the data sets. Mean square error is used as the criterion for the regression model and misclassification rate is used for the classification task. All the settings are exactly the same as those used by Shah (2016), except we use $l_{2}$-regularizer to penalise the multinomial regression instead of group Lasso. This is because we don’t know how Shah (2016) grouped the features.

Since the inputs for these two data sets are numerical and CCU data set corresponds to a regression task, Random Intersection Chains can not be applied directly. To handle this difficulty, the continuous features and response should be transformed to a discrete version. The response of CCU data set is split into 5 categories by quantiles, and all the continuous features are then split to 5 intervals according to information gain. Setting $d_{\rm freq}$=2500, $d_{\rm conf}$=1225 and $K=5$, $M=300$, we add the product $X_{i_{1}}X_{i_{2}}\cdots X_{i_{k}}$ as an interactive feature to the input if there is a rule in the form of ($X_{i_{1}}$=$x_{i_{1}}$, $X_{i_{2}}$=$x_{i_{2}}$, …, $X_{i_{k}}$=$x_{i_{k}}$) for some $x_{i_{1}}$, $x_{i_{2}}$, …, $x_{i_{k}}$ in the resulting rule sets. The results of models with and without adding the rules found by Random Intersection Chains are shown in Table 3, labeled by “RIC” and “Main”. We also list out the results reported by Shah (2016), including base procedures (“Main*”), iterated Lasso fits (“Iterated”), Lasso following marginal screening for interactions (“Screening”), Backtracking, Random Forests (Breiman, 2001), hierNet (Bien et al., 2013) and MARS (Friedman, 1991). For CCU data set, our base model outperforms the one used by Shah (2016), which may caused by a better penalty parameter. Random Intersection Chains leads to comparable or better result when compared to existing algorithms. As for ISOLET data set, the result of our base model is not as good as the one used by Shah (2016). This is not surprising since we simply use $l_{2}$-regularizer while Shah (2016) adopted group Lasso to penalise the model. But we can see that Random Intersection Chains can run on this data set and leads to a good improvement, while some existing methods such as Screening, hierNet, MARS are inapplicable. We think this could be an evidence of our method’s efficiency.