OpenRaiser/Intern-Atlas huggingface dataset:
Pivot Selection for Median String Problem
Venue: arXiv cs.DS 2020
Year: 2020

The Median String Problem is W[1]-Hard under the Levenshtein distance, thus, approximation heuristics are used. Perturbation-based heuristics have been proved to be very competitive as regards the ratio approximation accuracy/convergence speed. However, the computational burden increase with the size of the set. In this paper, we explore the idea of reducing the size of the problem by selecting a subset of representative elements, i.e. pivots, that are used to compute the approximate median instead of the whole set. We aim to reduce the computation time through a reduction of the problem size while achieving similar approximation accuracy. We explain how we find those pivots and how to compute the median string from them. Results on commonly used test data suggest that our approach can reduce the computational requirements (measured in computed edit distances) by $8$\% with approximation accuracy as good as the state of the art heuristic. This work has been supported in part by CONICYT-PCHA/Doctorado Nacional/$2014-63140074$ through a Ph.D. Scholarship; Universidad Católica de la Santísima Concepción through the research project DIN-01/2016; European Union's Horizon 2020 under the Marie Skłodowska-Curie grant agreement $690941$; Millennium Institute for Foundational Research on Data (IMFD); FONDECYT-CONICYT grant number $1170497$; and for O. Pedreira, Xunta de Galicia/FEDER-UE refs. CSI ED431G/01 and GRC: ED431C 2017/58.
Deterministic Decoding for Discrete Data in Variational Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

Variational autoencoders are prominent generative models for modeling discrete data. However, with flexible decoders, they tend to ignore the latent codes. In this paper, we study a VAE model with a deterministic decoder (DD-VAE) for sequential data that selects the highest-scoring tokens instead of sampling. Deterministic decoding solely relies on latent codes as the only way to produce diverse objects, which improves the structure of the learned manifold. To implement DD-VAE, we propose a new class of bounded support proposal distributions and derive Kullback-Leibler divergence for Gaussian and uniform priors. We also study a continuous relaxation of deterministic decoding objective function and analyze the relation of reconstruction accuracy and relaxation parameters. We demonstrate the performance of DD-VAE on multiple datasets, including molecular generation and optimization problems.
Scheduling Kernels via Configuration LP
Venue: arXiv cs.DS 2020
Year: 2020

Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) -- a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time $p_{\max}$ has a kernelization yielding a reduced instance whose size is exponential in $p_{\max}$. Can this be reduced to polynomial in $p_{\max}$? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge $N$-fold integer programming. This solution is further reduced in size by a series of steps, until its encoding length is polynomial in the parameters. Then, we show that huge $N$-fold IP is in NP, which implies that there is a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge $N$-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our "conditional kernel" provides new insight.
Language-Integrated Updatable Views (Extended version)
Venue: arXiv cs.PL 2020
Year: 2020

Relational lenses are a modern approach to the view update problem in relational databases. As introduced by Bohannon et al. (2006), relational lenses allow the definition of updatable views by the composition of lenses performing individual transformations. Horn et al. (2018) provided the first implementation of incremental relational lenses, which demonstrated that relational lenses can be implemented efficiently by propagating changes to the database rather than replacing the entire database state. However, neither approach proposes a concrete language design; consequently, it is unclear how to integrate lenses into a general-purpose programming language, or how to check that lenses satisfy the well-formedness conditions needed for predictable behaviour. In this paper, we propose the first full account of relational lenses in a functional programming language, by extending the Links web programming language. We provide support for higher-order predicates, and provide the first account of typechecking relational lenses which is amenable to implementation. We prove the soundness of our typing rules, and illustrate our approach by implementing a curation interface for a scientific database application.
Resource Allocation Technique for Hybrid TDMA-NOMA System with Opportunistic Time Assignment
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we develop a resource allocation technique for a hybrid time division multiple access (TDMA) - non-orthogonal multiple access (NOMA) system with opportunistic time assignment. In particular, the available transmission time is divided into several time-slots, through which multiple users are served by exploiting power-domain NOMA. To fully exploit underlying benefits of this hybrid TDMA-NOMA system, we utilize the available resources efficiently by jointly allocating transmit power and time-slots to several groups of users in the system. Furthermore, these resources are allocated to maximize minimum rate of the users in the system. However, this max-min resource allocation problem is non-convex due to coupled design parameters of time and power allocations. Hence, we exploit a novel second-order cone formulation to overcome this non-convexity issue and develop an iterative algorithm to realize a solution to the original max-min problem. Simulation results show that this joint resource allocation technique has a considerable performance enhancement in terms of both minimum achieved rate and overall system throughput compared to that of the conventional resource allocation technique where equal time-slots are assigned to the groups of users.
Fast uncertainty quantification of tracer distribution in the brain interstitial fluid with multilevel and quasi Monte Carlo
Venue: arXiv cs.CE 2020
Year: 2020

