Search

Evolutionary multi-objective optimization algorithms have been developed to find a representative set of Pareto-optimal solutions in the past decades. However, researchers have pointed out that finding a representative set of Pareto-optimal solutions is not sufficient; the task of choosing a single preferred Pareto-optimal solution is also another important task which has received a widespread attention so far. In this paper, we propose an algorithm to help the decision maker (DM) choose the final preferred solution based on his/her preferred objectives. Our algorithm is called an adaptive angle based pruning algorithm with independent bias intensity tuning parameter (ADA-τ). The method begins by calculating the angle between a pair of solutions by using a simple arctangent function. The bias intensity parameter of each objective is introduced independently in order to approximate the portions of desirable solutions based on the DM’s preferred objectives. We consider several benchmark problems including two and three-objective problems. The experimental results have shown that our pruning algorithm provides a robust sub-set of Pareto-optimal solutions for the benchmark problems.

Given a set of facilities and a set of users, a reverse k nearest neighbors (RkNN) query q returns every user for which the query facility is one of the k-closest facilities. Due to its importance, RkNN query has received significant research attention in the past few years. Almost all of the existing techniques adopt a pruning-and-verification framework. Regions-based pruning and half-space pruning are the two most notable pruning strategies. The half-space based approach prunes a larger area and is generally believed to be superior. Influenced by this perception, almost all existing RkNN algorithms utilize and improve the half-space pruning strategy. We observe the weaknesses and strengths of both strategies and discover that the regions-based pruning has certain strengths that have not been exploited in the past. Motivated by this, we present a new RkNN algorithm called SLICE that utilizes the strength of regions-based pruning and overcomes its limitations. Our extensive experimental study on synthetic and real data sets demonstrate that SLICE is significantly more efficient than the existing algorithms. We also provide a detailed theoretical analysis to analyze various aspects of our algorithm such as I/O cost, the unpruned area, and the cost of its verification phase etc. The experimental study validates our theoretical analysis. © 2014 IEEE.

Search Results Clustering (SRC) is a well-known approach to address the lexical ambiguity issue that all search engines suffer from. This paper develops an Expectation Maximization (EM)-based adaptive term pruning method for enhancing search result analysis. Knowledge preserving capabilities of this approach are demonstrated on the AMBIENT dataset using Snowball clustering method.

For many applications of the A* algorithm, the state space is a graph rather than a tree. The implication of this for parallel A* algorithms is that different processors may perform significant duplicated work if interprocessor duplicates are not pruned. In this paper, we consider the problem of duplicate pruning in parallel A* graph-search algorithms implemented on distributed-memory machines. A commonly used method for duplicate pruning uses a hash function to associate with each distinct node of the search space a particular processor to which duplicate nodes arising in different processors are transmitted and thereby pruned. This approach has two major drawbacks. First, load balance is determined solely by the hash function. Second, node transmissions for duplicate pruning are global; this can lead to hot spots and slower message delivery. To overcome these problems, we propose two different duplicate pruning strategies: 1) To achieve good load balance, we decouple the task of duplicate pruning from load balancing, by using a hash function for the former and a load balancing scheme for the latter. 2) A novel search-space partitioning scheme that allocates disjoint parts of the search space to disjoint subcubes in a hypercube (or disjoint processor groups in the target architecture), so that duplicate pruning is achieved with only intrasubcube or adjacent intersubcube communication. Thus message latency and hot-spot probability are greatly reduced. The above duplicate pruning schemes were implemented on an nCUBE2 hypercube multicomputer to solve the Traveling Salesman Problem (TSP). For uniformly distributed intercity costs, our strategies yield a speedup improvement of 13 to 35 percent on 1,024-processors over previous methods that do not prune any duplicates, and 13 to 25 percent over the previous hashing-only scheme. For normally distributed data the corresponding figures are 135 percent and 10 to 155 percent. Finally, we analyze the scalability of our parallel A* algorithms on k-ary n-cube networks in terms of the isoefficiency metric, and show that they have isoefficiency lower and upper bounds of /spl Theta/(P log P) and /spl Theta/(Pkn/sup 2/), respectively.

