4
$\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!

$\endgroup$
  • $\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 '16 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 '16 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 '16 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 '16 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 '16 at 3:47
0
$\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

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The classical CLT applies only to the sample mean, not to the sum. $\endgroup$ – Mur1lo Jun 22 '16 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 '16 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 '16 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 '16 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 '16 at 14:16

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.