--- title: "Machine learning is function approximation" description: "This essay grew out of Mikhail Romanov's machine learning basics lecture in the JetBrains Foundation's Computer Science and Artificial Intelligence program, and much of its framing and math owes to him. To practise the ideas hands-on, try his course Mathematics for Deep Learning in the JetBrains IDE plugin catalog." canonical_url: "https://gulyuk.com/ideas/function-approximation" --- > Index of every page on this site: [llms.txt](https://gulyuk.com/llms.txt) This essay grew out of [Mikhail Romanov](https://www.linkedin.com/in/mikhail-v-romanov/)'s machine learning basics lecture in the JetBrains Foundation's Computer Science and Artificial Intelligence program, and much of its framing and math owes to him. To practise the ideas hands-on, try his course [Mathematics for Deep Learning](https://plugins.jetbrains.com/plugin/33838-deep-learning-pt-1-mathematics) in the JetBrains IDE plugin catalog. This is an interactive essay. Every figure is playable, and after the first one a bar appears that lets you change the target function all the figures fit. Equations sit in boxes marked "skippable": nothing essential lives only there. ## Fit it by hand Below are 24 noisy measurements of some unknown curve. Drag the seven handles to pull a smooth curve through the cloud. You control: the seven handle heights · Fixed: the points and the handle positions. This figure has its own data. *Fig. 1. Drag the handles up and down (arrow keys work too). The number is the score: the mean squared distance between the points and your curve.* That score is the mean squared error, or MSE. Lower is better. Every method on this page is a different answer to one question: how should the curve be built so that this number is small, and stays small on points it has not seen yet? That is the whole job. A neural network, a decision tree and a polynomial are all machines for producing curves like this one, built from different simple parts. We will take the parts one at a time. **Math (skippable): the setup in symbols** Every measurement is a pair `(x_i, y_i)`: the circumstances of the measurement and its result. Behind the points sits a dependency we cannot see, `f`, and what we record is that dependency plus noise `\varepsilon_i`: ```tex y_i = f(x_i) + \varepsilon_i . ``` A model is a function `\hat y = \mathrm{Net}_w(x)` with adjustable numbers `w`, its weights. Over `S` measurements its score is the average loss, and training means choosing the weights that make the score smallest: ```tex L_{\text{total}}(w) = \frac{1}{S}\sum_{s=1}^{S} L\big(\mathrm{Net}_w(x_s),\, y_s\big), \qquad w^{*} = \arg\min_{w}\; L_{\text{total}}(w). ``` With the squared distance as the loss this is the mean squared error of the figure above. The absolute distance gives the mean absolute error, which treats a big miss as only proportionally worse: ```tex \mathrm{MSE} = \frac{1}{S}\sum_{s=1}^{S} \lVert y_s - \hat y_s \rVert^{2}, \qquad \mathrm{MAE} = \frac{1}{S}\sum_{s=1}^{S} \lvert y_s - \hat y_s \rvert . ``` A loss is not the same thing as a metric. A metric answers a question you care about, such as "how often is the answer within `\epsilon`?": ```tex \mathrm{Acc}_{\epsilon} = \frac{1}{S}\sum_{i=1}^{S}\big[\,\lvert y_i - \hat y_i\rvert < \epsilon\,\big]. ``` It is a fine metric and a useless loss. Nudge `\hat y_i` a little and every bracket stays at 0 or 1, so `\partial\,\mathrm{Acc}_{\epsilon} / \partial \hat y_i = 0` almost everywhere, and a method that follows slopes gets no signal. A loss has to change smoothly when the prediction moves, and fall as the prediction gets closer to `y`. "Fit it for me" runs ordinary least squares with a degree-5 polynomial and reads the handle heights off it. ## Polynomials: the first thing everyone tries A polynomial of degree d is a sum of powers, 1, x, x², …, xᵈ, each with its own coefficient. Choosing the coefficients by least squares is a single linear solve, so there is nothing to train and nothing to tune except the degree. The pieces 1, x, x², …, xᵈ are the basis: a menu of simple shapes. A fit is a recipe that says how much of each shape to add up, and the coefficients are the amounts. Different menus can produce exactly the same set of curves. The figure lets you pick between two menus for degree-d polynomials: **Powers of x**, the one above, and **Chebyshev**, described below the figure. Here the polynomial sees only the 30 dots. The ink-coloured line is the true function, which the fit never gets to see. You control: degree d · Learned by least squares: the coefficients · Fixed: the data *Fig. 2. Raise the degree. Filled dots are training points; hollow dots are held-out measurements. The grey band is the gap between your fit and the truth, and the test error is measured against the true curve. Try the "Noisy points" target in the bar above.* Watch the two errors. The training error only ever goes down. The test error, measured against the true curve, falls and then climbs: with enough freedom the polynomial starts chasing the noise between the dots instead of the curve behind them. The Chebyshev basis is a different menu for the same curves. Its k-th piece, T k (x) = cos(k·arccos x) on the interval from −1 to 1, is a polynomial of degree k that wiggles up and down between −1 and 1 exactly k times. Compare that with the powers: x¹⁵ and x¹⁷ are both almost flat near zero and both shoot up at the ends, so they look nearly the same, and a solver has trouble telling them apart. Every Chebyshev piece has a visibly different rhythm, so the solver never confuses them. Any polynomial of degree d can be written in either basis; only the arithmetic changes, not the set of curves you can reach. There is a second, separate failure, and it is about arithmetic rather than overfitting. Write the same polynomial in powers of x and push the degree past about 15: the columns of the problem become nearly identical, the solve loses most of its digits, and the page flags it. Chebyshev polynomials describe exactly the same family of curves with a well-behaved solve, so the warning goes away. It does not cure overfitting: on noisy points a high-degree Chebyshev fit can be just as wild. The choice of basis is a numerical decision, not a mathematical one. Weierstrass (1885): any continuous function on an interval can be approximated as closely as you like by a polynomial. That tells you a good polynomial exists. It does not tell you that a fit to 30 noisy points will find it. **Math (skippable)** Weierstrass: for continuous `f` on `[a,b]` and any `\varepsilon>0` there is a polynomial `p` with `\max_{x}|f(x)-p(x)|<\varepsilon`. Taylor's polynomial `\sum_k f^{(k)}(a)(x-a)^k/k!` is the local version: excellent near `a`, useless far away. Even for the perfectly smooth `1/(1+x^2)` the series around 0 diverges for `|x|>1`, because the function has poles at `x=\pm i` in the complex plane. The Chebyshev pieces satisfy `T_0=1,\ T_1=x,\ T_{k+1}=2xT_k-T_{k-1}`, which is another way to write `T_k(\cos\vartheta)=\cos(k\vartheta)`. They are also orthogonal on `[-1,1]` with weight `1/\sqrt{1-x^2}`, which is what keeps the columns of `\Phi` well separated. Least squares solves `\min_w \|\Phi w - y\|^2` where `\Phi_{ij}=\phi_j(x_i)`. The monomial columns `x^j` become almost parallel as `j` grows, so `\Phi^\top\Phi` is nearly singular. ## Runge's lesson: where you sample matters Suppose you may measure the function anywhere you like, and you want the one polynomial of degree n that passes through n+1 measurements. The obvious choice is evenly spaced measurements. It is also a trap. You control: number of nodes and where they sit · Fixed: the function 1/(1+25x²). This figure has its own target. *Fig. 3. The dots along the bottom mark where the function was sampled. Compare where they sit with where the error appears.* With evenly spaced nodes the polynomial wiggles harder and harder near the ends: at degree 10 the largest error is 1.9, at degree 20 it is 60, on a function that never exceeds 1. Adding more data made the fit worse. Now crowd the nodes toward the ends, spacing them like the horizontal positions of equally spaced points on a circle. These are Chebyshev points. At degree 20 the largest error drops to 0.018. No fixed rule for placing nodes works for every continuous function (Faber, 1914). Chebyshev points are simply a very good default for smooth ones. There is a way out that changes the family: ratios of polynomials, called Padé or rational approximants. The Runge function is itself a ratio, 1 over 1 + 25x², so a rational fit can match it exactly with two parameters where a polynomial needs ever more. The price is that the fit is no longer linear in its parameters, and the denominator can hit zero where you do not want it to. **Math (skippable)** The interpolation error at `x` is `\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)` for some `\xi` in the interval. You cannot control `f^{(n+1)}`, but you can choose the nodes to keep the product small. Chebyshev nodes (nearly) minimise its maximum; evenly spaced nodes make it huge near the ends. Equivalently, the Lebesgue constant, which measures how much the interpolant can amplify errors in the data, grows exponentially for equispaced nodes and only logarithmically for Chebyshev nodes. ## Splines: many small pieces instead of one big one A single polynomial is global: nudge it anywhere and it moves everywhere. The fix is to stop asking one curve to do everything. Connect a handful of simple pieces at points called knots. In this chapter, and the next ones, the method gets to look at the target function itself rather than at noisy dots. This is function approximation in its pure form. You control: knot positions and heights and number of knots · Fixed: the shape of each piece *Fig. 4. Drag knots, or move the selected one with the arrow keys. Auto-place puts knots where the curve bends most. Changing the target snaps the knots back onto it.* Each piece only cares about its own neighbourhood, so moving one knot changes the curve locally. The price is that you need enough knots, and how many you need depends on how curved the function is. Halving the knot spacing cuts the error of straight pieces by a factor of about 3.7, and of cubic pieces by about 17. That is the textbook 4 and 16, measured on a test function. A foretaste of chapter 8: a ReLU neuron is exactly one kink. A sum of ReLUs is a piecewise-linear curve, so a layer of them is a spline whose knots can be learned. **Math (skippable)** Straight pieces: `\max|f-s|\le \dfrac{h^2}{8}\max|f''|`. Cubic splines: the error shrinks like `h^4` when the end conditions suit the function. The measurement above uses `\sin\pi x`, whose second derivative vanishes at both ends, which is exactly what a natural spline assumes. Among all smooth curves through the knots, the natural cubic spline minimises `\int f''(x)^2\,dx`, which is where the name comes from: it is the shape a thin flexible ruler takes. ## Fourier: waves instead of bumps Splines are local. The opposite idea is to build the curve from waves that fill the whole interval: a constant, then half a cosine wave across the interval, then a full wave, then one and a half, and so on. Add enough of them and a surprisingly wide range of curves comes out. Unlike powers of x, these waves are orthogonal, which means they do not interfere with each other. Each coefficient is found on its own, by a single integral, and the best fit with K waves is simply the first K+1 terms (the constant plus K waves) of the best fit with more. You control: number of waves K · Fixed: the frequencies. The coefficients are computed from the target. *Fig. 5. Increase K. On Smooth the fit sharpens quickly. Then press "Break it", which switches to the Jump target.* Smooth curves need few waves. A jump is another story. Near the jump the partial sums overshoot by about 9.1% of the jump height, and adding waves only squeezes the overshoot closer to the jump without making it smaller. This is the Gibbs phenomenon. A basis made of global waves cannot make one local discontinuity cheap. Why cosines on [−1, 1]? Mirroring the function around the end removes the jump a plain sine and cosine series would see there whenever the two end values differ. A kink remains wherever the slope at the end is not zero, and that kink still limits how fast the error shrinks. Wavelets keep the idea of a set of building blocks but make every piece a small wave that lives in one place and at one scale. A jump then costs a few coefficients near it instead of ripples everywhere, which is why wavelets are used in image compression such as JPEG 2000. **Math (skippable)** We use `f(x)\approx\sum_{k=0}^{K}c_k\cos\!\big(k\pi\,\tfrac{x+1}{2}\big)`. The cosines are orthogonal on `[-1,1]`, so `c_k=\dfrac{\int f\,\phi_k}{\int\phi_k^2}`, with `\int\phi_0^2=2` and `\int\phi_k^2=1` for `k\ge1`. The smoother the mirrored extension of `f` is, the faster `c_k` decays: like `1/k^2` if it has a kink at the ends, like `1/k` if it has a jump, which is why the ripples never fade. ## Noise: when a perfect fit is a mistake So far most dots lay exactly on the curve. Real measurements do not. In the figure below every dot is the true curve plus random noise, whichever target you chose in the bar. The ink-coloured line is still the truth, and the fit never sees it. The model is the polynomial from chapter 1, in the well-behaved Chebyshev basis, with one slider. Filled dots are what it trains on. Hollow dots are fresh measurements it has never seen. You control: degree d · Learned by least squares: the coefficients · Lower panel: training error (solid line), test error (dashed line), dotted vertical line = your degree. This figure has its own noisy sample. *Fig. 6. Raise the degree and watch the lower panel. The training error only falls. The test error, measured against the true curve, falls and then climbs. "New noise" draws a fresh sample.* The best degree sits at the bottom of that U. To its left the fit is too stiff to follow the curve, and the error that remains is bias: it would be there however much data you collected. To its right the fit is flexible enough to chase the noise, and the error is variance: a different sample of dots would give a very different curve. A curve that passes through every dot (interpolation) is the extreme case of the second kind. The readout estimates both. It refits the same degree on 40 fresh samples; bias² is how far the average of those curves sits from the truth, and variance is how much the curves scatter around their own average. On average over samples, the squared test error against the truth is exactly bias² plus variance. The Test RMSE shown is one sample's square root, so do not add it to them directly. With the Smooth target and the opening sample, degree 6 is best, with a test RMSE of 0.044. Degree 20 trains down to 0.097 but tests at 0.423. It helps to keep three errors apart. The *approximation* error asks whether the family of curves can get close at all. The *generalisation* error asks how much the noise in the data hurts. The *optimisation* error asks whether the training procedure found the best member of the family. Universality theorems speak only to the first. Modern networks complicate this picture: some keep improving past the point where they fit the training data exactly. That is an active research topic, and this page does not claim to settle it. **Math (skippable)** For a fit `\hat f` trained on a random sample and a fixed point `x`: `\mathbb E\big[(\hat f(x)-f(x))^2\big]=\big(\mathbb E\hat f(x)-f(x)\big)^2+\operatorname{Var}\hat f(x)`. Scored against noisy measurements `y=f(x)+\varepsilon`, a further `\sigma^2` is added that no model can remove. For least squares with `p` parameters on `n` points the variance averages roughly `\sigma^2 p/n`, which is why it climbs steadily with the degree. ## Neighbours, stumps and boosting: curves made of steps Here is a model with almost no mathematics. To predict at a new point, look at the nearest dots and average their heights. That is k-nearest neighbours. The curve it draws is a staircase, because the answer only changes when a different dot becomes one of the nearest. The second model builds a staircase on purpose. A *stump* is a single step: one cut position, one height on each side. Boosting adds stumps one at a time, and each new stump is fitted to the residual, the part the sum so far still gets wrong. You control: the number of neighbours k, or the number of stumps · Fixed: the data. Nothing here is smooth, and nothing is extrapolated: outside the dots the curve stays flat. *Fig. 7. Filled dots train the model, hollow dots are held out. In boosting mode the lower panel shows what is still wrong (the dark dots) and the step the next stump will add (the red line). Try the Jump target: steps are exactly what it needs.* Both models are *local* and *piecewise constant*. They handle a jump with no ringing at all, which Fourier cannot. They pay for it on smooth curves, where a staircase needs many steps to look like a slope. Averaging more neighbours smooths out noise, and fewer stumps do the same; the extreme settings (one neighbour, or very many stumps) copy the noise. Boosting is also a first look at a theme that returns in chapter 8: a model made of many simple pieces whose positions are *learned*, not fixed in advance. The weakness of neighbours is dimension. Spread points evenly through a unit cube and ask how long a side must be to hold one tenth of them. In one dimension it is 0.1 of the range. In ten dimensions it is 0.79: almost the whole range in every direction. "Nearby" no longer means local. This is the curse of dimensionality, and it is why methods that can ignore useless inputs, such as boosted trees, remain popular on tables of many columns. **Math (skippable)** A stump `s(x)=\ell` for `x\le t` and `r` otherwise, fitted to residuals `e_i`, chooses `t` to maximise `\frac{(\sum_{\text{left}}e_i)^2}{n_L}+\frac{(\sum_{\text{right}}e_i)^2}{n_R}`; `\ell` and `r` are the two averages. With learning rate `\eta=0.5` the model after `m` steps is `\bar y+\eta\sum_{j\le m}s_j(x)`. A cube of side `a` holds a fraction `a^d` of uniform data, so holding a fraction `p` needs `a=p^{1/d}`. ## Kernels: smooth, local, and honest about doubt Staircases are blunt. A smoother local idea is to place a soft bump at each of a set of positions and add them up, with heights chosen by least squares. The bump here is a Gaussian, and its width is the one dial that matters. Narrow bumps are very local. Wide bumps blend into each other. A kernel is the same idea stated as a similarity: two inputs that are close count as similar, and the prediction at a new point is a weighted vote of the data points near it. A Gaussian process is a kernel method that also reports how unsure it is. Its answer at each point is a best guess plus a band, and the band is narrow close to the data and widens as you move away. You control: the bump width · Learned: the heights (a linear solve) · Fixed: the data and, in the process, the noise level. The pale red band is two standard deviations of the process. *Fig. 8. Slide the width. In the Gaussian-process mode the band pinches at every dot and widens in the gaps and beyond the ends, where the curve returns to zero. In the bumps mode there are twelve bumps at fixed positions.* Too narrow and the fit is a set of isolated hills that fall back to zero between the dots. Too wide and it is too stiff to follow a bend. In between, the fit is smooth where the polynomial was fragile and local where the Fourier series was global. On the Noisy target the process treats the dots as uncertain and smooths through them; on a clean target it is nearly an interpolant. The band is an honest statement, but only about the model's own assumptions: it says "if the function is as smooth as this width implies". Try the Jump target. No width is right, and the band cannot tell you that. The price is cost. A Gaussian process works with an n × n table of similarities and solves a linear system with it. The work grows like n³, which is nothing for thirty dots and a wall for a million. Big kernel tables are often close to low rank. Methods such as Nyström and random features replace the full table by a thin factor with m ≪ n columns, which cuts the cost to roughly n·m². The same idea, approximating a large table by a product of thin ones, runs through matrix and tensor factorisation and through low-rank adaptation of large networks. **Math (skippable)** With kernel `k(x,x')=\exp\!\big(-(x-x')^2/2\ell^2\big)`, data `y`, kernel table `K` and noise `\sigma`: mean `m(x)=k(x)^\top(K+\sigma^2 I)^{-1}y`; variance `k(x,x)-k(x)^\top(K+\sigma^2 I)^{-1}k(x)`. The bumps model uses `\sum_j w_j\,k(x,c_j)` with fixed centres `c_j` and ridge least squares for `w`. The page keeps the noise at least 0.02 so the table stays well conditioned; with duplicate points or a huge width it raises the noise further rather than failing. The noise term acts as regularisation: it keeps the fit from chasing every dot. ## Neurons: bricks you can tune So far the building blocks were fixed in advance: powers, cosines, hat functions. A neural network changes one thing. Each brick comes with its own knobs, and the knobs are part of what gets fitted. The classic brick is a squashed S-curve, the sigmoid. Four knobs bend it into any rising or falling step you like. y = w′·σ(w·x + b) + b′ · You control: all four. Dashed: the plain σ(x). *Fig. 9. w sets the steepness, b the position, w′ the height (negative flips it), b′ the vertical shift.* Now add many such bricks. Each one contributes one step at its own position, with its own height. A sum of steps is a staircase, and a fine enough staircase hugs any curve. You control: number of neurons N and the activation · Fixed here: positions and heights are read off the target *Fig. 10. Dotted verticals mark where each neuron switches on. Start with Step, then try ReLU at the same N.* Replace the step by a ReLU, which is zero up to a point and then climbs with a constant slope. Each neuron now contributes one kink instead of one step, and the sum is a piecewise-linear curve. With the same number of neurons the error is far smaller: this is the same family of curves as the straight splines of chapter 3, but with knots that a network is free to move. One honest caveat. Here the positions and heights are read off the target by a formula. A real network finds them by training, which can get stuck or generalise badly. The demo shows what a network could represent, not what training will find. **Math (skippable): the network as a formula** The sigmoid is `\sigma(z) = 1/(1+e^{-z})`, and the single neuron of the first figure is `y = w'\,\sigma(wx+b) + b'`. Add `N` of them and keep one output bias, and you have the whole two-layer network: ```tex \hat y = b_{\text{out}} + \sum_{i=1}^{N} w^{\text{out}}_i\, \sigma(w_i x + b_i). ``` Make a neuron steeper (`w_i \to \infty`, keeping its switching point `x_i = -b_i / w_i` in place) and the sigmoid turns into the step `\theta`, which is 0 for negative arguments and 1 for positive ones. The sum is then a staircase, `\hat y = b_{\text{out}} + \sum_i w^{\text{out}}_i\,\theta(x - x_i)`. Multiply a step by its own argument and you get the ReLU; multiply the sigmoid by its argument and you get its smooth cousin, SiLU: ```tex \mathrm{ReLU}(x) = x\,\theta(x), \qquad \mathrm{SiLU}(x) = x\,\sigma(x). ``` With several inputs the weights are stacked into matrices, one column of `W_{\text{in}}` per neuron. Then, for one input vector `x` or for a whole batch `X` with one sample per column, ```tex \hat y = b_{\text{out}} + W_{\text{out}}^{\top}\,\sigma\!\big(W_{\text{in}}^{\top} x + b_{\text{in}}\big), \qquad Y = b_{\text{out}} + W_{\text{out}}^{\top}\,\sigma\!\big(W_{\text{in}}^{\top} X + b_{\text{in}}\big). ``` A linear combination of sigmoids is the whole system: the only nonlinear step is `\sigma`, applied to one neuron at a time. Universal approximation (Cybenko 1989, Hornik 1991): a network with one hidden layer and enough neurons can approximate any continuous function on a bounded interval. It says nothing about how many neurons, or how to find them. Kolmogorov–Arnold networks (Liu and colleagues, 2024) move the learnable part from the nodes to the edges: every edge carries its own one-dimensional spline, and nodes simply add. The idea echoes this chapter, a sum of tunable one-dimensional pieces. Whether they match ordinary networks at equal cost is still debated, so treat them as an open question, not a verdict. ## Depth: folding a curve instead of adding bricks Chapter 8 added neurons side by side. A network can also stack layers, so that each layer feeds the next. Does that buy anything that simply adding more neurons does not? Take a tent: a function that rises from 0 to 1 and falls back to 0. Two ReLU neurons make one. Feed a tent into another tent and the curve folds: its two slopes become four. Fold again and you get eight. Each layer doubles the number of linear pieces, using the same two neurons. You control: the number of folds (layers) · Dark line: the deep net's output. Red line: a one-layer net with the same parameter budget and evenly spread kinks. These weights are constructed, not trained. *Fig. 11. Add layers. The dark line gains twice as many teeth each time. The red curve is a single layer given the same number of parameters; it falls behind quickly.* The counting is simple. The deep net uses about 6 parameters per layer, so 48 in total for 8 layers, and draws 256 linear pieces. A single layer with the same budget affords 15 neurons, and a one-layer net with W neurons cannot have more than W+1 pieces. Depth grows the number of pieces exponentially; width grows it linearly. Two cautions keep this honest. First, the sawtooth is a special function, chosen because folding makes it cheap. Depth is no free lunch for every curve. Second, these weights were written down by hand. Gradient descent is not guaranteed to find them, and the next chapter shows how training can be slow even when a good network exists. This is the third of the errors from chapter 5, optimisation: the family can contain a good answer that training never reaches. **Math (skippable)** On `[0,1]`, `\operatorname{tent}(u)=2\,\mathrm{relu}(u)-4\,\mathrm{relu}(u-\tfrac12)`. The `L`-fold composition has `2^L` linear pieces, each of slope `\pm 2^L`. A one-hidden-layer ReLU net with `W` units is piecewise linear with at most `W+1` pieces. Telgarsky (2016) makes this precise: some functions computed by deep nets of modest size need exponentially many units if the net is forced to be shallow. ## Fourier features: giving a network the right alphabet The target below is two waves added together: a slow one and a fast one. A small network is trained on 48 points of it by gradient descent, and you watch the fit improve step by step. The training is live and runs at most 300 steps. You control: the frequency scale of the input features (plain means the raw input x) · Learned: all network weights, by Adam · Fixed: the data, the seed and the 300-step cap. *Fig. 12. With a plain input the network learns the slow wave first and the fast wave much later. Move the scale up to give it sine and cosine features at random frequencies; the fast wave arrives sooner. Too high and the fit starts to wobble between the dots.* Watch the readout. After 300 steps a plain network has learned 99% of the slow wave but only 3% of the fast one. This habit, fitting slow components before fast ones, is called spectral bias. The network is not unable to represent the fast wave; the training is just slow to reach it. The remedy is a change of alphabet, not of network. Instead of feeding in x, feed in sines and cosines of x at a spread of frequencies. The network then starts with fast waves already within reach. At scale 4 it learns 98% of the fast wave in the same 300 steps. The scale is a real choice. It sets how fast the features can wiggle. Far too high, and the network can fit the points with waves that swing wildly between them. This is the variance error of chapter 5 again. Spectral bias was described for deep networks by Rahaman and colleagues (2019). Random Fourier features as network inputs are due to Tancik and colleagues (2020), who used them for images and 3D scenes, where the input is just a few coordinates. **Math (skippable)** The input `x` is replaced by `\gamma(x)=\big[\sin(2\pi b_j x),\ \cos(2\pi b_j x)\big]_{j=1}^{16}` with `b_j\sim\mathcal N(0,\sigma^2)`. The network has two hidden layers of 32 tanh units and a linear output; training minimises mean squared error with Adam (learning rate 0.01). The numbers shown are `\int_{-1}^{1} g(x)\sin(k\pi x)\,dx` for `k=1` and `k=8`, divided by the target's amplitude of each (1 and 0.5). A value of 100% means that wave is fully learned. **Math (skippable): what one training step does** The weights form a long vector `w = (w_1, \dots, w_p)`, and the training score `L_{\text{total}}(w)` is a landscape over it. Its slope along each weight is collected in the gradient: ```tex \nabla_w L = \Big(\frac{\partial L}{\partial w_1},\ \dots,\ \frac{\partial L}{\partial w_p}\Big). ``` For a small step `dw` the score changes, to first order, by ```tex dL = \langle \nabla L,\, dw \rangle = \lVert \nabla L \rVert\, \lVert dw \rVert \cos\angle(\nabla L,\, dw). ``` This is largest when `dw` points along the gradient and most negative when it points against it, so the step that lowers the score fastest is ```tex w_{t+1} = w_t - \alpha\, \nabla_w L^{(t)}_{\text{total}}, ``` with a step size `\alpha`. Adam, which this page uses, adds momentum to this step and scales each weight's step by the size of its recent gradients. The gradient itself comes from the chain rule, applied from the output backwards (backpropagation). Suppose a weight `w_1` inside `f_1` reaches the score `L` along two routes, through `f_2` and through `f_3`, which meet in `f_4`. Each route contributes a product of local slopes, and the routes add: ```tex \frac{dL}{dw_1} = \frac{\partial L}{\partial y_4}\Big(\frac{\partial f_4}{\partial y_2}\frac{\partial f_2}{\partial y_1} + \frac{\partial f_4}{\partial y_3}\frac{\partial f_3}{\partial y_1}\Big)\frac{\partial f_1}{\partial w_1}. ``` Working from `L` backwards, every factor is computed once and shared by all the weights behind it, so a single backward sweep delivers every weight's derivative. For the simplest case, one sample and the network of chapter 8 with squared error, write `v_i = w^{\text{out}}_i` for the output weights, `z_i = w_i x + b_i`, `\hat y = b_{\text{out}} + \sum_i v_i\,\sigma(z_i)` and `L = (y - \hat y)^2`. With `\delta = \partial L / \partial \hat y = -2(y - \hat y)` the chain rule gives ```tex \frac{\partial L}{\partial b_{\text{out}}} = \delta, \quad \frac{\partial L}{\partial v_i} = \delta\, \sigma(z_i), \quad \frac{\partial L}{\partial w_i} = \delta\, v_i\, \sigma'(z_i)\, x, \quad \frac{\partial L}{\partial b_i} = \delta\, v_i\, \sigma'(z_i), ``` where `\sigma'(z) = \sigma(z)\big(1 - \sigma(z)\big)`. The network trained above uses tanh instead, and only that factor changes: `\tanh'(z) = 1 - \tanh^2(z)`. For whole layers, with `Z = WX` (one sample per column of `X`; here `W` is `W_{\text{in}}^{\top}` of chapter 8, one row per neuron), the same rule reads ```tex \frac{\partial L}{\partial W} = \frac{\partial L}{\partial Z}\, X^{\top}, \qquad \frac{\partial L}{\partial X} = W^{\top}\, \frac{\partial L}{\partial Z}, ``` which is why a whole network can be differentiated with a handful of matrix products. ## Which tool, when Several figures above have a "Pin to compare" button (chapters 1, 3, 4, 6, 7 and 8). Pin a few fits and they land here, drawn on the same target with their error, their parameter count and the time they took to compute. *Fig. 13. The pinned fits on the current target. Change the target in the bar and pins are cleared, because errors on different targets cannot be compared.* The comparison that matters most is what happens outside the data (extrapolation). Here the same fits are drawn beyond the interval they were built on (shaded), where the target keeps going. *Fig. 14. Beyond the shaded region nothing was measured. Polynomials explode, splines continue in a straight line, cosine series repeat, neighbours and stumps stay flat, and kernel fits fade back to zero.* ### Pick your case Twelve ways to approximate a function, compared by basis, parameters, error rate, behaviour in many dimensions, extrapolation, noise, uncertainty, cost and what each is best at.
Method Basis Parameters Error rate Many dimensions Beyond the data Noise Uncertainty Cost Best at
Polynomial fit Global Linear Fast for smooth functions, if the degree is moderate Terms explode Explodes Overfits at high degree Not built in (classical confidence bands exist) Cheap Few points, smooth trend
Chebyshev interpolation Global Linear Geometric for analytic functions Grids explode Explodes Interpolates the noise Not built in Cheap Smooth functions you can sample anywhere
Splines Local Linear h² straight, h⁴ cubic Grids explode Straight line Plain splines interpolate noise Not built in Cheap One-dimensional curves, kinks and jumps with enough knots
Cosine / Fourier series Global Linear Set by smoothness; a kink at the ends or a jump slows it, and Gibbs ripples at jumps Grids explode Repeats Truncation smooths Not built in Cheap (fast transforms) Smooth or periodic signals
Nearest neighbours Local None fitted: the data is the model Slow: a staircase, so error shrinks like the spacing Degrades fast (curse of dimensionality) Constant Averaging k neighbours smooths; k = 1 copies the noise Not built in Cheap to build, scans the data to predict Quick baselines, jumps, local patterns
Boosted stumps and trees Local, learned splits Nonlinear (split positions) Staircase: slow on smooth curves, fine at jumps Copes when only a few inputs matter Constant Small steps and early stopping limit overfitting Not built in Cheap training rounds Tables of mixed inputs, jumps
Gaussian bumps (RBF) Local, smooth Linear weights, nonlinear width Fast for smooth functions when the bumps overlap Needs data to fill the space Fades to zero A ridge term or fewer bumps Not built in Cheap (one linear solve) Smooth functions from scattered points
Gaussian process Kernel bumps on the data Linear weights, nonlinear kernel settings Fast for smooth functions if the kernel fits Needs data to fill the space Reverts to the mean, with a wide band Explicit noise term Yes, if the kernel's assumptions hold Grows like n³ in the number of points Small data where you need error bars
One-hidden-layer network Learned bricks Nonlinear Can beat grids when the target has structure Can cope Straight lines (ReLU) Needs regularisation Not built in (ensembles and Bayesian variants exist) Training Flexible shapes, many inputs
Deep network Learned compositions Nonlinear Depth can multiply the linear pieces (chapter 9) Can cope Straight lines (ReLU) Needs regularisation Not built in Training Structured, high-dimensional data
Network + Fourier features Learned, with fixed waves as inputs Nonlinear Reaches fine detail faster than a plain network Aimed at few inputs, such as coordinates Depends on the chosen frequencies Too high a scale fits the noise Not built in Training Fine detail from coordinates (images, signals)
These are rules of thumb, not laws. Which row wins depends on how many inputs you have, how smooth the function is, how noisy the data is, and what a mistake costs. If you remember one thing from this page: every method here is a set of simple pieces (a dictionary) plus a rule for choosing the coefficients, and the interesting question is what each dictionary makes cheap and what it makes expensive. ## Glossary Terms that carry a dotted underline in the text open their definition when you tap or press them. All of them are collected here.
## Sitemap See the full [sitemap](https://gulyuk.com/sitemap.md) for all pages.