smoothing.qmd

---
title: "Smoothing"
---
### Some example data, and the problem setting

The following code produces a function whose graphs shows several ups and downs.
Don't pay to much attention on how the function works; just look at its graph.

```{r}
library( splines )

spline_coefs = c( .1, .1, .1, .3, 1.3, 1.3, -.1, -.1, -.1, .3, .3  )
spline_knots = c( .1, .1, .32, .35, .36, .48, .7 )
  
true_function <- function(x)
   bs( x, knots=spline_knots, intercept=TRUE ) %*% spline_coefs

xg <- seq( 0, 1, length.out=1000 )
plot( xg, true_function( xg ), type="l" )
```

Let's assume, we have some complicated apparatus or some complex system, which 
responds to some input or stimulus with an output or response governed by this
function. Unfortunately, the measurement of the response is very noisy, and
we have measurements only for a limited number of stimulus values.

Here's the 100 stimulus values:

```{r}
n <- 100
set.seed( 13245769 )
x <- runif( n )
```

And here's the measured responses:

```{r}
y <- true_function( x ) + rnorm( n, sd=.1 )
```

This is how our data looks like:

```{r}
plot( x, y )
```

Can we reconstruct the original function from this noisy data?

### Binned means

The simplest idea would be to bin the x-values and calculate for
each bin of x values an average of the y values, e.g. one average of the y values
corresponding to the x-values x from 0 to 0.1, one average for x between .1 and .2, etc.

```{r}
suppressPackageStartupMessages( library( tidyverse ) )

tibble( x, y ) %>%
mutate( xbin = cut_width( x, .1, center=0.05 ) ) %>%
group_by( xbin ) %>%
summarise_all( mean ) %>%
ggplot() + geom_point( aes( xbin, y ) )
```

### Kernel smoothing

The hard cuts might introduce artefacts. An alternative is the following:

To get a smooth $y$ value for a given value $x_0$, calculate a *weighted* mean
of the $y$ values, where the weight depends on the distance $x-x_0$ and is 0
for distance larger than some "smoothing bandwidth" $h$:

$$ f_\text{sm}(x_0) = \frac{ \sum_i y_i w_i }{\sum_i w_i}, $$
where the weights depend on some "kernel function" $f_\text{K}$ as
$$ w_i = f_\text{K}\left(\frac{x-x_0}{h}\right).$$

