Anima Anandkumar pioneered the research of finding global optimal in non-convex problems, a big pain point in machine learning. Our protagonist for this week's Techie Tuesdays, Anima is an academician who represents the best of both worlds--industry and academia. She has contributed significantly to major AI and ML projects at Amazon. This will be a treat for all machine learning enthusiasts. In my two hours of conversation with Anima Anandkumar, Principal Scientist at Amazon Web Services, I've had the most potent dose of technical knowledge ever injected. Not that I didn't expect it while talking to an ex-faculty of UC Irvine (soon to be an endowed professor at Caltech), known for her research on non-convex problems (in deep learning). Our Techie Tuesdays protagonist of the week, Anima has worked towards establishing a strong collaboration between academia and industry. She follows an unconventional style of teaching, the one she would have loved as a student.

Observable operator models (OOMs) and related models are one of the most important and powerful tools for modeling and analyzing stochastic systems. They exactly describe dynamics of finite-rank systems and can be efficiently and consistently estimated through spectral learning under the assumption of identically distributed data. In this paper, we investigate the properties of spectral learning without this assumption due to the requirements of analyzing large-time scale systems, and show that the equilibrium dynamics of a system can be extracted from nonequilibrium observation data by imposing an equilibrium constraint. In addition, we propose a binless extension of spectral learning for continuous data. In comparison with the other continuous-valued spectral algorithms, the binless algorithm can achieve consistent estimation of equilibrium dynamics with only linear complexity.

We propose a Bayesian nonparametric mixture model for prediction- and information extraction tasks with an efficient inference scheme. It models categorical-valued time series that exhibit dynamics from multiple underlying patterns (e.g. user behavior traces). We simplify the idea of capturing these patterns by hierarchical hidden Markov models (HHMMs) - and extend the existing approaches by the additional representation of structural information. Our empirical results are based on both synthetic- and real world data. They indicate that the results are easily interpretable, and that the model excels at segmentation and prediction performance: it successfully identifies the generating patterns and can be used for effective prediction of future observations.

Designing effective exploration-exploitation algorithms in Markov decision processes (MDPs) with large state-action spaces is the main challenge in reinforcement learning (RL). In fact, the learning performance degrades with the number of states and actions in the MDP. However, MDPs often exhibit a low-dimensional latent structure in practice, where a small hidden state is observable through a possibly large number of observations. In this paper, we study the setting of rich-observation Markov decision processes (\richmdp), where hidden states are mapped to observations through an injective mapping, so that an observation can be generated by only one hidden state. While this mapping is unknown a priori, we introduce a spectral decomposition method that consistently estimates how observations are clustered in the hidden states. The estimated clustering is then integrated into an optimistic algorithm for RL (UCRL), which operates on the smaller clustered space. The resulting algorithm proceeds through phases and we show that its per-step regret (i.e., the difference in cumulative reward between the algorithm and the optimal policy) decreases as more observations are clustered together and finally, matches the (ideal) performance of an RL algorithm running directly on the hidden MDP.

In late post-revolutionary France one man was tasked to map out the country. Gaspard de Prony, a mathematician and engineer, decided to approach the task by creating logarithmic and trigonometric tables. These tables, which would come to be known as Tables of de Prony, were destined to speed up the trigonometric calculations needed to complete these cartographic task. In handling the vast amounts of data, de Prony asked for help. His team was divided in three levels of hierarchy: besides a couple of highly skilled mathematicians, several mathematicians with less sophisticated skills, he also hired sixty to eighty hairdressers.

This paper introduces DeepBach, a graphical model aimed at modeling polyphonic music and specifically hymn-like pieces. We claim that, after being trained on the chorale harmonizations by Johann Sebastian Bach, our model is capable of generating highly convincing chorales in the style of Bach. DeepBach's strength comes from the use of pseudo-Gibbs sampling coupled with an adapted representation of musical data. This is in contrast with many automatic music composition approaches which tend to compose music sequentially. Our model is also steerable in the sense that a user can constrain the generation by imposing positional constraints such as notes, rhythms or cadences in the generated score. We also provide a plugin on top of the MuseScore music editor making the interaction with Deep-Bach easy to use.

