3
$\begingroup$

I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning).

Could someone please explain with the help of examples and/or references?

$\endgroup$
0

2 Answers 2

7
$\begingroup$

Section 5.2 Error Decomposition of the book Understanding Machine Learning: From Theory to Algorithms (2014) gives a description of the approximation error and estimation error in the context of empirical risk minimization (ERM) and, in particular, in the context of the bias-complexity tradeoff (which is strictly related to the bias-variance tradeoff).

Error/risk decomposition

The expected risk (error) of a hypothesis $h_S \in \mathcal{H}$ selected based on the training dataset $S$ from a hypothesis class $\mathcal{H}$ can be decomposed into the approximation error, $\epsilon_{\mathrm{app}}$, and the estimation error, $\epsilon_{\mathrm{est}}$, as follows

\begin{align} L_{\mathcal{D}}\left(h_{S}\right) &= \epsilon_{\mathrm{app}}+\epsilon_{\mathrm{est}} \\ &= \epsilon_{\mathrm{app}}+ \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \\ &= \left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right) + \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \label{1}\tag{1} \end{align}

Approximation error

The approximation error (AE), aka inductive bias, defined as

$$\epsilon_{\mathrm{app}} = \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) $$

is the error due to the specific choice of hypothesis class (or set) $\mathcal{H}$. So, $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is minimal risk/error that can be achieved with a hypothesis class $\mathcal{H}$. In other words, if you limit yourself to $\mathcal{H}$ and you select the "best" hypothesis in $\mathcal{H}$, then $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is the expected risk of that hypothesis.

Here are some properties.

  • The larger $\mathcal{H}$ is, the smaller this error is (because it's more likely that a larger hypothesis class contains the actual hypothesis we are looking for). So, if $\mathcal{H}$ does not contain the actual hypothesis we are searching for, then this error could not be zero.

  • This error does not depend on the training data. You can see in the formula above that there's no $S$ (the training dataset), but only on $D$ (the distribution over the space of inputs and labels from which $S$ was assumed to have been sampled)

Estimation error

The estimation error (EE) is the difference between the approximation error $\epsilon_{\mathrm{app}}$ and the error achieved by the ERM predictor $L_{\mathcal{D}}\left(h_{S}\right)$, i.e.

\begin{align} \epsilon_{\mathrm{est}} &=L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \\ &= L_{\mathcal{D}}\left(h_{S}\right) - \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) \end{align}

Here are some properties.

  • The estimation error depends on the training dataset $S$. You can see $S$ in the formula above.

  • $\epsilon_{\mathrm{est}}$ also depends on the choice of the hypothesis class (given that it is defined as a function of $\epsilon_{\mathrm{app}}$).

Bias-complexity tradeoff

If we increase the size and complexity of the hypothesis class, the approximation error decreases, but the estimation error may increase (i.e. we may have over-fitting). On the other hand, if we decrease the size and complexity of the hypothesis class, the estimation error may decrease, but the bias may increase (i.e. we may have under-fitting). So, we have a bias-complexity trade-off (where the bias refers to the approximation error or inductive bias) and the complexity refers to the complexity of the hypothesis class.

Error excess

In section 4.1 of this book also describes a similar (but equivalent) error decomposition, which is called error excess because it's a difference between the expected risk and the Bayes error (which is sometimes called inherent error or irreducible error), which they denote by $R^{*}$, while the other book above, which also points out that there's this equivalent error excess decomposition, denote it by $\epsilon_{\mathrm{Bayes}}$. So, here's the error excess

$$R(h)-R^{*}=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h)-R^{*}\right)}_{\text {approximation excess}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\text {estimation error}}$$

So, if you take $R^{*} = \epsilon_{\mathrm{Bayes}}$ from both sides of the equation, you end up with

$$R(h)=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h) \right)}_{\epsilon_{\mathrm{app}}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\epsilon_{\mathrm{est}}} \label{2}\tag{2}$$

which is equivalent to equation \ref{1}, where

  • $L_{\mathcal{D}}\left(h_{S}\right) \equiv R(h)$
  • $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) \equiv \inf _{h \in \mathcal{H}} R(h)$

Illustration

A nice picture that illustrates the relationship between these terms can be found in figure 4.1 of this book (p. 62).

enter image description here

Here, the red points are specific hypotheses. In this illustration, we can see that the best hypothesis (the Bayes hypothesis) lies outside our chosen hypothesis class $\mathcal{H}$. The distance between the risk of $h \in \mathcal{H}$ and the risk of $h^* = \operatorname{arg inf} _{h \in \mathcal{H}} R(h)$ is the estimation error, while the distance between $h^*$ and the Bayes hypothesis (i.e. the hypothesis that achieves the Bayes error) is the approximation excess in equation \ref{2}.

$\endgroup$
2
  • $\begingroup$ Could you please elaborate if the training error on my dataset can ever be zero ? Looking at equation above seems no. However I always thought these equations explain why the difference between train and test error can never be zero. $\endgroup$ Dec 14, 2021 at 10:51
  • $\begingroup$ @SiddhantTandon I will try to answer your question later. In the first book, they use $L$ to refer to the training error, while, in the second, they refer to it as the expected risk of the hypothesis. I think that this use of different terminology may cause confusion because here the training error is not defined. The second book actually calls what I called the "approximation excess" the "approximation error", but I was trying to connect the definitions of the two books in this answer. There's also a clear distinction between expected risk and empirical risk. $\endgroup$
    – nbro
    Dec 14, 2021 at 11:58
1
$\begingroup$

I think this is best explained by pictures. Please note that $h_{S}$ is the output of the ERM learner (under the hypothesis class $\mathcal{H}$) is denoted by $ERM_{\mathcal{H}}$, $f$ is the target hypothesis or the true labeling function. Also:

  1. By definition, the approximation error $=\epsilon_{app} := \underset{h\in \mathcal{H}}{min}\ L_{\mathcal{D}}(h)$ is always less than or equal to the estimation error (or the generalization risk/error) $=\epsilon_{est}=\mathcal{L}_{\mathcal{D}}(h_{\mathcal{S}})$.
  2. The estimation error $\epsilon_{est}=L_{\mathcal{D}}(h_{S})$ is NOT the training error (or empirical risk/error) $L_{S}(h_{S})$, rather the estimation error results because of the training error.

A small hypothesis class (or space) $\mathcal{H}$ not containing the target hypothesis $f$, the hypothesis $h_{S} \in \mathcal{H}$ found by the $ERM_{\mathcal{H}}$ learner via training, by some chance - say - small training set size, is not $h^{\star}$. Increasing the training set size may often help (i.e. make $h_{S}$ move closer or even equal to $h^{\star}$):

Small hypothesis class

Another relatively small but slightly better hypothesis space $\mathcal{H}^{'}$: The approximation error (generalization error comes from the best hypothesis) is smaller than that one, i.e. $h^{\star}$ closely approximates the target function:

Better hypothesis class

A good hypothesis space $\mathcal{H^{''}}$, of course the best hypothesis class is $\mathcal{H^{'''}}=\{f\}$ but most of the time we don't know what the (class of the) target hypothesis function $f$ is (if we know the function $f$ then learning is redundant), and especially under the assumption of agnostic PAC learning, it's often not a labeling function but rather a data generating distribution:

A good hypothesis class

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .