Pruning by isomorphism in branch-and-cut

 The paper presents a branch-and-cut for solving (0, 1) integer linear programs having a large symmetry group. The group is used for pruning the enumeration tree and for generating cuts. The cuts are non-standard, cutting integer feasible solutions but leaving the optimal value of the problem unchanged. Pruning and cut generation are performed by backtracking procedures using a Schreier-Sims table for representing the group. Applications to hard set covering problems and to the generation of covering designs and error correcting codes are presented. Received: August 2001 / Accepted: October 2002 Publication online: December 9, 2002 Key Words. branch-and-cut – isomorphism pruning – symmetry     

An exact depth-first algorithm for the pallet loading problem

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.     

On the LASSO and its Dual

Abstract

Proposed by Tibshirani, the least absolute shrinkage and selection operator (LASSO) estimates a vector of regression coefficients by minimizing the residual sum of squares subject to a constraint on the l ¹-norm of the coefficient vector. The LASSO estimator typically has one or more zero elements and thus shares characteristics of both shrinkage estimation and variable selection. In this article we treat the LASSO as a convex programming problem and derive its dual. Consideration of the primal and dual problems together leads to important new insights into the characteristics of the LASSO estimator and to an improved method for estimating its covariance matrix. Using these results we also develop an efficient algorithm for computing LASSO estimates which is usable even in cases where the number of regressors exceeds the number of observations. An S-Plus library based on this algorithm is available from StatLib.     

The Mode Tree: A Tool for Visualization of Nonparametric Density Features

Abstract

Recognition and extraction of features in a nonparametric density estimate are highly dependent on correct calibration. The data-driven choice of bandwidth h in kernel density estimation is a difficult one that is compounded by the fact that the globally optimal h is not generally optimal for all values of x. In recognition of this fact a new type of graphical tool, the mode tree, is proposed. The basic mode tree plot relates the locations of modes in density estimates with the bandwidths of those estimates. Additional information can be included on the plot indicating factors such as the size of modes, how modes split, and the locations of antimodes and bumps. The use of a mode tree in adaptive multimodality investigations is proposed, and an example is given to show the value in using a normal kernel, as opposed to the biweight or other kernels, in such investigations. Examples of such investigations are provided for Ahrens's chondrite data and van Winkle's Hidalgo stamp data. Finally, the bivariate mode tree is introduced, together with an example using Scott's lipid data.     

Multiscale support vector regression method in Sobolev spaces on bounded domains

In this paper, we investigate the multiscale support vector regression (SVR) method for approximation of functions in Sobolev spaces on bounded domains. The Vapnik ?-intensive loss function, which has been developed well in learning theory, is introduced to replace the standard l² loss function in multiscale least squares methods. Convergence analysis is presented to verify the validity of the multiscale SVR method with scaled versions of compactly supported radial basis functions. Error estimates on noisy observation data are also derived to show the robustness of our proposed algorithm. Numerical simulations support the theoretical predictions.     

Combining an Additive and Tree-Based Regression Model Simultaneously: STIMA

Additive models and tree-based regression models are two main classes of statistical models used to predict the scores on a continuous response variable. It is known that additive models become very complex in the presence of higher order interaction effects, whereas some tree-based models, such as CART, have problems capturing linear main effects of continuous predictors. To overcome these drawbacks, the regression trunk model has been proposed: a multiple regression model with main effects and a parsimonious amount of higher order interaction effects. The interaction effects can be represented by a small tree: a regression trunk. This article proposes a new algorithm—Simultaneous Threshold Interaction Modeling Algorithm (STIMA)—to estimate a regression trunk model that is more general and more efficient than the initial one (RTA) and is implemented in the R-package stima. Results from a simulation study show that the performance of STIMA is satisfactory for sample sizes of 200 or higher. For sample sizes of 300 or higher, the 0.50 SE rule is the best pruning rule for a regression trunk in terms of power and Type I error. For sample sizes of 200, the 0.80 SE rule is recommended. Results from a comparative study of eight regression methods applied to ten benchmark datasets suggest that STIMA and GUIDE are the best performers in terms of cross-validated prediction error. STIMA appeared to be the best method for datasets containing many categorical variables. The characteristics of a regression trunk model are illustrated using the Boston house price dataset.

