Lars Otten, UC Irvine

Lars Otten

Position:	Graduate student / Ph.D. candidate
Email:	(GPG key)
Office:	4099 Bren Hall
Address:	Department of Computer Science University of California, Irvine Irvine, CA 92697-3435

I am 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've begun my studies in the Fall of 2006 and hope to defend my dissertation in Summer 2012.

Research – Teaching – Personal – Publications – Software

Research

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 recently 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 (new: 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/

Teaching

I am not teaching at this point. In Spring 2009 I was the teaching assistant for CS 174 "Bioinformatics" with Prof. Xiaohui Xie. I was a reader for ICS 11 / Econ 11 "The Internet and Public Policy" with Prof. Scott Jordan in Winter 2009 and teaching assistant for CS 175 "Project in AI" with Prof. Eric Mjolsness in Fall 2008.

Personal

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.

The best way to get in touch with me is via email at email address . For encrypted email, you can obtain the respective GnuPG key from a key server (here for instance), its ID is 0x830EB280 with the following fingerprint:
869A 685A 0951 E946 92C0 8C7F A9A6 C83A 830E B280.

Journal Articles

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. To appear in Bioinformatics, 2012. (Supplementary material)
Anytime AND/OR Depth-first Search for Combinatorial Optimization. Lars Otten and Rina Dechter. In AI Communications Vol. 25(3), 2012.

Peer-Reviewed Publications

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]

Workshops

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.

Software

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.

Slightly 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.