11.1 The value of approximation

As schoolchildren, we were taught to admire the exactness of mathematics. The length of the hypotenuse of a right triangle with legs of 3 and 4 m is 5 m exactly, not a little less or a little more. Archimedes's 250 B.C.E. value of 22/7 for π was merely an upper bound for the ratio of a circle's circumference to its diameter. The exact value, known to one million digits by 1973, is something different and worth striving for.

Later in life, we learned that transcribing all 10 digits off the screen of a calculator is not really necessary; 3 or 4 is sufficient for most purposes. Yet we know that we can recompute all 10, should the need arise. We also came to appreciate the value of a back-of-the-envelope calculation, where the goal is merely to estimate the correct order of magnitude of the answer. Yet we view such calculations as imperfect—a tool to guide the development of a more accurate solution.

The situation in data analysis is fundamentally different. The accuracy of a result is a combination of methodological error, meaning error associated with the underlying theory and its computation, and observational error. Once methodological error is reduced to a level well below observation error, further improvement accomplishes little. The appropriate goal is to develop a methodology with acceptably small error, not one with none.

Of course, one might decide to err on the safe side; that is, to use only exact theories and to carry out all calculations to as many significant digits as possible. Superficially, such a strategy would not seem to be a bad one and, indeed, solutions achieved this way are certainly no worse than those that employ approximations. Yet the approach has serious limitations, over and above the obvious one that exact theories are unavailable for many imperfectly understood real-world phenomena. Approximations can bring simplicity, speed of computation, and adaptability to a solution which, in its exact form, is inscrutable, slow, and inflexible.

A simple method is one whose structure is sufficiently well-understood that its general behavior can be anticipated and its pitfalls identified and avoided. The grid search procedure (Section 4.6) for finding the minimum error solution is simple in this sense. This exhaustive search is easy to understand (and to code) and, although not completely foolproof, fails only when the search limits have been so poorly chosen that they fail to enclose the solution or when the solution varies over scale lengths smaller than the grid spacing. Linear theories of the form $\mathbf{Gm}=\mathbf{d}$ are simple, too. The matrix G may be large and complicated, yet it is straightforward to create and interpret. Furthermore, its least squares solution (Section 4.7) will succeed except in cases that can be easily detected (e.g., when the matrix inverse is near-singular) and corrected (e.g., by adding prior information). As we will see below, approximations that linearize an exact nonlinear theory have wide application.

Approximations can also improve the speed of computation. Speed is an extremely important issue in very large problems that challenge the capabilities of the current generation of computers and in real-time applications, where a solution is needed immediately after the data becomes available. A Global Positioning System (GPS) receiver would be of limited utility in an automobile if it took 10 min to determine a location!

Finally, some data analysis scenarios need to adapt to evolving conditions that affect the character of the data. The character of a river hydrograph, for example, may evolve significantly over the years as its watershed becomes urbanized. The methodology needed to predict discharge from precipitation may need to be correspondingly updated. Some approximate methods are particularly well-suited for incorporating machine learning.

11.2 Polynomial approximations and Taylor series

A polynomial can always be designed to behave similarly to a smooth function y(t) in the vicinity of a specified point t₀. This assertion can be demonstrated by constructing a polynomial y_p(t) that has the same value, first derivative, second derivative, etc. at this point. The polynomial becomes a better and better approximation to the function as derivatives of higher and higher order are matched (Figure 11.1). A polynomial with unknown coefficients c_i is

$y_p\left(t\right)=c_0+c_1\left(t-t_0\right)+c_2{\left(t-t_0\right)}^2+c_3{\left(t-t_0\right)}^3+\cdots \dots$

and its derivates are

$\begin{array}{l}\frac{\mathrm{d}{y}_p}{\mathrm{d}t}=c_1+2c_2\left(t-t_0\right)+3c_3{\left(t-t_0\right)}^2+\dots \hfill \\ \frac{{\mathrm{d}}^2{y}_p}{\mathrm{d}{t}^2}=2c_2+6c_3\left(t-t_0\right)+\dots \hfill \\ \mathrm{e}\mathrm{t}\mathrm{c}\text{.}\hfill \end{array}$

When evaluated at the point $t-t_0$, these functions each depends upon a single constant:

$y_p\left(t_0\right)=c_0\mathrm{and}{\left.\frac{\mathrm{d}{y}_p}{\mathrm{d}t}\right|}_{t_0}=c_1\mathrm{and}{\left.\frac{{\mathrm{d}}^2{y}_p}{\mathrm{d}{t}^2}\right|}_{t_0}=2c_2\mathrm{e}\mathrm{t}\mathrm{c}\text{.}$

After solving for the constants and inserting them into Equation (11.1), a polynomial y_p(t) is obtained, whose value and derivatives match the smooth function y(t) at the point t₀:

$y_p\left(t\right)=y\left(t_0\right)+{\left.\frac{\mathrm{d}y}{\mathrm{d}t}\right|}_{t_0}\left(t-t_0\right)+\frac{1}{2}{\left.\frac{{\mathrm{d}}^{2}y}{\mathrm{d}{t}^2}\right|}_{t_0}{\left(t-t_0\right)}^2+\dots$

This polynomial can be shown to converge to the smooth function when the number of terms becomes indefinitely large; that is, $y_p\left(t\right)\to y\left(t\right)$ (at least for a finite interval of the t axis containing t₀). This result is known as Taylor theorem and Equation (11.4) is known as the Taylor series representation of the function y(t). As we will show below, Taylor series play a critical role in many approximation methods.

11.3 Small number approximations

An important class of approximations uses just the first two terms of the Taylor series to represent a function in the neighborhood of a point $t=t_0$, since the higher order terms are typically negligible there. Consider the function $y\left(t\right)={\left(1\pm t\right)}^n$. At the point $t_0=0$, it has value $y\left(0\right)=1$ and first derivative ${\left.\mathrm{d}y/\mathrm{d}t\right|}_0={\left.\pm n{\left(1\pm t\right)}^{n-1}\right|}_0=\pm n$. Inserting these values into Equation (11.4) yields

${\left(1\pm t\right)}^n\approx 1\pm \mathit{nt}$

This approximation is surprisingly accurate. For instance, ${\left(1+0.04\right)}^{1/2}=1.0198$, whereas $\left(1+\mathrm{½}\times 0.04\right)=1.02$; the difference is only 0.02 %.

Two additional examples are the functions sin t and cos t in the neighborhood of the point $t_0=0$. The sine has a value of 0, a first derivative of 1, and a second derivative of 0 at this point, while the cosine has a value of 1, a first derivative of 0, and a second derivative of $-1$ there. Inserting these values into Equation (11.4) yields

$sint\approx t\mathrm{and}cost\approx 1-\frac{1}{2}{t}^2$

These and other small number approximations can be used to simplify and speed up data analysis problems (see Crib Sheet 11.1).

11.4 Small number approximation applied to distance on a sphere

A common problem encountered when working with geographical data is to determine the great circle distance r between two points on a sphere (such as the Earth). Spherical trigonometry can be used to show that this distance, measured in degrees of arc, is given by

