OpenRaiser/Intern-Atlas huggingface dataset:
Sound up-to techniques and Complete abstract domains
Venue: arXiv cs.LO 2018
Year: 2018

Abstract interpretation is a method to automatically find invariants of programs or pieces of code whose semantics is given via least fixed-points. Up-to techniques have been introduced as enhancements of coinduction, an abstract principle to prove properties expressed via greatest fixed-points. While abstract interpretation is always sound by definition, the soundness of up-to techniques needs some ingenuity to be proven. For completeness, the setting is switched: up-to techniques are always complete, while abstract domains are not. In this work we show that, under reasonable assumptions, there is an evident connection between sound up-to techniques and complete abstract domains.
Using Machine Learning to Improve Cylindrical Algebraic Decomposition
Venue: arXiv cs.SC 2018
Year: 2018

Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead. Machine learning is the process of fitting a computer model to a complex function based on properties learned from measured data. In this paper we apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Groebner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.
A matrix-free approach to parallel and memory-efficient deformable image registration
Venue: arXiv cs.CV 2018
Year: 2018

We present a novel computational approach to fast and memory-efficient deformable image registration. In the variational registration model, the computation of the objective function derivatives is the computationally most expensive operation, both in terms of runtime and memory requirements. In order to target this bottleneck, we analyze the matrix structure of gradient and Hessian computations for the case of the normalized gradient fields distance measure and curvature regularization. Based on this analysis, we derive equivalent matrix-free closed-form expressions for derivative computations, eliminating the need for storing intermediate results and the costs of sparse matrix arithmetic. This has further benefits: (1) matrix computations can be fully parallelized, (2) memory complexity for derivative computation is reduced from linear to constant, and (3) overall computation times are substantially reduced. In comparison with an optimized matrix-based reference implementation, the CPU implementation achieves speedup factors between 3.1 and 9.7, and we are able to handle substantially higher resolutions. Using a GPU implementation, we achieve an additional speedup factor of up to 9.2. Furthermore, we evaluated the approach on real-world medical datasets. On ten publicly available lung CT images from the DIR-Lab 4DCT dataset, we achieve the best mean landmark error of 0.93 mm compared to other submissions on the DIR-Lab website, with an average runtime of only 9.23 s. Complete non-rigid registration of full-size 3D thorax-abdomen CT volumes from oncological follow-up is achieved in 12.6 s. The experimental results show that the proposed matrix-free algorithm enables the use of variational registration models also in applications which were previously impractical due to memory or runtime restrictions.
Persistent Monitoring of Stochastic Spatio-temporal Phenomena with a Small Team of Robots
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents a solution for persistent monitoring of real-world stochastic phenomena, where the underlying covariance structure changes sharply across time, using a small number of mobile robot sensors. We propose an adaptive solution for the problem where stochastic real-world dynamics are modeled as a Gaussian Process (GP). The belief on the underlying covariance structure is learned from recently observed dynamics as a Gaussian Mixture (GM) in the low-dimensional hyper-parameters space of the GP and adapted across time using Sequential Monte Carlo methods. Each robot samples a belief point from the GM and locally optimizes a set of informative regions by greedy maximization of the submodular entropy function. The key contributions of this paper are threefold: adapting the belief on the covariance using Markov Chain Monte Carlo (MCMC) sampling such that particles survive even under sharp covariance changes across time; exploiting the belief to transform the problem of entropy maximization into a decentralized one; and developing an approximation algorithm to maximize entropy on a set of informative regions in the continuous space. We illustrate the application of the proposed solution through extensive simulations using an artificial dataset and multiple real datasets from fixed sensor deployments, and compare it to three competing state-of-the-art approaches.
5PEN TECHNOLOGY: A New Dawn in Homogeneous and Heterogeneous Computing
Venue: arXiv cs.HC 2018
Year: 2018

This research work is a pair review into the conceptual frame work and innovation into Pen-style Personal Network Gadget Package (P-ISM) as inevitable tool to easy, fast and convenient access to the internet. Computing activities have increased the degree of people using personal computers (PCs), complicated packages and all form of social media applications (Apps.) have emerged within this short period. Meeting these trends (day to day activities) in more convenient form has led to the modern sophisticated garget such as Pen-Style Network Gadget Package (P-ISM) prototype. The growth in internet affects our lives in much better way than we know and its sustainability made 5 pen technology innovations a salt after.
Extracting Lungs from CT Images using Fully Convolutional Networks
Venue: arXiv cs.CV 2018
Year: 2018

Analysis of cancer and other pathological diseases, like the interstitial lung diseases (ILDs), is usually possible through Computed Tomography (CT) scans. To aid this, a preprocessing step of segmentation is performed to reduce the area to be analyzed, segmenting the lungs and removing unimportant regions. Generally, complex methods are developed to extract the lung region, also using hand-made feature extractors to enhance segmentation. With the popularity of deep learning techniques and its automated feature learning, we propose a lung segmentation approach using fully convolutional networks (FCNs) combined with fully connected conditional random fields (CRF), employed in many state-of-the-art segmentation works. Aiming to develop a generalized approach, the publicly available datasets from University Hospitals of Geneva (HUG) and VESSEL12 challenge were studied, including many healthy and pathological CT scans for evaluation. Experiments using the dataset individually, its trained model on the other dataset and a combination of both datasets were employed. Dice scores of $98.67\%\pm0.94\%$ for the HUG-ILD dataset and $99.19\%\pm0.37\%$ for the VESSEL12 dataset were achieved, outperforming works in the former and obtaining similar state-of-the-art results in the latter dataset, showing the capability in using deep learning approaches.
A comprehensive study of Game Theory applications for smart grids, demand side management programs, and transportation networks
Venue: arXiv cs.SY 2018
Year: 2018

Game theory is a powerful analytical tool for modeling decision makers strategies, behaviors and interactions. Act and decisions of a decision maker can benefit or negatively impact other decision makers interests. Game theory has been broadly used in economics, politics and engineering field. For example, game theory can model decision making procedure of different companies competing with each other to maximize their profit. Here, we present a brief introduction of game theory formulation and its applications. The focus of the chapter is non-cooperative Stackelberg game model and its applications in solving power system related problems. These applications include but not limited to; expanding transmission network, improving power system reliability, containing market power in the electricity market, solving power system dispatch, executing demand response and allocating resource in a wireless system. Finally, this chapter elaborates on solving a game theory problem through an example.
Optimized Base-Station Cache Allocation for Cloud Radio Access Network with Multicast Backhaul
Venue: arXiv cs.IT 2018
Year: 2018

The performance of cloud radio access network (C-RAN) is limited by the finite capacities of the backhaul links connecting the centralized processor (CP) with the base-stations (BSs), especially when the backhaul is implemented in a wireless medium. This paper proposes the use of wireless multicast together with BS caching, where the BSs pre-store contents of popular files, to augment the backhaul of C-RAN. For a downlink C-RAN consisting of a single cluster of BSs and wireless backhaul, this paper studies the optimal cache size allocation strategy among the BSs and the optimal multicast beamforming transmission strategy at the CP such that the user's requested messages are delivered from the CP to the BSs in the most efficient way. We first state a multicast backhaul rate expression based on a joint cache-channel coding scheme, which implies that larger cache sizes should be allocated to the BSs with weaker channels. We then formulate a two-timescale joint cache size allocation and beamforming design problem, where the cache is optimized offline based on the long-term channel statistical information, while the beamformer is designed during the file delivery phase based on the instantaneous channel state information. By leveraging the sample approximation method and the alternating direction method of multipliers (ADMM), we develop efficient algorithms for optimizing cache size allocation among the BSs, and quantify how much more cache should be allocated to the weaker BSs. We further consider the case with multiple files having different popularities and show that it is in general not optimal to entirely cache the most popular files first. Numerical results show considerable performance improvement of the optimized cache size allocation scheme over the uniform allocation and other heuristic schemes.
Switching Differentiator
Venue: arXiv cs.SY 2018
Year: 2018

A novel switching differentiator that has considerably simple form is proposed. Under the assumption that time-derivatives of the signal are norm-bounded, it is shown that estimation errors are convergent to the zeros asymptotically. The estimated derivatives shows neithor chattering nor peaking pheonomenon. A 1st-order diffentiator is firstly proposed and, by connecting this differentiator in series, higher-order derivatives are also available. Simulation results show that the proposed differentiator show extreme performance compared to the widly used previous differntiators such as high-gain observer or hige-order sliding mode differentiator.
Heavy Hitters over Interval Queries
Venue: arXiv cs.DS 2018
Year: 2018

Heavy hitters and frequency measurements are fundamental in many networking applications such as load balancing, QoS, and network security. This paper considers a generalized sliding window model that supports frequency and heavy hitters queries over an interval given at \emph{query time}. This enables drill-down queries, in which the behavior of the network can be examined in finer and finer granularities. For this model, we asymptotically improve the space bounds of existing work, reduce the update and query time to a constant, and provide deterministic solutions. When evaluated over real Internet packet traces, our fastest algorithm processes packets $90$--$250$ times faster, serves queries at least $730$ times quicker and consumes at least $40\%$ less space than the known method.
Control of Magnetic Microrobot Teams for Temporal Micromanipulation Tasks
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we present a control framework that allows magnetic microrobot teams to accomplish complex micromanipulation tasks captured by global Linear Temporal Logic (LTL) formulas. To address this problem, we propose an optimal control synthesis method that constructs discrete plans for the robots that satisfy both the assigned tasks as well as proximity constraints between the robots due to the physics of the problem. Our proposed algorithm relies on an existing optimal control synthesis approach combined with a novel sampling-based technique to reduce the state-space of the product automaton that is associated with the LTL specifications. The synthesized discrete plans are executed by the microrobots independently using local magnetic fields. Simulation studies show that the proposed algorithm can address large-scale planning problems that cannot be solved using existing optimal control synthesis approaches. Moreover, we present experimental results that also illustrate the potential of our method in practice. To the best of our knowledge, this is the first control framework that allows independent control of teams of magnetic microrobots for temporal micromanipulation tasks.
Exclusion of GNSS NLOS Receptions Caused by Dynamic Objects in Heavy Traffic Urban Scenarios Using Real-Time 3D Point Cloud: An Approach without 3D Maps
Venue: arXiv cs.RO 2018
Year: 2018

Absolute positioning is an essential factor for the arrival of autonomous driving. Global Navigation Satellites System (GNSS) receiver provides absolute localization for it. GNSS solution can provide satisfactory positioning in open or sub-urban areas, however, its performance suffered in super-urbanized area due to the phenomenon which are well-known as multipath effects and NLOS receptions. The effects dominate GNSS positioning performance in the area. The recent proposed 3D map aided (3DMA) GNSS can mitigate most of the multipath effects and NLOS receptions caused by buildings based on 3D city models. However, the same phenomenon caused by moving objects in urban area is currently not modelled in the 3D geographic information system (GIS). Moving objects with tall height, such as the double-decker bus, can also cause NLOS receptions because of the blockage of GNSS signals by surface of objects. Therefore, we present a novel method to exclude the NLOS receptions caused by double-decker bus in highly urbanized area, Hong Kong. To estimate the geometry dimension and orientation relative to GPS receiver, a Euclidean cluster algorithm and a classification method are used to detect the double-decker buses and calculate their relative locations. To increase the accuracy and reliability of the proposed NLOS exclusion method, an NLOS exclusion criterion is proposed to exclude the blocked satellites considering the elevation, signal noise ratio (SNR) and horizontal dilution of precision (HDOP). Finally, GNSS positioning is estimated by weighted least square (WLS) method using the remaining satellites after the NLOS exclusion. A static experiment was performed near a double-decker bus stop in Hong Kong, which verified the effectiveness of the proposed method.
Generating Interpretable Fuzzy Controllers using Particle Swarm Optimization and Genetic Programming
Venue: arXiv cs.AI 2018
Year: 2018

Autonomously training interpretable control strategies, called policies, using pre-existing plant trajectory data is of great interest in industrial applications. Fuzzy controllers have been used in industry for decades as interpretable and efficient system controllers. In this study, we introduce a fuzzy genetic programming (GP) approach called fuzzy GP reinforcement learning (FGPRL) that can select the relevant state features, determine the size of the required fuzzy rule set, and automatically adjust all the controller parameters simultaneously. Each GP individual's fitness is computed using model-based batch reinforcement learning (RL), which first trains a model using available system samples and subsequently performs Monte Carlo rollouts to predict each policy candidate's performance. We compare FGPRL to an extended version of a related method called fuzzy particle swarm reinforcement learning (FPSRL), which uses swarm intelligence to tune the fuzzy policy parameters. Experiments using an industrial benchmark show that FGPRL is able to autonomously learn interpretable fuzzy policies with high control performance.
A Basic Result on the Superposition of Arrival Processes in Deterministic Networks
Venue: arXiv cs.PF 2018
Year: 2018

Time-Sensitive Networking (TSN) and Deterministic Networking (DetNet) are emerging standards to enable deterministic, delay-critical communication in such networks. This naturally (re-)calls attention to the network calculus theory (NC), since a rich set of results for delay guarantee analysis have already been developed there. One could anticipate an immediate adoption of those existing network calculus results to TSN and DetNet. However, the fundamental difference between the traffic specification adopted in TSN and DetNet and those traffic models in NC makes this difficult, let alone that there is a long-standing open challenge in NC. To address them, this paper considers an arrival time function based max-plus NC traffic model. In particular, for the former, the mapping between the TSN / DetNet and the NC traffic model is proved. For the latter, the superposition property of the arrival time function based NC traffic model is found and proved. Appealingly, the proved superposition property shows a clear analogy with that of a well-known counterpart traffic model in NC. These results help make an important step towards the development of a system theory for delay guarantee analysis of TSN / DetNet networks.
On the Enumeration of Maximal $(Δ, γ)$-Cliques of a Temporal Network
Venue: arXiv cs.DS 2018
Year: 2018

A temporal network is a mathematical way of precisely representing a time varying relationship among a group of agents. In this paper, we introduce the notion of $(Δ, γ)$-Cliques of a temporal network, where every pair of vertices present in the clique communicates atleast $γ$ times in each $Δ$ period within a given time duration. We present an algorithm for enumerating all such maximal cliques present in the network. We also implement the proposed algorithm with three human contact network data sets. Based on the obtained results, we analyze the data set on multiple values of $Δ$ and $γ$, which helps in finding out contact groups with different frequencies.
On Obtaining Stable Rankings
Venue: arXiv cs.DB 2018
Year: 2018

Decision making is challenging when there is more than one criterion to consider. In such cases, it is common to assign a goodness score to each item as a weighted sum of its attribute values and rank them accordingly. Clearly, the ranking obtained depends on the weights used for this summation. Ideally, one would want the ranked order not to change if the weights are changed slightly. We call this property {\em stability} of the ranking. A consumer of a ranked list may trust the ranking more if it has high stability. A producer of a ranked list prefers to choose weights that result in a stable ranking, both to earn the trust of potential consumers and because a stable ranking is intrinsically likely to be more meaningful. In this paper, we develop a framework that can be used to assess the stability of a provided ranking and to obtain a stable ranking within an "acceptable" range of weight values (called "the region of interest"). We address the case where the user cares about the rank order of the entire set of items, and also the case where the user cares only about the top-$k$ items. Using a geometric interpretation, we propose algorithms that produce stable rankings. In addition to theoretical analyses, we conduct extensive experiments on real datasets that validate our proposal.
Precision Medicine as an Accelerator for Next Generation Cognitive Supercomputing
Venue: arXiv cs.AI 2018
Year: 2018

In the past several years, we have taken advantage of a number of opportunities to advance the intersection of next generation high-performance computing AI and big data technologies through partnerships in precision medicine. Today we are in the throes of piecing together what is likely the most unique convergence of medical data and computer technologies. But more deeply, we observe that the traditional paradigm of computer simulation and prediction needs fundamental revision. This is the time for a number of reasons. We will review what the drivers are, why now, how this has been approached over the past several years, and where we are heading.
Relational to RDF Data Exchange in Presence of a Shape Expression Schema
Venue: arXiv cs.DB 2018
Year: 2018

We study the relational to RDF data exchange problem, where the tar- get constraints are specified using Shape Expression schema (ShEx). We investi- gate two fundamental problems: 1) consistency which is checking for a given data exchange setting whether there always exists a solution for any source instance, and 2) constructing a universal solution which is a solution that represents the space of all solutions. We propose to use typed IRI constructors in source-to- target tuple generating dependencies to create the IRIs of the RDF graph from the values in the relational instance, and we translate ShEx into a set of target dependencies. We also identify data exchange settings that are key covered, a property that is decidable and guarantees consistency. Furthermore, we show that this property is a sufficient and necessary condition for the existence of universal solutions for a practical subclass of weakly-recursive ShEx.