3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ I dunno but this seems like a simple algorithmic problem...Teaching this to a MN might be tougher and more time consuming $\endgroup$
    – user9947
    Commented Mar 30, 2018 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – Charles-Ugo Brouillard
    Commented Mar 30, 2018 at 16:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sledge
    Commented Mar 31, 2018 at 0:37
  • $\begingroup$ 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. $\endgroup$
    – Charles-Ugo Brouillard
    Commented Apr 2, 2018 at 0:12
  • 1
    $\begingroup$ 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? $\endgroup$
    – maaartinus
    Commented Apr 3, 2018 at 17:08

5 Answers 5

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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...

Improve this answer
$\endgroup$
0
$\begingroup$

(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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Charles-Ugo Brouillard
    Commented Apr 10, 2018 at 16:54
  • $\begingroup$ 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). $\endgroup$
    – Dror Hilman
    Commented Apr 17, 2018 at 3:35
0
$\begingroup$

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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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' ? $\endgroup$
    – Charles-Ugo Brouillard
    Commented Apr 10, 2018 at 16:44
  • $\begingroup$ 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 ... $\endgroup$
    – user3352632
    Commented Apr 11, 2018 at 8:40
0
$\begingroup$

How about this ?

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 ?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .