Recently I looked at simple techniques for time series smoothing and forecasting. One such primitive method is the single exponentially weighted moving average (SEWMA), defined as

where the sequences are indexed from 1. denotes an observed value of the time series and a SEWMA value. In words, this recursive definition expresses that the next SEWMA value is a weighted average of the curent observed and SEWMA values.

If I pose the question "What is the predicted value for the next time series observation?" we just apply the formula.

A typical imperative implementation

sewma <- function (alp, y) {This is R code, but it should look familiar enough to anyone who has written Java, C#, etc.

S <- y[1]

for (t in 2:length(y)) { S <- alp * y[t] + (1-alp) * S }

S

}

Haskell implementation

In Haskell, a fold is a way of recursively iterating a data structure, accumulating a return value. The left fold has type

foldl :: (a -> b -> a) -> a -> [b] -> aDenote one of the values from the conceptual sequence of accumulator values as . The function

foldl f s y = ...

`f`

maps from the current accumulator and list values to the next accumulator valuewhich is the form of the SEWMA equation above. The

`foldl1`

function is a specialisation of `foldl`

that uses the first value of the list as the initial accumulator value, yielding the implementationsewma alp = foldl1 (\s y -> alp * y + (1-alp) * s)

Revisiting R

R has the

`Reduce`

function for performing folds. sewma <- function (alp, ys) {

Reduce(function (S, y) { S <- alp * y + (1-alp) * S }, ys[2:length(ys)], ys[1])

}

Summary

If accumulating a value over a data structure can be represented with a step function of the form

then a left fold captures the recursive implementation.

## No comments:

Post a Comment