OpenRaiser/Intern-Atlas huggingface dataset:
Model-Based Inverse Reinforcement Learning from Visual Demonstrations
Venue: arXiv cs.RO 2021
Year: 2021

Scaling model-based inverse reinforcement learning (IRL) to real robotic manipulation tasks with unknown dynamics remains an open problem. The key challenges lie in learning good dynamics models, developing algorithms that scale to high-dimensional state-spaces and being able to learn from both visual and proprioceptive demonstrations. In this work, we present a gradient-based inverse reinforcement learning framework that utilizes a pre-trained visual dynamics model to learn cost functions when given only visual human demonstrations. The learned cost functions are then used to reproduce the demonstrated behavior via visual model predictive control. We evaluate our framework on hardware on two basic object manipulation tasks.
Poisoned classifiers are not only backdoored, they are fundamentally broken
Venue: arXiv cs.LG 2021
Year: 2021

Under a commonly-studied backdoor poisoning attack against classification models, an attacker adds a small trigger to a subset of the training data, such that the presence of this trigger at test time causes the classifier to always predict some target class. It is often implicitly assumed that the poisoned classifier is vulnerable exclusively to the adversary who possesses the trigger. In this paper, we show empirically that this view of backdoored classifiers is incorrect. We describe a new threat model for poisoned classifier, where one without knowledge of the original trigger, would want to control the poisoned classifier. Under this threat model, we propose a test-time, human-in-the-loop attack method to generate multiple effective alternative triggers without access to the initial backdoor and the training data. We construct these alternative triggers by first generating adversarial examples for a smoothed version of the classifier, created with a procedure called Denoised Smoothing, and then extracting colors or cropped portions of smoothed adversarial images with human interaction. We demonstrate the effectiveness of our attack through extensive experiments on high-resolution datasets: ImageNet and TrojAI. We also compare our approach to previous work on modeling trigger distributions and find that our method are more scalable and efficient in generating effective triggers. Last, we include a user study which demonstrates that our method allows users to easily determine the existence of such backdoors in existing poisoned classifiers. Thus, we argue that there is no such thing as a secret backdoor in poisoned classifiers: poisoning a classifier invites attacks not just by the party that possesses the trigger, but from anyone with access to the classifier.
CT-CPP: Coverage Path Planning for 3D Terrain Reconstruction Using Dynamic Coverage Trees
Venue: arXiv cs.RO 2021
Year: 2021

This letter addresses the 3D coverage path planning (CPP) problem for terrain reconstruction of unknown obstacle rich environments. Due to sensing limitations, the proposed method, called CT-CPP, performs layered scanning of the 3D region to collect terrain data, where the traveling sequence is optimized using the concept of a coverage tree (CT) with a TSP-inspired tree traversal strategy. The CT-CPP method is validated on a high-fidelity underwater simulator and the results are compared to an existing terrain following CPP method. The results show that CT-CPP yields significant reduction in trajectory length, energy consumption, and reconstruction error.
The efficacy of Neural Planning Metrics: A meta-analysis of PKL on nuScenes
Venue: arXiv cs.CV 2021
Year: 2021

A high-performing object detection system plays a crucial role in autonomous driving (AD). The performance, typically evaluated in terms of mean Average Precision, does not take into account orientation and distance of the actors in the scene, which are important for the safe AD. It also ignores environmental context. Recently, Philion et al. proposed a neural planning metric (PKL), based on the KL divergence of a planner's trajectory and the groundtruth route, to accommodate these requirements. In this paper, we use this neural planning metric to score all submissions of the nuScenes detection challenge and analyze the results. We find that while somewhat correlated with mAP, the PKL metric shows different behavior to increased traffic density, ego velocity, road curvature and intersections. Finally, we propose ideas to extend the neural planning metric.
Gray codes for Fibonacci q-decreasing words
Venue: arXiv cs.DM 2021
Year: 2021

An $n$-length binary word is $q$-decreasing, $q\geq 1$, if every of its length maximal factor of the form $0^a1^b$ satisfies $a=0$ or $q\cdot a > b$.We show constructively that these words are in bijection with binary words having no occurrences of $1^{q+1}$, and thus they are enumerated by the $(q+1)$-generalized Fibonacci numbers. We give some enumerative results and reveal similarities between $q$-decreasing words and binary words having no occurrences of $1^{q+1}$ in terms of frequency of $1$ bit. In the second part of our paper, we provide an efficient exhaustive generating algorithm for $q$-decreasing words in lexicographic order, for any $q\geq 1$, show the existence of 3-Gray codes and explain how a generating algorithm for these Gray codes can be obtained. Moreover, we give the construction of a more restrictive 1-Gray code for $1$-decreasing words, which in particular settles a conjecture stated recently in the context of interconnection networks by Eğecioğlu and Iršič.
Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
Venue: arXiv cs.LG 2021
Year: 2021

