 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Although I'd consider myself a math geek as well, I'm not so good when it comes
to statistics, so maybe someone can help me out with this one I need for
radiosity optimizations:
The problem I need to solve is probably quite similar to those famous quality
control jobs, where you produce (or buy) something and need to take samples, to
make sure with a certain confidence that only a certain maximum percentage of
the products fails to meet the specifications.
So in its simplest form, the question would be:
(1) Given an allowed percentage of failure p (say, 10% may be faulty), and a
desired test confidence q (say, I want to be 95% sure that those 10% are met),
how many samples do I need to take (need a formula though, not just values for
this case)?
However, being the miser I am, and each test being very costly, I don't want to
waste a single penny; so when my first samples look like I'll only have 1% of
failures, I get the idea that I might not have to do all these tests, but cut
them short.
(2) Again given allowed percentage of failure p and a confidence q, a number of
samples taken already N, and a number of failures among them M, the question
is: Can I stop testing here, because I (a) can be sure enough I'll have too
many failures and should better optimize my production, (b) can be sure enough
my level of quality is ok, or (c) do I need to continue taking samples before I
decide?
Now things get even more complicated: Let's say that with every failed product,
I can do an analysis of what went wrong, and eliminate that source of error
from my production (unfortunately I don't know by how much the overall quality
will improve by this). What can math tell me about this?
So much for the pure math; in case you're interested, and might have additional
ideas, this is how it relates to POV's radiosity (note that there's an
additional feedback here, that causes the percentage of failure to in fact
decrease as I take samples):
I intend to re-design the pretrace sequence, and throw out the current fixed
start and end resolution. Instead, I want to specify a (user-defined) maximum
allowed percentage of samples to be taken during final render, and have the
pretrace run until that requirement is met with a certain (hard-coded)
confidence. This will be done on a per-tile basis, and tiles proving to be
particularly problematic will be split up even more recursively, to get some
adaptive element.
In order to do this, while I am generating samples during pre-trace I want to
keep an eye on the ratio between the "radiosity queries" (not necessarily equal
to the number of rays shot) triggered, and the new samples gathered (the
"failures") to satisfy these queries (both per tile), and stop work on a tile
as soon as I'm confident enough that the final render will not take
(significantly) more new samples than the user declared as acceptable.
Questions that still bug me here:
- When can I stop work on a single tile because I can be confident that it has
enough samples?
- Is there a smart way to find out "on the fly" how good I am doing "right now"
(instead of just how good I have been doing "so far" since I started, which
will always look worse because I'll have improved since then with every
failure), without having to use designated "measuring intervals"?
- When does it make sense to "drill down" on a certain tile, and effectively
split it up into four? Doing it too soon might have memory requirements go
berserk. (Hm... thinking about it, maybe I should always keep track of the
pretrace quality separately for every quarter even while I'm still pretracing
it as a whole, and drill down as soon as I am happy with one quarter of the
tile but still significantly unhappy with some other.)
- When I "drill down" on a certain tile, is there a way I can re-use information
obtained on the whole combined tile so far? (Then again, maybe the smartest
thing to do when drilling down is to start a brand new measuring interval
anyway.)
Thanks in advance for any helpful or inspiring comments!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> The problem I need to solve is probably quite similar to those famous quality
> control jobs, where you produce (or buy) something and need to take samples, to
> make sure with a certain confidence that only a certain maximum percentage of
> the products fails to meet the specifications.
Actually the trend is to ensure 100% quality control
using automated inspection, but that's not what you
want to hear ;)
> (1) Given an allowed percentage of failure p (say, 10% may be faulty), and a
> desired test confidence q (say, I want to be 95% sure that those 10% are met),
> how many samples do I need to take (need a formula though, not just values for
> this case)?
I think such a statement usually says "we have to take x samples
*out of our total of N objects* to be 95% sure that ...". Do you
have some N? I suppose it might be something like the estimated
number of samples required by the final render pass.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Christian Froeschlin <chr### [at] chrfr de> wrote:
> > The problem I need to solve is probably quite similar to those famous quality
> > control jobs, where you produce (or buy) something and need to take samples, to
> > make sure with a certain confidence that only a certain maximum percentage of
> > the products fails to meet the specifications.
>
> Actually the trend is to ensure 100% quality control
> using automated inspection, but that's not what you
> want to hear ;)
.... and it probably won't work in practice with such things as, e.g., how much
amps a fuse can take before it blows :)
> > (1) Given an allowed percentage of failure p (say, 10% may be faulty), and a
> > desired test confidence q (say, I want to be 95% sure that those 10% are met),
> > how many samples do I need to take (need a formula though, not just values for
> > this case)?
>
> I think such a statement usually says "we have to take x samples
> *out of our total of N objects* to be 95% sure that ...". Do you
> have some N? I suppose it might be something like the estimated
> number of samples required by the final render pass.
Hum... sounds a bit familiar, so you may be right - but... well, unfortunately I
don't have such an N.
What I can tell for sure is the number of pixels that will be rendered; I can
also guesstimate the number of "radiosity queries" triggered per ray, by
measuring the average during pretrace. Unfortunately I can't correlate the
number of pixels with the number of rays by any means, due to stuff like focal
blur or adaptive antialiasing.
Still there must be some mathematical solution to this problem...?!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"clipka" <nomail@nomail> wrote:
> Still there must be some mathematical solution to this problem...?!
Looks like this is (or at least comes very close to) what I need (particularly
the "calculate sample size" function):
http://www.quality-one.com/products/inttools.php
If I understand it correctly, you feed it the number of failures observed during
testing, the "confidence level" (i.e. how sure you want to be about the result)
and the desired reliability (i.e. the percentage of failures to be expected "in
the field"), and it spits out the "sample size", i.e. how often you must have
made the test in order for the number of observed failures to be considered
acceptable.
Can anyone come up with a forumla for this?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"clipka" <nomail@nomail> wrote:
> Can anyone come up with a forumla for this?
I guess I have come up with something at last - can someone please verify that
I'm doing a valid test here?
This is the idea:
I will employ a "failure-free reliability testing" scheme to check whether I
have achieved the desired sample coverage, using the following parameters:
- reliability: user-specified sample coverage to achieve during pretrace
- confidence level: hard-coded to, say, 95%
- accepted failures: zero
- number of tests: n = ln (1-confidence) / ln (reliability)
with a "test" being a "radiosity query", that may either be satisfied by a
sample re-use ("pass"), or require a new sample to be gathered ("fail").
To get the required number of tests for the current tile, I will pretrace at a
suitable resolution, maybe multiple times (using jitter) if necessary, until I
have performed at least n tests, of which I will examine only the last n (in
fact, since I'll do a failure-free scheme, I'll just have to count the number
of re-uses since the last gather); if I find that I did not gather any new
sample for the last n tests, I can be confident enough that I have achieved the
desired coverage already.
If I find that I haven't reached the desired coverage yet, I check how many
consecutive re-uses I encountered since the last gather, and use this number N
to estimate the current coverage as N/(N+1). I use this estimate to get a first
estimate how many more rays I need to shoot in the current tile to achieve the
desired coverage, and maybe increase the pretrace resolution accordingly.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
looks very much like pruning in decision trees :
1) http://www.cs.cmu.edu/~tom/mlbook.html chapter III
2) Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann
Publishers, 1993.
Sorry, a little bit too long to explain in a mail.
The idea is :
knowing the number of errors (E) among N tries, find the error proba such that
seeing E errors among N is not rare.
binomial law -> approximated with normal law -> confidence intervals
Approximating binomial with normal law can be done when the sample size is circa
35
Hope this helps
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"fdecomite" <nomail@nomail> wrote:
> The idea is :
> knowing the number of errors (E) among N tries, find the error proba such that
> seeing E errors among N is not rare.
> binomial law -> approximated with normal law -> confidence intervals
>
> Approximating binomial with normal law can be done when the sample size is
> circa 35
>
> Hope this helps
To be honest - no, not at all :P
Actually I was searching for a simple formula, to feed my values in and be
happy... found a different solution for my problem meanwhile though.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am Sun, 04 Jan 2009 23:05:16 -0500 schrieb clipka:
> (2) Again given allowed percentage of failure p and a confidence q, a
> number of samples taken already N, and a number of failures among them
> M, the question is: Can I stop testing here, because I (a) can be sure
> enough I'll have too many failures and should better optimize my
> production, (b) can be sure enough my level of quality is ok, or (c) do
> I need to continue taking samples before I decide?
May be a bit late now, but...
Using the approximation of the binomial distribution by normal
distribution you can be sufficiently sure that no more samples have to be
taken when the number of failures k is smaller or equal than
k <= N * p - 0.5 - 1.645 * sqrt(N * p * (1-p))
if you assume a level of significance of 0.05. (case b)
With this test you try to keep the probability that you decide the
quality is ok although, in fact, it is bad as low as possible.
You can be sufficiently sure that your quality is too bad if the number
of failures k is greater than
k > N*p - 0.5 + 1.645 * sqrt(N * p * (1-p)
if you assume a level of significance of 0.05. (case a)
With this test you try to keep the probability that you decide the
quality is bad although, in fact, it is ok as low as possible
Otherwise you should take more samples. (case c) However, it may turn out
that the actual quality is very close to p (not really that bad but not
good enough) and you'll just take samples forever!
The value 1.645 was taken from a table of the normal distribution. Note
that this approximation can be very inaccurate for a low number of
samples or very values for p that are very close to 0 or 1. p should not
change while you take samples.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
