Penalized Estimation of Free-Knot Splines

Abstract

Polynomial splines are often used in statistical regression models for smooth response functions. When the number and location of the knots are optimized, the approximating power of the spline is improved and the model is nonparametric with locally determined smoothness. However, finding the optimal knot locations is an historically difficult problem. We present a new estimation approach that improves computational properties by penalizing coalescing knots. The resulting estimator is easier to compute than the unpenalized estimates of knot positions, eliminates unnecessary “corners” in the fitted curve, and in simulation studies, shows no increase in the loss. A number of GCV and AIC type criteria for choosing the number of knots are evaluated via simulation.     

Selecting the Number of Knots for Penalized Splines

Penalized splines, or P-splines, are regression splines fit by least-squares with a roughness penalty.P-splines have much in common with smoothing splines, but the type of penalty used with a P-spline is somewhat more general than for a smoothing spline. Also, the number and location of the knots of a P-spline is not fixed as with a smoothing spline. Generally, the knots of a P-spline are at fixed quantiles of the independent variable and the only tuning parameters to choose are the number of knots and the penalty parameter. In this article, the effects of the number of knots on the performance of P-splines are studied. Two algorithms are proposed for the automatic selection of the number of knots. The myopic algorithm stops when no improvement in the generalized cross-validation statistic (GCV) is noticed with the last increase in the number of knots. The full search examines all candidates in a fixed sequence of possible numbers of knots and chooses the candidate that minimizes GCV.The myopic algorithm works well in many cases but can stop prematurely. The full-search algorithm worked well in all examples examined. A Demmler–Reinsch type diagonalization for computing univariate and additive P-splines is described. The Demmler–Reinsch basis is not effective for smoothing splines because smoothing splines have too many knots. For P-splines, however, the Demmler–Reinsch basis is very useful for super-fast generalized cross-validation.     

Piecewise monotone interpolation

In reaction to a recent paper by E. Passow in this Journal, it is shown that broken line interpolation as a scheme for piecewise monotone interpolation is hard to improve upon. It is also shown that a family of smooth piecewise polynomial interpolants, introduced by Swartz and Varga and noted by Passow to be piecewise monotone, converges monotonely, for fixed data, to a piecewise constant interpolant as the degree goes to infinity. Finally, piecewise monotone interpolation by splines with simple knots is discussed.     

Restructuring forward step of MARS algorithm using a new knot selection procedure based on a mapping approach

In high dimensional data modeling, Multivariate Adaptive Regression Splines (MARS) is a popular nonparametric regression technique used to define the nonlinear relationship between a response variable and the predictors with the help of splines. MARS uses piecewise linear functions for local fit and apply an adaptive procedure to select the number and location of breaking points (called knots). The function estimation is basically generated via a two-stepwise procedure: forward selection and backward elimination. In the first step, a large number of local fits is obtained by selecting large number of knots via a lack-of-fit criteria; and in the latter one, the least contributing local fits or knots are removed. In conventional adaptive spline procedure, knots are selected from a set of all distinct data points that makes the forward selection procedure computationally expensive and leads to high local variance. To avoid this drawback, it is possible to restrict the knot points to a subset of data points. In this context, a new method is proposed for knot selection which bases on a mapping approach like self organizing maps. By this method, less but more representative data points are become eligible to be used as knots for function estimation in forward step of MARS. The proposed method is applied to many simulated and real datasets, and the results show that it proposes a time efficient forward step for the knot selection and model estimation without degrading the model accuracy and prediction performance.     

MARS: selecting basis functions and knots with an empirical Bayes method

An empirical Bayes method to select basis functions and knots in multivariate adaptive regression spline (MARS) is proposed, which takes both advantages of frequentist model selection approaches and Bayesian approaches. A penalized likelihood is maximized to estimate regression coefficients for selected basis functions, and an approximated marginal likelihood is maximized to select knots and variables involved in basis functions. Moreover, the Akaike Bayes information criterion (ABIC) is used to determine the number of basis functions. It is shown that the proposed method gives estimation of regression structure that is relatively parsimonious and more stable for some example data sets.     

SHAPE-PRESERVING APPROXIMATION BY SPLINE FUNCTIONS

The author establishes the Jackson-type estimates for monotone and convex approxi-mation by spline functions with non-equally spaced knots.These estimaes involve highorder modulus of the approximated function and its derivatives.Hence some Bernstein-type theorems can be got conveniently.     

Shape constrained smoothing using smoothing splines