As a query processing optimization technique over inverted index, static index pruning can significantly reduce index size and query processing time. A fast static index pruning algorithm is presented, which is a term-centric method and adopts BM25 weighting as the pruning measure. The algorithm scans through documents set with one pass and directly builds pruned index, and therefore avoids the construction of original index. The correctness of the algorithm is proved and the theoretical analysis reveals that its IO performance takes precedence over other algorithms. The experiments based on TREC data set also show that the fast static index pruning algorithm requires less time to build pruned index, and the pruning effectiveness outperforms the baseline method.

Monte-Carlo Tree Search is a sampling-based search algorithm that has been successfully applied to a variety of games. Monte-Carlo rollouts allow it to take distant consequences of moves into account, giving it a strategic advantage in many domains over traditional depth-limited minimax search with alpha-beta pruning. However, MCTS builds a highly selective tree and can therefore miss crucial moves and fall into traps in tactical situations. Full-width minimax search does not suffer from this weakness. This paper proposes MCTS-minimax hybrids that employ shallow minimax searches within the MCTS framework. The three proposed approaches use minimax in the selection/expansion phase, the rollout phase, and the backpropagation phase of MCTS. Without requiring domain knowledge in the form of evaluation functions, these hybrid algorithms are a first step at combining the strategic strength of MCTS and the tactical strength of minimax. We investigate their effectiveness in the test domains of Connect-4 and Breakthrough.

In this paper, we recast static index pruning as a model induction problem under the framework of Kullback's principle of minimum cross-entropy. We show that static index pruning has an approximate analytical solution in the form of convex integer program. Further analysis on computation feasibility suggests that one of its surrogate model can be solved efficiently. This result has led to the rediscovery of \emph{uniform pruning}, a simple yet powerful pruning method proposed in 2001 and later easily ignored by many of us. To empirically verify this result, we conducted experiments under a new design in which prune ratio is strictly controlled. Our result on standard ad-hoc retrieval benchmarks has confirmed that uniform pruning is robust to high prune ratio and its performance is currently state of the art.

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.

We develop a new static index pruning criterion based on the notion of information preservation. This idea is motivated by the fact that model degeneration, as does static index pruning, inevitably reduces the predictive power of the resulting model. We model this loss in predictive power using conditional entropy and show that the decision in static index pruning can therefore be optimized to preserve information as much as possible. We evaluated the proposed approach on three different test corpora, and the result shows that our approach is comparable in retrieval performance to state-of-the-art methods. When efficiency is of concern, our method has some advantages over the reference methods and is therefore suggested in Web retrieval settings.

Tree pruning can significantly reduce the complexity of sphere decoding (SD). How to determine the pruning rule is an open problem of tree pruning. In this paper, we propose a pruning strategy for SD based on path metric. Because only the nearest lattice point is concerned, if the ratio of the metric to the minimum metric is larger than a threshold, the path whose metric is large enough can be pruned. We analyze the influence of the choice of the thresholds on the performance and the complexity. Through analysis and the simulations, we can show that the complexity reduction is significant while maintaining the negligible performance degradation when proper thresholds are chosen. Besides, tradeoff between complexity and performance can be easily achieved by adjusting the thresholds.

We compare the most important pruning methods which are common in different LVCSR decoding architectures and lead them back to a theoretical motivation. Based on this motivation, we propose a new pruning method which fades the word end pruning over a large part of the search network. We analyze the methods regarding their relationship between search-space and word error rate, and regarding their mutual dependence. We show that the different pruning methods are mutually dependent and difficult to combine, and that our new pruning method is the most effective method regarding both the search space and runtime efficiency.

