9
$\begingroup$

Assume the following 1 dimensional sequence:

A, B, C, Z, B, B, #, C, C, C, V, $, W, A, % ...

Letters A, B, C, .. here represent 'ordinary' events.

Symbols #, $, %, ... here represent 'special' events

The temporal spacing between all events is non-uniform (anything from seconds, to days) though the further in the past an event is the less likely it is to influence future events. Ideally I can take into account these time delays explicitly.

There are on the order of 10000 ordinary event types, and on the order of 100 special event types. The amount of ordinary events preceding a special event varies but unlikely to be more than a 100-300.

Fundamentally I'm interested in looking for patterns in the ordinary event sequence that end up being predictive for the special events.

Now you can approach this in different ways: creating feature vectors + standard classification, association rule learning, HMMs, etc.

In this case Im curious as to how an LSTM based network would fit best. Straightforward would be to do something like Karparthy's char-rnn and predict the next event given a history. Then for a new sequence

C, Z, Q, V, V, ... , V, W

You could run it through the model and see what special event is most probable to come next. But it does not quite feel the right fit.

Since this is a temporal classification problem it seems the proper thing to do though is use Connectionist Temporal Classification as described by Alex Graves.

However, before investing too much at the moment I'm looking for something easier and quicker to experiment with to get a feel of how well LSTMs would fit here. Tensorflow will see an CTC example at some point, but not yet.

So my (sub) questions are:

  1. Given the problem above and I'd like to experiment with LSTMs is it worth trying the char-rnn type approach, should I bite the bullet and get to grips with CTC, or is there a better place to start.
  2. How would you explicitly incorporate inter-event timing information. Using a fixed clock with no-op events obviously works but seems ugly.
  3. Assuming I managed to train an LSTM is there a way to inspect the model to see what kind of event 'motifs' it has picked up? (ie, analogous to the filters in convnets)

Any sample code (python preferred) always helpful.

Edit: Just to add that there is some noise in the sequence. Some events can be safely ignored but exactly which ones are not always possible to say up front. So ideally the model (and the motifs derived from it) is robust against this.

$\endgroup$
  • $\begingroup$ What kind of data set is this? $\endgroup$ – pir Dec 17 '15 at 10:49
  • $\begingroup$ @felbo: I cant say explicitly unfortunately but its data from hardware, not financial / sales / ads / .. $\endgroup$ – dgorissen Dec 17 '15 at 15:05
  • $\begingroup$ Ok. Actually, one-hot encoding (in my answer) might be problematic if you have ~10k event types. You could perhaps do something along the lines of word2vec so you only have ~300 input dimensions. Similarly, it's likely problematic to predict the next event type out of 10k options. Instead, it would make sense to reframe problem to just predict the 100 special types and then a 'normal event' class for all the 10k normal events. $\endgroup$ – pir Dec 17 '15 at 15:12
  • $\begingroup$ Just to be clear: I assume you have tons of data for this kind of problem. $\endgroup$ – pir Dec 17 '15 at 15:18
  • $\begingroup$ @felbo: indeed. Had been thinking of just using an index, learning a vector embedding like word2vec, or group the events into classes to reduce the dimensionality. Similar on the prediction side, agreed. $\endgroup$ – dgorissen Dec 17 '15 at 15:21
2
$\begingroup$

Your data seems to be just sequences of tokens. Try build a LSTM autoencoder and let the encoder learns some fixed representations of the first part of your sequence and the decoder to predict the remaining.

These representations would be your motifs.

Ref:

Bahdanau, D., Cho, K., & Bengio, Y. (2014). Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473.

Srivastava, N., Mansimov, E., & Salakhutdinov, R. (2015). Unsupervised learning of video representations using LSTMs. arXiv preprint arXiv:1502.04681.

$\endgroup$
0
$\begingroup$

The most important part is how you "phrase" the classification problem, meaning how you represent the input and what you want to output. Seeing as you have so many different event types you need to learn an embedding of these. This can be done directly in e.g. Keras. You can see this example on how to learn an embedding directly from data. Another approach would be to learn an embedding beforehand using a unsupervised approach such as word2vec. However, this requires more work on your part as you need to come up with a relevant task and train that to generate the embedding. Given that you have enough data it is easier (although slightly less effective) to learn the embedding directly. For the output I would not predict all the different types of events, but only the special events and a "background class" to keep the problem feasible. If you really want to be able to predict every single class then you need to use some tricks (look into how word2vec does it).

Regarding the time between events. You could simply add that to your LSTM as an additional dimension (see e.g. this for an example of how to do that in Keras). This would be easy to do and would allow the LSTM to take the temporal difference into account.

I do not know of any way to visualize the motifs by "unrolling" the temporal nature of the network. You might be able to generate some motifs using a generative network, but it would likely be difficult to interpret. One way to explore motifs could be to simply find the top 100000 most common sequences of non-special events of e.g. length 20-100, input them into the trained model and extract the probability output from the final softmax layer. In this way you could find sequences that are connected to certain special events. However, it's difficult to say whether this motif approach is feasible/useful without looking at your data.

$\endgroup$
  • $\begingroup$ Just to be clear. On the motif side, you mean looking at the raw data and extracting most common subsequences of a particular minimum length (or use frequent item set mining to generate them) and then see where special event predictions are maximal? In that case it seems easier to approach it as a standard classification problem no? $\endgroup$ – dgorissen Dec 17 '15 at 15:36
  • $\begingroup$ I was hoping the time-dependent nature of a recurrent model would allow for some kind of useful inspection. Alternatively perhaps the thing to do would be to run the model in 'reverse'. Maximise the prediction confidence of each special event type and see what kind of sequences that results in. However, not quite sure how that would work and perhaps needs a generative model. $\endgroup$ – dgorissen Dec 17 '15 at 15:36
  • $\begingroup$ Please see my updated answer. Yes, I mean seeing where "special event predictions are maximal" based on the raw data. I don't understand what you mean about approaching it as a standard classification problem :) $\endgroup$ – pir Dec 25 '15 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.