An Iterative Procedure for Shape-constrained Smoothing using Smoothing Splines
Posted on
This note is for Turlach, B. A. (2005). Shape constrained smoothing using smoothing splines. Computational Statistics, 20(1), 81–104.
Shape constrained smoothing using smoothing splines
shape constraints: positive, monotone, convex or concave
the paper propose a new method for calculating smoothing splines that fulfill these kinds of constraints
- the 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
- the resulting problem can be solved using the algorithm of Goldfarb and Idnani (1982, 1983)
Given data ${(t_i, y_i)}, t_i\in [a, b]$ for $i=1,\ldots,n$, consider the following problem,
\[\begin{align*} \min &\sum_{i=1}^n (y_i - g(t_i))^2 + \lambda \int_a^b(g^{(m)}(u))^2du\\ s.t. & g^{(r)}(t) \ge 0, t\in [a, b] \end{align*}\]- the unconstrined minimizer is a natural spline of order $2m$ with knots at the observation points $t_i$
the paper concentrates on the case $m=2$ and present an algorithm for calculating a natural cubic spline that fulfills the constraints for any $r\le 2$ or any combination of such $r$’s
-
Mammen and Thomas-Agnan (1999): the finite number of constraints can be replaced by a finite number of constraints with only a small loss of accuracy
- by way of contrast, Utreras (1985) shows, for $m=2$ and $r=1$ (monotonicity), the solution is a piecewise cubic polynomial with knots at the points $t_i$ and at most $k=2[n/2]+2$ additional knots whose location is unknown. He suggested that an exchange algorithm could be devised to find the solution. (but to the best of the authors’ knowledge, such an algorithm is not yet proposed)
- for the case $m=2$ and $r=2$ (convexity/concavity), Elfving and Andersson (1988) give a complete characterization theorem for the solution. This leads to a nonlinear minimization problem that the authors propose to solve by Newton’s method
Given these difficulties for finding the exact solution, most algorithms proposed calculate approximate solutions. Monotonicity constraints are considered in
- Ramsay (1988)
- Gaylord and Ramirez (1991)
- He and Shi (1998), see also He and Ng (1999)
- Fritsch (1990): calculate a monotone cubic $C^1$-spline
- Tantjyaswasdikul and Woodroofe (1994): $m=1$ and $r=1$
Algorithms for estimating a convex/concave function are given in
- Dierckx (1980)
- Irvine et al. (1986)
- Schmidt (1987)
- Schmidt and Scholz (1990)
- Schwetlick and Kunert (1993): propose a method for general $m$ and $r$ but concentrate on the convex/concave case
- Dole (1999): estimation of monotone convex functions
typically, these approaches involve the choice of an appropriate B-spline basis which transforms the minimisation problem into a least-sqaures problem for the coefficients of the basis functions.
- the constraints will impose some contraints on these coefficients and which typically leads to a quadratic programming problem that has to be solved. Some allow automatic location of knot points.
the proposed approach differs in several ways from those cited above
- instead of choosing a suitable $B$-spline basis and identifying the necessary constraints on the coefficients of the basis functions,
- fit an (unconstrained) smoothing spline in the first step
- next, verify whether this estimate has the desired shape. If there are any violations, we add constraints that ensure that the smoothing spline will have the desired shape at those points where it currently does not fulfill the shape restrictions. Then the constrained smoothing spline is updated
- the process of verifying-and-adding-new-constraints is iterated
- most of the above proposals treat for one value of $r$ only. By way of contrast, the proposal is easily extended to the case where the constraint should hold for several values of $r$ simultaneously.
another approach to constrained smoothing splines: Ramsay (1998)
- the author proposes to impose the smoothness penalty on a function, say $w$, which is related to the function $g$ via a differential equation
other nonparametric smoothers can also be used to estimate functions with shape restrictions
- for monotone smoothing, several alternative approaches were proposed (e.g., Delecroix et al, 1995, 1996; Friedman and Tibshirani, 1984)
Monotone smoothing
consider the necessary conditions $g’(t_i) \ge 0$ initially, and then add more constraints for voilated subintervals.