Multivariate Adaptive Regression Spline Based Framework For Statistically Parsimonious Adaptive Dyanmic Programming

Central to Dynamic Programming (DP) is the 'cost-to-go' or 'future value' function, which is obtained via solving the Bellman's equation, and central to many Approximate Dynamic Programming (ADP) methods is the approximation of the future value function. The exact DP algorithm seeks to compute and store a table consisting of one cost-to-go value for each point in the state space, and its usefulness is limited by the curse of dimensionality, which renders the methodology computationally intractable in the face of real life problems with high-dimensional state spaces and in the face of continuous state variables. ADP methodology seeks to address and redress the issue of the curse of dimensionality by not seeking to compute the future value function exactly and at each point of the state space; rather opting for an approximation of the future value function in the domain of the state space. Existing ADP methodologies have successfully handled 'continuous' state variables through discretization of the state space and estimation of the cost-to-go or future value function and have been challenged in scenarios involving a mix of 'continuous' and 'categorical' or qualitative state variables. The first part of this dissertation research seeks to develop a flexible, nonparametric statistical modeling method which can capture complex nonlinearity in data comprised of a mix of continuous and categorical variables and can be used to approximate future value functions in stochastic dynamic programming (SDP) problems with a mix of continuous and categorical state variables. This dissertation proposes a statistical modeling method, called 'TreeMARS' which combines the versatility of tree-models with the flexibility of multivariate adaptive regression splines (MARS). An extension of the proposed model, called 'Boosted TreeMARS', is also presented. Comparisons are made to the tree-regression model that uses a similar concept, but only permits the use of linear regression at the terminal nodes. Comparisons are presented on a 10-dimensional simulated data set. The second part of the dissertation research, seeking statistical parsimony, proposes a sequential statistical modeling methodology utilizing the 'sequential' concept from Design and Analysis of Computer Experiments (DACE) to make the grid 'only fine enough' for the 'efficient' discretization and then use MARS methods to approximate future value functions. This methodology can be extended in the future to use tree-based MARS models to approximate future value functions involving a mix of continuous and categorical state variables. This sequential grid discretization is nothing but sequential exploration of the state space and this concept of sequential exploration of the state space provides a statistically parsimonious ADP methodology which 'adaptively' captures the important variables from the state space and builds approximations around these quantities while seeking approximation of the future value functions, by using adaptive and flexible modeling.

Multivariate Adaptive Regression Splines (MARS) is a statistical modeling method used to represent high-dimensional data with interactions. It uses different algorithms to select the terms to be included in the approximation model that best represent the data. In addition, it performs a variable selection, therefore the most significant predictors are shown in the final model. Design and analysis of computer experiments (DACE) is a statistical technique for creating approximations (called metamodels) of computer models. For optimization problems in which there is an unknown function that must be approximated, DACE approach could be applied. In stochastic dynamic programming (SDP) for example, a metamodel can be used to approximate the unknown future value function.The goal of DACE is to efficiently predict the response value of a computer model. MARS has been used as a metamodel in DACE technique. MARS is a flexible model, however in optimization, certain characteristics may be desired, such as a convex or piecewise-linear structure. To satisfy these characteristics, different variants of MARS have been developed. By enabling these variants, MARS modeling facilitates the optimization process. These variations include the ability to model a convex function, a piecewise-linear function and to provide a smoothing option using a quintic routine.DACE has had an enormous contribution for studying complex system, however one of consistent concerns for the researchers is computational time. As researchers seek to study more and more complex systems, corresponding computer models continue to push the limits of computing power. To overcome this drawback, efficient sequential approaches have been studied to reduce the computational effort. This research work focuses its efforts on the development of sequential approaches based on MARS model. The objective is to sequentially update the approximation function using current and new input data points. Additionally, by using less input data points, an accurate prediction of the unknown function could be obtained in a faster manner, and thus the complexity of the model structure is less. This could also facilitate the optimization process.Different case studies are shown in order to test the different MARS variants and sequential MARS approaches proposed in this dissertation. These cases include an inventory forecasting problem, an automotive crash safety design problem and an air pollution SDP problem.

