Graduate Student Alumnus (Ph.D.)
I was a graduate student in Prof. Rina Dechter's group, working towards a Ph.D. in Artificial Intelligence and Machine Learning in the School of Information and Computer Sciences at UC Irvine. I began my studies in the Fall of 2006 and have successfully defended my dissertation in March 2013.
My area of concentration is probabilistic inference and constraint reasoning, or more generally inference in graphical models. The unifying theme of my research lies in exploiting problem structure to solve various kinds of inference tasks. The input is often formulated as constraint satisfaction and optimization problems (CSPs / WCSPs) as well as queries over Bayesian and Markov networks (e.g., P(e), MPE, belief updating). These problems are typically NP-hard.
I have investigated methods like variable elimination and belief propagation for exact and approximate reasoning, but the focus of my thesis work is on search methods for optimization. The underlying general framework of AND/OR search spaces allows capturing independencies as well as redundancies among subproblems. Over time my work on these inference methods has also increasingly intersected with distributed computing and statistical learning.
In particular, the main contributions of my graduate work are as follows:
- I have studied anytime performance of AND/OR Branch and Bound for optimization problems. My scheme Breadth-Rotating AOBB achieves better performance with unchanged asymptotic complexity guarantees, yielding successively better solutions faster; this turns it into a viable approximation scheme while maintaining completeness.
- I have developed distributed versions of our state-of-the-art sequential AND/OR search algorithms. The assumed parallel framework is very general (loosely coupled, independent worker nodes with minimal communication). We have empirically demonstrated good parallel speedup on several hundred machines.
- I have investigated learning of statistical regression models for complexity prediction of the aforementioned inference schemes. These estimates are crucial, for instance, in achieving efficient load balancing in the distributed implementation. Other possible applications include guidance in parameter selection for the respective algorithms.
Applications are manifold, but one driving factor in our experimental evaluation are haplotyping and linkage problems over general pedigrees in human genetic analysis (under a joint NIH grant with computational biologists and statisticians). These queries can be modeled as Bayesian networks and are thus susceptible to our advanced inference methods. Other relevant problem domains include medical diagnosis, scheduling and planning, information theory, and image segmentation.
An entry based on my AND/OR Branch and Bound implementation placed first in all three MPE tracks of the PASCAL 2011 Probabilistic Inference Challenge. A previous version of my solver placed third in the UAI'10 Approximate Inference Challenge. Before that, I was involved in organizing the UAI'08 Probabilistic Inference Evaluation.
My implementation of sequential and distributed AND/OR Branch and Bound can be downloaded below (full source code under GPL); our research group also maintains a (slightly outdated) website where we make available some of the algorithms that were developed in the past: http://graphmod.ics.uci.edu/
Before coming to UCI I was a student at RWTH Aachen University in Aachen, Germany and Chalmers University of Technology in Gothenburg, Sweden, from which I obtained a M.Sc. degree in Dependable Computer Systems in 2006.
I maintain a (sparse) personal webpage at www.lotten.net.
- Extending the Reach of AND/OR Search for Optimization in Graphical Models.. Lars Otten. Ph.D. Thesis, 2013.
- AND/OR Branch-and-Bound on a Computational Grid. Lars Otten and Rina Dechter. To appear in Journal of Artificial Intelligence Research Vol. 59, 2017. (Problem instances)
- A System for Exact and Approximate Genetic Linkage Analysis of SNP Data in Large Pedigrees. Mark Silberstein, Omer Weissbrod, Lars Otten, Anna Tzemach, Andrei Anisenia, Oren Shtark, Dvir Tuberg, Eddie Galfrin, Irena Gannon, Adel Shalata, Zvi U. Borochowitz, Rina Dechter, Elizabeth Thompson, Dan Geiger. In Bioinformatics Vol. 29(2), 2012. (Supplementary material)
- Anytime AND/OR Depth-first Search for Combinatorial Optimization. Lars Otten and Rina Dechter. In AI Communications Vol. 25(3), 2012. Extended Abstract in Proceedings of CP'14.
- Caching in Context-Minimal OR Spaces. Levi Lelis, Rina Dechter, and Lars Otten. In Proceedings of SoCS'15, Ein Gedi, Israel, June 2015.
- Memory-Efficient Stratified Sampling for Search Tree Size Estimation in Graphical Model Optimization. Levi Lelis, Lars Otten, and Rina Dechter. In Proceedings of CP'14, Lyon, France, September 2014.
- Predicting the Size of Depth-First Branch and Bound Search Trees. Levi Lelis, Lars Otten, and Rina Dechter. In Proceedings of AAAI'13, Bellevue, WA, July 2013.
- A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models. Lars Otten and Rina Dechter. In Proceedings of UAI'12, Catalina Island, CA, August 2012.
- Join-Graph-Based Cost-Shifting Schemes. Alexander Ihler, Natalia Flerova, Rina Dechter, and Lars Otten. In Proceedings of UAI'12, Catalina Island, CA, August 2012.
- Advances in Distributed Branch and Bound, Lars Otten and Rina Dechter. In Proceedings of ECAI'12, Montpellier, France, August 2012.
- Anytime Depth-first Search for Combinatorial Optimization, Lars Otten and Rina Dechter. In Proceedings of SoCS'11, Barcelona, Spain, July 2011.
- Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models, Kalev Kask, Andrew Gelfand, Lars Otten, and Rina Dechter. In Proceedings of AAAI'11, San Francisco, CA, USA, August 2011.
- Finding Most Likely Haplotypes in General Pedigrees through Parallel Search with Dynamic Load Balancing, Lars Otten and Rina Dechter. In Proceedings of PSB'11, The Big Island of Hawaii, USA, January 2011.
- Towards Parallel Search for Optimization in Graphical Models, Lars Otten and Rina Dechter. In Proceedings of ISAIM'10, Fort Lauderdale, FL, USA, January 2010.
- Maximum Likelihood Haplotying through Search on a Grid of Computers, Lars Otten, Rina Dechter, Mark Silberstein, and Dan Geiger. In Proceedings of RECOMB'09, Tucson, AZ, USA, May 2009.
- Refined Bounds for Instance-Based Search-Complexity of Counting and Other #P Problems, Lars Otten and Rina Dechter. In Proceedings of CP'08, Sydney, Australia, September 2008. [LNCS Link] (also available: extended workshop version)
- On the Practical Significance of Hypertree vs. Tree Width, Rina Dechter, Lars Otten, and Radu Marinescu. In Proceedings of ECAI'08, Patras, Greece, July 2008.
- Bounding Search Space Size via (Hyper)tree Decompositions, Lars Otten and Rina Dechter. In Proceedings of UAI'08, Helsinki, Finland, July 2008.
- Randomization in Constraint Programming for Airline Planning, Lars Otten, Mattias Grönkvist, and Devdatt Dubhashi. In Proceedings of CP'06, Nantes, France, September 2006. [LNCS link]
- Winning the PASCAL 2011 MAP Challenge with Enhanced AND/OR Branch-and-Bound, Lars Otten, Alexander Ihler, Kalev Kask, and Rina Dechter. In DISCML'12 Workshop, at NIPS'12, Lake Tahoe, NV, USA, December 2012.
- Learning Subproblem Complexities in Distributed Branch and Bound, Lars Otten and Rina Dechter. In DISCML'11 Workshop, at NIPS'11, Granada, Spain, December 2011.
- Mini-bucket Elimination with Moment Matching, Natalia Flerova, Alexander Ihler, Rina Dechter, and Lars Otten. In DISCML'11 Workshop, at NIPS'11, Granada, Spain, December 2011.
- Anytime Depth-First Search with Problem Decomposition for Optimization in Graphical Models, Lars Otten and Rina Dechter. In GKR'11 Workshop, at IJCAI'11, Barcelona, Spain, July 2011.
- Load Balancing for Parallel Branch and Bound, Lars Otten and Rina Dechter. In SofT'10 Workshop and CRAGS'10 Workshop, at CP'10, St. Andrews, Scotland, September 2010.
- Refined Bounds for Instance-Based Search-Complexity of Counting and Other #P Problems (Extended version), Lars Otten and Rina Dechter. In Counting Workshop '08, at CP'08, Sydney, Australia, September 2008.
- Bounding Graphical Models Processing by Hypertree Width, Lars Otten and Rina Dechter. In Doctoral Programme of CP07, Providence, RI, USA, September 2007.
Zip archive with problem instances used for several papers above:
- uai_problems.zip, in UAI format.
Available for download below is my sequential AND/OR Branch and Bound (AOBB) implementation called daoopt that solves MPE or similar max-product queries over Bayesian or Markov networks. It implements both standard depth-first AOBB and Breadth-Rotating AOBB as introduced in our SoCS'11 paper (PDF) for improved anytime performance. Both variants use the Mini Bucket heuristic for pruning and to guide the search. The full source code also includes distributed AOBB as described in my dissertation.
- Outdated: precompiled daoopt-0.99.5a (32 bit static Linux binary).
- Full source release under GPL License.
The problem specification should be in UAI file format, gzipped input is supported. Run the program with the --help argument to see a list of options, and feel free to contact me with questions. In general I'd be happy to hear from you if you're using the solver.