There are many choices for kernel functions. Wikipedia [lists](https://en.wikipedia.org/wiki/Kernel_(statistics)) the popular
ones.

A kernel function should be symmetric $f_\text{K}(x)=f_\text{K}(-x)$, 
have a single mode at 0, be continuous, perhaps also differentiable, and 
small or even zero for $|x|>0$. We use the tricube kernel
$$ f_\text{tc}(u) = \left\{ \begin{align}
\frac{70}{81} \left(1-|u|^3\right)^3 \qquad & \text{for } |u| \le 1 
\\
0 \qquad & \text{otherwise} 
\end{align} \right.$$

The prefactor merely ensures that the function has a unit integral. 
As we divide by the weight sum anyway, we don't need it:

```{r}
tricube <- function(u)
  ifelse( abs(u) < 1, ( 1 - abs(u)^3 )^3, 0 )
```

Here's the smoothing function $f_\text{sm}$ from above, now in R:

```{r}
kernel_smooth <- function( x0, x, y, h ) {
  w <- tricube( ( x - x0 ) / h )
  sum( w * y ) / sum( w )
}
```

We use it to draw a smoothed plot:

```{r}
xg <- seq( 0, 1, length.out = 300 )

plot( 
  xg, 
  sapply( xg, kernel_smooth, x, y, h=.1), 
  type="l", col="red", ylim=c( -.1, 1.5 ) )

lines( xg, true_function( xg ), col="blue" )
points( x, y )
```

For comparison, we have added to the smoothing curve (red) the true function (blue),
from which we had sampled our data.

#### Bandwidth choice

Experiment a bit with values for $h$, the kernel width (also called the "smoothing bandwidth").

How to choose a good value? What's the trade-off?


### Local regression

(also known as "LOESS smoothing" or "LOWESS smoothing", for 
"locally estimated/weighted scatterplot smoothing")

In the curves above, the smoothed line has difficulties following the steep decent in the middle.
This is because a kernel smoother cannot "sense slope".

Before, we have calculated a weighted average to get a smooth $y$ value for a given
point $x_0$. Now, we will perform a weighted regression at this point.

Let's choose $x_0=0.4$ and look at the weights by making a scatter plot  
using points with weight-proportional area:

```{r}
x0 <- .4

w <- tricube( ( x - x0 ) / .1 )

plot( x, y, cex=w )
```

Let's fit a regression in line into with plot. We use the fact that the `lm` function 
accepts weights.

```{r}
fit <- lm( y ~ x, weights=w )

fit
```

Here, `lm` has now maximized the weighted sum of squared residuals,

$$ \frac{\sum_i w_i ( \hat y_i - y )^2}{\sum_i w_i}, \qquad \text{with } \hat y_i = \hat a + \hat b x_i, $$
where $\hat a$ and $\hat b$ are the fitetd coefficients (intercept and slope), reported by
```{r}
coef(fit)
```
and $w_i$ are the weights, calculated as above.

Let's put the regression line into our plot, in orange, together fith the fitted
value at point $x_0$ (in red) :

```{r}
plot( x, y, cex=w )
abline( a=coef(fit)[1], b=coef(fit)[2], col="orange" )
points( x0, coef(fit)[1] + x0*coef(fit)[2], col="red" )
lines( xg, true_function(xg), col="lightblue" )
```

Here is a function that does all these steps:

```{r}
local_regression_smooth <- function( x0, x, y, h ) {
  w <- tricube( ( x - x0 ) / h )
  fit <- lm( y ~ x, weights=w )
  coef(fit)[1] + x0 * coef(fit)[2]
}
```

It's not vectorized, so we have to wrap it in an `sapply` to get the whole smoothed curve
(as before):

```{r}
plot( 
  xg, 
  sapply( xg, local_regression_smooth, x, y, h=.1), 
  type="l", col="red", ylim=c( -.1, 1.5 ) )

lines( xg, true_function( xg ), col="blue" )
```
Here, switching from simple kernel smoothing to local regression did not make that much of a difference
but sometimes, it helps a lot.

#### Higher-order local regression

Of course, instead of fitting a regression line, we could have fitted a parabola.
This is quickly done, by adding a quadratic term to the regression

```{r}
local_quadratic_regression_smooth <- function( x0, x, y, h ) {
  w <- tricube( ( x - x0 ) / h )
  fit <- lm( y ~ x + I(x^2), weights=w )
  coef(fit)[1] + x0 * coef(fit)[2] + x0^2 * coef(fit)[3]
}
```

```{r}
plot( 
  xg, 
  sapply( xg, local_quadratic_regression_smooth, x, y, h=.1), 
  type="l", col="red", ylim=c( -.1, 1.5 ) )

lines( xg, true_function( xg ), col="blue" )
```

This did, in fact, improve the fit.

#### Adaptive bandwidth

What if the x values are not uniformly dstributed?

This time, we draw our x values from a non-uniform distribution:

```{r}
set.seed( 13245768 )

x <- sample( c( rbeta( n/2, 3, 7 ), rbeta( n/2, 9, 1 ) ) )
y <- true_function( x ) + rnorm( n, sd=.1 )

plot( x, y )
lines( xg, sapply( xg, local_quadratic_regression_smooth, x, y, h=.1 ), col="red" )
lines( xg, true_function( xg ), col="blue" )
```

The bandwidth is too large where the points are dense and too narrow where they are sparse.

Adaptive bandwidth: Always choose $h$ such that a fixed number of x values are within the
kernel window.

```{r}
local_quadratic_regression_adaptive_smooth <- function( x0, x, y, hn ) {
  ds <- sort( abs( x - x0 ) )
  h <- ds[hn]
  w <- tricube( ( x - x0 ) / h )
  fit <- lm( y ~ x + I(x^2), weights=w )
  coef(fit)[1] + x0 * coef(fit)[2] + x0^2 * coef(fit)[3]
}

plot( x, y )
lines( xg, sapply( xg, local_quadratic_regression_adaptive_smooth, x, y, hn=30 ), col="red" )
lines( xg, true_function( xg ), col="blue" )
```

#### Locfit

In R, all this, and more, is available via the `loess` function (part of base R)
or the `locfit` package. Our implementation above is, of course, very simple and slow, so better
use these functions.

```{r}
plot( x, y )
lines( xg, sapply( xg, local_quadratic_regression_adaptive_smooth, x, y, hn=30 ), col="red" )
lines( xg, true_function( xg ), col="blue" )

fit <- loess( y ~ x, degree=2, span = 30/length(x) )
lines( xg, predict( fit, xg ), col="orange", lty="dashed" )
```

Here, we specified in the `loess` call that we want local regression with quadratic polynomials, 
with an adaptive bandwidth as given by `span` (which specified the number of points put under
the kernel as fraction of the total number of data points).

It seems that the "loess" function (orange line) gives a slightly better result than our simple implementation (red line).
Maybe it knows an additional trick?

### Uncertainty estimation

#### Bootstrapping

Usually, we do not know the "true" function. So, how can we judge how good it is?

Bootstrapping offers a way.

Bootstrapping means to replace the data with new data which is obtained by 
drawing observations, i.e., $(x,y)$ pairs, from the data, with replacement. 
Doing this many times provides a distribution of possible alternative fits.

First, let's do this for simple kernel smoothing:

```{r}
plot( x, y, xlim=c(0,1), ylim=c(-.2,1.6) )

for( i in 1:100 ) {
  bss <- sample.int( length(x), replace=TRUE )
  lines( xg, sapply( xg, kernel_smooth, x[bss], y[bss], h=.1 ), 
     col = adjustcolor( "red", alpha=.1 ) ) }

lines( xg, true_function(xg), col="blue" )
```

Now the same for local quadratic regression with the `loess` function:

```{r}
plot( x, y, xlim=c(0,1), ylim=c(-.5,1.5) )

for( i in 1:100 ) {
  bss <- sample.int( length(x), replace=TRUE )
  lines( xg, predict( loess( y[bss] ~ x[bss], degree=2, span = 30/length(x) ), xg ),
     col = adjustcolor( "red", alpha=.1 ) ) }

lines( xg, true_function(xg), col="blue" )
```

#### Leave-one-out cross-validation

Another possibility is to use LOO-CV:

Calculate for each data point its y value, using the y values of its neighbours, but
not using the point's own y value.

```{r}
yhat_loo <- sapply( 1:length(x), function(i)
  kernel_smooth( x[i], x[-i], y[-i], h=.1 ) ) 

plot( x, y )
points( x, yhat_loo, col="red" )
```

Now we can calculate a mean squared error (MSE):

```{r}
mean( ( y - yhat_loo )^2 )  # Mean squared error
```

Is the MSE lower with a more advanced smoother?

```{r}
yhat_loo <- sapply( 1:length(x), function(i)
  predict( loess( y[-i] ~ x[-i] ), x[i] ) ) 

mean( ( y - yhat_loo )^2, na.rm=TRUE )
```

#### Standard errors from regression

Using the math of ordinary least squares (OLS) regression, we can also get standard errors
from a LOESS fit.

Here, we multiply by 1.96 to get a 95% confidence band. 

```{r}
pred <- predict( loess( y ~ x, span=.1 ), xg, se=TRUE )

plot( x, y, xlim=c(0,1), ylim=c(-.5,1.5) )
lines( xg, pred$fit, col="red" )
rect( xg, pred$fit - 1.96 * pred$se.fit, 
      lead(xg), pred$fit + 1.96 * pred$se.fit, col=alpha("red",.3), lty="blank" )
lines( xg, true_function(xg), col="blue" )


```

### Example with Poisson noise

Above, the noise was Gaussian (normal). In our single-cell data, it is Poissonian.
Furthermore, we would like to calculate the curve on the log level, while properly dealing
with zeroes.

We construct example count data from our curved function.

Let's use a few more data points this time:

```{r}
n <- 300
```

Let's sample predictors. We call them x, as before, even though t might be appropriate, too,
as in out real-data example, the x axis was pseudotime.

```{r}
set.seed( 13245768 )
x <- runif(n)
```

First, we need cell sizes (count totals per cell). We draw them from a log normal:

```{r}
s = round( exp( rnorm( n, log(1e3), .5 ) ) )

hist( log10(s) )
```

Next, we get true fractions from our `true_function`, which we exponentiate. We have to rescale and shift a bit to get realistic values:

```{r}
true_fraction <- function(x) exp( true_function(x) * 4 - 8 )

q <- true_fraction(x)

plot( x, q, log="y")
```

Now, we add the Poisson noise:

```{r}
k <- rpois( n, q * s )

plot( x, log( k/s * 1e4 + 1 ) )
```

### Kernel smoothing

Let's first use a simple kernel smoother. However, for the average, we use this time not
$$ f_\text{sm}(x_0) = \frac{ \sum_i y_i w_i }{\sum_i w_i}, $$
as before, but
$$ f_\text{Psm}(x_0) = \log \frac{ \sum_i k_i w_i }{\sum_i s_i w_i}, $$
We first try it, then see why this makes sense.

```{r}
kernel_smooth_Poisson <- function( x0, x, k, s, h ) {
  w <- tricube( ( x - x0 ) / h )
  sum( w * k ) / sum( w * s )
}
```

We use it to draw a smoothed plot:

```{r}
xg <- seq( 0, 1, length.out = 300 )

plot( xg, sapply( xg, kernel_smooth_Poisson, x, k, s, h=.1 ), 
  type="l", col="red", log="y", ylim=c(1e-4,1e-1) )

lines( xg, true_fraction( xg ), col="blue" )

```
To understand the change in the last two equations, we need a short detour:

#### Inverse-variance weighting

Given $n$ independent random variables $X_i$ with variances $v_i=\operatorname{v_i}$, 
we want to estimate the expectation 
of their mean, $\operatorname{E}\left(\frac{1}{n}\sum_{i=1}^n X_i\right)$, by way 
of estimating a weighted mean,
$$ \hat\mu = \frac{\sum_iw_iX_i}{\sum_i w_i}. $$
How should the weights be chosen such that the estimator's sampling variance, 
$\operatorname{Var}\hat\mu$, is minimized?

If all the estimated variances are the same,  $v_i=v$, then the weights should all be the same, too:
$w_i\propto 1$.

In general, however, the weights might differ. Then, one should choose $w_i\propto \frac{1}{v_i}$.

This is easily proven with Lagrange multipliers; the proof can be found on the Wikipedia page
on [inverse-variance weighting](https://en.wikipedia.org/wiki/Inverse-variance_weighting).

#### Application to Poisson variables

Let us now assume that the random variables we want to average over are fractions
derived from Poisson counts. We have cells, indexed by $i$, with counts for our gene
of interest, given by $K_i\sim \operatorname{Pois}(s_i q)$, where $s_i$ is the
"size", i.e., the total count sum for the cell. We wish to estimate the common
expected fraction $q$ via teh weighted average
$$ \hat q = \frac{\sum_iw_i\frac{K_i}{s_i}}{\sum_i w_i}. $$
What weights $w_i$ should we use? Using $\operatorname{Var} K_i=s_i q$ together with
the preceding result, we get
$$ w_i \propto \frac{1}{\operatorname{Var}\frac{K_i}{s_i}}=\frac{1}{\frac{1}{s_i^2}\operatorname{Var}K_i}=\frac{1}{\frac{1}{s_i^2}s_iq}=\frac{s_i}{q} \propto s_i $$
Hence:

$$ \hat q = \frac{\sum_iw_i\frac{K_i}{s_i}}{\sum_i w_i} = \frac{\sum_i s_i\frac{K_i}{s_i}}{\sum_i s_i} = \frac{\sum_i K_i}{\sum_i s_i}. $$
This justifies our switching from $\frac{1}{n}\sum_i(k_i/s_i)$ to $(\sum_i k_i)/(\sum_i s_i)$ in our smoothing function.

### Generalized linear models

Before proceding further, we need another detour, this time to introduce generalized
linear models (GLMs) as a generalization of OLS linear models. 

#### Example: Radioactive decay

We have measurements of the number of clicks per minute for a radioactive sample.
Let's simulate this: We count every 10 minutes for 1 minute, up to 200 minutes. The
activite at t=0 is 1000 clicks/min, the half-life is 130 min.

```{r}
t <- seq( from=0, by=10, length.out=20 )
expected_counts_per_min <- 100* 2^( - t / 20 )

k <- rpois( length(t), expected_counts_per_min )

plot( t, k )
```

A simple approach is to plot on a semi-log plot:

```{r}
plot( t, k, log="y")
```
and fit a regression line. However, the zeroes mess this up.

Here's a better way:

We may assume that 
$$ k_i \sim \operatorname{Pois}( \alpha e^{\kappa t_i})$$
The true values are $\alpha = 100$ (the initial click rate) and
$\kappa = \ln 2 / 20\approx .035$ (using the half life, 20, from above).

We can find maximum-likelihood estimates for $\alpha$ and $\kappa$. 
Here is the log-likelihood for a pair of candidate values $\alpha$ and $kappa$:

```{r}
ll <- function( alpha, kappa )
  sum( dpois( k, alpha * exp( -kappa * t ), log=TRUE ) )
```

We can find the parameters that maximize this function, using some guessed initital values:

```{r}
optim( 
  c( 50, 0.1 ),
  function( x ) -ll( x[1], x[2] ) )
```
#### GLMs

Rewriting our model a bit, we recover the form of a "generalized linear model" (GLM). A GLM
always has three components:

(i) The response (in our case, the counts $K_i$) follows a distribution from the so-called exponential 
family (which includes the normal, the Poisson, the binomial, the gamma-Poisson, and others). Here, we have:

$$ K_i \sim \operatorname{Pois}( \mu_i ). $$
(ii) The mean parameter $\mu_i$ in that distribution is coupled with teh so-called "linear
predictir$ \eta_i$ by a function, the so-called "link function". Here:
$$ \eta_i = \log \mu_i. $$
(iii) The linear predictor is a linear combination of known predictors $x_ij$ with unknown coefficients $\beta_j$. In general
$$ \eta_i = \beta_0 + \sum_j \beta_j x_{ij} + o_i$$
and here simply
$$ \eta_i = \beta_0 + \beta_1 t_i, $$ 
i.e. we have, besides the intercept $\beta_0$, only one further coefficient, $\beta_1$. 

There are also no offsets $o_i$. (If the time
we had waited at each time point to count would not always have been the same but
differed from measurement to measurement, we would have included the length these 
waiting times as "exposure values" $o_i$.)

We can clearly identify how the coefficients of the GLM correspond to
our parameters: $\beta_1=-\kappa=-\ln2/T_{1/2}$ and $\beta_0=\ln\alpha$.

If the model has this shape, the general optimizer `optim` that we have used above
can be replaced by a GLM solver:

```{r}
fit <- glm( k ~ t, family = poisson(link="log") )
fit
```
We get the same result as with optim. We see this directly for the coefficient for $t$ (i.e.,
$\kappa$), but for $\alpha$, we have to exponentiate:
```{r}
exp(coef(fit)[1])
```

#### IRLS

The `glm` function is faster than `optim` and more stable, because it uses a special
algorithm known as "iteratively reweighted least squares" (IRLS) fitting.

I was too lazy to write up how this works, so I asked ChatGPT to do my work:

https://chatgpt.com/share/38554552-182e-45cf-9ea9-556a3592d6df

### Local regression with GLMs

Now, that we know GLMs, we can come back to our count data to be smoothed:

```{r}
set.seed( 13245768 )
x <- runif(n)
s <- round( exp( rnorm( n, log(1e3), .5 ) ) )
k <- rpois( n, q * s )

plot( x, log( k/s * 1e4 + 1 ) )
```

Instead of a simple kernel smoother, let's to local regression again, but now
with the `glm` function instead of the `lm` function:

```{r}
local_quadratic_regression_smooth_Poisson <- function( x0, x, k, s, h ) {
  w <- tricube( ( x - x0 ) / h )
  fit <- glm( k ~ x + I(x^2), weights=w, offset=log(s), family=poisson("log") )
  unname( coef(fit)[1] + x0 * coef(fit)[2] + x0^2 * coef(fit)[3] )
}
```

Can you see why we pass the totals $s$ as offsets? Why logarithmized? Have a careful
look at the formula with $o_i$ above.

Here is the result. Smoothed curve in red, noisy data in gray, original function in blue.

```{r}
suppressWarnings(
  yhat <- sapply( xg, local_quadratic_regression_smooth_Poisson, x, k, s, .15 ) )

plot( x, log( k/s + 1e-4 ), col="gray" )
lines( xg, yhat, col="red" )
lines( xg, log( true_fraction( xg ) ), col="blue" ) 
```
We get a lot of warnings aboutv failure of IRLS to converge for some values.

Instead of trying to debug this, we use the locfit package, where we have a ready-made
function for this purpose:

```{r}
library( locfit )

fit <- locfit( k ~ lp( x, h=.15), weights=s, family="poisson" )

plot( x, log( k/s + 1e-4 ), col="gray" )
lines( xg, log( predict( fit, xg ) ), col="red" )
lines( xg, log( true_fraction( xg ) ), col="blue" ) 

```

### Spline regression

#### Spline basis: first look

Another possibility is construct a smoothing curve as a linear combination of suitable 
basis function.

The function `bs` from the `splines` package produces a popular choice for a bsis function
known as "B splines".

We ask `bs` to provide a 7-dimensional basis and evaluate the basis functions
at the points `xg` (our sequence of 300 numbers between 0 and 1):

```{r}
library( splines )

head( cbind( x=xg,  bs( xg, df=7, intercept=TRUE ) ) )
```

Here's a plot

```{r}
knots <- seq( 0, 1, length.out=8 )
matplot( xg, bs( xg, intercept=TRUE, Boundary.knots=knots[c(1,8)], knots=knots[1:7] ), 
    type="l", lty="solid" ) 

abline( v=knots, col="gray" )
```
In a spline basis, the domain of the basis (here, the unit interval), is split into intervals, as 
indicated above by the gray lines. The boundaries of the intervals are marked with gray lines
above and called knots. As we specified 7 degrees of freedom, we have $7-1=6$ knots. The knots
can be places arbitrarily, but here, we have spaced them uniformly.

A B-spline basis, comprising basis functions $b_s$ (here, $s=1,\dots,10) is constructed to have the 
following properties:

- Each spline is a piecewise-polynomial function, i.e, between any two knots, it is a polynomial.

- The degree of the polynomial can be chosen; for `bs`, the default is 3.

- The basis peritions the unit, i.e., for every $x$ within the range of knots, $\sum_s b_s(x)=1$.

For a B-spline basis made of 3rd-degree polynomials, we further have:

- Each basis has support on at most 4 segments of the domain, as split by the knots.

- The basis functions are twice differentiable, but the third derivative is discontinuous at the knots.

#### Unpenalized spline regression

To deomstrate spline regression, we go back to our original example with Gaussian, rather than Poisson, noise:

```{R}
n <- 100
set.seed( 13245769 )
x <- runif( n )
y <- true_function( x ) + rnorm( n, sd=.1 )
```

We seek a smoothing curve $f(x)=\sum_s \beta_s b_s(x)$ that minimizes $\sum_i\left(y_i-f(x_i)\right)^2$.

We can find this by OLS regression:

```{r}
my_bs <- function(x) bs( x, intercept=TRUE, Boundary.knots=c(0,1), knots=seq(0,1,length.out=8)[2:7] )

fit <- lm.fit( my_bs(x), y ) 
fit$coefficients

plot( x, y )
lines( xg, true_function(xg), col="blue")
lines( xg, my_bs(xg) %*% fit$coefficients, col="red" )
```

If we increase the number of knots, the fit becomes better but also too "wiggly"

```{r}
my_bs <- function(x) bs( x, intercept=TRUE, Boundary.knots=c(0,1), knots=seq(0,1,length.out=20)[2:19] )

fit <- lm.fit( my_bs(x), y ) 
fit$coefficients

plot( x, y )
lines( xg, true_function(xg), col="blue")
lines( xg, my_bs(xg) %*% fit$coefficients, col="red" )
```

#### Curvature-penalized spline regression

We can solve this issue by adding a penalty term on curvature to our least-square sum:
$$\sum_i\left(y_i-f(x_i)\right)^2 + \lambda\int_0^1(f''(x))^2\text{d}x=\text{min!}$$

The function `

```{r}
fit <- smooth.spline( x, y, nknots=20 )

plot( x, y )
lines( xg, true_function(xg), col="blue")
lines( xg, predict( fit, xg )$y, col="red")
```

#### Construction for the B-spline basis

In an iterative construction (de Boor construction), we increase the polynomial degree in each
iteration. 

We start with a 0th-degree basis, where $b_{s,0}$ is simply 1 between the $s$-th and the $(s+1)$th knot
and 0 elsewhere.

```{r}
m <- 13
knots <- seq( 0, 1, length.out=m+1 )

bs0 <- sapply( 1:m, function(i) as.numeric( xg >= knots[i] & xg < knots[i+1] ) )

matplot( xg, bs0, type="l", lty="solid" )
abline( v=knots, col="gray" )
```

The, we construct the 1st-degree basis as follows: $b_{s,1}$ has support between the knot $s$ and knot $s+2$.
It is a linear interpolation between $b_{s,0}$ and $b_{s+1,0}$, where the "mixing ratio" between the
two 0th-degree basis function linearly goes from 1:0 to 0:1 while going along the support.

This yields triangles:

```{r}
bs1 <- sapply( 1:(m-2), function(s) 
  ( xg - knots[s]   ) / ( knots[s+1] - knots[s]   ) * bs0[,s] +
  ( knots[s+2] - xg ) / ( knots[s+2] - knots[s+1] ) * bs0[,s+1]  )

matplot( xg, bs1, type="l", lty="solid" )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs1), col="#00000030" )
```

The vertical gray lines indicate the knots, the horizontal one shows that the sum of all basis function
adds up to 1 in all the interior segments.

We repeat the process, using the same code, with changes to the indices: Now, the interpolation
runs with over two segments of each of the previous splines. As we perform linear interpolation over
linear functions we get piecewise quadratic polynomials, i.e., the following functions are pieced 
together from parabolas.

```{r}
bs2 <- sapply( 1:(m-3), function(s) 
  ( xg - knots[s]   ) / ( knots[s+2] - knots[s]   ) * bs1[,s] +
  ( knots[s+3] - xg ) / ( knots[s+3] - knots[s+1] ) * bs1[,s+1]  )

matplot( xg, bs2, type="l", lty="solid", ylim=c(0,1) )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs2), col="#00000030" )
```

As we interpolated between pieces that added to one, the result adds to one again, as indicated by the gray line. Again,
this only holds in the inner segments.

One more iteration to get to third degree polynomical pieces:

```{r}
bs3 <- sapply( 1:(m-4), function(s) 
  ( xg - knots[s]   ) / ( knots[s+3] - knots[s]   ) * bs2[,s] +
  ( knots[s+4] - xg ) / ( knots[s+4] - knots[s+1] ) * bs2[,s+1]  )

matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1) )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs3), col="#00000030" )
```

The basis still adds up to 1 in the inner segments.

We refactor our code to use a recursive function, taking the argument, `x`, the 
index of the basis function, `s`, the basis degree `k`, and the `knots` vector:

```{r}
bsf <- function( x, s, k, knots ) {
  if( k == 0 )
    as.numeric( x >= knots[s] & x < knots[s+1] )
  else
    ( x - knots[s]     ) / ( knots[s+k]   - knots[s]   ) * bsf( x, s,   k-1, knots ) +
    ( knots[s+k+1] - x ) / ( knots[s+k+1] - knots[s+1] ) * bsf( x, s+1, k-1, knots )
}
```

This function is known as the Cox-de Beer formula.

With it, we can reconstruct our last plot:

```{r}
m <- 13
knots <- seq( 0, 1, length.out=m+1 )

bs3 <- sapply( 1:(m-4), function(s) bsf( xg, s, 3, knots ) )

matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1) )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs3), col="#00000030" )
```
The basis produced by `bs` also adds up to 1 in the outer segments. This is achieved
by moving the outer knots where the sum is not 1 very close together. 

We rerun the code to show this, changing only the knot vector

```{r}
m <- 13
knots <- c( -.003, -.002, -.001, seq( 0, 1, length.out=m-6 ), 1.001, 1.002, 1.003, 1.004 )

bs3 <- sapply( 1:(m-4), function(s) bsf( xg, s, 3, knots ) )

matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1) )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs3), col="#00000030" )
```
Of course, we should form the limit of moving the outer knots exactly to 0 and 1, but that would require
us to think very carefully about where to put $<$ and where $\le$ in the $k=0$ case, and that is cumbersome.
Luckily for us, the authors of `bs` have done that for us.

```{r}
bs3 <- bs( xg, df=m-4, intercept=TRUE )
matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1) )
abline( v=knots, col="gray" )
lines( xg, rowSums(bs3), col="#00000030" )
```

#### Curvature of the spline basis

For the curvature penalization mentioned earlier, we need the second derivative
of the spline basis. As these are piece-wise 3rd-degree polynomials, we
expect the second derivative to be piecewise linear. We can calculate explicitely
the second derivative of the Cox-de Beer function, or we can rely on other people's work
and believe the formula given, e.g., in Wikipedia.

Still, we can quickly calculate the second derivative via finite differences. For the orginal, we just get
a repeat of a V-shaped curve:

```{r}
m <- 13
knots <- seq( 0, 1, length.out=m+1 )

bs3 <- sapply( 1:(m-4), function(s) bsf( xg, s, 3, knots ) )
matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1), main="degree-3 spline basis" )