Publisher Summary This chapter discusses learning approaches to prune the successor set(s). It studies the exclusion of forbidden states or move sequences and localizing the search using the notion of relevance. The chapter distinguishes between on-the-fly and offline learning. One of the most effective approaches to tackle large problem spaces is to prune (i.e., cutoff branches from) the search tree. There are multiple reasons for pruning. Some branches might not lead to a goal state, others lead to inferior solutions; some result in positions already reached on different paths, and others are redundant; though these might lead to a solution, there are still alternatives that also lead to a solution. All state space pruning techniques reduce the node-branching factor of the search tree such that fewer successor nodes have to be analyzed. Since a smaller part of the state space is generated, pruning saves both search time and space. However, there might be a trade-off between the two. Some techniques require rather complex data structures, such that the maintenance of pruning information may be involved. Static pruning techniques detect pruning knowledge prior to the main search routine. Other pruning rules may not be known to the search algorithm at its start and have to be inferred during the execution of the program. This leads to layered search algorithms. In the top-level search, the search algorithms search for problem solutions, and in frequently invoked lower-level searches, pruning knowledge is refined.

Pattern recognition in large amount of data has been paramount in the last decade, since that is not straightforward to design interactive and real time classification systems. Very recently, the Optimum-Path Forest classifier was proposed to overcome such limitations, together with its training set pruning algorithm, which requires a parameter that has been empirically set up to date. In this paper, we propose a Harmony Search-based algorithm that can find near optimal values for that. The experimental results have showed that our algorithm is able to find proper values for the OPF pruning algorithm parameter.

Fuzzified game tree search algorithm is based on the idea that the exact game tree evaluation is not required to find the best move. Therefore, pruning techniques may be applied earlier resulting in faster search and greater performance. Applied to an abstract domain, it outperforms the existing ones such as Alpha-Beta, PVS, Negascout, NegaC*, SSS*/ Dual* and MTD(f). In this paper we present experimental results in real domain games, where the proposed algorithm demonstrated 10 percent performance increase over the existing algorithms.

Many traditional pruning methods assume that all the datasets are equally probable and equally important. Thus, they apply equal pruning to all the datasets. However, in real-world classification problems, all the datasets are not equal. Consequently, considering equal pruning rate tends to generate inefficient and large size decision trees. Therefore, we propose a practical algorithm to deal with the data specific classification problem when there are datasets with different properties. In this paper, First, we computed the data specific pruning values for each dataset. Then, we used expert knowledge to find inexact pruning value. Finally, we integrated those values in a well established pruning technique to form Expert Knowledge based Pruning (EKBP). We empirically validated the analysis with publicly available 40 datasets from UCI on four existing techniques. Both the analytical and experimental results have shown that our proposed method achieves reduction of tree size and retains equal or better accuracy.

In this paper, we formulate a novel problem for finding black hole and volcano patterns in a large directed graph. Specifically, a black hole pattern is a group which is made of a set of nodes in a way such that there are only in links to this group from the rest nodes in the graph. In contrast, a volcano pattern is a group which only has out links to the rest nodes in the graph. Both patterns can be observed in real world. For instance, in a trading network, a black hole pattern may represent a group of traders who are manipulating the market. In the paper, we first prove that the black hole mining problem is a dual problem of finding volcanoes. Therefore, we focus on finding the black hole patterns. Along this line, we design two pruning schemes to guide the black hole finding process. In the first pruning scheme, we strategically prune the search space based on a set of pattern-size-independent pruning rules and develop an iBlack hole algorithm. The second pruning scheme follows a divide-and-conquer strategy to further exploit the pruning results from the first pruning scheme. Indeed, a target directed graphs can be divided into several disconnected sub graphs by the first pruning scheme, and thus the black hole finding can be conducted in each disconnected sub graph rather than in a large graph. Based on these two pruning schemes, we also develop an iBlackhole-DC algorithm. Finally, experimental results on real-world data show that the iBlackhole-DC algorithm can be several orders of magnitude faster than the iBlackhole algorithm, which has a huge computational advantage over a brute-force method.

The search for the optimal word sequence can be performed efficiently even in a speech recognizer with a very large vocabulary and complex models. This is achieved using pruning methods with empirically chosen parameters and the willingness to accept a certain amount of pruning errors. Quite unsatisfying though, it is state-of-the-art that such pruning errors are not directly detected but, instead, indirect consequences of them, providing only a rough picture of what happens during search. With the tool Direct Observation of Pruning Errors (DOPE), described in this paper, pruning errors are detected on the state hypothesis level, which is a very fine level of granulation, several orders of magnitude finer than the sentence level. This allows much more exact analyses, including the analysis of pruning methods, or the effects of pruning parameters.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-12127-2_11, Proceedings of 9th International Workshop, MCS 2010, Cairo, Egypt, April 7-9, 2010., This article introduces a double pruning algorithm that can be used to reduce the storage requirements, speed-up the classification process and improve the performance of parallel ensembles. A key element in the design of the algorithm is the estimation of the class label that the ensemble assigns to a given test instance by polling only a fraction of its classifiers. Instead of applying this form of dynamical (instance-based) pruning to the original ensemble, we propose to apply it to a subset of classifiers selected using standard ensemble pruning techniques. The pruned subensemble is built by first modifying the order in which classifiers are aggregated in the ensemble and then selecting the first classifiers in the ordered sequence. Experiments in benchmark problems illustrate the improvements that can be obtained with this technique. Specifically, using a bagging ensemble of 101 CART trees as a starting point, only the 21 trees of the pruned ordered ensemble need to be stored in memory. Depending on the classification task, on average, only 5 to 12 of these 21 classifiers are queried to compute the predictions. The generalization performance achieved by this double pruning algorithm is similar to pruned ordered bagging and significantly better than standard bagging.

A fast OBS pruning algorithm based on pseudo-entropy of weights is proposed to resolve the problems of the number of hidden neurons is difficult to be determined in neural networks and low pruning speed in conventional OBS (Optimal Brain Surgeon) pruning algorithm. The algorithm makes the network constrain the distribution of weight automatically during the training process, obtain a simpler structure of network, and improve the speed of pruning. The result of experimental shows that the structure of network has been simplified; the generalization capability of network and the speed of pruning have been improved greatly by using the algorithm mentioned above.

This paper presents an efficient frame-synchronous beam pruning for automatic speech recognition. With conventional beam pruning, hypotheses that have a greater potential to reach various words on a lexical tree are likely to be pruned out, since this potential is not taken into account. To make the beam pruning less restrictive for hypotheses with a greater potential and vice versa, the proposed method adds a reward as a monotonically increasing function of the number of reachable words from the node where a hypothesis stays on a lexical tree, to the likelihood of the hypothesis. The reward is designed not to collapse the ASR probabilistic framework. The proposed method reduces the processing time from 30% to 70% for grammar-based tasks. For a language-model-based dictation task, it also causes an additional reduction from the processing time of the beam pruning with the language model look-ahead technique.

Probability trees are decision trees that predict class probabilities rather than the most likely class. The pruning criterion used to learn a probability tree strongly influences the size of the tree and thereby also the quality of its probability estimates. While the effect of pruning criteria on classification accuracy is well-studied, only recently there is more interest in the effect on probability estimates. Hence, it is currently unclear which pruning criteria for probability trees are preferable under which circumstances. In this paper we survey six of the most important pruning criteria for probability trees, and discuss their theoretical advantages and disadvantages. We also perform an extensive experimental study of the relative performance of these pruning criteria. The main conclusion is that overall a pruning criterion based on randomization tests performs best because it is most robust to extreme data characteristics (such as class skew or a high number of classes). We also identify and explain several shortcomings of the other pruning criteria. ispartof: Machine Learning vol:78 issue:1 pages:251-285 status: published

In this paper, a novel pruning algorithm is proposed for self-organizing the feed-forward neural network based on the sensitivity analysis, named novel pruning feed-forward neural network (NP-FNN). In this study, the number of hidden neurons is determined by the output's sensitivity to the hidden nodes. This technique determines the relevance of the hidden nodes by analyzing the Fourier decomposition of the variance. Then each hidden node can obtain a contribution ratio. The connected weights of the hidden nodes with small ratio will be set as zeros. Therefore, the computational cost of the training process will be reduced significantly. It is clearly shown that the novel pruning algorithm minimizes the complexity of the final feed-forward neural network. Finally, computer simulation results are carried out to demonstrate the effectiveness of the proposed algorithm.

The game playing is an import domain of heuristic search, and its procedure is represented by a special and/or tree. Alpha-beta pruning is always used for problem solving by searching the game-playing-tree. In this paper, the plan which child nodes are inserted into game-playing-tree from large value of estimation function to small one when the node of no receiving fixed ply depth is expand is proposed based on alpha-beta pruning. It improves effect of search

In this paper we develop a new post-pruning algorithm. This new pruning algorithm uses two or more post-pruning algorithms to prune a decision tree that has been built on training set by different orders, and the “best” tree is selected based either on separate test set accuracy or cross-validations from trees coming from result of the above step. The algorithm is theoretically based on occam's razor that is a simpler model is chosen if two models have the same performance on the training set. An experiment is implemented on three databases in UCI machine learning repository and the new algorithm is employed to compares with two well-known post-pruning algorithms. The results show that the hybrid pruning algorithm effectively reduces the complexity of decision trees without sacrificing accuracy.

Ensemble pruning deals with the reduction of base classifiers prior to combination in order to improve generalization and prediction efficiency. Existing ensemble pruning algorithms require much pruning time. This paper presents a fast pruning approach: PMEP (Pattern Mining based Ensemble Pruning). In this algorithm, the prediction results of all base classifiers are organized as a transaction database, and FP-Tree structure is used to compact the prediction results. Then a greedy pattern mining method is explored to find the ensemble of size k . After obtaining the ensembles of all possible sizes, the one with the best accuracy is outputted. Compared with Bagging, GASEN, and Forward Selection, experimental results show that PMEP achieves the best prediction accuracy and keeps the size of the final ensemble small, more importantly, its pruning time is much less than other ensemble pruning algorithms.

Genetic algorithm is one of the commonly used approaches on machine learning. In this paper, we put forward a genetic algorithm approach for pruning decision tree. Binary coding is adopted in which an individual in a population consists of a fixed number of weight that stand for a solution candidate. The evaluation function considers error rate of decision tree over the test set. Three common operators for genetic algorithm such as random mutation and single-point crossover is applied for the population. Finally the algorithm returns an individual with the highest fitness as a local optimal weight. Based on four databases from UCI, we compared our approach with several other traditional decision tree pruning techniques including cost-complexity pruning, Pessimistic Error Pruning and Reduced error pruning. The results show that our approach has an better or equal effect with other pruning method.

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.

Pruning is one of the key procedures in training decision tree classifiers. It removes trivial rules from the raw knowledge base built from training examples, in order to avoid over-using noisy, conflicting, or fuzzy inputs, so that the refined model can generalize better with unseen cases. In this paper, we present a number of properties of k-norm pruning, a recently proposed pruning algorithm, which has clear theoretical interpretation. In an earlier paper it was shown that k-norm pruning compares very favorably in terms of accuracy and size with minimal cost-complexity pruning and error based pruning, two of the most cited decision tree pruning methods; it was also shown that k-norm pruning is more efficient, at times orders of magnitude more efficient than minimal cost-complexity pruning and error based pruning. In this paper, we demonstrate the validity of the k-norm properties through a series of theorems, and explain their practical significance.

In optimizing the neural network structure, there are two methods: the pruning scheme and the constructive scheme. This paper uses the pruning scheme to optimize neural network structure. The genetic algorithm is used to find out the optimum node pruning. In the conventional researches, the input and hidden layers were optimized separately. On the contrary we attempted to optimize the two layers simultaneously by encoding two layers in a chromosome. The offspring networks inherit the weights from the parent. For learning, we used the existing error back-propagation algorithm. In our experiment with various databases from UCI Machine Learning Repository, we could get the peak performance when the network size was reduced by about 8~25%. As a result of t-test the proposed method was shown to have a better performance, compared with other pruning or construction methods.

