Time Series

 Finally, compare you results to say (Theta+ARIMA+ETS)/3 - this may be a humbling experience :-)
 
Hey, I recently researched time series classification for a personal project. I'm going to dump some of my notes here, with the caveat that I'm not by any means an expert in the area.
First, the most helpful summary paper I've found in this area is The Great Time Series 

Here's another awesome resource with open source implementations and datasets to play with: http://timeseriesclassification.com/index.php
PREPROCESSING
  • Z-normalization transforms time series values so that the mean is ~0, and the standard deviation is ~1. See https://jmotif.github.io/sax-vsm_site/morea/algorithm/znorm.html "in some cases, this preprocessing is not recommended as it introduces biases. For example, if the signal variance is significantly small, z-normalization will simply overamplify the noise to the unit of amplitude."
  • Piecewise Aggregate Approximation (PAA) - It's kind of like a histogram where you add up all the values in a window, but you scale it down by averaging them together. Think "avg pooling". There's a special distance measure that reduces the complexity, so it's performant. SAX (see below) uses PAA to transform the time series to a string of words.
SUPERVISED ML
  • Some neural models are already well-suited for spatial input out of the box, like RNNs/LSTMs, or CNNs
INSTANCE-BASED CLASSIFICATION
  • Dynamic time-warping - this is often used as a baseline, because it's very simple and apparently performs well. Uses dynamic programming to align the two sequences according to their closest fit. It's hella slow, but there are ways to speed it up like FastDTW and the LB Keogh lower bound. Con: apparently performance degrades with long time series, relatively short features of interest, and moderate noise
  • Weighted DTW - adds a multiplicative weight penalty based on the warping distance between points in the warping path
  • Time Warp Edit distance (TWE) - an elastic distance metric that gives you control via a stiffness parameter, v. Stiffness enforces a multiplicative penalty on the distance between matched points in a manner similar to WDTW.
  • Move-Split-Merge (MPM) - Kind of like string edit distance, but for parts of a time series.
  • Derivative DTW (DDTW) - a weighted combination of raw series and first-order differences for NN classification with full-window DTW.
SVM + String Kernels
Most of these methods were originally applied to gene protein classification, but they should generalize.
  • k-spectrum kernel - The kernel essentially asks "how many subsequences do they have in common?" The vector space is the set of all possible k-mers, and each value is 1 if the sequence contains the given subsequence, otherwise 0. The kernel function compares two examples by taking the inner product.
  • Mismatch kernel - Similar to the k-spectrum, but allow for approximate matches by looking for subsequences within a local edit distance neighborhood.
  • Spatial representation kernel - Similar to k-spectrum, but matches don't have to be contiguous, so ABCD matches with ABZZCD.
  • Fisher kernel - I had a harder time following this one, but I think it trains a HMM on positive classes, then computes a feature vector for each example by taking the gradient of the HMM's model parameters at that point, and train a classic SVM in this new feature space.
SHAPELETS
Informally, shapelets are time series subsequences which are in some sense maximally representative of a class. You can use the distance to the shapelet, rather than the distance to the nearest neighbor to classify objects. Shapelets are local features, so they're robust to noise in the rest of the instance. They're also phase-invariant: location of a shapelet has no baring on the classification.
Basically, a random forrest is trained, where each split point of the tree is a shapelet. You slide a window across training examples, looking for shapelets (subsequences) that split the dataset in such a way that maximizes information gain.
  • Logical shapelets - multiple shapelets are combined in logic expressions
  • Fast shapelets - Instead of a full enumerative search at each node, the fast shapelets algorithm discretises and approximates the shapelets using a dictionary of SAX words.
  • Shapelet transform - separates the shapelet discovery from the classifier by finding the top k shapelets on a single run (in contrast to the decision tree, which searches for the best shapelet at each node). The shapelets are used to transform the data, where each attribute in the new dataset represents the distance of a series to one of the shapelets. Then you can train a new model on top of this dataset.
  • Learned shapelets - adopts a heuristic gradient descent shapelet search procedure rather than enumeration. LS finds k shapelets that, unlike FS and ST, are not restricted to being subseries in the training data.
INTERVAL-BASED
  • Time Series Forest (TSF) - Similar to shapelets. The authors overcome the problem of the huge interval feature space by employing a random forest approach, using summary statistics of each interval as features. Training a single tree involves selecting sqrt(m) random intervals, generating the mean, standard deviation and slope, then creating and training a tree on the resulting 3*sqrt(m) features.
  • Learned Pattern Similarity (LPS)
  • Piecewise-linear approximations (PLA) - Also similar to shapelets, but rather than use subsequences as candidate features, since there are too many to consider, they use linear approximations. They "discretize" each time series, using a regression tree to approximate it in a series of flat lines. They consider different sized portions of this approximation at each split of the decision tree, instead of just the whole thing.
BAG OF WORDS
These approaches can be better than shapelets when the number of patterns is important, instead of just finding the closest match to a pattern.
  • Symbolic Aggregate approXimation (SAX) - SAX transforms a time-series X of length n into a string of arbitrary length w. Step 1: convert time series to Piecewise Aggregate Approximation representation (see notes above). Step 2: Z-normalize, then pick equal-areas-under-the-curve to decide on an alphabet, so that each word has approximately equal likelihood of occurring. Helpful example: https://jmotif.github.io/sax-vsm_site/morea/algorithm/SAX.html
  • SAX Distance - a formula to compare two SAX representations of time series. Basically mean squared error between letters, while allowing close letters to count as equal.
  • Bag-of-Words Vector Space Model (SAX-VSM) - Uses SAX representation like above, but then applies TF-IDF weighting to the resultsing word-document matrix.
  • Bag-of-Patterns (BOP) - Applies SAX to each window to form a word (If consecutive windows produce identical words, then only the first of that run is recorded to avoid over counting trivial matches). The distribution of words over a series forms a count histogram. To classify new samples, the same transform is applied to the new series and the nearest neighbour histogram within the training matrix found.
  • Time Series Bag-of-Features (TSBF) - Local information is captured from multiple subsequences selected from random locations and of random lengths and partitioned into shorter intervals to detect patterns represented by a series of measurements over shorter time segments. Local features are aggregated into a compact codebook, and combined with other info like subsequence locations and various global features, on top of which a supervised learning can be trained.
  • Bag-of-SFA-Symbols (BOSS) - It first extracts substructures (patterns) from a time series using Symbolic Fourier Approximation (which like SAX, converts to words). After a discrete fourier transform, do low pass filtering and quantisation (via Multiple Coefficient Binning), which reduces noise and allows for string matching algorithms to be applied. Sequences of words are counted and histogrammed. Two time series are then compared based on the differences in the set of noise reduced patterns (a modified Euclidean distance)
  • BOSSVS - BOSS with TF-IDF weighting and cosine similarity, similar to SAX-SVM
  • WEASEL (Word ExtrAction for time Series cLassification) - similar to BoF/TSBF/BOSS
FEATURE-BASED METHODS
  • FRESH - Extract lots of statistics about time series (min, max, median, peaks, etc), use statistical p-values to determine which them are useful for learning the problem at hand, and train another model on top of it.
ENSEMBLE METHODS