How to pass the sequential var. length data for the NN?

Question

The main task is from Inductive Logic Programming (ILP) area. The task related to ANN is inspired by paper below but is applied to more complex case.Learning an approximation to clause evaluation function

The main task is the search of the best theory (hypothesis) that subsumes bottom theory (most specific hypothesis), that covers as many positive examples as possible, and covers as few negative examples as possible and has minimal description length.

The input data consist from the several records. The records represent the set of clauses (theory/hypothesis). Every record represents the single clause which is the set of literals (possible empty). The clause is encoded via bit vector where every bit indicates if the literal is dropped or active. Bottom clause's bit vector is filled with 1's. A record contain numeric vector is #'s of occurrences of a literal in the clause. The vector is associated with bit vector. A record's length (i.e. bit vector and numeric vector length) may vary. Every record contain also the fixed number of numeric values whose representation is trivial.

The output is 2 numbers. Their values (both in the range [0.0, 1.0]) are coverages for positive and negative examples.

So, my question is: How to represent/normalize these records for the NN? In particular, is there a (tricky) way to represent the bit vector compactly? Its length can be up to a few thousands.

Also, I'd like to mention about learning mode(s). The NN may learn fitness function approximation in 'online' mode from real data, i.e. in parallel with main searching. In this mode all the training samples have the same clauses length schema.

It may learn in 'offline' mode from abstract (generated) datasets, and, finally, in both modes. It's unclear for me is it necessary to consider 2nd and 3rd cases (I think they are significantly complicated input data format to the NN).

Answer 1

Ok, I'm not an expert in Inductive Logic Programming, so my undestanding can be a bit limited. I have read referenced paper and your clarifications (very helpful ones). Your problem don't have a readily avaliable solution that is guaranteed to work, so I can only give some directions to look.

In my understanding your first problem is working with training samples, that contain different numbers of clauses. This can be dealt by two approaches. First, assuming you are working with small (maybe 1-4) number of clauses you can try fixed length representation with all nonexistent clauses padded with zeroes. This is the simplest thing possible and have some chances to work.

If you want to work with large number of clauses or simple approach won't work, it might be worth to try convolutional neural network (CNN) approach. As I understand, exact order of clauses is irrelevant and CNN provides exactly that kind of positional invariance while also reducing number of parameters to be learned (unless you want to generate clauses that are composed from other clauses rather than from literals, in which case things will become quite more complex).

As for bit vectors, note that in most cases compact representations are more difficult for NN to deal with and "bag of features" representations are best option in many cases. This is because you first concern should be to keep things understandable for NN.

Regarding perfomance, vectors with length of 10000 (and more) are quite common and should not be major problem for properly optimized implementation (and since you probably will mostly be dealing with sparse vectors and good implementation knows how to multiply them efficiently). So you should probably try things as they are and see what happens, starting with the simplest setup possible. If you run into some difficult problems, come back here and describe them. Machine learning in general is very much an expiremental field where you learn by doing and it is generally considered good practice not to solve difficulities until they manifest themselves in practical settings.

In other problem domains, such as language processing, one can usually learn compact represenation of such "bag of features" vectors by pre-training autoencoders or similar techinques, however, in you settings, every literal only have meaning in the context of specific problem. If NN goes through many examples in training phase, it still might be beneficial to put low-dimensional "embedding" layer on top of bit vector (or maybe on top of concatenation of bit vector and numeric vector).

I very much doubt that 'offline' mode with learning from abstract (generated) datasets will lead to generalizations that benefit specific problems. I feel that most perfomance gain that was obtained by authors of that paper is due to NN learning problem-specific regularities rather then understanding anything about Logic Programming in general. But this is separate interesting (and very difficult) research problem itself. However, expirements with generated datasets can be very helpful in finding best NN topology.

You might also find useful to read recent papers on application of NNs, in particular CNNs, autoencoders and recursive tree-based autoencoders to image processing and (especially) natural language processing tasks, because you can learn some useful ideas that could be transferable to your domain.