The algebraic code excited linear prediction (ACELP) algorithm has been adopted by many speech coding standards, due to low complexity and high quality in its analysis-by-synthesis optimization. One of the optimum proposed algorithms, for reduction of complexity of fix codebook search, is the method based on the pruning of tree with less probability for best excitation in depth first tree search. In this paper, two methods of dynamic pruning of tree, namely single and multi level dynamic tree pruning, are proposed. In addition to low complexity like pruning of tree method, both methods have higher efficiency close to the depth first tree method (one of the most efficient searching methods). The efficiency and complexity of these two methods are compared with pruning of tree and depth first tree methods in an example using by GSM EFR coders.

In this article we review standard null-move pruning and introduce our extended version of it, which we call verified null-move pruning. In verified null-move pruning, whenever the shallow null-move search indicates a fail-high, instead of cutting off the search from the current node, the search is continued with reduced depth. Our experiments with verified null-move pruning show that on average, it constructs a smaller search tree with greater tactical strength in comparison to standard null-move pruning. Moreover, unlike standard null-move pruning, which fails badly in zugzwang positions, verified null-move pruning manages to detect most zugzwangs and in such cases conducts a re-search to obtain the correct result. In addition, verified null-move pruning is very easy to implement, and any standard null-move pruning program can use verified null-move pruning by modifying only a few lines of code., Comment: 9 pages

We propose depth-limited heuristic search as a general paradigm for real-time problem solving in a dynamic environment. When combined with iterative-deepening, it provides the ability to commit to an action almost instantaneously, but allows the quality of that decision to improve as long as time is available. Once a deadline is reached, the best decision arrived at is executed. We illustrate the paradigm in three different settings, corresponding to single-agent search, two-player games, and multi-agent problem solving. First we review two-player minimax search with alpha-beta pruning. Minimax can be extended to themaxn algorithm for more than two players, which admits a much weaker form of alpha-beta pruning. Finally, we explore real-time search algorithms for single-agent problems. Minimax is specialized tominimin, which allows a very powerfulalpha pruning algorithm. In addition,real-time-A * allows backtracking while still guaranteeing a solution and making locally optimal decisions.

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 Web search engines maintain large-scale inverted indexes which are queried thousands of times per second by users eager for information. In order to cope with the vast amounts of query loads, search engines prune their index to keep documents that are likely to be returned as top results, and use this pruned index to compute the first batches of results. While this approach can improve performance by reducing the size of the index, if we compute the top results only from the pruned index we may notice a significant degradation in the result quality: if a document should be in the top results but was not included in the pruned index, it will be placed behind the results computed from the pruned index. Given the fierce competition in the online search market, this phenomenon is clearly undesirable.In this paper, we study how we can avoid any degradation of result quality due to the pruning-based performance optimization, while still realizing most of its benefit. Our contribution is a number of modifications in the pruning techniques for creating the pruned index and a new result computation algorithm that guarantees that the top-matching pages are always placed at the top search results, even though we are computing the first batch from the pruned index most of the time. We also show how to determine the optimal size of a pruned index and we experimentally evaluate our algorithms on a collection of 130 million Web pages.

Some fast nearest neighbor search (NNS) algorithms using metric properties have appeared in the last years for reducing computational cost. Depending on the structure used to store the training set, different strategies to speed up the search have been defined. For instance, pruning rules avoid the search of some branches of a tree in a tree-based search algorithm. In this paper, we propose a new and simple pruning rule that can be used in most of the tree-based search algorithms. All the information needed by the rule can be stored in a table (at preprocessing time). Moreover, the rule can be computed in constant time. This approach is evaluated through real and artificial data experiments. In order to test its performance, the rule is compared to and combined with other previously defined rules.