Efficient uncertainty quantification algorithms are key to understand the propagation of uncertainty -- from uncertain input parameters to uncertain output quantities -- in high resolution mathematical models of brain physiology. Advanced Monte Carlo methods such as quasi Monte Carlo (QMC) and multilevel Monte Carlo (MLMC) have the potential to dramatically improve upon standard Monte Carlo (MC) methods, but their applicability and performance in biomedical applications is underexplored. In this paper, we design and apply QMC and MLMC methods to quantify uncertainty in a convection-diffusion model of tracer transport within the brain. We show that QMC outperforms standard MC simulations when the number of random inputs is small. MLMC considerably outperforms both QMC and standard MC methods and should therefore be preferred for brain transport models.
The Impact of Hole Geometry on Relative Robustness of In-Painting Networks: An Empirical Study
Venue: arXiv cs.CV 2020
Year: 2020

In-painting networks use existing pixels to generate appropriate pixels to fill "holes" placed on parts of an image. A 2-D in-painting network's input usually consists of (1) a three-channel 2-D image, and (2) an additional channel for the "holes" to be in-painted in that image. In this paper, we study the robustness of a given in-painting neural network against variations in hole geometry distributions. We observe that the robustness of an in-painting network is dependent on the probability distribution function (PDF) of the hole geometry presented to it during its training even if the underlying image dataset used (in training and testing) does not alter. We develop an experimental methodology for testing and evaluating relative robustness of in-painting networks against four different kinds of hole geometry PDFs. We examine a number of hypothesis regarding (1) the natural bias of in-painting networks to the hole distribution used for their training, (2) the underlying dataset's ability to differentiate relative robustness as hole distributions vary in a train-test (cross-comparison) grid, and (3) the impact of the directional distribution of edges in the holes and in the image dataset. We present results for L1, PSNR and SSIM quality metrics and develop a specific measure of relative in-painting robustness to be used in cross-comparison grids based on these quality metrics. (One can incorporate other quality metrics in this relative measure.) The empirical work reported here is an initial step in a broader and deeper investigation of "filling the blank" neural networks' sensitivity, robustness and regularization with respect to hole "geometry" PDFs, and it suggests further research in this domain.
Markov Chain Monte Carlo with Neural Network Surrogates: Application to Contaminant Source Identification
Venue: arXiv cs.CE 2020
Year: 2020

Subsurface remediation often involves reconstruction of contaminant release history from sparse observations of solute concentration. Markov Chain Monte Carlo (MCMC), the most accurate and general method for this task, is rarely used in practice because of its high computational cost associated with multiple solves of contaminant transport equations. We propose an adaptive MCMC method, in which a transport model is replaced with a fast and accurate surrogate model in the form of a deep convolutional neural network (CNN). The CNN-based surrogate is trained on a small number of the transport model runs based on the prior knowledge of the unknown release history. Thus reduced computational cost allows one to reduce the sampling error associated with construction of the approximate likelihood function. As all MCMC strategies for source identification, our method has an added advantage of quantifying predictive uncertainty and accounting for measurement errors. Our numerical experiments demonstrate the accuracy comparable to that of MCMC with the forward transport model, which is obtained at a fraction of the computational cost of the latter.
Creating High Resolution Images with a Latent Adversarial Generator
Venue: arXiv cs.CV 2020
Year: 2020

Generating realistic images is difficult, and many formulations for this task have been proposed recently. If we restrict the task to that of generating a particular class of images, however, the task becomes more tractable. That is to say, instead of generating an arbitrary image as a sample from the manifold of natural images, we propose to sample images from a particular "subspace" of natural images, directed by a low-resolution image from the same subspace. The problem we address, while close to the formulation of the single-image super-resolution problem, is in fact rather different. Single image super-resolution is the task of predicting the image closest to the ground truth from a relatively low resolution image. We propose to produce samples of high resolution images given extremely small inputs with a new method called Latent Adversarial Generator (LAG). In our generative sampling framework, we only use the input (possibly of very low-resolution) to direct what class of samples the network should produce. As such, the output of our algorithm is not a unique image that relates to the input, but rather a possible se} of related images sampled from the manifold of natural images. Our method learns exclusively in the latent space of the adversary using perceptual loss -- it does not have a pixel loss.
LSQ: Load Balancing in Large-Scale Heterogeneous Systems with Multiple Dispatchers
Venue: arXiv cs.NI 2020
Year: 2020