$cosr=sin{\lambda }_{1}sin{\lambda }_2+cos{\lambda }_{1}cos{\lambda }_{2}cos\mathrm{\Delta }L$

Here, λ₁ and λ₂ are the latitudes of the two points, respectively; L₁ and L₂ are their longitudes; and $\mathrm{\Delta }L=L_2-L_1$. Six distinct trigonometric functions must be evaluated in order to determine r—a time-consuming process. A small r approximation can reduce the count of functions. The first step is to define the difference in latitude as $\mathrm{\Delta }\lambda ={\lambda }_2-{\lambda }_1$ and the mean latitude as $\overline{\lambda }=\frac{1}{2}\left({\lambda }_2+{\lambda }_1\right)$. Standard trigonometric identities are then used to rewrite Equation (11.7) in terms of these quantities:

$cosr=\frac{1}{2}cos\mathrm{\Delta }\lambda -\frac{1}{2}cos\overline{\lambda }+\frac{1}{2}+\frac{1}{2}cos\mathrm{\Delta }\lambda cos\mathrm{\Delta }L+{cos}^2\overline{\lambda }cos\mathrm{\Delta }L-\frac{1}{2}cos\mathrm{\Delta }L$

By assumption, ΔL, Δλ, and r are all small. After applying the small number approximations of Equation (11.6) and after considerable algebra, the approximation is found to be

$r^2\approx {\left(\mathrm{\Delta }\lambda \right)}^2+{\left(\mathrm{\Delta }L\right)}^2{cos}^2\overline{\lambda }-{\left(\mathrm{\Delta }\lambda \right)}^2{\left(\mathrm{\Delta }L\right)}^2\left[\frac{1}{4}-\frac{{cos}^2\overline{\lambda }}{6}\right]$

The first two terms on the right-hand side represent the Euclidian distance between the points; that is, distance as measured on a plane. The last term corrects this flat-earth distance for the curvature of the surface. Only two functions, a cosine and a square root, need to be evaluated in order to determine r, which is a factor-of-three reduction in effort compared with the exact formula. Furthermore, the approximation is very accurate, at least out to distances of a few degrees (Figure 11.2).

11.5 Small number approximation applied to variance

A commonly encountered problem is that of estimating the variance of a nonlinear function of the model parameters. As an example, suppose that a least squares procedure estimates an angular frequency m^est with variance σ_m², but we would rather state confidence bounds for the period $T=2\pi /m$. As discussed in Chapter 3, this problem can be solved exactly by assuming that m is normally distributed, working out the probability density function p(T), and then calculating its mean and variance. However, the exact procedure is difficult and time-consuming; the approximation that is developed here is accurate when $m^{\mathrm{e}\mathrm{s}\mathrm{t}}\gg {\sigma }_m$.

The idea is to examine how a small fluctuation Δm in frequency causes a small fluctuation ΔT in period. Writing $m=m^{\mathrm{e}\mathrm{s}\mathrm{t}}+\mathrm{\Delta }m$ and $T=T^{\mathrm{e}\mathrm{s}\mathrm{t}}+\mathrm{\Delta }T$ and inserting them into the formula relating frequency and period yield

$\begin{array}{c}\hfill T=\frac{2\pi }{m}=2\pi {\left[m^{\mathrm{e}\mathrm{s}\mathrm{t}}+\mathrm{\Delta }m\right]}^{-1}=\frac{2\pi }{m^{\mathrm{e}\mathrm{s}\mathrm{t}}}{\left[1+\frac{\mathrm{\Delta }m}{m^{\mathrm{e}\mathrm{s}\mathrm{t}}}\right]}^{-1}\hfill \\ \hfill \approx \frac{2\pi }{m^{\mathrm{e}\mathrm{s}\mathrm{t}}}\left[1-\frac{\mathrm{\Delta }m}{m^{\mathrm{e}\mathrm{s}\mathrm{t}}}\right]=\frac{2\pi }{m^{\mathrm{e}\mathrm{s}\mathrm{t}}}-\frac{2\pi }{{\left(m^{\mathrm{e}\mathrm{s}\mathrm{t}}\right)}^2}\mathrm{\Delta }m\hfill \end{array}$

After equating T^est with 2π/m^est, small fluctuations in period and frequency are found to be related through

$\mathrm{\Delta }T\approx \frac{2\pi }{{\left(m^{\mathrm{e}\mathrm{s}\mathrm{t}}\right)}^2}\mathrm{\Delta }m$

If the fluctuations in Δm have a variance of σ_m², then according to the usual rules of error propagation, the fluctuations in ΔT will have variance:

${\sigma }_T^2\approx {\left[\frac{2\pi }{{\left(m^{\mathrm{e}\mathrm{s}\mathrm{t}}\right)}^2}\right]}^2{\sigma }_m^2$

The period T has the same variance, since it differs from ΔT only by an additive constant. As an example, we consider the case $m^{\mathrm{e}\mathrm{s}\mathrm{t}}=2\pi \times 1.3$ rad/s, ${\sigma }_{\omega }=0.2$ rad/s, which leads to $T^{\mathrm{e}\mathrm{s}\mathrm{t}}=0.769$ s and ${\sigma }_T=0.019$ s, estimates that agree well with a numerical simulation (Figure 11.3).

11.6 Taylor series in multiple dimensions

In a typical data analysis problem, the predicted data d^pre(m) is a function of model parameters m. The Taylor series for d^pre(m) is a straightforward generalization of the one-dimensional series and can be shown to be

$\begin{array}{l}{d}_i^{\mathrm{p}\mathrm{r}\mathrm{e}}\left(\mathbf{m}\right)=d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}\left({\mathbf{m}}_0\right)+{\displaystyle \sum _{j=1}^M}{\left.\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial m_j}\right|}_{{\mathbf{m}}_0}\left(m_j-m_{0j}\right)\\ +\frac{1}{2}{\displaystyle \sum _{\mathit{j}=1}^{\mathit{M}}}{\displaystyle \sum _{\mathit{k}=1}^{\mathit{M}}}{\left.\frac{{\partial }^2{\mathit{d}}_{\mathit{i}}^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial {\mathit{m}}_{\mathit{j}}\partial {\mathit{m}}_{\mathit{k}}}\right|}_{{\mathbf{m}}_0}\left({\mathit{m}}_{\mathit{j}}-{\mathit{m}}_{0\mathit{j}}\right)\left({\mathit{m}}_{\mathit{k}}-{\mathit{m}}_{0\mathit{k}}\right)+\dots \hfill \end{array}$

The sequence of terms is the same as in the one-dimensional case: a constant term; a linear term, a quadratic term, and so forth. Derivatives of the same order appear in the same places in both formulas, as well: the linear term is multiplied by a first derivative; the quadratic term by a second derivative; and so forth. The main complication is that both the data and the model parameters are subscripted quantities, so summations are involved. Note that the first derivative has two subscripts and is therefore a matrix, say G⁽⁰⁾:

$G_{ij}^{\left(0\right)}={\left.\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial m_j}\right|}_{{\mathbf{m}}_0}$

The matrix G is called the linearized data kernel. The Taylor series is a little simpler when a scalar function of the model parameters, such as the prediction error E, is being considered:

$\begin{array}{ll}E\left(\mathbf{m}\right)=& E\left({\mathbf{m}}_0\right)+{\displaystyle \sum _{j=1}^M}{\left.\frac{\partial E}{\partial m_j}\right|}_{{\mathbf{m}}_0}\left(m_j-m_{0j}\right)\hfill \\ & +\frac{1}{2}{\displaystyle \sum _{j=1}^M}{\displaystyle \sum _{k=1}^M}{\left.\frac{{\partial }^{2}E}{\partial m_j\partial m_k}\right|}_{{\mathbf{m}}_0}\left(m_j-m_{0j}\right)\left(m_k-m_{0k}\right)+\dots \hfill \end{array}$

The first derivative has one subscript and so is a vector, say b⁽⁰⁾, and the second derivative has two subscripts and so is a matrix, say B⁽⁰⁾:

$b_j^{\left(0\right)}={\left.\frac{\partial E}{\partial m_j}\right|}_{{\mathbf{m}}_0}\mathrm{and}{B}_{ij}^{\left(0\right)}={\left.\frac{{\partial }^{2}E}{\partial m_j\partial m_k}\right|}_{{\mathbf{m}}_0}$

The quantities b and B are called the gradient vector and the curvature matrix, respectively. Equations (11.13) and (11.15) can then be written in vector notation as

$\begin{array}{l}{\mathbf{d}}^{\mathrm{p}\mathrm{r}\mathrm{e}}\approx {\mathbf{d}}_0^{\mathrm{p}\mathrm{r}\mathrm{e}}+{\mathbf{G}}^{\left(0\right)}\mathrm{\Delta }\mathbf{m}\hfill \\ E\approx E_0+{\mathbf{b}}^{\left(0\right)\mathrm{T}}\mathrm{\Delta }\mathbf{m}+\frac{1}{2}{\left(\mathrm{\Delta }\mathbf{m}\right)}^{\mathrm{T}}{\mathbf{B}}^{\left(0\right)}\mathrm{\Delta }\mathbf{m}\hfill \\ \mathrm{with}{\mathbf{d}}_0^{\mathrm{p}\mathrm{r}\mathrm{e}}={\mathbf{d}}^{\mathrm{p}\mathrm{r}\mathrm{e}}\left({\mathbf{m}}_0\right)\mathrm{and}{E}_0=E\left({\mathbf{m}}_0\right)\mathrm{and}\mathrm{\Delta }\mathbf{m}=\mathbf{m}-{\mathbf{m}}_0\hfill \end{array}$

11.7 Small number approximation applied to covariance

The procedure for estimating variance (Section 11.5) can be generalized to the nonlinear vector function T(m), providing a way to estimate the covariance matrix C_T. The first step is to expand the function T(m) in a Taylor series around the point m^est and keep only the first two terms. The resulting linear approximation relates small fluctuations in m to small fluctuations in T:

$\begin{array}{l}\mathrm{\Delta }\mathbf{T}=\mathbf{M}\mathrm{\Delta }\mathbf{m}\hfill \\ \mathrm{with}\mathrm{\Delta }\mathbf{m}=\mathbf{m}-{\mathbf{m}}^{\mathrm{e}\mathrm{s}\mathrm{t}}\mathrm{and}\mathrm{\Delta }\mathbf{T}=\mathbf{T}-\mathbf{T}\left({\mathbf{m}}^{\mathrm{e}\mathrm{s}\mathrm{t}}\right)\mathrm{and}{M}_{ij}={\left.\frac{\partial T_i}{\partial m_j}\right|}_{{\mathbf{m}}^{\mathrm{e}\mathrm{s}\mathrm{t}}}\hfill \end{array}$

The standard error propagation rule (Section 3.12) then gives ${\mathbf{C}}_T=\mathbf{M}{\mathbf{C}}_m{\mathbf{M}}^{\mathrm{T}}$.

11.8 Solving nonlinear problems with iterative least squares

The error E(m) and its derivatives can be computed as long as the theory d^pre(m) is known, irrespective of whether it is linear or nonlinear. Consequently, we can apply the principle of least square to nonlinear problems; the solution m^est is the one that minimizes the error E(m), or equivalently, the one that solves $\partial E/\partial m_i=0$. Unfortunately, this set of nonlinear equations is usually difficult to solve exactly. However, if we can guess a trial solution m₀ that is close to the minimum error solution, then we can use Taylor's theorem to approximate E(m) as a low order polynomial centered about this point. If m₀ is close enough to the minimum that a quadratic approximation will suffice, then the process of solving $\partial E/\partial m_i=0$ is very simple, because the derivative of a quadratic function is a linear function. Differentiating the expression for E in Equation (11.17) and setting the result to zero yield

$0\approx {\mathbf{b}}^{\left(0\right)}+{\mathbf{B}}^{\left(0\right)}\mathrm{\Delta }\mathbf{m}\mathrm{or}\mathrm{\Delta }\mathbf{m}\approx -{\left[{\mathbf{B}}^{\left(0\right)}\right]}^{-1}{\mathbf{b}}^{\left(0\right)}$

This equation enables us to find an updated solution, $\mathbf{m}={\mathbf{m}}_0+\mathrm{\Delta }\mathbf{m}$, that is closer to the minimum than is m₀. This process can be iterated indefinitely, to provide a sequence of ms that, under favorable circumstances, will converge to the minimum error solution. It is sometimes referred to as Newton's method. A limitation is that the curvature matrix B must be calculated, in addition to the gradient vector b. Calculating this matrix may be difficult.

In the special case of the linear theory ${\mathbf{d}}^{\mathrm{p}\mathrm{r}\mathrm{e}}=\mathbf{Gm}$, the error is

$E={\left[{\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}-\mathbf{Gm}\right]}^{\mathrm{T}}\left[{\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}-\mathbf{Gm}\right]={\mathbf{d}}^{\mathrm{obsT}}{\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}-2{\mathbf{d}}^{\mathrm{obsT}}\mathbf{Gm}+{\mathbf{m}}^{\mathrm{T}}{\mathbf{G}}^{\mathrm{T}}\mathbf{Gm}$

The unknown quantities m₀, b, and B are found by comparison with Equation (11.17):

${\mathbf{m}}_0=0\mathrm{and}\mathbf{b}=-2{\mathbf{G}}^{\mathrm{T}}{\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}\mathrm{and}\mathbf{B}=2{\mathbf{G}}^{\mathrm{T}}\mathbf{G}$

Inserting these values into Equation (11.19) yields the familiar least squares solution: $\mathbf{m}={\left[{\mathbf{G}}^{\mathrm{T}}\mathbf{G}\right]}^{-1}{\mathbf{G}}^{\mathrm{T}}{\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}$. This correspondence suggests the strategy of approximating the curvature matrix as ${\mathbf{B}}^{\left(0\right)}\approx {\mathbf{G}}^{\left(0\right)\mathrm{T}}{\mathbf{G}}^{\left(0\right)}$, in which case the procedure for updating a trial solution m^(k) is (Tarantola and Valette, 1982; see also Menke, 2014)

