search

tslearn-team / tslearn

The machine learning toolkit for time series analysis in Python
https://tslearn.readthedocs.io
BSD 2-Clause "Simplified" License
2.88k stars 336 forks source link

Implement (Stochastic) Subgradient Mean #44

Closed unnamedplay-r closed 4 years ago

unnamedplay-r commented 6 years ago

Summary: Stochastically explore the DTW Averaging Space. It's a useful algorithm for exploring online settings and larger sample sizes. The paper is a bit of work to get through as they rigerously detail a connection between the DTW sample mean to nonsmooth optimization methods for their proposed algorithm. They also detail a non-stochastic subgradient method and present a vectorized version of DBA that might provide additional performance benefits (I'll create a seperate issue for refactoring DBA to that).

I think this package would benefit greatly for both the Subgradient (SG) and Stochastic Subgradient (SSG) methods.

Original Paper: Nonsmooth Analysis and Subgradient Methods for Averaging in Dynamic Time Warping Spaces

Relevant sections are 4.1. The Subgradient Mean Algorithm and 4.3. The Stochastic Subgradient Mean Algorithm and their respective algorithms 1 and 3.

rtavenar commented 4 years ago

It is now merged to dev, and will be included in tslearn from version 0.3. Thanks @unnamedplay-r for the ref!