Unbiased Recursive Partitioning: A Conditional Inference Framework

Recursive binary partitioning is a popular tool for regression analysis. Two fundamental problems of exhaustive search procedures usually applied to fit such models have been known for a long time: overfitting and a selection bias towards covariates with many possible splits or missing values. While pruning procedures are able to solve the overfitting problem, the variable selection bias still seriously affects the interpretability of tree-structured regression models. For some special cases unbiased procedures have been suggested, however lacking a common theoretical foundation. We propose a unified framework for recursive partitioning which embeds tree-structured regression models into a well defined theory of conditional inference procedures. Stopping criteria based on multiple test procedures are implemented and it is shown that the predictive performance of the resulting trees is as good as the performance of established exhaustive search procedures. It turns out that the partitions and therefore the models induced by both approaches are structurally different, confirming the need for an unbiased variable selection. Moreover, it is shown that the prediction accuracy of trees with early stopping is equivalent to the prediction accuracy of pruned trees with unbiased variable selection. The methodology presented here is applicable to all kinds of regression problems, including nominal, ordinal, numeric, censored as well as multivariate response variables and arbitrary measurement scales of the covariates. Data from studies on glaucoma classification, node positive breast cancer survival and mammography experience are re-analyzed.     

Hierarchical linear regression models for conditional quantiles

The quantile regression has several useful features and therefore is gradually developing into a comprehensive approach to the statistical analysis of linear and nonlinear response models, but it cannot deal effectively with the data with a hierarchical structure. In practice, the existence of such data hierarchies is neither accidental nor ignorable, it is a common phenomenon. To ignore this hierarchical data structure risks overlooking the importance of group effects, and may also render many of the traditional statistical analysis techniques used for studying data relationships invalid. On the other hand, the hierarchical models take a hierarchical data structure into account and have also many applications in statistics, ranging from overdispersion to constructing min-max estimators. However, the hierarchical models are virtually the mean regression, therefore, they cannot be used to characterize the entire conditional distribution of a dependent variable given high-dimensional covariates. Furthermore, the estimated coefficient vector (marginal effects) is sensitive to an outlier observation on the dependent variable. In this article, a new approach, which is based on the Gauss-Seidel iteration and taking a full advantage of the quantile regression and hierarchical models, is developed. On the theoretical front, we also consider the asymptotic properties of the new method, obtaining the simple conditions for an n1/2-convergence and an asymptotic normality. We also illustrate the use of the technique with the real educational data which is hierarchical and how the results can be explained.     

Joint semiparametric mean-covariance model in longitudinal study

Semiparametric regression models and estimating covariance functions are very useful for longitudinal study. To heed the positive-definiteness constraint, we adopt the modified Cholesky decomposition approach to decompose the covariance structure. Then the covariance structure is fitted by a semiparametric model by imposing parametric within-subject correlation while allowing the nonparametric variation function. We estimate regression functions by using the local linear technique and propose generalized es...     

Wavelet-Based Weighted LASSO and Screening Approaches in Functional Linear Regression

One useful approach for fitting linear models with scalar outcomes and functional predictors involves transforming the functional data to wavelet domain and converting the data-fitting problem to a variable selection problem. Applying the LASSO procedure in this situation has been shown to be efficient and powerful. In this article, we explore two potential directions for improvements to this method: techniques for prescreening and methods for weighting the LASSO-type penalty. We consider several strategies for each of these directions which have never been investigated, either numerically or theoretically, in a functional linear regression context. We compare the finite-sample performance of the proposed methods through both simulations and real-data applications with both 1D signals and 2D image predictors. We also discuss asymptotic aspects. We show that applying these procedures can lead to improved estimation and prediction as well as better stability. Supplementary materials for this article are available online.     

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 distributionally robust multiperiod stochastic optimization

This paper considers model uncertainty for multistage stochastic programs. The data and information structure of the baseline model is a tree, on which the decision problem is defined. We consider “ambiguity neighborhoods” around this tree as alternative models which are close to the baseline model. Closeness is defined in terms of a distance for probability trees, called the nested distance. This distance is appropriate for scenario models of multistage stochastic optimization problems as was demonstrated in Pflug and Pichler (SIAM J Optim 22:1–23, 2012). The ambiguity model is formulated as a minimax problem, where the the optimal decision is to be found, which minimizes the maximal objective function within the ambiguity set. We give a setup for studying saddle point properties of the minimax problem. Moreover, we present solution algorithms for finding the minimax decisions at least asymptotically. As an example, we consider a multiperiod stochastic production/inventory control problem with weekly ordering. The stochastic scenario process is given by the random demands for two products. We determine the minimax solution and identify the worst trees within the ambiguity set. It turns out that the probability weights of the worst case trees are concentrated on few very bad scenarios.     

The role of local partial independence in learning of Bayesian networks

