# Using RNNs to segment long streams

I'm using an LSTM to segment a long streams of linear data into contiguous parts. My specific application is extracting key signature changes from a stream of notes. Specifically, I want to (for each piece) feed note by note into the LSTM and have it output a vector that can be softmaxed to identify the current key signature of the piece at that moment, continuously. That is, since the key signature can change throughout the piece, I want the output of the network to remain correct across the whole piece, not just at the end. Analogous problems could be given the words from a book as input, determine where chapters begin and end or given the frames of a movie determine the time ranges of the elements of the story (exposition, rising action, climax, falling action, resolution, etc.).

The key takeaway here is that the segmentation is highly context sensitive. Additionally, there may be more changes than the LSTM can remember (or maybe, relying on it to remember this feels very fragile). So, I don't see it reasonable to construct an encoder-decoder type scheme where at the end a decoder outputs a range (offsets into the input stream) for each key signature identified in the piece.

One challenge that arises from this is that training requires inputting full pieces with lots of samples (since the task is context sensitive) and computing loss over a similarly sized output. Crucially, while the input may be sparse the output will be dense (although very repetitive) so you'll definitely pay a large memory price to do the backpropagation. I'm concerned that this memory pressure may place significant restrictions on batch sizes.

I've considered several approaches to make training outputs more reasonable:

1. Don't input full scores. Pick pieces of scores that begin in one key and change to another and use these pairs as inputs. Then train the LSTM to correctly identify the first key change in a stream.

This seems reasonable at first, but fails to really address the problem. For one, this doesn't definitely solve the input length issue (there can be long scores in a single key). It also doesn't solve the output repetitiveness issue, because it still requires one output vector per timestep. It also loses high level (whole score) context, as it would require (for prediction) you to feed in notes into the LSTM until it signals a key change. Then, restart the LSTM at that point to find the next key change. I could see scenarios where this might miss short changes that happen when modulating between two keys (ex. as a graph A -> B -> C where B is short; feeding in just B -> C might not contain enough information for it to recognize B, but with the context of A and knowing that it eventually reaches C, it can infer a small section of B between them). This also precludes other global knowledge (for example, many songs modulate up at the end to make it more dramatic).

1. Don't input full scores AND modify the output strategy to not be sequence based

Similar to above, except instead of computing loss over every output for each timestep, take only the last output. That output now is a starting key signature, timestep offset, and ending key signature where the offset is an index into the timesteps input into the LSTM indicating at what point the key switched from "starting key signature" to "ending key signature." I really dislike this approach because although it solves the output size problem, having a network output an index feels wrong. This output doesn't constrain that index to one in [0, num_timesteps); it could output anything (and may do so when presented with new input).

This approach also suffers from the same global state issue as above.

1. Batch the (outputs of the) batches

Change nothing about the inputs or outputs. Instead, batch each batch into x timesteps with x outputs (where x is a reasonable size that balances batch size without output matrix width/size). Then persist LSTM state when training. Train each batch in chunks computing loss after each chunk. Once you're complete with a batch reset the LSTM state and start the next batch.

Explained more concretely: You have batches with 100 scores each with 1000 timesteps (1000 inputs and 1000 expected outputs). For each of these batches, split the timesteps and expected outputs into sequential chunks of pairs of 250 inputs and 250 outputs. Input each of these chunks into the network, and compute loss on the output. Do not clear the state of the LSTM after each chunk. Only reset the state of the LSTM after you finish a batch (all 4 chunks, in this case).

There is one fatal flaw of this approach. It does not support bidirectional RNNs, which is rather unfortunate.

The third solution feels like the best of the three, because it doesn't suffer from the issues of 1 & 2 (namely output constraints and lack of global state). But, it doesn't seem to support bidirectional LSTMs, which seems like a huge drawback. It also feels like a workaround for the fact that the output is repetitive in can be impractically large. Additionally, it feels like is possible to have very jagged output (key change every note), because the softmax doesn't explicitly know about the softmax output of the previous or next timestep. Maybe some smoothing could help here? Maybe this claim is unfounded?

Is there a better solution than #3 for segmenting long streams? Is there an RNN approach that doesn't have output size proportional to input size but can still handle arbitrary number of segments?