Search

Tree-based methods are a non-parametric modelling strategy that can be used in combination with generalized linear models or Cox proportional hazards models, mostly at an exploratory stage. Their popularity is mainly due to the simplicity of the technique along with the ease in which the resulting model can be interpreted. Variable selection bias from variables with many possible splits or missing values has been identified as one of the problems associated with tree-based methods. A number of unbiased recursive partitioning algorithms have been proposed that avoid this bias by using p -values in the splitting procedure of the algorithm. The final tree is obtained using direct stopping rules (pre-pruning strategy) or by growing a large tree first and pruning it afterwards (post-pruning). Some of the drawbacks of pre-pruned trees based on p -values in the presence of interaction effects and a large number of explanatory variables are discussed, and a simple alternative post-pruning solution is presented that allows the identification of such interactions. The proposed method includes a novel pruning algorithm that uses a false discovery rate (FDR) controlling procedure for the determination of splits corresponding to significant tests. The new approach is demonstrated with simulated and real-life examples.

Entropy-based pruning has a limit in selecting a fine distribution of phrase pairs to be pruned in a threshold.Changing the distribution through other divergence metrics improves pruning efficiency in our preliminary empirical analysis.Derived problematic factors are fixed divergence distribution and missing impact of word-coupling strength.We propose a fine pruning method using two parameters to control the factors and analyze their effects to divergence change.It improves pruning efficiency compared with Entropy-based pruning in practical translations of English, Spanish, and French. A widely used automatic translation approach, phrase-based statistical machine translation, learns a probabilistic translation model composed of phrases from a large parallel corpus with a large language model. The translation model is often enormous because of many combinations of source and target phrases, which leads to the restriction of applications to limited computing environments. Entropy-based pruning resolves this issue by reducing the model size while retaining the translation quality. To safely reduce the size, this method detects redundant components by evaluating a relative entropy of models before and after pruning the components. In the literature, this method is effective, but we have observed that it can be improved more by adjusting the divergence distribution determined by the relative entropy. In the results of preliminary experiments, we derive two factors responsible for limiting pruning efficiency of entropy-based pruning. The first factor is proportion of pairs composing translation models with respect to their translation probability and its estimate. The second factor is the exponential increase of the divergence for pairs with low translation probability and estimate. To control the factors, we propose a divergence-based fine pruning using a divergence metric to adapt the curvature change of the boundary conditions for pruning and Laplace smoothing. In practical translation tasks for English-Spanish and English-French language pairs, this method shows statistically significant improvement on the efficiency up to 50% and average 12% more pruning compared to entropy-based pruning to show the same translation quality.

Learning from imbalanced data is attracting an increasing interest by the machine learning community. This is mainly due to the high number of real applications that are affected by this situation. The adaptation of the standard decision trees to deal with imbalanced data represents one of the important number of approaches that have been developed to address this problem. This adaptation has been proposed under three different perspectives: splitting criterion, assignment rule and pruning. In this paper, we focus our attention to the pruning of decision trees. We propose an adaptation of the standard pruning algorithm MCCP to address the skewed-data problem. Our contribution affects two levels: adaption of the metric used in selecting nodes to be firstly pruned and change of the evaluation measure used in selecting the best decision-tree through the pruning set. Our goal is to show that, contrary to the popular belief in the literature enquiring into the uselessness of decision tree pruning, an adaptive pruning technique for imbalanced situations is more efficient and more accurate towards the minority class. A total of twelve binary class data-sets having different imbalance ratio are used to test the performance of the proposed method. Experimental results show that the proposed post-pruning approach can increase the performance of imbalanced decision trees in terms of evaluation measures that are recent and appropriate for the context of imbalanced classification.

Ensemble pruning is substantial for the successful application of an ensemble system. A novel method for Ensemble Pruning via BackTracking algorithm (EnPBT) was proposed by us in our previous work. Backtracking algorithm can systematically search for the solutions of a problem in a depth-first and jumping manner, suitable for solving all those large-scale combinatorial problems. The validity of EnPBT algorithm has been verified in our previous work. However, the relatively slow pruning speed might be a drawback of EnPBT. Aiming at this problem, an efficient and novel ensemble pruning algorithm is proposed in this paper, i.e. One-Path and Two-Trips (OPTT) ensemble pruning algorithm. It is very fast in pruning speed, while its classification performance has no significant difference with EnPBT, as demonstrated in the experimental results of this work. In short, OPTT achieves a proper trade-off between pruning effectiveness and efficiency.

Ensemble methods have been successfully used as a classification scheme. The reduction of the complexity of this popular learning paradigm motivated the appearance of ensemble pruning algorithms. This paper presents a new ensemble pruning method which highly reduces the complexity of ensemble methods and performs better than complete bagging in terms of classification accuracy. More importantly, it is a very fast algorithm. It consists in ordering all base classifiers with respect to a new criterion which exploits an unsupervised ensemble margin. This method highlights the major influence of low margin instances on the performance of the pruning task and, more generally, the potential of low margin instances for the design of better ensembles. Comparison to both the naive approach of randomly pruning base classifiers and another ordering-based pruning algorithm is carried out in an extensive empirical analysis.