$\begin{array}{l}\mathrm{\Delta }\mathbf{d}={\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}-{\mathbf{d}}^{\mathrm{p}\mathrm{r}\mathrm{e}}\left({\mathbf{m}}^{\left(k\right)}\right)\hfill \\ G_{ij}^{\left(k\right)}={\left.\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial m_j}\right|}_{{\mathbf{m}}^{\left(k\right)}}\hfill \\ \mathrm{\Delta }\mathbf{m}={\left[{\mathbf{G}}^{\left(k\right)\mathrm{T}}{\mathbf{G}}^{\left(k\right)}\right]}^{-1}{\mathbf{G}}^{\left(k\right)\mathrm{T}}\mathrm{\Delta }\mathbf{d}\hfill \\ {\mathbf{m}}^{\left(k+1\right)}={\mathbf{m}}^{\left(k\right)}+\mathrm{\Delta }\mathbf{m}\hfill \end{array}$

The covariance of the solution is approximately

${\mathbf{C}}_m={\sigma }_d^2{\left[{\mathbf{G}}^{\left(k_{\text{max}}\right)\mathrm{T}}{\mathbf{G}}^{\left(k_{\text{max}}\right)}\right]}^{-1}$

where k_max signifies the final iteration.

This procedure is known as iterative least squares. An important issue is when to stop iterating. Possibilities include when the error of the fit, as quantified by its posterior variance, declines below a specified value that represents the fit being acceptably good; or when the error no longer decreases significantly between iterations; that is, when $\mathrm{\Delta }E=E\left(m^{\left(k\right)}\right)-E\left(m^{\left(k+1\right)}\right)$ declines below a specified value; or when the solution no longer changes significantly between iterations; that is {[Δm]^T[Δm]}^1/2 declines below a specified value.

Prior information, represented by the linear equation $\mathbf{H}\mathbf{m}={\mathbf{h}}^{\mathrm{p}\mathrm{r}\mathrm{i}}$, can be added to the procedure in order to generalize it. The only nuance is that the prior information is satisfied by the model parameters ${\mathbf{m}}^{\left(k+1\right)}$ and not by the model perturbation Δm. Inserting ${\mathbf{m}}^{\left(k+1\right)}={\mathbf{m}}^{\left(k\right)}+\mathrm{\Delta }\mathbf{m}$ into the prior information equation yields

$\mathbf{H}\mathrm{\Delta }\mathbf{m}=\mathbf{h}-\mathbf{H}{\mathbf{m}}^{\left(k\right)}$

See Crib Sheet 11.2 for the complete formulation.

11.9 Fitting a sinusoid of unknown frequency

Suppose that the data consists of a single sinusoid superimposed on a background level, and that the amplitude, phase, and frequency of the sinusoid, as well as the background level, is unknown. This scenario is described by an equation that is nonlinear in the model parameters:

$d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}=m_1\overline{d}+m_{2}Asin\left(m_4{\omega }_a{t}_i\right)+m_{3}Acos\left(m_4{\omega }_a{t}_i\right)$

The constants $\overline{d}$, A, and ω_a have been introduced in order to normalize the size of the model parameters, which will be in the $\pm 1$ range (or close to it) when these constants are properly chosen. The matrix G^(k) has elements:

$\begin{array}{l}{G}_{i1}^{\left(k\right)}=\overline{d}\hfill \\ G_{i2}^{\left(k\right)}=Asin\left(m_4^{\left(k\right)}{\omega }_a{t}_i\right)\hfill \\ G_{i3}^{\left(k\right)}=Acos\left(m_4^{\left(k\right)}{\omega }_a{t}_i\right)\hfill \\ G_{i3}^{\left(k\right)}=m_2^{\left(k\right)}A{\omega }_a{t}_{i}cos\left(m_4^{\left(k\right)}{\omega }_a{t}_i\right)-m_3^{\left(k\right)}A{\omega }_a{t}_{i}sin\left(m_4^{\left(k\right)}{\omega }_a{t}_i\right)\hfill \end{array}$

This model can be applied to the Black Rock Forest temperature data, which has a pronounced annual cycle. We set $\overline{d}$ to the mean of the data, A to half its range, and ω_a to the frequency 2π/365 rad/day. A reasonable trial solution is $\mathbf{m}={\left[1.0,0.1,-0.9,1.0\right]}^{\mathrm{T}}$. (The choice $m_2=0.1$, $m_3=-0.9$ implies that the highest temperature is in summer.) The iterative procedure of Equation (11.22) is then used to refine this estimate. The iteration process is terminated when the change in model parameters, from one iteration to the next, drops below a predetermined value (in this example, ${10}^{-4}$).

This method produces an estimated period of $365.61\pm 0.06$ days (95%), where the confidence interval was computed by the method of Section 11.5. Whether the nonlinear fit (Figure 11.4) provides a better estimate of the period that can be determined from standard amplitude spectral density analysis is debatable. The annual peak in the amplitude spectral density is broad, owing to the relatively few annual oscillations in the temperature time series (only 11). Nevertheless, its center is very close to the value determined by the nonlinear analysis (Figure 11.5).

11.10 The gradient method

The gradient vector $b_i^{\left(k\right)}=\partial E^{\left(k\right)}/\partial m_i$ represents the slope of the error function E(m) in the vicinity of the trial solution m^(k). It points in the direction in which the error most rapidly increases, which is to say, directly away from the direction in which m^(k) must be perturbed to lower the error. For this reason, its appearance in the rule for updating a trial solution m^(k) (Equation 11.19) is unsurprising. This relationship is further examined by rewriting the update rule as

$\begin{array}{l}\mathrm{\Delta }\mathbf{m}=-{\left[{\mathbf{B}}^{\left(k\right)}\right]}^{-1}{\mathbf{b}}^{\left(k\right)}={\mathbf{M}}^{\left(k\right)}{\mathbf{\nu }}^{\left(k\right)}\mathrm{with}\mathbf{M}=\left|{\mathbf{b}}^{\left(k\right)}\right|{\left[{\mathbf{B}}^{\left(k\right)}\right]}^{-1}\hfill \\ \mathrm{and}\mathbf{\nu }=-{\mathbf{b}}^{\left(k\right)}/\left|{\mathbf{b}}^{\left(k\right)}\right|\hfill \end{array}$

Here |b| is the length of b. This rule has a simple interpretation: the vector ν^(k) is the downslope direction; that is, the direction in which m^(k) should be perturbed to most reduce the error. The matrix M^(k) encodes information about the size of the perturbation needed to reach the minimum in the error E(m), and although it also can change the direction of the perturbation, this effect is usually secondary.

The gradient vector b^(k) can be computed easily from the linearized data kernel G^(k):

$\begin{array}{l}{b}_i^{\left(k\right)}={\left.\frac{\partial E}{\partial m_i}\right|}_{{\mathbf{m}}^{\left(k\right)}}=\frac{\partial }{\partial m_i}{\displaystyle \sum _{j=1}^N}{\left(d_j^{\mathrm{o}\mathrm{b}\mathrm{s}}-d_j^{\mathrm{p}\mathrm{r}\mathrm{e}}\right)}^2=-2G_{ji}^{\left(k\right)}\left(d_j^{\mathrm{o}\mathrm{b}\mathrm{s}}-d_j^{\mathrm{p}\mathrm{r}\mathrm{e}}\right)\hfill \\ \mathrm{or}{\mathbf{b}}^{\left(k\right)}=-2{\mathbf{G}}^{\left(k\right)\mathrm{T}}\left({\mathbf{d}}^{\mathrm{o}\mathrm{b}\mathrm{s}}-{\mathbf{d}}^{\mathrm{p}\mathrm{r}\mathrm{e}}\right)\hfill \end{array}$

The calculation of the matrix M^(k) is more difficult because it involves taking a matrix inverse. A trial solution would be easier to update if it could be omitted from the formula. The gradient method approximates M^(k) as αI, where α is an unknown step size. An initial guess for α is made at the start of the error minimization process and is used to tentatively update the trial solution according to the rule ${\mathbf{m}}^{\left(k+1\right)}={\mathbf{m}}^{\left(k\right)}+\alpha {\mathbf{\nu }}^{\left(k\right)}$. The iteration process continues if the error $E^{\left(k+1\right)}$ has decreased. However, if the error has increased, the new solution has overshot the minimum because the step size is too big. The step size is decreased, say by replacing α with α/2, and another tentative solution is tried.

The main limitation of the gradient method, compared to iterative least squares, is that more iteration is needed to achieve an acceptable solution. While each step moves the solution towards the minimum, the step size has not been correctly set to move it to the minimum, so convergence is much slower. When applied to Black Rock Forest temperature problem described in the previous section, about 3500 iterations of the gradient method are needed to provide an acceptable solution (Figure 11.6) whereas fewer than 10 iterations of the iterative least squares method are needed for a solution with similar accuracy.

The least squares error E(m) is the sum of many individual errors:

$E\left(\mathbf{m}\right)={\displaystyle \sum _{i=1}^N}{e}_i^2\mathrm{where}{e}_i=d_i^{\mathrm{o}\mathrm{b}\mathrm{s}}-d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}\left(\mathbf{m}\right)$

In many practical cases, the number of individual errors is very large (N ≈ 100,000 in the Black Rock Forest case). The updating rule ${\mathbf{m}}^{\left(k+1\right)}={\mathbf{m}}^{\left(k\right)}+\alpha {\mathbf{\nu }}^{\left(k\right)}$ is only approximate. The omission of some of the individual errors from the formula for ν^(k) makes it somewhat more approximate, but as long as ν^(k) is not too inaccurate, each step will still move the solution towards the minimum. Furthermore, if a different random subset of individual errors is used in each step, the entire dataset can be cycled through during the course of the solution. This approximation is called the stochastic gradient method. In the case of the Black Rock Forest dataset, a reduction of the number of individual errors by a factor of 1000 still leads to an acceptable solution (Figure 11.6).

11.11 Precomputation of a function and table lookups

Many data analysis methods require that the same function be evaluated numerous times. If the function is complicated but has only one or two arguments of known range, then precalculating it and storing its values in a table may prove computationally efficient. As long as the time needed to perform a table lookup is less than the time needed to evaluate the function, computation time is reduced. Some accuracy is lost, too, since a table lookup provides only an approximate value of the function, but in many cases this inaccuracy is overwhelmed by other sources of error (and especially measurement error) that enter into the problem.

The lookup table for a one-dimensional function d(x) is just the time series $d_k=d\left(x_k\right)$ with $x_k=k\mathrm{\Delta }x+x_{\text{min}}\left(1<k<K\right)$. The range of x_k must encompass all values of x that need to be estimated, and the sampling must be small enough to faithfully represent fluctuations in the function. A simple estimate of the function d(x) is the value of the corresponding table entry, d_n with $n=\mathrm{floor}\left(\left(z-z_{\text{min}}\right)/\mathrm{\Delta }x\right)+1$. Here the function floor(x) is the largest integer smaller than x. Alternatively, d(x) could be estimated by linearly interpolating between the two bracketing d_n and $d_{n+1}$, though the interpolation process adds computation time.

As an example, we consider the problem of using a grid search to determine two model parameters (m₁, m₂) where the data d_i(t_i) obeys

$d_i\left(t_i\right)=sin\left\{\pi sin\left[\pi x_{i}sin\pi \left(1-x_i^2\right)\right]\right\}\mathrm{with}{x}_i=m_1+m_2{t}_i$

Note that d_i(x_i) is a complicated function of just one variable x_i(t_i). In order to set up the lookup table, we need to know the range of plausible values of the model parameters (m₁, m₂) and time t. Let us suppose that they are $0\le m_1\le 1$, $0\le m_2\le 1$, and $0\le t\le 1$. These ranges allow us to compute the range for the xs in the lookup table as $0\le x\le 2$. The version of the grid search that uses the lookup table executes in only about half the time of the version that directly computes d_i(t_i) each time it is needed (Figure 11.7).

Lookup tables are applicable to functions of two or more variables, but tables of more than two dimensions are seldom useful, because the time needed to construct them is very large.

11.12 Artificial neural networks

Suppose that the function d(x) is not accurately known. One strategy is to start with an initially poor estimate of it and improve it as new information becomes available. One advantage of using a lookup table to represent the function is that a table is easily updated. The values of its elements can be trivially changed to reflect new information. However, a table is also inflexible, in the sense that, once defined, the width Δx of its elements cannot easily be changed to reflect new information about the scale length over which d(x) varies. Furthermore, the value of d(x) jumps abruptly as an interval boundary is crossed, which may violate prior information about the function's smoothness. In this section, a new approximation, called the artificial neural network (or neural net, for short), is introduced. It shares some similarity with a lookup table but is more adaptable and smooth. (Notice that the attribute of the lookup table upon which we are focusing is updatability, not computation speed; neural nets are not especially speedy.)

An arbitrary function d(x) can be represented schematically as a row of three boxes, with interconnecting lines that represent information flowing from left to right (Figure 11.8A). In this network representation, the left box represents input x, the right box represents output d(x), and the middle box represents the workings of the function, which may be arbitrarily complicated. The middle box encapsulates (or hides) all the details of the function, and for this reason is said to be hidden. The table approximation replaces the workings in the middle box with a simple table lookup (Figure 11.8B). Since each element of the table specifies the value of the function d(x) in a distinct interval of the x-axis, the process of interrogating the table lookup can be viewed as summing boxcar or tower functions, each of which is constant in the interval and zero outside of it (Figure 11.8C).

The left and right edges of the each table entry can be made separate by viewing a tower as the sum of two step functions:

$d_{\mathrm{c}}H\left(w_{\mathrm{L}}x+b_{\mathrm{L}}\right)-d_{\mathrm{c}}H\left(w_{\mathrm{R}}x+b_{\mathrm{R}}\right)$

