Optimal search trees using two-way key comparisons

A generalization of binary search trees and binary split trees is developed that takes advantage of two-way key comparisons: the two-way comparison tree. The two-way comparison tree has little use for dynamic situations but is an improvement over the optimal binary search tree and the optimal binary split tree for static data sets. AnO(n) time and space algorithm is presented for constructing an optimal two-way comparison tree when access probabilities are equal, and an exact formula for the optimal cost is developed. The construction of the optimal two-way comparison tree for unequal access frequencies, both successful and unsuccessful, is computable inO(n ⁵) time andO(n ³) space using algorithms similar to those for the optimal binary split tree. The optimal two-way comparison tree can improve search cost by up to 50% over the optimal binary search tree.     

On the costs of optimal and near-optimal binary search trees

Summary We show that the cost of an optimal binary search tree can vary substantially, depending only on the left-to-right order imposed on the probabilities. We also prove that the costs of some common classes of near-optimal trees cannot be bounded above by the cost of an optimal tree plus a constant. This work was supported by the National Research Council of Canada, while the author was at the University of Waterloo     

On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krají?ek and Pudlák (J.?Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4?C5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist. We show that if one allows errors, then such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow an algorithm, called a heuristic acceptor, to claim a small number of false ??theorems?? and err with bounded probability on other inputs. The amount of false ??theorems?? is measured according to a polynomial-time samplable distribution on non-tautologies. Our result remains valid for all recursively enumerable languages and can also be viewed as the existence of an optimal weakly automatizable heuristic proof system. The notion of a heuristic acceptor extends the notion of a classical acceptor; in particular, an optimal heuristic acceptor for any distribution simulates every classical acceptor for the same language. We also note that the existence of a co-NP-language L with a polynomial-time samplable distribution on $\overline{L}$ that has no polynomial-time heuristic acceptors is equivalent to the existence of an infinitely-often one-way function.     

A framework for learning in search-based systems

We provide an overall framework for learning in search based systems that are used to find optimum solutions to problems. This framework assumes that prior knowledge is available in the form of one or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number of classes formed will depend on the resource constraints of the system. In the training phase, example problems are run using a standard admissible search algorithm. In this phase, heuristic information corresponding to each class is learned. This new information can be used in the problem solving phase by appropriate search algorithms so that subsequent problem instances can be solved more efficiently. In this framework, we also show that heuristic information of forms other than the conventional single valued underestimate value can be used, since we maintain the heuristic of each class explicitly. We show some novel search algorithms that can work with some such forms. Experimental results have been provided for some domains     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

Discriminant ECOC: a heuristic method for application dependent design of error correcting output codes

We present a heuristic method for learning error correcting output codes matrices based on a hierarchical partition of the class space that maximizes a discriminative criterion. To achieve this goal, the optimal codeword separation is sacrificed in favor of a maximum class discrimination in the partitions. The creation of the hierarchical partition set is performed using a binary tree. As a result, a compact matrix with high discrimination power is obtained. Our method is validated using the UCI database and applied to a real problem, the classification of traffic sign images.     

Considering complex training images with search tree partitioning

Using a complex training image (TI) for the single normal equation simulation (SNESIM) algorithm results in poor simulated realizations since that image contains trends and location specific patterns. By pooling all the TI patterns in a single search tree and not recording the relative locations of those patterns, some critical features of these complex TIs are lost.The search tree partitioning approach subdivides a large TI into imbricated, homogeneous, smaller images, called partition classes. Each of these partition classes has a corresponding search tree that can be utilized by the SNESIM algorithm. These partition classes are obtained by processing the TIs with spatial filters that are pattern sensitive. The resulting filter scores are then clustered into partition classes. All patterns within a partition class are recorded by a search tree; there is one tree per partition class. At each pixel along the simulation path, the partition class is retrieved first and used to select the appropriate search tree. That search tree contains the patterns relevant to that partition class.In practice, the partitioning approach adds flexibility in choosing a TI. TIs that were easier to obtain but traditionally too complex for simulation can now be considered as input to SNESIM. In many cases, it also significantly increases the simulation speed by searching a vector of smaller trees instead of a single large one. A plugin for the SGeMS software is provided.     

Updating a balanced search tree in O(1) rotations

Olivié has recently introduced the class of ‘half-balanced’ binary search trees, which have O(log n) access time but require only a constant number of single rotations for rebalancing after an insertion or a deletion. In this paper we show that a well-known class of balanced binary trees, the ‘symmetric binary B-trees’ of Bayer, have the same properties. This is not surprising, for Bayer's class and Oliviés class contain exactly the same binary trees.     

基于区分矩阵的启发式属性约简算法

由于大量等价类元素的存在,同一等价类中的记录与其他非该等价类中的记录相比较将会产生大量空元素及重复元素,使得构造区分矩阵需要耗费大量的时间与空间。因此以信息向量为工具处理等价类,改进了区分矩阵的构造过程,有效地提高了构造区分矩阵的时空间效率;其次,利用属性频度为启发信息,给出了一种基于区分矩阵的启发式属性约简算法;最后,利用恒星天体光谱数据集,实验验证了算法的有效性。     

Fast approximate matching of binary codes with distinctive bits

Although the distance between binary codes can be computed fast in Hamming space, linear search is not practical for large scale datasets. Therefore attention has been paid to the efficiency of performing approximate nearest neighbor search, in which hierarchical clustering trees (HCT) are widely used. However, HCT select cluster centers randomly and build indexes with the entire binary code, this degrades search performance. In this paper, we first propose a new clustering algorithm, which chooses cluster centers on the basis of relative distances and uses a more homogeneous partition of the dataset than HCT has to build the hierarchical clustering trees. Then, we present an algorithm to compress binary codes by extracting distinctive bits according to the standard deviation of each bit. Consequently, a new index is proposed using compressed binary codes based on hierarchical decomposition of binary spaces. Experiments conducted on reference datasets and a dataset of one billion binary codes demonstrate the effectiveness and efficiency of our method.     

A heuristic method for learning Bayesian networks using discrete particle swarm optimization

Bayesian networks are a powerful approach for representing and reasoning under conditions of uncertainty. Many researchers aim to find good algorithms for learning Bayesian networks from data. And the heuristic search algorithm is one of the most effective algorithms. Because the number of possible structures grows exponentially with the number of variables, learning the model structure from data by considering all possible structures exhaustively is infeasible. PSO (particle swarm optimization), a powerful optimal heuristic search algorithm, has been applied in various fields. Unfortunately, the classical PSO algorithm only operates in continuous and real-valued space, and the problem of Bayesian networks learning is in discrete space. In this paper, two modifications of updating rules for velocity and position are introduced and a Bayesian networks learning based on binary PSO is proposed. Experimental results show that it is more efficient because only fewer generations are needed to obtain optimal Bayesian networks structures. In the comparison, this method outperforms other heuristic methods such as GA (genetic algorithm) and classical binary PSO.     

Optimal binary search trees with costs depending on the access paths

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n^k+2) and O(n^k+1), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.     

