OpenRaiser/Intern-Atlas huggingface dataset:
The Evolutionary Dynamics of Independent Learning Agents in Population Games
Venue: arXiv cs.MA 2020
Year: 2020

Understanding the evolutionary dynamics of reinforcement learning under multi-agent settings has long remained an open problem. While previous works primarily focus on 2-player games, we consider population games, which model the strategic interactions of a large population comprising small and anonymous agents. This paper presents a formal relation between stochastic processes and the dynamics of independent learning agents who reason based on the reward signals. Using a master equation approach, we provide a novel unified framework for characterising population dynamics via a single partial differential equation (Theorem 1). Through a case study involving Cross learning agents, we illustrate that Theorem 1 allows us to identify qualitatively different evolutionary dynamics, to analyse steady states, and to gain insights into the expected behaviour of a population. In addition, we present extensive experimental results validating that Theorem 1 holds for a variety of learning methods and population games.
Joint Cyber Risk Assessment of Network Systems with Heterogeneous Components
Venue: arXiv cs.SI 2020
Year: 2020

Cyber risks are the most common risks encountered by a modern network system. However, it is significantly difficult to assess the joint cyber risk owing to the network topology, risk propagation, and heterogeneities of components. In this paper, we propose a novel backward elimination approach for computing the joint cyber risk encountered by different types of components in a network system; moreover, explicit formulas are also presented. Certain specific network topologies including complete, star, and complete bi-partite topologies are studied. The effects of propagation depth and compromise probabilities on the joint cyber risk are analyzed using stochastic comparisons. The variances and correlations of cyber risks are examined by a simulation experiment. It was discovered that both variances and correlations change rapidly when the propagation depth increases from its initial value. Further, numerical examples are also presented.
To Share or Not to Share? Performance Guarantees and the Asymmetric Nature of Cross-Robot Experience Transfer
Venue: arXiv cs.RO 2020
Year: 2020

In the robotics literature, experience transfer has been proposed in different learning-based control frameworks to minimize the costs and risks associated with training robots. While various works have shown the feasibility of transferring prior experience from a source robot to improve or accelerate the learning of a target robot, there are usually no guarantees that experience transfer improves the performance of the target robot. In practice, the efficacy of transferring experience is often not known until it is tested on physical robots. This trial-and-error approach can be extremely unsafe and inefficient. Building on our previous work, in this paper we consider an inverse module transfer learning framework, where the inverse module of a source robot system is transferred to a target robot system to improve its tracking performance on arbitrary trajectories. We derive a theoretical bound on the tracking error when a source inverse module is transferred to the target robot and propose a Bayesian-optimization-based algorithm to estimate this bound from data. We further highlight the asymmetric nature of cross-robot experience transfer that has often been neglected in the literature. We demonstrate our approach in quadrotor experiments and show that we can guarantee positive transfer on the target robot for tracking random periodic trajectories.
Extracting Latent State Representations with Linear Dynamics from Rich Observations
Venue: arXiv cs.LG 2020
Year: 2020

Recently, many reinforcement learning techniques were shown to have provable guarantees in the simple case of linear dynamics, especially in problems like linear quadratic regulators. However, in practice, many reinforcement learning problems try to learn a policy directly from rich, high dimensional representations such as images. Even if there is an underlying dynamics that is linear in the correct latent representations (such as position and velocity), the rich representation is likely to be nonlinear and can contain irrelevant features. In this work we study a model where there is a hidden linear subspace in which the dynamics is linear. For such a model we give an efficient algorithm for extracting the linear subspace with linear dynamics. We then extend our idea to extracting a nonlinear mapping, and empirically verify the effectiveness of our approach in simple settings with rich observations.
Want to Identify, Extract and Normalize Adverse Drug Reactions in Tweets? Use RoBERTa
Venue: arXiv cs.CL 2020
Year: 2020

This paper presents our approach for task 2 and task 3 of Social Media Mining for Health (SMM4H) 2020 shared tasks. In task 2, we have to differentiate adverse drug reaction (ADR) tweets from nonADR tweets and is treated as binary classification. Task3 involves extracting ADR mentions and then mapping them to MedDRA codes. Extracting ADR mentions is treated as sequence labeling and normalizing ADR mentions is treated as multi-class classification. Our system is based on pre-trained language model RoBERTa and it achieves a) F1-score of 58% in task2 which is 12% more than the average score b) relaxed F1-score of 70.1% in ADR extraction of task 3 which is 13.7% more than the average score and relaxed F1-score of 35% in ADR extraction + normalization of task3 which is 5.8% more than the average score. Overall, our models achieve promising results in both the tasks with significant improvements over average scores.
Binary Random Projections with Controllable Sparsity Patterns
Venue: arXiv cs.LG 2020
Year: 2020

Random projection is often used to project higher-dimensional vectors onto a lower-dimensional space, while approximately preserving their pairwise distances. It has emerged as a powerful tool in various data processing tasks and has attracted considerable research interest. Partly motivated by the recent discoveries in neuroscience, in this paper we study the problem of random projection using binary matrices with controllable sparsity patterns. Specifically, we proposed two sparse binary projection models that work on general data vectors. Compared with the conventional random projection models with dense projection matrices, our proposed models enjoy significant computational advantages due to their sparsity structure, as well as improved accuracies in empirical evaluations.
Object Files and Schemata: Factorizing Declarative and Procedural Knowledge in Dynamical Systems
Venue: arXiv cs.LG 2020
Year: 2020

Modeling a structured, dynamic environment like a video game requires keeping track of the objects and their states declarative knowledge) as well as predicting how objects behave (procedural knowledge). Black-box models with a monolithic hidden state often fail to apply procedural knowledge consistently and uniformly, i.e., they lack systematicity. For example, in a video game, correct prediction of one enemy's trajectory does not ensure correct prediction of another's. We address this issue via an architecture that factorizes declarative and procedural knowledge and that imposes modularity within each form of knowledge. The architecture consists of active modules called object files that maintain the state of a single object and invoke passive external knowledge sources called schemata that prescribe state updates. To use a video game as an illustration, two enemies of the same type will share schemata but will have separate object files to encode their distinct state (e.g., health, position). We propose to use attention to determine which object files to update, the selection of schemata, and the propagation of information between object files. The resulting architecture is a drop-in replacement conforming to the same input-output interface as normal recurrent networks (e.g., LSTM, GRU) yet achieves substantially better generalization on environments that have multiple object tokens of the same type, including a challenging intuitive physics benchmark.
True to the Model or True to the Data?
Venue: arXiv cs.LG 2020
Year: 2020

A variety of recent papers discuss the application of Shapley values, a concept for explaining coalitional games, for feature attribution in machine learning. However, the correct way to connect a machine learning model to a coalitional game has been a source of controversy. The two main approaches that have been proposed differ in the way that they condition on known features, using either (1) an interventional or (2) an observational conditional expectation. While previous work has argued that one of the two approaches is preferable in general, we argue that the choice is application dependent. Furthermore, we argue that the choice comes down to whether it is desirable to be true to the model or true to the data. We use linear models to investigate this choice. After deriving an efficient method for calculating observational conditional expectation Shapley values for linear models, we investigate how correlation in simulated data impacts the convergence of observational conditional expectation Shapley values. Finally, we present two real data examples that we consider to be representative of possible use cases for feature attribution -- (1) credit risk modeling and (2) biological discovery. We show how a different choice of value function performs better in each scenario, and how possible attributions are impacted by modeling choices.
A Compact Gated-Synapse Model for Neuromorphic Circuits
Venue: arXiv cs.NE 2020
Year: 2020

This work reports a compact behavioral model for gated-synaptic memory. The model is developed in Verilog-A for easy integration into computer-aided design of neuromorphic circuits using emerging memory. The model encompasses various forms of gated synapses within a single framework and is not restricted to only a single type. The behavioral theory of the model is described in detail along with a full list of the default parameter settings. The model includes parameters such as a device's ideal set time, threshold voltage, general evolution of the conductance with respect to time, decay of the device's state, etc. Finally, the model's validity is shown via extensive simulation and fitting to experimentally reported data on published gated-synapses.
A Generative Neural Network Framework for Automated Software Testing
Venue: arXiv cs.SE 2020
Year: 2020

Search Based Software Testing (SBST) is a popular automated testing technique which uses a feedback mechanism to search for faults in software. Despite its popularity, it has fundamental challenges related to the design, construction and interpretation of the feedback. Neural Networks (NN) have been hugely popular in recent years for a wide range of tasks. We believe that they can address many of the issues inherent to common SBST approaches. Unfortunately, NNs require large and representative training datasets. In this work we present an SBST framework based on a deconvolutional generative neural network. Not only does it retain the beneficial qualities that make NNs appropriate for SBST tasks, it also produces its own training data which circumvents the problem of acquiring a training dataset that limits the use of NNs. We demonstrate through a series of experiments that this architecture is possible and practical. It generates diverse, sensible program inputs, while exploring the space of program behaviours. It also creates a meaningful ordering over program behaviours and is able to find crashing executions. This is all done without any prior knowledge of the program. We believe this proof of concept opens new directions for future work at the intersection of SBST and neural networks.
Parallel Betweenness Computation in Graph Database for Contingency Selection
Venue: arXiv cs.DC 2020
Year: 2020