Here H(z) (with $z=wx+b$) is the Heaviside step function, defined as zero when $z<0$ and unity when $z>0$. The weights w and the biases b parameterize the location of the edges, with the left edge at $x_{\mathrm{L}}=-b_{\mathrm{L}}/w_{\mathrm{L}}$ and the right edge at $x_{\mathrm{R}}=-b_{\mathrm{R}}/w_{\mathrm{R}}$. The constant d_c specifies the height of the tower (Figure 11.9). In a lookup table, the edges of adjacent towers match one another; that is, $x_{\mathrm{L}}^{\left(i\right)}=x_{\mathrm{R}}^{\left(i-1\right)}$ and $x_{\mathrm{R}}^{\left(i\right)}=x_{\mathrm{L}}^{\left(i+1\right)}$ (where the superscript consecutively numbers the towers). However, in a neural net, this requirement is relaxed and step functions are allowed to overlap in any fashion.

The issue of smoothness is addressed by replacing the step function H(z) by the sigmoid function:

$\sigma \left(z\right)=\frac{1}{1+exp\left(-z\right)}$

Like the step function, this function asymptotes to zero and unity, respectively, as $z\to \pm \infty$ and has a transition centered on $z=0$ (or $x_0=-b/w$). Unlike the step function, the sigmoid function is smooth. The parameter w controls the sharpness of the transition, with a maximum slope at x₀ of $s=\mathrm{d}\sigma /\mathrm{d}x=w/4$ (Figure 11.10).

11.13 Information flow in a neural net

A neural net consists of L columns (or layers) of boxes, with the kth layer containing N^(k) boxes. Because the neural net approximation was motivated by studies of information flow in animal brains, the boxes are called neurons. Information flows from left to right along connections, denoted by line segments connecting the boxes in adjacent layers. Neuron i in layer k has one parameter associated with it, its bias b_i^(k). The connection between neuron i in layer k and neuron j in layer $\left(k-1\right)$ has one parameter associated with it, its weight w_ij^(k); the absence of a connection is indicated by a zero weight. Neuron i in layer k also has an input value z_i^(k) and an output value (or activity) a_i^(k). The activities of neurons in layer 1 represent the input to the function and the activities of the neurons in layer L represent the output of the function. In the one-dimensional case considered above, layer 1 has one neuron with activity x and layer L has one neuron with activity d(x). However, neural nets can handle a multidimensional function d(x) simply by having multiple input and output neurons. The rule for propagating information between one layer and the next is

$\begin{array}{l}\begin{array}{l}\mathrm{Input}\mathrm{of}\hfill \\ \mathrm{neuron}i\\ \mathrm{on}\mathrm{layer}k\end{array}=\begin{array}{l}\mathrm{weighted}\mathrm{sum}\mathrm{of}\hfill \\ \mathrm{activities}\mathrm{of}\mathrm{neurons}\\ \mathrm{on}\mathrm{layer}\left(k-1\right)\end{array}+\begin{array}{l}\mathrm{bias}\mathrm{of}\hfill \\ \mathrm{neuron}i\\ \mathrm{on}\mathrm{layer}k\end{array}\hfill \\ \hfill z_i^{\left(k\right)}={\displaystyle \sum _{j=1}^{N^{\left(k-1\right)}}}{w}_{ij}^{\left(k\right)}{a}_j^{\left(k-1\right)}+b_i^{\left(k\right)}\hfill \\ \begin{array}{l}\mathrm{Activity}\mathrm{of}\hfill \\ \mathrm{neuron}i\\ \mathrm{on}\mathrm{layer}k\end{array}=\begin{array}{l}k=L:\mathrm{input}\mathrm{of}\mathrm{that}\mathrm{neuron}\hfill \\ k<L:\mathrm{sigmoid}\mathrm{function}\mathrm{applied}\mathrm{t}\mathrm{o}\mathrm{input}\\ \mathrm{of}\mathrm{that}\mathrm{neuron}\end{array}\\ a_i^{\left(k\right)}=\left\{\begin{array}{l}{z}_i^{\left(k\right)}\mathrm{when}k=L\hfill \\ \sigma \left(z_i^{\left(k\right)}\right)\mathrm{when}k<L\hfill \end{array}\right.\hfill \end{array}$

These relationships are depicted in Figure 11.11. Once the activities in layer 1 are specified, this rule can be used to propagate information layer by layer through the neural network. A simple MatLab function that performs this operation is provided:

a = eda_net_eval(N,w,b,a);
% set the activities of the layer 1 before calling this function
% N(i): column-vector with number of neurons in each layer;
% biases: b(1:N(i),i) is a column-vector that gives the
% biases of the N(i) neurons on the i-th layer
% weights: w(1:N(i),1:N(i-1),i) is a matrix that gives the
%  weights between the N(i) neurons in the i-th layer
%  and the N(i-1) neurons on the (i-1)-th layer.
% activity: a(1:N(i),i) is a column-vector that gives the
% activities of the N(i) neurons on the i-th layer

(MatLab eda_net_eval)

The neural nets for smoothed versions of a step function and a tower function are shown in Figure 11.12. Since the sigmoid function is omitted on the output layer, the activity of this layer is just a weighted sum of its inputs. This feature allows the easy amalgamation of networks. For instance, several single-tower networks can be amalgamated to yield a sum of towers (Figure 11.13).

A two-dimensional tower, say for input (x, y), can be created by amalgamating two one-dimensional tower networks, a tower in x and a tower in y (Figure 11.14A). However, their sum is not quite a two-dimensional tower function but rather consists of two intersecting ridges, one parallel to the x-axis and the other parallel to the y-axis, with a hump where the tower should be (Figure 11.14B). A fourth layer, implementing a step function with a transition higher than the ridges but lower than the hump, is needed to delete the ridges and form the tower (Figure 11.14C).

A function can be approximated to any degree of fidelity by summing together enough towers. Thus, a neural network is capable of approximating any continuous function. However, a network constructed in this fashion may not be the smallest capable of adequately approximating the function. In the next section we will develop a technique to train an arbitrary network to produce the best approximation of a function of which it is capable. This is a simple form of machine learning.

11.14 Training a neural net

The goal in training a neural net is to match the output $d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}=d^{\mathrm{p}\mathrm{r}\mathrm{e}}\left(x_i\right)$ of the neural net to some set of observed values (x_i, d_i^obs); that is, to find a set of weights and biases such that $d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}\approx d_i^{\mathrm{o}\mathrm{b}\mathrm{s}}$. This problem can be solved by defining an error $e_i=d_i^{\mathrm{o}\mathrm{b}\mathrm{s}}-d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}$ and finding the weights and biases that minimize the total error $E={\mathbf{e}}^{\mathrm{T}}\mathbf{e}$. Since the neural net is inherently nonlinear, the error minimization must be performed with the iterative least squares method (Section 11.8) or the gradient method (Section 11.10). The process refines an initial guess of the model parameters (the combined set of weights and biases) into a final estimate that minimizes the prediction error.

Both procedures require the derivatives:

$\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial b_n^{\left(k\right)}}\mathrm{and}\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial w_{\mathit{nm}}^{\left(k\right)}}$

At first glance, computing these derivatives appears to be a daunting task. However, recall that d_i^pre is just the activity of neuron 1 in layer L, and the formula for computing activities (Equation 11.33) is simple and easily differentiated. The chain rule (see Note 11.1) implies

