Comment by ot | Hacker News Reader

Comment by ot | Hacker News Reader

Compression is truly fascinating. It's what got me into reading computer science papers several years ago, and then became one of my research topics.

What is shown here is the LZ77 [1] factorization of a string. Compression in general works by exploiting redundancy in the source, and natural language is highly redundant, since many words repeat often. Hence the factors in the factorization often look like frequent words or n-grams.

A recent line of research is grammar compression, which tries to turn a text into a tree of rules that generate that text. While still not very good at general-purpose compression, the generated tree are much more interesting than the LZ77 factorization, since they "discover" something that looks like a syntactic parsing of the string, finding syllabes, words, phrases, sentences...

In Craig Nevill-Manning's Ph.D. thesis [2] introduction there are several examples of the inferred grammar of pieces of text, music, fractals, source code, etc... While the algorithm presented there (Sequitur) is now kind of obsolete, the thesis is very interesting because it makes some considerations with a linguistic perspective.

[1] http://en.wikipedia.org/wiki/LZ77_and_LZ78

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1...

Wow, those are some interesting links.

As somebody who's learned a foreign language to near-fluency as an adult, I've spent a lot of time trying to figure out how my brain infers a grammar from large quantities of input. Subjectively, it feels like my brain learns fixed phrases, and then notices that certain chunks can be replaced by subtrees of the appropriate type.

There are complications: inflections, gender, agreement, probability, and so on. But still, grammar compression looks like a fascinating formulation of the problem.

Yes that's what algorithms like RePair and Sequitur do: they build the tree bottom-up by replacing frequent subtrees with a new rule at each iteration.

I think that this is also the basic idea behind the usage-based model in linguistics, a theory on how we learn languages:

    The usage-based model is based on inductive learning,
    meaning that linguistic knowledge is acquired in a
    bottom-up manner through use. It allows for redundancy 
    and generalizations, because the language user generalizes
    over recurring experiences of use.

http://en.wikipedia.org/wiki/Construction_grammar#Grammar_as...

Very interesting. I feel like the very concept of a grammar is only a model we cast on language to make it easier to deal with. Langage is pretty free and can work without it. Grammar feels to me like a normalization "by contract". We normalize, then study the normalization tool itself without being aware it is an artefact. We model the model, give it free parameters, randomness, serendipity to make it accomodate reality and its endless string of special cases. We even try to separate meaning from experience.

This all feels more like a network of relations and probabilities of coocurrence of various (free?) orders. I followed your link and I strongly feel the suffix "grammar" is the real burden here. We're trying to put structure on what is actually creating it.

Every language has grammar by definition. We're just trying to discover it.

It's like the laws of physics: We have laws which seem to work, but we know they're not the whole story, so we observe more of what happens and try to bring our laws into harmony with the actual underlying laws.

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?

It 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

[2] http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf

Thanks.

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.

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

Well, yes, all my grammars are stochastic (else I'd be generating the same piece of music every time).

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

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

That sounds perfect -- thanks!

You'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-64...

Hmm, that link doesn't work for me (probably some kind of session id is needed). Can you post another url?

sorry for the late reply... just saw your post: http://www.springer.com/computer/ai/book/978-3-540-88008-0

Thanks! Looks like I have a lot of reading to do...

Reply on news.ycombinator.com