Summary  In some regression settings one would like to combine the flexibility of nonparametric smoothing with some prior knowledge about the regression curve. Such prior knowledge may come from a physical or economic theory, leading to shape constraints such as the underlying regression curve being positive, monotone, convex or concave. We propose a new method for calculating smoothing splines that fulfill these kinds of constraints. Our approach leads to a quadratic programming problem and the infinite number of constraints are replaced by a finite number of constraints that are chosen adaptively. We show that the resulting problem can be solved using the algorithm of Goldfarb and Idnani (1982, 1983) and illustrate our method on several real data sets.     

On the Construction of Optimal Monotone Cubic Spline Interpolations

In this paper we derive necessary optimality conditions for an interpolating spline function which minimizes the Holladay approximation of the energy functional and which stays monotone if the given interpolation data are monotone. To this end optimal control theory for state-restricted optimal control problems is applied. The necessary conditions yield a complete characterization of the optimal spline. In the case of two or three interpolation knots, which we call thelocalcase, the optimality conditions are treated analytically. They reduce to polynomial equations which can very easily be solved numerically. These results are used for the construction of a numerical algorithm for the optimal monotone spline in the general (global) case via Newton's method. Here, the local optimal spline serves as a favourable initial estimation for the additional grid points of the optimal spline. Some numerical examples are presented which are constructed by FORTRAN and MATLAB programs.     

Evolutionary computation for optimal knots allocation in smoothing splines

In this paper, a novel methodology is presented for optimal placement and selections of knots, for approximating or fitting curves to data, using smoothing splines. It is well-known that the placement of the knots in smoothing spline approximation has an important and considerable effect on the behavior of the final approximation [1]. However, as pointed out in [2], although spline for approximation is well understood, the knot placement problem has not been dealt with adequately. In the specialized bibliography, several methodologies have been presented for selection and optimization of parameters within B-spline, using techniques based on selecting knots called dominant points, adaptive knots placement, by data selection process, optimal control over the knots, and recently, by using paradigms from computational intelligent, and Bayesian model for automatically determining knot placement in spline modeling. However, a common two-step knot selection strategy, frequently used in the bibliography, is an homogeneous distribution of the knots or equally spaced approach [3].     

Statistical inferences for varying-coefficint models based on locally weighted regression technique

1. IntroductionIn recent y6ars, some progress has been made towards increaJsing the flexibility of linearregression models. One of the obvious extensions in this direction is the sthcalled varyingcoefficient regression models in which the regressiOn funtions are llnear in the regressors,but their coefficients are allowed to change with the value of another factor. Specificallysuppose that we have a response variable Y and regressors X1 t X2,' t Xv as well as anothervariable V. A varyingco…     

Comparison of Parametric and Bootstrap Approaches to Obtaining Confidence Intervals for Logspline Density Estimation

In earlier articles, we developed an automated methodology for using cubic splines with tail linear constraints to model the logarithm of a univariate density function. This methodology was subsequently modified so that the knots were determined by stepwise addition-deletion and the remaining coefficients were determined by maximum likelihood estimation. An alternative approach, referred to as the free knot spline procedure, is to use the maximum likelihood method to estimate the knot locations as well as the remaining coefficients. This article compares various approaches to constructing confidence intervals for logspline density estimates, for both the stepwise procedure and the free knot procedure. It is concluded that a variation of the bootstrap, in which only a limited number of bootstrap simulations are used to estimate standard errors that are combined with standard normal quantiles, seems to perform the best, especially when coverages and computing time are both taken into account.     

On the estimation of a monotone conditional variance in nonparametric regression

A monotone estimate of the conditional variance function in a heteroscedastic, nonparametric regression model is proposed. The method is based on the application of a kernel density estimate to an unconstrained estimate of the variance function and yields an estimate of the inverse variance function. The final monotone estimate of the variance function is obtained by an inversion of this function. The method is applicable to a broad class of nonparametric estimates of the conditional variance and particularly attractive to users of conventional kernel methods, because it does not require constrained optimization techniques. The approach is also illustrated by means of a simulation study.     

Testing for no effect via splines

A spline-based test statistic for a constant mean function is proposed based on the penalized residual sum-of-squares difference between the null model and a B-spline model in which the regression function is approximated with P-splines approach. When the number of knots is fixed, the limiting null distribution of the test statistic is shown to be the distribution of a linear combination of independent chi-squared random variables, each with one degree of freedom. A smoothing parameter is selected by setting a specified value equal to the expected value of the test statistic under the null hypothesis. Simulation experiments are conducted to study the proposed spline-based test statistic’s finite-sample properties.     

