Hungarian algorithm on jit.matrix
Hi,
I want to use the Hungarian algorithm (https://en.wikipedia.org/wiki/Hungarian_algorithm) in jitter. Basically, a NxN matrix as input would return a size N vector with the colums indices for each row that minimize the cost (as expressed in the input matrix).
The steps to the algorithm are described here, but the iteration process makes it inconvenient with usual objects. However, I don't really like the idea of externals, and would prefer a vanilla Max solution.
What do you think would be the best way to implement that?
jit.gen ? javascript ? node.script ? else ?
Thanks for any advice!
Interesting question.
That would be the start with standard objects:
And a quick shot at finding the columns with two zeros:
Hi Jean-François,
I got roughly to the same point with dimop and stumbled on the
Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn.
... for which I got to this hint:
That's when I started considering jit.gen (or anything to get through) !
Thanks for your patch though: I learnt about the handy "-1" step in jit.dimop (how handy, compared to using jit.matrixinfo to get the dim!) and you reminded me about the equally handy @in2_name. :)
Still stucked on the next steps...
I ended up using javascript and it was pretty much straight forward using a ready-made library like this one : https://github.com/addaleax/munkres-js
It is a bit CPU-greedy and I'll need to see if this can be optimized somehow, but it does the job for now!
I made a version of hungarian munkres with jitter if anyone is interested. It isnt ideal for larger datasets, but works well on smaller sets. If you need a similar algorithm for larger datasets i also made an implementation of the action algorithm, very fast, but less optimal "optimal transport" if you will :-)
Regards Gus
Btw it was a bit of a nightmare to realize, as i was implementing it, while trying to understand all the steps, so it took quite a while until i got it working. But once all the little details are ironed out, its pretty cool i think.. And its definitely doable with standard jitter objects alongside jit.gen, for more specific operations..
I used it as a way to "gridify" or organize a 2d embedding of audio segment descriptor vectors, using a ton of different ways to describe sound over the duration of a sample. Then i can more easily "browse" or interact with a corpus of sound via a screen, or controllers etc, or simply just inspect interesting neighborhoods, with a large selection of sound.
I just made the 2d embeddings with my own SOM algorithm, but tri-map, pac-map or uMap would probably make better embeddings in 2d on high-dimensional data like audio. I also made some implementations of blue-noise relaxation, as well as sinkhorn iterations which is also pretty useful.
That's great Gussi!
Do you plan to share the code?
The Hungarian algorithm is super useful, indeed.
V8 makes it work decently, but its still not extra fluid. It would be worth having an efficient Jitter version!
Don't know about "efficient" per se, my main motivation behind the patch was just to understand it and make it work. In practice I'd probably just use a python library instead, since faster implementations should be easy enough to find on Github.
Still for most use cases, "auction algorithm" is probably the better fit, for assignment problems:
https://en.wikipedia.org/wiki/Auction_algorithm
It just scales way better with large datasets. Much easier to implement in jitter as well.. For reference on a small test data set of 283 elements with 2 planes, auction (Bertsekas) takes around 35ms on my machine, while Hungarian takes around 15seconds. And the result is nearly identical, meaning we get an almost as good optimal transport or assignment with auction at orders of magnitude faster speeds. With large datasets Hungarian is pretty much impossible to do due to its O(n³) complexity, where auction is only O(n²) more or less.
I'll clean the patch up a bit, and delete unused stuff i worked on in parallel with the patch, then share it when i have the time. Hopefully within a few days.
Thanks for all this info! I didn't know about the auction algorithm, will definitely take a look a it.
The Hungarian wrapper I made with v8 (around the library mentionned above) will match two sets of 200 items in about 500ms on my pretty recent laptop, which is still much behind the 35ms!
Yeah there were some issues with the way i implemented the hungarian using jitter only, that always bugged me. If i remember correctly i had to artificially rate limit certain iterative operations or else objects like zl-family, pack, and other max-native objects would complain, and basically stop working. So i had to put "deferlow" in a few spots within the greedy start assignment module as an example, since i had to use jit.iter in order to set certain values via pack etc.
But maybe there is a way to keep more of the processing in a more jitter friendly, parallel style next time.? My speeds for the hungarian are definitely held back by those issues. But fun to try.
So this is more of a learning project i think, it works, but could be much faster if i did some more thinking :-) Still most of the core processes are jitter.objects where possible.
Have you considered using jit inside JS, if youre already working with that? It's not too hard to set up, and you can get pretty efficient jitter operational speeds using native objects and matrices. Then you can always combine with JS native methods or functions when you have to.
I've build projects in the past, that use JS as the main "max patcher", initializing and interacting with objects entirely within JS, and at least back then before v8, it was much faster than doing iteration in JS alone, on arrays or whatever. Jitter is pretty much capable of numpy-like vectorized operations (parallel, simd) vs regular python arrays as far as i can tell.. In addition i think back then, really large patches would sometimes be slow to work with, due to all the visible patching i assume? so having the ability to essentially "hide" everything inside JS might also in itself help alleviate some of that slowdown due to clutter? But i'm not sure, maybe someone from c74 can elaborate.
Also there is the option for moving on to the GPU for some real speed. Maybe you can find a hungarian GLSL shader somewhere? that would be fast i expect, and easy enough to do in jitter.
Still for any "real sized" or large datasets i think most people use auction anyway :-) just much more easy to parallelize most processes, making it so much faster on modern machines..
Just implemented the Auction and its much faster indeed. Thanks Gussi for the hint!
Also while reading about this, I found out that Dimitri Bertsekas, the mathematician who originally designed the algorithm, passed out recently. So I made this little hommage post, where you can see how smoothly this runs now!