Approximate inference in Bayesian networks using binary probability trees

The present paper introduces a new kind of representation for the potentials in a Bayesian network: Binary Probability Trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees.     

On the spectral theory of trees with finite cone type

We study basic spectral features of graph Laplacians associated with a class of rooted trees which contains all regular trees. Trees in this class can be generated by substitution processes. Their spectra are shown to be purely absolutely continuous and to consist of finitely many bands. The main result gives stability of the absolutely continuous spectrum under sufficiently small radially label symmetric perturbations for non-regular trees in this class. In sharp contrast, the absolutely continuous spectrum can be completely destroyed by arbitrary small radially label symmetric perturbations for regular trees in this class.     

Improved customer choice predictions using ensemble methods

In this paper various ensemble learning methods from machine learning and statistics are considered and applied to the customer choice modeling problem. The application of ensemble learning usually improves the prediction quality of flexible models like decision trees and thus leads to improved predictions. We give experimental results for two real-life marketing datasets using decision trees, ensemble versions of decision trees and the logistic regression model, which is a standard approach for this problem. The ensemble models are found to improve upon individual decision trees and outperform logistic regression.     

The realizability problem for Golovach-type functions

The problem mentioned in the title is stated as follows. Consider a function f with some necessary properties of the Golovach function, namely, a piecewise constant nonincreasing right continuous function defined on the set of nonnegative real numbers and taking integer values such that this function is identically equal to 1 at sufficiently large argument values. The problem of realizing the function f in a class $\mathbb{G}$ of topological graphs is to find a graph $G \in \mathbb{G}$ such that its Golovach functions coincides with f. Examples of realization of some functions possessing the properties mentioned above are considered. In the simplest case, all graphs for which the function can be realized are described. For less trivial examples, realizability criteria for functions with the properties of the Golovach function in the class of trees and in the class of trees with given edge search number which have the least number of edges are presented.     

Maximizing the number of independent subsets over trees with bounded degree

The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has already been investigated by many authors. In view of the applications of this graph parameter, trees of restricted degree are of particular interest. In the current article, we give a characterization of the trees with given maximum degree which maximize the number of independent subsets, and show that these trees also minimize the number of independent edge subsets. The structure of these trees is quite interesting and unexpected: it can be described by means of a novel digital system—in the case of maximum degree 3, we obtain a binary system using the digits 1 and 4. The proof mainly depends on an exchange lemma for branches of a tree. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 49–68, 2008     

Machine-learning classifiers for imbalanced tornado data

Learning from imbalanced data, where the number of observations in one class is significantly larger than the ones in the other class, has gained considerable attention in the machine learning community. Assuming the difficulty in predicting each class is similar, most standard classifiers will tend to predict the majority class well. This study applies tornado data that are highly imbalanced, as they are rare events. The severe weather data used herein have thunderstorm circulations (mesocyclones) that produce tornadoes in approximately 6.7 % of the total number of observations. However, since tornadoes are high impact weather events, it is important to predict the minority class with high accuracy. In this study, we apply support vector machines (SVMs) and logistic regression with and without a midpoint threshold adjustment on the probabilistic outputs, random forest, and rotation forest for tornado prediction. Feature selection with SVM-recursive feature elimination was also performed to identify the most important features or variables for predicting tornadoes. The results showed that the threshold adjustment on SVMs provided better performance compared to other classifiers.     

Cooperative study teams in mathematics classrooms

This article describes a general instructional strategy designed to help students in the learning process from textbooks and to furnish opportunities for practice in critical reading. Students participate in cooperative learning by breaking the class up into small groups—the Study Teams—and providing them with worksheets and reading organizers, which organize the material into small items that reflect the major concepts in the reading material on which the study is focused. Some of the benefits that this type of instruction with Study Teams can produce are described.     

An ensemble method using credal decision trees

Supervised classification learning can be considered as an important tool for decision support. In this paper, we present a method for supervised classification learning, which ensembles decision trees obtained via convex sets of probability distributions (also called credal sets) and uncertainty measures. Our method forces the use of different decision trees and it has mainly the following characteristics: it obtains a good percentage of correct classifications and an improvement in time of processing compared with known classification methods; it not needs to fix the number of decision trees to be used; and it can be parallelized to apply it on very large data sets.     

The Long-Eight-Figure Spines of Lens Spaces and Binary Trees

There is a conjecture that the long-eight-figure spines of lens spaces are minimal in the class of almost special spines. In the work the embedding of these spines into the lens spaces with respect to the lenses' natural presentations is described effectively via flypes of binary trees.     

Optimal binary split trees

Split trees are a technique for storing records with fixed frequency distributions. It was previously believed that no polynomial time algorithms to construct optimal representations of split trees were likely (B. A. Sheil, Median split trees: A fast lookup technique for frequently occurring keys, Comm. ACM (1978), p.949). In this paper we present an O(n⁵) algorithm to construct optimal binary split trees. Other efficient algorithms to construct suboptimal split trees are also discussed. The definition of split trees is later generalized to a larger class of trees so that we can compare several important classes of trees.     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

Bayesian MAP model selection of chain event graphs