We provide a new convergence analysis of stochastic gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain. Under certain conditions on the target distribution, we prove that $\tilde O(d^4ε^{-2})$ stochastic gradient evaluations suffice to guarantee $ε$-sampling error in terms of the total variation distance, where $d$ is the problem dimension. This improves existing results on the convergence rate of SGLD (Raginsky et al., 2017; Xu et al., 2018). We further show that provided an additional Hessian Lipschitz condition on the log-density function, SGLD is guaranteed to achieve $ε$-sampling error within $\tilde O(d^{15/4}ε^{-3/2})$ stochastic gradient evaluations. Our proof technique provides a new way to study the convergence of Langevin-based algorithms and sheds some light on the design of fast stochastic gradient-based sampling algorithms.
Optimism in the Face of Adversity: Understanding and Improving Deep Learning through Adversarial Robustness
Venue: arXiv cs.LG 2021
Year: 2021

Driven by massive amounts of data and important advances in computational resources, new deep learning systems have achieved outstanding results in a large spectrum of applications. Nevertheless, our current theoretical understanding on the mathematical foundations of deep learning lags far behind its empirical success. Towards solving the vulnerability of neural networks, however, the field of adversarial robustness has recently become one of the main sources of explanations of our deep models. In this article, we provide an in-depth review of the field of adversarial robustness in deep learning, and give a self-contained introduction to its main notions. But, in contrast to the mainstream pessimistic perspective of adversarial robustness, we focus on the main positive aspects that it entails. We highlight the intuitive connection between adversarial examples and the geometry of deep neural networks, and eventually explore how the geometric study of adversarial examples can serve as a powerful tool to understand deep learning. Furthermore, we demonstrate the broad applicability of adversarial robustness, providing an overview of the main emerging applications of adversarial robustness beyond security. The goal of this article is to provide readers with a set of new perspectives to understand deep learning, and to supply them with intuitive tools and insights on how to use adversarial robustness to improve it.
SPA: Stochastic Probability Adjustment for System Balance of Unsupervised SNNs
Venue: arXiv cs.NE 2021
Year: 2021

Spiking neural networks (SNNs) receive widespread attention because of their low-power hardware characteristic and brain-like signal response mechanism, but currently, the performance of SNNs is still behind Artificial Neural Networks (ANNs). We build an information theory-inspired system called Stochastic Probability Adjustment (SPA) system to reduce this gap. The SPA maps the synapses and neurons of SNNs into a probability space where a neuron and all connected pre-synapses are represented by a cluster. The movement of synaptic transmitter between different clusters is modeled as a Brownian-like stochastic process in which the transmitter distribution is adaptive at different firing phases. We experimented with a wide range of existing unsupervised SNN architectures and achieved consistent performance improvements. The improvements in classification accuracy have reached 1.99% and 6.29% on the MNIST and EMNIST datasets respectively.
A Unified Approach for Autonomous Volumetric Exploration of Large Scale Environments under Severe Odometry Drift
Venue: arXiv cs.RO 2021
Year: 2021

Exploration is a fundamental problem in robot autonomy. A major limitation, however, is that during exploration robots oftentimes have to rely on on-board systems alone for state estimation, accumulating significant drift over time in large environments. Drift can be detrimental to robot safety and exploration performance. In this work, a submap-based, multi-layer approach for both mapping and planning is proposed to enable safe and efficient volumetric exploration of large scale environments despite odometry drift. The central idea of our approach combines local (temporally and spatially) and global mapping to guarantee safety and efficiency. Similarly, our planning approach leverages the presented map to compute global volumetric frontiers in a changing global map and utilizes the nature of exploration dealing with partial information for efficient local and global planning. The presented system is thoroughly evaluated and shown to outperform state of the art methods even under drift-free conditions. Our system, termed GLoca}, will be made available open source.
Scalable Statistical Root Cause Analysis on App Telemetry
Venue: arXiv cs.SE 2021
Year: 2021

Despite engineering workflows that aim to prevent buggy code from being deployed, bugs still make their way into the Facebook app. When symptoms of these bugs, such as user submitted reports and automatically captured crashes, are reported, finding their root causes is an important step in resolving them. However, at Facebook's scale of billions of users, a single bug can manifest as several different symptoms according to the various user and execution environments in which the software is deployed. Root cause analysis (RCA) therefore requires tedious manual investigation and domain expertise to extract out common patterns that are observed in groups of reports and use them for debugging. We propose Minesweeper, a technique for RCA that moves towards automatically identifying the root cause of bugs from their symptoms. The method is based on two key aspects: (i) a scalable algorithm to efficiently mine patterns from telemetric information that is collected along with the reports, and (ii) statistical notions of precision and recall of patterns that help point towards root causes. We evaluate Minesweeper's scalability and effectiveness in finding root causes from symptoms on real world bug and crash reports from Facebook's apps. Our evaluation demonstrates that Minesweeper can perform RCA for tens of thousands of reports in less than 3 minutes, and is more than 85% accurate in identifying the root cause of regressions.
Primitive Recursive Ordered Fields and Some Applications
Venue: arXiv cs.CC 2021
Year: 2021

