Permutation (symbolic)

SymbolicPermutation(; τ = 1, m = 3) <: 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]} and Berger et al. (2019) ^[Berger2019].

Estimation

Univariate time series

To estimate probabilities or entropies from univariate time series, use the following methods:

• probabilities(x::AbstractVector, est::SymbolicPermutation). Constructs state vectors from x using embedding lag τ and embedding dimension m. The ordinal patterns of the state vectors are then symbolized, and probabilities are taken as the relative frequency of symbols.
• genentropy(x::AbstractVector, est::SymbolicPermutation; α=1, base = 2) computes probabilities by calling probabilities(x::AbstractVector, est::SymbolicPermutation), then computer the order-α generalized entropy to the given base.

See below for in-place versions below allow you to provide a pre-allocated symbol array s for faster repeated computations of input data of the same length.

Multivariate datasets

Although not dealt with in the original Bandt & Pompe (2002) paper, numerically speaking, permutation entropy can also be computed for multivariate datasets with dimension ≥ 2. Such datasets may be, for example, preembedded time series. Then, just skip the delay reconstruction step, compute and symbols directly from the $L$ existing state vectors $\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x_L}\}$.

• probabilities(x::Dataset, est::SymbolicPermutation). Compute ordinal patterns of the state vectors of x directly (without doing any embedding), symbolize those patterns, and compute probabilities as relative frequencies of symbols.
• genentropy(x::Dataset, est::SymbolicPermutation). Computes probabilities from symbol frequencies using probabilities(x::Dataset, est::SymbolicPermutation), then computes the order-α generalized (permutation) entropy to the given base.

Speeding up repeated computations

probabilities!(s::Vector{Int}, x::AbstractVector, est::SymbolicPermutation) → ps::Probabilities
probabilities!(s::Vector{Int}, x::AbstractDataset, est::SymbolicPermutation) → ps::Probabilities

Description

Embedding, ordinal patterns and symbolization

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\}}$.

Probability computation

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.

Entropy computation

The generalized order-α Renyi entropy^[Rényi1960] can be computed over the probability distribution of symbols as $H(m, \tau, \alpha) = \dfrac{\alpha}{1-\alpha} \log \left( \sum_{j=1}^R p_j^\alpha \right)$. Permutation entropy, as described in Bandt and Pompe (2002), is just the limiting case as $α \to1$, that is $H(m, \tau) = - \sum_j^R p(\pi_j^{m, \tau}) \ln p(\pi_j^{m, \tau})$.

symbolize(x::AbstractVector{T}, est::SymbolicPermutation) where {T} → Vector{Int}
symbolize(x::AbstractDataset{m, T}, est::SymbolicPermutation) where {m, T} → Vector{Int}

If x is an m-dimensional dataset, then symbolize x by converting each m-dimensional state vector as a unique integer in the range $1, 2, \ldots, m-1$, using encode_motif.

If x is a univariate time series, first x create a delay reconstruction of x using embedding lag est.τ and embedding dimension est.m, then symbolizing the resulting state vectors with encode_motif.

Examples

Symbolize a 7-dimensional dataset. Motif lengths (or order of the permutations) are inferred to be 7.

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

Symbolize a univariate time series by first embedding it in dimension 5 with embedding lag 2. Motif lengths (or order of the permutations) are therefore 5.

using DelayEmbeddings, Entropies
n = 5000
x = rand(n)
s = symbolize(x, SymbolicPermutation(m = 5, τ = 2))

The integer vector s now has length n-(m-1)*τ = 4992, and each s[i] contains the integer symbol for the ordinal pattern of state vector x[i].

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)