OpenRaiser/Intern-Atlas huggingface dataset:
Structural Controllability of a Consensus Network with Multiple Leaders
Venue: arXiv cs.SY 2018
Year: 2018

This paper examines the structural controllability for a group of agents, called followers, connected to each other based on the consensus law under commands of multiple leaders, which are agents with superior capabilities, over a fixed communication topology. It is proved that the graph-theoretic sufficient and necessary condition for the set of followers to be structurally controllable under the leaders' commands is leader-follower connectivity of the associated graph topology. This shrinks to graph connectivity for the case of solo leader. In the approach, we explicitly put into account the dependence among the entries of the system matrices for a consensus network using the linear parameterization technique introduced in [1].
Ranking with Adaptive Neighbors
Venue: arXiv cs.LG 2018
Year: 2018

Retrieving the most similar objects in a large-scale database for a given query is a fundamental building block in many application domains, ranging from web searches, visual, cross media, and document retrievals. State-of-the-art approaches have mainly focused on capturing the underlying geometry of the data manifolds. Graph-based approaches, in particular, define various diffusion processes on weighted data graphs. Despite success, these approaches rely on fixed-weight graphs, making ranking sensitive to the input affinity matrix. In this study, we propose a new ranking algorithm that simultaneously learns the data affinity matrix and the ranking scores. The proposed optimization formulation assigns adaptive neighbors to each point in the data based on the local connectivity, and the smoothness constraint assigns similar ranking scores to similar data points. We develop a novel and efficient algorithm to solve the optimization problem. Evaluations using synthetic and real datasets suggest that the proposed algorithm can outperform the existing methods.
EdgeStereo: A Context Integrated Residual Pyramid Network for Stereo Matching
Venue: arXiv cs.CV 2018
Year: 2018

Recent convolutional neural networks, especially end-to-end disparity estimation models, achieve remarkable performance on stereo matching task. However, existed methods, even with the complicated cascade structure, may fail in the regions of non-textures, boundaries and tiny details. Focus on these problems, we propose a multi-task network EdgeStereo that is composed of a backbone disparity network and an edge sub-network. Given a binocular image pair, our model enables end-to-end prediction of both disparity map and edge map. Basically, we design a context pyramid to encode multi-scale context information in disparity branch, followed by a compact residual pyramid for cascaded refinement. To further preserve subtle details, our EdgeStereo model integrates edge cues by feature embedding and edge-aware smoothness loss regularization. Comparative results demonstrates that stereo matching and edge detection can help each other in the unified model. Furthermore, our method achieves state-of-art performance on both KITTI Stereo and Scene Flow benchmarks, which proves the effectiveness of our design.
LivDet 2017 Fingerprint Liveness Detection Competition 2017
Venue: arXiv cs.CV 2018
Year: 2018

Fingerprint Presentation Attack Detection (FPAD) deals with distinguishing images coming from artificial replicas of the fingerprint characteristic, made up of materials like silicone, gelatine or latex, and images coming from alive fingerprints. Images are captured by modern scanners, typically relying on solid-state or optical technologies. Since from 2009, the Fingerprint Liveness Detection Competition (LivDet) aims to assess the performance of the state-of-the-art algorithms according to a rigorous experimental protocol and, at the same time, a simple overview of the basic achievements. The competition is open to all academics research centers and all companies that work in this field. The positive, increasing trend of the participants number, which supports the success of this initiative, is confirmed even this year: 17 algorithms were submitted to the competition, with a larger involvement of companies and academies. This means that the topic is relevant for both sides, and points out that a lot of work must be done in terms of fundamental and applied research.
MCScript: A Novel Dataset for Assessing Machine Comprehension Using Script Knowledge
Venue: arXiv cs.CL 2018
Year: 2018

We introduce a large dataset of narrative texts and questions about these texts, intended to be used in a machine comprehension task that requires reasoning using commonsense knowledge. Our dataset complements similar datasets in that we focus on stories about everyday activities, such as going to the movies or working in the garden, and that the questions require commonsense knowledge, or more specifically, script knowledge, to be answered. We show that our mode of data collection via crowdsourcing results in a substantial amount of such inference questions. The dataset forms the basis of a shared task on commonsense and script knowledge organized at SemEval 2018 and provides challenging test cases for the broader natural language understanding community.
CloudHealth: A Model-Driven Approach to Watch the Health of Cloud Services
Venue: arXiv cs.SE 2018
Year: 2018

Cloud systems are complex and large systems where services provided by different operators must coexist and eventually cooperate. In such a complex environment, controlling the health of both the whole environment and the individual services is extremely important to timely and effectively react to misbehaviours, unexpected events, and failures. Although there are solutions to monitor cloud systems at different granularity levels, how to relate the many KPIs that can be collected about the health of the system and how health information can be properly reported to operators are open questions. This paper reports the early results we achieved in the challenge of monitoring the health of cloud systems. In particular we present CloudHealth, a model-based health monitoring approach that can be used by operators to watch specific quality attributes. The CloudHealth Monitoring Model describes how to operationalize high level monitoring goals by dividing them into subgoals, deriving metrics for the subgoals, and using probes to collect the metrics. We use the CloudHealth Monitoring Model to control the probes that must be deployed on the target system, the KPIs that are dynamically collected, and the visualization of the data in dashboards.
Constant delay algorithms for regular document spanners
Venue: arXiv cs.DB 2018
Year: 2018

Regular expressions and automata models with capture variables are core tools in rule-based information extraction. These formalisms, also called regular document spanners, use regular languages in order to locate the data that a user wants to extract from a text document, and then store this data into variables. Since document spanners can easily generate large outputs, it is important to have good evaluation algorithms that can generate the extracted data in a quick succession, and with relatively little precomputation time. Towards this goal, we present a practical evaluation algorithm that allows constant delay enumeration of a spanner's output after a precomputation phase that is linear in the document. While the algorithm assumes that the spanner is specified in a syntactic variant of variable set automata, we also study how it can be applied when the spanner is specified by general variable set automata, regex formulas, or spanner algebras. Finally, we study the related problem of counting the number of outputs of a document spanner, providing a fine grained analysis of the classes of document spanners that support efficient enumeration of their results.
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Venue: arXiv cs.GT 2018
Year: 2018

In a generalized network design (GND) problem, a set of resources are assigned to multiple communication requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. For example, a request may be to establish a virtual circuit, thus contributing to the load on each edge in the circuit. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads. The current paper advances the existing literature on approximation algorithms for GND problems with (D)oS cost functions in various aspects: (1) we present a generic approximation framework that yields approximation results for a much wider family of requests in both directed and undirected graphs; (2) our framework allows for unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) our framework is fully combinatorial and runs in strongly polynomial time; (4) the family of (D)oS cost functions considered in the current paper is more general than the one considered in the existing literature, providing a more accurate abstraction for practical energy conservation scenarios; and (5) we obtain the first approximation ratio for GND with (D)oS cost functions that depends only on the parameters of the resources' technology and does not grow with the number of resources, the number of requests, or their weights. The design of our framework relies heavily on Roughgarden's smoothness toolbox (JACM 2015), thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms.
Temporal Correlation of Interference in Vehicular Networks with Shifted-Exponential Time Headways
Venue: arXiv cs.NI 2018
Year: 2018

We consider a one-dimensional vehicular network where the time headway (time difference between successive vehicles as they pass a point on the roadway) follows the shifted-exponential distribution. We show that neglecting the impact of shift in the deployment model, which degenerates the distribution of vehicles to a Poisson Point Process, overestimates the temporal correlation of interference at the origin. The estimation error becomes large at high traffic conditions and small time-lags.
Which differences can be expected when two universities in the Leiden Ranking are compared? Some benchmarks for institutional research evaluations
Venue: arXiv cs.DL 2018
Year: 2018

The comparison of two universities in terms of bibliometric indicators frequently faces the problem of assessing the differences as meaningful or not. This Letter to the Editor proposes some benchmarks which can be used for supporting the interpretation of institutional differences.
Linearity is Strictly More Powerful than Contiguity for Encoding Graphs
Venue: arXiv cs.DM 2018
Year: 2018

Linearity and contiguity are two parameters devoted to graph encoding. Linearity is a generalisation of contiguity in the sense that every encoding achieving contiguity $k$ induces an encoding achieving linearity $k$, both encoding having size $Θ(k.n)$, where $n$ is the number of vertices of $G$. In this paper, we prove that linearity is a strictly more powerful encoding than contiguity, i.e. there exists some graph family such that the linearity is asymptotically negligible in front of the contiguity. We prove this by answering an open question asking for the worst case linearity of a cograph on $n$ vertices: we provide an $O(\log n/\log\log n)$ upper bound which matches the previously known lower bound.
An application of cascaded 3D fully convolutional networks for medical image segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Recent advances in 3D fully convolutional networks (FCN) have made it feasible to produce dense voxel-wise predictions of volumetric images. In this work, we show that a multi-class 3D FCN trained on manually labeled CT scans of several anatomical structures (ranging from the large organs to thin vessels) can achieve competitive segmentation results, while avoiding the need for handcrafting features or training class-specific models. To this end, we propose a two-stage, coarse-to-fine approach that will first use a 3D FCN to roughly define a candidate region, which will then be used as input to a second 3D FCN. This reduces the number of voxels the second FCN has to classify to ~10% and allows it to focus on more detailed segmentation of the organs and vessels. We utilize training and validation sets consisting of 331 clinical CT images and test our models on a completely unseen data collection acquired at a different hospital that includes 150 CT scans, targeting three anatomical organs (liver, spleen, and pancreas). In challenging organs such as the pancreas, our cascaded approach improves the mean Dice score from 68.5 to 82.2%, achieving the highest reported average score on this dataset. We compare with a 2D FCN method on a separate dataset of 240 CT scans with 18 classes and achieve a significantly higher performance in small organs and vessels. Furthermore, we explore fine-tuning our models to different datasets. Our experiments illustrate the promise and robustness of current 3D FCN based semantic segmentation of medical images, achieving state-of-the-art results. Our code and trained models are available for download: https://github.com/holgerroth/3Dunet_abdomen_cascade.
Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we review multi-agent collective behavior algorithms in the literature and classify them according to their underlying mathematical structure. For each mathematical technique, we identify the multi-agent coordination tasks it can be applied to, and we analyze its scalability, bandwidth use, and demonstrated maturity. We highlight how versatile techniques such as artificial potential functions can be used for applications ranging from low-level position control to high-level coordination and task allocation, we discuss possible reasons for the slow adoption of complex distributed coordination algorithms in the field, and we highlight areas for further research and development.
Low coherence unit norm tight frames
Venue: arXiv cs.IT 2018
Year: 2018

Equiangular tight frames (ETFs) have found significant applications in signal processing and coding theory due to their robustness to noise and transmission losses. ETFs are characterized by the fact that the coherence between any two distinct vectors is equal to the Welch bound. This guarantees that the maximum coherence between pairs of vectors is minimized. Despite their usefulness and widespread applications, ETFs of a given size $N$ are only guaranteed to exist in $\mathbb{R}^{d}$ or $\mathbb{C}^{d}$ if $N = d + 1$. This leads to the problem of finding approximations of ETFs of $N$ vectors in $\mathbb{R}^{d}$ or $\mathbb{C}^{d}$ where $N > d+1.$ To be more precise, one wishes to construct a unit norm tight frame (UNTF) such that the maximum coherence between distinct vectors of this frame is as close to the Welch bound as possible. In this paper low coherence UNTFs in $\mathbb{R}^d$ are constructed by adding a strategically chosen set of vectors called an "optimal" set to an existing ETF of $d+1$ vectors. In order to do so, combinatorial objects called block designs are used. Estimates are provided on the maximum coherence between distinct vectors of this low coherence UNTF. It is shown that for certain block designs, the constructed UNTF attains the smallest possible maximum coherence between pairs of vectors among all UNTFs containing the starting ETF of $d+1$ vectors. This is particularly desirable if there does not exist a set of the same size for which the Welch bound is attained.
An Assertion-Based Program Logic for Probabilistic Programs
Venue: arXiv cs.LO 2018
Year: 2018

Research on deductive verification of probabilistic programs has considered expectation-based logics, where pre- and post-conditions are real-valued functions on states, and assertion-based logics, where pre- and post-conditions are boolean predicates on state distributions. Both approaches have developed over nearly four decades, but they have different standings today. Expectation-based systems have managed to formalize many sophisticated case studies, while assertion-based systems today have more limited expressivity and have targeted simpler examples. We present Ellora, a sound and relatively complete assertion-based program logic, and demonstrate its expressivity by verifying several classical examples of randomized algorithms using an implementation in the EasyCrypt proof assistant. Ellora features new proof rules for loops and adversarial code, and supports richer assertions than existing program logics. We also show that Ellora allows convenient reasoning about complex probabilistic concepts by developing a new program logic for probabilistic independence and distribution law, and then smoothly embedding it into Ellora. Our work demonstrates that the assertion-based approach is not fundamentally limited and suggests that some notions are potentially easier to reason about in assertion-based systems.
Achieving Human Parity on Automatic Chinese to English News Translation
Venue: arXiv cs.CL 2018
Year: 2018