We establish primitive recursive versions of some known facts about computable ordered fields of reals and computable reals, and then apply them to proving primitive recursiveness of some natural problems in linear algebra and analysis. In particular, we find a partial primitive recursive analogue of Ershov-Madison's theorem about real closures of computable ordered fields, relate the corresponding fields to the primitive recursive reals, give sufficient conditions for primitive recursive root-finding, computing normal forms of matrices, and computing solution operators of some linear systems of PDE.
Learn to Navigate Maplessly with Varied LiDAR Configurations: A Support Point-Based Approach
Venue: arXiv cs.RO 2021
Year: 2021

Deep reinforcement learning (DRL) demonstrates great potential in mapless navigation domain. However, such a navigation model is normally restricted to a fixed configuration of the range sensor because its input format is fixed. In this paper, we propose a DRL model that can address range data obtained from different range sensors with different installation positions. Our model first extracts the goal-directed features from each obstacle point. Subsequently, it chooses global obstacle features from all point-feature candidates and uses these features for the final decision. As only a few points are used to support the final decision, we refer to these points as support points and our approach as support point-based navigation (SPN). Our model can handle data from different LiDAR setups and demonstrates good performance in simulation and real-world experiments. Moreover, it shows great potential in crowded scenarios with small obstacles when using a high-resolution LiDAR.
A Faster Parameterized Algorithm for Temporal Matching
Venue: arXiv cs.DS 2021
Year: 2021

A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A $Δ$-temporal matching $M$ is a set of time edges $(e,t)$ (an edge $e$ paired up with a point in time $t$) such that for all distinct time edges $(e,t),(e',t') \in M$ we have that $e$ and $e'$ do not share an endpoint, or the time-labels $t$ and $t'$ are at least $Δ$ time units apart. Mertzios et al. [STACS '20] provided a $2^{O(Δν)}\cdot |{\mathcal G}|^{O(1)}$-time algorithm to compute the maximum size of a $Δ$-temporal matching in a temporal graph $\mathcal G$, where $|\mathcal G|$ denotes the size of $\mathcal G$, and $ν$ is the $Δ$-vertex cover number of $\mathcal G$. The $Δ$-vertex cover number is the minimum number $ν$ such that the classical vertex cover number of the union of any $Δ$ consecutive layers of the temporal graph is upper-bounded by $ν$. We show an improved algorithm to compute a $Δ$-temporal matching of maximum size with a running time of $Δ^{O(ν)}\cdot |\mathcal G|$ and hence provide an exponential speedup in terms of $Δ$.
Composite Enclaves: Towards Disaggregated Trusted Execution
Venue: arXiv cs.CR 2021
Year: 2021

The ever-rising computation demand is forcing the move from the CPU to heterogeneous specialized hardware, which is readily available across modern datacenters through disaggregated infrastructure. On the other hand, trusted execution environments (TEEs), one of the most promising recent developments in hardware security, can only protect code confined in the CPU, limiting TEEs' potential and applicability to a handful of applications. We observe that the TEEs' hardware trusted computing base (TCB) is fixed at design time, which in practice leads to using untrusted software to employ peripherals in TEEs. Based on this observation, we propose \emph{composite enclaves} with a configurable hardware and software TCB, allowing enclaves access to multiple computing and IO resources. Finally, we present two case studies of composite enclaves: i) an FPGA platform based on RISC-V Keystone connected to emulated peripherals and sensors, and ii) a large-scale accelerator. These case studies showcase a flexible but small TCB (2.5 KLoC for IO peripherals and drivers), with a low-performance overhead (only around 220 additional cycles for a context switch), thus demonstrating the feasibility of our approach and showing that it can work with a wide range of specialized hardware.
Regret-optimal control in dynamic environments
Venue: arXiv cs.LG 2021
Year: 2021

We consider control in linear time-varying dynamical systems from the perspective of regret minimization. Unlike most prior work in this area, we focus on the problem of designing an online controller which minimizes regret against the best dynamic sequence of control actions selected in hindsight (dynamic regret), instead of the best fixed controller in some specific class of controllers (static regret). This formulation is attractive when the environment changes over time and no single controller achieves good performance over the entire time horizon. We derive the state-space structure of the regret-optimal controller via a novel reduction to $H_{\infty}$ control and present a tight data-dependent bound on its regret in terms of the energy of the disturbance. Our results easily extend to the model-predictive setting where the controller can anticipate future disturbances and to settings where the controller only affects the system dynamics after a fixed delay. We present numerical experiments which show that our regret-optimal controller interpolates between the performance of the $H_2$-optimal and $H_{\infty}$-optimal controllers across stochastic and adversarial environments.
SCOP: Scientific Control for Reliable Neural Network Pruning
Venue: arXiv cs.CV 2021
Year: 2021

