OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Reweighted Belief Propagation for Distributed Likelihood Fusion Problems
Venue: arXiv cs.SY 2018
Year: 2018

Belief propagation (BP) is a powerful tool to solve distributed inference problems, though it is limited by short cycles in the corresponding factor graph. Such cycles may lead to incorrect solutions or oscillatory behavior. Only for certain types of problems are convergence properties understood. We extend this knowledge by investigating the use of reweighted BP for distributed likelihood fusion problems, which are characterized by equality constraints along possibly short cycles. Through a linear formulation of BP, we are able to analytically derive convergence conditions for certain types of graphs and optimize the convergence speed. We compare with standard belief consensus and observe significantly faster convergence.
Low-Latency Heterogeneous Networks with Millimeter-Wave Communications
Venue: arXiv cs.NI 2018
Year: 2018

Heterogeneous network (HetNet) is a key enabler to largely boost network coverage and capacity in the forthcoming fifth-generation (5G) and beyond. To support the explosively growing mobile data volumes, wireless communications with millimeter-wave (mm-wave) radios have attracted massive attention, which is widely considered as a promising candidate in 5G HetNets. In this article, we give an overview on the end-to-end latency of HetNets with mm-wave communications. In general, it is rather challenging for formulating and optimizing the delay problem with buffers in mm-wave communications, since conventional graph-based network optimization techniques are not applicable when queues are considered. Toward this end, we develop an adaptive low-latency strategy, which uses cooperative networking to reduce the end-to-end latency. Then, we evaluate the performance of the introduced strategy. Results reveal the importance of proper cooperative networking in reducing the end-to-end latency. In addition, we have identified several challenges in future research for low-latency mm-wave HetNets.
Multiple Object Detection, Tracking and Long-Term Dynamics Learning in Large 3D Maps
Venue: arXiv cs.RO 2018
Year: 2018

In this work, we present a method for tracking and learning the dynamics of all objects in a large scale robot environment. A mobile robot patrols the environment and visits the different locations one by one. Movable objects are discovered by change detection, and tracked throughout the robot deployment. For tracking, we extend the Rao-Blackwellized particle filter of previous work with birth and death processes, enabling the method to handle an arbitrary number of objects. Target births and associations are sampled using Gibbs sampling. The parameters of the system are then learnt using the Expectation Maximization algorithm in an unsupervised fashion. The system therefore enables learning of the dynamics of one particular environment, and of its objects. The algorithm is evaluated on data collected autonomously by a mobile robot in an office environment during a real-world deployment. We show that the algorithm automatically identifies and tracks the moving objects within 3D maps and infers plausible dynamics models, significantly decreasing the modeling bias of our previous work. The proposed method represents an improvement over previous methods for environment dynamics learning as it allows for learning of fine grained processes.
Benchmarking Clinical Decision Support Search
Venue: arXiv cs.IR 2018
Year: 2018

Finding relevant literature underpins the practice of evidence-based medicine. From 2014 to 2016, TREC conducted a clinical decision support track, wherein participants were tasked with finding articles relevant to clinical questions posed by physicians. In total, 87 teams have participated over the past three years, generating 395 runs. During this period, each team has trialled a variety of methods. While there was significant overlap in the methods employed by different teams, the results were varied. Due to the diversity of the platforms used, the results arising from the different techniques are not directly comparable, reducing the ability to build on previous work. By using a stable platform, we have been able to compare different document and query processing techniques, allowing us to experiment with different search parameters. We have used our system to reproduce leading teams runs, and compare the results obtained. By benchmarking our indexing and search techniques, we can statistically test a variety of hypotheses, paving the way for further research.
Detecting the impact of public transit on the transmission of epidemics
Venue: arXiv cs.SI 2018
Year: 2018

In many developing countries, public transit plays an important role in daily life. However, few existing methods have considered the influence of public transit in their models. In this work, we present a dual-perspective view of the epidemic spreading process of the individual that involves both contamination in places (such as work places and homes) and public transit (such as buses and trains). In more detail, we consider a group of individuals who travel to some places using public transit, and introduce public transit into the epidemic spreading process. A novel modeling framework is proposed considering place-based infections and the public-transit-based infections. In the urban scenario, we investigate the public transit trip contribution rate (PTTCR) in the epidemic spreading process of the individual, and assess the impact of the public transit trip contribution rate by evaluating the volume of infectious people. Scenarios for strategies such as public transit and school closure were tested and analyzed. Our simulation results suggest that individuals with a high public transit trip contribution rate will increase the volume of infectious people when an infectious disease outbreak occurs by affecting the social network through the public transit trip contribution rate.
A Method to Compute the Sparse Graphs for Traveling Salesman Problem Based on Frequency Quadrilaterals
Venue: arXiv cs.DM 2018
Year: 2018

In this paper, an iterative algorithm is designed to compute the sparse graphs for traveling salesman problem (TSP) according to the frequency quadrilaterals so that the computation time of the algorithms for TSP will be lowered. At each computation cycle, the algorithm first computes the average frequency \bar{f}(e) of an edge e with N frequency quadrilaterals containing e in the input graph G(V,E). Then the 1/3|E| edges with low frequency are eliminated to generate the output graph with a smaller number of edges. The algorithm can be iterated several times and the original optimal Hamiltonian cycle is preserved with a high probability. The experiments demonstrate the algorithm computes the sparse graphs with the O(nlog_2n) edges containing the original optimal Hamiltonian cycle for most of the TSP instances in the TSPLIB. The computation time of the iterative algorithm is O(Nn^2).
Road Damage Detection Using Deep Neural Networks with Images Captured Through a Smartphone
Venue: arXiv cs.CV 2018
Year: 2018

Research on damage detection of road surfaces using image processing techniques has been actively conducted, achieving considerably high detection accuracies. Many studies only focus on the detection of the presence or absence of damage. However, in a real-world scenario, when the road managers from a governing body need to repair such damage, they need to clearly understand the type of damage in order to take effective action. In addition, in many of these previous studies, the researchers acquire their own data using different methods. Hence, there is no uniform road damage dataset available openly, leading to the absence of a benchmark for road damage detection. This study makes three contributions to address these issues. First, to the best of our knowledge, for the first time, a large-scale road damage dataset is prepared. This dataset is composed of 9,053 road damage images captured with a smartphone installed on a car, with 15,435 instances of road surface damage included in these road images. In order to generate this dataset, we cooperated with 7 municipalities in Japan and acquired road images for more than 40 hours. These images were captured in a wide variety of weather and illuminance conditions. In each image, we annotated the bounding box representing the location and type of damage. Next, we used a state-of-the-art object detection method using convolutional neural networks to train the damage detection model with our dataset, and compared the accuracy and runtime speed on both, using a GPU server and a smartphone. Finally, we demonstrate that the type of damage can be classified into eight types with high accuracy by applying the proposed object detection method. The road damage dataset, our experimental results, and the developed smartphone application used in this study are publicly available (https://github.com/sekilab/RoadDamageDetector/).
Using deep Q-learning to understand the tax evasion behavior of risk-averse firms
Venue: arXiv cs.AI 2018
Year: 2018

Designing tax policies that are effective in curbing tax evasion and maximize state revenues requires a rigorous understanding of taxpayer behavior. This work explores the problem of determining the strategy a self-interested, risk-averse tax entity is expected to follow, as it "navigates" - in the context of a Markov Decision Process - a government-controlled tax environment that includes random audits, penalties and occasional tax amnesties. Although simplified versions of this problem have been previously explored, the mere assumption of risk-aversion (as opposed to risk-neutrality) raises the complexity of finding the optimal policy well beyond the reach of analytical techniques. Here, we obtain approximate solutions via a combination of Q-learning and recent advances in Deep Reinforcement Learning. By doing so, we i) determine the tax evasion behavior expected of the taxpayer entity, ii) calculate the degree of risk aversion of the "average" entity given empirical estimates of tax evasion, and iii) evaluate sample tax policies, in terms of expected revenues. Our model can be useful as a testbed for "in-vitro" testing of tax policies, while our results lead to various policy recommendations.
Hyper-Hue and EMAP on Hyperspectral Images for Supervised Layer Decomposition of Old Master Drawings
Venue: arXiv cs.CV 2018
Year: 2018

Old master drawings were mostly created step by step in several layers using different materials. To art historians and restorers, examination of these layers brings various insights into the artistic work process and helps to answer questions about the object, its attribution and its authenticity. However, these layers typically overlap and are oftentimes difficult to differentiate with the unaided eye. For example, a common layer combination is red chalk under ink. In this work, we propose an image processing pipeline that operates on hyperspectral images to separate such layers. Using this pipeline, we show that hyperspectral images enable better layer separation than RGB images, and that spectral focus stacking aids the layer separation. In particular, we propose to use two descriptors in hyperspectral historical document analysis, namely hyper-hue and extended multi-attribute profile (EMAP). Our comparative results with other features underline the efficacy of the three proposed improvements.
Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels
Venue: arXiv cs.IT 2018
Year: 2018

