Introducing surrogate models

Posted by

0

In my last post, where I wrote about sequential parameter optimization, I asked you if you did some assumptions about the underlying function when trying to find the optimal spot. (If you missed this and you’re interested in an easy introduction to sequential parameter optimization you might like to have a look here.)
But back to the assumptions. If you don’t want to do a random search, you definitely take some assumptions about the underlying function. That might be something simple, like ‘following the steepest path leads to the highest spot’ or more complex assumptions about the nature of the function, like ‘it might be polynomial’.
The former assumption can be used for a simple search strategy, the latter for building a surrogate model that hopefully resembles the function.
A good surrogate model enables to find better spots with lesser function evaluations, which might be expensive. In this post I want to introduce a very simple surrogate model to give a general idea of surrogate models.

Hands on ‘Least Squares Regression’

Given the situation that you did some experiments where you changed only one parameter and measured the results. Your results might be a little noisy since you already exhausted your possibilities in terms of accuracy. But still, only after a small set of experiment setups you get the idea that there might be a linear relation between the parameter and the resulting value. If that would be the case, a straight line would be the best model to fit the data. The Least Squares Method is a technique to find a line that fits the data, minimizing the error between the line and the actual data.
In this little demo you can experiment yourself how this method works. By clicking into the white area you add points, that resemble the results of the experiment. At least two points are needed to fit a line. By clicking the button the algorithm tries to find the best line through these points, by minimizing the quadratic error, that results from deviation from the line in y-direction.

fit line
clear

Theory of the method

So how does it work? We started with the assumption that there is a linear relation in the data, thus we want to find the line that fits the data best.
A line can be described as a function of x with y-intercept b and slope m as:

f(x) = y = b + mx

We said, we want to find the line, that fits the data ‘best’. In this case best would be the line that has the least sum of squared errors. Given n known points of data we can define the error r between the line and the actual points as:

r_1:= b + m*x_1 - y_1\\ ~\quad~ ~\vdots \\ r_n:= b + m*x_n - y_n

If we’re heading to minimize the sum of squared errors we’re looking at this term:

\min\limits_{b,m} \sum\limits_{i=1}^n (r_n)^2 = \min\limits_{b,m} \sum\limits_{i=1}^n (b + m*x_n - y_n)^2

With this term we obtain a function of the parameters b und m, which, for a set of given points (x_i; y_i), returns the sum of squared errors this line would produce:

f(b,m)=\sum\limits_{i=1}^n (b + m*x_n - y_n)^2

Hence, we’re searching the values for the parameters b and m that would minimize the error of the line, in other words: we want to find the minimum of this function. To solve this minimization problem we determine the position where the partial derivatives of the function are zero.

f_b'(b,m) = \sum\limits_{i=1}^n 2 (b+mx_i-y_i) \quad=~ \quad~ 2nb~~ + 2m\sum\limits_{i=1}^n x_i - 2\sum\limits_{i=1}^n ~y_i~ \overset{!}{=} 0
f_m'(b,m) = \sum\limits_{i=1}^n 2 (b+mx_i-y_i) x_i =~ 2b\sum\limits_{i=1}^n x_i + 2m\sum\limits_{i=1}^n x_i^2 - 2\sum\limits_{i=1}^n x_iy_i \overset{!}{=} 0

This way we obtain a system of two linear equations. Now the first row is divided by 2n and the linear system is written in matrix notation:

\begin{pmatrix}1&\frac{1}{n}\sum\limits_{i=1}^n x_i \\ \sum\limits_{i=1}^n x_i & \sum\limits_{i=1}^n x_i^2 \end{pmatrix} \begin{pmatrix}b\\m\end{pmatrix}=\begin{pmatrix}\frac{1}{n}\sum\limits_{i=1}^n ~y_i\\\sum\limits_{i=1}^n x_iy_i\end{pmatrix}

We simplify the notation by replacing the average values:

