OpenRaiser/Intern-Atlas huggingface dataset:
Graph Spanners: A Tutorial Review
Venue: arXiv cs.DM 2020
Year: 2020

This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.
Pose Estimation for Ground Robots: On Manifold Representation, Integration, Re-Parameterization, and Optimization
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we focus on motion estimation dedicated for non-holonomic ground robots, by probabilistically fusing measurements from the wheel odometer and exteroceptive sensors. For ground robots, the wheel odometer is widely used in pose estimation tasks, especially in applications under planar-scene based environments. However, since the wheel odometer only provides 2D motion estimates, it is extremely challenging to use that for performing accurate full 6D pose (3D position and 3D orientation) estimation. Traditional methods on 6D pose estimation either approximate sensor or motion models, at the cost of accuracy reduction, or rely on other sensors, e.g., inertial measurement unit (IMU), to provide complementary measurements. By contrast, in this paper, we propose a novel method to utilize the wheel odometer for 6D pose estimation, by modeling and utilizing motion manifold for ground robots. Our approach is probabilistically formulated and only requires the wheel odometer and an exteroceptive sensor (e.g., a camera). Specifically, our method i) formulates the motion manifold of ground robots by parametric representation, ii) performs manifold based 6D integration with the wheel odometer measurements only, and iii) re-parameterizes manifold equations periodically for error reduction. To demonstrate the effectiveness and applicability of the proposed algorithmic modules, we integrate that into a sliding-window pose estimator by using measurements from the wheel odometer and a monocular camera. By conducting extensive simulated and real-world experiments, we show that the proposed algorithm outperforms competing state-of-the-art algorithms by a significant margin in pose estimation accuracy, especially when deployed in complex large-scale real-world environments.
Virtual Fixture Assistance for Suturing in Robot-Aided Pediatric Endoscopic Surgery
Venue: arXiv cs.RO 2020
Year: 2020

The limited workspace in pediatric endoscopic surgery makes surgical suturing one of the most difficult tasks. During suturing, surgeons have to prevent collisions between tools and also collisions with the surrounding tissues. Surgical robots have been shown to be effective in adult laparoscopy, but assistance for suturing in constrained workspaces has not been yet fully explored. In this letter, we propose guidance virtual fixtures to enhance the performance and the safety of suturing while generating the required task constraints using constrained optimization and Cartesian force feedback. We propose two guidance methods: looping virtual fixtures and a trajectory guidance cylinder, that are based on dynamic geometric elements. In simulations and experiments with a physical robot, we show that the proposed methods achieve a more precise and safer looping in robot-assisted pediatric endoscopy.
Toward a Knowledge-based Personalised Recommender System for Mobile App Development
Venue: arXiv cs.IR 2020
Year: 2020

Over the last few years, the arena of mobile application development has expanded considerably beyond the balance of the worldś software markets. With the growing number of mobile software companies, and the mounting sophistication of smartphones\' technology, developers have been building several categories of applications on dissimilar platforms. However, developers confront several challenges through the implementation of mobile application projects. In particular, there is a lack of consolidated systems that are competent to provide developers with personalised services promptly and efficiently. Hence, it is essential to develop tailored systems which can recommend appropriate tools, IDEs, platforms, software components and other correlated artifacts to mobile application developers. This paper proposes a new recommender system framework comprising a fortified set of techniques that are designed to provide mobile app developers with a distinctive platform to browse and search for the personalised artifacts. The proposed system make use of ontology and semantic web technology as well as machine learning techniques. In particular, the new RS framework comprises the following components; (i) domain knowledge inference module: including various semantic web technologies and lightweight ontologies; (ii) profiling and preferencing: a new proposed time-aware multidimensional user modelling; (iii) query expansion: to improve and enhance the retrieved results by semantically augmenting users\' query; and (iv) recommendation and information filtration: to make use of the aforementioned components to provide personalised services to the designated users and to answer a userś query with the minimum mismatches.
Masking by Moving: Learning Distraction-Free Radar Odometry from Pose Information
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents an end-to-end radar odometry system which delivers robust, real-time pose estimates based on a learned embedding space free of sensing artefacts and distractor objects. The system deploys a fully differentiable, correlation-based radar matching approach. This provides the same level of interpretability as established scan-matching methods and allows for a principled derivation of uncertainty estimates. The system is trained in a (self-)supervised way using only previously obtained pose information as a training signal. Using 280km of urban driving data, we demonstrate that our approach outperforms the previous state-of-the-art in radar odometry by reducing errors by up 68% whilst running an order of magnitude faster.
Neural Conversational QA: Learning to Reason v.s. Exploiting Patterns
Venue: arXiv cs.CL 2020
Year: 2020

Neural Conversational QA tasks like ShARC require systems to answer questions based on the contents of a given passage. On studying recent state-of-the-art models on the ShARCQA task, we found indications that the models learn spurious clues/patterns in the dataset. Furthermore, we show that a heuristic-based program designed to exploit these patterns can have performance comparable to that of the neural models. In this paper we share our findings about four types of patterns found in the ShARC corpus and describe how neural models exploit them. Motivated by the aforementioned findings, we create and share a modified dataset that has fewer spurious patterns, consequently allowing models to learn better.
Hypergraph Partitioning With Embeddings
Venue: arXiv cs.DS 2020
Year: 2020

Problems in scientific computing, such as distributing large sparse matrix operations, have analogous formulations as hypergraph partitioning problems. A hypergraph is a generalization of a traditional graph wherein "hyperedges" may connect any number of nodes. As a result, hypergraph partitioning is an NP-Hard problem to both solve or approximate. State-of-the-art algorithms that solve this problem follow the multilevel paradigm, which begins by iteratively "coarsening" the input hypergraph to smaller problem instances that share key structural features. Once identifying an approximate problem that is small enough to be solved directly, that solution can be interpolated and refined to the original problem. While this strategy represents an excellent trade off between quality and running time, it is sensitive to coarsening strategy. In this work we propose using graph embeddings of the initial hypergraph in order to ensure that coarsened problem instances retrain key structural features. Our approach prioritizes coarsening within self-similar regions within the input graph, and leads to significantly improved solution quality across a range of considered hypergraphs. Reproducibility: All source code, plots and experimental data are available at https://sybrandt.com/2019/partition.
Meta-learnt priors slow down catastrophic forgetting in neural networks
Venue: arXiv cs.AI 2020
Year: 2020

Current training regimes for deep learning usually involve exposure to a single task / dataset at a time. Here we start from the observation that in this context the trained model is not given any knowledge of anything outside its (single-task) training distribution, and has thus no way to learn parameters (i.e., feature detectors or policies) that could be helpful to solve other tasks, and to limit future interference with the acquired knowledge, and thus catastrophic forgetting. Here we show that catastrophic forgetting can be mitigated in a meta-learning context, by exposing a neural network to multiple tasks in a sequential manner during training. Finally, we present SeqFOMAML, a meta-learning algorithm that implements these principles, and we evaluate it on sequential learning problems composed by Omniglot and MiniImageNet classification tasks.
The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem
Venue: arXiv cs.DS 2020
Year: 2020

Contention resolution schemes have proven to be a useful and unifying abstraction for a variety of constrained optimization problems, in both offline and online arrival models. Much of prior work restricts attention to product distributions for the input set of elements, and studies contention resolution for increasingly general packing constraints, both offline and online. In this paper, we instead focus on generalizing the input distribution, restricting attention to matroid constraints in both the offline and online random arrival models. In particular, we study contention resolution when the input set is arbitrarily distributed, and may exhibit positive and/or negative correlations between elements. We characterize the distributions for which offline contention resolution is possible, and establish some of their basic closure properties. Our characterization can be interpreted as a distributional generalization of the matroid covering theorem. For the online random arrival model, we show that contention resolution is intimately tied to the secretary problem via two results. First, we show that a competitive algorithm for the matroid secretary problem implies that online contention resolution is essentially as powerful as offline contention resolution for matroids, so long as the algorithm is given the input distribution. Second, we reduce the matroid secretary problem to the design of an online contention resolution scheme of a particular form.
Multiservice-based Network Slicing Orchestration with Impatient Tenants
Venue: arXiv cs.NI 2020
Year: 2020

The combination of recent emerging technologies such as network function virtualization (NFV) and network programmability (SDN) gave birth to the novel Network Slicing paradigm. 5G networks consist of multi-tenant infrastructures capable of offering leased network "slices" to new customers (e.g., vertical industries) enabling a new telecom business model: Slice-as-a-Service (SlaaS). However, as the service demand gets increasingly dense, slice requests congestion may occur leading to undesired waiting periods. This may turn into impatient tenant behaviors that increase potential loss of the business attractiveness to customers. In this paper, we aim to i study the slicing admission control problem by means of a multi-queuing system for heterogeneous tenant requests, ii) derive its statistical behavior model, iii) find out the rational strategy of impatient tenants waiting in queue-based slice admission control systems, iv) prove mathematically and empirically the benefits of allowing infrastructure providers to share its information with the upcoming tenants, and v) provide a utility model for network slices admission optimization. Our results analyze the capability of the proposed SlaaS system to be approximately Markovian and evaluate its performance as compared to a baseline solution.
Electrical Flows over Spanning Trees
Venue: arXiv cs.DS 2020
Year: 2020

The network reconfiguration problem seeks to find a rooted tree $T$ such that the energy of the (unique) feasible electrical flow over $T$ is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from $\min\{O(m-n), O(n)\}$ for general graphs, to $O(\sqrt{n})$ over grids with uniform resistances on edges, and $O(1)$ for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance.
A Deep Learning Approach to Grasping the Invisible
Venue: arXiv cs.RO 2020
Year: 2020

We study an emerging problem named "grasping the invisible" in robotic manipulation, in which a robot is tasked to grasp an initially invisible target object via a sequence of pushing and grasping actions. In this problem, pushes are needed to search for the target and rearrange cluttered objects around it to enable effective grasps. We propose to solve the problem by formulating a deep learning approach in a critic-policy format. The target-oriented motion critic, which maps both visual observations and target information to the expected future rewards of pushing and grasping motion primitives, is learned via deep Q-learning. We divide the problem into two subtasks, and two policies are proposed to tackle each of them, by combining the critic predictions and relevant domain knowledge. A Bayesian-based policy accounting for past action experience performs pushing to search for the target; once the target is found, a classifier-based policy coordinates target-oriented pushing and grasping to grasp the target in clutter. The motion critic and the classifier are trained in a self-supervised manner through robot-environment interactions. Our system achieves a 93% and 87% task success rate on each of the two subtasks in simulation and an 85% task success rate in real robot experiments on the whole problem, which outperforms several baselines by large margins. Supplementary material is available at https://sites.google.com/umn.edu/grasping-invisible.
Packet Chasing: Spying on Network Packets over a Cache Side-Channel
Venue: arXiv cs.CR 2020
Year: 2020

This paper presents Packet Chasing, an attack on the network that does not require access to the network, and works regardless of the privilege level of the process receiving the packets. A spy process can easily probe and discover the exact cache location of each buffer used by the network driver. Even more useful, it can discover the exact sequence in which those buffers are used to receive packets. This then enables packet frequency and packet sizes to be monitored through cache side channels. This allows both covert channels between a sender and a remote spy with no access to the network, as well as direct attacks that can identify, among other things, the web page access patterns of a victim on the network. In addition to identifying the potential attack, this work proposes a software-based short-term mitigation as well as a light-weight, adaptive, cache partitioning mitigation that blocks the interference of I/O and CPU requests in the last-level cache.
On-Demand Trajectory Predictions for Interaction Aware Highway Driving
Venue: arXiv cs.RO 2020
Year: 2020

Highway driving places significant demands on human drivers and autonomous vehicles (AVs) alike due to high speeds and the complex interactions in dense traffic. Merging onto the highway poses additional challenges by limiting the amount of time available for decision-making. Predicting others' trajectories accurately and quickly is crucial to safely executing maneuvers. Many existing prediction methods based on neural networks have focused on modeling interactions to achieve better accuracy while assuming the existence of observation windows over 3s long. This paper proposes a novel probabilistic model for trajectory prediction that performs competitively with as little as 400ms of observations. The proposed model extends a deterministic car-following model to the probabilistic setting by treating model parameters as unknown random variables and introducing regularization terms. A realtime inference procedure is derived to estimate the parameters from observations in this new model. Experiments on dense traffic in the NGSIM dataset demonstrate that the proposed method achieves state-of-the-art performance with both highly constrained and more traditional observation windows.
Spatial Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Graph Convolutional Networks (GCNs) have recently become the primary choice for learning from graph-structured data, superseding hash fingerprints in representing chemical compounds. However, GCNs lack the ability to take into account the ordering of node neighbors, even when there is a geometric interpretation of the graph vertices that provides an order based on their spatial positions. To remedy this issue, we propose Spatial Graph Convolutional Network (SGCN) which uses spatial features to efficiently learn from graphs that can be naturally located in space. Our contribution is threefold: we propose a GCN-inspired architecture which (i) leverages node positions, (ii) is a proper generalization of both GCNs and Convolutional Neural Networks (CNNs), (iii) benefits from augmentation which further improves the performance and assures invariance with respect to the desired properties. Empirically, SGCN outperforms state-of-the-art graph-based methods on image classification and chemical tasks.
TransSent: Towards Generation of Structured Sentences with Discourse Marker
Venue: arXiv cs.CL 2020
Year: 2020