Consider a binary linear code of length $N$, minimum distance $d_{\text{min}}$, transmission over the binary erasure channel with parameter $0 < ε< 1$ or the binary symmetric channel with parameter $0 < ε< \frac12$, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions "quickly" from $δ$ to $1-δ$ for any $δ>0$ if the minimum distance is large. In particular the width of the transition is of order $O(1/\sqrt{d_{\text{min}}})$. We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as $Θ(1/N^{\frac12-κ})$, for any $κ>0$, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since $Θ(1/N^{\frac12})$ is the smallest transition possible for any code, we speak of "almost" optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
Rapid Testing of IaaS Resource Management Algorithms via Cloud Middleware Simulation
Venue: arXiv cs.SE 2018
Year: 2018

Infrastructure as a Service (IaaS) Cloud services allow users to deploy distributed applications in a virtualized environment without having to customize their applications to a specific Platform as a Service (PaaS) stack. It is common practice to host multiple Virtual Machines (VMs) on the same server to save resources. Traditionally, IaaS data center management required manual effort for optimization, e.g. by consolidating VM placement based on changes in usage patterns. Many resource management algorithms and frameworks have been developed to automate this process. Resource management algorithms are typically tested via experimentation or using simulation. The main drawback of both approaches is the high effort required to conduct the testing. Existing Cloud or IaaS simulators require the algorithm engineer to reimplement their algorithm against the simulator's API. Furthermore, the engineer manually needs to define the workload model used for algorithm testing. We propose an approach for the simulative analysis of IaaS Cloud infrastructure that allows algorithm engineers and data center operators to eval- uate optimization algorithms without investing additional effort to reimplement them in a simulation environment. By leveraging runtime monitoring data, we automatically construct the simula- tion models used to test the algorithms. Our validation shows that algorithm tests conducted using our IaaS Cloud simulator match the measured behavior on actual hardware.
On the Effective Energy Efficiency of Ultra-reliable Networks in the Finite Blocklength Regime
Venue: arXiv cs.IT 2018
Year: 2018

Effective Capacity (EC) indicates the maximum communication rate subject to a certain delay constraint while effective energy efficiency (EEE) denotes the ratio between EC and power consumption. In this paper, we analyze the EEE of ultra-reliable networks operating in the finite blocklength regime. We obtain a closed form approximation for the EEE in Rayleigh block fading channels as a function of power, error probability, and delay. We show the optimum power allocation strategy for maximizing the EEE in finite blocklength transmission which reveals that Shannon's model underestimates the optimum power when compared to the exact finite blocklength model. Furthermore, we characterize the buffer constrained EEE maximization problem for different power consumption models. The results show that accounting for empty buffer probability (EBP) and extending the maximum delay tolerance jointly enhance the EC and EEE.
Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices
Venue: arXiv cs.SY 2018
Year: 2018

Approximating the set of reachable states of a dynamical system is an algorithmic yet mathematically rigorous way to reason about its safety. Although progress has been made in the development of efficient algorithms for affine dynamical systems, available algorithms still lack scalability to ensure their wide adoption in the industrial setting. While modern linear algebra packages are efficient for matrices with tens of thousands of dimensions, set-based image computations are limited to a few hundred. We propose to decompose reach set computations such that set operations are performed in low dimensions, while matrix operations like exponentiation are carried out in the full dimension. Our method is applicable both in dense- and discrete-time settings. For a set of standard benchmarks, it shows a speed-up of up to two orders of magnitude compared to the respective state-of-the art tools, with only modest losses in accuracy. For the dense-time case, we show an experiment with more than 10.000 variables, roughly two orders of magnitude higher than possible with previous approaches.
Killing Two Birds with One Stone -- Querying Property Graphs using SPARQL via GREMLINATOR
Venue: arXiv cs.DB 2018
Year: 2018

