5
$\begingroup$

Our algorithm is about estimating the true statistic values from a data set. The data set is a table in relational database, we are going to estimate the statistic value for filtered records, like SUM("Sales") WHERE city="New York". We do this because the table is too large to calculate the true answer.

We use relative error for accuracy measurement at first, but we soon noticed that for small values, the error usually exceeds 100% and raises the average error. For example, if the true answer is 3, and my algorithm gives 9, it is a 200% error and will result in a very high average error, even if the other queries are answered properly. So I'm wondering if using relative error is not proper here, because if my algorithm always estimate a very small value, there will be unlikely for my algorithm to give an average error over 100%. It is unfair if my algorithm overestimates the true value.

Please note that I'm not trying to develop an algorithm to do the estimation, but I'm finding a fair measurement to evaluate the accuracy for different estimation algorithms. For example, we can estimate the sum by 1) Sampling from the original data set and estimate the sum with CLT, or 2) Draw a histogram offline and give an approximate answer for specific queries online according to the histogram. My question here is that under the traditional definition of relative error, the algorithm that always give small values tend to benefit more, so I'm looking for another measurement which is fairer.

I use the following formula in the past, but I'm wondering if it has any theories behind it:

$error=abs(x_{estimate}-x_{true})/{max(x_{estimate},x_{true})}$

So is there any better measurement to measure the error for an estimation algorithm?

Thanks!

Improve this question
$\endgroup$
6
  • $\begingroup$ Let me ask you if I really understood what your question. Lets suppose you have the data $x_1,\,x_2,...,x_n$. In your example you want to find out the value of $x_1 + x_2 +...+x_n$, but you are not able to perform the whole summation. Is that why you need the approximation? Do the algorithm you created require or use randomness in any sense? $\endgroup$
    – Mur1lo
    Jun 22, 2016 at 3:39
  • 1
    $\begingroup$ Can you say more about your situation, your data & your goals? This doesn't make sense to me, & I don't think this question is answerable. $\endgroup$
    – gung - Reinstate Monica
    Jun 22, 2016 at 4:04
  • $\begingroup$ @Mur1lo Yes, the original data set is too large, so we used some kind of algorithm to make an approximation for it. We don't include randomness in our algorithm. $\endgroup$
    – DarkZero
    Jun 22, 2016 at 5:09
  • $\begingroup$ @gung I added some background information for you. I am just wondering if it is reasonable to use relative error to measure the error of an estimation algorithm, because it punishes too much for overestimation... $\endgroup$
    – DarkZero
    Jun 22, 2016 at 5:10
  • $\begingroup$ In the denominator of your error formula why do you have max? Shouldn't it be only the true value? ref: en.wikipedia.org/wiki/Approximation_error $\endgroup$
    – Mur1lo
    Jun 23, 2016 at 3:47

2 Answers 2

Reset to default
1
$\begingroup$

I would suggest adding a "small" number to the denominator of your ratio.

$$error=\frac{|x_{estimate}-x_{true}|}{x_{true}+K}$$

You set $K$ equal to a "negligible" amount. For your example, setting $K=6$ would give an error of 66% instead of 200% for $K=0$.

The number to add will depend on your context and what kind of absolute errors are negligible

Improve this answer
$\endgroup$
1
$\begingroup$

There are a lot of measures for error of estimation and the one you provided is a valid one. But since you are working with the sum of random variables, I suggest using normal distribution (supported by the Central Limit Theorem) and instead of calculating once the sum of sales in New York, you’ll have to repeat that algorithm (at least 30 times) including randomness in your selection.

With your sample of 30 "sum of sales" you can use Normal Distribution and not only calculate the Mean Square Error as a good estimator of error, but also calculate probabilities.

Another good news is most of statistical inference is developed for variables with normal distribution.

Improve this answer
$\endgroup$
8
  • $\begingroup$ The classical CLT applies only to the sample mean, not to the sum. $\endgroup$
    – Mur1lo
    Jun 22, 2016 at 17:38
  • 1
    $\begingroup$ Central Theorem Limit it's actually a summary of different convergence laws. In en.wikipedia.org/wiki/Central_limit_theorem says " central limit theorem is any of a set of weak-convergence theorems in probability theory. They all express the fact that a sum of many independent and identically distributed (i.i.d.) random variables (...) will tend to be distributed according to (...) normal distribution" $\endgroup$
    – Camila Burne
    Jun 22, 2016 at 18:12
  • $\begingroup$ By "a sum" the author did not mean ANY sum. The mean is a particular type of sum, just like $\sum(X_i -\bar X)^2/n$ is another sum. The problem is that the variance of $\sum X_i$ goes to infinity and as a consequence it cannot converge in law to any distribution with finite variance. $\endgroup$
    – Mur1lo
    Jun 22, 2016 at 19:10
  • 2
    $\begingroup$ The recommendation to repeat an estimator 30 times in order to use a Normal distribution is truly strange. What support can you adduce for that? $\endgroup$
    – whuber ♦
    Jun 22, 2016 at 20:55
  • 1
    $\begingroup$ I'm not questioning the 30: I'm questioning the very idea that any replication is needed in the first place! That idea seems to belie a fundamental misconception about sampling and estimation. $\endgroup$
    – whuber ♦
    Jun 23, 2016 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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