Ideas on how to make a neural net learn how to split sequence into sub sequences

How can I train a neural network to recognize sub-sequences in a sequence flow?

For example: Given the sequence 111100002222 as an input sample from a stream, the neural network would recognize that 1111 , 0000 , 2222 are sub sequences (so 111100 would not be a valid subsequence) and so on for ~ 50 to 100 different subsequences.

There is no particular order in which the subsequence would appear in the flow. No network architecture restriction. Subsequences are of variable length.

General concepts, ideas, and theory are welcome.

• I dunno but this seems like a simple algorithmic problem...Teaching this to a MN might be tougher and more time consuming – DuttaA Mar 30 '18 at 15:05
• It is indeed an algorithm problem. However, the 'learning' process of knowing which subsequence goes well together is , in my opinion, a problem where NN are particulary useful. – Charles-Ugo Brouillard Mar 30 '18 at 16:22
• Is this sequence like a class label for some other related sequence that you are trying to model? If that's the case, add some detail to you example and maybe we can help you. If not, you could easily implement what you ask using regex in your language of choice. – Sledge Mar 31 '18 at 0:37
• Yes it is ! We could replace the example above with , let’s say , sentences without spaces. ex : If i feed into the neural netwok : ‘ILikePizza’ , a correctly trained neural network would be able to ouput or classify ‘I like pizza’ , recognizing those 3 different words (sub sentences) in the character flow. Whether it’s classification or even a regression of some sort would be valid. – Charles-Ugo Brouillard Apr 2 '18 at 0:12
• You example in the question is rather useless: Splitting on character change does the job. You can learn it, but there's no reason to. Your second example is better, but ILikePizza is equally trivial, just split before each an uppercase character. Still nothing useful to learn. Should it handle ilikepizza as well? Provide a few more inputs. provide something to learn from. +++ Can you split strcprstskrzkrk (I can; it's an actual sentence)? In case you can't, would you expect the network to be able to? What other input should it get? – maaartinus Apr 3 '18 at 17:08

The problem in the original question is akin to that of inducing a context-sensitive grammar (CSL), except that it is harder because a CSL is assumed to be composed of fixed-length subsequences. It is probably closer to the problem of inducing a Reber grammar, but that in turn seems like an overkill.

LSTMs are known to be able to learn both CSL and Reber grammars. However, I doubt that this is what you really need because of the following comment:

[...] given an entire book where there is NO spaces anywhere, only characters (including special characters, like commas), in what way can we make the network learn the 'word boudaries' of this book.

This is called morphology induction, and it is a much harder problem than that of simple Reber grammar induction. Note that finding word boundaries is a special case of the problem of finding morpheme boundaries. There have been many attempts to solve this (also see this survey paper for more details and references).

Most approaches developed seem to rely on statistical principles (like MDL) and do not use neural networks (a counterexample using LSTMs). My intuition is that the extreme morphological variability across languages (ranging from Finno-Ugric languages with highly inflectional morphology to Sino-Tibetan languages with hardly any morphology at all) makes it hard to train neural networks in a language-agnostic way. However, you might have better luck if you focus on a single language.

Hope that helps.

I guess, supervised learning should work rather well: You'd feed the network with a fixed substring and it'd determine if the middle character is the first letter of a word, or a last one, or neither or both.

So 2*n+1 inputs (fed e.g., with the string "ingsits") should output a 1 on the output determining if the middle letter (here: "s") is the first one of a word and a 0 on the output determining if it's the last one (taken from "Thekingsitsthere"). Each input character should probably be 1 hot encoded.

You'd probably want to use more context characters than in my example. OTOH you can use a simple MLP with no temporal complications. It'll never get perfect as it's impossible, but it get pretty close.

Concerning unsupervised learning I'm skeptical...

(NOTE: I think it will be easier to do it without ANNs...)

But if you insist:

1. convert the sequence into a fixed-size vectors.
2. push trough a 2-5 1D-convolution layer with 1 neuron dense layer at the end (sigmoid activation) and another K-points detector for getting the sequence breakage points
3. create a training set - to find the break-points (12, 23, 34 ...) in the sequence.
4. train a detector with SGD to find these break-points. - loss functions: cross_entropy.

Then, it should learn to find the breakage points, and based on this you can easily split the sequence.

• Mmmm...never thought of using CNN for that kind of things, although, it kinda makes sense. I'm wondering, however, if a K-points detector could overcome the variable length problem ('scholar' / 'scholarship' / 'scholar' & 'ship' ). Maybe using a standard classifier outputting probability of the key points found by the CNN ? – Charles-Ugo Brouillard Apr 10 '18 at 16:54
• you can pad the sequences, so it will have fixed sizes. Moreover, conv. layers usually can deal with variable size vectors, as long as it is all-convolutional network (no dense layers). – Dror Hilman Apr 17 '18 at 3:35

Another approach could be to predict the class of a sequence and not the break point. Assuming that each sequence is part of a class, you can use a LSTM. Inputing the multiple sequences (111100002222 ) and let predict the class for each sequence (c1,c1,c1,c1,c0,c0,c0,c0,c2,c2,c2,c2)

• That would be a good idea, but what about variable length repetitive sub-sequences ? If i follow the 'word' example , how would the network be able to learn between 'scholar' / 'scholarship' / 'scholar' & 'ship' ? – Charles-Ugo Brouillard Apr 10 '18 at 16:44
• Therefore, you have to annotate your data that scholar is 1111111 and scholarship is 11111112222. Is this your real use case or just an example? Then I can come up with a better idea ... – user3352632 Apr 11 '18 at 8:40

1 - Learn all the basic building blocks of possible sub-sequence
In our words sequence example, that would correspond to phonemes.
(I'm guessing that this step can even be done using unsupervised learning.)
So in the following example : Hello Laurie, we would have learned 3 phonemes : HE, LO, RI.

2- Learn all subsequence as sequences of 'building blocks'
Using a ClockWorkRNN with timesteps of interval +1 with, let's say, 10-15 timestep (groups), that is fed the next 'phoneme id' in the sequence, we would have a space large enough to record most words (Obviously, the number of timesteps should be size of the biggest word).
This is the subsequences memory RNN.
Its sole purpose is to remember subsequences.

Now, i'm really brainstorming here , taking a very wild guess, but what if :
After training this RNN to a satisfying error rate, we check if the output of the RNN is very different to the next input for a couple of timesteps.
In other word, we see if the neural network has been able to 'guess' the next building block of the subsequence.
If not, then its a point of interest , because there is not a lot of possibilities as of why this would happend : the only one I see is

1 - The RNN is currently receiving another word, thus making this timestep a sub-sequence 'break point'

Do you guys see any points that could prove this theory wrong ?