Using A* for Inference in Probabilistic Classifier Chains

1 Introduction

Multi-label classification (MLC) is a machine learning problem in which models are sought that assign a subset of (class) labels to each instance. Multi-label classification problems are ubiquitous and naturally occur in many applications, for instance, in assigning tags to content.

Maybe the most interesting problem in multi-label learning is that the labels shows statistical dependencies between them. These relationships constitute a key source of information, thus, it is hardly surprising that research on MLC has very much focused on this topic. In this regard, two kinds of label dependence have been formally distinguished, namely, conditional dependence and marginal (unconditional) dependence [Dembczy´nski et al., 2012a]. Several methods are able to detect interdependencies among labels, see [Godbole and Sarawagi, 2004; Tsoumakas and Vlahavas, 2007; Read et al., 2008; Cheng and H¨ullermeier, 2009; Monta˜n´es et al., 2011; Read et al., 2011; Monta˜n´es et al., 2014].

∗Research supported by MINECO, grant TIN2011-23558.

Copyright c© 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Regarding conditional label dependence, Probabilistic Classifier Chains (PCC) has aroused great interest since it estimates the conditional joint distribution of the labels. However, the original PCC algorithm [Dembczy´nski et al., 2010] suffers from high computational cost because it uses exhaustive search as the inference strategy to select optimal predictions given a loss function. Then, several efforts of overcoming this drawback have being proposed. Monte Carlo sampling [Dembczynski et al., 2012b; Read et al., 2014] is a simple alternative to control the computational cost of the inference process. ϵ-Approximate [Dembczynski et al., 2012b] is a more sophisticated algorithm based on uniform-cost search. This method can output optimal predictions in terms of subset 0/1 loss reducing significantly the computational cost. Finally, a more recently approach based on beam search [Kumar et al., 2012; 2013] also presents good behavior both in terms of performance and computational cost.

An alternative to these (uninformed) approaches is to apply other search algorithms. Among them, heuristic search is at least worthy of consideration. However, to the best of our knowledge this possibility has never been studied before. The main contribution of this paper is to fill this gap in the literature, proposing a new approach for inference in linear PCC models based on the combination of A* algorithm [Hart et al., 1968] and an admisible heuristic. Our proposal guarantees, not only optimal predictions in terms of subset 0/1 loss, but also that it explores less nodes than all previous methods that also provide optimal predictions.

The paper is organized as follows. Section 2 formally describes MLC and PCC. Recent approaches for inference in PCC are discussed in Section 3. Section 4 details the new method based on A*. Finally, our experiments are discussed in Section 5 and some conclusions are exposed in Section 6.

2 Multi-label classification and PCC

Let be L = {ℓ1, ℓ2, . . . , ℓm} a finite and non-empty set of m labels and S = {(x1, y1), . . . , (xn, yn)} a training set independently and randomly drawn according to an unknown probability distribution P(X, Y) on X × Y, where X and Y are the input and the output space, respectively. The former is the instance space, whereas the latter is given by the power set P(L) of L. To ease notation, we define yi as a binary vector yi = (yi,1, yi,2, . . . , yi,m) in which yi,j = 1 indicates the presence (relevance) and yi,j = 0 the absence (irrelevance) of ℓj in the labeling of xi. Hence, yi is the realization of a corresponding random vector Y = (Y1,Y2, . . . ,Ym). Using this convention, the output space can also be defined as Y = {0, 1}m. The goal in MLC is to induce from S a classifier f : X -→ Y that minimizes the risk in terms of certain loss function L(·). This risk can be defined as the expected loss over the joint distribution P(X,Y), that is,

thus, denoting by P(y | x) the conditional distribution Y = y given X = x , the risk minimizer f ∗ can be expressed by

Let us comment that the conditional distribution P(y | x) presents different properties which are crucial for optimizing different loss functions. Despite several loss functions have been taken for evaluating MLC, like Hamming loss or F1, here we will focus on just the subset 0/1 loss. This measure looks if predicted and relevant label subsets are equal or not:

In case of this evaluation measure, it suffices taking the mode of the entire joint conditional distribution for optimizing this loss. Formally, the risk minimizer adopts the simplified following form

