OpenRaiser/Intern-Atlas huggingface dataset:
All-in-One: A DRL-based Control Switch Combining State-of-the-art Navigation Planners
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous navigation of mobile robots is an essential aspect in use cases such as delivery, assistance or logistics. Although traditional planning methods are well integrated into existing navigation systems, they struggle in highly dynamic environments. On the other hand, Deep-Reinforcement-Learning-based methods show superior performance in dynamic obstacle avoidance but are not suitable for long-range navigation and struggle with local minima. In this paper, we propose a Deep-Reinforcement-Learning-based control switch, which has the ability to select between different planning paradigms based solely on sensor data observations. Therefore, we develop an interface to efficiently operate multiple model-based, as well as learning-based local planners and integrate a variety of state-of-the-art planners to be selected by the control switch. Subsequently, we evaluate our approach against each planner individually and found improvements in navigation performance especially for highly dynamic scenarios. Our planner was able to prefer learning-based approaches in situations with a high number of obstacles while relying on the traditional model-based planners in long corridors or empty spaces.
Bayesian Inference of a Social Graph with Trace Feasibility Guarantees
Venue: arXiv cs.SI 2021
Year: 2021

Network inference is the process of deciding what is the true unknown graph underlying a set of interactions between nodes. There is a vast literature on the subject, but most known methods have an important drawback: the inferred graph is not guaranteed to explain every interaction from the input trace. We consider this an important issue since such inferred graph cannot be used as input for applications that require a reliable estimate of the true graph. On the other hand, a graph having trace feasibility guarantees can help us better understand the true (hidden) interactions that may have taken place between nodes of interest. The inference of such graph is the goal of this paper. Firstly, given an activity log from a social network, we introduce a set of constraints that take into consideration all the hidden paths that are possible between the nodes of the trace, given their timestamps of interaction. Then, we develop a nontrivial modification of the Expectation-Maximization algorithm by Newman [1], that we call Constrained-EM, which incorporates the constraints and a set of auxiliary variables into the inference process to guide it towards the feasibility of the trace. Experimental results on real-world data from Twitter confirm that Constrained-EM generates a posterior distribution of graphs that explains all the events observed in the trace while presenting the desired properties of a scale-free, small-world graph. Our method also outperforms established methods in terms of feasibility and quality of the inferred graph.
Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Cooperative multi-agent reinforcement learning is a decentralized paradigm in sequential decision making where agents distributed over a network iteratively collaborate with neighbors to maximize global (network-wide) notions of rewards. Exact computations typically involve a complexity that scales exponentially with the number of agents. To address this curse of dimensionality, we design a scalable algorithm based on the Natural Policy Gradient framework that uses local information and only requires agents to communicate with neighbors within a certain range. Under standard assumptions on the spatial decay of correlations for the transition dynamics of the underlying Markov process and the localized learning policy, we show that our algorithm converges to the globally optimal policy with a dimension-free statistical and computational complexity, incurring a localization error that does not depend on the number of agents and converges to zero exponentially fast as a function of the range of communication.
Rosita++: Automatic Higher-Order Leakage Elimination from Cryptographic Code
Venue: arXiv cs.CR 2021
Year: 2021

Side-channel attacks are a major threat to the security of cryptographic implementations, particularly for small devices that are under the physical control of the adversary. While several strategies for protecting against side-channel attacks exist, these often fail in practice due to unintended interactions between values deep within the CPU. To detect and protect from side-channel attacks, several automated tools have recently been proposed; one of their common limitations is that they only support first-order leakage. In this work, we present the first automated tool for detecting and eliminating higher-order leakage from cryptographic implementations. Rosita++ proposes statistical and software-based tools to allow high-performance higher-order leakage detection. It then uses the code rewrite engine of Rosita (Shelton et al. NDSS 2021) to eliminate detected leakage. For the sake of practicality we evaluate Rosita++ against second and third order leakage, but our framework is not restricted to only these orders. We evaluate Rosita++ against second-order leakage with three-share implementations of two ciphers, PRESENT and Xoodoo, and with the second-order Boolean-to-arithmetic masking, a core building block of masked implementations of many cryptographic primitives, including SHA-2, ChaCha and Blake. We show effective second-order leakage elimination at a performance cost of 36% for Xoodoo, 189% for PRESENT, and 29% for the Boolean-to-arithmetic masking. For third-order analysis, we evaluate Rosita++ against the third-order leakage using a four-share synthetic example that corresponds to typical four-share processing. Rosita++ correctly identified this leakage and applied code fixes.
Dense Contrastive Visual-Linguistic Pretraining
Venue: arXiv cs.CV 2021
Year: 2021

