CODEWITHSUNDEEP
algorithmmathsignal-processingmoving-average
Bach
Bach

Reputation: 6217

"Time Aware" Exponential Moving Average

I am trying to figure out an online algorithm for "time aware" exponential moving average, sampled at varying times. By "time aware" I mean something like "giving more weight to data sampled at similar time of day", but (a) I'll give a more precise definition and (b) this is only an example for something more general that interests me.

I'll start by defining "time aware" by giving a precise example that assumes that data is sampled in constant intervals during the day; say, every 1 hour. In that case, I keep 24 different EMAs, and whenever data is sampled, I put it into the relevant EMA, taking its result and putting it in a general EMA of the results. So, at 12:00, Tuesday, I get the result of the EMA of the EMA results for 12:00, 11:00, 10:00, etc. where the EMA result for 12:00 is the EMA of some typical period of x days of data sampled at 12:00, etc.

This is an online algorithm which works well and provides reasonable results for the case where the data is sampled in constant time intervals. Without that assumption, its results become meaningless, or perhaps it is not even well defined.

The more general case can be described so: at a given moment I have a set of samples, each is a tuple (x,v) where x is some sample invariant (can be thought of as the sampling "location") and v is the sampling "value", and I would like to find out the (weighted) average at some "location" y, where the weights have negative correlation to the distances of y from x. This generalizes the previous problem by letting x be the pair (t,d) where t is the sampling time and d is the time-of-day (hour, in our case), and by defining some metric on the set of all such tuples which will describe well our needs. A reasonable demand would be to decide that if d is constant, the weight function on the distances will be similar to that of exponentially moving average (perhaps a continuous version of it).

The main problem is finding an efficient online algorithm that does the work in the general case, or define a specific metric which allows such an efficient online algorithm, or show that in almost any interesting case it is impossible.

Upvotes: 1

Views: 1102

Answers (1)

Michael Simbirsky
Michael Simbirsky

Reputation: 3103

EMA is essentially weighted average. When you combine several weighted averages with some weights you get a new weighted average with weights equal to products. This is exactly what you got with "time aware" EMA.

Of course, you can generalize it widely by assigning (almost arbitrary) weight as a function of "t".

As for online algorithm, you apparently want to add new points with very little efforts. EMA works nicely in this respect because EMA(x_1,...,x_n+1) = a*EMA(x_1,..., x_n) + (1-a)*x_n. You can find a lot of similar formulas for cases where weights have some symmetries or recursions (aka "group property"). Most likely, your recursive formula will have more summands in this case.

Upvotes: 1

Related Questions