Among MLC algorithms, let us focus on PCC methods. This group of algorithms is based on learning a CC model [Read et al., 2011] so the training phase consists on 1) taking an order of the label set and 2) training a probabilistic binary classifier for estimating P(yj | x, y1, . . . , yj-1) for each label ℓj following this order. The probabilistic model fj obtained for predicting label ℓj is of the form

The training data for classifier fj is the set Sj = {(x1, y1,j), . . . , (xn, yn,j)} where xi =(x, yi,1, . . . , yi,j-1), that is, the features are xi supplemented by the relevance of the labels ℓ1, . . . , ℓj-1 preceding ℓj in the chain and the category is the relevance of label ℓj.

The great advantage of PCC approaches is that they allow to perform inference for each instance, which consists of estimating the risk minimizer for a given loss function over the estimated entire joint conditional distribution. The idea revolves around repeatedly applying the product rule of probability to the joint distribution of the labels Y = (Y1,Y2, . . . ,Ym), that is, computing

Notice that from a theoretical point of view, this expression holds for any order considered for the labels.

1 The expression [[p]] evaluates to 1 if p is true and 0 otherwise.

3 Inference in Probabilistic Classifier Chains

Several methods have been previously proposed for inference in PCC. Before proceeding to cope with the particularities of some of them, let us recall that their training phases are equal, thus, the models fj will be the same. So, in what follows we will just describe their respective prediction phases.

In this sense, let now consider the task of performing different inference procedures as different manners of exploring a probability binary tree. In such tree, the root node is labeled by the empty set whereas a generic node k of level j < m with k ≤ 2j , is labeled by yk j = (v1, v2, . . . , vj) with vi ∈ {0, 1} for i = 1, . . . , j. This node has two children respectively labeled as y2k-1 j+1 = (v1, v2, . . . , vj, 0) and y2k j+1 =(v1, v2, . . . , vj, 1) and with marginal joint conditional probability P(y1 = v1, . . . , yj = vj, yj+1 = 0 | x) and P(y1 = v1, . . . , yj = vj, yj+1 = 1 | x). The weights of the edges between both father and children are respectively P(yj+1 = 0 | x, y1 = v1, . . . , yj = vj) and P(yj+1 = 1 | x, y1=v1, . . . , yj =vj), which are respectively estimated by 1 - fj+1(x, v1, . . . , vj) and fj+1(x, v1, . . . , vj). The marginal joint conditional probability of the children are computed by the product rule of probability: P(y1=v1, . . . , yj= vj , yj+1 = vj+1 | x) = P(yj+1 = vj+1 | x, y1 = v1, . . . , yj = vj) · P(y1=v1, . . . , yj=vj | x). See the examples in Figure 1.

3.1 Greedy Search and Exhaustive Search

The Greedy Search (GS) strategy defines the original CC method [Read et al., 2009; 2011]. CC provides an output ˆy=(ˆ y1, . . . , ˆ ym) for a new unlabeled instance x by successively querying each classifier fj that estimates the probability P(yj | x, y1, . . . , yj-1). Notice that when ˆ yj is estimated, fj uses the predictions of the previous labels, ˆ y1, . . . , ˆ yj-1. This means that, in terms of the probability binary tree defined above, GS only explores one path. In the example depicted in Figure 1, GS would select the rightmost leaf, so the optimal solution is not reached.

Concerning the optimization of subset 0/1 loss, a rigorous analysis [Dembczynski et al., 2012b] establishes bounds for the performance of GS, concluding that it offers quite poor performance for this loss function. However, the work concludes stating that GS tries to optimize subset 0/1 loss, since it is more suitable for estimating the mode of the joint rather of the marginal conditional distribution.

Unlike GS that explores only one path, Exhaustive Search (ES) explores all possible paths in the tree. Thus, ES estimates the entire joint conditional distribution P(· | x), providing Bayes optimal inference. For each combination of labels y = (y1, y2, . . . , ym) it computes P(y | x) and L(y, f(x)) for all f(x) and outputs the combination ˆy = (ˆ y1, . . . , ˆ ym) = f ∗ (x) with minimum risk for the given loss L(·, ·). By doing so, it generally improves in terms of performance, since it perfectly estimates the risk minimizer, albeit at the cost of a higher computational cost, as it comes down to summing over an exponential (2m) number of label combinations. ES is the inference process used by the original PCC method [Dembczy´nski et al., 2010].

