1
$\begingroup$

My understanding is when we are computing sufficient statistics on a stream, when a new instance arrives, the value of the new instance is added to the already computed sufficient stats. so there is no way of forgetting/decrementing any data since the value of all the current data is summarised in sufficient stats but this is just an intuitive explanation. how do I proof this using the formula?

Thanks

$\endgroup$
4
  • $\begingroup$ "Added to" is, unless meant very loosely, not general enough: the sufficient statistic might be the sample maximum, say. $\endgroup$ – Scortchi - Reinstate Monica Jun 13 '17 at 8:59
  • $\begingroup$ hi, the question is if we defined the concept of sufficient statistics assuming that we add observations with the ”Increment” operator. Can the sufficient statistics be computed if we also forget data with the ”Decrement” operator? $\endgroup$ – MugB Jun 13 '17 at 9:02
  • $\begingroup$ @MugB aren't you in effect restricting yourself to the exponential family? In that family, the sufficient statistic of a set of independent identically distributed data observations is simply the sum of individual sufficient statistics $\endgroup$ – Glen_b Jun 13 '17 at 10:52
  • $\begingroup$ @Glen_b if I understand you correctly, what you are saying is say if at timepoint 1, I have 100 data points for which i compute the sufficient stats for and at time point 2 I see another 100 data points and compute the sufficient stats again and say i am now considering that the data points in t1 is old and I want to forget them (considering limited memory, computational complexity, etc) so does that mean that I don't actually have to use the decrement operator? $\endgroup$ – MugB Jun 13 '17 at 17:31
1
$\begingroup$

Simply write the value out. Here for the mean: $$ \mu_n = n^{-1}\sum_i^n{x_i}=n^{-1}(\sum^{n-1}_i{x_i}+x_n)=n^{-1}((n-1)\mu_{n-1}+x_n)$$ And it is proved. For variance check out https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance online algorithm. In order to include forgetting to he variance set n = min(n,1/gamma), where gamma is the forgetting factor.

For minimum and maximum is proved by saying that the maximum of the maximum of two sets is the maximum of the union set. So set 1 is all previous observations and set 2 is the new observation.

Median can't be found using this iterative procedure.

$\endgroup$
5
  • $\begingroup$ For minimum and maximum is proved by saying that the maximum of the maximum of two sets is the maximum of the union set. So set 1 is all previous observations and set 2 is the new observation. $\endgroup$ – Peter Mølgaard Pallesen Jun 13 '17 at 9:06
  • $\begingroup$ Thanks Peter, but what if we are computing sufficient stats over a stream of data whereby we will need to take into account the sufficient stats that includes the arrival of a new instance - how do we forget or decrement the instance if it is no longer needed i.e old data? can this be done for standard deviation as well? $\endgroup$ – MugB Jun 13 '17 at 9:08
  • $\begingroup$ Use a forgetting factor: $$ \mu_n =(1- \gamma_n)*\mu_{n-1}+\gamma_n*x_n$$ Where $$ \gamma_n=max(1/n,\gamma)$$ So here you are forgetting with a factor of gamma when 1/n becomes smaller than gamma. So if you have 100 observations and a gamma of 0.05 then the newest observation have a weight of 1/20 and therefore have a higher weight than the past observations. Which are gradually being forgotten. $\endgroup$ – Peter Mølgaard Pallesen Jun 13 '17 at 9:12
  • $\begingroup$ For standard deviation you update the variance and take the sqaure root to obtain the standard deviation. $\endgroup$ – Peter Mølgaard Pallesen Jun 13 '17 at 9:18
  • $\begingroup$ okay i will try to implement this for variance to get the standard dev while being able to forget old data. thanks for your help and time. $\endgroup$ – MugB Jun 13 '17 at 9:20

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.