Logo ISMLL

LEARNING TIME-SERIES SHAPELETS

Josif Grabocka, Nicolas Schilling, Martin Wistuba, Lars Schmidt-Thieme
Contact: email

Partially funded by the
[REDUCTION] project
Reduction logo

This website is a supportive page for the paper: Josif Grabocka, Nicolas Schilling, Martin Wistuba, Lars Schmidt-Thieme (2014): Learning Time-Series Shapelets, in Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2014  [read paper here]

The purpose of this work is to learn (not search for) time-series shapelets, which are discriminatory time-series patterns. For an introduction on shapelets please see [Ye et al., KDD2009].
Some Text for it

The Soft-Minimum Distance Between a Shapelet and a Time Series

The distance between the k-th shapelet (S) and the j-th sliding window content of the i-th time-series (T) instance is defined as:
The distance between a shapelet and a sliding window content of a series

The minimum distance between a shapelet and a series is defined as the minimum distance between a shapelet and all the sliding window segments of a series:
The soft minimum function
The advantage of the soft-minimum is its differentiability. Based on the alpha parameter, the soft-minimum allows only the true minimum sliding window segment to contribute:
Illustration of the soft-minimum

Learning Shapelets

The minimum distances (M) can be used as predictors to approximate the time-series label (Y) using a linear model (W):
A linear model to approximate the target
A logistic regression loss can measure the quality of the prediction:
The logistic regression loss
The ultimate objective of our task is to minimize a regularized loss function accross all the instances (I) of the time-series dataset:
The objective function

Gradients for Updating the Shapelets and Weights

We can find the optimal shapelet for the objective function, by updating the shapelets in the minimum direction of the objective, hence the first gradient (details on the paper):
Gradient of the objective with respect to the shapelets

Similarly, the weights should also be jointly updated towards minimizing the objective:
Gradient of Weights

The Learning Algorithm

The gradients can be used to minimize the objective using a stochastic gradient descent learning algorithm:
Learning Algorithm
The algorithm updates the shapelets towards the minimum classification loss function. In the case of a linear loss that translates to linear separability:
Illustration of The Method

Experimental Results On UCR Time-Series Datasets

The results presented below include the AdaGrad variant of SGD that updates the learning rate at each iteration. Concretely, K := log(total_num_segments)*(num_classes-1), alpha := -30, eta := 0.1, iterations := 1000. Other parameters tuned via cross-validation from L={0.1 or 0.2}, R={2, 3}, lambda={0.01 or 0.1}. The Learning Shapelet (LS) is compared against [TSBF] and [DTW]. The results for LS represent the average accuracy over 5 runs using the shown hyper-parameters. LS has more total wins and more direct wins than the baselines. The Wilcoxon signed-rank (two tailed, level 5%) demonstrates that the classification performance of LS is superior with a statistically significance margin.

Dataset L R lW LS TSBF DTW
50words 0.2 2 0.01 0.2319 0.209 0.242
Adiac 0.2 3 0.1 0.4368 0.245 0.391
Beef 0.2 3 0.01 0.2400 0.287 0.467
CBF 0.1 2 0.01 0.0056 0.009 0.004
ChlorineConcentration 0.2 3 0.1 0.3486 0.336 0.350
CinC_ECG_torso 0.2 3 0.1 0.1670 0.262 0.070
Coffee 0.2 3 0.01 0.0000 0.004 0.179
Cricket_X 0.1 3 0.1 0.2092 0.278 0.236
Cricket_Y 0.2 3 0.1 0.2487 0.259 0.197
Cricket_Z 0.1 3 0.01 0.2005 0.263 0.180
DiatomSizeReduction 0.2 3 0.01 0.0333 0.126 0.065
ECG200 0.2 3 0.1 0.1260 0.145 0.120
ECGFiveDays 0.2 3 0.01 0.0000 0.183 0.203
FaceAll 0.1 3 0.01 0.2175 0.234 0.192
FaceFour 0.1 3 0.01 0.0478 0.051 0.114
FacesUCR 0.2 3 0.1 0.0587 0.090 0.088
Fish 0.1 3 0.1 0.0663 0.080 0.160
Gun_Point 0.2 3 0.01 0.0000 0.011 0.087
Haptics 0.2 3 0.01 0.5318 0.488 0.588
InlineSkate 0.1 3 0.1 0.5727 0.603 0.613
ItalyPowerDemand 0.2 3 0.1 0.0305 0.096 0.045
Lighting2 0.2 3 0.01 0.1770 0.257 0.131
Lighting7 0.1 3 0.01 0.1973 0.262 0.288
MALLAT 0.2 2 0.01 0.0457 0.037 0.086
MedicalImages 0.2 2 0.1 0.2705 0.269 0.253
MoteStrain 0.1 3 0.1 0.0871 0.135 0.134
OliveOil 0.1 3 0.01 0.5600 0.090 0.167
OSULeaf 0.1 3 0.01 0.1818 0.329 0.384
SonyAIBORobotSurface 0.1 3 0.1 0.1026 0.175 0.305
SonyAIBORobotSurfaceII 0.1 3 0.1 0.0816 0.196 0.141
SwedishLeaf 0.2 3 0.1 0.0870 0.075 0.157
Symbols 0.1 2 0.01 0.0356 0.034 0.062
syntheticcontrol 0.2 3 0.01 0.0073 0.008 0.017
Trace 0.1 2 0.01 0.0000 0.020 0.010
TwoLeadECG 0.2 2 0.01 0.0026 0.046 0.132
Two_Patterns 0.2 2 0.01 0.0030 0.001 0.002
uWaveGestureLibrary_X 0.2 3 0.01 0.2002 0.164 0.227
uWaveGestureLibrary_Y 0.2 3 0.01 0.2871 0.249 0.301
uWaveGestureLibrary_Z 0.2 2 0.01 0.2685 0.217 0.322
wafer 0.2 3 0.01 0.0038 0.004 0.005
WordsSynonyms 0.2 3 0.01 0.3398 0.302 0.252
yoga 0.2 3 0.01 0.1501 0.149 0.155
StarLightCurves 0.1 3 0.01 0.0335 0.022 0.095
NonInvasiveFatalECGThorax1 0.1 2 0.01 0.1308 0.138 0.185
NonInvasiveFatalECGThorax2 0.1 2 0.01 0.0886 0.130 0.129
Total Wins 22 15 8
Num. LS wins head-to-head 29 33
Num. LS losses head-to-head 16 12
Wilcoxon Signed-Rank Test (p-values) 0.03318 0.00544







Locations of Site Visitors