Figure 1: An example of the paths followed by ϵ-A (ϵ = .0) and BS (b = 2). The dotted arrows show the path followed by the algorithm. In the case of BS, the nodes with a cross are not explored anymore because they have not any of the highest marginal joint conditional probabilities at their level

3.2 ϵ-Approximate algorithm

The ϵ-Approximate (ϵ-A) algorithm [Dembczynski et al., 2012b] arises as an alternative to the high computational cost of ES and to the poor performance of GS. In terms of the probability tree defined above, it expands only those nodes whose marginal joint conditional probability, P(y1, . . . , yj | x), exceeds the threshold ϵ = 2-k , with 1 ≤ k ≤ m. In fact, the nodes are expanded in the decreasing order established by this probability (see Figure 1(a)). Two situations can be found: i) the node expanded is a leaf or ii) there are not more nodes that exceed the threshold ϵ. If the former situation happens, the prediction for the unlabeled instance will be the label combination of such leaf. Conversely, if situation ii) takes place, then GS is applied to the those nodes whose children do not exceed the threshold, and the prediction will be that with the highest entire joint conditional probability P(y1, . . . , ym | x).

The parameter ϵ plays a key role. The particular case of ϵ=0 (or any value in the interval [0, 2-m], that is, k=m) has special interest, since the algorithm performs a uniform-cost search (UC) and always finds the optimal solution. This is so because the marginal joint conditional probabilities for at least one leaf is guaranteed to be higher than ϵ. Even more, this leaf is the optimal solution, since the marginal joint conditional probabilities decrease in the successive steps of the algorithm. Figure 1(a) illustrates this situation. The dotted arrows show the path followed by the algorithm and at the end the optimal label combination in terms of subset 0/1 loss is reached (1, 0, 1). Conversely, the method is looking to GS as ϵ grows, being GS in case of k=1, ϵ=2-1 =0.5.

Notice that this method provides an optimal prediction whenever its corresponding joint probability is greater or equal than ϵ. Amore general interpretation for a generic value of ϵ=2-k is that the algorithm guarantees to reach an optimal solution until the k-th level on the tree. Unfortunately, this optimal combination of labels until k-th level can be different from the ones of the optimal solution, since such solution also depends on what happens hereinafter. From level k+1, if the entire joint conditional probability of the optimal solution is greater than ϵ, then none of its nodes is discarded and hence this optimal solution is reached. Conversely, if the entire joint conditional probability of the optimal solution is lower than ϵ, then the algorithm never reaches a leaf, and hence, GS is applied starting at each discarded node. Therefore, the optimal solution is reached only if GS follows the optimal path, which is not guaranteed.

Consequently, this algorithm estimates the risk minimizer for the subset 0/1 loss a greater or lesser extent depending on the value of ϵ. Even more, a theoretical analysis of this estimation [Dembczynski et al., 2012b] allows to bound its goodness as a function of ϵ.

3.3 Beam search

Beam Search (BS) [Kumar et al., 2012; 2013] also explores more than one path of the probabilistic tree. This method includes a parameter b called beam width that limits the number of label combinations explored. The idea is to explore b nodes at each level. Hence, depending on such value certain number of the top levels are exhaustively explored, particularly a total of k∗-1 levels, being k∗ the lowest integer such that b<2k∗. Then, only b nodes are explored for each of the remainder levels. The nodes explored from the level k∗ to the bottom are those with the highest marginal joint conditional probability seen thus far. At the end, the algorithm outputs the label combination with highest joint conditional probability.

Figure 1(b) shows an example of the BS algorithm with b=2. Hence, all nodes of the first level are explored. For the rest of levels, just two nodes are explored, those with highest marginal joint conditional probability among the children whose parents have been previously explored. At this respect, notice that the node with the optimal solution is not explored since its parent was discarded. This example confirms that BS can not guarantee to reach optimal solutions.

In the case of b=1, BS expands just one node at each level, that with highest marginal joint conditional probability, so BS follows just one path and is equivalent to GS. Also, if b=2m, BS performs an ES. Hence, BS encapsules both GS and ES. This makes possible to control the trade-off between computational cost and performance of the method by tuning b.

