Overlapping iteration over theano tensor

Question

I am trying to implement a scan loop in theano, which given a tensor will use a "moving slice" of the input. It doesn't have to actually be a moving slice, it can be a preprocessed tensor to another tensor that represents the moving slice.

Essentially:

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
 |-------|                                 (first  iteration)
   |-------|                               (second iteration)
     |-------|                             (third  iteration)
               ...
                    ...
                        ...
                               |-------|   (last   iteration)

where |-------| is the input for each iteration.

I am trying to figure out the most efficient way to do it, maybe using some form of referencing or manipulating strides, but I haven't managed to get something to work even for pure numpy.

One possible solution I found can be found here, but I can't figure out how to use strides and I don't see a way to use that with theano.

Answer 1

You can build a vector containing the starting index for the slice at each timestep and call Scan with that vector as a sequence and your original vector as a non-sequence. Then, inside Scan, you can obtain the slice you want at every iteration.

I included an example in which I also made the size of the slices a symbolic input, in case you want to change it from one call of your Theano function to the next:

import theano
import theano.tensor as T

# Input variables
x = T.vector("x")
slice_size = T.iscalar("slice_size")


def step(idx, vect, length):

    # From the idx of the start of the slice, the vector and the length of
    # the slice, obtain the desired slice.
    my_slice = vect[idx:idx + length]

    # Do something with the slice here. I don't know what you want to do
    # to I'll just return the slice itself.
    output = my_slice

    return output

# Make a vector containing the start idx of every slice
slice_start_indices = T.arange(x.shape[0] - slice_size + 1)

out, updates = theano.scan(fn=step,
                        sequences=[slice_start_indices],
                        non_sequences=[x, slice_size])

fct = theano.function([x, slice_size], out)

Running the function with your parameters produces the output :

print fct(range(17), 5)

[[  0.   1.   2.   3.   4.]
 [  1.   2.   3.   4.   5.]
 [  2.   3.   4.   5.   6.]
 [  3.   4.   5.   6.   7.]
 [  4.   5.   6.   7.   8.]
 [  5.   6.   7.   8.   9.]
 [  6.   7.   8.   9.  10.]
 [  7.   8.   9.  10.  11.]
 [  8.   9.  10.  11.  12.]
 [  9.  10.  11.  12.  13.]
 [ 10.  11.  12.  13.  14.]
 [ 11.  12.  13.  14.  15.]
 [ 12.  13.  14.  15.  16.]]

Answer 2

You could use this rolling_window recipe:

import numpy as np

def rolling_window_lastaxis(arr, winshape):
    """
    Directly taken from Erik Rigtorp's post to numpy-discussion.
    http://www.mail-archive.com/numpy-discussion@scipy.org/msg29450.html
    (Erik Rigtorp, 2010-12-31)

    See also:
    http://mentat.za.net/numpy/numpy_advanced_slides/ (Stéfan van der Walt, 2008-08)
    https://stackoverflow.com/a/21059308/190597 (Warren Weckesser, 2011-01-11)
    https://stackoverflow.com/a/4924433/190597 (Joe Kington, 2011-02-07)
    https://stackoverflow.com/a/4947453/190597 (Joe Kington, 2011-02-09)
    """
    if winshape < 1:
        raise ValueError("winshape must be at least 1.")
    if winshape > arr.shape[-1]:
        print(winshape, arr.shape)
        raise ValueError("winshape is too long.")
    shape = arr.shape[:-1] + (arr.shape[-1] - winshape + 1, winshape)
    strides = arr.strides + (arr.strides[-1], )
    return np.lib.stride_tricks.as_strided(arr, shape=shape, strides=strides)

x = np.arange(17)
print(rolling_window_lastaxis(x, 5))

which prints

[[ 0  1  2  3  4]
 [ 1  2  3  4  5]
 [ 2  3  4  5  6]
 [ 3  4  5  6  7]
 [ 4  5  6  7  8]
 [ 5  6  7  8  9]
 [ 6  7  8  9 10]
 [ 7  8  9 10 11]
 [ 8  9 10 11 12]
 [ 9 10 11 12 13]
 [10 11 12 13 14]
 [11 12 13 14 15]
 [12 13 14 15 16]]

Note that there are even fancier extensions of this, such as Joe Kington's rolling_window which can roll over multi-dimensional windows, and Sebastian Berg's implementation which, in addition, can jump by steps.