Ensemble pruning is crucial for the consideration of both efficiency and predictive accuracy of an ensemble system. This paper proposes a new Competitive technique for Ensemble Pruning based on Cross-Validation (CEPCV). The data to be learnt by neural computing models are mostly drifting with time and environment, therefore a dynamic ensemble pruning method is indispensable for practical applications, while the proposed CEPCV method is just the kind of dynamic ensemble pruning method, which can realize on-line ensemble pruning and take full advantage of potentially valuable information. The algorithm naturally inherits the predominance of cross-validation technique, which implies that those networks regarded as winners in selective competitions and chosen into the pruned ensemble have the ''strongest'' generalization capability. It is essentially based on the strategy of ''divide and rule, collect the wisdom'', and might alleviate the local minima problem of many conventional ensemble pruning approaches only at the cost of a little greater computational cost, which is acceptable to most applications of ensemble learning. The comparative experiments among the four ensemble pruning algorithms, including: CEPCV and the state-of-the-art Directed Hill Climbing Ensemble Pruning (DHCEP) algorithm and two baseline methods, i.e. BSM, which chooses the Best Single Model in the initial ensemble based on their performances on the pruning set, and ALL, which reserves all network members of the initial ensemble, on ten benchmark classification tasks, demonstrate the effectiveness and validity of CEPCV.

The efficiency of three forward-pruning techniques, i.e., futility pruning, null-move pruning, and LMR, is analyzed in shogi, a Japanese chess variant. It is shown that the techniques with the α – β pruning reduce the effective branching factor of shogi endgames to 2.8 without sacrificing much accuracy of the search results. Because the average number of the raw branching factor in shogi is around 80, the pruning techniques reduce the search space more effectively than in chess.

Highlights? Bottom-up pruning is extended to multiple tree context. ? Suitable pruning criteria are proposed. ? Method is tested on a number of UCI datasets. ? Method produces single trees with good performance/compactness. ? Applied to a churn prediction problem, interpretable trees were produced. A generalisation of bottom-up pruning is proposed as a model level combination method for a decision tree ensemble. Bottom up pruning on a single tree involves choosing between a subtree rooted at a node, and a leaf, dependant on a pruning criterion. A natural extension to an ensemble of trees is to allow subtrees from other ensemble trees to be grafted onto a node in addition to the operations of pruning to a leaf and leaving the existing subtree intact. Suitable pruning criteria are proposed and tested for this multi-tree pruning context. Gains in both performance and in particular compactness over individually pruned trees are observed in tests performed on a number of datasets from the UCI database. The method is further illustrated on a churn prediction problem in the telecommunications domain.

Support vector machine (SVM), which is analytically solved to reach its optimal structural formula, can be represented as a network architecture resembling artificial neural networks (multilayer perceptrons) that have been pruned to obtain model parsimony or improve generalization. This study presents two methods of pruning the support vector networks, and applies them to a case study of real-time flood stage forecasting. One method prunes the input variables by the cross-correlation method, while the other prunes the support vectors according to the derived relationship among SVM parameters. These pruning methods do not revise the SVM algorithm, and the pruned models therefore still have the optimal architecture. The real-time forecasting performance pertaining to the original and the pruned SVM models are compared, and comparison results indicate that the pruning reduces the network complexity but does not degrade the forecasting ability. Moreover, the deletion of support vectors and the change in their weights during the pruning process are identified, revealing that the support vectors with small weight (and hence less significant) tend to be pruned off, while the support vectors that are more informative to characterize the floods are preserved after the pruning. Finally, this study suggests that the proposed support vector pruning method be a potential data mining technique.

The cost-complexity pruning generates nested subtrees and selects the best one. However, its computational cost is large since it uses holdout sample or cross-validation. On the other hand, the pruning algorithms based on posterior calculations such as BIC (MDL) and MEP are faster, but they sometimes produce too big or small trees to yield poor generalization errors. In this paper, we propose an alternative pruning procedure which combines the ideas of the cost-complexity pruning and posterior calculation. The proposed algorithm uses only training samples, so that its computational cost is almost same as the other posterior-based algorithms, and at the same time yields similar accuracies as the cost-complexity pruning. Moreover it can be used for comparing non-nested trees, which is necessary for the BUMPing procedure. The empirical results show that the proposed algorithm performs similarly as the cost-complexity pruning in standard situations and works better for BUMPing.

In this paper forward-pruning methods, such as multi-cut and null move, are tested at so-called ALL nodes. We improved the principal variation search by four small but essential additions. The new PVS algorithm guarantees that forward pruning is safe at ALL nodes. Experiments show that multi-cut at ALL nodes (MC-A) when combined with other forward-pruning mechanisms give a significant reduction of the number of nodes searched. In comparison, a (more) aggressive version of the null move (variable null-move bound) gives less reduction at expected ALL nodes. Finally, it is demonstrated that the playing strength of the lines of action program MIA is significantly (scoring 21% more winning points than the opponent) increased by MC-A.

Decision tree is a divide and conquer classification method used in machine learning. Most pruning methods for decision trees minimize a classification error rate. In uncertain domains, some sub-trees that do not decrease the error rate can be relevant in pointing out some populations of specific interest or to give a representation of a large data file. A new pruning method (called DI pruning) is presented here. It takes into account the complexity of sub-trees and is able to keep sub-trees with leaves yielding to determine relevant decision rules, although they do not increase the classification efficiency. DI pruning allows to assess the quality of the data used for the knowledge discovery task. In practice, this method is implemented in the UnDeT software.

The efficiency of the αβ-algorithm as a minimax search procedure can be attributed to its effective pruning at the so-called cut-nodes; ideally only one move is examined there to establish the minimax value. This paper explores the benefits of investing additional search effort at cut-nodes by also expanding some of the remaining moves. Our results show a strong correlation between the number of promising move alternatives at cut-nodes and a new principal variation emerging. Furthermore, a new forward-pruning method is introduced that uses this additional information to ignore potentially futile subtrees. We also provide experimental results with the new pruning method in the domain of chess.

In the half century since minimax was first suggested as a strategy for adversary game search, various search algorithms have been developed. The standard approach has been to use improvements to the Alpha–Beta ( α – β ) algorithm. Some of the more powerful improvements examine continuations beyond the nominal search depth if they are of special interest, while others terminate the search early. The latter case is referred to as forward pruning. In this paper we discuss some important aspects of forward pruning, especially regarding risk-management, and propose ways of making risk-assessment. Finally, we introduce two new pruning methods based on some of the principles discussed here, and present experimental results from application of the methods in an established chess program.

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.

Empirical studies have shown that the performance of decision tree induction usually improves when the trees are pruned. Whether these results hold in general and to what extent pruning improves the accuracy of a concept have not been investigated theoretically. This paper provides a theoretical study of pruning. We focus on a particular type of pruning and determine a bound on the error due to pruning. This is combined with PAC (probably approximately correct) learning theory to determine a sample size sufficient to guarantee a probabilistic bound on the concept error. We also discuss additional pruning rules and give an analysis for the pruning error.

We describe a very simple selective search algorithm for two-player games, called best-first minimax. It always expands next the node at the end of the expected line of play, which determines the minimax value of the root. It uses the same information as alpha-beta minimax, and takes roughly the same time per node generation. We present an implementation of the algorithm that reduces its space complexity from exponential to linear in the search depth, but at significant time cost. Our actual implementation saves the subtree generated for one move that is still relevant after the player and opponent move, pruning subtrees below moves not chosen by either player. We also show how to efficiently generate a class of incremental random game trees. On uniform random game trees, best-first minimax outperforms alpha-beta, when both algorithms are given the same amount of computation. On random trees with random branching factors, best-first outperforms alpha-beta for shallow depths, but eventually loses at greater depths. We obtain similar results in the game of Othello. Finally, we present a hybrid best-first extension algorithm that combines alpha-beta with best-first minimax, and performs significantly better than alpha-beta in both domains, even at greater depths. In Othello, it beats alpha-beta in two out of three games.

Korf, R.E., Multi-player alpha-beta pruning (Research Note), Artificial Intelligence 48 (1991) 99-111. We consider the generalization of minimax search with alpha-beta pruning to non-cooperative, perfect-information games with more than two players. The minimax algorithm was generalized in [2] to the maxn algorithm applied to vectors of n-tuples representing the evaluations for each of the players. If we assume an upper bound on the sum of the evaluations for each player, and a lower bound on each individual evaluation, then shallow alpha-beta pruning is possible, but not deep pruning. In the best case, the asymptotic branching factor is reduced to (1 + 4bv'~b-"s~-3)/2. In the average case, however, pruning does not reduce the asymptotic branching factor. Thus, alpha-beta pruning is found to be effective only in the special case of two-player games. In addition, we show that it is an optimal directional algorithm for two players.

In game-tree search, a point value is customarily used to measure position evaluation. If the uncertainty about the value is to be reflected in the evaluation, which is described with probabilistic distribution or probabilities, the search process must back up distributions from leaf nodes to the root. It is shown that even though the merit value of a node is described by probabilities, α-β bounded windows can still be used to cut off some subtrees from search when a space-efficient depth-first traversal is applied to the game tree. Several variations of probability-based α-β game tree pruning are presented. We also show that probability-based α-β pruning can be viewed as a generalization of the standard α-β game tree search algorithm and that it inherits some good properties from its point-value version.

The alpha-beta technique for searching game trees is analyzed, in an attempt to provide some insight into its behavior. The first portion of this paper is an expository presentation of the method together with a proof of its correctness and a historical discussion. The alpha-beta procedure is shown to be optimal in a certain sense, and bounds are obtained for its running time with various kinds of random data.