1,721,097 research outputs found
Another proof of a slow convergence result of Birgé
No full textWe give a short proof of the following result. Let fn be any density estimate based upon an i.i.d. sample drawn from a density f. For any monotone decreasing sequence {an} of positive numbers converging to zero with , a density f may be found such that for all n. This density may be picked from the class of densities on [0, 1] that are bounded by two. The proof of this fact simplifies an earlier proof by Birgé (1986) and extends a weaker lower bound by the author (1983).Density estimation Nonparametric estimation Lower bounds Minimax theory Rate of convergence
A tree classifier based on a consistent splitting rule /
No full textTree classifiers partition the feature space into regions based on simple binary decisions called splitting rules. It can be shown that many splitting rules are not universally consistent, meaning that they may not converge to the optimal solution. This thesis introduces a method for growing decision trees grown with a consistent splitting rule, using random jumps and local optimizations to avoid an otherwise computationally expensive task. The tree classifier is tested on synthetic and natural data, showing comparable performance with other machine learning methods. In addition, a new data set is introduced to perform automatic classification of underwater mines from sonar imagery. Features are extracted and performance evaluated using the new splitting rule
A probabilistic min-max tree /
No full textMIN-MAX trees have been studied for thirty years as models of game trees in artificial intelligence. Judea Pearl introduced a popular probabilistic model that assigns random independent and identically distributed values to the leaves. Among the dependent models, incremental models assume that terminal values are computed as sums of edge values on the path from the root to a leaf. We study a special case called the scSUM model where the edge values follow a Bernoulli distribution with mean p. Let be the root's value of a complete b-ary, n-level scSUM tree. We prove the E/n tends to a uniformly continuous function . Surprisingly, is very nonlinear and has some flat parts. More formally, for all b, there exist (0, 1) such that, cases{&:E has a finite limit cr &: has a finite limit cr &:E tends to 1/2 cr} inally and tend to zero when b tends to infinity
A genetic algorithm with self-adaptive niche sizing
No full textOptimization of multimodal functions is hard for traditional optimization techniques. Holland's genetic algorithm combined with the concept of niche and speciation already showed success in such difficult problems. Some implementations of this concept exist, but the effective ones all lack flexibility by requiring either previous knowledge about the function to optimize or by imposing some fixed external schedule of exploration. We present an implementation of this concept using minimum spanning trees that is compared with a previous algorithm on random choices of input parameters. Our proposal does not require any a priori knowledge about the function. Two approaches using the minimum spanning trees are studied, one of which--the biggest proportion method (BPM)--outperforms its competitor on the battery of test problems and shows its capability of automatically adapting to the function to optimize
Recommended from our members
Mini-Workshop: Probability Theory on Trees and Analysis of Algorithms
Get PDF[no abstract available
A probabilistic exploration of the Horton-Strahler number /
No full textIn this Master's thesis, we consider the Horton-Strahler number for various distributions of random binary trees with n nodes. For random equiprobable binary trees with n nodes, we give a new probabilistic proof of the well-known result that E = log n + O(1), and show that for every x 0, bf P} { vert S sb{n} - log sb4 n vert ge x } le {D over 4 sp{x}}, or some constant For random binary tries and Patricia trees constructed from n i.i.d. sequences of independent bits with probability we use fill-up levels to show that lim limits sb{n to infty}} { bf P} left {S sb{n} 0.S sb{n}$. Finally, we discuss the use of the Horton-Strahler number in drawing trees. We illustrate a known algorithm for drawing "realistic-looking" trees and present a new algorithm for drawing "nice-looking" trees, both with PostScript implementations
Optimization of Bézier outlines and automatic font generation
No full textA new method for the approximation of bitmap outlines with Bezier curves is presented in this thesis. This probabilistic approach accurately describes the contours with a small number of continuous splines. The approximation is refined iteratively using a quality function. The evaluation method is based upon the smoothness of the generated outline and the precision at which it interpolates the original contour. Merge operations of adjacent Bezier splines and spline alterations using an adaptive random search technique are employed for finding an optimal solution.A program implementing the proposed algorithm was created and may be used to automatically generate PostScript type 1 fonts. The algorithm has shown to be very stable and to converge rapidly. Many new typefaces have been generated with the software and are shown in this thesis
Analysis of random trees
No full textIn the first part of the thesis, we analyze the expected time complexity of range searching with k-d trees in all dimensions when the data points are uniformly distributed in the unit hypercube. The partial match results of Flajolet and Puech are reproved using elementary probabilistic methods. In addition, we analyze the expected complexity of orthogonal and convex range search, as well as nearest neighbor search. We introduce a new data structure, the squarish k-d tree, in which the longest edge is always cut first. This modification makes the expected time behavior of lower-dimensional partial match queries behave as for perfectly balanced complete k-d trees on n nodes. This is in contrast to a result of Flajolet and Puech, who proved that for (standard) random k-d trees with cuts that rotate among the coordinate axes, the expected time behavior is much worse than for balanced complete k-d trees. We show that the expected complexity for range search and nearest neighbor search for squarish k-d trees is either optimal or near optimal.In the second part, we analyze branch-and-bound search for random b-ary trees. In particular, let Tn be a b-ary tree of height n, that has independent, nonnegative, identically distributed random variables associated with each of its edges. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of Tn. Assume that the edge random variable X is nondegenerate, has E {Xtheta} < infinity for some theta > 2, and satisfies bP{ X = c} < 1 where c is the left-most point of the support of X. We analyze the performance of the standard branch-and-bound algorithm for this problem and prove that the number of nodes visited is in probability (beta + o(1)) n, where beta ∈ (1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for beta are derived. We also show that any search algorithm must visit (beta + o(1))n nodes with probability tending to one, so branch-and-bound is asymptotically optimal where first-order asymptotics are concerned
- …