Bayesian networks are one of the most widely used tools for modeling multivariate systems. It has been demonstrated that more expressive models, which can capture additional structure in each conditional probability table (CPT), may enjoy improved predictive performance over traditional Bayesian networks despite having fewer parameters. Here we investigate this phenomenon for models of various degree of expressiveness on both extensive synthetic and real data. To characterize the regularities within CPTs in terms of independence relations, we introduce the notion of partial conditional independence (PCI) as a generalization of the well-known concept of context-specific independence (CSI). To model the structure of the CPTs, we use different graph-based representations which are convenient from a learning perspective. In addition to the previously studied decision trees and graphs, we introduce the concept of PCI-trees as a natural extension of the CSI-based trees. To identify plausible models we use the Bayesian score in combination with a greedy search algorithm. A comparison against ordinary Bayesian networks shows that models with local structures in general enjoy parametric sparsity and improved out-of-sample predictive performance, however, often it is necessary to regulate the model fit with an appropriate model structure prior to avoid overfitting in the learning process. The tree structures, in particular, lead to high quality models and suggest considerable potential for further exploration.     

Automatically replacing indices into parallel arrays with pointers to records

In older languages lists, trees and graphs are represented with sets of arrays where indices of elements correspond to pointers to the nodes of the data structure. We present an algorithm that replaces such arrays with objects allocated dynamically from the heap, and indices with true pointers. Generated pointers are strongly typed and elements of logically related arrays are combined into records. The algorithm is potentially useful, especially in automatic translation between high-level programming languages.     

Bayesian Ensemble Trees (BET) for Clustering and Prediction in Heterogeneous Data

We propose a novel “tree-averaging” model that uses the ensemble of classification and regression trees (CART). Each constituent tree is estimated with a subset of similar data. We treat this grouping of subsets as Bayesian ensemble trees (BET) and model them as a Dirichlet process. We show that BET determines the optimal number of trees by adapting to the data heterogeneity. Compared with the other ensemble methods, BET requires much fewer trees and shows equivalent prediction accuracy using weighted averaging. Moreover, each tree in BET provides variable selection criterion and interpretation for each subset. We developed an efficient estimating procedure with improved estimation strategies in both CART and mixture models. We demonstrate these advantages of BET with simulations and illustrate the approach with a real-world data example involving regression of lung function measurements obtained from patients with cystic fibrosis. Supplementary materials for this article are available online.     

Term Structure Models in Multistage Stochastic Programming: Estimation and Approximation

This paper investigates some common interest rate models for scenario generation in financial applications of stochastic optimization. We discuss conditions for the underlying distributions of state variables which preserve convexity of value functions in a multistage stochastic program. One- and multi-factor term structure models are estimated based on historical data for the Swiss Franc. An analysis of the dynamic behavior of interest rates generated with these models reveals several deficiencies which have an impact on the performance of investment policies derived from the stochastic program. While barycentric approximation is used here for the generation of scenario trees, these insights may be generalized to other discretization techniques as well.     

Structure of the Loday–Ronco Hopf algebra of trees

Loday and Ronco defined an interesting Hopf algebra structure on the linear span of the set of planar binary trees. They showed that the inclusion of the Hopf algebra of non-commutative symmetric functions in the Malvenuto–Reutenauer Hopf algebra of permutations factors through their Hopf algebra of trees, and these maps correspond to natural maps from the weak order on the symmetric group to the Tamari order on planar binary trees to the boolean algebra.We further study the structure of this Hopf algebra of trees using a new basis for it. We describe the product, coproduct, and antipode in terms of this basis and use these results to elucidate its Hopf-algebraic structure. In the dual basis for the graded dual Hopf algebra, our formula for the coproduct gives an explicit isomorphism with a free associative algebra. We also obtain a transparent proof of its isomorphism with the non-commutative Connes–Kreimer Hopf algebra of Foissy, and show that this algebra is related to non-commutative symmetric functions as the (commutative) Connes–Kreimer Hopf algebra is related to symmetric functions.     

No-arbitrage conditions,scenario trees,and multi-asset financial optimization

Many numerical optimization methods use scenario trees as a discrete approximation for the true (multi-dimensional) probability distributions of the problem’s random variables. Realistic specifications in financial optimization models can lead to tree sizes that quickly become computationally intractable. In this paper we focus on the two main approaches proposed in the literature to deal with this problem: scenario reduction and state aggregation. We first state necessary conditions for the node structure of a tree to rule out arbitrage. However, currently available scenario reduction algorithms do not take these conditions explicitly into account. State aggregation excludes arbitrage opportunities by relying on the risk-neutral measure. This is, however, only appropriate for pricing purposes but not for optimization. Both limitations are illustrated by numerical examples. We conclude that neither of these methods is suitable to solve financial optimization models in asset–liability or portfolio management.     

Visualization of Multivariate Density Estimates With Level Set Trees

This article presents a method for visualization of multivariate functions. The method is based on a tree structure—called the level set tree—built from separated parts of level sets of a function. The method is applied for visualization of estimates of multivarate density functions. With different graphical representations of level set trees we may visualize the number and location of modes, excess masses associated with the modes, and certain shape characteristics of the estimate. Simulation examples are presented where projecting data to two dimensions does not help to reveal the modes of the density, but with the help of level set trees one may detect the modes. I argue that level set trees provide a useful method for exploratory data analysis.     

