Permutation (symbolic)

SymbolicPermutation <: PermutationProbabilityEstimator

A symbolic, permutation based probabilities/entropy estimator.

Properties of original signal preserved

Permutations of a signal preserve ordinal patterns (sorting information). This implementation is based on Bandt & Pompe et al. (2002)^{[BandtPompe2002]}.

Description

Consider the $n$-element univariate time series $\{x(t) = x_1, x_2, \ldots, x_n\}$. Let $\mathbf{x_i}^{m, \tau} = \{x_j, x_{j+\tau}, \ldots, x_{j+(m-1)\tau}\}$ for $j = 1, 2, \ldots n - (m-1)\tau$ be the $i$-th state vector in a delay reconstruction with embedding dimension $m$ and reconstruction lag $\tau$. There are then $N = n - (m-1)\tau$ state vectors.

For an $m$-dimensional vector, there are $m!$ possible ways of sorting it in ascending order of magnitude. Each such possible sorting ordering is called a motif. Let $\pi_i^{m, \tau}$ denote the motif associated with the $m$-dimensional state vector $\mathbf{x_i}^{m, \tau}$, and let $R$ be the number of distinct motifs that can be constructed from the $N$ state vectors. Then there are at most $R$ motifs; $R = N$ precisely when all motifs are unique, and $R = 1$ when all motifs are the same.

Each unique motif $\pi_i^{m, \tau}$ can be mapped to a unique integer symbol $0 \leq s_i \leq M!-1$. Let $S(\pi) : \mathbb{R}^m \to \mathbb{N}_0$ be the function that maps the motif $\pi$ to its symbol $s$, and let $\Pi$ denote the set of symbols $\Pi = \{ s_i \}_{i\in \{ 1, \ldots, R\}}$.

The probability of a given motif is its frequency of occurrence, normalized by the total number of motifs (with notation from ^{[Fadlallah2013]}),

where the function $\mathbf{1}_A(u)$ is the indicator function of a set $A$. That is, $\mathbf{1}_A(u) = 1$ if $u \in A$, and $\mathbf{1}_A(u) = 0$ otherwise.

Permutation entropy can be computed over the probability distribution of symbols as $H(m, \tau) = - \sum_j^R p(\pi_j^{m, \tau}) \ln p(\pi_j^{m, \tau})$.

Estimation from univariate time series/datasets

• To compute permutation entropy for a univariate signal x, use the signature entropy(x::AbstractVector, est::SymbolicPermutation; τ::Int = 1, m::Int = 3).

• The corresponding (unordered) probability distribution of the permutation symbols for a univariate signal x can be computed using probabilities(x::AbstractVector, est::SymbolicPermutation; τ::Int = 1, m::Int = 3).

Estimation from multivariate time series/datasets

Although not dealt with in the original paper, numerically speaking, permutation entropy can also be computed for multivariate datasets (either embedded or consisting of multiple time series variables).

Then, just skip the delay reconstruction step, compute symbols directly from the $L$ existing state vectors $\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x_L}\}$, symbolize each $\mathbf{x_i}$ precisely as above, then compute the quantity

• To compute permutation entropy for a multivariate/embedded dataset x, use the signature entropy(x::AbstractDataset, est::SymbolicPermutation).

• To get the corresponding probability distribution for a multivariate/embedded dataset x, use probabilities(x::AbstractDataset, est::SymbolicPermutation).

symbolize(x::AbstractDataset, est::SymbolicPermutation) → Vector{Int}

Symbolize the vectors in x using Algorithm 1 from Berger et al. (2019)^[Berger2019].

The symbol length is automatically determined from the dimension of the input data vectors.

Example

Computing the order-5 permutation entropy for a 7-dimensional dataset.

using DelayEmbeddings, Entropies
D = Dataset([rand(7) for i = 1:1000])
symbolize(D, SymbolicPermutation(5))

encode_motif(x, m::Int = length(x)) → Int

Encode the length-m motif x (a vector of indices that would sort some vector v in ascending order) into its unique integer symbol, using Algorithm 1 in Berger et al. (2019)^[Berger2019].

Example

v = rand(5)

# The indices that would sort `v` in ascending order. This is now a permutation 
# of the index permutation (1, 2, ..., 5)
x = sortperm(v)

# Encode this permutation as an integer.
encode_motif(x)