Supplemental materials for this article, including the R-package stima, are available online.     

Model Search by Bootstrap “Bumping”

Abstract

We propose a bootstrap-based method for enhancing a search through a space of models. The technique is well suited to complex, adaptively fitted models—it provides a convenient method for finding better local minima and for resistant fitting. Applications to regression, classification, and density estimation are described. We also provide results on the asymptotic behavior of bumping estimates.     

Research on estimation model of the battery state of charge in a hybrid electric vehicle based on the classification and regression tree

ABSTRACT

In order to achieve the accurate estimation of state of charge (SOC) of the battery in a hybrid electric vehicle (HEV), this paper proposed a new estimation model based on the classification and regression tree (CART) which belongs to a kind of decision tree. The basic principle and modelling process of the CART decision tree were introduced in detail in this paper, and we used the voltage, current, and temperature of the battery in an HEV to estimate the value of SOC under the driving cycle. Meanwhile, we took the energy feedback of the HEV under the regenerative braking into consideration. The simulation data and experimental data were used to test the effectiveness of the estimation model of CART, and the results indicate that the proposed estimation model has high accuracy, the relative error of simulation is within 0.035, while the relative error of experiment is less than 0.05.     

Treed Regression

Abstract

Given a data set consisting of n observations on p independent variables and a single dependent variable, treed regression creates a binary tree with a simple linear regression function at each of the leaves. Each node of the tree consists of an inequality condition on one of the independent variables. The tree is generated from the training data by a recursive partitioning algorithm. Treed regression models are more parsimonious than CART models because there are fewer splits. Additionally, monotonicity in some or all of the variables can be imposed.     

The Bumpy Road to the Mode Forest

Abstract

The mode tree of Minnotte and Scott provides a valuable method of investigating features such as modes and bumps in a unknown density. By examining kernel density estimates for a range of bandwidths, we can learn a lot about the structure of a data set. Unfortunately, the basic mode tree can be strongly affected by small changes in the data, and gives no way to differentiate between important modes and those caused, for example, by outliers. The mode forest overcomes these difficulties by looking simultaneously at a large collection of mode trees, all based on some variation of the original data, by means such as resampling or jittering. The resulting graphic tool is both visually appealing and informative.     

Unified Noncrossing Multiple Quantile Regressions Tree

In this article, we consider the estimation problem of a tree model for multiple conditional quantile functions of the response. Using the generalized, unbiased interaction detection and estimation algorithm, the quantile regression tree (QRT) method has been developed to construct a tree model for an individual quantile function. However, QRT produces different tree models across quantile levels because it estimates several QRT models separately. Furthermore, the estimated quantile functions from QRT often cross each other and consequently violate the basic properties of quantiles. This undesirable phenomenon reduces prediction accuracy and makes it difficult to interpret the resulting tree models. To overcome such limitations, we propose the unified noncrossing multiple quantile regressions tree (UNQRT) method, which constructs a common tree structure across all interesting quantile levels for better data visualization and model interpretation. Furthermore, the UNQRT estimates noncrossing multiple quantile functions simultaneously by enforcing noncrossing constraints, resulting in the improvement of prediction accuracy. The numerical results are presented to demonstrate the competitive performance of the proposed UNQRT over QRT. Supplementary materials for this article are available online.     

Phylogenetic Inference for Binary Data on Dendograms Using Markov Chain Monte Carlo

Abstract

Using a stochastic model for the evolution of discrete characters among a group of organisms, we derive a Markov chain that simulates a Bayesian posterior distribution on the space of dendograms. A transformation of the tree into a canonical cophenetic matrix form, with distinct entries along its superdiagonal, suggests a simple proposal distribution for selecting candidate trees “close” to the current tree in the chain. We apply the consequent Metropolis algorithm to published restriction site data on nine species of plants. The Markov chain mixes well from random starting trees, generating reproducible estimates and confidence sets for the path of evolution.     

Computing S Estimators for Regression and Multivariate Location/Dispersion

Abstract

An improved resampling algorithm for S estimators reduces the number of times the objective function is evaluated and increases the speed of convergence. With this algorithm, S estimates can be computed in less time than least median squares (LMS) for regression and minimum volume ellipsoid (MVE) for location/scatter estimates with the same accuracy. Here accuracy refers to the randomness due to the algorithm. S estimators are also more statistically efficient than the LMS and MVE estimators, that is, they have less variability due to the randomness of the data.     

Refined Error Estimates for Radial Basis Function Interpolation

We discuss new and refined error estimates for radial-function scattered-data interpolants and their derivatives. These estimates hold on R ^d , the d-torus, and the 2-sphere. We employ a new technique, involving norming sets, that enables us to obtain error estimates, which in many cases give bounds orders of magnitude smaller than those previously known.     

Weighted extended B-spline method for the approximation of the stationary Stokes problem

A new stabilized, mesh-free method for the approximation of the Stokes problem, using weighted extended B-splines (WEB-splines) as shape functions has been proposed. The web-spline based bilinear velocity–constant pressure element satisfies the so called inf–sup condition or Ladyshenskaya–Babus˘ka–Brezzi (LBB) condition. The main advantage of this method over standard finite element methods is that it uses regular grids instead of irregular partitions of domain, thus eliminating the difficult and time consuming pre-processing step. Convergence and Condition number estimates are derived. Numerical experiments in two space dimensions confirm the theoretical predictions.     

A Generalized Single Linkage Method for Estimating the Cluster Tree of a Density

The goal of clustering is to detect the presence of distinct groups in a dataset and assign group labels to the observations. Nonparametric clustering is based on the premise that the observations may be regarded as a sample from some underlying density in feature space and that groups correspond to modes of this density. The goal then is to find the modes and assign each observation to the domain of attraction of a mode. The modal structure of a density is summarized by its cluster tree; modes of the density correspond to leaves of the cluster tree. Estimating the cluster tree is the primary goal of nonparametric cluster analysis. We adopt a plug-in approach to cluster tree estimation: estimate the cluster tree of the feature density by the cluster tree of a density estimate. For some density estimates the cluster tree can be computed exactly; for others we have to be content with an approximation. We present a graph-based method that can approximate the cluster tree of any density estimate. Density estimates tend to have spurious modes caused by sampling variability, leading to spurious branches in the graph cluster tree. We propose excess mass as a measure for the size of a branch, reflecting the height of the corresponding peak of the density above the surrounding valley floor as well as its spatial extent. Excess mass can be used as a guide for pruning the graph cluster tree. We point out mathematical and algorithmic connections to single linkage clustering and illustrate our approach on several examples. Supplemental materials for the article, including an R package implementing generalized single linkage clustering, all datasets used in the examples, and R code producing the figures and numerical results, are available online.     

Spline Estimation of Discontinuous Regression Functions

Abstract

This article deals with regression function estimation when the regression function is smooth at all but a finite number of points. An important question is: How can one produce discontinuous output without knowledge of the location of discontinuity points? Unlike most commonly used smoothers that tend to blur discontinuity in the data, we need to find a smoother that can detect such discontinuity. In this article, linear splines are used to estimate discontinuous regression functions. A procedure of knot-merging is introduced for the estimation of regression functions near discontinuous points. The basic idea is to use multiple knots for spline estimates. We use an automatic procedure involving the least squares method, stepwise knot addition, stepwise basis deletion, knot-merging, and the Bayes information criterion to select the final model. The proposed method can produce discontinuous outputs. Numerical examples using both simulated and real data are given to illustrate the performance of the proposed method.     

On the Spurious Correlation Between Sample Betas and Mean Returns

Abstract

Cornerstone asset pricing models, such as capital asset pricing model (CAPM) and arbitrage pricing theory (APT), yield theoretical predictions about the relationship between expected returns and exposure to systematic risk, as measured by beta(s). Numerous studies have investigated the empirical validity of these models. We show that even if no relationship holds between true expected returns and betas in the population, the existence of low-probability extreme outcomes induces a spurious correlation between the sample means and the sample betas. Moreover, the magnitude of this purely spurious correlation is similar to the empirically documented correlation, and the regression slopes and intercepts are very similar as well. This result does not necessarily constitute evidence against the theoretical asset pricing models, but it does shed new light on previous empirical results, and it points to an issue that should be carefully considered in the empirical testing of these models. The analysis points to the dangers of relying on simple least squares regression for drawing conclusions about the validity of equilibrium pricing models.