Machine translation has made rapid advances in recent years. Millions of people are using it today in online translation systems and mobile applications in order to communicate across language barriers. The question naturally arises whether such systems can approach or achieve parity with human translations. In this paper, we first address the problem of how to define and accurately measure human parity in translation. We then describe Microsoft's machine translation system and measure the quality of its translations on the widely used WMT 2017 news translation task from Chinese to English. We find that our latest neural machine translation system has reached a new state-of-the-art, and that the translation quality is at human parity when compared to professional human translations. We also find that it significantly exceeds the quality of crowd-sourced non-professional translations.
Reconstructing Gaussian sources by spatial sampling
Venue: arXiv cs.IT 2018
Year: 2018

Consider a Gaussian memoryless multiple source with $m$ components with joint probability distribution known only to lie in a given class of distributions. A subset of $k \leq m$ components are sampled and compressed with the objective of reconstructing all the $m$ components within a specified level of distortion under a mean-squared error criterion. In Bayesian and nonBayesian settings, the notion of universal sampling rate distortion function for Gaussian sources is introduced to capture the optimal tradeoffs among sampling, compression rate and distortion level. Single-letter characterizations are provided for the universal sampling rate distortion function. Our achievability proofs highlight the following structural property: it is optimal to compress and reconstruct first the sampled components of the GMMS alone, and then form estimates for the unsampled components based on the former.
Event Correlation and Forecasting over Multivariate Streaming Sensor Data
Venue: arXiv cs.DC 2018
Year: 2018

Event management in sensor networks is a multidisciplinary field involving several steps across the processing chain. In this paper, we discuss the major steps that should be performed in real- or near real-time event handling including event detection, correlation, prediction and filtering. First, we discuss existing univariate and multivariate change detection schemes for the online event detection over sensor data. Next, we propose an online event correlation scheme that intends to unveil the internal dynamics that govern the operation of a system and are responsible for the generation of various types of events. We show that representation of event dependencies can be accommodated within a probabilistic temporal knowledge representation framework that allows the formulation of rules. We also address the important issue of identifying outdated dependencies among events by setting up a time-dependent framework for filtering the extracted rules over time. The proposed theory is applied on the maritime domain and is validated through extensive experimentation with real sensor streams originating from large-scale sensor networks deployed in ships.
Training of Convolutional Networks on Multiple Heterogeneous Datasets for Street Scene Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We propose a convolutional network with hierarchical classifiers for per-pixel semantic segmentation, which is able to be trained on multiple, heterogeneous datasets and exploit their semantic hierarchy. Our network is the first to be simultaneously trained on three different datasets from the intelligent vehicles domain, i.e. Cityscapes, GTSDB and Mapillary Vistas, and is able to handle different semantic level-of-detail, class imbalances, and different annotation types, i.e. dense per-pixel and sparse bounding-box labels. We assess our hierarchical approach, by comparing against flat, non-hierarchical classifiers and we show improvements in mean pixel accuracy of 13.0% for Cityscapes classes and 2.4% for Vistas classes and 32.3% for GTSDB classes. Our implementation achieves inference rates of 17 fps at a resolution of 520x706 for 108 classes running on a GPU.
Achieving Spatial Scalability for Coded Caching over Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

The coded caching scheme proposed by Maddah-Ali and Niesen considers the delivery of files in a given content library to users through a deterministic error-free network where a common multicast message is sent to all users at a fixed rate, independent of the number of users. In order to apply this paradigm to a wireless network, it is important to make sure that the common multicast rate does not vanish as the number of users increases. This paper focuses on a variant of coded caching successively proposed for the so-called combination network, where the multicast message is further encoded by a Maximum Distance Separable (MDS) code and the MDS-coded blocks are simultaneously transmitted from different Edge Nodes (ENs) (e.g., base stations or access points). Each user is equipped with multiple antennas and can select to decode a desired number of EN transmissions, while either nulling of treating as noise the others, depending on their strength. The system is reminiscent of the so-called evolved Multimedia Broadcast Multicast Service (eMBMS), in the sense that the fundamental underlying transmission mechanism is multipoint multicasting, where each user can independently and individually (in a user-centric manner) decide which EN to decode, without any explicit association of users to ENs. We study the performance of the proposed system when users and ENs are distributed according to homogeneous Poisson Point Processes in the plane and the propagation is affected by Rayleigh fading and distance dependent pathloss. Our analysis allows the system optimization with respect to the MDS coding rate. Also, we show that the proposed system is fully scalable, in the sense that it can support an arbitrarily large number of users, while maintaining a non-vanishing per-user delivery rate.