(With: Balaraman Ravindran)

Short abstract: Markov Decision Process (MDP) homomorphisms map states and actions from one MDP to another, providing a basis for the transfer of learning, and MDP minimisation. Homomorphisms in the discrete MDP setting have been comprehensively studied; only recently has work been done to define homomorphisms in continuous or partially observable domains. The objective of this work is to find homomorphisms between continuous and/or partially observable MDPs, in both an exact and approximate manner. More...

(With: Balaraman Ravindran)

Short abstract: The correlated topic model, proposed by Blei et. al, allows the modelling of correlated topics. However, due to the non-conjugacy of the model, the inference procedure is expensive, and complicated. We collapse the model (in a sense) by using the MAP estimate of hidden parameters, instead of marginalising over them. This allows us to use Gibbs sampling, and a far simpler Variational Bayes (VB) inference procedure, both of which can be easily parallelised. More...

(With: Gaurav Raina, Ramya Korlakai Vinayak)

Short abstract: Biological systems are ripe with phenomenon occurring across various timescales, yet conventional system design principles steer us away from the very phenomena that make biology interesting. It is not obvious that conventional design wisdom applies in this setting. We shed some light on the topic through the study of two of the simplest quadratic population models with two distinct timescales. We show that they capture the range of phenomenon from fixed points, to limit cycles, to chaos, and analytically characterise the same using Hopf bifurcation theory. We comment on the qualitative differences between the two models, and the resulting implications to control theory. More...

(With: Balaraman Ravindran, Prateek Gaur) Will appear at AAMAS 2012

Short abstract: Reinforcement learning provides a very natural framework to model how an agent learns to perform a task as it interacts with an environment. Within the field, there are several approaches to reuse solutions to certain tasks while solving a new one. However, there is no consensus on which tasks the agent should remember solutions for. We propose a simple algorithm inspired by small world networks to learn subtasks while solving a task that requires virtually no information of the environment. Additionally, we show that the subtasks we learn can be easily composed by the agent to solve any other task; more formally, we prove that any task can be solved using only a logarithmic combination of these subtasks and primitive actions. Experimental results show that the subtasks we generate outperform other popular subtask generation schemes on standard domains. More...

(With: Aditya Nori, Akash Lal, Sriram Rajamani)

Abstract: Statistical relational learning consists of inferring new relations from an existing data corpus using probabilistic formulas as specifications. We advance the state-of-the-art in relational learning significantly using techniques developed in program verification. In particular, our technique efficiently deals with axioms which are probabilistic formulas with probability 0 or 1. Our technique is inspired by the popular Counterexample Guided Abstraction Refinement (CEGAR) scheme, which is widely used in software model checking and theorem proving. Techniques such as generalization used for accelerating convergence of CEGAR in verification have counterparts in CEGAR for relational inference. We also present an implementation of our algorithm in a tool SOFT-CEGAR. We empirically compare our approach to state-of-the-art statistical relational learning approaches such as TUFFY and ALCHEMY over four real-world applications. We find that SOFT-CEGAR significantly outperforms these approaches both in terms of runtime and quality of results. More...

(With: Kapil Vasawani)

Short Abstract: As the size and complexity of applications increase, there is a need for tools that allow programmers to efficiently debug large programs. We experimented with the statistical model of Holmes, which used path profiles from test cases to localise root causes of bugs. We were able to decrease the false positive rate by using versioning information. We also tried to address complications arising from multiple bugs by using clustering the test cases.

(With: Anshul Rai, Ranjita Bhagwan, Sriram Rajamani, George Varghese)

Abstract: Bridging the abstraction gap between policy and configuration is a central problem in network management. Be it the problem of assigning VMs to hosts in a data center, or configuring VLANs and ACLs in enterprise networks, network management problems often involve combinatorial optimization. We propose using Satisfiability Modulo Theories (SMT) solvers to solve combinatorial optimization problems in network management. More...

Abstract: There are several sources of information about buggy programs that can be used to aid the automated debugging of programs, ranging from the path coverage statistics (Holmes), concolic execution (DART and CUTE) to data invariants (Daikon). These methods vary in the amount of information they provide about the program, as well as the amount of time and resources they require to obtain it.

Could we devise a mechanism to quickly determine what method to be used to determine the root cause of the problem in the most most optimal fashion given the costs and returns?

Abstract: Genetic algorithms do not maintain a “global” picture, thus making it hard to generate free instances adhering to a structure, unless this is encoded in the representation of the population. Nondeterministic hierarchical planning could be used to impose a loose structure, directing randomness by specifying goals that must be achieved, and constructing evaluation functions to grow a population that meets these goals. This could lead to results that are structured, yet “creative”. Perhaps the plans themselves could evolve.