Parallel betweenness computation algorithms are proposed and implemented in a graph database for power system contingency selection. Principles of the graph database and graph computing are investigated for both node and edge betweenness computation. Experiments on the 118-bus system and a real power system show that speed-up can be achieved for both node and edge betweenness computation while the speeding effect on the latter is more remarkable due to the data retrieving advantages of the graph database on the power network data.
Classification of cancer pathology reports: a large-scale comparative study
Venue: arXiv cs.LG 2020
Year: 2020

We report about the application of state-of-the-art deep learning techniques to the automatic and interpretable assignment of ICD-O3 topography and morphology codes to free-text cancer reports. We present results on a large dataset (more than 80 000 labeled and 1 500 000 unlabeled anonymized reports written in Italian and collected from hospitals in Tuscany over more than a decade) and with a large number of classes (134 morphological classes and 61 topographical classes). We compare alternative architectures in terms of prediction accuracy and interpretability and show that our best model achieves a multiclass accuracy of 90.3% on topography site assignment and 84.8% on morphology type assignment. We found that in this context hierarchical models are not better than flat models and that an element-wise maximum aggregator is slightly better than attentive models on site classification. Moreover, the maximum aggregator offers a way to interpret the classification process.
Learning Patterns of Tourist Movement and Photography from Geotagged Photos at Archaeological Heritage Sites in Cuzco, Peru
Venue: arXiv cs.SI 2020
Year: 2020

The popularity of media sharing platforms in recent decades has provided an abundance of open source data that remains underutilized by heritage scholars. By pairing geotagged internet photographs with machine learning and computer vision algorithms, we build upon the current theoretical discourse of anthropology associated with visuality and heritage tourism to identify travel patterns across a known archaeological heritage circuit, and quantify visual culture and experiences in Cuzco, Peru. Leveraging large-scale in-the-wild tourist photos, our goals are to (1) understand how the intensification of tourism intersects with heritage regulations and social media, aiding in the articulation of travel patterns across Cuzco's heritage landscape; and to (2) assess how aesthetic preferences and visuality become entangled with the rapidly evolving expectations of tourists, whose travel narratives are curated on social media and grounded in historic site representations.
Investigating the Effects of Mobility Metrics in Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2020
Year: 2020

