Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use an efficient algorithm to find the best permutation #5

Closed
fakufaku opened this issue Jul 2, 2019 · 3 comments
Closed

Use an efficient algorithm to find the best permutation #5

fakufaku opened this issue Jul 2, 2019 · 3 comments

Comments

@fakufaku
Copy link

fakufaku commented Jul 2, 2019

The current implementation of bss_eval, in mir_eval and here, exhaustively tests all permutations of sources which has factorial cost. It is possible to find the permutation in quadratic time using a minimum weight matching algorithm for bipartite graphs. This algorithm is implemented in scipy by the function linear_sum_assignment.

I have made a PR to mir_eval with the required changes. In mir_eval it seems to start to make a difference in runtime only for 9 or more sources, but the difference is very significant then. However, since you are also implementing computationally lighter versions of bss_eval/si_sdr here, there is potentially room for improvement even with fewer sources.

I'd be happy to pitch in some code if required.

@aliutkus
Copy link
Member

aliutkus commented Jul 2, 2019

I never considered the setting where the order of the sources is unknown in my estimates,

but I think it's a really cool contribution, and I'd be happy if we included this, because the case of MANY sources is probably going to be a big thing in the near future, since few and known sources is working so well

@fakufaku
Copy link
Author

fakufaku commented Jul 2, 2019

Great! In determined separation, this is rather the norm to not know the permutation (or that's how it seemed to me).

Actually, my above comment (now edited) was a bit mis-leading, the PR I did is for mir_eval. I also took a look at the current code in this repo, but I wasn't sure if it is stable enough to accept a contribution. If you think it is the case, I'd be happy to start.

@aliutkus
Copy link
Member

aliutkus commented Jul 2, 2019

I'd be in to have this feature right from the start
still, @faroit may have a better understanding of what needs be done before ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants