OpenRaiser/Intern-Atlas huggingface dataset:
Robust Algorithms for TSP and Steiner Tree
Venue: arXiv cs.DS 2020
Year: 2020

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution's cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.
Semi-Automating Knowledge Base Construction for Cancer Genetics
Venue: arXiv cs.CL 2020
Year: 2020

In this work, we consider the exponentially growing subarea of genetics in cancer. The need to synthesize and centralize this evidence for dissemination has motivated a team of physicians to manually construct and maintain a knowledge base that distills key results reported in the literature. This is a laborious process that entails reading through full-text articles to understand the study design, assess study quality, and extract the reported cancer risk estimates associated with particular hereditary cancer genes (i.e., penetrance). In this work, we propose models to automatically surface key elements from full-text cancer genetics articles, with the ultimate aim of expediting the manual workflow currently in place. We propose two challenging tasks that are critical for characterizing the findings reported cancer genetics studies: (i) Extracting snippets of text that describe \emph{ascertainment mechanisms}, which in turn inform whether the population studied may introduce bias owing to deviations from the target population; (ii) Extracting reported risk estimates (e.g., odds or hazard ratios) associated with specific germline mutations. The latter task may be viewed as a joint entity tagging and relation extraction problem. To train models for these tasks, we induce distant supervision over tokens and snippets in full-text articles using the manually constructed knowledge base. We propose and evaluate several model variants, including a transformer-based joint entity and relation extraction model to extract <germline mutation, risk-estimate>} pairs. We observe strong empirical performance, highlighting the practical potential for such models to aid KB construction in this space. We ablate components of our model, observing, e.g., that a joint model for <germline mutation, risk-estimate> fares substantially better than a pipelined approach.
On the (Parameterized) Complexity of Almost Stable Marriage
Venue: arXiv cs.GT 2020
Year: 2020

In the Stable Marriage problem. when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the "no blocking pair" condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, we find a matching whose size exceeds that of stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is "closest", in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.
Coordinated Coverage and Fault Tolerance using Fixed-Wing Unmanned Aerial Vehicles
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents an approach for deploying and maintaining a fleet of homogeneous fixed-wing unmanned aerial vehicles (UAVs) for all-time coverage of an area. Two approaches for loiter circle packing have been presented: square and hexagon packing, and the benefits of hexagon packing for minimizing the number of deployed UAVs have been shown. Based on the number of UAVs available and the desired loitering altitude, the proposed algorithm solves an optimization problem to calculate the centres of the loitering circles and the loitering radius for that altitude. The algorithm also incorporates fault recovery capacity in case of simultaneous multiple UAV failures. These failures could form clusters of survivor (active) UAVs over the area with no overall survivor information. The algorithm deploys a super-agent with a larger communication capacity at a higher altitude to recover from the failure. The super-agent collects the information of survivors, and updates the homogeneous radius and the locations of the loitering circles at the same altitude to restore the full coverage. The individual survivor UAVs are then informed and transit to the new loitering circles using Dubin's paths. The relationship with the extent of recoverable loss fractions of the deployed UAVs have been analysed for varying the initial loiter radii. Simulation results have been presented to demonstrate the applicability of the approach and compare the two presented packing approaches.
A Lightweight Isolation Mechanism for Secure Branch Predictors
Venue: arXiv cs.CR 2020
Year: 2020

Recently exposed vulnerabilities reveal the necessity to improve the security of branch predictors. Branch predictors record history about the execution of different programs, and such information from different processes are stored in the same structure and thus accessible to each other. This leaves the attackers with the opportunities for malicious training and malicious perception. Instead of flush-based or physical isolation of hardware resources, we want to achieve isolation of the content in these hardware tables with some lightweight processing using randomization as follows. (1) Content encoding. We propose to use hardware-based thread-private random numbers to encode the contents of the branch predictor tables (both direction and destination histories) which we call XOR-BP. Specifically, the data is encoded by XOR operation with the key before written in the table and decoded after read from the table. Such a mechanism obfuscates the information adding difficulties to cross-process or cross-privilege level analysis and perception. It achieves a similar effect of logical isolation but adds little in terms of space or time overheads. (2) Index encoding. We propose a randomized index mechanism of the branch predictor (Noisy-XOR-BP). Similar to the XOR-BP, another thread-private random number is used together with the branch instruction address as the input to compute the index of the branch predictor. This randomized indexing mechanism disrupts the correspondence between the branch instruction address and the branch predictor entry, thus increases the noise for malicious perception attacks. Our analyses using an FPGA-based RISC-V processor prototype and additional auxiliary simulations suggest that the proposed mechanisms incur a very small performance cost while providing strong protection.
Co-occurrence Based Texture Synthesis
Venue: arXiv cs.CV 2020
Year: 2020

As image generation techniques mature, there is a growing interest in explainable representations that are easy to understand and intuitive to manipulate. In this work, we turn to co-occurrence statistics, which have long been used for texture analysis, to learn a controllable texture synthesis model. We propose a fully convolutional generative adversarial network, conditioned locally on co-occurrence statistics, to generate arbitrarily large images while having local, interpretable control over the texture appearance. To encourage fidelity to the input condition, we introduce a novel differentiable co-occurrence loss that is integrated seamlessly into our framework in an end-to-end fashion. We demonstrate that our solution offers a stable, intuitive and interpretable latent representation for texture synthesis, which can be used to generate a smooth texture morph between different textures. We further show an interactive texture tool that allows a user to adjust local characteristics of the synthesized texture image using the co-occurrence values directly.
Quantifying the Impact on Software Complexity of Composable Inductive Programming using Zoea
Venue: arXiv cs.PL 2020
Year: 2020

Composable inductive programming as implemented in the Zoea programming language is a simple declarative approach to software development. At the language level it is evident that Zoea is significantly simpler than all mainstream languages. However, until now we have only had anecdotal evidence that software produced with Zoea is also simpler than equivalent software produced with conventional languages. This paper presents the results of a quantitative comparison of the software complexity of equivalent code implemented in Zoea and also in a conventional programming language. The study uses a varied set of programming tasks from a popular programming language chrestomathy. Results are presented for relative program complexity using two established metrics and also for relative program size. It was found that Zoea programs are approximately 50% the complexity of equivalent programs in a conventional language and on average equal in size. The results suggest that current programming languages (as opposed to software requirements) are the largest contributor to software complexity and that significant complexity could be avoided through an inductive programming approach.
Calibration of the internal and external parameters of wheeled robot mobile chasses and inertial measurement units based on nonlinear optimization
Venue: arXiv cs.RO 2020
Year: 2020

Mobile robot positioning, mapping, and navigation systems generally employ an inertial measurement unit (IMU) to obtain the acceleration and angular velocity of the robot. However, errors in the internal and external parameters of an IMU arising from defective calibration directly affect the accuracy of robot positioning and pose estimation. While this issue has been addressed by the mature internal reference calibration methods available for IMUs, external reference calibration methods between the IMU and the chassis of a mobile robot are lacking. This study addresses this issue by proposing a novel chassis-IMU internal and external parameter calibration algorithm based on nonlinear optimization, which is designed for robots equipped with cameras, IMUs, and wheel speed odometers, and functions under the premise of accurate calibrations for the internal parameters of the IMU and the internal and external parameters of the camera. All of the internal and external reference calibrations are conducted using the robot's existing equipment without the need for additional calibration aids. The feasibility of the method is verified by its application to a Mecanum wheel omnidirectional mobile platform as an example, as well as suitable for other type chassis of mobile robots. The proposed calibration method is thereby demonstrated to guarantee the accuracy of robot pose estimation.
The Bourgeois Gentleman, Engineering and Formal Methods
Venue: arXiv cs.SE 2020
Year: 2020

Industrial applications involving formal methods are still exceptions to the general rule. Lack of understanding, employees without proper education, difficulty to integrate existing development cycles, no explicit requirement from the market, etc. are explanations often heard for not being more formal. This article reports some experience about a game changer that is going to seamlessly integrate formal methods into safety critical systems engineering.
Context-Based Quotation Recommendation
Venue: arXiv cs.CL 2020
Year: 2020

While composing a new document, anything from a news article to an email or essay, authors often utilize direct quotes from a variety of sources. Although an author may know what point they would like to make, selecting an appropriate quote for the specific context may be time-consuming and difficult. We therefore propose a novel context-aware quote recommendation system which utilizes the content an author has already written to generate a ranked list of quotable paragraphs and spans of tokens from a given source document. We approach quote recommendation as a variant of open-domain question answering and adapt the state-of-the-art BERT-based methods from open-QA to our task. We conduct experiments on a collection of speech transcripts and associated news articles, evaluating models' paragraph ranking and span prediction performances. Our experiments confirm the strong performance of BERT-based methods on this task, which outperform bag-of-words and neural ranking baselines by more than 30% relative across all ranking metrics. Qualitative analyses show the difficulty of the paragraph and span recommendation tasks and confirm the quotability of the best BERT model's predictions, even if they are not the true selected quotes from the original news articles.
A Survey on Unknown Presentation Attack Detection for Fingerprint
Venue: arXiv cs.CV 2020
Year: 2020

Fingerprint recognition systems are widely deployed in various real-life applications as they have achieved high accuracy. The widely used applications include border control, automated teller machine (ATM), and attendance monitoring systems. However, these critical systems are prone to spoofing attacks (a.k.a presentation attacks (PA)). PA for fingerprint can be performed by presenting gummy fingers made from different materials such as silicone, gelatine, play-doh, ecoflex, 2D printed paper, 3D printed material, or latex. Biometrics Researchers have developed Presentation Attack Detection (PAD) methods as a countermeasure to PA. PAD is usually done by training a machine learning classifier for known attacks for a given dataset, and they achieve high accuracy in this task. However, generalizing to unknown attacks is an essential problem from applicability to real-world systems, mainly because attacks cannot be exhaustively listed in advance. In this survey paper, we present a comprehensive survey on existing PAD algorithms for fingerprint recognition systems, specifically from the standpoint of detecting unknown PAD. We categorize PAD algorithms, point out their advantages/disadvantages, and future directions for this area.
Detecting Forged Facial Videos using convolutional neural network
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose to detect forged videos, of faces, in online videos. To facilitate this detection, we propose to use smaller (fewer parameters to learn) convolutional neural networks (CNN), for a data-driven approach to forged video detection. To validate our approach, we investigate the FaceForensics public dataset detailing both frame-based and video-based results. The proposed method is shown to outperform current state of the art. We also perform an ablation study, analyzing the impact of batch size, number of filters, and number of network layers on the accuracy of detecting forged videos.
On Efficient Connectivity-Preserving Transformations in a Grid
Venue: arXiv cs.DS 2020
Year: 2020

We consider a discrete system of $n$ devices lying on a 2-dimensional square grid and forming an initial connected shape $S_I$. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step. We study the problem of transforming $S_I$ into a given connected target shape $S_F$ of the same number of devices, via a finite sequence of \emph{line moves}. Our focus is on designing \emph{centralised} transformations aiming at \emph{minimising the total number of moves} subject to the constraint of \emph{preserving connectivity} of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the \emph{associated graphs} of $ S_I $ and $ S_F $ are isomorphic to a Hamiltonian line. In particular, our transformations make $ O(n \log n $) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving \emph{universal transformation} that can transform any initial connected shape $ S_I $ into any target connected shape $ S_F $, through a sequence of $O(n\sqrt{n})$ moves. Finally, we establish $Ω(n \log n)$ lower bounds for two restricted sets of transformations. These are the first lower bounds for this model and are matching the best known $ O(n \log n) $ upper bounds.
Attack-aware Security Function Chain Reordering
Venue: arXiv cs.NI 2020
Year: 2020

Attack-awareness recognizes self-awareness for security systems regarding the occurring attacks. More frequent and intense attacks on cloud and network infrastructures are pushing security systems to the limit. With the end of Moore's Law, merely scaling against these attacks is no longer economically justified. Previous works have already dealt with the adoption of Software-defined Networking and Network Function Virtualization in security systems and used both approaches to optimize performance by the intelligent placement of security functions. However, these works have not yet considered the sequence in which traffic passes through these functions. In this work, we make a case for the need to take this ordering into account by showing its impact. We then propose a reordering framework and analyze what aspects are necessary for modeling security service function chains and making decisions regarding the order based on those models. We show the impact of the order and validate our framework in an evaluation environment. The effect can extend to multiple orders of magnitude, and the framework's evaluation proves the feasibility of our concept.
A socio-technical framework for digital contact tracing
Venue: arXiv cs.CY 2020
Year: 2020

In their efforts to tackle the COVID-19 crisis, decision makers are considering the development and use of smartphone applications for contact tracing. Even though these applications differ in technology and methods, there is an increasing concern about their implications for privacy and human rights. Here we propose a framework to evaluate their suitability in terms of impact on the users, employed technology and governance methods. We illustrate its usage with three applications, and with the European Data Protection Board (EDPB) guidelines, highlighting their limitations.
T-VSE: Transformer-Based Visual Semantic Embedding
Venue: arXiv cs.CV 2020
Year: 2020

Transformer models have recently achieved impressive performance on NLP tasks, owing to new algorithms for self-supervised pre-training on very large text corpora. In contrast, recent literature suggests that simple average word models outperform more complicated language models, e.g., RNNs and Transformers, on cross-modal image/text search tasks on standard benchmarks, like MS COCO. In this paper, we show that dataset scale and training strategy are critical and demonstrate that transformer-based cross-modal embeddings outperform word average and RNN-based embeddings by a large margin, when trained on a large dataset of e-commerce product image-title pairs.
VecQ: Minimal Loss DNN Model Compression With Vectorized Weight Quantization
Venue: arXiv cs.CV 2020
Year: 2020

Quantization has been proven to be an effective method for reducing the computing and/or storage cost of DNNs. However, the trade-off between the quantization bitwidth and final accuracy is complex and non-convex, which makes it difficult to be optimized directly. Minimizing direct quantization loss (DQL) of the coefficient data is an effective local optimization method, but previous works often neglect the accurate control of the DQL, resulting in a higher loss of the final DNN model accuracy. In this paper, we propose a novel metric called Vector Loss. Based on this new metric, we develop a new quantization solution called VecQ, which can guarantee minimal direct quantization loss and better model accuracy. In addition, in order to speed up the proposed quantization process during model training, we accelerate the quantization process with a parameterized probability estimation method and template-based derivation calculation. We evaluate our proposed algorithm on MNIST, CIFAR, ImageNet, IMDB movie review and THUCNews text data sets with numerical DNN models. The results demonstrate that our proposed quantization solution is more accurate and effective than the state-of-the-art approaches yet with more flexible bitwidth support. Moreover, the evaluation of our quantized models on Saliency Object Detection (SOD) tasks maintains comparable feature extraction quality with up to 16$\times$ weight size reduction.
A tropical geometry approach to BIBO stability
Venue: arXiv cs.CG 2020
Year: 2020

Given a Laurent polynomial F and its amoeba AF. We relate here the question of the BIBO stability of a multi linear time invariant system with a rational transfer function. We formulate very simple criteria for BIBO strong or weak stability in terms of the position of the origin 0 with respect to the amoeba AF and suggest an algorithmic procedure in order to test such property.
DDD20 End-to-End Event Camera Driving Dataset: Fusing Frames and Events with Deep Learning for Improved Steering Prediction
Venue: arXiv cs.CV 2020
Year: 2020

Neuromorphic event cameras are useful for dynamic vision problems under difficult lighting conditions. To enable studies of using event cameras in automobile driving applications, this paper reports a new end-to-end driving dataset called DDD20. The dataset was captured with a DAVIS camera that concurrently streams both dynamic vision sensor (DVS) brightness change events and active pixel sensor (APS) intensity frames. DDD20 is the longest event camera end-to-end driving dataset to date with 51h of DAVIS event+frame camera and vehicle human control data collected from 4000km of highway and urban driving under a variety of lighting conditions. Using DDD20, we report the first study of fusing brightness change events and intensity frame data using a deep learning approach to predict the instantaneous human steering wheel angle. Over all day and night conditions, the explained variance for human steering prediction from a Resnet-32 is significantly better from the fused DVS+APS frames (0.88) than using either DVS (0.67) or APS (0.77) data alone.