OpenRaiser/Intern-Atlas huggingface dataset:
TS-MULE: Local Interpretable Model-Agnostic Explanations for Time Series Forecast Models
Venue: arXiv cs.LG 2021
Year: 2021

Time series forecasting is a demanding task ranging from weather to failure forecasting with black-box models achieving state-of-the-art performances. However, understanding and debugging are not guaranteed. We propose TS-MULE, a local surrogate model explanation method specialized for time series extending the LIME approach. Our extended LIME works with various ways to segment and perturb the time series data. In our extension, we present six sampling segmentation approaches for time series to improve the quality of surrogate attributions and demonstrate their performances on three deep learning model architectures and three common multivariate time series datasets.
Developing Visualisations to Enhance an Insider Threat Product: A Case Study
Venue: arXiv cs.HC 2021
Year: 2021

This paper describes the process of developing data visualisations to enhance a commercial software platform for combating insider threat, whose existing UI, while perfectly functional, was limited in its ability to allow analysts to easily spot the patterns and outliers that visualisation naturally reveals. We describe the design and development process, proceeding from initial tasks/requirements gathering, understanding the platform's data formats, the rationale behind the visualisation's design, and then refining the prototype through gathering feedback from representative domain experts who are also current users of the software. Through a number of example scenarios, we show that the visualisation can support the identified tasks and aid analysts in discovering and understanding potentially risky insider activity within a large user base.
Decentralized Global Connectivity Maintenance for Multi-Robot Navigation: A Reinforcement Learning Approach
Venue: arXiv cs.RO 2021
Year: 2021

The problem of multi-robot navigation of connectivity maintenance is challenging in multi-robot applications. This work investigates how to navigate a multi-robot team in unknown environments while maintaining connectivity. We propose a reinforcement learning (RL) approach to develop a decentralized policy, which is shared among multiple robots. Given range sensor measurements and the positions of other robots, the policy aims to generate control commands for navigation and preserve the global connectivity of the robot team. We incorporate connectivity concerns into the RL framework as constraints and introduce behavior cloning to reduce the exploration complexity of policy optimization. The policy is optimized with all transition data collected by multiple robots in random simulated scenarios. We validate the effectiveness of the proposed approach by comparing different combinations of connectivity constraints and behavior cloning. We also show that our policy can generalize to unseen scenarios in both simulation and holonomic robots experiments.
A Tutorial on Mathematical Modeling of Millimeter Wave and Terahertz Cellular Systems
Venue: arXiv cs.NI 2021
Year: 2021

Millimeter wave (mmWave) and terahertz (THz) radio access technologies (RAT) are expected to become a critical part of the future cellular ecosystem providing an abundant amount of bandwidth in areas with high traffic demands. However, extremely directional antenna radiation patterns that need to be utilized at both transmit and receive sides of a link to overcome severe path losses, dynamic blockage of propagation paths by large static and small dynamic objects, macro- and micromobility of user equipment (UE) makes provisioning of reliable service over THz/mmWave RATs an extremely complex task. This challenge is further complicated by the type of applications envisioned for these systems inherently requiring guaranteed bitrates at the air interface. This tutorial aims to introduce a versatile mathematical methodology for assessing performance reliability improvement algorithms for mmWave and THz systems. Our methodology accounts for both radio interface specifics as well as service process of sessions at mmWave/THz base stations (BS) and is capable of evaluating the performance of systems with multiconnectivity operation, resource reservation mechanisms, priorities between multiple traffic types having different service requirements. The framework is logically separated into two parts: (i) parameterization part that abstracts the specifics of deployment and radio mechanisms, and (ii) queuing part, accounting for details of the service process at mmWave/THz BSs. The modular decoupled structure of the framework allows for further extensions to advanced service mechanisms in prospective mmWave/THz cellular deployments while keeping the complexity manageable and thus making it attractive for system analysts.
Realistic PointGoal Navigation via Auxiliary Losses and Information Bottleneck
Venue: arXiv cs.CV 2021
Year: 2021

We propose a novel architecture and training paradigm for training realistic PointGoal Navigation -- navigating to a target coordinate in an unseen environment under actuation and sensor noise without access to ground-truth localization. Specifically, we find that the primary challenge under this setting is learning localization -- when stripped of idealized localization, agents fail to stop precisely at the goal despite reliably making progress towards it. To address this we introduce a set of auxiliary losses to help the agent learn localization. Further, we explore the idea of treating the precise location of the agent as privileged information -- it is unavailable during test time, however, it is available during training time in simulation. We grant the agent restricted access to ground-truth localization readings during training via an information bottleneck. Under this setting, the agent incurs a penalty for using this privileged information, encouraging the agent to only leverage this information when it is crucial to learning. This enables the agent to first learn navigation and then learn localization instead of conflating these two objectives in training. We evaluate our proposed method both in a semi-idealized (noiseless simulation without Compass+GPS) and realistic (addition of noisy simulation) settings. Specifically, our method outperforms existing baselines on the semi-idealized setting by 18\%/21\% SPL/Success and by 15\%/20\% SPL in the realistic setting. Our improved Success and SPL metrics indicate our agent's improved ability to accurately self-localize while maintaining a strong navigation policy. Our implementation can be found at https://github.com/NicoGrande/habitat-pointnav-via-ib.
Graph Based Answer Set Programming Solver Systems
Venue: arXiv cs.LO 2021
Year: 2021

Answer set programming (ASP) is a popular nonmonotonic-logic based paradigm for knowledge representation and solving combinatorial problems. Computing the answer set of an ASP program is NP-hard in general, and researchers have been investing significant effort to speed it up. The majority of current ASP solvers employ SAT solver-like technology to find these answer sets. As a result, justification for why a literal is in the answer set is hard to produce. There are dependency graph based approaches to find answer sets, but due to the representational limitations of dependency graphs, such approaches are limited. This paper proposes a novel dependency graph-based approach for finding answer sets in which conjunction of goals is explicitly represented as a node which allows arbitrary answer set programs to be uniformly represented. Our representation preserves causal relationships allowing for justification for each literal in the answer set to be elegantly found. In this paper, we explore two different approaches based on the graph representation: bottom-up and top-down. The bottom-up approach finds models by assigning truth values along with the topological order, while the top-down approach generates models starting from the constraints.
Section 108 and Software Collections, A User's Guide
Venue: arXiv cs.DL 2021
Year: 2021

This user's guide explains Section 108 of the U.S. Copyright Act, a set of rights for libraries and archives, in the context of software collections. It also addresses the interaction between Section 108 and fair use (Section 107) in this context. The guide will help library and archives workers who preserve and provide access to software collections to navigate U.S. copyright law.
When a Computer Cracks a Joke: Automated Generation of Humorous Headlines
Venue: arXiv cs.CL 2021
Year: 2021

Automated news generation has become a major interest for new agencies in the past. Oftentimes headlines for such automatically generated news articles are unimaginative as they have been generated with ready-made templates. We present a computationally creative approach for headline generation that can generate humorous versions of existing headlines. We evaluate our system with human judges and compare the results to human authored humorous titles. The headlines produced by the system are considered funny 36\% of the time by human evaluators.
Solving infinite-horizon Dec-POMDPs using Finite State Controllers within JESP
Venue: arXiv cs.AI 2021
Year: 2021

This paper looks at solving collaborative planning problems formalized as Decentralized POMDPs (Dec-POMDPs) by searching for Nash equilibria, i.e., situations where each agent's policy is a best response to the other agents' (fixed) policies. While the Joint Equilibrium-based Search for Policies (JESP) algorithm does this in the finite-horizon setting relying on policy trees, we propose here to adapt it to infinite-horizon Dec-POMDPs by using finite state controller (FSC) policy representations. In this article, we (1) explain how to turn a Dec-POMDP with $N-1$ fixed FSCs into an infinite-horizon POMDP whose solution is an $N^\text{th}$ agent best response; (2) propose a JESP variant, called \infJESP, using this to solve infinite-horizon Dec-POMDPs; (3) introduce heuristic initializations for JESP aiming at leading to good solutions; and (4) conduct experiments on state-of-the-art benchmark problems to evaluate our approach.
Learning to Regrasp by Learning to Place
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we explore whether a robot can learn to regrasp a diverse set of objects to achieve various desired grasp poses. Regrasping is needed whenever a robot's current grasp pose fails to perform desired manipulation tasks. Endowing robots with such an ability has applications in many domains such as manufacturing or domestic services. Yet, it is a challenging task due to the large diversity of geometry in everyday objects and the high dimensionality of the state and action space. In this paper, we propose a system for robots to take partial point clouds of an object and the supporting environment as inputs and output a sequence of pick-and-place operations to transform an initial object grasp pose to the desired object grasp poses. The key technique includes a neural stable placement predictor and a regrasp graph-based solution through leveraging and changing the surrounding environment. We introduce a new and challenging synthetic dataset for learning and evaluating the proposed approach. We demonstrate the effectiveness of our proposed system with both simulator and real-world experiments. More videos and visualization examples are available on our project webpage.
An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization
Venue: arXiv cs.LG 2021
Year: 2021

The conditional gradient algorithm (also known as the Frank-Wolfe algorithm) has recently regained popularity in the machine learning community due to its projection-free property to solve constrained problems. Although many variants of the conditional gradient algorithm have been proposed to improve performance, they depend on first-order information (gradient) to optimize. Naturally, these algorithms are unable to function properly in the field of increasingly popular zeroth-order optimization, where only zeroth-order information (function value) is available. To fill in this gap, we propose a novel Accelerated variance-Reduced Conditional gradient Sliding (ARCS) algorithm for finite-sum problems, which can use either first-order or zeroth-order information to optimize. To the best of our knowledge, ARCS is the first zeroth-order conditional gradient sliding type algorithms solving convex problems in zeroth-order optimization. In first-order optimization, the convergence results of ARCS substantially outperform previous algorithms in terms of the number of gradient query oracle. Finally we validated the superiority of ARCS by experiments on real-world datasets.
How Does Facebook Retain Segregated Friendship? An Agent-Based Model Approach
Venue: arXiv cs.SI 2021
Year: 2021

Facebook, the largest social networking site in the world, has overcome the structural barriers that historically constrain individuals to reach out to different others. Through the platform, people from all walks of life and virtually any location can develop diverse friendships online. However, friendships on Facebook have been as segregated as friendships in real life. This research sought to understand why the leading social networking site intended to 'bring the world closer together' retains segregated friendship. In doing so, we employed a series of agent-based simulations based on the Framework for Intergroup Relations and Multiple Affiliations Networks (FIRMAN). As demonstrated, Facebook has primarily enhanced users' capacity to maintain a larger number of friendships (tie capacity), while has done little to empower users' ability to accept diversity and befriend different others (tie outreachability). Facebook must focus on the latter should they truly wish to contribute to the development of a more inclusive society. While in this study we focus on ethnically segregated friendship on Facebook, we argue that the same explanation may also hold for racially and ideologically segregated friendships on other bi-directional social networking sites.
Fast User Adaptation for Human Motion Prediction in Physical Human-Robot Interaction
Venue: arXiv cs.RO 2021
Year: 2021

Accurate prediction of human movements is required to enhance the efficiency of physical human-robot interaction. Behavioral differences across various users are crucial factors that limit the prediction of human motion. Although recent neural network-based modeling methods have improved their prediction accuracy, most did not consider an effective adaptations to different users, thereby employing the same model parameters for all users. To deal with this insufficiently addressed challenge, we introduce a meta-learning framework to facilitate the rapid adaptation of the model to unseen users. In this study, we propose a model structure and a meta-learning algorithm specialized to enable fast user adaptation in predicting human movements in cooperative situations with robots. The proposed prediction model comprises shared and adaptive parameters, each addressing the user's general and individual movements. Using only a small amount of data from an individual user, the adaptive parameters are adjusted to enable user-specific prediction through a two-step process: initialization via a separate network and adaptation via a few gradient steps. Regarding the motion dataset that has 20 users collaborating with a robotic device, the proposed method outperforms existing meta-learning and non-meta-learning baselines in predicting the movements of unseen users.
Regular Sequential Serializability and Regular Sequential Consistency
Venue: arXiv cs.DB 2021
Year: 2021

Strictly serializable (linearizable) services appear to execute transactions (operations) sequentially, in an order consistent with real time. This restricts a transaction's (operation's) possible return values and in turn, simplifies application programming. In exchange, strictly serializable (linearizable) services perform worse than those with weaker consistency. But switching to such services can break applications. This work introduces two new consistency models to ease this trade-off: regular sequential serializability (RSS) and regular sequential consistency (RSC). They are just as strong for applications: we prove any application invariant that holds when using a strictly serializable (linearizable) service also holds when using an RSS (RSC) service. Yet they relax the constraints on services -- they allow new, better-performing designs. To demonstrate this, we design, implement, and evaluate variants of two systems, Spanner and Gryff, relaxing their consistency to RSS and RSC, respectively. The new variants achieve better read-only transaction and read tail latency than their counterparts.
Optimization-based Block Coordinate Gradient Coding
Venue: arXiv cs.DC 2021
Year: 2021

Existing gradient coding schemes introduce identical redundancy across the coordinates of gradients and hence cannot fully utilize the computation results from partial stragglers. This motivates the introduction of diverse redundancies across the coordinates of gradients. This paper considers a distributed computation system consisting of one master and $N$ workers characterized by a general partial straggler model and focuses on solving a general large-scale machine learning problem with $L$ model parameters. We show that it is sufficient to provide at most $N$ levels of redundancies for tolerating $0, 1,\cdots, N-1$ stragglers, respectively. Consequently, we propose an optimal block coordinate gradient coding scheme based on a stochastic optimization problem that optimizes the partition of the $L$ coordinates into $N$ blocks, each with identical redundancy, to minimize the expected overall runtime for collaboratively computing the gradient. We obtain an optimal solution using a stochastic projected subgradient method and propose two low-complexity approximate solutions with closed-from expressions, for the stochastic optimization problem. We also show that under a shifted-exponential distribution, for any $L$, the expected overall runtimes of the two approximate solutions and the minimum overall runtime have sub-linear multiplicative gaps in $N$. To the best of our knowledge, this is the first work that optimizes the redundancies of gradient coding introduced across the coordinates of gradients.
Atrial Fibrillation: A Medical and Technological Review
Venue: arXiv cs.LG 2021
Year: 2021

Atrial Fibrillation (AF) is the most common type of arrhythmia (Greek a-, loss + rhythmos, rhythm = loss of rhythm) leading to hospitalization in the United States. Though sometimes AF is asymptomatic, it increases the risk of stroke and heart failure in patients, in addition to lowering the health-related quality of life (HRQOL). AF-related care costs the healthcare system between $6.0 to $26 billion each year. Early detection of AF and clinical attention can help improve symptoms and HRQOL of the patient, as well as bring down the cost of care. However, the prevalent paradigm of AF detection depends on electrocardiogram (ECG) recorded at a single point in time and does not shed light on the relation of the symptoms with heart rhythm or AF. In the recent decade, due to the democratization of health monitors and the advent of high-performing computers, Machine Learning algorithms have been proven effective in identifying AF, from the ECG of patients. This paper provides an overview of the symptoms of AF, its diagnosis, and future prospects for research in the field.
Breaking the Computational Bottleneck: Design of Near-Optimal High-Memory Spatially-Coupled Codes
Venue: arXiv cs.IT 2021
Year: 2021

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging. We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interests, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems.
A Distributed Process Model of Cryptographic Protocols
Venue: arXiv cs.CR 2021
Year: 2021

Cryptographic Protocols (CP) are distributed algorithms intended for secure communication in an insecure environment. They are used, for example, in electronic payments, electronic voting procedures, systems of confidential data processing, etc. Errors in CPs can bring to great financial and social damage, therefore it is necessary to use mathematical methods to substantiate the correctness and safety of CPs. In this paper, a distributed process model of CPs is presented, which allows one to formally describe CPs and their properties. It is shown how to solve the problems of verification of CPs on the base of this model.
G-CoS: GNN-Accelerator Co-Search Towards Both Better Accuracy and Efficiency
Venue: arXiv cs.AR 2021
Year: 2021

Graph Neural Networks (GNNs) have emerged as the state-of-the-art (SOTA) method for graph-based learning tasks. However, it still remains prohibitively challenging to inference GNNs over large graph datasets, limiting their application to large-scale real-world tasks. While end-to-end jointly optimizing GNNs and their accelerators is promising in boosting GNNs' inference efficiency and expediting the design process, it is still underexplored due to the vast and distinct design spaces of GNNs and their accelerators. In this work, we propose G-CoS, a GNN and accelerator co-search framework that can automatically search for matched GNN structures and accelerators to maximize both task accuracy and acceleration efficiency. Specifically, GCoS integrates two major enabling components: (1) a generic GNN accelerator search space which is applicable to various GNN structures and (2) a one-shot GNN and accelerator co-search algorithm that enables simultaneous and efficient search for optimal GNN structures and their matched accelerators. To the best of our knowledge, G-CoS is the first co-search framework for GNNs and their accelerators. Extensive experiments and ablation studies show that the GNNs and accelerators generated by G-CoS consistently outperform SOTA GNNs and GNN accelerators in terms of both task accuracy and hardware efficiency, while only requiring a few hours for the end-to-end generation of the best matched GNNs and their accelerators.