OpenRaiser/Intern-Atlas huggingface dataset:
Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
Venue: arXiv cs.NE 2020
Year: 2020

Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic Weighted Vertex Cover problem and analyze the runtime performances of the well-studied algorithms Randomized Local Search and (1+1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1+1) EA with 1/5-th Rule requires pseudo-polynomial expected runtime.
Fixed-parameter tractable algorithms for Tracking Shortest Paths
Venue: arXiv cs.DS 2020
Year: 2020

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System help to show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.
A Formal Development Cycle for Security Engineering in Isabelle
Venue: arXiv cs.CR 2020
Year: 2020

In this paper, we show a security engineering process based on a formal notion of refinement fully formalized in the proof assistant Isabelle. This Refinement-Risk Cycle focuses on attack analysis and security refinement supported by interactive theorem proving. Since we use a fully formalized model of infrastructures with actors and policies we can support a novel way of formal security refinement for system specifications. This formal process is built practically as an extension to the Isabelle Infrastructure framework with attack trees. We define a formal notion of refinement on infrastructure models. Thanks to the formal foundation of Kripke structures and branching time temporal logic in the Isabelle Infrastructure framework, these stepwise transformations can be interleaved with attack tree analysis thus providing a fully formal security engineering framework. The process is illustrated on an IoT healthcare case study introducing GDPR requirements and blockchain.
Approximating Surfaces in $R^3$ by Meshes with Guaranteed Regularity
Venue: arXiv cs.CG 2020
Year: 2020

We study the problem of approximating a surface $F$ in $R^3$ by a high quality mesh, a piecewise-flat triangulated surface whose triangles are as close as possible to equilateral. The MidNormal algorithm generates a triangular mesh that is guaranteed to have angles in the interval $[49.1^o, 81.8^o]$. As the mesh size $e\rightarrow 0$, the mesh converges pointwise to $F$ through surfaces that are isotopic to $F$. The GradNormal algorithm gives a piecewise-$C^1$ approximation of $F$, with angles in the interval $[35.2^o, 101.5^o]$ as $e\rightarrow 0$. Previously achieved angle bounds were in the interval $[30^o, 120^o]$.
Perception as prediction using general value functions in autonomous driving applications
Venue: arXiv cs.RO 2020
Year: 2020

We propose and demonstrate a framework called perception as prediction for autonomous driving that uses general value functions (GVFs) to learn predictions. Perception as prediction learns data-driven predictions relating to the impact of actions on the agent's perception of the world. It also provides a data-driven approach to predict the impact of the anticipated behavior of other agents on the world without explicitly learning their policy or intentions. We demonstrate perception as prediction by learning to predict an agent's front safety and rear safety with GVFs, which encapsulate anticipation of the behavior of the vehicle in front and in the rear, respectively. The safety predictions are learned through random interactions in a simulated environment containing other agents. We show that these predictions can be used to produce similar control behavior to an LQR-based controller in an adaptive cruise control problem as well as provide advanced warning when the vehicle behind is approaching dangerously. The predictions are compact policy-based predictions that support prediction of the long term impact on safety when following a given policy. We analyze two controllers that use the learned predictions in a racing simulator to understand the value of the predictions and demonstrate their use in the real-world on a Clearpath Jackal robot and an autonomous vehicle platform.
A Geometric View of the Service Rates of Codes Problem and its Application to the Service Rate of the First Order Reed-Muller Codes
Venue: arXiv cs.IT 2020
Year: 2020

Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the storage system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing approaches is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.
Towards a Framework for Certification of Reliable Autonomous Systems
Venue: arXiv cs.SE 2020
Year: 2020

A computational system is called autonomous if it is able to make its own decisions, or take its own actions, without human supervision or control. The capability and spread of such systems have reached the point where they are beginning to touch much of everyday life. However, regulators grapple with how to deal with autonomous systems, for example how could we certify an Unmanned Aerial System for autonomous use in civilian airspace? We here analyse what is needed in order to provide verified reliable behaviour of an autonomous system, analyse what can be done as the state-of-the-art in automated verification, and propose a roadmap towards developing regulatory guidelines, including articulating challenges to researchers, to engineers, and to regulators. Case studies in seven distinct domains illustrate the article.
End-to-End Vision-Based Adaptive Cruise Control (ACC) Using Deep Reinforcement Learning
Venue: arXiv cs.CV 2020
Year: 2020

This paper presented a deep reinforcement learning method named Double Deep Q-networks to design an end-to-end vision-based adaptive cruise control (ACC) system. A simulation environment of a highway scene was set up in Unity, which is a game engine that provided both physical models of vehicles and feature data for training and testing. Well-designed reward functions associated with the following distance and throttle/brake force were implemented in the reinforcement learning model for both internal combustion engine (ICE) vehicles and electric vehicles (EV) to perform adaptive cruise control. The gap statistics and total energy consumption are evaluated for different vehicle types to explore the relationship between reward functions and powertrain characteristics. Compared with the traditional radar-based ACC systems or human-in-the-loop simulation, the proposed vision-based ACC system can generate either a better gap regulated trajectory or a smoother speed trajectory depending on the preset reward function. The proposed system can be well adaptive to different speed trajectories of the preceding vehicle and operated in real-time.
On simulation in automata networks
Venue: arXiv cs.CC 2020
Year: 2020

An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map $f:Q^n\rightarrow Q^n$. In this paper we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph. Our contributions are the following. For non-Boolean alphabets and for any network size, there are intrinsically non-sequential transformations (i.e. that can not be obtained as composition of sequential updates of some network). Moreover there is no universal automaton network that can produce all non-bijective functions via compositions of asynchronous updates. On the other hand, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet. We also characterize the set of functions that are generated by non-bijective sequential updates. Following Tchuente, we characterize the interaction graphs $D$ whose semigroup of transformations is the full semigroup of transformations on $Q^n$, and we show that they are the same if we force either sequential updates only, or all asynchronous updates.
A 3D Reactive Navigation Algorithm for Mobile Robots by Using Tentacle-Based Sampling
Venue: arXiv cs.RO 2020
Year: 2020

This paper introduces a reactive navigation framework for mobile robots in 3-dimensional (3D) space. The proposed approach does not rely on the global map information and achieves fast navigation by employing a tentacle based sampling and their heuristic evaluations on-the-fly. This reactive nature of the approach comes from the prior arrangement of navigation points on tentacles (parametric contours) to sample the navigation space. These tentacles are evaluated at each time-step, based on heuristic features such as closeness to the goal, previous tentacle preferences and nearby obstacles in a robot-centered 3D grid. Then, the navigable sampling point on the selected tentacle is passed to a controller for the motion execution. The proposed framework does not only extend its 2D tentacle-based counterparts into 3D, but also introduces offline and online parameters, whose tuning provides versatility and adaptability of the algorithm to work in unknown environments. To demonstrate the superior performance of the proposed algorithm over a state-of-art method, the statistical results from physics-based simulations on various maps are presented. The video of the work is available at https://youtu.be/rrF7wHCz-0M.
TiFL: A Tier-based Federated Learning System
Venue: arXiv cs.LG 2020
Year: 2020

Federated Learning (FL) enables learning a shared model across many clients without violating the privacy requirements. One of the key attributes in FL is the heterogeneity that exists in both resource and data due to the differences in computation and communication capacity, as well as the quantity and content of data among different clients. We conduct a case study to show that heterogeneity in resource and data has a significant impact on training time and model accuracy in conventional FL systems. To this end, we propose TiFL, a Tier-based Federated Learning System, which divides clients into tiers based on their training performance and selects clients from the same tier in each training round to mitigate the straggler problem caused by heterogeneity in resource and data quantity. To further tame the heterogeneity caused by non-IID (Independent and Identical Distribution) data and resources, TiFL employs an adaptive tier selection approach to update the tiering on-the-fly based on the observed training performance and accuracy overtime. We prototype TiFL in a FL testbed following Google's FL architecture and evaluate it using popular benchmarks and the state-of-the-art FL benchmark LEAF. Experimental evaluation shows that TiFL outperforms the conventional FL in various heterogeneous conditions. With the proposed adaptive tier selection policy, we demonstrate that TiFL achieves much faster training performance while keeping the same (and in some cases - better) test accuracy across the board.
Domain Adaptive Medical Image Segmentation via Adversarial Learning of Disease-Specific Spatial Patterns
Venue: arXiv cs.CV 2020
Year: 2020

In medical imaging, the heterogeneity of multi-centre data impedes the applicability of deep learning-based methods and results in significant performance degradation when applying models in an unseen data domain, e.g. a new centreor a new scanner. In this paper, we propose an unsupervised domain adaptation framework for boosting image segmentation performance across multiple domains without using any manual annotations from the new target domains, but by re-calibrating the networks on few images from the target domain. To achieve this, we enforce architectures to be adaptive to new data by rejecting improbable segmentation patterns and implicitly learning through semantic and boundary information, thus to capture disease-specific spatial patterns in an adversarial optimization. The adaptation process needs continuous monitoring, however, as we cannot assume the presence of ground-truth masks for the target domain, we propose two new metrics to monitor the adaptation process, and strategies to train the segmentation algorithm in a stable fashion. We build upon well-established 2D and 3D architectures and perform extensive experiments on three cross-centre brain lesion segmentation tasks, involving multicentre public and in-house datasets. We demonstrate that recalibrating the deep networks on a few unlabeled images from the target domain improves the segmentation accuracy significantly.
GeoRocket: A scalable and cloud-based data store for big geospatial files
Venue: arXiv cs.DC 2020
Year: 2020

We present GeoRocket, a software for the management of very large geospatial datasets in the cloud. GeoRocket employs a novel way to handle arbitrarily large datasets by splitting them into chunks that are processed individually. The software has a modern reactive architecture and makes use of existing services including Elasticsearch and storage back ends such as MongoDB or Amazon S3. GeoRocket is schema-agnostic and supports a wide range of heterogeneous geospatial file formats. It is also format-preserving and does not alter imported data in any way. The main benefits of GeoRocket are its performance, scalability, and usability, which make it suitable for a number of scientific and commercial use cases dealing with very high data volumes, complex datasets, and high velocity (Big Data). GeoRocket also provides many opportunities for further research in the area of geospatial data management.
AI-Powered GUI Attack and Its Defensive Methods
Venue: arXiv cs.CR 2020
Year: 2020

Since the first Graphical User Interface (GUI) prototype was invented in the 1970s, GUI systems have been deployed into various personal computer systems and server platforms. Recently, with the development of artificial intelligence (AI) technology, malicious malware powered by AI is emerging as a potential threat to GUI systems. This type of AI-based cybersecurity attack, targeting at GUI systems, is explored in this paper. It is twofold: (1) A malware is designed to attack the existing GUI system by using AI-based object recognition techniques. (2) Its defensive methods are discovered by generating adversarial examples and other methods to alleviate the threats from the intelligent GUI attack. The results have shown that a generic GUI attack can be implemented and performed in a simple way based on current AI techniques and its countermeasures are temporary but effective to mitigate the threats of GUI attack so far.
Lagrangian Duality for Constrained Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

This paper explores the potential of Lagrangian duality for learning applications that feature complex constraints. Such constraints arise in many science and engineering domains, where the task amounts to learning optimization problems which must be solved repeatedly and include hard physical and operational constraints. The paper also considers applications where the learning task must enforce constraints on the predictor itself, either because they are natural properties of the function to learn or because it is desirable from a societal standpoint to impose them. This paper demonstrates experimentally that Lagrangian duality brings significant benefits for these applications. In energy domains, the combination of Lagrangian duality and deep learning can be used to obtain state-of-the-art results to predict optimal power flows, in energy systems, and optimal compressor settings, in gas networks. In transprecision computing, Lagrangian duality can complement deep learning to impose monotonicity constraints on the predictor without sacrificing accuracy. Finally, Lagrangian duality can be used to enforce fairness constraints on a predictor and obtain state-of-the-art results when minimizing disparate treatments.
Coordinating Complementary Waveforms for Suppressing Range Sidelobes in a Doppler Band
Venue: arXiv cs.IT 2020
Year: 2020

We present a general method for constructing radar transmit pulse trains and receive filters for which the radar point-spread function in delay and Doppler (radar cross-ambiguity function) is essentially free of range sidelobes inside a Doppler interval around the zero-Doppler axis. The transmit and receive pulse trains are constructed by coordinating the transmission of a pair of Golay complementary waveforms across time according to zeros and ones in a binary sequence $P$. In the receive pulse train filter, each waveform is weighted according to an element from another sequence $Q$. We show that the spectrum of essentially the product of $P$ and $Q$ sequences controls the size of the range sidelobes of the cross-ambiguity function. We annihilate the range sidelobes at low Doppler by designing the $(P,Q)$ pairs such that their products have high-order spectral nulls around zero Doppler. We specify the subspace, along with a basis, for such sequences, thereby providing a general way of constructing $(P,Q)$ pairs. At the same time, the signal-to-noise ratio (SNR) at the receiver output, for a single point target in white noise, depends only on the choice of $Q$. By jointly designing the transmit-receive sequences $(P,Q)$, we can maximize the output SNR subject to achieving a given order of the spectral null. The proposed $(P,Q)$ constructions can also be extended to sequences consisting of more than two complementary waveforms; this is done explicitly for a library of Golay complementary quads. Finally, we extend the construction of $(P,Q)$ pairs to multiple-input-multiple-output (MIMO) radar, by designing transmit-receive pairs of paraunitary waveform matrices whose matrix-valued cross-ambiguity function is essentially free of range sidelobes inside a Doppler interval around the zero-Doppler axis.
A Visual Analytics Framework for Reviewing Streaming Performance Data
Venue: arXiv cs.DC 2020
Year: 2020

Understanding and tuning the performance of extreme-scale parallel computing systems demands a streaming approach due to the computational cost of applying offline algorithms to vast amounts of performance log data. Analyzing large streaming data is challenging because the rate of receiving data and limited time to comprehend data make it difficult for the analysts to sufficiently examine the data without missing important changes or patterns. To support streaming data analysis, we introduce a visual analytic framework comprising of three modules: data management, analysis, and interactive visualization. The data management module collects various computing and communication performance metrics from the monitored system using streaming data processing techniques and feeds the data to the other two modules. The analysis module automatically identifies important changes and patterns at the required latency. In particular, we introduce a set of online and progressive analysis methods for not only controlling the computational costs but also helping analysts better follow the critical aspects of the analysis results. Finally, the interactive visualization module provides the analysts with a coherent view of the changes and patterns in the continuously captured performance data. Through a multi-faceted case study on performance analysis of parallel discrete-event simulation, we demonstrate the effectiveness of our framework for identifying bottlenecks and locating outliers.
DUMA: Reading Comprehension with Transposition Thinking
Venue: arXiv cs.CL 2020
Year: 2020

Multi-choice Machine Reading Comprehension (MRC) requires model to decide the correct answer from a set of answer options when given a passage and a question. Thus in addition to a powerful Pre-trained Language Model (PrLM) as encoder, multi-choice MRC especially relies on a matching network design which is supposed to effectively capture the relationships among the triplet of passage, question and answers. While the newer and more powerful PrLMs have shown their mightiness even without the support from a matching network, we propose a new DUal Multi-head Co-Attention (DUMA) model, which is inspired by human's transposition thinking process solving the multi-choice MRC problem: respectively considering each other's focus from the standpoint of passage and question. The proposed DUMA has been shown effective and is capable of generally promoting PrLMs. Our proposed method is evaluated on two benchmark multi-choice MRC tasks, DREAM and RACE, showing that in terms of powerful PrLMs, DUMA can still boost the model to reach new state-of-the-art performance.