Search results for "Tree"
showing 10 items of 1841 documents
A multi-locus inference of the evolutionary diversification of extant flamingos (Phoenicopteridae).
2014
9 pages; International audience; BACKGROUND: Modern flamingos (Phoenicopteridae) occupy a highly specialized ecology unique among birds and represent a potentially powerful model system for informing the mechanisms by which a lineage of birds adapts and radiates. However, despite a rich fossil record and well-studied feeding morphology, molecular investigations of the evolutionary progression among modern flamingos have been limited. Here, using three mitochondrial (mtDNA) markers, we present the first DNA sequence-based study of population genetic variation in the widely distributed Chilean Flamingo and, using two mtDNA and 10 nuclear (nDNA) markers, recover the species tree and divergence…
On the Non-uniform Redundancy in Grammatical Evolution
2016
This paper investigates the redundancy of representation in grammatical evolution (GE) for binary trees. We analyze the entire GE solution space by creating all binary genotypes of predefined length and map them to phenotype trees, which are then characterized by their size, depth and shape. We find that the GE representation is strongly non-uniformly redundant. There are huge differences in the number of genotypes that encode one particular phenotype. Thus, it is difficult for GE to solve problems where the optimal tree solutions are underrepresented. In general, the GE mapping process is biased towards short tree structures, which implies high GE performance if the optimal solution requir…
Cluster-based active learning for compact image classification
2010
In this paper, we consider active sampling to label pixels grouped with hierarchical clustering. The objective of the method is to match the data relationships discovered by the clustering algorithm with the user's desired class semantics. The first is represented as a complete tree to be pruned and the second is iteratively provided by the user. The active learning algorithm proposed searches the pruning of the tree that best matches the labels of the sampled points. By choosing the part of the tree to sample from according to current pruning's uncertainty, sampling is focused on most uncertain clusters. This way, large clusters for which the class membership is already fixed are no longer…
A distance metric on binary trees using lattice-theoretic measures
1990
A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )
Structural difficulty in grammatical evolution versus genetic programming
2013
Genetic programming (GP) has problems with structural difficulty as it is unable to search effectively for solutions requiring very full or very narrow trees. As a result of structural difficulty, GP has a bias towards narrow trees which means it searches effectively for solutions requiring narrow trees. This paper focuses on the structural difficulty of grammatical evolution (GE). In contrast to GP, GE works on variable-length binary strings and uses a grammar in Backus-Naur Form (BNF) to map linear genotypes to phenotype trees. The paper studies whether and how GE is affected by structural difficulty. For the analysis, we perform random walks through the search space and compare the struc…
Efficient lower and upper bounds of the diagonal-flip distance between triangulations
2006
There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.
An efficient upper bound of the rotation distance of binary trees
2000
A polynomial time algorithm is developed for computing an upper bound for the rotation distance of binary trees and equivalently for the diagonal-flip distance of convex polygons triangulations. Ordinal tools are used.
On the Locality of Standard Search Operators in Grammatical Evolution
2014
Offspring should be similar to their parents and inherit their relevant properties. This general design principle of search operators in evolutionary algorithms is either known as locality or geometry of search operators, respectively. It takes a geometric perspective on search operators and suggests that the distance between an offspring and its parents should be less than or equal to the distance between both parents. This paper examines the locality of standard search operators used in grammatical evolution (GE) and genetic programming (GP) for binary tree problems. Both standard GE and GP search operators suffer from low locality since a substantial number of search steps result in an o…
The Myriad Virtues of Wavelet Trees
2009
Wavelet Trees have been introduced in [Grossi, Gupta and Vitter, SODA '03] and have been rapidly recognized as a very flexible tool for the design of compressed full-text indexes and data compressors. Although several papers have investigated the beauty and usefulness of this data structure in the full-text indexing scenario, its impact on data compression has not been fully explored. In this paper we provide a complete theoretical analysis of a wide class of compression algorithms based on Wavelet Trees. We also show how to improve their asymptotic performance by introducing a novel framework, called Generalized Wavelet Trees, that aims for the best combination of binary compressors (like,…
On the Irrelevance of Expected Stock Returns in the Pricing of Options in the Binomial Model: A Pedagogical Note
2005
The option pricing theory is now either a standard or a main part of many financial courses on both intermediate and advanced levels. All the textbooks that include the option pricing theory present a detailed treatment of the binomial model. However, the binomial model, although quite simple and intuitive in appearance, is rather tricky when it comes to its practical implementations and applications. In fact, it is amazing that the students often get totally confused when it finally comes to the issue of the choice of the parameters of the binomial model. The reason for all this confusion lies in the fact that all the textbooks emphasize the irrelevance of the binomial option price from th…