Lars Otten, UC Irvine

Lars Otten

Position:	Graduate student
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 the School of Information and Computer Sciences at UC Irvine since the fall of 2006.

Research – Teaching – Personal – Publications – Software

Research

My area of concentration is artificial intelligence in general and graphical model inference in particular, where I am trying to exploit structure in various contexts. The reasoning tasks I deal with comprise constraint satisfaction and optimization problems as well as queries over Bayesian and Markov networks (e.g., P(e), MPE, belief updating).

I have previously investigated different complexity measures for reasoning problems represented as graphical models. Specifically, I worked on instance-based complexity bounds in the presence of determinism, which can be used to guide parameter selection for the underlying algorithm.

More recently, my focus has shifted a bit, intersecting AI with parallel and distributed computing: My current research circles around parallelization strategies for established state-of-the-art algorithms in the context of graphical model reasoning. At this point, the focus lies on computational grid environments, but other systems are under consideration for future research as well.

Applications are manifold, but one driving factor in our experimental evaluation are haplotyping and linkage problems from human genetic analysis. These can be modeled as Bayesian networks and are thus susceptible to our highly advanced methods like AND/OR graph search. With inherently exponential complexity, however, and evergrowing sets of available data, these kinds of problems make it very natural to exploit vast computational resources in parallel.

I've implemented a first prototype system on a small local computational grid and made it accessible through a web site interface. It uses our algorithms for finding the most likely haplotypes in general pedigrees:

SuperHaplo@UCI

At this point the system is not open to the public, please contact me directly if you are interested.

My implementation of AND/OR Branch and Bound can be downloaded below; our research group also maintains a website where we make available some of the algorithms we developed: http://graphmod.ics.uci.edu/

After being involved in organizing the UAI'08 Probabilistic Inference Evaluation, I participated in the UAI'10 Approximate Inference Challenge, where my solver placed third in the MPE category.

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

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.

Peer-Reviewed Publications

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

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.

Precompiled daoopt-0.99.5a (32 bit static Linux binary).
Full source release temporarily unavailable, check back soon.

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.