Answers.Body: <p>The problem in the original question is akin to that of inducing a <a href="https://en.wikipedia.org/wiki/Context-sensitive_grammar" rel="nofollow noreferrer">context-sensitive grammar</a> (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 <a href="https://github.com/DylanAuty/rebergen" rel="nofollow noreferrer">Reber grammar</a>, but that in turn seems like an overkill.</p>
  
  <p>LSTMs are known to be able to learn both <a href="ftp://ftp.idsia.ch/pub/juergen/L-IEEE.pdf" rel="nofollow noreferrer">CSL</a> and <a href="http://www.bioinf.jku.at/publications/older/2604.pdf" rel="nofollow noreferrer">Reber</a> grammars. However, I doubt that this is what you really need because of the following comment:</p>
  
  <blockquote>
    <p>[...] 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.</p>
  </blockquote>
  
  <p>This is called morphology induction, and it is a <em>much</em> harder problem than that of simple Reber grammar induction. Note that finding <em>word</em> boundaries is a special case of the problem of finding <em>morpheme</em> boundaries. <a href="https://link.springer.com/chapter/10.1007/978-94-017-6059-1_2" rel="nofollow noreferrer">There</a> <a href="https://gupea.ub.gu.se/bitstream/2077/21418/1/gupea_2077_21418_1.pdf" rel="nofollow noreferrer">have</a> <a href="http://www.aclweb.org/anthology/W02-0603" rel="nofollow noreferrer">been</a> <a href="http://people.cs.uchicago.edu/~jagoldsm/Papers/algorithm.pdf" rel="nofollow noreferrer">many</a> <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.9794&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">attempts</a> <a href="http://www.aclweb.org/anthology/P00-1027" rel="nofollow noreferrer">to solve</a> <a href="http://www.aclweb.org/anthology/N01-1024" rel="nofollow noreferrer">this</a> (also see <a href="https://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00050" rel="nofollow noreferrer">this</a> survey paper for more details and references). </p>
  
  <p>Most approaches developed seem to rely on statistical principles (like <a href="https://en.wikipedia.org/wiki/Minimum_description_length" rel="nofollow noreferrer">MDL</a>) and <em>do not</em> use neural networks (a <a href="http://grammar.ucsd.edu/sdlp/current/Malouf_2016_Generating_morphological_paradigms.pdf" rel="nofollow noreferrer">counterexample</a> 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.</p>
  
  <p>Hope that helps.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-10T13:38:29.800Z
Answers.LastActivityDate: 2018-07-10T13:38:29.800Z
Answers.UserDisplayName: cantordust
Answers.Body: <p>(NOTE: I think it will be easier to do it without ANNs...)</p>
  
  <p>But if you insist:</p>
  
  <ol>
  <li>convert the sequence into a fixed-size vectors.</li>
  <li>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</li>
  <li>create a training set - to find the break-points (12, 23, 34 ...) in the sequence.</li>
  <li>train a detector with SGD to find these break-points. - loss functions: cross_entropy. </li>
  </ol>
  
  <p>Then, it should learn to find the breakage points, and based on this you can easily split the sequence.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T16:54:41.987Z
Answers.Text: 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 ?
Answers.UserDisplayName: Charles-Ugo Brouillard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-17T03:35:39.717Z
Answers.Text: 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).
Answers.UserDisplayName: Dror Hilman
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T03:24:08.583Z
Answers.LastActivityDate: 2018-04-10T03:24:08.583Z
Answers.UserDisplayName: Dror Hilman
Answers.Body: <p>How about this ?<br/><br/>
  <strong>1 - Learn all the basic building blocks of possible sub-sequence</strong><br/>
  In our words sequence example, that would correspond to <a href="https://en.wikipedia.org/wiki/Phoneme" rel="nofollow noreferrer">phonemes</a>.<br/>
  (<em>I'm guessing that this step can even be done using unsupervised learning.)</em><br/>
  So in the following example :
  <strong>Hello Laurie</strong>, we would have learned 3 phonemes : <strong>HE</strong>, <strong>LO</strong>, <strong>RI</strong>.<br/></p>
  
  <p><strong>2- Learn all subsequence as sequences of 'building blocks'</strong><br/>
  Using a <a href="https://arxiv.org/abs/1402.3511" rel="nofollow noreferrer">ClockWorkRNN</a> with timesteps of interval +1 with, let's say, 10-15 timestep (groups), that is fed the next '<em>phoneme id</em>' in the sequence, we would have a space large enough to record most <em>words</em> (Obviously, the number of timesteps should be size of the biggest word).<br/>
  This is the subsequences memory RNN.<br>
  Its sole purpose is to remember subsequences.<br/></p>
  
  <p>Now, i'm really brainstorming here , taking a very wild guess, but what if : <br/>
  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.<br/>
  In other word, we see if the neural network has been able to '<em>guess</em>' the next building block of the subsequence.<br/>
  If not, then its a <strong>point of interest</strong> , because there is not a lot of possibilities as of why this would happend : the only one I see is <br/></p>
  
  <p>1 - The RNN is currently receiving another word, thus making this timestep a sub-sequence '<em>break point</em>'</p>
  
  <p>Do you guys see any points that could prove this theory wrong ?</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T20:32:47.903Z
Answers.LastActivityDate: 2018-04-10T20:32:47.903Z
Answers.UserDisplayName: Charles-Ugo Brouillard
Answers.Body: <p>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.</p>
  
  <p>So <code>2*n+1</code> 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.</p>
  
  <p>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.</p>
  
  <p>Concerning unsupervised learning I'm skeptical...</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T02:54:48.923Z
Answers.LastActivityDate: 2018-04-10T02:54:48.923Z
Answers.UserDisplayName: maaartinus
Answers.Body: <p>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)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T16:44:02.047Z
Answers.Text: 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' ?
Answers.UserDisplayName: Charles-Ugo Brouillard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-11T08:40:13.963Z
Answers.Text: 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 ...
Answers.UserDisplayName: user3352632
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-10T07:22:28.453Z
Answers.LastActivityDate: 2018-04-10T07:22:28.453Z
Answers.UserDisplayName: user3352632
Body: <p>How can I train a neural network to recognize sub-sequences in a sequence flow?</p>
  
  <p>For example: Given the sequence <strong>111100002222</strong> as an input sample from a stream, the neural network would recognize that <strong>1111</strong> , <strong>0000</strong> , <strong>2222</strong> are sub sequences (so <strong>111100</strong> would not be a valid subsequence) and so on for ~ 50 to 100 different subsequences.</p>
  
  <p>There is no particular order in which the subsequence would appear in the flow.
  No network architecture restriction.
  Subsequences are of variable length.</p>
  
  <p>General concepts, ideas, and theory are welcome. </p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-30T16:22:08.793Z
Comments.Text: 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.
Comments.UserDisplayName: Charles-Ugo Brouillard
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-31T00:37:17.703Z
Comments.Text: 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.
Comments.UserDisplayName: Sledge
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-02T00:12:39.213Z
Comments.Text: 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.
Comments.UserDisplayName: Charles-Ugo Brouillard
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-03T17:08:54.660Z
Comments.Text: 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?
Comments.UserDisplayName: maaartinus
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-03T20:52:19.840Z
Comments.Text: Let's take a global approach to be able to understand the examples better : 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 .   
    Ex :  **Offmythrone,jester.Thekingsitsthere.** = **Off my throne, jester. The king sits there.**   The whole purpose of this network would be to learn **boundaries** between concatenated inputs, in other words, when to seperate between a constant input flow, no matter what is the input context.
Comments.UserDisplayName: Charles-Ugo Brouillard
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-03T20:58:37.213Z
Comments.Text: Other short examples :   ` **Walktall...myfriends | 
  WhatcanIsay?Youguys...arethebest.  |
  I'vecomeupwithanewricepee  |
  KingsofLucis,cometome!  |
  MAGITEKENGINE!IT'SCLOSE!** `
Comments.UserDisplayName: Charles-Ugo Brouillard
Tags: <neural-networks><algorithm>
Title: Ideas on how to make a neural net learn how to split sequence into sub sequences
UserDisplayName: Charles-Ugo Brouillard
ThreadText: # Ideas on how to make a neural net learn how to split sequence into sub sequences
  
  (Asked by: username_0 on 2018-03-30)
  
  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.
  
  **Tags:** neural-networks, algorithm
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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.  
  > **username_0**: 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.  
  > **username_2**: 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?  
  > **username_0**: Let's take a global approach to be able to understand the examples better : 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 .      Ex :  **Offmythrone,jester.Thekingsitsthere.** = **Off my throne, jester. The king sits there.**   The whole purpose of this network would be to learn **boundaries** between concatenated inputs, in other words, when to seperate between a constant input flow, no matter what is the input context.  
  > **username_0**: Other short examples :   ` **Walktall...myfriends |  WhatcanIsay?Youguys...arethebest.  | I'vecomeupwithanewricepee  | KingsofLucis,cometome!  | MAGITEKENGINE!IT'SCLOSE!** `  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_3 on 2018-07-10. Score: 2 | Accepted answer
  
  The problem in the original question is akin to that of inducing a [context-sensitive grammar](https://en.wikipedia.org/wiki/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](https://github.com/DylanAuty/rebergen), but that in turn seems like an overkill.
  
  LSTMs are known to be able to learn both [CSL](ftp://ftp.idsia.ch/pub/juergen/L-IEEE.pdf) and [Reber](http://www.bioinf.jku.at/publications/older/2604.pdf) 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](https://link.springer.com/chapter/10.1007/978-94-017-6059-1_2) [have](https://gupea.ub.gu.se/bitstream/2077/21418/1/gupea_2077_21418_1.pdf) [been](http://www.aclweb.org/anthology/W02-0603) [many](http://people.cs.uchicago.edu/~jagoldsm/Papers/algorithm.pdf) [attempts](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.9794&rep=rep1&type=pdf) [to solve](http://www.aclweb.org/anthology/P00-1027) [this](http://www.aclweb.org/anthology/N01-1024) (also see [this](https://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00050) survey paper for more details and references).
  
  Most approaches developed seem to rely on statistical principles (like [MDL](https://en.wikipedia.org/wiki/Minimum_description_length)) and *do not* use neural networks (a [counterexample](http://grammar.ucsd.edu/sdlp/current/Malouf_2016_Generating_morphological_paradigms.pdf) 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.
  
  
  ---
  
  ### Answer by username_4 on 2018-04-10. Score: 0
  
  (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.
  
  > **Comments:**
  > **username_0**: 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 ?  
  > **username_4**: 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).  
  
  ---
  
  ### Answer by username_0 on 2018-04-10. Score: 0
  
  How about this ?  
    
  **1 - Learn all the basic building blocks of possible sub-sequence**  
  In our words sequence example, that would correspond to [phonemes](https://en.wikipedia.org/wiki/Phoneme).  
  (*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](https://arxiv.org/abs/1402.3511) 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 ?
  
  
  ---
  
  ### Answer by username_2 on 2018-04-10. Score: 0
  
  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...
  
  
  ---
  
  ### Answer by username_5 on 2018-04-10. Score: 0
  
  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)
  
  > **Comments:**
  > **username_0**: 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' ?  
  > **username_5**: 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 ...  
  
  ---
  
  