Mobile Ad Hoc Networks (MANETs) are formed by a collection of mobile nodes (MNs) that are capable of moving from one location to another location. These networks are widely identified by their unique characteristics such as lack of infrastructure, mobility and multi-hop communication. Unlike traditional (wired) networks, MNs in MANETs do not rely on any infrastructure or central management. Mobility allows MNs to move at different values of speed. Multi-hop communication is used to deliver data across the entire network. Due to mobility and changing network topology, the performance of these networks is significantly affected by the choice of mobility models and routing protocols. Our research work aims to evaluate the effects of mobility metrics on distinguishing between entity and group mobility models in MANETs. In addition, we demonstrate the interactions between mobility metrics and performance metrics. We also investigate how effective are the mobility metrics and which metrics can clearly distinguish between entity and group mobility models? We performed extensive simulations using network simulator, ns-2.35, to capture mobility metrics as well as different performance metrics. Simulation results reveal the efficiency of mobility metrics on distinguishing between entity and group mobility models. We also obtain useful interactions between mobility metrics and performance metrics. The results presented in this paper provide new insights into the variability of mobility metrics in MANETs. Furthermore, our simulation results reveal better understanding of the relationships between mobility metrics (e.g., relative speed, node degree, network partitions etc.) and performance metrics (e.g., packet delivery ratio, end-to-end delay and normalized routing load
A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions
Venue: arXiv cs.DM 2020
Year: 2020

We propose a quantum algorithm to estimate the Gowers $U_2$ norm of a Boolean function, and extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $ε$-far from the set of linear Boolean functions, which seems to perform better than the classical BLR algorithm. Finally, we outline an algorithm to estimate Gowers $U_3$ norms of Boolean functions.
Actionable Attribution Maps for Scientific Machine Learning
Venue: arXiv cs.CV 2020
Year: 2020

The scientific community has been increasingly interested in harnessing the power of deep learning to solve various domain challenges. However, despite the effectiveness in building predictive models, fundamental challenges exist in extracting actionable knowledge from the deep neural network due to their opaque nature. In this work, we propose techniques for exploring the behavior of deep learning models by injecting domain-specific actionable concepts as tunable ``knobs'' in the analysis pipeline. By incorporating the domain knowledge with generative modeling, we are not only able to better understand the behavior of these black-box models, but also provide scientists with actionable insights that can potentially lead to fundamental discoveries.
Next Generation Wi-Fi and 5G NR-U in the 6 GHz Bands: Opportunities & Challenges
Venue: arXiv cs.NI 2020
Year: 2020

The ever-increasing demand for unlicensed spectrum has prompted regulators in the US and Europe to consider opening up the 6 GHz bands for unlicensed access. These bands will open up 1.2 GHz of additional spectrum for unlicensed radio access technologies (RATs), such as Wi-Fi and 5G New Radio Unlicensed (NR-U), in the US and if permitted, 500 MHz of additional spectrum in Europe. The abundance of spectrum in these bands creates new opportunities for the design of mechanisms and features that can support the emerging bandwidth-intensive and latency-sensitive applications. However, coexistence of unlicensed devices both with the bands' incumbent users and across different unlicensed RATs present significant challenges. In this paper, we provide a comprehensive survey of the existing literature on various issues surrounding the operations of unlicensed RATs in the 6 GHz bands. In particular, we discuss how key features in next-generation Wi-Fi are being designed to leverage these additional unlicensed bands. We also shed light on the foreseeable challenges that designers of unlicensed RATs might face in the near future. Our survey encompasses key research papers, contributions submitted to standardization bodies and regulatory agencies, and documents presented at various other venues. Finally, we highlight a few key research problems that are likely to arise due to unlicensed operations in the 6 GHz bands. Tackling these research challenges effectively will be critical in ensuring that the new unlicensed bands are efficiently utilized while guaranteeing the interference-free operation of the bands' incumbent users.
Accelerating Binarized Neural Networks via Bit-Tensor-Cores in Turing GPUs
Venue: arXiv cs.DC 2020
Year: 2020

Despite foreseeing tremendous speedups over conventional deep neural networks, the performance advantage of binarized neural networks (BNNs) has merely been showcased on general-purpose processors such as CPUs and GPUs. In fact, due to being unable to leverage bit-level-parallelism with a word-based architecture, GPUs have been criticized for extremely low utilization (1%) when executing BNNs. Consequently, the latest tensorcores in NVIDIA Turing GPUs start to experimentally support bit computation. In this work, we look into this brand new bit computation capability and characterize its unique features. We show that the stride of memory access can significantly affect performance delivery and a data-format co-design is highly desired to support the tensorcores for achieving superior performance than existing software solutions without tensorcores. We realize the tensorcore-accelerated BNN design, particularly the major functions for fully-connect and convolution layers -- bit matrix multiplication and bit convolution. Evaluations on two NVIDIA Turing GPUs show that, with ResNet-18, our BTC-BNN design can process ImageNet at a rate of 5.6K images per second, 77% faster than state-of-the-art. Our BNN approach is released on https://github.com/pnnl/TCBNN.
Efficient Splitting of Measures and Necklaces
Venue: arXiv cs.DS 2020
Year: 2020

We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $ε$-CONSENSUS SPLITTING. In the problem $ε$-CONSENSUS SPLITTING, there are $n$ non-atomic probability measures on the interval $[0, 1]$ and $k$ agents. The goal is to divide the interval, via at most $n (k-1)$ cuts, into pieces and distribute them to the $k$ agents in an approximately equitable way, so that the discrepancy between the shares of any two agents, according to each measure, is at most $2 ε/ k$. It is known that this is possible even for $ε= 0$. NECKLACE SPLITTING is a discrete version of $ε$-CONSENSUS SPLITTING. For $k = 2$ and some absolute positive constant $ε$, both of these problems are PPAD-hard. We consider two types of approximation. The first provides every agent a positive amount of measure of each type under the constraint of making at most $n (k - 1)$ cuts. The second obtains an approximately equitable split with as few cuts as possible. Apart from the offline model, we consider the online model as well, where the interval (or necklace) is presented as a stream, and decisions about cutting and distributing must be made on the spot. For the first type of approximation, we describe an efficient algorithm that gives every agent at least $\frac{1}{nk}$ of each measure and works even online. For the second type of approximation, we provide an efficient online algorithm that makes $\text{poly}(n, k, ε)$ cuts and an offline algorithm making $O(nk \log \frac{k}ε)$ cuts. We also establish lower bounds for the number of cuts required in the online model for both problems even for $k=2$ agents, showing that the number of cuts in our online algorithm is optimal up to a logarithmic factor.