Nowadays, the efficiency and even the feasibility of traditional load-balancing policies are challenged by the rapid growth of cloud infrastructure and the increasing levels of server heterogeneity. In such heterogeneous systems with many load-balancers, traditional solutions, such as JSQ, incur a prohibitively large communication overhead and detrimental incast effects due to herd behavior. Alternative low-communication policies, such as JSQ(d) and the recently proposed JIQ, are either unstable or provide poor performance. We introduce the Local Shortest Queue (LSQ) family of load balancing algorithms. In these algorithms, each dispatcher maintains its own, local, and possibly outdated view of the server queue lengths, and keeps using JSQ on its local view. A small communication overhead is used infrequently to update this local view. We formally prove that as long as the error in these local estimates of the server queue lengths is bounded in expectation, the entire system is strongly stable. Finally, in simulations, we show how simple and stable LSQ policies exhibit appealing performance and significantly outperform existing low-communication policies, while using an equivalent communication budget. In particular, our simple policies often outperform even JSQ due to their reduction of herd behavior. We further show how, by relying on smart servers (i.e., advanced pull-based communication), we can further improve performance and lower communication overhead.
Dynamic Experience Replay
Venue: arXiv cs.AI 2020
Year: 2020

We present a novel technique called Dynamic Experience Replay (DER) that allows Reinforcement Learning (RL) algorithms to use experience replay samples not only from human demonstrations but also successful transitions generated by RL agents during training and therefore improve training efficiency. It can be combined with an arbitrary off-policy RL algorithm, such as DDPG or DQN, and their distributed versions. We build upon Ape-X DDPG and demonstrate our approach on robotic tight-fitting joint assembly tasks, based on force/torque and Cartesian pose observations. In particular, we run experiments on two different tasks: peg-in-hole and lap-joint. In each case, we compare different replay buffer structures and how DER affects them. Our ablation studies show that Dynamic Experience Replay is a crucial ingredient that either largely shortens the training time in these challenging environments or solves the tasks that the vanilla Ape-X DDPG cannot solve. We also show that our policies learned purely in simulation can be deployed successfully on the real robot. The video presenting our experiments is available at https://sites.google.com/site/dynamicexperiencereplay
Fake Generated Painting Detection via Frequency Analysis
Venue: arXiv cs.CV 2020
Year: 2020

With the development of deep neural networks, digital fake paintings can be generated by various style transfer algorithms.To detect the fake generated paintings, we analyze the fake generated and real paintings in Fourier frequency domain and observe statistical differences and artifacts. Based on our observations, we propose Fake Generated Painting Detection via Frequency Analysis (FGPD-FA) by extracting three types of features in frequency domain. Besides, we also propose a digital fake painting detection database for assessing the proposed method. Experimental results demonstrate the excellence of the proposed method in different testing conditions.
Adaptive Verifiability-Driven Strategy for Evolutionary Approximation of Arithmetic Circuits
Venue: arXiv cs.NE 2020
Year: 2020

We present a novel approach for designing complex approximate arithmetic circuits that trade correctness for power consumption and play important role in many energy-aware applications. Our approach integrates in a unique way formal methods providing formal guarantees on the approximation error into an evolutionary circuit optimisation algorithm. The key idea is to employ a novel adaptive search strategy that drives the evolution towards promptly verifiable approximate circuits. As demonstrated in an extensive experimental evaluation including several structurally different arithmetic circuits and target precisions, the search strategy provides superior scalability and versatility with respect to various approximation scenarios. Our approach significantly improves capabilities of the existing methods and paves a way towards an automated design process of provably-correct circuit approximations.
Characterizations and approximability of hard counting classes below #P
Venue: arXiv cs.CC 2020
Year: 2020

An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P, is of key importance, as it contains self-reducible counting problems with easy decision version, thus eligible to be approximable. Indeed, most problems known so far to admit an fpras fall into this class. An open question raised recently by the community of descriptive complexity is to find a logical characterization of TotP and of robust subclasses of TotP. In this work we define two subclasses of TotP, in terms of descriptive complexity, both of which are robust in the sense that they have natural complete problems, which are defined in terms of satisfiability of Boolean formulae. We then explore the relationship between the class of approximable counting problems and TotP. We prove that TotP $\nsubseteq$ FPRAS if and only if NP $\neq$ RP and FPRAS $\nsubseteq$ TotP unless RP = P. To this end we introduce two ancillary classes that can both be seen as counting versions of RP. We further show that FPRAS lies between one of these classes and a counting version of BPP. Finally, we provide a complete picture of inclusions among all the classes defined or discussed in this paper with respect to different conjectures about the NP vs. RP vs. P questions.
Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning
Venue: arXiv cs.DB 2020
Year: 2020

Similar trajectory search is a fundamental problem and has been well studied over the past two decades. However, the similar subtrajectory search (SimSub) problem, aiming to return a portion of a trajectory (i.e., a subtrajectory) which is the most similar to a query trajectory, has been mostly disregarded despite that it could capture trajectory similarity in a finer-grained way and many applications take subtrajectories as basic units for analysis. In this paper, we study the SimSub problem and develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those non-learning based algorithms in terms of effectiveness and efficiency. We conduct experiments on real-world trajectory datasets, which verify the effectiveness and efficiency of the proposed algorithms.
An Incremental Explanation of Inference in Hybrid Bayesian Networks for Increasing Model Trustworthiness and Supporting Clinical Decision Making
Venue: arXiv cs.AI 2020
Year: 2020

Various AI models are increasingly being considered as part of clinical decision-support tools. However, the trustworthiness of such models is rarely considered. Clinicians are more likely to use a model if they can understand and trust its predictions. Key to this is if its underlying reasoning can be explained. A Bayesian network (BN) model has the advantage that it is not a black-box and its reasoning can be explained. In this paper, we propose an incremental explanation of inference that can be applied to hybrid BNs, i.e. those that contain both discrete and continuous nodes. The key questions that we answer are: (1) which important evidence supports or contradicts the prediction, and (2) through which intermediate variables does the information flow. The explanation is illustrated using a real clinical case study. A small evaluation study is also conducted.
Microservice Decomposition via Static and Dynamic Analysis of the Monolith
Venue: arXiv cs.SE 2020
Year: 2020

Migrating monolithic software systems into microservices requires the application of decomposition techniquesto find and select appropriate service boundaries. These techniques are often based on domain knowledge, static code analysis, and non-functional requirements such as maintainability. In this paper, we present our experience with an approach that extends static analysis with dynamic analysis of a legacy software system's runtime behavior, including the live trace visualization to support the decomposition into microservices. Overall, our approach combines established analysis techniques for microservice decomposition, such as the bounded context pattern of domain-driven design, and enriches the collected information via dynamic software visualization to identify appropriate microservice boundaries. In collaboration with the German IT service provider adesso SE, we applied our approach to their real-word, legacy lottery application in|FOCUS to identify good microservice decompositions for this layered monolithic Enterprise Java system.
Hadath: From Social Media Mapping to Multi-Resolution Event-Enriched Maps
Venue: arXiv cs.IR 2020
Year: 2020

Publicly available data is increasing rapidly, and will continue to grow with the advancement of technologies in sensors, smartphones and the Internet of Things. Data from multiple sources can improve coverage and provide more relevant knowledge about surrounding events and points of Interest. The strength of one source of data can compensate for the shortcomings of another source by providing supplementary information. Maps are also getting popular day-by-day and people are using it to achieve their daily task smoothly and efficiently. Starting from paper maps hundred years ago, multiple type of maps are available with point of interest, real-time traffic update or displaying micro-blogs from social media. In this paper, we introduce Hadath, a system that displays multi-resolution live events of interest from a variety of available data sources. The system has been designed to be able to handle multiple type of inputs by encapsulating incoming unstructured data into generic data packets. System extracts local events of interest from generic data packets and identify their spatio-temporal scope to display such events on a map, so that as a user changes the zoom level, only events of appropriate scope are displayed. This allows us to show live events in correspondence to the scale of view - when viewing at a city scale, we see events of higher significance, while zooming in to a neighbourhood, events of a more local interest are highlighted. The final output creates a unique and dynamic map browsing experience. Finally, to validate our proposed system, we conducted experiments on social media data.