2
$\begingroup$

I was reading some notes on machine learning when I came across the following sentence:

First, we may have a large estimation error. This means that, even if the true relationship between x and y is linear, it is hard for us to estimate it on the basis of a small (and potentially noisy) training set $S_n$. Our estimated parameters $\hat{\theta}$ will not be entirely correct. The larger the training set is, the smaller the estimation error will be.

I think the notes try to give a intuitive explanation of what the term means, but I was not sure if I understood it completely. Does having an estimation error mean that the way that we are estimating our parameters is wrong even if we are choosing from the correct set of classifiers? Say that our data was truly linear, but we still failed to to separate it. Is that a correct example?

Also, any answer relating it to the concepts of bias and variance (or overfitting and underfitting, will be greatly appreciated!)

I am looking for both a intuitive explanation and if there exists, a rigurous mathematical one for what that term means, it would be awesome!

$\endgroup$
  • $\begingroup$ Can you post a link to where these notes are coming from? $\endgroup$ – Jon Nov 3 '17 at 16:03
  • $\begingroup$ @jon I wish, I don't think I have access to them anymore. If I find them I will. $\endgroup$ – Pinocchio Nov 3 '17 at 20:27
10
$\begingroup$

A common decomposition of the error incurred when forming a predictive model is into three pieces.

1) Bayes Error: Even the best predictor will sometimes be wrong. Imagine predicting height based on gender. If you had the best predictor available you would still incur error because height does not depend solely on gender. The best predictor is typically called the Bayes predictor.

2) Approximation Error: When forming predictive models, because we want a tractable problem, and because we do not want to over-fit to the data (see 3), we restrict our set of models to some family. For example, in ordinary least squares regression we typically restrict ourselves to a linear model with normal noise which has fixed variance. If the nature of the data generating mechanism does not follow these rules, even the best predictor in this family to which we've restricted ourselves will have more error than the Bayes predictor.

3) Estimation Error: Once we've restricted ourselves to some family of predictors, we must use our data to pick one predictor from that family. What if we do not choose the right one? Then we incur more error. To be clear, I am not referring to picking the wrong predictor by accident, but rather by statistical inference on a limited set of data.

One of the most fundamental issues in machine learning is the interplay between approximation error and estimation error. As we enlarge our family of predictors our approximation error monotonically decreases, as we are able to capture more complex relationships. However, as our family of predictors increases, our estimation error increases as we over-fit more.

An extreme example of this is fitting a polynomial model to scalar data $x_i$, $y_i$. Imagine that the data was generated by some cubic polynomial plus error. Now suppose we increase the maximum degree in our polynomial $d = 0, 1, 2, 3, \dots$.

The first prediction will be the sample mean, lots of approximation error, little estimation error (but still some as this will most likely not be the true mean). As we increase $d$ we are trading approximation error for estimation error.

Once we hit $d=3$ we will probably make our best predictions, after all, we have all of the flexibility needed to produce the Bayes predictor, so we are only limited by the limited size of our data.

Eventually, as we increase $d$ we will have no error on our training set at all, and our data will have cooked up some higher order relations that don't exist at all.

$\endgroup$
4
$\begingroup$

Found this on a research paper:

enter image description here

hope it helps.

$\endgroup$
2
$\begingroup$

Let $F$ be a family of functions, $f^\prime$ is the best function given training dataset $D_n$, $R(f)$ be a function that give the estimation of loss of a given function $f$. $R^*$ is the minimum statistical risk (true risk) for all functions (including but not limited to those in $F$).

Expected Risk - Minimum Statistical Risk = $E[R(f^\prime )] - R^* = (E[R(f^\prime )] -\inf_{f in F} R(f)) + (\inf_{f \in F} R(f) - R^*)$ = Estimation error + Approximation Error

Or in other words, estimation error estimates how good is the algorithm that chooses $f$ from $F$ given training dataset, approximation error estimates how good the function family is.

$\endgroup$
  • 2
    $\begingroup$ It is not very clear how this answers the question. $\endgroup$ – Michael R. Chernick May 4 '17 at 19:05
  • $\begingroup$ @MichaelChernick I used an example of expected risk to illustrate the definition here of Estimation Error vs Approximation Error. See "Statistical Learning Theory". $\endgroup$ – tartaruga_casco_mole May 5 '17 at 12:53
  • 1
    $\begingroup$ Note that @MichaelChernick said "it is not very clear ...". For example, you do not define $R^*$. $\endgroup$ – GeoMatt22 May 5 '17 at 12:58
  • $\begingroup$ @GeoMatt22 I added some clarification. Let me know what else is unclear :) $\endgroup$ – tartaruga_casco_mole May 5 '17 at 14:03
  • $\begingroup$ A minor change for clarity would be to put the take-home message up front. For example put the last sentence first, but replacing the symbols with words, then start the rest with "Formally, ...". Perhaps also add a reference to "Statistical Learning Theory"? (Not my area, I know this is where I saw it explained, but only to expand on it :) ) To be clear though: I think your answer does not disagree with the top one, and it would need significant expansion to improve on that one ... up to you if it is worth it to do! $\endgroup$ – GeoMatt22 May 5 '17 at 15:22
2
$\begingroup$

The intuition is this: imagine you have to listen to what someone's saying and transcribe it. If you're sitting in a quite room with a person it's much easier to do than in a night club where music is blasting. The person is saying the same thing in the same voice, but it's harder to catch what he's saying because of the noise in the latter case. Now if you are wearing the headphones and the person is talking into the noise cancelling microphones, that's a different story. In fact you might get the same error rate in transcribing the speech in both an isolated room and a nightclub depending on the equipment used.

That's what estimation error is: you won't get every word the person is saying correctly because of the combination of interference of the noise in data and the estimation method. A "better" estimation method may allow you to eliminate a lot of noise. You want less noise in data but you also want good estimation methods.

$\endgroup$

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.