We show a statistical pruning approach for maximum likelihood (ML) detection of multiple-input multiple-output (MIMO) systems. We present a general pruning strategy for sphere decoder (SD), which can also be applied to any tree search algorithms. Our pruning rules are effective especially for the case when SD has high complexity. Three specific pruning rules are given and discussed. From analyzing the union bound on the symbol error probability, we show that the diversity order of the deterministic pruning is only one by fixing the pruning probability. By choosing different pruning probability distribution functions, the statistical pruning can achieve arbitrary diversity orders and SNR gains. Our statistical pruning strategy thus achieves a flexible trade-off between complexity and performance.

Maximal frequent itemsets (MFIs) mining is important for many applications. To improve the performance of the MFI algorithms, the key is to use appropriate pruning techniques which can maximally reduce the searching space of the algorithm. In this paper, we present a novel pruning technique, subset equivalence pruning. To mining MFIs in data streams, we reconstruct the FPmax* algorithm to a single-pass algorithm, named FPmax*-DS. Subset equivalence pruning technique is added in FPmax*-DS. The experiments show that the pruning technique can efficiently reduce the searching space. Especially for some dense datasets, the size of searching space can be trimmed off by about 40%.

Pruning decision trees is an effective way to overwhelm over-fitting in practice. Various pruning methods have been proposed in many literatures. Though these methods prune decision trees in the light of the principle of 'Minimum Description Length', they fail to explicitly take into account the impacts of tree scales in the pruning process. This paper proposes a simple decision tree pruning method based on RST (Rough Set Theory). Depth-fitting ratio is introduced for pruning a constructed decision tree, which involves both the depth and the explicit degrees of the sub-trees under evaluation. Experiments on some open data sets shows the feasibility of the new pruning method.

In this paper an algorithm for pruning a set of non-dominated solutions is proposed. The algorithm is based on the crowding distance calculation used in the elitist non-dominated sorting genetic algorithm (NSGA-II). The time complexity class of the new algorithm is estimated and in most cases it is the same as for the original pruning algorithm. Numerical results also support this estimate. For used bi-objective test problems, the proposed pruning algorithm is demonstrated to provide better distribution compared to the original pruning algorithm of NSGA-II. However, with tri-objective test problems there is no improvement and this study reveals that crowding distance does not estimate crowdedness well in this case and presumably also in cases of more objectives.

This work proposes a new rule pruning procedure for Ant-Miner, an Ant Colony algorithm that discovers classification rules in the context of data mining. The performance of Ant-Miner with the new pruning procedure is evaluated and compared with the performance of the original Ant-Miner across several datasets. The results show that the new pruning procedure has a mixed effect on the performance of Ant-Miner. On one hand, overall it tends to decrease the classification accuracy more often than it improves it. On the other hand, the new pruning procedure in general leads to the discovery of classification rules that are considerably shorter, and so simpler (more easily interpretable by the users) than the rules discovered by the original Ant-Miner.

A lot of works address the mining of patterns under constraints. The search space is reduced by taking advantage of pruning conditions on patterns, typically by using anti-monotone and monotone properties. In this paper, we introduce two virtual patterns in order to automatically deduce pruning conditions from any constraint coming from the primitive-based framework which gathers a large set of varied constraints. These virtual patterns enable us to provide negative and positive pruning conditions according to the generalization and the specialization of patterns. We show that these pruning conditions are monotone or anti-monotone and can be pushed into usual constraint mining algorithms. Experiments carried on several contexts show that our proposals improve the mining.

Most speech recognition systems search through large finite state machines to find the most likely path, or hypothesis. Efficient search in these large spaces requires pruning of some hypotheses. Popular pruning techniques include probability pruning which keeps only hypotheses whose probability falls within a prescribed factor from the most likely one, and rank pruning which keeps only a prescribed number of the most probable hypotheses. Rank pruning provides better control over memory use and search complexity, but it requires sorting of the hypotheses, a time consuming task that may slow the recognition process. We propose a pruning technique which combines the advantages of probability and rank pruning. Its time complexity is similar to that of probability pruning and its search-space size, memory consumption, and recognition accuracy are comparable to those of rank pruning. We also describe a research-motivated Java-based speech recognition system that is being built at UCSD.

We propose a computationally efficient detection algorithm with near ML performance for space-time communications systems. Our algorithm is based on pruning (excluding) branches from the search tree arising in the sphere decoding (SD) algorithm. The choice of the branches to be pruned relies on intuitive geometrical reasoning which is in turn based on a simplified channel model designed to capture the effect of badly conditioned channel realizations. The remaining search tree after pruning can be processed by the conventional SD algorithm with strongly reduced complexity as against scanning the complete tree. Simulation results show that despite the pruning near ML results can be obtained.

The problem of determining the proper size of an artificial neural network is recognized to be crucial. One popular approach is pruning which means training a larger than necessary network and removing unnecessary weights/nodes. Though pruning is commonly used in architecture learning of neural network, there is still no theoretical framework about it. We give an information geometric explanation of pruning. In information geometric framework, most kinds of neural networks form exponential or mixture manifold which has a natural hierarchical structure. In a hierarchical set of systems, a lower order system is included in the parameter space of a large one as a submanifold. Such a parameter space has rich geometrical structures that are responsible for the dynamic behaviors of learning. The pruning problem is formulated in iterative m-projections from the current manifold to its submanifold in which the divergence between the two manifolds is minimized, and it means meaning the network performance does not worsen over the entire pruning process. The result gives a geometric understanding and an information geometric guideline of pruning, which has more authentic theoretic foundation.

In this paper we investigate the relationship between closed itemset mining, the complete pruning technique and item ordering in the Apriori algorithm. We claim, that when proper item order is used, complete pruning does not necessarily speed up Apriori, and in databases with certain characteristics, pruning increases run time significantly. We also show that if complete pruning is applied, then an intersection-based technique not only results in a faster algorithm, but we get free closed-itemset selection concerning both memory consumption and run-time.

The min-max modular neural network with Gaussian zero-crossing function (M3-GZC) has locally tuned response characteristic and emergent incremental learning ability, but it suffers from quadratic complexity in storage space and response time. Redundant Sample pruning and redundant structure pruning can be considered to overcome these weaknesses. This paper aims at the latter; it analyzes the properties of receptive field in M3-GZC network, and then proposes a strategy for pruning redundant modules. Experiments on both structure pruning and integrated with sample pruning are performed. The results show that our algorithm reduces both the size of the network and the response time notably while not changing the decision boundaries.

We implemented a pruning algorithm for a self-organizing tree (S-TREE) using cluster validity. The S-TREE algorithm need to set the limit of the number of nodes U to prune extra nodes beforehand. However, the implemented algorithm is not necessary to set U for pruning. Setting U in advance is difficult because the value of U depends on the problem. Moreover, U might be an obstacle to self-organization and prevent the formation of natural clusters. The usefulness of the algorithm was examined by experiments on vector quantization (VQ). In the experiments, performance of an S-TREE with the new pruning algorithm was compared with that of an S-TREE without pruning. The results of experiments showed that the implemented algorithm not only greatly reduces the number of leaf nodes but also maintains the quality of decoded images to a level approximately equivalent to that of images decoded by the S-TREE without a pruning algorithm. The results therefore indicate that the implemented algorithm also contributes the formation of the natural clusters.

It has been asserted that, using traditional pruning methods, growing decision trees with increasingly larger amounts of training data will result in larger tree sizes even when accuracy does not increase. With regard to error-based pruning, the experimental data used to illustrate this assertion have apparently been obtained using the default setting for pruning strength; in particular, using the default certainty factor of 25 in the C4.5 decision tree implementation. We show that, in general, an appropriate setting of the certainty factor for error-based pruning will cause decision tree size to plateau when accuracy is not increasing with more training data.

Selection of the optimal architecture of a neural network is crucial to ensure good generalization by reducing the occurrence of overfitting. While much work has been done to develop pruning algorithms for networks that employ summation units, not much has been done on pruning of product unit neural networks. The paper develops and tests a pruning algorithm for product unit networks, and illustrates its performance on several function approximation tasks.