As final remark, the fact that BS considers marginal joint conditional probabilities makes the method tend to estimate the risk minimizer for the subset 0/1 loss. In any case, it would be possible to consider other loss functions. At this respect, the authors of this proposal do not include any theoretical analysis about the goodness of the estimation of the risk minimizer. However, they empirically show that taking certain values of b (b < 15), the risk minimizer provided by the method converges to the one obtained using ES.

4 A* algorithm for inference in PCC

The algorithm A* is the most widely-known form of best-first search [Pearl, 1984] in which, at each iteration, the best node according to an evaluation function e is expanded. The particularity of A* algorithm is that e can be seen as a function E of other two functions g and h, e(k) = E(g(k), h(k)), where g(k) evaluates the cost of reaching node k from the root and h(k) evaluates the cost of reaching a solution (a leaf) from k. Hence, e(k) evaluates the total cost of reaching a solution from the root through k. In general, it is possible to obtain the exact value of the known information (g), but the unknown information must be estimated through an heuristic (h). To get an optimal solution, h must not overestimate the actual cost of reaching a solution, that is, it must be an admisible heuristic. This kind of heuristics are optimistic, because they estimate that the cost of getting a solution is less than it actually is. Also, A* algorithm is optimally efficient for any heuristic, because no other optimal algorithm using the same heuristic guarantees to expand fewer nodes than A*.

In order to adapt A* for inference in PCC, we must take into account that we have probabilities instead of costs. So, 1) A* must select the node with the highest estimated probability, 2) h must not underestimate the probability from the node to a leaf, and 3) E must be the product function, e=g·h. Considering all these aspects, e will provide an estimation of the entire joint conditional probability P(y1, . . . , ym | x) for optimizing subset 0/1 loss. In order to derive g and h, let see that the product rule of probability to the joint distribution of the labels Y=(Y1,Y2, . . . ,Ym) can be rewritten as

Hence, for a node at level j, let consider g to be the marginal joint conditional probability P(y1, . . . , yj | x) and h an heuristic that does not underestimate the marginal joint conditional probability P(yj+1, . . . , ym | x, y1, . . . , yj). Let remember that the values of y1, . . . , yj are known at level j.

Before discussing the heuristic h proposed here, let notice that g is the same marginal joint conditional probability that both ϵ-A algorithm and BS calculate to select the nodes to be expanded. Even more, ϵ-A with ϵ=0 is not only equivalent to UC, but also to A* with the constant heuristic h=1. This heuristic is admisible too, since none probability is greater than 1. But, on the other hand, it is also the worst admisible heuristic, since any other admisible heuristic will dominate it and consequently the A* algorithm using such heuristic will never expand more nodes than A* algorithm using h=1.

Let go now to discuss the heuristic proposed here for guaranteeing optimal predictions. Since our heuristic should not underestimate the marginal joint conditional probability P(yj+1, . . . , ym | x, y1, . . . , yj) in order to be admisible, it is quite straightforward to pick the maximum value of such probability for obtaining an optimal heuristic h∗ :

However, obtaining such maximum is, in fact, applying an ES over the set of labels L = {ℓj+1, . . . , ℓm}. Hence, this optimal heuristic is not computationally applicable. So, we need to obtain a tractable heuristic in exchange of renouncing to such optimality. This leads to design an heuristic ˆh also admisible, but less dominant than h∗ . For this purpose, let consider (yj+1, . . . , ym) the values that define h∗ , that is

and let notice that values (yj+1, . . . , ym) that maximize the product do not have to maximize each individual term, then

Hence, defining ˆh as

it is easy to deduce that ˆh is admisible and h∗ ≤ ˆh. But again, ˆh is not computationally applicable in general. However, this is not the case if we restrict ourselves to the case of using linear models. Remember that P(yi | x, y1, . . . , yi-1) is estimated through the model fi(x, y1, . . . , yi-1). Particularly, P(yi = 1 | x, y1, . . . , yi-1) = fi(x, y1, . . . , yi-1) and P(yi = 0 | x, y1, . . . , yi-1) = 1 - fi(x, y1, . . . , yi-1). Hence, if fi is a linear model, it adopts the following form

that splitting the second term in the known part (from ℓ1 to ℓj) and unknown part (from ℓj+1 to ℓi) it leads to

