Using machine learning to choose compression algorithms

https://vks.ai/2019-12-05-shrynk-using-machine-learning-to-learn-how-to-compress

by kootenpv • 7 years ago

125 58 7 years ago

gwern3• 7 years ago

Isn't one of the benefits of time-series databases more compact storage at minimal overhead?

kootenpv14• 7 years ago

Definitely! I really optimized for "no development time spent" and was just using pandas to extract html tables into csv and just store them :-). 2 lines of code really. I had no idea I would have it running for so long.

It was really just the example that made me wonder why I have to consider which compression would be best for files with my characteristics - but not saying it was best practice to begin with haha!

kootenpv14• 7 years ago

I'm a long time fan of your blog :O

sillysaurusx• 7 years ago

Me too! A few months ago I made detailed notes on how to set up your own: https://github.com/shawwn/wiki

Gwern was kind enough to assist by sending over the exact version numbers of all the Haskell libraries it depends on, and answering some questions about deployment. The version numbers turned out to be crucial to getting everything running.

IMO https://www.gwern.net/ is the ideal combination of style + ease of use (for the writer) + effective ways of organizing knowledge.

The whole thing is hosted out of an S3 bucket, so there's no server to manage and zero downtime. I've wondered if it'd be possible to use github pages for this purpose, since that would make it completely free. But it only takes a couple hours of work to get everything up and running. The biggest delay is waiting for haskell to compile all the libraries.

gwern3• 7 years ago

Thanks. I think it's a nice point in design space. Sort of a Art Deco Modernist minimalism, perhaps? But with rich features and excellent performance.

proverbialbunny5• 7 years ago

Does anyone know what is the leading time-series database people use today? Like, eg, bar / tick data.

(I use PostgreSQL, due to my ignorance.)

kbaker• 7 years ago

If you can model the domain, then you can achieve very good compression.

See this recent timescaledb post (since you mentioned Postgres) which goes over an array of techniques used in column-store databases that general-purpose compressors on a csv file full of data would not be able to match:

https://blog.timescale.com/blog/building-columnar-compressio... discussion: https://news.ycombinator.com/item?id=21412596

kootenpv14• 7 years ago

There's TimescaleDB built on top of PostgreSQL.

ploika• 7 years ago

I've never used it myself, but kdb+ is meant to be excellent if you need it.

JamesBarney2• 7 years ago

I've been happy with influxdb, but I've also noticed that a lot of people switch to a time series database way before they need to. You can go pretty far with postgres/oracle/sql server, and it has the advantage you don't need to manage different databases.

pedrocx4862• 7 years ago

Is there a way to do the reverse?

There's a quite "legendary" Game Boy Advance game out there (Klonoa - Densetsu no Star Medal) that never got a translation to English because it has some sort of in-house created compression by Namco applied to the game that was made so it could fit into a GBA cartridge. AFAIK no one was ever able to crack it open and release the code to de/compress it.

A while ago I had a "bounty" of USD100 for anyone that could do it (just the decompression and re-compression, not translation) but there aren't many people that want to fiddle with low-level GBA coding.

yorwba2• 7 years ago

I'm assuming the game is playable, i.e. the decompression code is included on the cartridge and you just don't know how it works. In that case you could emulate the game and use a language model to identify strings containing Japanese text (you'd need to know the encoding to do that) so they can be extracted for translation. That doesn't allow you to put the translations into the compressed code, but you might be able to instrument the emulator to inject translated strings on-the-fly.

amelius• 7 years ago

You might as well write a tool that extracts strings from a video signal using OCR, and translates them. That would make the solution more universal, and you could even use it to e.g. suppress ads.

londons_explore• 7 years ago

The GBA didn't have much RAM. There is a good chance tiny chunks of the game get decompressed as needed, and there is never a time when the whole thing is decompressed at once and can be dumped.

anaphor• 7 years ago

You should be able to do it with enough sample data, but it might not be perfect since you'd still be guessing at what it's really doing.

proverbialbunny5• 7 years ago

Anyone who does malware analysis professionally has to deal with packed data in new and funky ways, as malware binaries tend to be packed (ie compressed) in unique ways to get past antivirus software.

If the bounty was high enough there are people out there who do this sort of thing professionally and would probably jump on the opportunity.

eru• 7 years ago

For something like an obscure GBA game, you can probably write up some blogposts to add reputation to the minuscule monetary value of the bounty.

ma2rten2• 7 years ago

Instead of trying to crack the compression algorithm directly, it would make sense to disassemble the machine code and try to understand what it does.

nautilus12• 7 years ago

Doesn't it depend on whether the algorithm is lossy? If it's lossy (not bijective) it's impossible to invert the function

simiones2• 7 years ago

This is discussing text or code compression. There's no point in using lossy methods for the dialogue of your game.

phire• 7 years ago

It might end up smarter to RE the decompression and then patch the game to accept an uncompressed translation (and bump up the size of the rom from 16mb to 32mb)

js8• 7 years ago

How does it compare to context mixing algorithms such as https://en.wikipedia.org/wiki/ZPAQ ?

kootenpv14• 7 years ago

shrynk is not doing any compression itself, it's using ML to do a "meta" approach: it computes features on your data like how many rows, how many columns, how much duplication etc, and then predicts which existing compression algorithm (out of the available compressions) will be best given your requirements/preferences in terms of size, write time and read time.

jedimastert• 7 years ago

A somewhat different example but related (at least by name) but I recall an article from Chris Wellons' blog, Null Program, where he wanted to "discover" a new hashing algorithm, so he randomly generated them, JT compiled them to native, then tested them.

There was, how ever, no machine learning or optimizing. Instead, he called it "prospecting" and just generate a new one from scratch each time until he found something interesting.

https://nullprogram.com/blog/2018/07/31/

kootenpv14• 7 years ago

Yea - that is related to genetic programming. That, and using auto-encoders for e.g. image compression are known approaches in "AI".

I'm particularly proud of this meta approach and I am actually thinking this could become huge: the same thing can be done for hyperparameter optimization in machine learning tasks.

Hyperparamter optimization is currently focused on minimizing cross-validation error, but using this concept you could have weights on accuracy, training time and prediction time (very similar to compression where the 3 dimensions are size, write time and read time), and then given a new unknown dataset you could predict what model/hyperparameters to use.

Maybe this should be patented ;)

