Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

Inference in hybrid Bayesian networks with mixtures of truncated exponentials

Mixtures of truncated exponentials (MTE) potentials are an alternative to discretization for solving hybrid Bayesian networks. Any probability density function (PDF) can be approximated with an MTE potential, which can always be marginalized in closed form. This allows propagation to be done exactly using the Shenoy–Shafer architecture for computing marginals, with no restrictions on the construction of a join tree. This paper presents MTE potentials that approximate an arbitrary normal PDF with any mean and a positive variance. The properties of these MTE potentials are presented, along with examples that demonstrate their use in solving hybrid Bayesian networks. Assuming that the joint density exists, MTE potentials can be used for inference in hybrid Bayesian networks that do not fit the restrictive assumptions of the conditional linear Gaussian (CLG) model, such as networks containing discrete nodes with continuous parents.     

On top-down splaying

The splay tree is a self-adjusting binary search tree which has a good amortized performance. This paper studies some properties of top-down splay trees. Different ways to charge for the primitive operations of top-down splaying are discussed. We also give some empirical results concerning the behaviour of different top-down restructuring algorithms.This work was supported by the Academy of Finland.     

A survey of fuzzy decision tree classifier

Decision-tree algorithm provides one of the most popular methodologies for symbolic knowledge acquisition. The resulting knowledge, a symbolic decision tree along with a simple inference mechanism, has been praised for comprehensibility. The most comprehensible decision trees have been designed for perfect symbolic data. Over the years, additional methodologies have been investigated and proposed to deal with continuous or multi-valued data, and with missing or noisy features. Recently, with the growing popularity of fuzzy representation, some researchers have proposed to utilize fuzzy representation in decision trees to deal with similar situations. This paper presents a survey of current methods for Fuzzy Decision Tree (FDT) designment and the various existing issues. After considering potential advantages of FDT classifiers over traditional decision tree classifiers, we discuss the subjects of FDT including attribute selection criteria, inference for decision assignment and stopping criteria. To be best of our knowledge, this is the first overview of fuzzy decision tree classifier.     

基于输入-输出数据的概率分布和数字特征

