OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Agent Coverage in Urban Environments
Venue: arXiv cs.RO 2020
Year: 2020

We study multi-agent coverage algorithms for autonomous monitoring and patrol in urban environments. We consider scenarios in which a team of flying agents uses downward facing cameras (or similar sensors) to observe the environment outside of buildings at street-level. Buildings are considered obstacles that impede movement, and cameras are assumed to be ineffective above a maximum altitude. We study multi-agent urban coverage problems related to this scenario, including: (1) static multi-agent urban coverage, in which agents are expected to observe the environment from static locations, and (2) dynamic multi-agent urban coverage where agents move continuously through the environment. We experimentally evaluate six different multi-agent coverage methods, including: three types of ergodic coverage (that avoid buildings in different ways), lawn-mower sweep, voronoi region based control, and a naive grid method. We evaluate all algorithms with respect to four performance metrics (percent coverage, revist count, revist time, and the integral of area viewed over time), across four types of urban environments [low density, high density] x [short buildings, tall buildings], and for team sizes ranging from 2 to 25 agents. We believe this is the first extensive comparison of these methods in an urban setting. Our results highlight how the relative performance of static and dynamic methods changes based on the ratio of team size to search area, as well the relative effects that different characteristics of urban environments (tall, short, dense, sparse, mixed) have on each algorithm.
Narrative Interpolation for Generating and Understanding Stories
Venue: arXiv cs.CL 2020
Year: 2020

We propose a method for controlled narrative/story generation where we are able to guide the model to produce coherent narratives with user-specified target endings by interpolation: for example, we are told that Jim went hiking and at the end Jim needed to be rescued, and we want the model to incrementally generate steps along the way. The core of our method is an interpolation model based on GPT-2 which conditions on a previous sentence and a next sentence in a narrative and fills in the gap. Additionally, a reranker helps control for coherence of the generated text. With human evaluation, we show that ending-guided generation results in narratives which are coherent, faithful to the given ending guide, and require less manual effort on the part of the human guide writer than past approaches.
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Venue: arXiv cs.CG 2020
Year: 2020

Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified whenever we aim to quantify the similarity of the curves' shapes rather than their positioning in the plane, e.g., to compare the similarity of handwritten characters. Perhaps the most natural such notion is the (discrete) Fréchet distance under translation. Unfortunately, the algorithmic literature on this problem yields a very pessimistic view: On polygonal curves with $n$ vertices, the fastest algorithm runs in time $O(n^{4.667})$ and cannot be improved below $n^{4-o(1)}$ unless the Strong Exponential Time Hypothesis fails. Can we still obtain an implementation that is efficient on realistic datasets? Spurred by the surprising performance of recent implementations for the Fréchet distance, we perform algorithm engineering for the Fréchet distance under translation. Our solution combines fast, but inexact tools from continuous optimization (specifically, branch-and-bound algorithms for global Lipschitz optimization) with exact, but expensive algorithms from computational geometry (specifically, problem-specific algorithms based on an arrangement construction). We combine these two ingredients to obtain an exact decision algorithm for the Fréchet distance under translation. For the related task of computing the distance value up to a desired precision, we engineer and compare different methods. On a benchmark set involving handwritten characters and route trajectories, our implementation answers a typical query for either task in the range of a few milliseconds up to a second on standard desktop hardware. We believe that our implementation will enable the use of the Fréchet distance under translation in applications, whereas previous approaches would have been computationally infeasible.
A Smartphone-based System for Real-time Early Childhood Caries Diagnosis
Venue: arXiv cs.CV 2020
Year: 2020

Early childhood caries (ECC) is the most common, yet preventable chronic disease in children under the age of 6. Treatments on severe ECC are extremely expensive and unaffordable for socioeconomically disadvantaged families. The identification of ECC in an early stage usually requires expertise in the field, and hence is often ignored by parents. Therefore, early prevention strategies and easy-to-adopt diagnosis techniques are desired. In this study, we propose a multistage deep learning-based system for cavity detection. We create a dataset containing RGB oral images labeled manually by dental practitioners. We then investigate the effectiveness of different deep learning models on the dataset. Furthermore, we integrate the deep learning system into an easy-to-use mobile application that can diagnose ECC from an early stage and provide real-time results to untrained users.
Drawing Shortest Paths in Geodetic Graphs
Venue: arXiv cs.DM 2020
Year: 2020

Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph $G$, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of $G$, i.e., a drawing of $G$ in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing.
Runtime-Safety-Guided Policy Repair
Venue: arXiv cs.AI 2020
Year: 2020

We study the problem of policy repair for learning-based control policies in safety-critical settings. We consider an architecture where a high-performance learning-based control policy (e.g. one trained as a neural network) is paired with a model-based safety controller. The safety controller is endowed with the abilities to predict whether the trained policy will lead the system to an unsafe state, and take over control when necessary. While this architecture can provide added safety assurances, intermittent and frequent switching between the trained policy and the safety controller can result in undesirable behaviors and reduced performance. We propose to reduce or even eliminate control switching by `repairing' the trained policy based on runtime data produced by the safety controller in a way that deviates minimally from the original policy. The key idea behind our approach is the formulation of a trajectory optimization problem that allows the joint reasoning of policy update and safety constraints. Experimental results demonstrate that our approach is effective even when the system model in the safety controller is unknown and only approximated.
On the Error Exponent of Approximate Sufficient Statistics for M-ary Hypothesis Testing
Venue: arXiv cs.IT 2020
Year: 2020

Consider the problem of detecting one of M i.i.d. Gaussian signals corrupted in white Gaussian noise. Conventionally, matched filters are used for detection. We first show that the outputs of the matched filter form a set of asymptotically optimal sufficient statistics in the sense of maximizing the error exponent of detecting the true signal. In practice, however, M may be large which motivates the design and analysis of a reduced set of N statistics which we term approximate sufficient statistics. Our construction of these statistics is based on a small set of filters that project the outputs of the matched filters onto a lower-dimensional vector using a sensing matrix. We consider a sequence of sensing matrices that has the desiderata of row orthonormality and low coherence. We analyze the performance of the resulting maximum likelihood (ML) detector, which leads to an achievable bound on the error exponent based on the approximate sufficient statistics; this bound recovers the original error exponent when N = M. We compare this to a bound that we obtain by analyzing a modified form of the Reduced Dimensionality Detector (RDD) proposed by Xie, Eldar, and Goldsmith [IEEE Trans. on Inform. Th., 59(6):3858-3874, 2013]. We show that by setting the sensing matrices to be column-normalized group Hadamard matrices, the exponents derived are ensemble-tight, i.e., our analysis is tight on the exponential scale given the sensing matrices and the decoding rule. Finally, we derive some properties of the exponents, showing, in particular, that they increase linearly in the compression ratio N/M.
Deep Learning-based Signal Strength Prediction Using Geographical Images and Expert Knowledge
Venue: arXiv cs.NI 2020
Year: 2020

Methods for accurate prediction of radio signal quality parameters are crucial for optimization of mobile networks, and a necessity for future autonomous driving solutions. The power-distance relation of current empirical models struggles with describing the specific local geo-statistics that influence signal quality parameters. The use of empirical models commonly results in an over- or under-estimation of the signal quality parameters and require additional calibration studies. In this paper, we present a novel model-aided deep learning approach for path loss prediction, which implicitly extracts radio propagation characteristics from top-view geographical images of the receiver location. In a comprehensive evaluation campaign, we apply the proposed method on an extensive real-world data set consisting of five different scenarios and more than 125.000 individual measurements. It is found that 1) the novel approach reduces the average prediction error by up to 53% in comparison to ray-tracing techniques, 2) A distance of 250-300 meters spanned by the images offer the necessary level of detail, 3) Predictions with a root-mean-squared error of approximately 6 dB is achieved across inherently different data sources.
Efficient Private Machine Learning by Differentiable Random Transformations
Venue: arXiv cs.CR 2020
Year: 2020

With the increasing demands for privacy protection, many privacy-preserving machine learning systems were proposed in recent years. However, most of them cannot be put into production due to their slow training and inference speed caused by the heavy cost of homomorphic encryption and secure multiparty computation(MPC) methods. To circumvent this, I proposed a privacy definition which is suitable for large amount of data in machine learning tasks. Based on that, I showed that random transformations like linear transformation and random permutation can well protect privacy. Merging random transformations and arithmetic sharing together, I designed a framework for private machine learning with high efficiency and low computation cost.
New Quality Metrics for Dynamic Graph Drawing
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we present new quality metrics for dynamic graph drawings. Namely, we present a new framework for change faithfulness metrics for dynamic graph drawings, which compare the ground truth change in dynamic graphs and the geometric change in drawings. More specifically, we present two specific instances, cluster change faithfulness metrics and distance change faithfulness metrics. We first validate the effectiveness of our new metrics using deformation experiments. Then we compare various graph drawing algorithms using our metrics. Our experiments confirm that the best cluster (resp. distance) faithful graph drawing algorithms are also cluster (resp. distance) change faithful.
Planar L-Drawings of Bimodal Graphs
Venue: arXiv cs.CG 2020
Year: 2020

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding.
The Relational Data Borg is Learning
Venue: arXiv cs.DB 2020
Year: 2020

This paper overviews an approach that addresses machine learning over relational data as a database problem. This is justified by two observations. First, the input to the learning task is commonly the result of a feature extraction query over the relational data. Second, the learning task requires the computation of group-by aggregates. This approach has been already investigated for a number of supervised and unsupervised learning tasks, including: ridge linear regression, factorisation machines, support vector machines, decision trees, principal component analysis, and k-means; and also for linear algebra over data matrices. The main message of this work is that the runtime performance of machine learning can be dramatically boosted by a toolbox of techniques that exploit the knowledge of the underlying data. This includes theoretical development on the algebraic, combinatorial, and statistical structure of relational data processing and systems development on code specialisation, low-level computation sharing, and parallelisation. These techniques aim at lowering both the complexity and the constant factors of the learning time. This work is the outcome of extensive collaboration of the author with colleagues from RelationalAI, in particular Mahmoud Abo Khamis, Molham Aref, Hung Ngo, and XuanLong Nguyen, and from the FDB research project, in particular Ahmet Kara, Milos Nikolic, Maximilian Schleich, Amir Shaikhha, Jakub Zavodny, and Haozhe Zhang. The author would also like to thank the members of the FDB project for the figures and examples used in this paper. The author is grateful for support from industry: Amazon Web Services, Google, Infor, LogicBlox, Microsoft Azure, RelationalAI; and from the funding agencies EPSRC and ERC. This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 682588.
Self-supervised Sparse to Dense Motion Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Observable motion in videos can give rise to the definition of objects moving with respect to the scene. The task of segmenting such moving objects is referred to as motion segmentation and is usually tackled either by aggregating motion information in long, sparse point trajectories, or by directly producing per frame dense segmentations relying on large amounts of training data. In this paper, we propose a self supervised method to learn the densification of sparse motion segmentations from single video frames. While previous approaches towards motion segmentation build upon pre-training on large surrogate datasets and use dense motion information as an essential cue for the pixelwise segmentation, our model does not require pre-training and operates at test time on single frames. It can be trained in a sequence specific way to produce high quality dense segmentations from sparse and noisy input. We evaluate our method on the well-known motion segmentation datasets FBMS59 and DAVIS16.
Modeling and Analysis of Boundary Objects and Methodological Islands in Large-Scale Systems Development
Venue: arXiv cs.SE 2020
Year: 2020

Large-scale companies commonly face the challenge of managing relevant knowledge between different organizational groups, particularly in increasingly agile contexts. In previous studies, we found the importance of analyzing methodological islands (i.e., groups using different development methods than the surrounding organization) and boundary objects between them. In this paper, we propose a metamodel to better capture and analyze coordination and knowledge management in practice. Such a metamodel can allow practitioners to describe current practices, analyze issues, and design better-suited coordination mechanisms. We evaluated the conceptual model together with four large-scale companies developing complex systems. In particular, we derived an initial list of bad smells that can be leveraged to detect issues and devise suitable improvement strategies for inter-team coordination in large-scale development. We present the model, smells, and our evaluation results.
COVID-SEE: Scientific Evidence Explorer for COVID-19 Related Research
Venue: arXiv cs.CL 2020
Year: 2020

We present COVID-SEE, a system for medical literature discovery based on the concept of information exploration, which builds on several distinct text analysis and natural language processing methods to structure and organise information in publications, and augments search by providing a visual overview supporting exploration of a collection to identify key articles of interest. We developed this system over COVID-19 literature to help medical professionals and researchers explore the literature evidence, and improve findability of relevant information. COVID-SEE is available at http://covid-see.com.
Differential coverage: automating coverage analysis
Venue: arXiv cs.SE 2020
Year: 2020

While it is easy to automate coverage data collection, it is a time consuming/difficult/expensive manual process to analyze the data so that it can be acted upon. Complexity arises from numerous sources, of which untested or poorly tested legacy code and third-party libraries are two of the most common. Differential coverage and date binning are methods of combining coverage data and project/file history to determine if goals have been met and to identify areas of code which should be prioritized. These methods can be applied to any coverage metric which can be associated with a location -- statement, function, expression, toggle, etc. -- and to any language, including both software (C++, Python, etc.) and hardware description languages (SystemVerilog, VHDL). The goal of these approaches is to reduce the cost and the barrier to entry of using coverage data analysis in large-scale projects. The approach is realized in gendiffcov, a recently released open-source tool.
Adaptive Distillation for Decentralized Learning from Heterogeneous Clients
Venue: arXiv cs.LG 2020
Year: 2020

This paper addresses the problem of decentralized learning to achieve a high-performance global model by asking a group of clients to share local models pre-trained with their own data resources. We are particularly interested in a specific case where both the client model architectures and data distributions are diverse, which makes it nontrivial to adopt conventional approaches such as Federated Learning and network co-distillation. To this end, we propose a new decentralized learning method called Decentralized Learning via Adaptive Distillation (DLAD). Given a collection of client models and a large number of unlabeled distillation samples, the proposed DLAD 1) aggregates the outputs of the client models while adaptively emphasizing those with higher confidence in given distillation samples and 2) trains the global model to imitate the aggregated outputs. Our extensive experimental evaluation on multiple public datasets (MNIST, CIFAR-10, and CINIC-10) demonstrates the effectiveness of the proposed method.
On the Parameterized Complexity Of Grid Contraction
Venue: arXiv cs.DM 2020
Year: 2020

For a family of graphs $\mathcal{G}$, the $\mathcal{G}$-\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $F \subseteq E(G)$ of size at most $k$ such that $G/F$ belongs to $\mathcal{G}$. Here, $G/F$ is the graph obtained from $G$ by contracting all the edges in $F$. In this article, we initiate the study of \textsc{Grid Contraction} from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time $c^k \cdot |V(G)|^{\mathcal{O}(1)}$, for this problem. We complement this result by proving that unless Ð fails, there is no algorithm for \textsc{Grid Contraction} with running time $c^{o(k)} \cdot |V(G)|^{\mathcal{O}(1)}$. We also present a polynomial kernel for this problem.
Four short stories on surprising algorithmic uses of treewidth
Venue: arXiv cs.DS 2020
Year: 2020

This article briefly describes four algorithmic problems where the notion of treewidth is very useful. Even though the problems themselves have nothing to do with treewidth, it turns out that combining known results on treewidth allows us to easily describe very clean and high-level algorithms.
Communicative Reinforcement Learning Agents for Landmark Detection in Brain Images
Venue: arXiv cs.CV 2020
Year: 2020

Accurate detection of anatomical landmarks is an essential step in several medical imaging tasks. We propose a novel communicative multi-agent reinforcement learning (C-MARL) system to automatically detect landmarks in 3D brain images. C-MARL enables the agents to learn explicit communication channels, as well as implicit communication signals by sharing certain weights of the architecture among all the agents. The proposed approach is evaluated on two brain imaging datasets from adult magnetic resonance imaging (MRI) and fetal ultrasound scans. Our experiments show that involving multiple cooperating agents by learning their communication with each other outperforms previous approaches using single agents.
Commonsense Knowledge in Wikidata
Venue: arXiv cs.AI 2020
Year: 2020

Wikidata and Wikipedia have been proven useful for reason-ing in natural language applications, like question answering or entitylinking. Yet, no existing work has studied the potential of Wikidata for commonsense reasoning. This paper investigates whether Wikidata con-tains commonsense knowledge which is complementary to existing commonsense sources. Starting from a definition of common sense, we devise three guiding principles, and apply them to generate a commonsense subgraph of Wikidata (Wikidata-CS). Within our approach, we map the relations of Wikidata to ConceptNet, which we also leverage to integrate Wikidata-CS into an existing consolidated commonsense graph. Our experiments reveal that: 1) albeit Wikidata-CS represents a small portion of Wikidata, it is an indicator that Wikidata contains relevant commonsense knowledge, which can be mapped to 15 ConceptNet relations; 2) the overlap between Wikidata-CS and other commonsense sources is low, motivating the value of knowledge integration; 3) Wikidata-CS has been evolving over time at a slightly slower rate compared to the overall Wikidata, indicating a possible lack of focus on commonsense knowledge. Based on these findings, we propose three recommended actions to improve the coverage and quality of Wikidata-CS further.