Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

# Daniel_Burfoot comments on Talk about your research - Less Wrong Discussion

11 15 May 2011 01:32AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: 16 May 2011 02:30:21AM 2 points [-]

Did you reverse this? e.g. compression is useful for POS tagging, etc.

No, the original is correct. Let's say you want to compress a text corpus. Then you need a good probability model P(s), of the probability of a sentence, that assigns high probability to the sentences in the corpus. Since most sentences follow grammatical rules, the model P(s) will need to reflect those rules in some way. The better you understand the rules, the better your model will be, and the shorter the resulting codelength. So because parsing (and POS tagging, etc) is useful for compression, the compression principle allows you to evaluate your understanding of parsing (etc).

Comment author: 16 May 2011 06:13:13PM 0 points [-]

If your project works, then, it will reduce science to a problem in NP?

Comment author: 16 May 2011 07:21:30PM 1 point [-]

That's what other compression advocates want to do. In fact, it's pretty obvious that this is true - if you found an algorithm capable of computing the Kolmogorov complexity of any input string, you would pretty much put all theoretical scientists out of work. Unfortunately or not, this problem is uncomputable. Some people (Hutter et al) think, however, that it is possible to find good general purpose algorithms for computing approximations to the K-complexity.

I disagree - I think such algorithms are far out of reach. To me, the compression idea is interesting because it provides a new way to evaluate one's understanding of various phenomena. I want to study text compression because I am interested in text, not because I think it will lead to some grand all-purpose algorithm. This is in the spirit of The Virtue of Narrowness.