0
$\begingroup$

There's a lot of work done in statistics, while state-of-art in lossless data compression is apparently this: http://mattmahoney.net/dc/dce.html#Section_4

Please suggest good methods/models applicable for data compression. To be specific:
1) How to estimate the probability of the next bit in a bit string?
2) How to integrate predictions of different models?

Update:

you should include a better description of what data you want to compress...

Why, I'm talking about universal compression obviously. For data with known structure its really not a mathematical problem, so there's no sense to discuss it here. In other words, the first question is: given a string of bits, what do we do to determine the probability of the next bit, as precisely as possible?

otherwise we will have 10 different answers trying to summarize different part of the huge theory of compression

I'd written quite a few statistical compressors, and I'm not interested in that. I'm asking how a statistician would approach this task, detect correlations in given data, and compute a probability estimation for the next bit.

In addition, the two point you give to be more specific are not detailed enough to be understood.

What's not detailed in there? I'm even talking about bits, not some vague "symbols". I'd note though, that I'm talking about "probability of a bit" because computing a probability of bit==0 or bit==1 is a matter of convenience.

Also, I'm obviously not talking about some "random data compression", or methods with infinite complexity, like "Kolmogorov compression". Again, I want to know how a good statistician would approach this problem, given a string of bits.

Here's an example, if you need one: hxxp://encode.ru/threads/482-Bit-guessing-game

$\endgroup$
  • $\begingroup$ you should include a better description of what data you want to compress... otherwise we will have 10 different answers trying to summarize different part of the huge theory of compression. In addition, the two point you give to be more specific are not detailed enough to be understood. $\endgroup$ – robin girard Aug 7 '10 at 9:32
  • $\begingroup$ Thank you for updating! you said: "I'm talking about universal compression obviously" even if things are obvious within your community you maximise the chance of having original instructive answer by recalling things we few words or a link. $\endgroup$ – robin girard Aug 12 '10 at 11:31
  • $\begingroup$ My personal view is that we should not mix comments and question. Comment are made to give feedback or to ask questions about the question, most often it is a dialogue between two people. The question should be something clear, easy to read and understandable by as much people as possible... it's you explaining your problem to get an answer. $\endgroup$ – robin girard Aug 12 '10 at 11:36
2
$\begingroup$

Interesting question! All statistical models can be viewed as performing lossy data compression. For instance simple linear regression with one predictor replaces $N$ points (where $N$ can be massive, e.g., in the 1000s) with two parameters: a slope and intercept. The parameters may then be used to reconstruct the data, with degree of success depending on how good the original fit was.

Your specific example concerns predicting binary time series data (Bernoulli distributed data, which is a specific case of the binomial distribution). Binary data can encode a lot: coin flips, pictures, sounds, the digits of $\pi$, statistical programming languages...

As you can imagine, and as a quick search around Google will confirm, there are a lot of statistical models which could apply to binary data. One is logistic regression, or (to express the same model in a more general framework) a Generalized Linear Model with a binomial distribution and a logit link function. The function fit is of the following form: $\mbox{logit}[P(Y)] = \beta X + \epsilon$, where $X$ (predictors), $Y$ (probability of a 1), and $\epsilon$ (residuals) are vectors.

Okay. Now a little demonstration. Suppose data are generated so that the probability of a 1 correlates with the sine of time (represented as black points in the graph below). You don't know this, however. You get data for time points from 0 to 359 (blue points).

alt text http://img196.imageshack.us/img196/589/cointimepredict2.png

With the available data points, I fitted the function $\mbox{logit}[P(Y)] = \beta_0 + \beta_1 t + \beta_2 t^2 + \beta_3 t^3$, which popped out as $\mbox{logit}[P(Y)] = -0.2 -30.9 t -3.1 t^2 + 22.2 t^3$. (The probability predictions are plotted in red.) It's a good fit to the data (between 0 and 359). However as you can see, when extrapolating, it does a rather poor job: beyond a certain point it says "just guess 1!"

Take-home message: to do the analysis correctly, you need to have a some idea of the likely processes generating the data. If I knew a sine process were doing the job, then I'd be able to do a wonderful job predicting. Thinking about this is where a statistician would start. The appropriate model is always going to be domain specific, which is why, for example, compression techniques working well for images don't automatically apply to sounds.

$\endgroup$
  • $\begingroup$ Thanks, your post looks really nice, and its what I'd expect from a statistician too. I'd appreciate the explanation of the choice of logistic regression though :) But unfortunately it doesn't help me at all. Like, your function fitting is LMS, right? Even with logit, does it really minimize the (abs) entropy? Also all the common models in data compression are discrete - eg. a bit run model. Anyway, I guess I'd really have to ask a few more specific questions instead. $\endgroup$ – Shelwien Aug 14 '10 at 9:15
  • $\begingroup$ It's usually fitted using maximum likelihood estimation. You really need to say some more about what might have generated the binary data to progress any further. Also is there a specific data set? I see you linked to one, but was that just randomly chosen or do you have another specific one in mind? $\endgroup$ – AndyF Aug 14 '10 at 10:51
  • $\begingroup$ Its good then if its maximum likelihood, but it turns into bruteforce in real cases which is not very practical. As to "specific data", I can post some (eg from a text compressor), but the whole point is that we don't know a good model for it. So instead we have to "mix" predictions of a few not-so-good models. $\endgroup$ – Shelwien Aug 14 '10 at 11:46
  • $\begingroup$ posted an example $\endgroup$ – Shelwien Aug 14 '10 at 12:11
0
$\begingroup$

So, here's the example: http://nishi.dreamhosters.com/u/book1bwt_de.txt

Its a list of choices between 'd' and 'e' in coding of BWT output of a plaintext book. (This is a practical task, think bzip2). For the reference, current result is (reasonably good, but not really the best possible) 6087 bytes = 48686 bits (ie log-likelihood) for that string of 99054 bits

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.