$\begin{array}{l}\frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial b_j^{\left(k\right)}}=\frac{\partial a_1^L}{\partial b_j^{\left(k\right)}}=\frac{\partial z_j^{\left(k\right)}}{\partial b_j^{\left(k\right)}}\frac{\partial a_j^{\left(k\right)}}{\partial z_j^{\left(k\right)}}\frac{\partial a_1^{\left(L\right)}}{\partial a_j^{\left(k\right)}}\hfill \\ \mathrm{and}\hfill \\ \frac{\partial d_i^{\mathrm{p}\mathrm{r}\mathrm{e}}}{\partial w_{jm}^{\left(k\right)}}=\frac{\partial a_1^L}{\partial w_{jm}^{\left(k\right)}}=\frac{\partial z_j^{\left(k\right)}}{\partial w_{jm}^{\left(k\right)}}\frac{\partial a_j^{\left(k\right)}}{\partial z_j^{\left(k\right)}}\frac{\partial a_1^{\left(L\right)}}{\partial a_j^{\left(k\right)}}\hfill \end{array}$

While the derivatives of Equation (11.35) are of varying complexity, they are all tractable. The easiest is

$\frac{\partial z_j^{\left(k\right)}}{\partial b_j^{\left(k\right)}}=1$

The two next most complicated are

$\frac{\partial z_j^{\left(k\right)}}{\partial w_{jm}^{\left(k\right)}}=a_m^{\left(k-1\right)}\mathrm{and}\frac{\partial z_j^{\left(k\right)}}{\partial a_m^{\left(k-1\right)}}=w_{jm}^{\left(k\right)}$

More complicated still is

$\frac{\partial a_j^{\left(k\right)}}{\partial z_j^{\left(k\right)}}=\left\{\begin{array}{ll}\frac{\partial \sigma }{\partial z_j^{\left(k\right)}}=\frac{exp\left(-z_j^{\left(k\right)}\right)}{{\left[1+exp\left(-z_j^{\left(k\right)}\right)\right]}^2}=a_j^{\left(k\right)}\left[a_j^{\left(k\right)}-1\right]\hfill & \left(k<L\right)\hfill \\ 1\hfill & \left(k=L\right)\hfill \end{array}\right\}$

Finally, the $\partial a_i^{\left(L\right)}/\partial a_j^{\left(k\right)}$ derivative is built layer by layer, using another application of the chain rule. The derivative that connects changes in activities on adjacent layers is

$\frac{\partial a_i^{\left(k\right)}}{\partial a_j^{\left(k-1\right)}}=\frac{\partial a_i^{\left(k\right)}}{\partial z_i^{\left(k\right)}}\frac{\partial z_i^{\left(k\right)}}{\partial a_j^{\left(k-1\right)}}$

A succession of these derivatives can be used to connect the activities on the Lth layer to all the other layers, a process called back-propagation, since it starts with the Lth layer and works backward towards the first layer (Figure 11.15) (Werbos, 1974):

$\begin{array}{l}\frac{\partial a_i^{\left(L\right)}}{\partial a_j^{\left(L-1\right)}}=\frac{\partial a_i^{\left(L\right)}}{\partial z_i^{\left(L\right)}}\frac{\partial z_i^{\left(L\right)}}{\partial a_j^{\left(L-1\right)}}\mathrm{and}\hfill \\ \frac{\partial a_i^{\left(L\right)}}{\partial a_j^{\left(L-2\right)}}={\displaystyle \sum _{p=1}^{N^{\left(L-1\right)}}}\frac{\partial a_i^{\left(L\right)}}{\partial a_p^{\left(L-1\right)}}\frac{\partial a_p^{\left(L-1\right)}}{\partial a_j^{\left(L-2\right)}}\mathrm{and}\hfill \\ \frac{\partial a_i^{\left(L\right)}}{\partial a_j^{\left(L-3\right)}}={\displaystyle \sum _{p=1}^{N^{\left(L-2\right)}}}\frac{\partial a_i^{\left(L\right)}}{\partial a_p^{\left(L-2\right)}}\frac{\partial a_p^{\left(L-2\right)}}{\partial a_j^{\left(L-3\right)}}\mathrm{e}\mathrm{t}\mathrm{c}\text{.}\hfill \end{array}$

The summation arises because a perturbation in the activity of a neuron on the kth layer is due to the combined effect of perturbations of the activities of all the neurons on the (k − 1)th layer that connect with it (see Note 11.1).

A MatLab function that calculates the derivatives is provided:

[daLmaxdw, daLmaxdb] = eda_net_deriv(N,w,b,a);
% update the activities by calling a=eda_net_eval(N,w,b,a);
% before calling this function
% daLmaxdb(i,j,k): the change in the activity of the i-th neuron
% in layer Lmax due to a change in the bias of the of
% the j-th neuron in the layer k
% daLmaxdw(i,j,k,l): the change in the activity of the i-th
% neuron in layer Lmax due to a change in the weight
% connecting the j-th neuron in the layer l with the k-th
% neuron of layer l-1

(MatLab eda_net_deriv)

The weights and biases together constitute the model parameters m of the iterative least squares problem (Section 11.8). The matrix G_ij^(p) contains the derivatives, and has one row i for each observation and one column j for each model parameter. Careful bookkeeping is necessary to keep track of the correspondence between the jth model parameter and a particular weight or bias. Index tables can be used to translate back and forth between these two representations. We provide a MatLab function eda_net_map() that creates them but do not describe it further, here (see the comments in the script). An important issue is the starting values of the weights and activities. For simple networks that represent towers or other simple behaviors, it may be possible to choose the weights and biases so that initial behavior is somewhat close to matching the observations. In this case, training merely refines the behavior and only a few iterations are necessary. In more complicated cases, the weights and biases may need to be initialized to random numbers, with the hope that the training will converge eventually to the best-fitting values. In both cases, imposing prior information that the correction Δm^(k) is small can help prevent overshoots and improve the rate of convergence.

As an example, a network consisting of a single tower is trained to match observations d^obs(x, y) that have the shape of a two-dimensional Normal function (Figure 11.16A). The initial weights and biases are chosen to that the tower is centered on the peak of the Normal function but has edges that, while smooth, fall off more quickly than is observed (Figure 11.16B). The iterative least squares procedure converges rapidly and reduces the error to $6\times {10}^{-5}$ of its starting value (Figure 11.16C).

11.15 Neural net for a nonlinear response

In Section 7.4, river discharge d(t) is predicted from precipitation x(t) by developing a filter c(t) such that $d\left(t\right)=c\left(t\right)\ast \mathit{x}\left(\mathit{t}\right)$. A filter is appropriate when the response of the river to precipitation is linear. It assumes that the river responds similarly to a shower and a storm; the latter is merely a scaled up version of the former. In reality, few rivers are completely linear in this sense, because they behave differently in periods of low and high water. Storms cause a river to widen and, in extreme cases, to overflow its banks. Both effects lead to nonlinearities in the river's response to precipitation.

Consider the following very simple model of a river, in which the function y(t) represents the volume of water stored in its watershed:

$\frac{\mathrm{d}y}{\mathrm{d}x}=A_{\mathrm{w}}x\left(t\right)-d\left(t\right)\mathrm{with}d\left(t\right)=A_{\mathrm{r}}v\left(t\right)$

