Identifying consistent statements about numerical data with dispersion-corrected subgroup discovery

Let P denote our given global population of entities, for each of which we know the value of a real target variable \(y\!:P \rightarrow {\mathbb {R}}\) and additional descriptive information that is captured in some abstract description language \({\mathcal {L}}\) of subgroup selectors \(\sigma \! : P \rightarrow \{{\text {true}},{\text {false}}\}\). Each of these selectors describes a subpopulation \(\mathbf{ext }(\sigma ) \subseteq P\) defined bythat is referred to as the extension of \(\sigma \). Subgroup discovery is concerned with finding selectors \(\sigma \in {\mathcal {L}}\) that have a useful (or interesting) distribution of target values in their extension \(y_\sigma =\{y(p) : p \in \mathbf{ext }(\sigma )\}\). This notion of usefulness is given by an objective function \(f\! : {\mathcal {L}} \rightarrow {\mathbb {R}}\). That is, the formal goal is to find selectors \(\sigma \in {\mathcal {L}}\) with maximal \(f(\sigma )\). Since we assume f to be a function of the multiset of y-values, let us define \(f(\sigma )=f(\mathbf{ext }(\sigma ))=f(y_\sigma )\) to be used interchangeably for convenience. One example of a commonly used objective function is the impact measure \({\mathtt {ipa}}\) (see Webb 2001; here a scaled but order-equivalent version is given) defined bywhere \({\texttt {cov}}(Q)=|Q|/|P|\) denotes the coverage or relative size of Q (here—and wherever else convenient—we identify a subpopulation \(Q \subseteq P\) with the multiset of its target values).

The standard description language in the subgroup discovery literature¹ is the language \({\mathcal {L}}_{\text {cnj}}\) consisting of logical conjunctions of a number of base propositions (or predicates). That is, \(\sigma \in {\mathcal {L}}_{\text {cnj}}\) are of the formwhere the \(\pi _{i_j}\) are taken from a pool of base propositions \(\varPi =\{\pi _1,\ldots ,\pi _k\}\). These propositions usually correspond to equality or inequality constraints with respect to one variable x out of a set of description variables \(\{x_1,\ldots ,x_n\}\) that are observed for all population members (e.g., \(\pi (p)\equiv x(p) \ge v\)). However, for the scope of this paper it is sufficient to simply regard them as abstract Boolean functions \(\pi \! : P \rightarrow \{{\text {true}},{\text {false}}\}\). In this paper, we focus in particular on the refined language of closed conjunctions \({\mathcal {C}}_{\text {cnj}}\subseteq {\mathcal {L}}_{\text {cnj}}\) (Pasquier et al. 1999), which is defined as \({\mathcal {C}}_{\text {cnj}}=\{\sigma \in {\mathcal {L}}_{\text {cnj}}: {\mathbf {c}}(\sigma )=\sigma \}\) by the fixpoints of the closure operation \({\mathbf {c}}\! : {\mathcal {L}}_{\text {cnj}} \rightarrow {\mathcal {L}}_{\text {cnj}}\) given byThese are selectors to which no further proposition can be added without reducing their extension, and it can be shown that \({\mathcal {C}}_{\text {cnj}}\) contains at most one selector for each possible extension. While this can reduce the search space for finding optimal subgroups by several orders of magnitude, closed conjunctions are the longest (and most redundant) description for their extension and thus do not constitute intuitive descriptions by themselves. Hence, for reporting concrete selectors (as in Fig. 1), closed conjunctions have to be simplified to selectors of approximately minimum length that describe the same extension (Boley and Grosskreutz 2009).

The standard algorithmic approach for finding optimal subgroups with respect to a given objective function is branch-and-bound search—a versatile algorithmic puzzle solving framework with several forms and flavors (see, e.g., Mehlhorn and Sanders 2008, Chap. 12.4). At its core, all of its variants assume the availability and efficient computability of two ingredients:Based on these ingredients, a branch-and-bound algorithm simply enumerates all elements of \({\mathcal {L}}\) starting from \(\bot \) using \({\mathbf {r}}\) (branch), but—based on \(\hat{f}\)—avoids expanding descriptions that cannot yield an improvement over the best subgroups found so far (bound). Depending on the order in which language elements are expanded, one distinguishes between depth-first, breadth-first, breadth-first iterative deepening, and best-first search. In the last variant, the optimistic estimator is not only used for pruning the search space, but also to select the next element to be expanded, which is particularly appealing for informed, i.e., tight optimistic estimators. An important feature of branch-and-bound is that it effortlessly allows to speed-up the search in a sound way by relaxing the result requirement from being f-optimal to just being an a -approximation. That is, the found solution \(\sigma \) satisfies for all \(\sigma ' \in {\mathcal {L}}\) that \(f(\sigma )/f(\sigma ') \ge a\) for some approximation factor \(a \in (0,1]\). The pseudo-code given in Algorithm 1 summarizes all of the above ideas. Note that, for the sake of clarity, we omitted here some other common parameters such as a depth-limit and multiple solutions (top-k), which are straightforward to incorporate (see Lemmerich et al. 2016).