Bartlett′s Decomposition of the Posterior Distribution of the Covariance for Normal Monotone Ignorable Missing Data

This paper presents a decomposition for the posterior distribution of the covarianee matrix of normal models under a family of prior distributions when missing data are ignorable and monotone. This decomposition is an extension of Bartlett′s decomposition of the Wishart distribution to monotone missing data. It is not only theoretically interesting but also practically useful. First, with monotone missing data, it allows more efficient drawing of parameters from the posterior distribution than the factorized likelihood approach. Furthermore, with nonmonotone missing data, it allows for a very efficient monotone date augmentation algorithm and thereby multiple imputation or the missing data needed to create a monotone pattern.     

缺失数据下半参数单调回归模型的估计

研究了响应变量缺失情况下半参数单调回归模型的估计问题。利用嵌入核估计的方法得到了参数部分的估计,在此基础上构造了非参数部分的单调约束最小二乘估计。证明了参数估计的渐近分布为正态分布,得到了非参数部分估计的收敛速度。通过随机模拟研究了有限样本量下估计的表现。     

On 3-monotone approximation by piecewise polynomials

We consider 3-monotone approximation by piecewise polynomials with prescribed knots. A general theorem is proved, which reduces the problem of 3-monotone uniform approximation of a 3-monotone function, to convex local L₁ approximation of the derivative of the function. As the corollary we obtain Jackson-type estimates on the degree of 3-monotone approximation by piecewise polynomials with prescribed knots. Such estimates are well known for monotone and convex approximation, and to the contrary, they in general are not valid for higher orders of monotonicity. Also we show that any convex piecewise polynomial can be modified to be, in addition, interpolatory, while still preserving the degree of the uniform approximation. Alternatively, we show that we may smooth the approximating piecewise polynomials to be twice continuously differentiable, while still being 3-monotone and still keeping the same degree of approximation.     

Parameters Related to Tree‐Width,Zero Forcing,and Maximum Nullity of a Graph

Tree‐width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree‐width, largeur d'arborescence, path‐width, and proper path‐width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.     

Constrained Lp-Approximation by Generalized n-Convex Functions Induced by ECT-Systems

The problem of finding a best L_p-approximation (1 ≤ p < ∞) to a function in L_p from a special subcone of generalized n-convex functions induced by an ECT-system is considered. Tchebycheff splines with a countably infinite number of knots are introduced and best approximations are characterized in terms of local best approximations by these splines. Various properties of best approximations and their uniqueness in L₁ are investigated. Some special results for generalized monotone and convex cases are obtained.     

Monotonicity of the search number in the Golovach problem

The Golovach problem, also known as the ɛ-search problem, is as follows. A team of pursuers pursues an evader on a topological graph. The objective of the pursuers is to catch the evader, that is, approach the evader to a distance not exceeding a given nonnegative number ɛ. It is assumed that the evader is invisible to the pursuers and is fully informed beforehand about the search program of the pursuers. The problem is to find the ɛ-search number, i.e., the least number of pursuers sufficient for capturing the evader. Graphs with monotone ɛ-search number are studied; the ɛ-search number of a graph G is said to be monotone if it is not exceeded by the ɛ-search numbers of all connected subgraphs H of G. It is known that the ɛ-search number of any tree is monotone for all nonnegative ɛ. The edgesearch number, which is equal to the 0-search number, is monotone for all connected subgraphs of an arbitrary graph. A sufficient monotonicity condition for the ɛ-search number of any graph is obtained. This result is improved in the case of complete subgraphs. The Golovach function is constructed for graphs obtained by removing one edge from complete graphs with unit edges.     

Three-page approach to knot theory. Encoding and local moves

In the present paper, we suggest a new combinatorial approach to knot theory based on embeddings of knots and links into a union of three half-planes with the same boundary. The idea to embed knots into a “book” is quite natural and was considered already in [1]. Among recent papers on embeddings of knots into a book with infinitely many pages, we mention [2] and [3] (see also references therein). The restriction of the number of pages to three (or any other number ≥3) provides a convenient way toencode links by words in a finite alphabet. For those words, we give a finite set of local changes that realizes the equivalence of links by analogy with the Reidemeister moves for planar link diagrams. This work is partially supported by Russian Foundation for Basic Research grant No. 99-01-00090. Moscow State University. Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 33, No. 4, pp. 25–37, October–December, 1999. Translated by I. A. Dynnikov