This paper proposes a reliable neural network pruning algorithm by setting up a scientific control. Existing pruning methods have developed various hypotheses to approximate the importance of filters to the network and then execute filter pruning accordingly. To increase the reliability of the results, we prefer to have a more rigorous research design by including a scientific control group as an essential part to minimize the effect of all factors except the association between the filter and expected network output. Acting as a control group, knockoff feature is generated to mimic the feature map produced by the network filter, but they are conditionally independent of the example label given the real feature map. We theoretically suggest that the knockoff condition can be approximately preserved given the information propagation of network layers. Besides the real feature map on an intermediate layer, the corresponding knockoff feature is brought in as another auxiliary input signal for the subsequent layers. Redundant filters can be discovered in the adversarial process of different features. Through experiments, we demonstrate the superiority of the proposed algorithm over state-of-the-art methods. For example, our method can reduce 57.8% parameters and 60.2% FLOPs of ResNet-101 with only 0.01% top-1 accuracy loss on ImageNet. The code is available at https://github.com/huawei-noah/Pruning/tree/master/SCOP_NeurIPS2020.
STN4DST: A Scalable Dialogue State Tracking based on Slot Tagging Navigation
Venue: arXiv cs.CL 2021
Year: 2021

Scalability for handling unknown slot values is a important problem in dialogue state tracking (DST). As far as we know, previous scalable DST approaches generally rely on either the candidate generation from slot tagging output or the span extraction in dialogue context. However, the candidate generation based DST often suffers from error propagation due to its pipelined two-stage process; meanwhile span extraction based DST has the risk of generating invalid spans in the lack of semantic constraints between start and end position pointers. To tackle the above drawbacks, in this paper, we propose a novel scalable dialogue state tracking method based on slot tagging navigation, which implements an end-to-end single-step pointer to locate and extract slot value quickly and accurately by the joint learning of slot tagging and slot value position prediction in the dialogue context, especially for unknown slot values. Extensive experiments over several benchmark datasets show that the proposed model performs better than state-of-the-art baselines greatly.
Incorporating Interpretable Output Constraints in Bayesian Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Domains where supervised models are deployed often come with task-specific constraints, such as prior expert knowledge on the ground-truth function, or desiderata like safety and fairness. We introduce a novel probabilistic framework for reasoning with such constraints and formulate a prior that enables us to effectively incorporate them into Bayesian neural networks (BNNs), including a variant that can be amortized over tasks. The resulting Output-Constrained BNN (OC-BNN) is fully consistent with the Bayesian framework for uncertainty quantification and is amenable to black-box inference. Unlike typical BNN inference in uninterpretable parameter space, OC-BNNs widen the range of functional knowledge that can be incorporated, especially for model users without expertise in machine learning. We demonstrate the efficacy of OC-BNNs on real-world datasets, spanning multiple domains such as healthcare, criminal justice, and credit scoring.
Unsupervised Multiple Choices Question Answering: Start Learning from Basic Knowledge
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we study the possibility of almost unsupervised Multiple Choices Question Answering (MCQA). Starting from very basic knowledge, MCQA model knows that some choices have higher probabilities of being correct than the others. The information, though very noisy, guides the training of an MCQA model. The proposed method is shown to outperform the baseline approaches on RACE and even comparable with some supervised learning approaches on MC500.
Learning Spring Mass Locomotion: Guiding Policies with a Reduced-Order Model
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we describe an approach to achieve dynamic legged locomotion on physical robots which combines existing methods for control with reinforcement learning. Specifically, our goal is a control hierarchy in which highest-level behaviors are planned through reduced-order models, which describe the fundamental physics of legged locomotion, and lower level controllers utilize a learned policy that can bridge the gap between the idealized, simple model and the complex, full order robot. The high-level planner can use a model of the environment and be task specific, while the low-level learned controller can execute a wide range of motions so that it applies to many different tasks. In this letter we describe this learned dynamic walking controller and show that a range of walking motions from reduced-order models can be used as the command and primary training signal for learned policies. The resulting policies do not attempt to naively track the motion (as a traditional trajectory tracking controller would) but instead balance immediate motion tracking with long term stability. The resulting controller is demonstrated on a human scale, unconstrained, untethered bipedal robot at speeds up to 1.2 m/s. This letter builds the foundation of a generic, dynamic learned walking controller that can be applied to many different tasks.