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
3
$\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}} = \left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right)$$

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 training error $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) - \left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right) \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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.