nr <- nrow(bs3)
bs3xx <- bs3[1:(nr-2),] - 2*bs3[2:(nr-1),] + bs3[3:nr,]

matplot( xg[2:(nr-1)], bs3xx, type="l", lty="solid", main="2nd derivative" )
```
 
For the pulled-in outer knots, we get this:

```{r}
bs3 <- bs( xg, df=m-4, intercept=TRUE )
matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1), main="degree-3 spline basis" )

nr <- nrow(bs3)
bs3xx <- bs3[1:(nr-2),] - 2*bs3[2:(nr-1),] + bs3[3:nr,]

matplot( xg[2:(nr-1)], bs3xx, type="l", lty="solid", main="2nd derivative" )
```

For a given linear combination $f(x) = \sum_s \beta_s b_{s,3}(x)$, it is easy and
cheap to calculate the integral of its squared curvature:
$$\begin{align}
\int_0^1 \left(f(x)\right)^2\text{d}x &= 
\int_0^1\left(\sum_{s}\beta_sb_{s,3}\right)\left(\sum_{s'}\beta_sb_{s',3}\right)\text{d}x\\
&=\sum_{ss'} \beta_s\beta_{s'}\underbrace{\int_0^1b_{s,3}(x)b_{s',3}(x)\mathrm{d}x}_{=P_{ss'}}=
\vec\beta^\top P \vec \beta
\end{align}$$
The matrix $P$ can be easily calculated ahead of time and so, the objective of our 
minimization for curvature-penalized spline regression becomes:

$$\begin{align}
L=&\sum_i\left(y_i-f(x_i)\right)^2 + \lambda\int_0^1(f''(x))^2\text{d}x\\
=&(\vec{y}-X\vec\beta)^\top(\vec{y}-X\vec\beta) + \lambda \vec{β}^\top P \vec\beta\\
=&\vec y^\top\vec y - 2 \vec\beta^\top X^\top\vec y+\vec\beta^\top\left(
X^\top X + \lambda P\right)\vec\beta
\end{align}$$

Here, the matrix $X$ has matrix elements $X_{is}=b_{s,3}(x_i)$.

To  minimize this, we take the gradient w.r.t. $\vec\beta$:
$$ \nabla_{\vec\beta}L=-2X^\top\vec{y} + 2 \left(X^\top X + \lambda P\right)\vec\beta$$
Setting the gradient to zero, we obtain the OLS normal equation with the added penalty:
$$\left(X^\top X + \lambda P\right)\vec\beta = X^\top\vec{y} $$
As this is an equation of the form $A\vec x=\vec b$, it describes a system of linear equations
that can be solved with QR decomposition (i.e., Gauß elimination) in order to find $\vec\beta$.

This describes the math behind the `smooth.spline` function except for one point: a clever heuristic
to find a suitable value for the penalty strength parameter $\lambda$, which we will skip over.
(In brief: It turns out that a scale-free smoothing strength can be defined, which one then
multiplies with $\operatorname{tr}X^\top X / \operatorname{tr} P$ to obtain $\lambda$.)

#### P-Splines

An alternative to spline regression with curvature penality is P-spline smoothing.

Here, one uses a basis with rather very many basis functions (large $m$ in our notation),
lets all the basis functions keep the same shape (no "pulling in" of the boundary knots), and
replaced the curvature penalty with a penalty on the differences between the coefficients for adjacent 
splines:

$$ \|\vec y - X\vec\beta\|^2 - \lambda \sum_{s=1}^{m-1}\left(\beta_{s+1}-\beta_s\right)^2$$

It's easy to see that this penalty can be implemented using the same normal equation
as before when setting $P$ to 
$$P=\left( 
\begin{array}{r}
1  & -1 &    &    &  \\
-1 &  2 & -1 &    &  \\
   & -1 &  2 & -1 &  \\
   &    & -1 &  2 & -1 & \\
   &    &    & ⋱ &  ⋱ & ⋱ & \\
   &    &    &    & -1 &  2 & -1 & \\
   &    &    &    &    & -1 &  2 & -1 & \\
   &    &    &    &    &    & -1 &  1    
\end{array}
\right).$$

To demonstrate,w e first make a really large basis, which extends far out of the domain

```{r}
knots <- seq( -1, 2, length.out=100 )
m <- length(knots)-4
bs3 <- sapply( 1:m, function(s) bsf( xg, s, 3, knots ) )
matplot( xg, bs3, type="l", lty="solid", ylim=c(0,1), main="degree-3 spline basis" )
```
We remove the knots that have no influence inside the domain [0;1]:

```{r}
knots <- knots[
  min( which( sapply( 1:length(knots), function(l) bsf( 0, 1, 3, knots[l:length(knots)] ) ) > 0 ) ):
  max( which( sapply( 1:length(knots), function(l) bsf( 1, l-4, 3, knots[1:l] ) ) > 0 ) ) ]