An efficiently computable refinement operator has to be constructed specifically for the desired description language. For example for the language of conjunctions \({\mathcal {L}}_{\text {cnj}}\), one can define \({\mathbf {r}}_{\text {cnj}}\! : {\mathcal {L}}_{\text {cnj}} \rightarrow {{\mathcal {L}}_{\text {cnj}}}\) bywhere we identify a conjunction with the set of base propositions it contains. For the closed conjunctions \({\mathbf {c}}_{\text {cnj}}\), let us define the lexicographical prefix of a conjunction \(\sigma \in {\mathcal {L}}_{\text {cnj}}\) and a base proposition index \(i \in [k]\) as \(\sigma \!\!\mid _{i}=\sigma \cap \{\pi _1, \dots , \pi _i\}\). Moreover, let us denote with \(\mathbf{i }(\sigma )\) the minimal index such that the i-prefix of \(\sigma \) is extension-preserving, i.e., \( \mathbf{i }(\sigma )=\min \{i \! : \,\mathbf{ext }(\sigma \!\!\mid _{i})=\mathbf{ext }(\sigma )\}\). With this we can construct a refinement operator (Uno et al. 2004) \({\mathbf {r}}_{\text {ccj}}\! : {\mathcal {C}}_{\text {cnj}} \rightarrow 2^{{\mathcal {C}}_{\text {cnj}}}\) asThat is, a selector \(\varphi \) is among the refinements of \(\sigma \) if \(\varphi \) can be generated by an application of the closure operator given in Eq. (5) that is prefix-preserving.

How to obtain an optimistic estimator for an objective function of interest depends on the definition of that objective. For instance, the coverage function \({\texttt {cov}}\) is a valid optimistic estimator for the impact function \({\mathtt {ipa}}\) as defined in Eq. (4), because the second factor of the impact function is upper bounded by 1. In fact there are many different optimistic estimators for a given objective function. Clearly, the smaller the value of the bounding function for a candidate subpopulation, the higher is the potential for pruning the corresponding branch from the enumeration tree. Ideally, one would like to use \(\hat{f}(\sigma )=\max \{f(\varphi ) \! : \,\mathbf{ext }(\varphi ) \subseteq \mathbf{ext }(\sigma ) \}\), which is the most strict function that still is a valid optimistic estimator. Computing this function, however, is as hard as the whole subgroup optimization problem. Thus, as a next best option, one can disregard subset selectability and consider the (selection-unaware) tight optimistic estimator (Grosskreutz et al. 2008) given byThis leaves us with a new combinatorial optimization problem: given a subpopulation \(Q \subseteq P\), find a sub-selection of Q that maximizes f. In the following section we will discuss strategies for solving this optimization problem efficiently for different classes of objective functions—including dispersion-corrected objectives.

The most general previous approach for computing the tight optimistic estimator for subgroup discovery with a metric target variable is described by Lemmerich et al. (2016), where it is referred to as estimation by ordering. Here, we review this approach and give a uniform and generalized version of that paper’s results. For this, we define the general notion of a measure of central tendency as follows.

One can check that this definition applies to the standard measures of central tendency, i.e., the arithmetic and geometric mean as well as the median ² \({\texttt {med}}(Q)=y_{\lceil m/2 \rceil }\), and also to weighted variants of them (note, however, that it does not apply to the mode). With this we can define the class of objective functions for which the tight optimistic estimator can be computed efficiently by the standard approach as follows. We call \(f\! : 2^{P} \rightarrow {\mathbb {R}}\) a monotone level 1 objective function if it can be written aswhere \(c\) is some measure of central tendency and g is a function that is non-decreasing in both of its arguments. One can check that the impact measure \({\mathtt {ipa}}\) falls under this category of functions as do many of its variants.