eugenhotaj• 7 years ago

I'm particularly proud of this meta approach and I am actually thinking this could become huge: the same thing can be done for hyperparameter optimization in machine learning tasks.

There is already a substantial field of Machine Learning/Meta Learning which focuses on exactly this. For example, this paper [1] from NeurIPS 2015 does exactly what you suggest.

[1] https://papers.nips.cc/paper/5872-efficient-and-robust-autom...

md_3• 7 years ago

When and why would you want to apply ML to this problem?

Off the cuff, this seems like it competes with an alternative of simply running every considered compression algorithm and choosing the optimal one. I guess this would be advantageous if the RF classifier is meaningfully faster to run than the compression algorithms themselves. Is it?

kootenpv14• 7 years ago

Spot on (I briefly touch on this in the article)! This is why I try to work with cheap-to-compute features. I used to calculate how unique all values were, but ended up taking a sample instead to speed that part up for large data!

md_3• 7 years ago

How does that compare to just doing compression on a sample of data? :)

proverbialbunny5• 7 years ago

Is it possible to run data through a DNN, making sure the output is the same as the input (or close for lossless data), then take an autoencoder variant, record the 'compressed' data, then on the other end have the other half of the DNN to decompress it?

I'm pretty ignorant on the topic, so I get that that may be off, but if so, why wouldn't that be a valid solution to compressing data?

visarga• 7 years ago

Autoencoders have lossy compression.

kootenpv14• 7 years ago

Indeed, but this is for lossless compression :)

d_burfoot2• 7 years ago

Sure, and you can add some correction bits to fix the lossy encoding of the autoencoder.

The problem is that you have to encode/send the DNN itself, otherwise your receiver won't know how to decode the data. If you are not smart, the added codelength of the DNN will likely blow away your savings. If you are smart, this leads to a whole formulation of machine learning called MDL:

https://en.wikipedia.org/wiki/Minimum_description_length

mattnewport2• 7 years ago

From the data shown it's not obvious that some of the options would ever be best, would be interesting to see if any of the non csv options ever beat the csv options and for what type of data.

kootenpv14• 7 years ago

I can give you this... the larger the data the more useful parquet and compression on it will be...

mattnewport2• 7 years ago

From the brief description it seems like Parquet is just a weaker version of what a decent LZ style compressor will do anyway

mappu• 7 years ago

Are all compressors simply being run with their default arguments? There's a lot of scope for speed/filesize tradeoffs within a single compressor.

EDIT: You are missing `csv+zstd` ? It should obsolete `csv+gzip` at all speeds and compression levels.

There is a pareto-optimality frontier here - I ran my testing back in 2016 https://code.ivysaur.me/compression-performance-test/ but the numbers are now a little bit obsolete (e.g. zstd and brotli have both seen a lot of improvements).

alexott• 7 years ago

+1 - and if you could use zstd with custom dictionary, then you can achieve even better compression ratios

kootenpv14• 7 years ago

Yea zstd is really amazing... if I would choose a single one all the time it'd be zstd for sure.

kootenpv14• 7 years ago

Yea, I thought parameters per compression algorithm should indeed be added in a next version :) more compute but definitely an improvement. I think pandas doesn't offer zstd as option with csv, but I'll check once more.

EDIT: indeed, it's missing in `to_csv` - seems like an oversight.

WoodenChair• 7 years ago

We did a fun experiment in Chapter 5 of Classic Computer Science Problems in Python. We ran a genetic algorithm to find what order of a list (assuming the order doesn't matter) of names led to the best compression using one of the Python standard library's built-in compression algorithms. This article has made me interested in re-running the experiment with multiple compression algorithms.

d_burfoot2• 7 years ago

Why not use ML to build a statistical model of your data, and then use that model to compress it? You will likely get better codelengths for your specific dataset than off-the-shelf algorithms can achieve. And if you figure out a good model that describes the fluctuations in the cryptocurrency prices very well, then you can use that model pretty directly to make money via automated trading.

I've got an easy-to-use library for arithmetic encoding in Java, it would be easy to port to other languages: https://github.com/comperical/MirrorEncode

numbol• 7 years ago

Funny, it deeply resembles the last episodes of "Silicon Valley"

More seriously, the generalized compression algorithm can be one of the keys or even one of the definitions of generalized artificial intelligence

And Kolmogorov’s complexity was present by a subtle reference in the very last episode ...

mebr• 7 years ago

The wording could be improved to make it easier understand what is being offered more quickly.

This is using machine learning to predict on the given heterogeneous tabular data which compression algorithm will yield a higher compression rate.

There are multiple other ways to do this approximation.

Using machine learning to choose compression algorithms

Related Stories