Education
Open Problem: Tight Online Confidence Intervals for RKHS Elements
Vakili, Sattar, Scarlett, Jonathan, Javidi, Tara
Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel based bandit and reinforcement learning problems utilize confidence intervals applicable to the elements of a reproducing kernel Hilbert space (RKHS). However, the existing confidence bounds do not appear to be tight, resulting in suboptimal regret bounds. In fact, the existing regret bounds for several kernelized bandit algorithms (e.g., GP-UCB, GP-TS, and their variants) may fail to even be sublinear. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof, and the main challenge seems to stem from the online (sequential) nature of the observation points.
Learning to Ground Multi-Agent Communication with Autoencoders
Lin, Toru, Huh, Minyoung, Stauffer, Chris, Lim, Ser-Nam, Isola, Phillip
Communication requires having a common language, a lingua franca, between agents. This language could emerge via a consensus process, but it may require many generations of trial and error. Alternatively, the lingua franca can be given by the environment, where agents ground their language in representations of the observed world. We demonstrate a simple way to ground language in learned representations, which facilitates decentralized multi-agent communication and coordination. We find that a standard representation learning algorithm -- autoencoding -- is sufficient for arriving at a grounded common language. When agents broadcast these representations, they learn to understand and respond to each other's utterances and achieve surprisingly strong task performance across a variety of multi-agent communication environments.
Wasserstein Distance Maximizing Intrinsic Control
Durugkar, Ishan, Hansen, Steven, Spencer, Stephen, Mnih, Volodymyr
Mutual information based objectives have shown some success in learning skills that reach a diverse set of states in this setting. These objectives include a KL-divergence term, which is maximized by visiting distinct states even if those states are not far apart in the MDP. This paper presents an approach that rewards the agent for learning skills that maximize the Wasserstein distance of their state visitation from the start state of the skill. It shows that such an objective leads to a policy that covers more distance in the MDP than diversity based objectives, and validates the results on a variety of Atari environments.
Cooperative Deep $Q$-learning Framework for Environments Providing Image Feedback
Raghavan, Krishnan, Narayanan, Vignesh, Sarangapani, Jagannathan
In this paper, we address two key challenges in deep reinforcement learning setting, sample inefficiency and slow learning, with a dual NN-driven learning approach. In the proposed approach, we use two deep NNs with independent initialization to robustly approximate the action-value function in the presence of image inputs. In particular, we develop a temporal difference (TD) error-driven learning approach, where we introduce a set of linear transformations of the TD error to directly update the parameters of each layer in the deep NN. We demonstrate theoretically that the cost minimized by the error-driven learning (EDL) regime is an approximation of the empirical cost and the approximation error reduces as learning progresses, irrespective of the size of the network. Using simulation analysis, we show that the proposed methods enables faster learning and convergence and requires reduced buffer size (thereby increasing the sample efficiency).
An Adaptable Approach to Learn Realistic Legged Locomotion without Examples
Apraez, Daniel Felipe Ordoñez, Agudo, Antonio, Moreno-Noguer, Francesc, Martin, Mario
Learning controllers that reproduce legged locomotion in nature have been a long-time goal in robotics and computer graphics. While yielding promising results, recent approaches are not yet flexible enough to be applicable to legged systems of different morphologies. This is partly because they often rely on precise motion capture references or elaborate learning environments that ensure the naturality of the emergent locomotion gaits but prevent generalization. This work proposes a generic approach for ensuring realism in locomotion by guiding the learning process with the spring-loaded inverted pendulum model as a reference. Leveraging on the exploration capacities of Reinforcement Learning (RL), we learn a control policy that fills in the information gap between the template model and full-body dynamics required to maintain stable and periodic locomotion. The proposed approach can be applied to robots of different sizes and morphologies and adapted to any RL technique and control architecture. We present experimental results showing that even in a model-free setup and with a simple reactive control architecture, the learned policies can generate realistic and energy-efficient locomotion gaits for a bipedal and a quadrupedal robot. And most importantly, this is achieved without using motion capture, strong constraints in the dynamics or kinematics of the robot, nor prescribing limb coordination. We provide supplemental videos for qualitative analysis of the naturality of the learned gaits.
SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs
Ren, Hongyu, Dai, Hanjun, Dai, Bo, Chen, Xinyun, Zhou, Denny, Leskovec, Jure, Schuurmans, Dale
Knowledge graphs (KGs) capture knowledge in the form of head--relation--tail triples and are a crucial component in many AI systems. There are two important reasoning tasks on KGs: (1) single-hop knowledge graph completion, which involves predicting individual links in the KG; and (2), multi-hop reasoning, where the goal is to predict which KG entities satisfy a given logical query. Embedding-based methods solve both tasks by first computing an embedding for each entity and relation, then using them to form predictions. However, existing scalable KG embedding frameworks only support single-hop knowledge graph completion and cannot be applied to the more challenging multi-hop reasoning task. Here we present Scalable Multi-hOp REasoning (SMORE), the first general framework for both single-hop and multi-hop reasoning in KGs. Using a single machine SMORE can perform multi-hop reasoning in Freebase KG (86M entities, 338M edges), which is 1,500x larger than previously considered KGs. The key to SMORE's runtime performance is a novel bidirectional rejection sampling that achieves a square root reduction of the complexity of online training data generation. Furthermore, SMORE exploits asynchronous scheduling, overlapping CPU-based data sampling, GPU-based embedding computation, and frequent CPU--GPU IO. SMORE increases throughput (i.e., training speed) over prior multi-hop KG frameworks by 2.2x with minimal GPU memory requirements (2GB for training 400-dim embeddings on 86M-node Freebase) and achieves near linear speed-up with the number of GPUs. Moreover, on the simpler single-hop knowledge graph completion task SMORE achieves comparable or even better runtime performance to state-of-the-art frameworks on both single GPU and multi-GPU settings.
Colossal-AI: A Unified Deep Learning System For Large-Scale Parallel Training
Bian, Zhengda, Liu, Hongxin, Wang, Boxiang, Huang, Haichen, Li, Yongbin, Wang, Chuanrui, Cui, Fan, You, Yang
The Transformer architecture has improved the performance of deep learning models in domains such as Computer Vision and Natural Language Processing. Together with better performance come larger model sizes. This imposes challenges to the memory wall of the current accelerator hardware such as GPU. It is never ideal to train large models such as Vision Transformer, BERT, and GPT on a single GPU or a single machine. There is an urgent demand to train models in a distributed environment. However, distributed training, especially model parallelism, often requires domain expertise in computer systems and architecture. It remains a challenge for AI researchers to implement complex distributed training solutions for their models. In this paper, we introduce Colossal-AI, which is a unified parallel training system designed to seamlessly integrate different paradigms of parallelization techniques including data parallelism, pipeline parallelism, multiple tensor parallelism, and sequence parallelism. Colossal-AI aims to support the AI community to write distributed models in the same way as how they write models normally. This allows them to focus on developing the model architecture and separates the concerns of distributed training from the development process. The documentations can be found at https://www.colossalai.org and the source code can be found at https://github.com/hpcaitech/ColossalAI.
Pamela McCorduck's Contributions to the Birth of AI Continued Through Her Generosity - News - Carnegie Mellon University
As scientists laid the foundations of artificial intelligence, Pamela McCorduck was there. McCorduck, an author who wrote some of the first novels and histories about AI and was a generous friend of CMU, died Oct. 18. McCorduck described herself as an eyewitness to the birth and growth of AI. She was possibly best known for her 1979 book, "Machines Who Think," which chronicles the history of AI from the dreams and nightmares of ancient poets and prophets to the scientific discoveries of the 20th century. The novel contains the famous quote, "Artificial intelligence began with the ancient wish to forge the gods."
Vector Calculus for Machine Learning
To keep this post as engaging and entertaining as possible I will first introduce a brief history of Calculus and why I think it is so cool. Then, we will move on to reviewing fundamental concepts of your high school calculus such as derivative rules. Next, we will get our feet wet with vectors and matrices to make sure you are comfortable with these mathematical objects before covering partial and vector derivatives. Finally, I will conclude this post with the concept of a gradient, the intuition behind optimization with Gradient Descent and a cool implementation of calculus with Python leveraging the library SimPy. Feel free to skip any sections you like if you are comfortable with such topics. At the core, Calculus is just a very special way of thinking about large problems by splitting them into several, smaller, problems.