Since x is given and y1, . . . , yj are fixed, the last summation contains the variables for which the maximum must be obtained. Then, let denote by K+ = {k | j +1 ≤ k ≤ i-1, wy,k ≥ 0} the indexes of the positive coefficients and by K- = {k | j + 1 ≤ k ≤ i - 1, wy,k < 0} the indexes of the negatives. Hence fi(x, y1, . . . , yi-1) is maximum when

and similarly 1 - fi(x, y1, . . . , yi-1) is maximum if

Consequently, if yi,1 j+1 , . . . , yi,1 i-1 are the values that maximize fi(x, y1, . . . , yj, yj+1, . . . , yi-1) and if yi,0 j+1 , . . . , yi,0 i-1 are the values that maximize 1 - fi(x, y1, . . . , yj , yj+1, . . . , yi-1), then

Notice that yi,1 k = 1 - yi,0 k . Also, if yij+1 , . . . , yi i-1 equals either yi,1 j+1 , . . . , yi,1 i-1 or yi,0 j+1 , . . . , yi,0 i-1 respectively depending if 1 - fi(x, y1, . . . , yj, yi,0 j+1 , . . . , yi,0 i-1 ) is lower than fi(x, y1, . . . , yj, yi,1 j+1 , . . . , yi,1 i-1 ) or not, then the heuristic ˆh for a node at level j in the linear case will be

Remember that h∗ and ˆh only differ on the values of yj+1, . . . , yi-1. In the former, the same values are common for all the factors of the product, whereas in the latter these values depend on each term i of the product, and hence, they can be different, what makes ˆh not be an optimal heuristic. On the other hand, the cost of computing ˆh is of polynomial order, unlike h∗ which is of exponential order. Figure 2 exemplifies ˆh. Let focus on the node labeled by (1). The marginal joint conditional probability until this node is g = 0.6. For computing ˆh, first we evaluate the maximum marginal conditional probabilities P(y2 | x, y1 = 1) provided by h2(x, y1) and P(y3 | x, y1 = 1, y2) provided by h3(x, y1, y2) which respectively are 0.6 and 1.0. Then we carry out their product as applying the product rule of the probability to estimate the marginal joint conditional probability from that node to a leaf. Notice that the maximum at each level does not correspond to the same branch of the tree. In other words, the maximum in the first level correspond to y2 = 1, whereas the maximum in the second level is obtained by P(y3 | x, y1 = 1, y2 = 0) when y3 = 1 fixing y2 = 0. This is what makes the heuristic ˆh not to be the optimal one h∗ .

Figure 3 shows the path followed by A* using ˆh. It reaches the optimal leaf as theoretically is expected. Comparing this graph with the one in Figure 1(a) that illustrates ϵ-A with ϵ = .0, and taking into account the properties of the heuristics related to the dominance, ϵ-A, ϵ = .0 (equivalent to A* using h = 1 or UC search) explores more nodes than A* using ˆh.

As final remark, the A* algorithm using ˆh perfectly estimates the risk minimizer for the subset 0/1 loss, as both ϵ-A with ϵ = .0 and ES do it. Even more, A* with ˆh expands equal or less nodes, since ˆh is more dominant than the heuristic h = 1. Obviously, computing ˆh is more costly than computing h = 1 or applying just uniform-cost search. The question is then if this additional computing time compensates the theoretical guarantee it has of expanding less nodes.

5 Experimental results

The experiments reported here were performed over several benchmark datasets previously used in many MLC papers. The main characteristic for these experiments is the number of labels, which varies between 5 and 101. The methods compared were those discussed along the paper, except ES because it is computationally intractable. We do not include other approaches, like Monte Carlo sampling, due to the lack of space to properly discuss them in the paper. Hence, the methods compared were GS, uniform-cost search, ϵ-A for different values of ϵ ∈ {.0, .25, .5}, BS for several values of beam width b ∈ {1, 2, 3} and A* with the linear heuristic ˆh. Recall that ϵ-A(ϵ = .0) is equivalent to UC, whereas ϵ-A(ϵ = .5) is equivalent to GS and to BS with b = 1. The results will be presented in terms of the subset 0/1 loss estimated by means of a 10-fold cross-validation.

The base learner employed to obtain the binary classifiers fi was logistic regression [Lin et al., 2008] with probabilistic output. The regularization parameter C was established for each individual binary classifier performing a grid search over the values C ∈ {10-3 , 10-2 , . . . , 102 , 103 } optimizing the brier loss [Brier, 1950] estimated by means of a balanced 2-fold cross validation repeated 5 times. This loss function is a proper score that measures the accuracy of probabilistic predictions, as those provided by logistic regression.

