5 ms·
Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them.
by jmmcd 13y ago
Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them.
Since you say it's obsolete, do you have any links to papers or software related to successors of the Sequitur algorithm?
- ot 13y agoIt depends on what you want to do. RePair [1] is currently the best grammar-based compressor, but it doesn't give good theoretical guarantees. In theory, instead, there is an O(log n) approximation to the smallest grammar problem [2], but AFAIK doesn't work very well in practice. In the same paper there is a good introduction to the problem and an analysis of the previous algorithms, including Sequitur. [1] http://www.larsson.dogma.net/dcc99.pdf http://www.larsson.dogma.net/dcc99.pdf [2] http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf
- jmmcd 13y agoThanks. I think RePair can be regarded as grammar-based (though they don't say so), but I don't think it produces a grammar which would be useful in any context other than reproducing the original sentence. What I would really love (and maybe I'll just have to write it myself?) is a practical algorithm (not too worried about worst-case guarantees etc) which produces a semi-readable grammar from multiple example sentences, and can then be turned around to generate lots of new sentences.
- ot 13y agoThe concept of grammar compression basically didn't exist at the time RePair was published, but it is by all means a grammar compressor (same goes for LZ78). If you are interested in learning what a grammar should look like (which is very different from optimizing the number of rules) you may want to look into stochastic grammars http://en.wikipedia.org/wiki/Stochastic_grammar http://en.wikipedia.org/wiki/Stochastic_grammar.
- jmmcd 13y agoWell, yes, all my grammars are stochastic (else I'd be generating the same piece of music every time).
- kevgnulldev 13y agoI do a bit of algorithmic composition as well (mostly microsound/granular synthesis) using NN and other graphical models (e.g. HMMs) for higher level compositional control... for grammar inference check out: http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.3.393 http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.... Abstract: We show that a recurrent, second-order neural network using a real-time, forward training algorithm readily learns to infer small regular grammars from positive and negative string training samples. We present simulations that show the effect of initial conditions, training set size and order, and neural network architecture...
- jmmcd 13y agoThat sounds perfect -- thanks!
- kevgnulldev 13y agoYou're welcome. You might like this as well (the PDF is just the front matter of the book): http://download.springer.com/static/pdf/967/bfm%253A978-3-642-66438-0%252F1.pdf?auth66=1382903728_da0c75be6801cbf6bc3be0f7e38a4094&ext=.pdf http://download.springer.com/static/pdf/967/bfm%253A978-3-64...
- jmmcd 13y agoHmm, that link doesn't work for me (probably some kind of session id is needed). Can you post another url?
- kevgnulldev 13y agosorry for the late reply... just saw your post: http://www.springer.com/computer/ai/book/978-3-540-88008-0 http://www.springer.com/computer/ai/book/978-3-540-88008-0
- jmmcd 13y agoThanks! Looks like I have a lot of reading to do...