\bar{x}=\frac{1}{n}\sum\limits_{i=1}^{n}x_i \quad\text{and}\quad \bar{y}=\frac{1}{n}\sum\limits_{i=1}^{n}y_i

So our linear system now looks like this:

\begin{pmatrix}1&\bar{x} \\ \sum\limits_{i=1}^n x_i & \sum\limits_{i=1}^n x_i^2 \end{pmatrix} \begin{pmatrix}b\\m\end{pmatrix}=\begin{pmatrix}\bar{y}\\\sum\limits_{i=1}^n x_iy_i\end{pmatrix}

A solution for b depending on m can already be read from the system here:

b=\bar{y}-m\bar{x}

We obtain a complete solution by multiplying both sides of the equation with the inverse of our matrix:

\begin{pmatrix}b\\m\end{pmatrix}=\begin{pmatrix}1&\bar{x} \\ \sum\limits_{i=1}^n x_i & \sum\limits_{i=1}^n x_i^2 \end{pmatrix}^{-1}\begin{pmatrix}\bar{y}\\ \sum\limits_{i=1}^n x_iy_i\end{pmatrix}\\

The inverse of the matrix is:

\begin{pmatrix}1&\bar{x} \\ \sum\limits_{i=1}^n x_i & \sum\limits_{i=1}^n x_i^2 \end{pmatrix}^{-1}=\frac{1}{\sum\limits_{i=1}^n x_i^2-\sum\limits_{i=1}^n x_i \bar{x}}\begin{pmatrix} \sum\limits_{i=1}^n x_i^2& -\bar{x} \\ -\sum\limits_{i=1}^n x_i & 1 \end{pmatrix}

And with this we get as solution for b and m:

\begin{pmatrix}b\\m\end{pmatrix}=\frac{1}{\sum\limits_{i=1}^n x_i^2-\bar{x}\sum\limits_{i=1}^n x_i}\begin{pmatrix} \sum\limits_{i=1}^n x_i^2& -\bar{x} \\ -\sum\limits_{i=1}^n x_i & 1 \end{pmatrix}\begin{pmatrix}\bar{y}\\\sum\limits_{i=1}^n x_iy_i\end{pmatrix}

\Leftrightarrow\begin{pmatrix}b\\m\end{pmatrix}=\frac{1}{\sum\limits_{i=1}^n x_i^2-\bar{x}\sum\limits_{i=1}^n x_i}\begin{pmatrix} \bar{y}\sum\limits_{i=1}^n x_i^2 -\bar{x}\sum\limits_{i=1}^n x_iy_i \\ -\bar{y}\sum\limits_{i=1}^n x_i + \sum\limits_{i=1}^n x_iy_i \end{pmatrix}

After multiplication the result for m can still be simplified by using Steiner’s theorem, so that we end up with a term, that can be calculated quite easy:

m=\frac{\sum\limits_{i=1}^n x_iy_i ~-~\bar{y}\sum\limits_{i=1}^n x_i}{\sum\limits_{i=1}^n x_i^2~-~\bar{x}\sum\limits_{i=1}^n x_i }=\frac{\sum\limits_{i=1}^n x_iy_i ~-~n\bar{y}\bar{x}}{\sum\limits_{i=1}^n x_i^2~-~n\bar{x}^2}=\frac{\sum\limits_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{\sum\limits_{i=1}^n(x_i-\bar{x})^2}

We also get a solution for b, but now already knowing the value m it is easier to refer to the short formula using m we already found in the first steps:

\quad\quad b=\bar{y}-m\bar{x}=\frac{\bar{y}\sum\limits_{i=1}^n x_i^2 ~-~\bar{x}\sum\limits_{i=1}^n x_iy_i}{\sum\limits_{i=1}^n x_i^2~-~\bar{x}\sum\limits_{i=1}^n x_i }

To actually fit the line of course you only need these two formulas – calculating these values is actually nearly all the little demo does 😀 Hope you liked it.

Leave a Reply