Data.Mealy

Online statistics for ordered data (such as time-series data), modelled as mealy machines

Types

newtype Mealy a b

A Mealy is a triple of functions

• (a -> b) inject Convert an input into the state type.
• (b -> a -> b) step Update state given prior state and (new) input.
• (c -> b) extract Convert state to the output type.

By adopting this order, a Mealy sum looks like:

M id (+) id

where the first id is the initial injection to a contravariant position, and the second id is the covriant extraction.

inject kicks off state on the initial element of the Foldable, but is otherwise be independent of step.

scan (M e s i) (x : xs) = e <$> scanl' s (i x) xs

Constructors

Mealy

Fields

• l1 :: L1 a b

Instances

Profunctor Mealy

Defined in Data.Mealy

Methods

dimap :: (a -> b) -> (c -> d) -> Mealy b c -> Mealy a d

lmap :: (a -> b) -> Mealy b c -> Mealy a c

rmap :: (b -> c) -> Mealy a b -> Mealy a c

(#.) :: Coercible c b => q b c -> Mealy a b -> Mealy a c

(.#) :: Coercible b a => Mealy b c -> q a b -> Mealy a c

Functor (Mealy a)

Defined in Data.Mealy

Methods

fmap :: (a0 -> b) -> Mealy a a0 -> Mealy a b

(<$) :: a0 -> Mealy a b -> Mealy a a0

Applicative (Mealy a)

Defined in Data.Mealy

Methods

pure :: a0 -> Mealy a a0

(<*>) :: Mealy a (a0 -> b) -> Mealy a a0 -> Mealy a b

liftA2 :: (a0 -> b -> c) -> Mealy a a0 -> Mealy a b -> Mealy a c

(*>) :: Mealy a a0 -> Mealy a b -> Mealy a b

(<*) :: Mealy a a0 -> Mealy a b -> Mealy a a0

Category Mealy

Defined in Data.Mealy

Methods

id :: Mealy a a

(.) :: Mealy b c -> Mealy a b -> Mealy a c

pattern M :: (a -> c) -> (c -> a -> c) -> (c -> b) -> Mealy a b

Pattern for a Mealy.

M extract step inject

scan :: Mealy a b -> [a] -> [b]

Run a list through a Mealy and return a list of values for every step

length (scan _ xs) == length xs

fold :: Mealy a b -> [a] -> b

Fold a list through a Mealy.

cosieve == fold

newtype Averager a b

Most common statistics are averages, which are some sort of aggregation of values (sum) and some sort of sample size (count).

Constructors

Averager

Fields

• sumCount :: (a, b)

Instances

(Eq a, Eq b) => Eq (Averager a b)

Defined in Data.Mealy

Methods

(==) :: Averager a b -> Averager a b -> Bool

(/=) :: Averager a b -> Averager a b -> Bool

(Show a, Show b) => Show (Averager a b)

Defined in Data.Mealy

Methods

showsPrec :: Int -> Averager a b -> ShowS

show :: Averager a b -> String

showList :: [Averager a b] -> ShowS

(Additive a, Additive b) => Semigroup (Averager a b)

Defined in Data.Mealy

Methods

(<>) :: Averager a b -> Averager a b -> Averager a b

sconcat :: NonEmpty (Averager a b) -> Averager a b

stimes :: Integral b0 => b0 -> Averager a b -> Averager a b

(Additive a, Additive b) => Monoid (Averager a b)

av mempty == nan

Defined in Data.Mealy

Methods

mempty :: Averager a b

mappend :: Averager a b -> Averager a b -> Averager a b

mconcat :: [Averager a b] -> Averager a b

pattern A :: a -> b -> Averager a b

Pattern for an Averager.

A sum count

av :: Divisive a => Averager a a -> a

extract the average from an Averager

av gives NaN on zero divide

av_ :: (Eq a, Additive a, Divisive a) => Averager a a -> a -> a

substitute a default value on zero-divide

av_ (Averager (0,0)) x == x

online :: (Divisive b, Additive b) => (a -> b) -> (b -> b) -> Mealy a b

online f g is a Mealy where f is a transformation of the data and g is a decay function (convergent tozero) applied at each step.

online id id == av

Statistics

Generate some random variates for the examples.

xs0, xs1 & xs2 are samples from N(0,1)

xsp is a pair of N(0,1)s with a correlation of 0.8

>>> :set -XDataKinds
>>> import Control.Category ((>>>))
>>> import Data.List
>>> import Data.Mealy.Simulate
>>> g <- create
>>> xs0 <- rvs g 10000
>>> xs1 <- rvs g 10000
>>> xs2 <- rvs g 10000
>>> xsp <- rvsp g 10000 0.8

ma :: (Divisive a, Additive a) => a -> Mealy a a

A moving average using a decay rate of r. r=1 represents the simple average, and r=0 represents the latest value.

>>> fold (ma 0) (fromList [1..100])
100.0

>>> fold (ma 1) (fromList [1..100])
50.5

>>> fold (ma 0.99) xs0
-4.292501077490672e-2

A change in the underlying mean at n=10000 in the chart below highlights the trade-off between stability of the statistic and response to non-stationarity.

absma :: (Divisive a, Additive a, Signed a) => a -> Mealy a a

absolute average

>>> fold (absma 1) xs0
0.7894201075535578

sqma :: (Divisive a, Additive a) => a -> Mealy a a

average square

fold (ma r) . fmap (**2) == fold (sqma r)

std :: (Divisive a, ExpField a) => a -> Mealy a a

standard deviation

The construction of standard deviation, using the Applicative instance of a Mealy:

(\s ss -> sqrt (ss - s ** (one+one))) <$> ma r <*> sqma r

The average deviation of the numbers 1..1000 is about 1 / sqrt 12 * 1000 https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)#Standard_uniform

>>> fold (std 1) [0..1000]
288.9636655359978

The average deviation with a decay of 0.99

>>> fold (std 0.99) [0..1000]
99.28328803163829

>>> fold (std 1) xs0
0.9923523681261158

cov :: Field a => Mealy a a -> Mealy (a, a) a

The covariance of a tuple given an underlying central tendency fold.

>>> fold (cov (ma 1)) xsp
0.8011368250045314

corrGauss :: ExpField a => a -> Mealy (a, a) a

correlation of a tuple, specialised to Guassian

>>> fold (corrGauss 1) xsp
0.8020637696465039

corr :: ExpField a => Mealy a a -> Mealy a a -> Mealy (a, a) a

a generalised version of correlation of a tuple

>>> fold (corr (ma 1) (std 1)) xsp
0.8020637696465039

corr (ma r) (std r) == corrGauss r

beta1 :: ExpField a => Mealy a a -> Mealy (a, a) a

The beta in a simple linear regression of an (independent variable, single dependent variable) tuple given an underlying central tendency fold.

This is a generalisation of the classical regression formula, where averages are replaced by Mealy statistics.

\[ \begin{align} \beta & = \frac{n\sum xy - \sum x \sum y}{n\sum x^2 - (\sum x)^2} \\ & = \frac{n^2 \overline{xy} - n^2 \bar{x} \bar{y}}{n^2 \overline{x^2} - n^2 \bar{x}^2} \\ & = \frac{\overline{xy} - \bar{x} \bar{y}}{\overline{x^2} - \bar{x}^2} \\ \end{align} \]

>>> fold (beta1 (ma 1)) $ zipWith (\x y -> (y, x + y)) xs0 xs1
0.9953875263096014

alpha1 :: ExpField a => Mealy a a -> Mealy (a, a) a

The alpha in a simple linear regression of an (independent variable, single dependent variable) tuple given an underlying central tendency fold.

\[ \begin{align} \alpha & = \frac{\sum y \sum x^2 - \sum x \sum xy}{n\sum x^2 - (\sum x)^2} \\ & = \frac{n^2 \bar{y} \overline{x^2} - n^2 \bar{x} \overline{xy}}{n^2 \overline{x^2} - n^2 \bar{x}^2} \\ & = \frac{\bar{y} \overline{x^2} - \bar{x} \overline{xy}}{\overline{x^2} - \bar{x}^2} \\ \end{align} \]

>>> fold (alpha1 (ma 1)) $ zipWith (\x y -> ((3+y), x + 0.5 * (3 + y))) xs0 xs1
1.1880996822796197e-2

reg1 :: ExpField a => Mealy a a -> Mealy (a, a) (a, a)

The (alpha, beta) tuple in a simple linear regression of an (independent variable, single dependent variable) tuple given an underlying central tendency fold.

>>> fold (reg1 (ma 1)) $ zipWith (\x y -> ((3+y), x + 0.5 * (3 + y))) xs0 xs1
(1.1880996822796197e-2,0.49538752630956845)

beta :: (Field a, Field a, KnownNat n) => a -> Mealy (Array '[n] a, a) (Array '[n] a)

multiple regression

\[ \begin{align} {\hat {{\mathbf {B}}}}=({\mathbf {X}}^{{{\rm {T}}}}{\mathbf {X}})^{{ -1}}{\mathbf {X}}^{{{\rm {T}}}}{\mathbf {Y}} \end{align} \]

\[ \begin{align} {\mathbf {X}}={\begin{bmatrix}{\mathbf {x}}_{1}^{{{\rm {T}}}}\\{\mathbf {x}}_{2}^{{{\rm {T}}}}\\\vdots \\{\mathbf {x}}_{n}^{{{\rm {T}}}}\end{bmatrix}}={\begin{bmatrix}x_{{1,1}}&\cdots &x_{{1,k}}\\x_{{2,1}}&\cdots &x_{{2,k}}\\\vdots &\ddots &\vdots \\x_{{n,1}}&\cdots &x_{{n,k}}\end{bmatrix}} \end{align} \]

let ys = zipWith3 (\x y z -> 0.1 * x + 0.5 * y + 1 * z) xs0 xs1 xs2
let zs = zip (zipWith (\x y -> fromList [x,y] :: F.Array '[2] Double) xs1 xs2) ys
fold (beta 0.99) zs

0.4982692361226971, 1.038192474255091

alpha :: (Field a, ExpField a, KnownNat n) => a -> Mealy (Array '[n] a, a) a

alpha in a multiple regression

reg :: (Field a, ExpField a, KnownNat n) => a -> Mealy (Array '[n] a, a) (Array '[n] a, a)

multiple regression

let ys = zipWith3 (\x y z -> 0.1 * x + 0.5 * y + 1 * z) xs0 xs1 xs2
let zs = zip (zipWith (\x y -> fromList [x,y] :: F.Array '[2] Double) xs1 xs2) ys
fold (reg 0.99) zs

([0.4982692361226971, 1.038192474255091],2.087160803386695e-3)

asum :: Additive a => Mealy a a

accumulated sum

aconst :: b -> Mealy a b

constant Mealy

delay1 :: a -> Mealy a a

delay input values by 1

delay

Arguments

:: [a]

initial statistical values, delay equals length

-> Mealy a a

delays values by n steps

delay [0] == delay1 0

delay [] == id

delay [1,2] = delay1 2 . delay1 1

>>> scan (delay [-2,-1]) [0..3]
[-2,-1,0,1]

Autocorrelation example:

scan (((,) <$> id <*> delay [0]) >>> beta (ma 0.99)) xs0

depState :: (a -> b -> a) -> Mealy a b -> Mealy a a

Add a state dependency to a series.

Typical regression analytics tend to assume that moments of a distributional assumption are unconditional with respect to prior instantiations of the stochastics being studied.

For time series analytics, a major preoccupation is estimation of the current moments given what has happened in the past.

IID:

\[ \begin{align} x_{t+1} & = alpha_t^x + s_{t+1}\\ s_{t+1} & = alpha_t^s * N(0,1) \end{align} \]

Example: including a linear dependency on moving average history:

\[ \begin{align} x_{t+1} & = (alpha_t^x + beta_t^{x->x} * ma_t^x) + s_{t+1}\\ s_{t+1} & = alpha_t^s * N(0,1) \end{align} \]

>>> let xs' = scan (depState (\a m -> a + 0.1 * m) (ma 0.99)) xs0
>>> let ma' = scan ((ma (1 - 0.01)) >>> delay [0]) xs'
>>> let xsb = fold (beta1 (ma (1 - 0.001))) $ drop 1 $ zip ma' xs'
>>> -- beta measurement if beta of ma was, in reality, zero.
>>> let xsb0 = fold (beta1 (ma (1 - 0.001))) $ drop 1 $ zip ma' xs0
>>> xsb - xsb0
9.999999999999976e-2

This simple model of relationship between a series and it's historical average shows how fragile the evidence can be.

In unravelling the drivers of this result, the standard deviation of a moving average scan seems well behaved for r > 0.01, but increases substantively for values less than this. This result seems to occur for wide beta values. For high r, the standard deviation of the moving average seems to be proprtional to r**0.5, and equal to around (0.5*r)**0.5.

fold (std 1) (scan (ma (1 - 0.01)) xs0)

data Model1

a linear model of state dependencies for the first two moments

\[ \begin{align} x_{t+1} & = (alpha_t^x + beta_t^{x->x} * ma_t^x + beta_t^{s->x} * std_t^x) + s_{t+1}\\ s_{t+1} & = (alpha_t^s + beta_t^{x->s} * ma_t^x + beta_t^{s->s} * std_t^x) * N(0,1) \end{align} \]

Constructors

Model1

Fields

• alphaX :: Double
• alphaS :: Double
• betaMa2X :: Double
• betaMa2S :: Double
• betaStd2X :: Double
• betaStd2S :: Double

Instances

Eq Model1

Defined in Data.Mealy

Methods

(==) :: Model1 -> Model1 -> Bool

(/=) :: Model1 -> Model1 -> Bool

Show Model1

Defined in Data.Mealy

Methods

showsPrec :: Int -> Model1 -> ShowS

show :: Model1 -> String

showList :: [Model1] -> ShowS

Generic Model1

Defined in Data.Mealy

Associated Types

type Rep Model1 :: Type -> Type

Methods

from :: Model1 -> Rep Model1 x

to :: Rep Model1 x -> Model1

type Rep Model1

Defined in Data.Mealy

type Rep Model1 = D1 (MetaData "Model1" "Data.Mealy" "mealy-0.0.1-GP14lgtbKtV3sh2lziW7Q7" False) (C1 (MetaCons "Model1" PrefixI True) ((S1 (MetaSel (Just "alphaX") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double) :*: (S1 (MetaSel (Just "alphaS") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double) :*: S1 (MetaSel (Just "betaMa2X") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double))) :*: (S1 (MetaSel (Just "betaMa2S") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double) :*: (S1 (MetaSel (Just "betaStd2X") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double) :*: S1 (MetaSel (Just "betaStd2S") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Double)))))

zeroModel1 :: Model1

depModel1 :: Double -> Model1 -> Mealy Double Double

Apply a model1 relationship using a single decay factor.

>>> :set -XOverloadedLabels
>>> fold (depModel1 0.01 (zeroModel1 & #betaMa2X .~ 0.1)) xs0
-0.47228537123218206

conversion

foldB :: Reifies s W => (BVar s Double -> BVar s Double) -> BVar s Double -> BVar s [Double] -> BVar s Double

maB :: Reifies s W => BVar s Double -> BVar s [Double] -> BVar s Double

median

data Medianer a b

A rough Median. The average absolute value of the stat is used to callibrate estimate drift towards the median

Constructors

Medianer

Fields

• medAbsSum :: a
• medCount :: b
• medianEst :: a

onlineL1 :: (Ord b, Field b, Signed b) => b -> b -> (a -> b) -> (b -> b) -> Mealy a b

onlineL1 takes a function and turns it into a Fold where the step is an incremental update of an (isomorphic) median statistic.

onlineL1' :: (Ord b, Field b, Signed b) => b -> b -> (a -> b) -> (b -> b) -> Mealy a (b, b)

onlineL1' takes a function and turns it into a Mealy where the step is an incremental update of an (isomorphic) median statistic.

maL1 :: (Ord a, Field a, Signed a) => a -> a -> a -> Mealy a a

moving median > L.fold (maL1 inc d r) [1..n] 93.92822312742108

absmaL1 :: (Ord a, Field a, Signed a) => a -> a -> a -> Mealy a a

moving absolute deviation