The central observation for computing the tight optimistic estimator for monotone level 1 functions is that the optimum value must be attained on a sub-multiset that contains a consecutive segment of elements of Q from the top element w.r.t. y down to some cut-off element. Formally, let us define the top sequence of sub-multisets of Q as \( T_i=\{y_{m-i+1},\ldots , y_m\} \) for \(i \in [m]\) and note the following observation:

From this insight it is easy to derive an \({\mathcal {O}}(m)\) algorithm for computing the tight optimistic estimator under the additional assumption that we can compute g and the “incremental central tendency problem” \((i,Q,(c(T_1),\ldots ,c(T_{i-1})) \mapsto c(T_i)\) in constant time. Note that computing the incremental problem in constant time implies to only access a constant number of target values and of the previously computed central tendency values. This can for instance be done for \(c={\texttt {mean}}\) via the incremental formula \({\texttt {mean}}(T_i)=((i-1)\,{\texttt {mean}}(T_{i-1})+y_{m-i+1})/i\) or for \(c={\texttt {med}}\) through direct index access of either of the two values \(y_{m-\lfloor (i-1)/2 \rfloor }\) or \(y_{m-\lceil (i-1)/2 \rceil }\). Since, according to Proposition 1, we have to evaluate f only for the m candidates \(T_i\) to find \(\hat{f}(Q)\) we can do so in time \({\mathcal {O}}(m)\) by solving the problem incrementally for \(i=1,\ldots ,m\). The same overall approach can be readily generalized for objective functions that are monotonically decreasing in the central tendency or those that can be written as the maximum of one monotonically increasing and one monotonically decreasing level 1 function. However, it breaks down for objective functions that depend on more than just size and central tendency—which inherently is the case when we want to incorporate dispersion-control.

We will now extend the previous recipe for computing the tight optimistic estimator to objective functions that depend not only on subpopulation size and central tendency but also on the target value dispersion in the subgroup. Specifically, we focus on the median as measure of central tendency and consider functions that are both monotonically increasing in the described subpopulation size and monotonically decreasing in some dispersion measure around the median. To precisely describe this class of functions, we first have to formalize the notion of dispersion measure around the median. For our purpose the following definition suffices. Let us denote by \(Y_{\varDelta }^{{\texttt {med}}}\) the multiset of absolute differences to the median of a multiset \(Y \in {\mathbb {N}}^{\mathbb {R}}\), i.e., \(Y_{\varDelta }^{{\texttt {med}}}=\{|y_1-{\texttt {med}}(Y)|,\ldots ,|y_m-{\texttt {med}}(Y)|\}\).

One can check that this definition contains the measures median absolute deviation around the median \({\texttt {mmd}}(Y)={\texttt {med}}(Y_{\varDelta }^{{\texttt {med}}})\), the root mean of squared deviations around the median \({\texttt {rsm}}(Y)={\texttt {mean}}(\{x^2 \! : \,x \in Y_{\varDelta }^{{\texttt {med}}}\})^{1/2}\), as well as the mean absolute deviation around the median \({\texttt {amd}}(Y)={\texttt {mean}}(Y_{\varDelta }^{{\texttt {med}}})\).³ Based on Def. 2 we can specify the class of objective functions that we aim to tackle as follows: we call a function \(f\! : 2^{P} \rightarrow {\mathbb {R}}\) a dispersion-corrected or level 2 objective function (based on the median) if it can be written aswhere \(d\) is some dispersion measure around the median and \(g\! : {\mathbb {R}}^3 \rightarrow {\mathbb {R}}\) is a real function that is non-decreasing in its first argument and non-increasing in its third argument (without any monotonicity requirement for the second argument).

Our recipe for optimizing these functions is then to consider only subpopulations \(R \subseteq Q\) that can be formed by selecting all individuals with a target value in some interval. Formally, for a fixed index \(z \in \{1,\ldots ,m\}\) define \(m_z \le m\) as the maximal cardinality of a sub-multiset of the target values that has median index z, i.e.,Now, for \(k \in [m_z]\), let us define \(Q^k_{z}\) as the set with k consecutive elements around index z. That isWith this we can define the elements of the median sequence \(Q_z\) as those subsets of the form of Eq. (8) that maximize f for some fixed index \(z \in [m]\). That is, \(Q_z=Q^{k^*_z}_z\) where \(k^*_z \in [m_z]\) is minimal withThus, the number \(k^*_z\) is the smallest cardinality that maximizes the trade-off of size and dispersion encoded by g (given the fixed median \(y_z={\texttt {med}}(Q^k_z)\) for all k).

Figure 2 shows an exemplary median sequence based on 21 random target values. Note how the set sizes \(k^*_z\) vary non-monotonically for increasing median indices z (e.g., \(k^*_{10}=13\), \(k^*_{11}=10\), and \(k^*_{12}=11\)). The precise behavior of the \(k^*_z\)-sequence is determined by the cluster structure of the target values and the specific level-2 objective function. Below we will see that for some functions there is an additional regularity in the \(k^*_z\)-sequence that allows further algorithmic exploitation. For now, let us first note that, as desired, searching the median sequence is sufficient for finding optimal subsets of Q independent of the precise objective:

Consequently, we can compute the tight optimistic estimator for any dispersion-corrected objective function based on the median in time \({\mathcal {O}}(m^2)\) for subpopulations of size m—again, given a suitable incremental formula for \(d\). While this is not generally a practical algorithm in itself, it is a useful departure point for designing one. In the next section we show how it can be brought down to linear time when we introduce some additional constraints on the objective function.

Equipped with the general concept of the median sequence, we can now address the special case of dispersion-corrected objective functions where the trade-off between the subpopulation size and target value dispersion is captured by a linear function of size and the sum of absolute differences from the median. Concretely, let us define the dispersion-corrected coverage (w.r.t. absolute median deviation) bywhere \({\texttt {smd}}(Q)=\sum _{y \in Q}|y-{\texttt {med}}(Q)|\) denotes the sum of absolute deviations from the median. We then consider objective functions based on the dispersion-corrected coverage of the formwhere g is non-decreasing in its first argument. Let us note, however, that we could replace the \({\texttt {dcc}}\) function by any linear function that depends positively on \(|Q|\) and negatively on \({\texttt {smd}}\). It is easy to verify that function of this form also obey the more general definition of level-2 objective functions given in Sec. 3.2, and, hence can be optimized via the median sequence.

The key to computing the tight optimistic estimator \(\hat{f}\) in linear time for functions based on dispersion-corrected coverage is then that the members of the median sequence \(Q_z\) can be computed incrementally in constant time. Indeed, we can prove the following theorem, which states that the optimal size for a multiset around median index z is within 3 of the optimal size for a multiset around median index \(z+1\)—a fact that can also be observed in the example given in Fig. 2.

One idea to prove this theorem is to show that (a) the gain in f for increasing the multiset around a median index z is alternating between two discrete concave functions and (b) that the gains for growing multisets between two consecutive median indices are bounding each other. For an intuitive understanding of this argument, Fig. 3 shows for four different median indices \(z \in \{10,11,12,13\}\) the dispersion-corrected coverage for the sets \(Q^k_z\) as a function in k. On closer inspection, we can observe that when considering only every second segment of each function graph, the corresponding \({\texttt {dcc}}\)-values have a concave shape. A detailed proof, which is rather long and partially technical, can be found in “Appendix A”.

It follows that, after computing the objective value of \(Q_m\) trivially as \(f(Q_m)=g(1/|P|,y_m)\), we can obtain \(f(Q_{z-1})\) for \(z=m,\ldots ,2\) by checking the at most seven candidate set sizes given by Eq. (10) aswith \(k_z^-=\max (k_z^*-3,1)\) and \(k_z^+=\min (k_z^*+3,m_z)\). For this strategy to result in an overall linear time algorithm, it remains to see that we can compute individual evaluations of f in constant time (after some initial \({\mathcal {O}}(m)\) pre-processing step).

As a general data structure for quickly computing sums of absolute deviations from a center point, we can define for \(i \in [m]\) the cumulative left error \(e_l(i)\) and the cumulative right error \(e_r(i)\) asNote that we can compute these error terms for all \(i \in [m]\) by iterating over the ordered target values in time \({\mathcal {O}}(m)\) via the recursions and \(e_l(1)=e_r(m)=0\). Subsequently, we can compute sums of deviations from center points of arbitrary subpopulations in constant time, as the following statement shows (see “Appendix B” for a proof).

With this we can compute \(k \mapsto f(Q_z^k)\) in constant time (assuming g can be computed in constant time). Together with Proposition 2 and Theorem 3 this results in a linear time algorithm for computing \(Q \mapsto \hat{f}(Q)\) (see Algorithm 2 for a pseudo-code that summarizes all ideas).

To investigate the selection bias of \(f_1\) let us also consider the non-dispersion corrected variant \(f_0(Q)={\texttt {cov}}(Q) {\texttt {mds}}_+(Q)\), where we simply replace the dispersion-corrected coverage by the ordinary coverage. This function is a monotone level 1 function, hence, its tight optimistic estimator \(\hat{f_0}\) can be computed in linear time using the top sequence approach. Figure 4 shows the characteristics of the optimal subgroups that are discovered with respect to both of these objective functions (see also Table. 1 for exact values) where for all datasets the language of closed conjunctions \({\mathcal {C}}_{\text {cnj}}\) has been used as description language.

The first observation is that—as enforced by design—for all datasets the mean absolute deviation from the median is lower for the dispersion-corrected variant (except in one case where both functions yield the same subgroup). On average the dispersion for \(f_1\) is 49 percent of the global dispersion, whereas it is 113 percent for \(f_0\), i.e., when not optimizing the dispersion it is on average higher in the subgroups than in the global population. When it comes to the other subgroup characteristics, coverage and median target value, the global picture is that \(f_1\) discovers somewhat more specific groups (mean coverage 0.3 versus 0.44 for \(f_0\)) with higher median shift (on average 0.73 normalized median deviations higher). However, in contrast to dispersion, the behavior for median shift and coverage varies across the datasets. In Fig. 4, the datasets are ordered according to the difference in subgroup medians between the optimal subgroups w.r.t. \(f_0\) and those w.r.t. \(f_1\). This ordering reveals the following categorization of outcomes: When our description language is not able to reduce the error of subgroups with very high median value, \(f_1\) settles for more coherent groups with a less extreme but still outstanding central tendency. On the other end of the scale, when no coherent groups with moderate size and median shift can be identified, the dispersion-corrected objective selects very small groups with the most extreme target values. The majority of datasets obey the global trend of dispersion-correction leading to somewhat more specific subgroups with higher median that are, as intended, more coherent.

To determine based on these empirical observations whether we should generally favor dispersion correction, we have to specify an application context that specifies the relative importance of coverage, central tendency, and dispersion. For that let us consider the common statistical setting in which we do not observe the full global population P but instead subgroup discovery is performed only on an i.i.d. sample \(P' \subseteq P\) yielding subpopulations \(Q'=\sigma (P')\). While \(\sigma \) has been optimized w.r.t. the statistics on that sample \(Q'\) we are actually interested in the properties of the full subpopulation \(Q = \sigma (P)\). For instance, a natural question is what is the minimal y-value that we expect to see in a random individual \(q \in Q\) with high confidence. That is, we prefer subgroups with an as high as possible threshold \(l\) such that a random \(q \in Q\) satisfies with probability⁵ \(1-\delta \) that \(y(q) \ge l\). This criterion gives rise to a natural trade-off between the three evaluation metrics through the empirical Chebycheff inequality (see Kabán 2012, Eq. (17)), according to which we can compute such a value as \({\texttt {mean}}(Q')-\epsilon (Q')\) whereand \({\texttt {var}}(Y)=\sum _{y \in Y} (y-{\texttt {mean}}(Y))^2 / (|Y|-1)\) is the sample variance. Note that this expression is only defined for sample subpopulations with a size of at least \(1/\delta \). For smaller subgroups our best guess for a threshold value would be the one derived from the global sample \({\texttt {mean}}(P')-\epsilon (P')\) (which we assume to be large enough to determine an \(\epsilon \)-value). This gives rise to the following standardized lower confidence bound score \(\tilde{l}\) that evaluates how much a subgroup improves over the global \(l\) value:The plot on the left side of Fig. 5 shows the score values of the optimal subgroup w.r.t. to \(f_1\) (\(\tilde{l}_1\)) and \(f_0\) (\(\tilde{l}_0\)) using confidence parameter \(\delta =0.05\). Except for three exceptions (datasets 3,4, and 12), the subgroup resulting from \(f_1\) provides a higher lower bound than those from the non-dispersion corrected variant \(f_0\). That is, the data shows a strong advantage for dispersion correction when we are interested in selectors that mostly select individuals with a high target value from the underlying population P. In order to test the significance of these results, we can employ the Bayesian sign-test (Benavoli et al. 2014), a modern alternative to classic frequentist null hypothesis tests that avoids many of the well-known disadvantages of those (see Demšar 2008; Benavoli et al. 2016). With Bayesian hypothesis tests, we can directly evaluate the posterior probabilities of hypotheses given our experimental data instead of just rejecting a null hypothesis based on some arbitrary significance level. Moreover, we differentiate between sample size and effect size by the introduction of a region of practical equivalence (rope). Here, we are interested in the relative difference \(\tilde{z}=(\tilde{l}_1 - \tilde{l}_0)/(\max \{\tilde{l}_0, \tilde{l}_1\})\) on average for random subgroup discovery problems. Using a conservative choice for the rope, we call the two objective functions practically equivalent if the mean \(\tilde{z}\)-value is at most \(r=0.1\). Choosing the prior belief that \(f_0\) is superior, i.e., \(\tilde{z} < -r\), with a prior weight of 1, the procedure yields based on our 25 test datasets the posterior probability of approximately 1 that \(\tilde{z} > r\) on average (see the right part of Fig. 5 for in illustration of the posterior belief). Hence, we can conclude that dispersion-correction improves the relative lower confidence bound of target values on average by more than 10 percent when compared to the non-dispersion-corrected function.

To study the effect of the tight optimistic estimator, let us compare its performance to that of a baseline estimator that can be computed with the standard top sequence approach. Since \(f_1\) is upper bounded by \(f_0\), \(\hat{f_0}\) is a valid, albeit non-tight, optimistic estimator for \(f_1\) and can thus be used for this purpose. The exact speed-up factor is determined by the ratio of enumerated nodes for both variants as well as the ratio of computation times for an individual optimistic estimator computation. While both factors determine the practically relevant outcome, the number of nodes evaluated is a much more stable quantity, which indicates the full underlying speed-up potential independent of implementation details. Similarly, “number of nodes evaluated” is also an insightful unit of time for measuring optimization progress. Therefore, in addition to the computation time in seconds \(t_0\) and \(t_1\), let us denote by \({\mathcal {E}}_0, {\mathcal {E}}_1\subseteq {\mathcal {L}}\) the set of nodes enumerated by branch-and-bound using \(\hat{f_0}\) and \(\hat{f_1}\), respectively—but in both cases for optimizing the dispersion-corrected objective \(f_1\). Moreover, when running branch-and-bound with optimistic estimator \(\hat{f_i}\), let us denote by \(\sigma ^*_i(n)\) and \(\sigma ^+_i(n)\) the best selector found and the top element of the priority queue (w.r.t. \(\hat{f_i}\)), respectively, after n nodes have been enumerated.

Figure 6 (left) shows the speed-up factor \(t_1/t_0\) on a logarithmic axis for all datasets in increasing order along with the potential speed-up factors \(|{\mathcal {E}}_0|/|{\mathcal {E}}_1|\) (see Table 1 for numerical values). There are seven datasets for which the speed-up is minor followed by four datasets with a modest speed-up factor of 2. For the remaining 14 datasets, however, we have substantial speed-up factors between 4 and 20 and in four cases immense values between 100 and 4000. This demonstrates the decisive potential effect of tight value estimation even when compared to another non-trivial estimator like \(\hat{f_0}\) (which itself improves over simpler options by orders of magnitude; see Lemmerich et al. 2016). Similar to the results in Sect. 4.1, the Bayesian sign-test for the normalized difference \(z=(t_1-t_0)/\max \{t_1,t_0\}\) with the prior set to practical equivalence (\(z \in [-0.1,0.1]\)) reveals that the posterior probability of \(\hat{f}_1\) being superior to \(\hat{f}_0\) is apx. 1. In almost all cases the potential speed-up given by the ratio of enumerated nodes is considerably higher than the actual speed-up, which shows that, despite the same asymptotic time complexity, an individual computation of the tight optimistic estimator is slower than the simpler top sequence based estimator—but also indicates that there is room for improvements in the implementation.

Examining the optimization progress over time for the binaries dataset, which exhibits the most extreme speed-up (right plot in Fig. 6), we can see that not only does the tight optimistic estimator close the gap between best current selector and current highest potential selector much faster—thus creating the huge speed-up factor—but also that it causes better solutions to be found earlier. This is an important property when we want to use the algorithm as an anytime algorithm, i.e., when allowing the user to terminate computation preemptively, which is important in interactive data analysis systems. This is an advantage enabled specifically by using the tight optimistic estimator in conjunction with the best-first node expansion strategy.