Logit tree models for discrete choice data with application to advice-seeking preferences among Chinese Christians

Logit models are popular tools for analyzing discrete choice and ranking data. The models assume that judges rate each item with a measurable utility, and the ordering of a judge’s utilities determines the outcome. Logit models have been proven to be powerful tools, but they become difficult to interpret if the models contain nonlinear and interaction terms. We extended the logit models by adding a decision tree structure to overcome this difficulty. We introduced a new method of tree splitting variable selection that distinguishes the nonlinear and linear effects, and the variable with the strongest nonlinear effect will be selected in the view that linear effect is best modeled using the logit model. Decision trees built in this fashion were shown to have smaller sizes than those using loglikelihood-based splitting criteria. In addition, the proposed splitting methods could save computational time and avoid bias in choosing the optimal splitting variable. Issues on variable selection in logit models are also investigated, and forward selection criterion was shown to work well with logit tree models. Focused on ranking data, simulations are carried out and the results showed that our proposed splitting methods are unbiased. Finally, to demonstrate the feasibility of the logit tree models, they were applied to analyze two datasets, one with binary outcome and the other with ranking outcome.     

Qualitative inequalities for squared partial correlations of a Gaussian random vector

We describe various sets of conditional independence relationships, sufficient for qualitatively comparing non-vanishing squared partial correlations of a Gaussian random vector. These sufficient conditions are satisfied by several graphical Markov models. Rules for comparing degree of association among the vertices of such Gaussian graphical models are also developed. We apply these rules to compare conditional dependencies on Gaussian trees. In particular for trees, we show that such dependence can be completely characterised by the length of the paths joining the dependent vertices to each other and to the vertices conditioned on. We also apply our results to postulate rules for model selection for polytree models. Our rules apply to mutual information of Gaussian random vectors as well.     

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.     

Network analysis: Understanding consumers' choice in the film industry and predicting pre‐released weekly box‐office revenue

Predicting weekly box‐office demand is an important yet challenging question. For theater exhibitors, such information will enhance negotiation options with distributers, and assist in planning weekly movie portfolio mix. Existing literature focuses on forecasts of pre‐released total gross revenue or on weekly predictions based on first‐weeks observations. This work adds to the literature in modeling the entire demand structure forecasts by utilizing information on movie similarity network. Specifically, we draw upon the assumption that aggregated consumers' choice in the film industry is the main key in understanding movies' demand. Therefore, similar movies, in terms of audience appeal, should yield similar demand structure. In this work, we propose an automated technique that derives measurements of demand structure. We demonstrate that our technique enables to analyze different aspects of demand structure, namely, decay rate, time of first demand peak, per‐screen gross value at peak time, existence of second demand wave, and time on screens. We deploy ideas from variable selection procedures, to investigate the prediction power of similarity network on demand dynamics. We show that not only our models perform significantly better than models that discard the similarity network but are also robust to new sets of box‐office movies. Copyright © 2016 John Wiley & Sons, Ltd.     

Trees, set compositions and the twisted descent algebra

We first show that increasing trees are in bijection with set compositions, extending simultaneously a recent result on trees due to Tonks and a classical result on increasing binary trees. We then consider algebraic structures on the linear span of set compositions (the twisted descent algebra). Among others, a number of enveloping algebra structures are introduced and studied in detail. For example, it is shown that the linear span of trees carries an enveloping algebra structure and embeds as such in an enveloping algebra of increasing trees. All our constructions arise naturally from the general theory of twisted Hopf algebras.     

Algebraic connectivity and degree sequences of trees

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector.     

Semiparametric quantile modelling of hierarchical data

The classic hierarchical linear model formulation provides a considerable flexibility for modelling the random effects structure and a powerful tool for analyzing nested data that arise in various areas such as biology, economics and education. However, it assumes the within-group errors to be independently and identically distributed （i.i.d.） and models at all levels to be linear. Most importantly, traditional hierarchical models （just like other ordinary mean regression methods） cannot characterize the entire conditional distribution of a dependent variable given a set of covariates and fail to yield robust estimators. In this article, we relax the aforementioned and normality assumptions, and develop a so-called Hierarchical Semiparametric Quantile Regression Models in which the within-group errors could be heteroscedastic and models at some levels are allowed to be nonparametric. We present the ideas with a 2-level model. The level-1 model is specified as a nonparametric model whereas level-2 model is set as a parametric model. Under the proposed semiparametric setting the vector of partial derivatives of the nonparametric function in level-1 becomes the response variable vector in level 2. The proposed method allows us to model the fixed effects in the innermost level （i.e., level 2） as a function of the covariates instead of a constant effect. We outline some mild regularity conditions required for convergence and asymptotic normality for our estimators. We illustrate our methodology with a real hierarchical data set from a laboratory study and some simulation studies.