Chain event graphs are graphical models that while retaining most of the structural advantages of Bayesian networks for model interrogation, propagation and learning, more naturally encode asymmetric state spaces and the order in which events happen than Bayesian networks do. In addition, the class of models that can be represented by chain event graphs for a finite set of discrete variables is a strict superset of the class that can be described by Bayesian networks. In this paper we demonstrate how with complete sampling, conjugate closed form model selection based on product Dirichlet priors is possible, and prove that suitable homogeneity assumptions characterise the product Dirichlet prior on this class of models. We demonstrate our techniques using two educational examples.     

On the Wiener index of random trees

By a theorem of Janson, the Wiener index of a random tree from a simply generated family of trees converges in distribution to a limit law that can be described in terms of the Brownian excursion. The family of unlabelled trees (rooted or unrooted), which is perhaps the most natural one from a graph-theoretical point of view, since isomorphisms are taken into account, is not covered directly by this theorem though. The aim of this paper is to show how one can prove the same limit law for unlabelled trees by means of generating functions and the method of moments.     

Technologies for teaching and learning trend in bivariate data

Research on technology-use for teaching and learning statistics is sparse compared to that in algebra and calculus. This paper addresses the deficiency with regard to teaching and learning about ‘trend’ in bivariate data. Available research findings are reviewed and an empirical inquiry in a year 12 (upper secondary) class is reported. Treatment of a single dataset by the class is described. Spreadsheet, graphics calculator and projection technologies were utilized. The main conclusions are that the dataset that the teacher downloaded from the internet supported well the identification of trend and variability and testing alternative models; and the spreadsheet graphs that were projected onto the whiteboard mediated class discussion favourably.     

Lambda pruning: an approximation of the string subsequence kernel for practical SVM classification and redundancy clustering

The support vector machine (SVM) is a powerful learning algorithm, e.g., for classification and clustering tasks, that works even for complex data structures such as strings, trees, lists and general graphs. It is based on the usage of a kernel function for measuring scalar products between data units. For analyzing string data Lodhi et al. (J Mach Learn Res 2:419–444, 2002) have introduced a String Subsequence kernel (SSK). In this paper we propose an approximation to SSK based on dropping higher orders terms (i.e., subsequences which are spread out more than a certain threshold) that reduces the computational burden of SSK. As we are also concerned with practical application of complex kernels with high computational complexity and memory consumption, we provide an empirical model to predict runtime and memory of the approximation as well as the original SSK, based on easily measurable properties of input data. We provide extensive results on the properties of the proposed approximation, SSK-LP, with respect to prediction accuracy, runtime and memory consumption. Using some real-life datasets of text mining tasks, we show that models based on SSK and SSK-LP perform similarly for a set of real-life learning tasks, and that the empirical runtime model is also useful in roughly determining total learning time for a SVM using either kernel.     

非线性时间序列的投影寻踪学习网络逼近

本文研究非线性自回归模型投影寻踪学习网络逼近的收敛性,证明了在L^k(k为正整数）空间上,投影寻踪学习网络可以以任意精度逼近非线性自回归模型,给出基于投影寻踪学习网络的非线性时间序列模型建模和预报的计算方法和应用实例,对太阳黑子数据,山猫数据及西安数据进行了拟合和预报,将其结果与改进BP网和门限自回归模型相应的结果进行比较,结果表明基于投影寻踪学习网络的非线性时间序列的建模预报方法是一类行之有效的方法。     

Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif

A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees.     

Clique trees of chordal graphs: leafage and 3-asteroidals

Chordal graphs were characterized as those graphs having a tree, called clique tree, whose vertices are the cliques of the graph and for every vertex in the graph, the set of cliques that contain it form a subtree of clique tree. In this work, we study the relationship between the clique trees of a chordal graph and its subgraphs. We will prove that clique trees can be described locally and all clique trees of a graph can be obtained from clique trees of subgraphs. In particular, we study the leafage of chordal graphs, that is the minimum number of leaves among the clique trees of the graph. It is known that interval graphs are chordal graphs without 3-asteroidals. We will prove a generalization of this result using the framework developed in the present article. We prove that in a clique tree that realizes the leafage, for every vertex of degree at least 3, and every choice of 3 branches incident to it, there is a 3−asteroidal in these branches.     

Boolean autoencoders and hypercube clustering complexity

We introduce and study the properties of Boolean autoencoder circuits. In particular, we show that the Boolean autoencoder circuit problem is equivalent to a clustering problem on the hypercube. We show that clustering m binary vectors on the n-dimensional hypercube into k clusters is NP-hard, as soon as the number of clusters scales like ${m^\epsilon (\epsilon >0 )}$ , and thus the general Boolean autoencoder problem is also NP-hard. We prove that the linear Boolean autoencoder circuit problem is also NP-hard, and so are several related problems such as: subspace identification over finite fields, linear regression over finite fields, even/odd set intersections, and parity circuits. The emerging picture is that autoencoder optimization is NP-hard in the general case, with a few notable exceptions including the linear cases over infinite fields or the Boolean case with fixed size hidden layer. However learning can be tackled by approximate algorithms, including alternate optimization, suggesting a new class of learning algorithms for deep networks, including deep networks of threshold gates or artificial neurons.