OpenRaiser/Intern-Atlas huggingface dataset:
Proof of Concept: Automatic Type Recognition
Venue: arXiv cs.CV 2020
Year: 2020

The type used to print an early modern book can give scholars valuable information about the time and place of its production as well as its producer. Recognizing such type is currently done manually using both the character shapes of `M' or `Qu' and the size of the total type to look it up in a large reference work. This is a reliable method, but it is also slow and requires specific skills. We investigate the performance of type classification and type retrieval using a newly created dataset consisting of easy and difficult types used in early printed books. For type classification, we rely on a deep Convolutional Neural Network (CNN) originally used for font-group classification while we use a common writer identification method for the retrieval case. We show that in both scenarios, easy types can be classified/retrieved with a high accuracy while difficult cases are indeed difficult.
An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane
Venue: arXiv cs.CG 2020
Year: 2020

The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions that has exciting applications in machine learning. For discrete distributions, the problem of computing this distance can be expressed in terms of finding a minimum-cost perfect matching on a complete bipartite graph given by two multisets of points $A,B \subset \mathbb{R}^2$, with $|A|=|B|=n$, where the ground distance between any two points is the squared Euclidean distance between them. Although there is a near-linear time relative $\varepsilon$-approximation algorithm for the case where the ground distance is Euclidean (Sharathkumar and Agarwal, JACM 2020), all existing relative $\varepsilon$-approximation algorithms for the RMS distance take $Ω(n^{3/2})$ time. This is primarily because, unlike Euclidean distance, squared Euclidean distance is not a metric. In this paper, for the RMS distance, we present a new $\varepsilon$-approximation algorithm that runs in $O(n^{5/4}\mathrm{poly}\{\log n,1/\varepsilon\})$ time. Our algorithm is inspired by a recent approach for finding a minimum-cost perfect matching in bipartite planar graphs (Asathulla et al., TALG 2020). Their algorithm depends heavily on the existence of sub-linear sized vertex separators as well as shortest path data structures that require planarity. Surprisingly, we are able to design a similar algorithm for a complete geometric graph that is far from planar and does not have any vertex separators. Central components of our algorithm include a quadtree-based distance that approximates the squared Euclidean distance and a data structure that supports both Hungarian search and augmentation in sub-linear time.
Focus-and-Expand: Training Guidance Through Gradual Manipulation of Input Features
Venue: arXiv cs.LG 2020
Year: 2020

We present a simple and intuitive Focus-and-eXpand (\fax) method to guide the training process of a neural network towards a specific solution. Optimizing a neural network is a highly non-convex problem. Typically, the space of solutions is large, with numerous possible local minima, where reaching a specific minimum depends on many factors. In many cases, however, a solution which considers specific aspects, or features, of the input is desired. For example, in the presence of bias, a solution that disregards the biased feature is a more robust and accurate one. Drawing inspiration from Parameter Continuation methods, we propose steering the training process to consider specific features in the input more than others, through gradual shifts in the input domain. \fax extracts a subset of features from each input data-point, and exposes the learner to these features first, Focusing the solution on them. Then, by using a blending/mixing parameter $α$ it gradually eXpands the learning process to include all features of the input. This process encourages the consideration of the desired features more than others. Though not restricted to this field, we quantitatively evaluate the effectiveness of our approach on various Computer Vision tasks, and achieve state-of-the-art bias removal, improvements to an established augmentation method, and two examples of improvements to image classification tasks. Through these few examples we demonstrate the impact this approach potentially carries for a wide variety of problems, which stand to gain from understanding the solution landscape.
Covidex: Neural Ranking Models and Keyword Search Infrastructure for the COVID-19 Open Research Dataset
Venue: arXiv cs.IR 2020
Year: 2020

We present Covidex, a search engine that exploits the latest neural ranking models to provide information access to the COVID-19 Open Research Dataset curated by the Allen Institute for AI. Our system has been online and serving users since late March 2020. The Covidex is the user application component of our three-pronged strategy to develop technologies for helping domain experts tackle the ongoing global pandemic. In addition, we provide robust and easy-to-use keyword search infrastructure that exploits mature fusion-based methods as well as standalone neural ranking models that can be incorporated into other applications. These techniques have been evaluated in the ongoing TREC-COVID challenge: Our infrastructure and baselines have been adopted by many participants, including some of the highest-scoring runs in rounds 1, 2, and 3. In round 3, we report the highest-scoring run that takes advantage of previous training data and the second-highest fully automatic run.
Empty Rainbow Triangles in $k$-colored Point Sets
Venue: arXiv cs.CG 2020
Year: 2020