Multivariate Adaptive Regression Splines (MARS) provide a flexible statistical modeling method that employs forward and backward search algorithms to identify the combination of basis functions that best fits the data. In optimization, MARS has been used successfully to estimate the value function in stochastic dynamic programming, and MARS could be potentially useful in many real world optimization problems where objective (or other) functions need to be estimated from data, such as in simulation optimization. Many optimization methods depend on convexity, but a nonconvex MARS approximation is inherently possible because interaction terms are products of univariate terms. In this dissertation, convex versions of MARS are proposed. In order to ensure MARS convexity, two major modifications are made: (1) coefficients are constrained such that pairs of basis functions are guaranteed to jointly form convex functions; (2) The form of interaction terms is appropriately changed. Finally, MARS convexity can be achieved by the fact that the sum of convex functions is convex. The implementation of MARS for approximating complex optimization functions can involve hundreds to thousands of state or decision variables. In particular, this research studies application to an inventory forecasting stochastic dynamic programming problem and an airline fleet assignment problem. Although one can simply attempt a MARS approximation over all the variables, prior research on the fleet assignment application indicates that many variables have little effect on the objective. Thus, a data mining step to conduct variable selection is needed. This step separates potentially critical variables from clearly redundant ones. In this dissertation, variants of two data mining tools are explored separately and in combination for variable selection: regression trees and multiple testing procedures based on false discovery rate.

This book presents methods for investigating whether relationships are linear or nonlinear and for adaptively fitting appropriate models when they are nonlinear. Data analysts will learn how to incorporate nonlinearity in one or more predictor variables into regression models for different types of outcome variables. Such nonlinear dependence is often not considered in applied research, yet nonlinear relationships are common and so need to be addressed. A standard linear analysis can produce misleading conclusions, while a nonlinear analysis can provide novel insights into data, not otherwise possible. A variety of examples of the benefits of modeling nonlinear relationships are presented throughout the book. Methods are covered using what are called fractional polynomials based on real-valued power transformations of primary predictor variables combined with model selection based on likelihood cross-validation. The book covers how to formulate and conduct such adaptive fractional polynomial modeling in the standard, logistic, and Poisson regression contexts with continuous, discrete, and counts outcomes, respectively, either univariate or multivariate. The book also provides a comparison of adaptive modeling to generalized additive modeling (GAM) and multiple adaptive regression splines (MARS) for univariate outcomes. The authors have created customized SAS macros for use in conducting adaptive regression modeling. These macros and code for conducting the analyses discussed in the book are available through the first author's website and online via the book’s Springer website. Detailed descriptions of how to use these macros and interpret their output appear throughout the book. These methods can be implemented using other programs.

MARS(Multivariate Adaptive Regression Splines). Abstract: MARS is a new methodology, due to Friedman, for nonlinear regression modeling. MARS can be conceptualized as a generalization of recursive partitioning that uses spline fitting in lieu of other simple functions. Given a set of predictor variables, MARS fits a model in a form of an expansion of product spline basis functions of predictors chosen during a forward and backward recursive partitioning strategy. MARS produces continuous models for discrete data that can have multiple partitions and multilinear terms. Predictor variable contributions and interactions in a MARS model may be analyzed using an ANOVA style decomposition. By letting the predictor variables in MARS be lagged values of a time series, one obtains a new method for nonlinear autoregressive threshold modeling of time series. A significant feature of this extension of MARS is its ability to produce models with limit cycles when modeling time series data that exhibit periodic behavior. In a physical context, limit cycles represent a stationary state of sustained oscillations, a satisfying behavior for any model of a time series with periodic behavior. Analysis of the Wolf sunspot numbers with MARS appears to give an improvement over existing nonlinear Threshold and Bilinear models.

Applied Predictive Modeling covers the overall predictive modeling process, beginning with the crucial steps of data preprocessing, data splitting and foundations of model tuning. The text then provides intuitive explanations of numerous common and modern regression and classification techniques, always with an emphasis on illustrating and solving real data problems. The text illustrates all parts of the modeling process through many hands-on, real-life examples, and every chapter contains extensive R code for each step of the process. This multi-purpose text can be used as an introduction to predictive models and the overall modeling process, a practitioner’s reference handbook, or as a text for advanced undergraduate or graduate level predictive modeling courses. To that end, each chapter contains problem sets to help solidify the covered concepts and uses data available in the book’s R package. This text is intended for a broad audience as both an introduction to predictive models as well as a guide to applying them. Non-mathematical readers will appreciate the intuitive explanations of the techniques while an emphasis on problem-solving with real data across a wide variety of applications will aid practitioners who wish to extend their expertise. Readers should have knowledge of basic statistical ideas, such as correlation and linear regression analysis. While the text is biased against complex equations, a mathematical background is needed for advanced topics.