Structured sentences are important expressions in human writings and dialogues. Previous works on neural text generation fused semantic and structural information by encoding the entire sentence into a mixed hidden representation. However, when a generated sentence becomes complicated, the structure is difficult to be properly maintained. To alleviate this problem, we explicitly separate the modeling process of semantic and structural information. Intuitively, humans generate structured sentences by directly connecting discourses with discourse markers (such as and, but, etc.). Therefore, we propose a task that mimics this process, called discourse transfer. This task represents a structured sentence as (head discourse, discourse marker, tail discourse), and aims at tail discourse generation based on head discourse and discourse marker. We also propose a corresponding model called TransSent, which interprets the relationship between two discourses as a translation1 from the head discourse to the tail discourse in the embedding space. We experiment TransSent not only in discourse transfer task but also in free text generation and dialogue generation tasks. Automatic and human evaluation results show that TransSent can generate structured sentences with high quality, and has certain scalability in different tasks.
Learning in Text Streams: Discovery and Disambiguation of Entity and Relation Instances
Venue: arXiv cs.CL 2020
Year: 2020

We consider a scenario where an artificial agent is reading a stream of text composed of a set of narrations, and it is informed about the identity of some of the individuals that are mentioned in the text portion that is currently being read. The agent is expected to learn to follow the narrations, thus disambiguating mentions and discovering new individuals. We focus on the case in which individuals are entities and relations, and we propose an end-to-end trainable memory network that learns to discover and disambiguate them in an online manner, performing one-shot learning, and dealing with a small number of sparse supervisions. Our system builds a not-given-in-advance knowledge base, and it improves its skills while reading unsupervised text. The model deals with abrupt changes in the narration, taking into account their effects when resolving co-references. We showcase the strong disambiguation and discovery skills of our model on a corpus of Wikipedia documents and on a newly introduced dataset, that we make publicly available.
LOCALIS: Locally-adaptive Line Simplification for GPU-based Geographic Vector Data Visualization
Venue: arXiv cs.GR 2020
Year: 2020

Visualization of large vector line data is a core task in geographic and cartographic systems. Vector maps are often displayed at different cartographic generalization levels, traditionally by using several discrete levels-of-detail (LODs). This limits the generalization levels to a fixed and predefined set of LODs, and generally does not support smooth LOD transitions. However, fast GPUs and novel line rendering techniques can be exploited to integrate dynamic vector map LOD management into GPU-based algorithms for locally-adaptive line simplification and real-time rendering. We propose a new technique that interactively visualizes large line vector datasets at variable LODs. It is based on the Douglas-Peucker line simplification principle, generating an exhaustive set of line segments whose specific subsets represent the lines at any variable LOD. At run time, an appropriate and view-dependent error metric supports screen-space adaptive LOD levels and the display of the correct subset of line segments accordingly. Our implementation shows that we can simplify and display large line datasets interactively. We can successfully apply line style patterns, dynamic LOD selection lenses, and anti-aliasing techniques to our line rendering.
Detecting Parking Spaces in a Parcel using Satellite Images
Venue: arXiv cs.CV 2020
Year: 2020

Remote Sensing Images from satellites have been used in various domains for detecting and understanding structures on the ground surface. In this work, satellite images were used for localizing parking spaces and vehicles in parking lots for a given parcel using an RCNN based Neural Network Architectures. Parcel shapefiles and raster images from USGS image archive were used for developing images for both training and testing. Feature Pyramid based Mask RCNN yields average class accuracy of 97.56% for both parking spaces and vehicles
ISL: A novel approach for deep exploration
Venue: arXiv cs.LG 2020
Year: 2020

In this article we explore an alternative approach to address deep exploration and we introduce the ISL algorithm, which is efficient at performing deep exploration. Similarly to maximum entropy RL, we derive the algorithm by augmenting the traditional RL objective with a novel regularization term. A distinctive feature of our approach is that, as opposed to other works that tackle the problem of deep exploration, in our derivation both the learning equations and the exploration-exploitation strategy are derived in tandem as the solution to a well-posed optimization problem whose minimization leads to the optimal value function. Empirically we show that our method exhibits state of the art performance on a range of challenging deep-exploration benchmarks.