Knowledge graphs have become popular over the past decade and frequently rely on the Resource Description Framework (RDF) or Property Graph (PG) databases as data models. However, the query languages for these two data models -- SPARQL for RDF and the PG traversal language Gremlin -- are lacking interoperability. We present Gremlinator, the first translator from SPARQL -- the W3C standardized language for RDF -- and Gremlin -- a popular property graph traversal language. Gremlinator translates SPARQL queries to Gremlin path traversals for executing graph pattern matching queries over graph databases. This allows a user, who is well versed in SPARQL, to access and query a wide variety of Graph Data Management Systems (DMSs) avoiding the steep learning curve for adapting to a new Graph Query Language (GQL). Gremlin is a graph computing system-agnostic traversal language (covering both OLTP graph database or OLAP graph processors), making it a desirable choice for supporting interoperability for querying Graph DMSs. Gremlinator currently supports the translation of a subset of SPARQL 1.0, specifically the SPARQL SELECT queries.
ONCE and ONCE+: Counting the Frequency of Time-constrained Serial Episodes in a Streaming Sequence
Venue: arXiv cs.DS 2018
Year: 2018

As a representative sequential pattern mining problem, counting the frequency of serial episodes from a streaming sequence has drawn continuous attention in academia due to its wide application in practice, e.g., telecommunication alarms, stock market, transaction logs, bioinformatics, etc. Although a number of serial episodes mining algorithms have been developed recently, most of them are neither stream-oriented, as they require multi-pass of dataset, nor time-aware, as they fail to take into account the time constraint of serial episodes. In this paper, we propose two novel one-pass algorithms, ONCE and ONCE+, each of which can respectively compute two popular frequencies of given episodes satisfying predefined time-constraint as signals in a stream arrives one-after-another. ONCE is only used for non-overlapped frequency where the occurrences of a serial episode in sequence are not intersected. ONCE+ is designed for the distinct frequency where the occurrences of a serial episode do not share any event. Theoretical study proves that our algorithm can correctly mine the frequency of target time constraint serial episodes in a given stream. Experimental study over both real-world and synthetic datasets demonstrates that the proposed algorithm can work, with little time and space, in signal-intensive streams where millions of signals arrive within a single second. Moreover, the algorithm has been applied in a real stream processing system, where the efficacy and efficiency of this work is tested in practical applications.
Design and Analysis of 5G Scenarios with 'simmer': An R Package for Fast DES Prototyping
Venue: arXiv cs.NI 2018
Year: 2018

Simulation frameworks are important tools for the analysis and design of communication networks and protocols, but they can result extremely costly and/or complex (for the case of very specialized tools), or too naive and lacking proper features and support (for the case of ad-hoc tools). In this paper, we present an analysis of three 5G scenarios using 'simmer', a recent R package for discrete-event simulation that sits between the above two paradigms. As our results show, it provides a simple yet very powerful syntax, supporting the efficient simulation of relatively complex scenarios at a low implementation cost.
tempoGAN: A Temporally Coherent, Volumetric GAN for Super-resolution Fluid Flow
Venue: arXiv cs.LG 2018
Year: 2018

We propose a temporally coherent generative model addressing the super-resolution problem for fluid flows. Our work represents a first approach to synthesize four-dimensional physics fields with neural networks. Based on a conditional generative adversarial network that is designed for the inference of three-dimensional volumetric data, our model generates consistent and detailed results by using a novel temporal discriminator, in addition to the commonly used spatial one. Our experiments show that the generator is able to infer more realistic high-resolution details by using additional physical quantities, such as low-resolution velocities or vorticities. Besides improvements in the training process and in the generated outputs, these inputs offer means for artistic control as well. We additionally employ a physics-aware data augmentation step, which is crucial to avoid overfitting and to reduce memory requirements. In this way, our network learns to generate advected quantities with highly detailed, realistic, and temporally coherent features. Our method works instantaneously, using only a single time-step of low-resolution fluid data. We demonstrate the abilities of our method using a variety of complex inputs and applications in two and three dimensions.
Resource Allocation for Containing Epidemics from Temporal Network Data
Venue: arXiv cs.SI 2018
Year: 2018

We study the problem of containing epidemic spreading processes in temporal networks. We specifically focus on the problem of finding a resource allocation to suppress epidemic infection, provided that an empirical time-series data of connectivities between nodes is available. Although this problem is of practical relevance, it has not been clear how an empirical time-series data can inform our strategy of resource allocations, due to the computational complexity of the problem. In this direction, we present a computationally efficient framework for finding a resource allocation that satisfies a given budget constraint and achieves a given control performance. The framework is based on convex programming and, moreover, allows the performance measure to be described by a wide class of functionals called posynomials with nonnegative exponents. We illustrate our theoretical results using a data of temporal interaction networks within a primary school.