Let $S$ be a set of $n$ points in general position in the plane. Suppose that each point of $S$ has been assigned one of $k \ge 3$ possible colors and that there is the same number, $m$, of points of each color class. A polygon with vertices on $S$ is empty if it does not contain points of $S$ in its interior; and it is rainbow if all its vertices have different colors. Let $f(k,m)$ be the minimum number of empty rainbow triangles determined by $S$. In this paper we give tight asymptotic bounds for this function. Furthermore, we show that $S$ may not determine an empty rainbow quadrilateral for some arbitrarily large values of $k$ and $m$.
Image De-Quantization Using Generative Models as Priors
Venue: arXiv cs.CV 2020
Year: 2020

Image quantization is used in several applications aiming in reducing the number of available colors in an image and therefore its size. De-quantization is the task of reversing the quantization effect and recovering the original multi-chromatic level image. Existing techniques achieve de-quantization by imposing suitable constraints on the ideal image in order to make the recovery problem feasible since it is otherwise ill-posed. Our goal in this work is to develop a de-quantization mechanism through a rigorous mathematical analysis which is based on the classical statistical estimation theory. In this effort we incorporate generative modeling of the ideal image as a suitable prior information. The resulting technique is simple and capable of de-quantizing successfully images that have experienced severe quantization effects. Interestingly, our method can recover images even if the quantization process is not exactly known and contains unknown parameters.
How to Morph Graphs on the Torus
Venue: arXiv cs.CG 2020
Year: 2020

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in $O(n^{1+ω/2})$ time, where $ω$ is the matrix multiplication exponent, and the computed morph consists of $O(n)$ parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns' original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte's spring embedding theorem to torus graphs.
A Survey on Security Attacks and Defense Techniques for Connected and Autonomous Vehicles
Venue: arXiv cs.CR 2020
Year: 2020

Autonomous Vehicle has been transforming intelligent transportation systems. As telecommunication technology improves, autonomous vehicles are getting connected to each other and to infrastructures, forming Connected and Autonomous Vehicles (CAVs). CAVs will help humans achieve safe, efficient, and autonomous transportation systems. However, CAVs will face significant security challenges because many of their components are vulnerable to attacks, and a successful attack on a CAV may have significant impacts on other CAVs and infrastructures due to their communications. In this paper, we conduct a survey on 184 papers from 2000 to 2020 to understand state-of-the-art CAV attacks and defense techniques. This survey first presents a comprehensive overview of security attacks and their corresponding countermeasures on CAVs. We then discuss the details of attack models based on the targeted CAV components of attacks, access requirements, and attack motives. Finally, we identify some current research challenges and trends from the perspectives of both academic research and industrial development. Based on our studies of academic literature and industrial publications, we have not found any strong connection between academic research and industry's implementation on CAV-related security issues. While efforts from CAV manufacturers to secure CAVs have been reported, there is no evidence to show that CAVs on the market have the ability to defend against some novel attack models that the research community has recently found. This survey may give researchers and engineers a better understanding of the current status and trend of CAV security for CAV future improvement.
Memory based fusion for multi-modal deep learning
Venue: arXiv cs.LG 2020
Year: 2020

The use of multi-modal data for deep machine learning has shown promise when compared to uni-modal approaches with fusion of multi-modal features resulting in improved performance in several applications. However, most state-of-the-art methods use naive fusion which processes feature streams independently, ignoring possible long-term dependencies within the data during fusion. In this paper, we present a novel Memory based Attentive Fusion layer, which fuses modes by incorporating both the current features and longterm dependencies in the data, thus allowing the model to understand the relative importance of modes over time. We introduce an explicit memory block within the fusion layer which stores features containing long-term dependencies of the fused data. The feature inputs from uni-modal encoders are fused through attentive composition and transformation followed by naive fusion of the resultant memory derived features with layer inputs. Following state-of-the-art methods, we have evaluated the performance and the generalizability of the proposed fusion approach on two different datasets with different modalities. In our experiments, we replace the naive fusion layer in benchmark networks with our proposed layer to enable a fair comparison. Experimental results indicate that the MBAF layer can generalise across different modalities and networks to enhance fusion and improve performance.
Using LSTM and SARIMA Models to Forecast Cluster CPU Usage
Venue: arXiv cs.LG 2020
Year: 2020

