Dynamic time warping in Theano

gistfile1.py

'''
Dynamic time warping implementation in Theano

See also
https://github.com/astanway/theano-dtw
https://github.com/danielrenshaw/TheanoBatchDTW
'''

import theano
import theano.tensor as T
import numpy as np

# Reference implementation in pure Python
def dtw(D):
    for i in xrange(D.shape[0] - 1):
        for j in xrange(D.shape[1] - 1):
            D[i + 1, j + 1] += min([D[i, j], D[i, j + 1], D[i + 1, j]])

# In Theano (~100x slower!)
def dtw_theano(D):  
    def local_cost(j, D, i):
        D = T.set_subtensor(
            D[i + 1, j + 1],
            D[i + 1, j + 1] + T.min([D[i, j], D[i, j + 1], D[i + 1, j]]))

        return D

    def outer_loop(i, D, j_vals):
        D_local, _ = theano.scan(fn=local_cost,
                                 sequences=j_vals,
                                 outputs_info=[D],
                                 non_sequences=[i])
        return D_local[-1]

    D_dtw, _ = theano.scan(fn=outer_loop,
                           sequences=T.arange(D.shape[0] - 1),
                           outputs_info=[D],
                           non_sequences=[T.arange(D.shape[1] - 1)])

    return D_dtw[-1]