1,721,108 research outputs found
Perfect Strategies for the Ulam-Rényi Game with Multi-interval Questions
No full textWe study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious.
In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k > 0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions
Fault-Tolerant Search Algorithms
No full textSearching is one of the fundamental problems in computer science. Time and again algorithmic and combinatorial issues originally studied in the context of search find application in the most diverse areas of computer science and discrete mathematics. On the other hand, fault-tolerance is a necessary ingredient of computing. Due to their inherent complexity, information systems are naturally prone to errors, which may appear at any level – as imprecisions in the data, bugs in the software, or transient or permanent hardware failures. This book provides a concise, rigorous and up-to-date account of different approaches to fault-tolerance in the context of algorithmic search theory
Supermodularity and Subadditivity Properties of the Entropy on the Majorization Lattice
No full textWe prove that the entropy is a supermodular and subadditive function on the lattice of all n-dimensional probability distributions, ordered according to the partial order relation defined by majorization among vectors
An Interesting Property of Random Forest Distances with Respect to the Curse of Dimensionality
No full textRandom forest distances represent a powerful class of data-dependent similarity measures whose usefulness has been shown in many different scenarios. In this paper, we discuss an interesting property of these measures with respect to the curse of dimensionality, i.e., the set of problems that may arise when the feature space is too large with respect to the number of available objects. Starting from a recent theoretical characterization of two RF-distances defined on an ensemble of Extremely Randomized Trees (ERT), we provide some empirical evidence that such distances are indeed robust to the curse of dimensionality, improving their performances when increasing the dimensionality of the space. Further, we empirically show that this behavior is not restricted to the ERT-based RF-distances, but in general, it also holds with alternative training schemes
Computing Random Forest-distances in the presence of missing data
No full textIn this article, we study the problem of computing Random Forest-distances in the presence of missing data. We present a general framework which avoids pre-imputation and uses in an agnostic way the information contained in the input points. We centre our investigation on RatioRF, an RF-based distance recently introduced in the context of clustering and shown to outperform most known RF-based distance measures. We also show that the same framework can be applied to several other state-of-the-art RF-based measures and provide their extensions to the missing data case. We provide significant empirical evidence of the effectiveness of the proposed framework, showing extensive experiments with RatioRF on 15 datasets. Finally, we also positively compare our method with many alternative literature distances, which can be computed with missing values
A Fuzzy Evolutionary Approach to the Classification Problem
No full textGenetic algorithms are powerful and robust heuristic adaptation procedures suggested by biological evolution and molecular genetics. Fuzzy set theory and fuzzy logic have been proposed in order to provide some means for representing and manipulating imprecision and vagueness. In this paper genetic algorithms and fuzzy logic are combined in a uniform framework suitable for fuzzy classification. We discuss how a fuzzy classification methodology introduced in previous papers has been improved by becoming part of a genetic algorithm. The resulting genetic fuzzy classification technique shows increased sensitivity of solution, avoids the effect of fuzzy numbers grouping and allows for more effective search over solution space
- …