利用模糊推理建立了一种基于输入-输出数据构造联合概率密度函数的方法.首先,将一组单输入-单输出数据转换成模糊推理规则,通过选择适当的模糊蕴涵算子生成模糊关系,再利用这种模糊关系求出二维随机变量的联合概率密度函数.当将模糊蕴涵分别取为Larsen蕴涵和Mamdani蕴涵时,分别得到了两种具体的概率密度函数(称之为Lars...     

Power and reversal power links for binary regressions: An application for motor insurance policyholders

In binary regression, symmetric links such as logit and probit are usually considered as standard. However, in the presence of unbalancing of ones and zeros, these links can be inappropriate and inflexible to fit the skewness in the response curve and likely to lead to misspecification. This is the case of covering some type of insurance, where it can be observed that the probability of a given binary response variable approaches zero at different rates than it approaches one. Furthermore, when usual links are considered, there is not a skewness parameter associated with the distribution chosen that, regardless of the linear predictor, is easily interpreted. In order to overcome such problems, a proposal for the construction of a set of new skew links is developed in this paper, where some of their properties are discussed. In this context, power links and their reversal versions are presented. A Bayesian inference approach using MCMC is developed for the presented models. The methodology is illustrated considering a sample of motor insurance policyholders selected randomly by gender. Results suggest that the proposed link functions are more appropriate than other alternative link functions commonly used in the literature. Copyright © 2016 John Wiley & Sons, Ltd.     

Limit laws for the Randić index of random binary tree models

We investigate the Randić index of random binary trees under two standard probability models: the one induced by random permutations and the Catalan (uniform). In both cases the mean and variance are computed by recurrence methods and shown to be asymptotically linear in the size of the tree. The recursive nature of binary search trees lends itself in a natural way to application of the contraction method, by which a limit distribution (for a suitably normalized version of the index) is shown to be Gaussian. The Randić index (suitably normalized) is also shown to be normally distributed in binary Catalan trees, but the methodology we use for this derivation is singularity analysis of formal generating functions.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

Learning recursive probability trees from probabilistic potentials

A Recursive Probability Tree (RPT) is a data structure for representing the potentials involved in Probabilistic Graphical Models (PGMs). This structure is developed with the aim of capturing some types of independencies that cannot be represented with previous structures. This capability leads to improvements in memory space and computation time during inference. This paper describes a learning algorithm for building RPTs from probability distributions. The experimental analysis shows the proper behavior of the algorithm: it produces RPTs encoding good approximations of the original probability distributions.     

基于输入-输出数据的重心法模糊系统及其泛逼近性

研究基于输入-输出数据的重心法模糊系统及其泛逼近性.首先,将一组单输入-单榆出数据转换成模糊推理规则,通过选择适当的模糊蕴涵算子生成模糊关系,再利用这种模糊关系求出二雄随机变量的联合概率密度函数.当将模糊蕴涵分别取为Larsen蕴涵和Mamdani蕴涵时,分别得到了两种具体的概率密度函数(称之为Larsen分布和Mamdani分布).其次,利用这两种概率分布.分别求出了对应的两种回归函数,指出这种回归函数实际上是模糊控制中的重心法模糊系统.我们分别给出了这种模糊系统具有泛逼近性的充分条件.从而进一步揭示了模糊系统的概率论意义.     

Non-impeding noisy-AND tree causal models over multi-valued variables

To specify a Bayesian network (BN), a conditional probability table (CPT), often of an effect conditioned on its n causes, must be assessed for each node. Its complexity is generally exponential in n. Noisy-OR and a number of extensions reduce the complexity to linear, but can only represent reinforcing causal interactions. Non-impeding noisy-AND (NIN-AND) trees are the first causal models that explicitly express reinforcement, undermining, and their mixture. Their acquisition has a linear complexity, in terms of both the number of parameters and the size of the tree topology. As originally proposed, however, they allow only binary effects and causes. This work generalizes binary NIN-AND tree models to multi-valued effects and causes. It is shown that the generalized NIN-AND tree models express reinforcement, undermining, and their mixture at multiple levels, relative to each active value of the effect. The model acquisition is still efficient. For binary variables, they degenerate into binary NIN-AND tree models. Hence, this contribution enables CPTs of discrete BNs of arbitrary variables (binary or multi-valued) to be specified efficiently through the intuitive concepts of reinforcement and undermining.     

Parallelized phylogenetic post-analysis on multi-core architectures

Bioinformatics is experiencing a rapid and overwhelming accumulation of molecular sequence data, predominantly driven by novel wet-lab sequencing techniques. This trend poses scalability challenges for tool developers. In the field of phylogenetic inference (reconstruction of evolutionary trees from molecular sequence data), scalability is becoming an increasingly important issue for operations other than the tree reconstruction itself. In this paper we focus on post-analysis tasks in reconstructing very large trees, specifically the step of building (extended) majority rule consensus trees from a collection of equally plausible trees or a collection of bootstrap replicate trees. To this end we present non-parallel optimizations which establish our implementation as the fastest exact implementation in phylogenetics, and our novel parallelized routines are the first of their kind. Our non-parallel optimizations achieve a performance improvement of factor 50 compared to the previous version of our code and we achieve a maximum speedup of 5.5 on a 8-core Nehalem node for building consensus trees comprising up to 55,000 organisms. We also present a parallel approach for drawing bootstrap support values on a candidate tree, and experimentally assess our approach in order to better understand read-only versus read–write parallel hash table accesses on multi-core systems.     

Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks

This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy–Shafer architecture to propagate in join trees; the second is exact and is a modification of Rocha and Cozman’s branch-and-bound algorithm, but applied to general directed acyclic graphs.     

Computing upper and lower bounds in interval decision trees

This article presents algorithms for computing optima in decision trees with imprecise probabilities and utilities. In tree models involving uncertainty expressed as intervals and/or relations, it is necessary for the evaluation to compute the upper and lower bounds of the expected values. Already in its simplest form, computing a maximum of expectancies leads to quadratic programming (QP) problems. Unfortunately, standard optimization methods based on QP (and BLP – bilinear programming) are too slow for the evaluation of decision trees in computer tools with interactive response times. Needless to say, the problems with computational complexity are even more emphasized in multi-linear programming (MLP) problems arising from multi-level decision trees. Since standard techniques are not particularly useful for these purposes, other, non-standard algorithms must be used. The algorithms presented here enable user interaction in decision tools and are equally applicable to all multi-linear programming problems sharing the same structure as a decision tree.     

On spectral radii of matrices governing some numerical estimating algorithms with incomplete data

Many estimating procedures are carried out with incomplete data by means of different types of EM algorithms. They allow us to obtain maximum likelihood parameter estimates in classical inference and also estimates based on the posterior mode in Bayesian inference. This paper analyzes in detail the spectral radii of the Jacobian matrices algorithm as a possible way to evaluate convergence rates. The eigenvalues of such matrices are explicitly obtained in some cases and, in all of them, a geometric convergence rate is, at least, guaranteed near the optimum. Finally, a comparison between the leading eigenvalues of EM and direct and approximate EM-Bayes algorithms may suggest the efficiency of each case.     

On spectral radii of matrices governing some numerical estimating algorithms with incomplete data

Summary Many estimating procedures are carried out with incomplete data by means of different types of EM algorithms. They allow us to obtain maximum likelihood parameter estimates in classical inference and also estimates based on the posterior mode in Bayesian inference. This paper analyzes in detail the spectral radii of the Jacobian matrices algorithm as a possible way to evaluate convergence rates. The eigenvalues of such matrices are explicitly obtained in some cases and, in all of them, a geometric convergence rate is, at least, guaranteed near the optimum. Finally, a comparison between the leading eigenvalues of EM and direct and approximate EM-Bayes algorithms may suggest the efficiency of each case.     

Generating a Gray Code for P-Sequences

P-sequences are used for coding binary trees and they are also an alternative representation for well-formed parentheses strings. We present here the first Gray code and loopless generating algorithm for P-sequences, and extend them in a Gray code and a new loopless generating algorithm for well-formed parentheses strings. Ranking and unranking algorithms are also discussed.     

On the complexity of searching game trees and other recursion trees

Game tree searching is one of the fundamental topics in artificial intelligence and decision analysis. The main results of this paper are: (1) A simple nondirectional algorithm for searching binary bi-valued game trees is presented and analysed. For a wide range of parameters s in Schrüfers s-tree model it has a smaller branching factor than directional search. (2) A cascade technique for game tree models with at least four different node values is presented. This technique yields algorithms with smaller branching factors than alpha-beta. (The amount of storage required by the algorithms in (1) and (2) is only linear in the depth of the searched trees.) (3) Recursion trees are defined as a natural generalisation of game trees. A combinatorial lower bound for the complexity of searching symmetric recursion trees is proved. (4) Those recursion trees are characterized which can be searched by pruning techniques.     

Analyzing return asymmetry and quantiles through stochastic volatility models using asymmetric Laplace error via uniform scale mixtures

This paper proposes a new approach to analyze stock return asymmetry and quantiles. We also present a new scale mixture of uniform (SMU) representation for the asymmetric Laplace distribution (ALD). The use of the SMU for a probability distribution is a data augmentation technique that simplifies the Gibbs sampler of the Bayesian Markov chain Monte Carlo algorithms. We consider a stochastic volatility (SV) model with an ALD error distribution. With the SMU representation, the full conditional distribution for some parameters is shown to have closed form. It is also known that the ALD can be used to obtain the coefficients of quantile regression models. This paper also considers a quantile SV model by fixing the skew parameter of the ALD at specific quantile level. Simulation study shows that the proposed methodology works well in both SV and quantile SV models using Bayesian approach. In the empirical study, we analyze index returns of the stock markets in Australia, Japan, Hong Kong, Thailand, and the UK and study the effect of S&P 500 on these returns. The results show the significant return asymmetry in some markets and the influence by S&P 500 in all markets at all quantile levels. Copyright © 2014 John Wiley & Sons, Ltd.