As large scale cloud computing centers become more popular than individual servers, predicting future resource demand need has become an important problem. Forecasting resource need allows public cloud providers to proactively allocate or deallocate resources for cloud services. This work seeks to predict one resource, CPU usage, over both a short term and long term time scale. To gain insight into the model characteristics that best support specific tasks, we consider two vastly different architectures: the historically relevant SARIMA model and the more modern neural network, LSTM model. We apply these models to Azure data resampled to 20 minutes per data point with the goal of predicting usage over the next hour for the short-term task and for the next three days for the long-term task. The SARIMA model outperformed the LSTM for the long term prediction task, but performed poorer on the short term task. Furthermore, the LSTM model was more robust, whereas the SARIMA model relied on the data meeting certain assumptions about seasonality.
TrashCan: A Semantically-Segmented Dataset towards Visual Detection of Marine Debris
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents TrashCan, a large dataset comprised of images of underwater trash collected from a variety of sources, annotated both using bounding boxes and segmentation labels, for development of robust detectors of marine debris. The dataset has two versions, TrashCan-Material and TrashCan-Instance, corresponding to different object class configurations. The eventual goal is to develop efficient and accurate trash detection methods suitable for onboard robot deployment. Along with information about the construction and sourcing of the TrashCan dataset, we present initial results of instance segmentation from Mask R-CNN and object detection from Faster R-CNN. These do not represent the best possible detection results but provides an initial baseline for future work in instance segmentation and object detection on the TrashCan dataset.
Conformal Rule-Based Multi-label Classification
Venue: arXiv cs.LG 2020
Year: 2020

We advocate the use of conformal prediction (CP) to enhance rule-based multi-label classification (MLC). In particular, we highlight the mutual benefit of CP and rule learning: Rules have the ability to provide natural (non-)conformity scores, which are required by CP, while CP suggests a way to calibrate the assessment of candidate rules, thereby supporting better predictions and more elaborate decision making. We illustrate the potential usefulness of calibrated conformity scores in a case study on lazy multi-label rule learning.
Enhanced detection of fetal pose in 3D MRI by Deep Reinforcement Learning with physical structure priors on anatomy
Venue: arXiv cs.CV 2020
Year: 2020

Fetal MRI is heavily constrained by unpredictable and substantial fetal motion that causes image artifacts and limits the set of viable diagnostic image contrasts. Current mitigation of motion artifacts is predominantly performed by fast, single-shot MRI and retrospective motion correction. Estimation of fetal pose in real time during MRI stands to benefit prospective methods to detect and mitigate fetal motion artifacts where inferred fetal motion is combined with online slice prescription with low-latency decision making. Current developments of deep reinforcement learning (DRL), offer a novel approach for fetal landmarks detection. In this task 15 agents are deployed to detect 15 landmarks simultaneously by DRL. The optimization is challenging, and here we propose an improved DRL that incorporates priors on physical structure of the fetal body. First, we use graph communication layers to improve the communication among agents based on a graph where each node represents a fetal-body landmark. Further, additional reward based on the distance between agents and physical structures such as the fetal limbs is used to fully exploit physical structure. Evaluation of this method on a repository of 3-mm resolution in vivo data demonstrates a mean accuracy of landmark estimation within 10 mm of ground truth as 87.3%, and a mean error of 6.9 mm. The proposed DRL for fetal pose landmark search demonstrates a potential clinical utility for online detection of fetal motion that guides real-time mitigation of motion artifacts as well as health diagnosis during MRI of the pregnant mother.
Feasibility of Cross-Chain Payment with Success Guarantees
Venue: arXiv cs.DC 2020
Year: 2020

We consider the problem of cross-chain payment whereby customers of different escrows---implemented by a bank or a blockchain smart contract---successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment problems did not require this success, or any form of progress. We demonstrate that it is possible to solve this problem when assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time, but impossible to solve without assuming synchrony. Yet, we solve a weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.
A Product Channel Attack to Wireless Physical Layer Security
Venue: arXiv cs.IT 2020
Year: 2020

We propose a novel attack that compromises the physical layer security of downlink (DL) communications in wireless systems. This technique is based on the transmission of a slowly-varying random symbol by the eavesdropper during its uplink transmission, so that the equivalent fading channel observed at the base station (BS) has a larger variance. Then, the BS designs the secure DL transmission under the assumption that the eavesdropper's channel experiences a larger fading severity than in reality. We show that this approach can lead the BS to transmit to Bob at a rate larger than the secrecy capacity, thus compromising the system secure operation. Our analytical results, corroborated by simulations, show that the use of multiple antennas at the BS may partially alleviate but not immunize against these type of attacks.
VIPriors Object Detection Challenge
Venue: arXiv cs.CV 2020
Year: 2020

