Repository navigation
Project 2: Design a tool to optimize the parameters of any command line tool #9
Description
Project: Given a command line tool with a number of parameters and a target metric to be optimized, I want a tool that will run the program and find the values for those parameters that maximizes some target metric. My particular use case is genome sequence assembly, which often has a variety of parameters related to expected coverage of the reads and heuristics to remove read errors and collapse heterozygous variation. When I tackle that optimization, the process is manual and tedious: submitting jobs to a scheduler, rerunning failed jobs, inspecting outputs, tweaking parameters, and repeating. I want to design and implement a tool to automate that process and generate a report of the result.
Project Lead: Shaun Jackman / @sjackman / Graduate Student / BC Cancer Agency Genome Sciences Centre
Activity
hyounesy commentedon Jun 14, 2016
Interesting.
I have also done some work on general parameter analysis of R/bioconductor packages as part of the VisRseq framework that might be applicable for this problem. I would be happy to provide further info if this may be of immediate use for you.
sjackman commentedon Jun 15, 2016
Hi, Hamid. Thanks for your interest. One approach I had considered was using R functions like
optimandoptimize. Which R optimization function did you use?I had also considered implementing simple optimization methods like grid search, line search, twiddle and amoeba aka Nelder–Mead. However it's implemented, I want it to be usable as a command-line program.
hyounesy commentedon Jun 15, 2016
Makes sense.
For VisRseq (which is not command-line) I am currently using a simple randomized search. I was interested in visual parameter exploration where a target metric does not necessarily exist. For example, for differential expression analysis tools (e.g. edgeR, DESeq, etc.), different parameters result in different genes detected as differentially expressed, but it is not always clear which result is better. I am however considering to experiment with better sampling (e.g. monte carlo) to distribute the parameter samples in the areas where there is more variation in the results.
[-]Design a tool to optimize the parameters of command line software[/-][+]Design a tool to optimize the parameters of any command line tool[/+]sjackman commentedon Jun 23, 2016
There are two existing tools for parameter optimization:
We definitely need to explore whether building on one of these existing tools fits our requirements.
There's also the possibility of building on other optimization systems such as R's
optimizefamily of functions or Python'sscipy.optimize. I don't know whether either of these handles optimization of discrete variables / metrics.sseemayer commentedon Jun 23, 2016
Sounds like a cool idea to have generic parameter optimization for cluster jobs 👍 !
ParOpt is a fairly simple script based on
scipy.optimizethat is limited to jobs running synchronously on one machine where the objective function to be optimized can be parsed from the command line's STDOUT. It does not support asynchronous execution or clusters at all (except for maybe jury rigging some shell scripts to submit/evaluate jobs).Thinking about it, generic optimization could actually benefit greatly from parallelization. Since these generic methods cannot rely on gradients and are typically very slow to run, parallelizing the problem will make the wait times much shorter. Parallelization is definitely possible for grid search since that is embarrassingly parallel, but a quick google search gave me this article on parallel Nelder-Mead too.
It might be possible to run the function evaluations using DRMAA to abstract between different scheduling systems.
I'd be happy to answer any questions you might have about ParOpt 😄
sjackman commentedon Jun 24, 2016
Great! Thanks for your response, Stefan! I'll likely have more questions for you. Any chance you'd like to come to Vancouver, Canada for Hackseq Oct 15–17 and/or ASHG 2016 following it? 😄 You too, Richard @blahah! Come join us! Three ASHG sponsored travel awards ($1,500) are available!
sseemayer commentedon Jun 24, 2016
Both your hackathon and conference sound amazing and I could visit my sister that lives in Redmond, WA so your offer is doubly tempting. On the other hand, I'll have just started my postdoc around then so I'll pass this time. I might come back on that offer next year, though!
sjackman commentedon Jun 24, 2016
😢 Best of luck with your postdoc!
sjackman commentedon Jun 24, 2016
We're planning to have a Docker image with a bunch of bioinformatics software preinstalled running on machines at the BC Cancer Agency Genome Sciences Centre during the Hackathon. Which bioinformatics software do you plant to use for your project? In particular, is there any software that you plan to use that is not already listed here? http://www.bcgsc.ca/services/orca
sjackman commentedon Jun 24, 2016
I'll be using the two tools listed above, Biopsy and ParOpt, as well as Python scipy and R.
Yes, I'm talking to myself. I'm leading a project and also helping to organize the hackathon. =)
whitecat commentedon Jun 28, 2016
This project seems like a cool area of work, running and testing is always a big problem in programming.
What features would you want more than Biopsy and ParOpt already offers? @sseemayer seems to say adding parallelization for cluster jobs. @sjackman refers to adding a different algorithm using R.
sjackman commentedon Jul 1, 2016
I need to set aside some time to test out Biopsy and ParOpt, and to write up the requirements for this project. Off the top of my head:
Other suggestions welcome!
GlastonburyC commentedon Jul 9, 2016
I imagine if there are multiple parameters there will be trade-offs? Perhaps a feature of the live updating report would allow you to display this information. Potentially a choice of what to optimize may be beneficial too, as well as joint optimization of all parameters.
What is the compute time of one run? - Important to know to help determine what opt strategy to use.
20 remaining items
sjackman commentedon Aug 2, 2016
Another optimization package that I stumbled on: https://github.com/HIPS/spearmint
dpo commentedon Aug 2, 2016
Glad you like OPAL. Let me know of any difficulties when you try it. I'm very happy to help.
mgelbart commentedon Aug 3, 2016
Hi all, @sjackman alerted me to this thread. I co-developed Spearmint, which @sjackman posted above. This thread already contains a lot of good stuff, but here's my two cents.
This problem is tricky for many reasons. First, it goes by many names: black-box optimization, algorithm configuration, derivative-free global optimization of expensive functions, etc etc etc. This happened because it lands at the intersection of several fields: statistics (experimental design), optimization, machine learning...
I don't think there's a perfect tool out there... each one has its strengths and weaknesses. Maybe it's useful to make a list of questions about your particular problem. Here is what I always ask:
I think the choice of tool depends on the answers. For example, Spearmint works best for <100 parameters, works better on continuous parameters, is good for very slow functions, can do noisy, can do parallel, and requires a bit of effort on the user's part. It also handles some fancier cases like black-box constraints, which are probably not needed here. But one thing mentioned above which it does handle is integration with remote compute clusters like SGE, DRMAA, etc.
BTW, if you use Spearmint, I suggest grabbing code of the
PESCbranch rather thanmasterbecause the latest stuff is in there and I've been too lazy to merge into master. Actually I'll also be pushing some more improvements soon.Here are some other tools I know about
autoweka/) (Thornton et al., 2013)
DiceOptim/index.html) (Roustant et al., 2012)
The last one is a startup in the Valley doing just this. They have a very nice clean API and might be free for educational use but they charge a lot of money in general.
It would be nice to construct a sort of "decision tree" for choosing a tool based on the specifics of your problem, but nobody has done this yet AFAIK. Here are a few thoughts in that direction though:
optimize, Nelder-Mead, genetic algorithms. These will not be as sparing in the use of function evaluations as, say, Bayesian optimization methods. OTOH, if your function is not that slow, heavyweight software like Spearmint may be overkill, leading to a big inefficiency if the optimizer itself takes much more time than the function evaluations.mgelbart commentedon Aug 3, 2016
(@dpo, I'm not sure if we've met, but I've certainly heard a lot about you from our mutual friend Sasha Aravkin. I had no idea you were working on this stuff!)
sjackman commentedon Aug 3, 2016
Thanks for the detailed response, Mike. Here are the answers to your questions:
A maximum of about 16 parameters. I can order them by priority to fit in whatever limit. The parameters that I'm most interested in number about 5. Even optimizing a single variable k would be useful. Doing it by hand is easy but tedious. Here's a typical list from ABySS: https://github.com/bcgsc/abyss#assembly-parameters
Nearly all integer. Two continuous variables, though the response to these variables will not be smooth but steppy.
Fifteen minutes for toy problems like bacteria, a day or two for typical problems like human, and a week for large problems like spruce.
Yes. Integration with a scheduler would be helpful.
Yes.
Thanks, Mike!
mgelbart commentedon Aug 3, 2016
@sjackman Given your answers, I think Spearmint (or similar approaches) would be a reasonable fit. I could help out a bit. Spearmint deals with integers by pretending they are continuous variables, and then just rounding them at the end. This means it can do dumb things sometimes, but it's not horrible. There will probably be several good tools and it will come down to which one you find easier/convenient to use. Perhaps the cluster integration is a selling point of Spearmint.
Also, I forgot another important question (I edited my post above to add it to the list, for posterity): is your function noisy? In other words, if you run your code twice with the same parameters, will you get the same results? This is something that Spearmint handles naturally but will break some more classical optimization methods.
sjackman commentedon Aug 3, 2016
No. The function is deterministic. At least ABySS is. Other genome assembly programs may not be. I'm a developer of ABySS.
sjackman commentedon Aug 3, 2016
How about optimizing multiple metrics and finding the Pareto frontier? With genome assembly you want to optimize both the contiguity and the correctness of the assembly. There are other performance indicators, but those two are the most important. They can be blended into a single metric, called NGA50.
mgelbart commentedon Aug 3, 2016
Ha! Funny that you asked that. This touches on my specific area of research, and is a rare case where Spearmint is way ahead of most alternatives. There are 3 approaches:
Approach (1) means you can just use one of the techniques we've been talking about, but it is the least satisfying because you have to arbitrarily pick a weight for blending. For approach (2), well sometimes your problem really is of this nature and other times you are framing it this way when it's truly a multi-objective problem. In any case, Spearmint can deal with this if you're using that
PESCbranch of the repo I mentioned above. My thesis might be a good reference. For (3), my collaborators recently came out with code for this, which lives on yet another branch of the Spearmint repo. I haven't used this myself but I think it should be reasonably straightforward. Here's the paper.Finally, once you get into this "multi-objective" territory, there is an additional question to ask yourself:
For most cases, the answer is the former -- yours too, probably? But if it's the latter than you can play some tricks to increase efficiency a lot. For example, imagine contiguity takes 30 seconds to measure and correctness takes 3 hours. Then you're much better off testing contiguity for many parameter values and zeroing in on promising regions of the space before investing the big resources in measuring correctness.
sjackman commentedon Aug 3, 2016
Great! For this hackathon project, I plan on doing a mixture of 1 and 2 for the actual optimization. For example optimize contiguity, and then optimize correctness constrained that the contiguity can't decrease by more than 10% (for example). After the optimization I'll plot the Pareto front of all the runs that were run, without actually trying to optimize the front. It would be nice to eventually get to 3 though.
All the metrics come from the same run, pretty much. It takes 95% or more of the time to get the genome assembly, and then just a bit longer to measure its contiguity and correctness, which are measured with independent programs, and correctness does take longer to measure than contiguity.
dpo commentedon Aug 4, 2016
Nice to meet you @mgelbart ! I've certainly heard about you from Sasha as well. Thanks for listing so many alternatives for parameter optimization. It's a hot topic.
NOMAD, the black-box optimizer hiding underneath OPAL can also solve multi-objective problems but that feature hasn't been interfaced in OPAL. It wouldn't be too difficult to do I believe.
The main trick in NOMAD is to define a surrogate model that will speed up the optimization and somewhat expand the search to wider regions. The beauty of it is: anything can be a surrogate model. The surrogate need not be an "approximation" of the actual objective in the sense of numerical analysis. It should merely be a guide and indicate promising regions. There are examples in the papers I linked to above. In particular, any other optimizer listed above could be used as a surrogate. In that case, NOMAD will act as a safety net in case that optimizer fails to identify an improved guess, or fails for any other reason. The convergence guarantees will continue to apply.
[-]Design a tool to optimize the parameters of any command line tool[/-][+]Project 2: Design a tool to optimize the parameters of any command line tool[/+]dpo commentedon Oct 9, 2016
I'd like to introduce two colleagues of mine who specialize in optimization with special interest in derivative-free and parameter optimization: Margherita and Philippe. Just so everybody can find out who everybody is, I'm going to list the home pages (I don't believe they currently are Github users):
Margherita: http://web.math.unifi.it/users/porcelli
Philippe: http://perso.fundp.ac.be/~phtoint/toint.html
Margherita and Philippe both author a nonsmooth optimization package called BFO (for Brute-Force Optimization), a new kid on the block that we believe would also fit well in your testing schedule. BFO is written in Matlab and is built on principles that share similarities with the optimizer underlying OPAL:
https://sites.google.com/site/bfocode
BFO is being actively worked on and I am told it should support surrogate models and categorical variables in the near future (if it doesn't already). One of its distinctive features is that it will self-tune on the test problems given.
If you don't have access to Matlab, one of us will be happy to run the tests; we just have to engineer communication between Matlab and your tools.
We're hoping you'll include BFO in your tests. We're available to answer any questions and to contribute as we're always looking for interesting new applications of parameter optimization.
sjackman commentedon Oct 9, 2016
This issue has permanently moved to hackseq/2016_project_2#1