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!