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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jun 23, 2016 at 3:47

4 Answers 4

Reset to default
2
$\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
    Commented 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
    Commented 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
    Commented 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 ♦
    Commented 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 ♦
    Commented Jun 23, 2016 at 14:16
1
$\begingroup$

Just create a standard number like the centriam work out the probability equally to it's exact measurements. Then create possibility to get the final outcome. Then finally judgement weigh the answers

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm afraid I don't really follow this. Could you expand on it to make it more useful to readers? $\endgroup$
    – mkt
    Commented Jul 31, 2023 at 8:53
0
$\begingroup$

As I understand it correctly you have several estimates $\hat{\theta}_i$ of different population statistics $\theta_i$, and wish to create an expression for the error that may occur.

You currently compute the mean relative error (I assume using the absolute value of the deviation?)

$$\text{mean relative error} = \frac{1}{n} \sum_{i=1}^n \frac{|\hat{\theta}_i - \theta_i|}{\theta_i}$$

Your problem is that some of the relative errors $\frac{|\hat{\theta}_i - \theta_i|}{\theta_i}$ may be large while their importance is small because the error $|\hat{\theta}_i - \theta_i|$ is small.

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

I guess that you neither want the mean absolute error

$$\text{mean absolute error} = \frac{1}{n} \sum_{i=1}^n {|\hat{\theta}_i - \theta_i|}$$

and your use of the relative errors can be based on the idea/assumption that the relative error is constant among your values and the relevant value to describe the algorithm. For example your algorithm might be that you take a sample $k$ and multiply the average with the total size $m$ of the population to get an estimate of the sum in the population. Then your errors get multiplied with a factor $m$ but for the estimate of the error you would like to look at the error without that multiplication, hence use the relative error.

If your situation is like the above example, then you should just accept that some relative errors can be very large. Sure it may happen with a small value $\theta_i$ but if your model is right, then the same relative error can just as well happen with a large value of $\theta_i$.

Possibly your model is not right and the relative errors are not constant. In order to get a better view of this you could plot the error versus the true values, to get an idea of the distribution of the error and it's relation with the true value. Also you might use information about the distribution and models behind of the sales (why do they vary? different amount of people, different sales per person, different percentage of people that make a sale, etc.) to come up with a better performance measure.

For example, consider jars with 1000 marbles with red or white colour where the number of each colour is unknown. We estimate the sum of white/red marbles by sampling, without replacement, 50 marbles from the jars. Then the relationship between error and value looks like the following:

example

These type of relationships can be very different and depending on the relationship and your goal with computing the error you may want to apply a different statistic. Potentially it can be better to not use a single statistic and estimate the relationship between the error and the true value instead. Some algorithms may be better for larger values and worse for smaller values, to compare the algorithms you either come up with a cost function that allows you to average the error for different cases, or you display the comparison in error as a curve/graph.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is not a definite answer, as it will depend on the relationship that you have. But, the main point is that you need to figure out that relationship. $\endgroup$
    – Sextus Empiricus
    Commented Jul 31, 2023 at 9:28

Your Answer

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

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