This paper is a brief report to our submission to the VIPriors Object Detection Challenge. Object Detection has attracted many researchers' attention for its full application, but it is still a challenging task. In this paper, we study analysis the characteristics of the data, and an effective data enhancement method is proposed. We carefully choose the model which is more suitable for training from scratch. We benefit a lot from using softnms and model fusion skillfully.
Graph topology inference benchmarks for machine learning
Venue: arXiv cs.LG 2020
Year: 2020

Graphs are nowadays ubiquitous in the fields of signal processing and machine learning. As a tool used to express relationships between objects, graphs can be deployed to various ends: I) clustering of vertices, II) semi-supervised classification of vertices, III) supervised classification of graph signals, and IV) denoising of graph signals. However, in many practical cases graphs are not explicitly available and must therefore be inferred from data. Validation is a challenging endeavor that naturally depends on the downstream task for which the graph is learnt. Accordingly, it has often been difficult to compare the efficacy of different algorithms. In this work, we introduce several ease-to-use and publicly released benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.
DRIFT: Deep Reinforcement Learning for Functional Software Testing
Venue: arXiv cs.LG 2020
Year: 2020

Efficient software testing is essential for productive software development and reliable user experiences. As human testing is inefficient and expensive, automated software testing is needed. In this work, we propose a Reinforcement Learning (RL) framework for functional software testing named DRIFT. DRIFT operates on the symbolic representation of the user interface. It uses Q-learning through Batch-RL and models the state-action value function with a Graph Neural Network. We apply DRIFT to testing the Windows 10 operating system and show that DRIFT can robustly trigger the desired software functionality in a fully automated manner. Our experiments test the ability to perform single and combined tasks across different applications, demonstrating that our framework can efficiently test software with a large range of testing objectives.
MaxSAT Evaluation 2020 -- Benchmark: Identifying Maximum Probability Minimal Cut Sets in Fault Trees
Venue: arXiv cs.CR 2020
Year: 2020

This paper presents a MaxSAT benchmark focused on the identification of Maximum Probability Minimal Cut Sets (MPMCSs) in fault trees. We address the MPMCS problem by transforming the input fault tree into a weighted logical formula that is then used to build and solve a Weighted Partial MaxSAT problem. The benchmark includes 80 cases with fault trees of different size and composition as well as the optimal cost and solution for each case.
Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction
Venue: arXiv cs.SE 2020
Year: 2020

Database Management Systems (DBMS) are used ubiquitously. To efficiently access data, they apply sophisticated optimizations. Incorrect optimizations can result in logic bugs, which cause a query to compute an incorrect result set. We propose Non-Optimizing Reference Engine Construction (NoREC), a fully-automatic approach to detect optimization bugs in DBMS. Conceptually, this approach aims to evaluate a query by an optimizing and a non-optimizing version of a DBMS, to then detect differences in their returned result set, which would indicate a bug in the DBMS. Obtaining a non-optimizing version of a DBMS is challenging, because DBMS typically provide limited control over optimizations. Our core insight is that a given, potentially randomly-generated optimized query can be rewritten to one that the DBMS cannot optimize. Evaluating this unoptimized query effectively corresponds to a non-optimizing reference engine executing the original query. We evaluated NoREC in an extensive testing campaign on four widely-used DBMS, namely PostgreSQL, MariaDB, SQLite, and CockroachDB. We found 159 previously unknown bugs in the latest versions of these systems, 141 of which have been fixed by the developers. Of these, 51 were optimization bugs, while the remaining were error and crash bugs. Our results suggest that NoREC is effective, general and requires little implementation effort, which makes the technique widely applicable in practice.
Challenges and Prospects of Negawatt Trading in Light of Recent Technological Developments
Venue: arXiv cs.CY 2020
Year: 2020

With the advancement of the smart grid, the current energy system is moving towards a future where people can buy what they need, sell when they have excess, and can trade the right of buying to other prosumers. While the first two schemes already exist in the market, selling the right of buying, also known as negawatt trading, is something that is yet to be implemented. Here, we review the challenges and prospects of negawatt trading in light of recent technological advancements. Through reviewing a number of emerging technologies, we show that the necessary methodologies that are needed to establish negawatt trading as a feasible energy management scheme in the smart grid are already available. Grid interactive buildings and distributed ledger technologies for instance can ensure active participation and fair pricing. However, some additional challenges need to address for fully functional negawatt trading mechanisms in today's energy market.