# Bias and Variance Analysis of Contemporary Symbolic Regression Methods
## 2 Bias/Variance Decomposition  
In supervised machine learning tasks, we want to identify a function \(\hat{f}(x)=y\), which approximates the unknown ground truth \(f(x)\) for any \(x\) drawn from a problem-specific distribution \(P\). \(x\) is a vector of so-called features and \(y\) the scalar target. The target values contain randomly distributed noise \(\epsilon\). In this work, we define \(\epsilon\sim\mathrm{N}(0,\sigma)\) with \(\sigma\) being a problem-specific standard deviation, as it is done in SRBench [8]. Therefore, our data-generating function is \(y=f(x)+\epsilon\). To find an approximation \(\hat{f}(x)\), we use a training set \(D=\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\}\) with \(x_{i}\sim P\) and their corresponding \(y\) values. The goal of machine learning is to learn a prediction model \(\hat{y}=\hat{f}(x,D)\) which minimizes a predefined loss function \(L(y,\hat{y})\) on a training set \(D\). This means that the output of a machine learning model depends on the used algorithm, the features \(x\) and the set of training samples \(D\). Bias and variance of an algorithm occur due to changes in the training data \(D\) and have a direct effect on the error and loss of models. We use the mean squared error as the loss function. For this loss function, [PERSON] et al. [1] describe that a model's expected error on previously unseen data consists of bias, variance and irreducible noise \(\epsilon\). However, [PERSON] [16] describes how the decomposition of the error into bias and variance is also possible for other loss functions. The distribution of training sets \(D\) that contain values drawn from \(P\) also leads to a distribution of model outputs \(\hat{y_{0}}=\hat{f}(x_{0},D)\) for a single fixed feature vector \(x_{0}\). The bias is the difference between the ground truth value \(y_{0}=f(x_{0})\) and the expected value over \(D\) over the \(\hat{f}\) of model outputs \(\mathbb{E}_{D}\Big{[}\hat{f}(x_{0},D)\Big{]}\), as depicted in Equation (1). The bias describes, how far our estimation is \"off\" on average from the truth. \[\mathrm{Bias}_{D}(\hat{f},x)=\mathbb{E}_{D}\Big{[}\hat{f}(x,D)\Big{]}-f(x) \tag{1}\]  
\[\mathrm{Var}_{D}(\hat{f},x)=\mathbb{E}_{D}\Big{[}\Big{(}\mathbb{E}_{D}\Big{[} \hat{f}(x,D)\Big{]}-\hat{f}(x,D)\Big{)}^{2}\Big{]} \tag{2}\]  
Variance defines, how far the outputs of estimators spread on a specific point \(x_{0}\) when they were trained on different data sets. It is independent of the ground truth. It is defined in Equation (2) as the expected squared difference between the output of models and the average output of those model on a specific point \(x_{0}\). Both properties are not mutually exclusive. However, algorithms with high variance tend to have lower bias and vice versa, so practitioners need to find an algorithm setting that minimizes both properties. This is called the bias-variance trade-off [1]. An example inspired by [PERSON] et al. [17] for high bias, high variance and an optimal trade-off between both is given in Figures 1 and 2, where we want to approximate an oscillating function with polynomial regression. We use polynomial regression as the results nicely translates to SR as its search space is a subset of SR methods with an arithmetic function set. We add normal distributed noise to each target value \(y\), so \(y=f(x)+\epsilon\) with \(\epsilon\sim\mathrm{N}(0,\sigma)\) and \(\sigma=0.2\). Each set of samples \(D\) consists of ten randomly sampled observations \(D=\{x_{1},\ldots,x_{10}\}\) with \(x_{i}\sim\mathrm{N}(\pi,2)\). Figure 1 shows the ground truth and one training set of samples. We get a different model with every different set of samples \(D\). Depending on the algorithm settings, those models behave more or less similar, resulting in different bias and variance measures. We expect the error of a perfect model to be equally distributed as the irreducible noise \(\epsilon\). Figure 1: A simple example of an oscillating ground truth \(f(x)=0.1x+sin(x)\) with randomly sampled points \(y_{D}\in D\).