m <- length(knots)-4

knots
```

Now, we calculate the values of the spline basis at the x coordinates of the
data points, and, for later use, also at our grid of equidistant points

```{r}
spx <- sapply( 1:m, function(s) bsf( x, s, 3, knots ) )
spxg <- sapply( 1:m, function(s) bsf( xg, s, 3, knots ) )
```

We construct the penalty matrix $P$
```{r}
pty <- diag(2,m)
pty[ row(pty) == col(pty)+1 ] <- -1
pty[ row(pty) == col(pty)-1 ] <- -1
pty[1,1] <- 1
pty[m,m] <- 1
image( 1:m, 1:m, pty, asp=1 )
```

Now, we solve the normal equations for $\lambda=1$:

```{r}
lambda <- 1
beta <- solve( t(spx) %*% spx + lambda * pty , t(spx) %*% y )
```

Here is the plot

```{r}
plot( x, y )
lines( xg, spxg %*% beta, col="red" )
lines( xg, true_function(xg), col="blue" )
```

Here, for a few more values of lambda:

```{r}
plot( x, y )
for( lambda in c( .01, .1, 1, 10, 100 ) ) {
  beta <- solve( t(spx) %*% spx + lambda * pty , t(spx) %*% y )
  lines( xg, spxg %*% beta, col="red" )
}  
lines( xg, true_function(xg), col="blue" )
```