Unbiased split selection for classification trees based on the Gini Index

Classification trees are a popular tool in applied statistics because their heuristic search approach based on impurity reduction is easy to understand and the interpretation of the output is straightforward. However, all standard algorithms suffer from a major problem: variable selection based on standard impurity measures as the Gini Index is biased. The bias is such that, e.g., splitting variables with a high amount of missing values—even if missing completely at random (MCAR)—are artificially preferred. A new split selection criterion that avoids variable selection bias is introduced. The exact distribution of the maximally selected Gini gain is derived by means of a combinatorial approach and the resulting p-value is suggested as an unbiased split selection criterion in recursive partitioning algorithms. The efficiency of the method is demonstrated in simulation studies and a real data study from veterinary gynecology in the context of binary classification and continuous predictor variables with different numbers of missing values. The proposed method is extendible to categorical and ordinal predictor variables and to other split selection criteria such as the cross-entropy.     

基于BDD的增量启发式搜索

增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法--BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.     

Bounds on Threshold Probabilities for Coloring Properties of Random Hypergraphs

We study the threshold probability for the property of existence of a special-form \(r\)?-?coloring for a random \(k\)?-?uniform hypergraph in the \(H(n,k,p)\) binomial model. A parametric set of \(j\)?-?chromatic numbers of a random hypergraph is considered. A coloring of hypergraph vertices is said to be \(j\)?-?proper if every edge in it contains no more than \(j\) vertices of each color. We analyze the question of finding the sharp threshold probability of existence of a \(j\)?-?proper \(r\)?-?coloring for \(H(n,k,p)\). Using the second moment method, we obtain rather tight bounds for this probability provided that \(k\) and \(j\) are large as compared to \(r\).

     

Embedding All Binary Trees in the Hypercube

An O(N²) heuristic algorithm is presented that embeds all binary trees, with dilation 2 and small average dilation, into the optimal-sized hypercube. The heuristic relies on a conjecture about all binary trees containing a perfect matching. It provides a practical and robust technique for mapping binary trees into the hypercube and ensures that the communication load is evenly distributed across the network assuming any shortest path routing strategy. One contribution of this work is the identification of a rich collection of binary trees that can be easily mapped into the hypercube.     

基于最小k 近邻错分率编码确定方法及其在多类分类中的应用

构造输出编码矩阵是将多类分类问题分解为多个两类分类问题的有效方法之一,如何判断一个编码阵的好坏是此类问题的关键．提出以最小庇近邻错分率作为评价标准,把构造问题简化为一个搜索问题．在M类的所有二类划分空间中,通过行交换规则和有限启发式搜索策略搜索出南近邻错分率最小的l个二类划分,并依据编码规则得到最终输出编码矩阵．实验中用人工数据集和UCI数据集分别测试,通过与几种经典的编码方法比较,结果表明该编码方法能在编码长度较小情况下得到更好的分类效果．     

Finding optimal solutions to the graph partitioning problem with heuristic search

As search spaces become larger and as problems scale up, an efficient way to speed up the search is to use a more accurate heuristic function. A better heuristic function might be obtained by the following general idea. Many problems can be divided into a set of subproblems and subgoals that should be achieved. Interactions and conflicts between unsolved subgoals of the problem might provide useful knowledge which could be used to construct an informed heuristic function. In this paper we demonstrate this idea on the graph partitioning problem (GPP). We first show how to format GPP as a search problem and then introduce a sequence of admissible heuristic functions estimating the size of the optimal partition by looking into different interactions between vertices of the graph. We then optimally solve GPP with these heuristics. Experimental results show that our advanced heuristics achieve a speedup of up to a number of orders of magnitude. Finally, we experimentally compare our approach to other states of the art graph partitioning optimal solvers on a number of classes of graphs. The results obtained show that our algorithm outperforms them in many cases.     

Large Deviations for the Weighted Height of an Extended Class of Trees

We use large deviations to prove a general theorem on the asymptotic edge-weighted height H_n^* of a large class of random trees for which H_n^* ∼ c log n for some positive constant c. A graphical interpretation is also given for the limit constant c. This unifies what was already known for binary search trees, random recursive trees and plane oriented trees for instance. New applications include the heights of some random lopsided trees and of the intersection of random trees.