Inspired by the success of BERT, several multimodal representation learning approaches have been proposed that jointly represent image and text. These approaches achieve superior performance by capturing high-level semantic information from large-scale multimodal pretraining. In particular, LXMERT and UNITER adopt visual region feature regression and label classification as pretext tasks. However, they tend to suffer from the problems of noisy labels and sparse semantic annotations, based on the visual features having been pretrained on a crowdsourced dataset with limited and inconsistent semantic labeling. To overcome these issues, we propose unbiased Dense Contrastive Visual-Linguistic Pretraining (DCVLP), which replaces the region regression and classification with cross-modality region contrastive learning that requires no annotations. Two data augmentation strategies (Mask Perturbation and Intra-/Inter-Adversarial Perturbation) are developed to improve the quality of negative samples used in contrastive learning. Overall, DCVLP allows cross-modality dense region contrastive learning in a self-supervised setting independent of any object annotations. We compare our method against prior visual-linguistic pretraining frameworks to validate the superiority of dense contrastive learning on multimodal representation learning.
Edge but not Least: Cross-View Graph Pooling
Venue: arXiv cs.LG 2021
Year: 2021

Graph neural networks have emerged as a powerful model for graph representation learning to undertake graph-level prediction tasks. Various graph pooling methods have been developed to coarsen an input graph into a succinct graph-level representation through aggregating node embeddings obtained via graph convolution. However, most graph pooling methods are heavily node-centric and are unable to fully leverage the crucial information contained in global graph structure. This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. The proposed Co-Pooling fuses pooled representations learnt from both node view and edge view. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations. Co-Pooling has the advantage of handling various graphs with different types of node attributes. Extensive experiments on a total of 15 graph benchmark datasets validate the effectiveness of our proposed method, demonstrating its superior performance over state-of-the-art pooling methods on both graph classification and graph regression tasks.
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts
Venue: arXiv cs.LG 2021
Year: 2021