Here v(t) is the mean velocity of water in the river, A_w is the area of the watershed, and A_r is the cross-sectional area of the river. Precipitation x(t) increases stored water and river discharge d(t) decreases it. Now assume that the velocity is linear in the volume of stored water; that is, $v\left(t\right)=c_{1}y\left(t\right)$, where c₁ is a constant. The model becomes

$\frac{\mathrm{d}y}{\mathrm{d}x}=A_{\mathrm{w}}x\left(t\right)-c_1{A}_{\mathrm{r}}y\left(t\right)$

This differential equation is linear in the unknown y(t) and will therefore have a linear response to an impulsive precipitation event (the response to $A_{\mathrm{w}}x\left(t\right)=\delta \left(t\right)$ can be shown to be $y\left(t\right)=exp\left(-c_1{A}_{\mathrm{r}}t\right)$ for $t>0$ and zero otherwise). Since discharge is proportional to stored water, it too has a linear response. A filter can completely capture the relationship between precipitation and discharge.

The model is now modified into a nonlinear one by assuming that the cross-sectional area of the river is proportional to stored water, so that $A_{\mathrm{r}}=c_{2}y\left(t\right)$, where c₂ is a constant. The model becomes

$\frac{\mathrm{d}y}{\mathrm{d}x}=A_{\mathrm{w}}g\left(t\right)-c_1{c}_2{y}^2\left(t\right)$

This differential equation is nonlinear in the unknown y(t) and consequently does not have a linear response. While an impulse in precipitation will cause a transient discharge signal, the signal for a storm will not have the same shape as the signal for a shower. Furthermore, the response to several closely spaced precipitation events will not linearly superimpose. As we will demonstrate below, a neural net is capable of predicting this nonlinear behavior.

Initially, a neural net is constructed that is capable of representing convolution by the filter c(t). Later, this network is modified by adding connections that enhance its ability to represent nonlinearities. The filtering operation $d\left(t\right)=c\left(t\right)\ast \mathit{x}\left(\mathit{t}\right)$ is just a multidimensional generalization of the linear function $d\left(x\right)=cx+h$ (with $h=0$):

$d\left(t_i\right)=c\left(t\right)\ast \mathit{x}\left(\mathit{t}\right)={\mathit{c}}_1\mathit{x}\left({\mathit{t}}_{\mathit{i}}\right)+{\mathit{c}}_2\mathit{x}\left({\mathit{t}}_{\mathit{i}-1}\right)+{\mathit{c}}_3\mathit{x}\left({\mathit{t}}_{\mathit{i}-2}\right)+\cdots \dots$

Therefore, a linear function-emulating network is first created (Figure 11.17) and K of these networks are amalgamated into a filter-emulating network that implements convolution by a length-K filter. The linear function-emulating network exploits the property of the sigmoid function $\sigma \left(wx-b\right)$ that, for small weight w, its output is a linear function of its input, at least near its transition point $x_0=-b/w$ (see Figure 11.10D). This linear behavior is demonstrated by expanding the sigmoid function in a Taylor series:

$\sigma \left(wx-b\right)\approx \frac{1}{2}+\frac{1}{4}w\left(x-x_0\right)\mathrm{f}\mathrm{o}\mathrm{r}x\approx x_0\mathrm{and}w\ll 1$

The linear function-emulating network has four layers containing six parameters (three weights and three biases). These parameters can be initialized so that the network behaves linearly; subsequent training enables it to capture more complicated nonlinear behaviors.

This utility of the filter-emulating network is demonstrated using a precipitation-discharge test dataset. A synthetic precipitation time series x(t), of length $N=1000$, is created from a random patterns of spiky precipitation events. The corresponding discharge time series d^obs(t) is determined by solving Equation (11.43) numerically. The nonlinear nature of the relationship between precipitation and discharge is apparent; large precipitation events produce disproportionately large peaks in discharge. A $K=10$ filter-emulating network is initialized to the filter $c\left(t\right)=Aexp\left(-bt\right)$, where the parameters A and b are determined by least squares (see Section 7.4). Several additional connections are added to the network to allow it to better approximate a nonlinear response function (Figure 11.18) and these new connections are assigned small, randomly chosen weights. The final network contains $M=69$ unknown weights and biases. When trained on the first half of the dataset, the network achieves an error reduction of a factor of about 10 when compared to the filter (Figure 11.19). Finally, without any retraining, the network is used to predict the second half of the test dataset. The network predicts it equally well, suggesting that it has successfully captured the nonlinear and, from the point of view of the test, unknown dynamics of the river system.

While not pursued here, the neural net could in principal be retrained on a daily basis, as more data arrives, using a rolling window of several years of data (see Problem 11.7). Such a strategy—a form of machine learning—would allow the network to adapt to unquantified factors that affects river dynamics, such as land-use changes. In the case we have been considering, the problem is small enough that full iterative least squares could be used for each daily update. In larger problems or ones in which very frequent updates are needed, the stochastic gradient method (Section 11.10) might prove preferable.

Problems

11.1. Derive the small number approximation for exp(x) near the point $x=0$. Plot the function and its approximation. What is the range of x for which the error is less than 5%?

11.2. Suppose that uncorrelated normally distributed random variables x and y have means $\overline{x}$ and $\overline{y}$, respectively, and variances σ_x² and σ_y², respectively, with ${\sigma }_x\ll \overline{x}$ and ${\sigma }_y\ll \overline{y}$. Use small number approximations to estimate the covariance matrix C_uv of $u=xy$ and $v=x/y$.

11.3. Modify eda11_05 to include both annual and diurnal frequencies of oscillation. By how much is the error reduced?

11.4. Suppose that the time needed to evaluate a function of one variable is T_f, the time needed to lookup its value in a table is $T_t=T_f/10$, and the number of table entries is K. How many times must the function be evaluated in a grid search in order to achieve an 80% reduction in computation time? Be sure to include the time needed to create the table in your estimate.

11.5. Modify eda11_13.m to fit the function:

$d^{\mathrm{o}\mathrm{b}\mathrm{s}}\left(x,y\right)=sin\left(x\right)cos\left(y\right)\mathrm{with}0\le x\le \pi \mathrm{and}0\le y\le \pi$

with a neural net containing two towers.

11.6. (A) Modify the neural net in eda11_11.m  to model the parabola with just two towers of slope $s=12.5$. (B) Add code, modeled on the iterative least squares procedure in eda11_13.m, to train the network. How good is the fit?

11.7. (This problem is especially difficult.) The test dataset in the nonlinear response example (Section 11.15) was generated by the script nonlinearresponse.m. This script solves Equation (11.43) with $c_1{c}_2=c_f=0.2$. Modify this script to generate a test dataset of length 10,000 in which the coefficient c_f systematically increases from 0.2 at the start of the dataset to 0.5 at its end, emulating land-use changes in the watershed. Then modify the network training script eda11_15. Retain the section that uses iterative least squares to train on the first 500 points, but then predict the data in two different ways: by applying the neural net, as is, to the entire dataset; and by retraining the network each time step using a moving window of the previous 500 points. Use the same iterative least squares method, but with only one iteration, to retrain. Compare the results of the two methods. Can the retrained network keep up with changing river conditions?