Robots acting in human-scale environments must plan under uncertainty in large state-action spaces and face constantly changing reward functions as requirements and goals change. Planning under uncertainty in large state-action spaces requires hierarchical abstraction for efficient computation. We introduce a new hierarchical planning framework called Abstract Markov Decision Processes (AMDPs) that can plan in a fraction of the time needed for complex decision making in ordinary MDPs. AMDPs provide abstract states, actions, and transition dynamics in multiple layers above a base-level "flat" MDP . AMDPs decompose problems into a series of subtasks with both local reward and local transition functions used to create policies for subtasks. The resulting hierarchical planning method is independently optimal at each level of abstraction, and is recursively optimal when the local reward and transition functions are correct. We present empirical results showing significantly improved planning speed, while maintaining solution quality, in the Taxi domain and in a mobile-manipulation robotics problem. Furthermore, our approach allows specification of a decision-making model for a mobile-manipulation problem on a Turtlebot, spanning from low-level control actions operating on continuous variables all the way up through high-level object manipulation tasks.

Multi-agent systems in cluttered environments require path planning that not only prevents collisions with static obstacles, but also safely coordinates the motion of many agents. The challenge of multi-agent path finding becomes even more difficult when the agents experience uncertainty in their pose. In this work, we develop a multi-agent path planner that considers uncertainty, called uncertainty M* (UM*), which is based on a prior multi-agent path approach called M*. UM* plans a path through the belief space for each individual agent and then uses a strategy similar to M* that coordinates only agents that are "likely" to collide. This approach has the same scalability advantages as M*. We then introduce an extension called Permuted UM* (PUM*) that uses randomized restarts to enhance performance. We finish by presenting a belief space representation appropriate for multi-agent path planning with uncertainty and validate the performance of UM* and PUM* in simulation and mixed-reality experiments.

The deployment of robots in public environments is gaining more and more attention and interest both for the research opportunities and for the possibility of developing commercial applications over it. In these scenarios, proper definitions and implementations of human-robot interactions are crucial and the specific characteristics of the environment (in particular, the presence of untrained users) makes the task of defining and implementing effective interactions particularly challenging. In this paper, we describe a method and a fully implemented robotic system using conditional planning for generating and executing short-term interactions by a robot deployed in a public environment. To this end, the proposed method integrates and extends two components already successfully used for planning in robotics: ROSPlan and Petri Net Plans. The contributions of this paper are the problem definition of generating short-term interactions as a conditional planning problem and the description of a solution fully implemented on a real robot. The proposed method is based on the integration between a contingent planner in ROSPlan and the Petri Net Plans execution framework, and it has been tested in different scenarios where the robot interacted with hundreds of untrained users.

We address the problem of finding shortest paths in graphs where some edges have a prior probability of existence, and their existence can be verified during planning with time- consuming operations. Our work is motivated by real-world robot motion planning, where edge existence is often expensive to verify (typically involves time-consuming collision-checking between the robot and world models), but edge existence probabilities are readily available. The goal then, is to develop an anytime algorithm that can return good solutions quickly by somehow leveraging the existence probabilities, and continue to return better-quality solutions or provide tighter suboptimality bounds with more time. While our motivation is fast and high-quality motion planning for robots, this work presents two fundamental contributions applicable to generic graphs with probabilistic edges. They are: a) an algorithm for efficiently computing all relevant shortest paths in a graph with probabilistic edges, and as a by-product the expected shortest path cost, and b) an anytime algorithm for evaluating (verifying existence of) edges in a collection of paths, which is optimal in expectation under a chosen distribution of the algorithm interruption time. Finally, we provide a practical approach to integrate a) and b) in the context of robot motion planning and demonstrate significant improvements in success rate and planning time for a 11 degree-of-freedom mobile manipulation planning problem. We also conduct additional evaluations on a 2D grid navigation domain to study our algorithm’s behavior.