Training large-scale mixture of experts models efficiently on modern hardware requires assigning datapoints in a batch to different experts, each with a limited capacity. Recently proposed assignment procedures lack a probabilistic interpretation and use biased estimators for training. As an alternative, we propose two unbiased estimators based on principled stochastic assignment procedures: one that skips datapoints which exceed expert capacity, and one that samples perfectly balanced assignments using an extension of the Gumbel-Matching distribution [29]. Both estimators are unbiased, as they correct for the used sampling procedure. On a toy experiment, we find the `skip'-estimator is more effective than the balanced sampling one, and both are more robust in solving the task than biased alternatives.
Robustness and Sensitivity of BERT Models Predicting Alzheimer's Disease from Text
Venue: arXiv cs.CL 2021
Year: 2021

Understanding robustness and sensitivity of BERT models predicting Alzheimer's disease from text is important for both developing better classification models and for understanding their capabilities and limitations. In this paper, we analyze how a controlled amount of desired and undesired text alterations impacts performance of BERT. We show that BERT is robust to natural linguistic variations in text. On the other hand, we show that BERT is not sensitive to removing clinically important information from text.
Broccoli: Bug localization with the help of text search engines
Venue: arXiv cs.SE 2021
Year: 2021

Bug localization is a tedious activity in the bug fixing process in which a software developer tries to locate bugs in the source code described in a bug report. Since this process is time-consuming and requires additional knowledge about the software project, information retrieval techniques can aid the bug localization process. In this paper, we investigate if normal text search engines can improve existing bug localization approaches. In a case study, we evaluate the performance of our search engine approach Broccoli against seven state-of-the-art bug localization algorithms on 82 open source projects in two data sets. Our results show that including a search engine can increase the performance of the bug localization and that it is a useful extension to existing approaches. As part of our analysis we also exposed a flaw in a commonly used benchmark strategy, i.e., that files of a single release are considered. To increase the number of detectable files, we mitigate this flaw by considering the state of the software repository at the time of the bug report. Our results show that using single releases may lead to an underestimation of the the prediction performance.
Learning to maximize global influence from local observations
Venue: arXiv cs.LG 2021
Year: 2021

We study a family online influence maximization problems where in a sequence of rounds $t=1,\ldots,T$, a decision maker selects one from a large number of agents with the goal of maximizing influence. Upon choosing an agent, the decision maker shares a piece of information with the agent, which information then spreads in an unobserved network over which the agents communicate. The goal of the decision maker is to select the sequence of agents in a way that the total number of influenced nodes in the network. In this work, we consider a scenario where the networks are generated independently for each $t$ according to some fixed but unknown distribution, so that the set of influenced nodes corresponds to the connected component of the random graph containing the vertex corresponding to the selected agent. Furthermore, we assume that the decision maker only has access to limited feedback: instead of making the unrealistic assumption that the entire network is observable, we suppose that the available feedback is generated based on a small neighborhood of the selected vertex. Our results show that such partial local observations can be sufficient for maximizing global influence. We model the underlying random graph as a sparse inhomogeneous Erdős--Rényi graph, and study three specific families of random graph models in detail: stochastic block models, Chung--Lu models and Kronecker random graphs. We show that in these cases one may learn to maximize influence by merely observing the degree of the selected vertex in the generated random graph. We propose sequential learning algorithms that aim at maximizing influence, and provide their theoretical analysis in both the subcritical and supercritical regimes of all considered models.
Formal Verification of a Distributed Dynamic Reconfiguration Protocol
Venue: arXiv cs.DC 2021
Year: 2021

We present a formal, machine checked TLA+ safety proof of MongoRaftReconfig, a distributed dynamic reconfiguration protocol. MongoRaftReconfig was designed for and implemented in MongoDB, a distributed database whose replication protocol is derived from the Raft consensus algorithm. We present an inductive invariant for MongoRaftReconfig that is formalized in TLA+ and formally proved using the TLA+ proof system (TLAPS). We also present a formal TLAPS proof of two key safety properties of MongoRaftReconfig, LeaderCompleteness and StateMachineSafety. To our knowledge, these are the first machine checked inductive invariant and safety proof of a dynamic reconfiguration protocol for a Raft based replication system.
Mining Shape Expressions with ShapeIt
Venue: arXiv cs.SE 2021
Year: 2021

We present ShapeIt, a tool for mining specifications of cyber-physical systems (CPS) from their real-valued behaviors. The learned specifications are in the form of linear shape expressions, a declarative formal specification language suitable to express behavioral properties over real-valued signals. A linear shape expression is a regular expression composed of parameterized lines as atomic symbols with symbolic constraints on the line parameters. We present here the architecture of our tool along with the different steps of the specification mining algorithm. We also describe the usage of the tool demonstrating its applicability on several case studies from different application domains.
Description-based Label Attention Classifier for Explainable ICD-9 Classification
Venue: arXiv cs.LG 2021
Year: 2021

ICD-9 coding is a relevant clinical billing task, where unstructured texts with information about a patient's diagnosis and treatments are annotated with multiple ICD-9 codes. Automated ICD-9 coding is an active research field, where CNN- and RNN-based model architectures represent the state-of-the-art approaches. In this work, we propose a description-based label attention classifier to improve the model explainability when dealing with noisy texts like clinical notes. We evaluate our proposed method with different transformer-based encoders on the MIMIC-III-50 dataset. Our method achieves strong results together with augmented explainablilty.
Toward Efficient and Robust Multiple Camera Visual-inertial Odometry
Venue: arXiv cs.RO 2021
Year: 2021

Efficiency and robustness are the essential criteria for the visual-inertial odometry (VIO) system. To process massive visual data, the high cost on CPU resources and computation latency limits VIO's possibility in integration with other applications. Recently, the powerful embedded GPUs have great potentials to improve the front-end image processing capability. Meanwhile, multi-camera systems can increase the visual constraints for back-end optimization. Inspired by these insights, we incorporate the GPU-enhanced algorithms in the field of VIO and thus propose a new front-end with NVIDIA Vision Programming Interface (VPI). This new front-end then enables multi-camera VIO feature association and provides more stable back-end pose optimization. Experiments with our new front-end on monocular datasets show the CPU resource occupation rate and computational latency are reduced by 40.4% and 50.6% without losing accuracy compared with the original VIO. The multi-camera system shows a higher VIO initialization success rate and better robustness overall state estimation.
Free Energy Principle for State and Input Estimation of a Quadcopter Flying in Wind
Venue: arXiv cs.RO 2021
Year: 2021

The free energy principle from neuroscience provides a brain-inspired perception scheme through a data-driven model learning algorithm called Dynamic Expectation Maximization (DEM). This paper aims at introducing an experimental design to provide the first experimental confirmation of the usefulness of DEM as a state and input estimator for real robots. Through a series of quadcopter flight experiments under unmodelled wind dynamics, we prove that DEM can leverage the information from colored noise for accurate state and input estimation through the use of generalized coordinates. We demonstrate the superior performance of DEM for state estimation under colored noise with respect to other benchmarks like State Augmentation, SMIKF and Kalman Filtering through its minimal estimation error. We demonstrate the similarities in the performance of DEM and Unknown Input Observer (UIO) for input estimation. The paper concludes by showing the influence of prior beliefs in shaping the accuracy-complexity trade-off during DEM's estimation.
MCTS Based Agents for Multistage Single-Player Card Game
Venue: arXiv cs.AI 2021
Year: 2021

The article presents the use of Monte Carlo Tree Search algorithms for the card game Lord of the Rings. The main challenge was the complexity of the game mechanics, in which each round consists of 5 decision stages and 2 random stages. To test various decision-making algorithms, a game simulator has been implemented. The research covered an agent based on expert rules, using flat Monte-Carlo search, as well as complete MCTS-UCB. Moreover different playout strategies has been compared. As a result of experiments, an optimal (assuming a limited time) combination of algorithms were formulated. The developed MCTS based method have demonstrated a advantage over agent with expert knowledge.
A 4-DoF Parallel Origami Haptic Device for Normal, Shear, and Torsion Feedback
Venue: arXiv cs.RO 2021
Year: 2021

We present a mesoscale finger-mounted 4-degree-of-freedom (DoF) haptic device that is created using origami fabrication techniques. The 4-DoF device is a parallel kinematic mechanism capable of delivering normal, shear, and torsional haptic feedback to the fingertip. Traditional methods of robot fabrication are not well suited for designing small robotic devices because it is challenging and expensive to manufacture small, low-friction joints. Our device uses origami manufacturing principles to reduce complexity and the device footprint. We characterize the bandwidth, workspace, and force output of the device. The capabilities of the torsion-DoF are demonstrated in a virtual reality scenario. Our results show that the device can deliver haptic feedback in 4-DoFs with an effective operational workspace of 0.64cm$^3$ with $\pm 30 ^ \circ$ rotation at every location. The maximum forces and torques the device can apply in the x-, y-, z-, and $θ$-directions, are $\pm$1.5N, $\pm$1.5N, 2N, and 5N$\cdot$mm, respectively, and the device has an operating bandwidth of 9Hz.
Weather of the Dorm WIFI Ecosystem at the University of Colorado Boulder for Fall Semester 2019 to Spring Semester 2020 a Case Study of WIFI and a Campus Response to the COVID-19 Perturbation
Venue: arXiv cs.CY 2021
Year: 2021

Growing use of network technology in Higher Education means that there has been increasing demand to adapt technology platforms and tools that transform student learning strategies, faculty teaching, research modalities, as well as general operations. Many of the new modalities are necessary for IHE business. In August 2019, we began collecting and analyzing data from the campus WIFI network. A goal of the research was to answer question like what passive sensing of the IHE WIFI might tell us about the dynamics of the WIFI weather in the IHE ecosystem and what does anonymized data tell us about the IHE ecosystem. The analogy with weather prediction seemed appropriate and a viable approach. Starting Fall 2019, data were collected in the observational phase. In the analysis phase, we applied Singular Spectrum Analysis decomposition, to deconstruct WIFI data from dorms, the central campus dining cafeteria, the recreation center, and other buildings on campus. That analysis led to the identification of clusters of buildings that behaved similarly. Just as in the case of models of the weather, a final component of this research was forecasting. We found that weekly forecast of WIFI behavior in the Fall 2019, were straight forward using SSA and seemed to present behavior of a low dimensional dynamical system. However, in Spring 2020, and the COVID perturbation, the campus ecosystem received a shock and data show that the campus changed very quickly. We found that as the campus moved to conduct remote learning, teaching, the closure of research labs, and the edict to work remotely, SSA forecasting techniques not trained on the Spring 2020, data after the shock, performed poorly. While SSA forecasting trained on a portion of the data did better.
Spatial Aggregation and Temporal Convolution Networks for Real-time Kriging
Venue: arXiv cs.LG 2021
Year: 2021

Spatiotemporal kriging is an important application in spatiotemporal data analysis, aiming to recover/interpolate signals for unsampled/unobserved locations based on observed signals. The principle challenge for spatiotemporal kriging is how to effectively model and leverage the spatiotemporal dependencies within the data. Recently, graph neural networks (GNNs) have shown great promise for spatiotemporal kriging tasks. However, standard GNNs often require a carefully designed adjacency matrix and specific aggregation functions, which are inflexible for general applications/problems. To address this issue, we present SATCN -- Spatial Aggregation and Temporal Convolution Networks -- a universal and flexible framework to perform spatiotemporal kriging for various spatiotemporal datasets without the need for model specification. Specifically, we propose a novel spatial aggregation network (SAN) inspired by Principal Neighborhood Aggregation, which uses multiple aggregation functions to help one node gather diverse information from its neighbors. To exclude information from unsampled nodes, a masking strategy that prevents the unsampled sensors from sending messages to their neighborhood is introduced to SAN. We capture temporal dependencies by the temporal convolutional networks, which allows our model to cope with data of diverse sizes. To make SATCN generalizable to unseen nodes and even unseen graph structures, we employ an inductive strategy to train SATCN. We conduct extensive experiments on three real-world spatiotemporal datasets, including traffic speed and climate recordings. Our results demonstrate the superiority of SATCN over traditional and GNN-based kriging models.