Table 1 shows subset 0/1 scores. UC, ϵ-A(.0) and A*(ˆh)

provide optimal predictions in terms 0/1 subset loss, given the fi classifiers learned. They are shown all together in the first column. As expected, the performance of ϵ-A algorithm decreases as the value of ϵ increases (.25 or .5). These two versions combined perform worse than UC, ϵ-A(.0) and A*(ˆh) in 13 out of 16 cases. On the other hand, the performance of BS converges to the optimal one as the value of b increases. For BS(2) there are four datasets in which its scores are worse than those of A*(ˆh), UC and ϵ-A(.0) and in the other four its results are equal or better. Notice that the differences are larger when BS(2) performs worse. In the case of BS(3), in five datasets its scores are exactly the same than those of UC, ϵ-A(.0) and A*(ˆh), showing the convergence of the method. We do not run further experiments to study this aspect, because as we shall analyze later, the number of nodes explored by BS(3) is greater than those of the optimal methods.

Table 2 contains the number of nodes explored by each method and average prediction times. GS (or ϵ-A(.5) and BS(1)) is, of course, the method which explores the least number of nodes, since it only goes over one path in the tree. Such number corresponds to the number of labels plus one, because the root node is also explored. In the comparison between those methods that do not return optimal predictions, it seems that ϵ-A(.25) tends to explore less nodes than BS(2), but it is worse in terms of subset 0/1 loss. BS(3) is the algorithm that expands the most number of nodes.

Focusing on the methods that return optimal predictions, A*(ˆh) explores less nodes, as we proved theoretically before. In fact, it explores a number of nodes lower than two times the number of labels (those of BS(2)), and sometimes it is quite close to the number of nodes explored by GS. This suggest that ˆh seems a quite good heuristic. However, the difference with respect to ϵ-A(.0) or UC is surprisingly small. The number of nodes explored by these two algorithms is lower than expected. The reason may be that the predictions of classifiers fi along the optimal path are usually close to 1 or to 0. There is not much uncertainty, so the level of backtracking is low. All these results suggest that the inference in PCC over these concrete MLC datasets, analyzed as a searching problem, is a quite easy task. In this sense, it is worth noting that those approaches based on sampling techniques, like Monte Carlo sampling, should use very small samples in order to be competitive over these benchmark datasets, further considering that such methods do not guarantee optimal predictions.

Looking at prediction times, interestingly ϵ-A(.0) and UC are not much slower than ϵ-A(.25) and ϵ-A(.5) and similar to BS(2) and BS(3). Moreover, UC and ϵ-A(.0) are faster than A*(ˆh) despite they explore more nodes. The reason is obviously the computational cost of ˆh, which is due to the number of probabilities that must be computed {P(yi | x, y1, . . . , yi-1)|i = j+1..m}, see (1). An alternative is to reduce the number of probabilities calculated, for instance, only the next d probabilities. Parameter d would allow us to control computational complexity.

6 Conclusions and future work

This paper proposes a new approach based on A* algorithm with an admisible heuristic for inferring predictions in PCC. Hence, our proposal A*(ˆh) provides optimal predictions in terms of subset 0/1 loss and explores less nodes than previous approaches that also produce optimal predictions. A*(ˆh) is limited to linear models, but this is not a major drawback because it is quite common to employ linear models. This is usually the case of MLC problems with many labels in which the examples of some classes may be scarce, since using nonlinear models in such problems can lead to overfitting.

In the experiments performed, uniform-cost search (or ϵA(ϵ = .0)) is a better choice than A*(ˆh) since the computational cost of evaluating the heuristic does not compensate the reduction in nodes explored. In any case, the benchmark datasets employed here seem quite simple and these methods should be tested over more complex problems. At this respect, approaches like beam search, Monte Carlo sampling and our proposal begin to have sense for more complex and difficult -as inference problems- MLC tasks.

In our opinion, heuristic search is a promising line of research for inference in PCC. As future work, new heuristics can be devised, keeping in mind that we should look for a trade off between their computational complexity and the quality of the estimations. For instance, limiting the depth of the heuristic may be a plausible alternative.