OpenRaiser/Intern-Atlas huggingface dataset:
A Nonparametric Off-Policy Policy Gradient
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning (RL) algorithms still suffer from high sample complexity despite outstanding recent successes. The need for intensive interactions with the environment is especially observed in many widely popular policy gradient algorithms that perform updates using on-policy samples. The price of such inefficiency becomes evident in real-world scenarios such as interaction-driven robot learning, where the success of RL has been rather limited. We address this issue by building on the general sample efficiency of off-policy algorithms. With nonparametric regression and density estimation methods we construct a nonparametric Bellman equation in a principled manner, which allows us to obtain closed-form estimates of the value function, and to analytically express the full policy gradient. We provide a theoretical analysis of our estimate to show that it is consistent under mild smoothness assumptions and empirically show that our approach has better sample efficiency than state-of-the-art policy gradient methods.
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Venue: arXiv cs.CC 2020
Year: 2020

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ and degree $s$ (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.
Minimizing the Age of Information of Cognitive Radio-Based IoT Systems Under A Collision Constraint
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a cognitive radio-based IoT monitoring system, consisting of an IoT device that aims to update its measurement to a destination using cognitive radio technique. Specifically, the IoT device as a secondary user (SIoT), seeks and exploits the spectrum opportunities of the licensed band vacated by its primary user (PU) to deliver status updates without causing visible effects to the licensed operation. In this context, the SIoT should carefully make use of the licensed band and schedule when to transmit to maintain the timeliness of the status update. We adopt a recent metric, Age of Information (AoI), to characterize the timeliness of the status update of the SIoT. We aim to minimize the long-term average AoI of the SIoT while satisfying the collision constraint imposed by the PU by formulating a constrained Markov decision process (CMDP) problem. We first prove the existence of optimal stationary policy of the CMDP problem. The optimal stationary policy (termed age-optimal policy) is shown to be a randomized simple policy that randomizes between two deterministic policies with a fixed probability. We prove that the two deterministic policies have a threshold structure and further derive the closed-form expression of average AoI and collision probability for the deterministic threshold-structured policy by conducting Markov Chain analysis. The analytical expression offers an efficient way to calculate the threshold and randomization probability to form the age-optimal policy. For comparison, we also consider the throughput maximization policy (termed throughput-optimal policy) and analyze the average AoI performance under the throughput-optimal policy in the considered system. Numerical simulations show the superiority of the derived age-optimal policy over the throughput-optimal policy. We also unveil the impacts of various system parameters on the corresponding optimal policy and the resultant average AoI.
Comparing Python, Go, and C++ on the N-Queens Problem
Venue: arXiv cs.MS 2020
Year: 2020

Python currently is the dominant language in the field of Machine Learning but is often criticized for being slow to perform certain tasks. In this report, we use the well-known $N$-queens puzzle as a benchmark to show that once compiled using the Numba compiler it becomes competitive with C++ and Go in terms of execution speed while still allowing for very fast prototyping. This is true of both sequential and parallel programs. In most cases that arise in an academic environment, it therefore makes sense to develop in ordinary Python, identify computational bottlenecks, and use Numba to remove them.
On the Evaluation of Intelligent Process Automation
Venue: arXiv cs.HC 2020
Year: 2020

Intelligent Process Automation (IPA) is emerging as a sub-field of AI to support the automation of long-tail processes which requires the coordination of tasks across different systems. So far, the field of IPA has been largely driven by systems and use cases, lacking a more formal definition of the task and its assessment. This paper aims to address this gap by providing a formalisation of IPA and by proposing specific metrics to support the empirical evaluation of IPA systems. This work also compares and contrasts IPA against related tasks such as end-user programming and program synthesis.
Sample-based Distributional Policy Gradient
Venue: arXiv cs.LG 2020
Year: 2020

Distributional reinforcement learning (DRL) is a recent reinforcement learning framework whose success has been supported by various empirical studies. It relies on the key idea of replacing the expected return with the return distribution, which captures the intrinsic randomness of the long term rewards. Most of the existing literature on DRL focuses on problems with discrete action space and value based methods. In this work, motivated by applications in robotics with continuous action space control settings, we propose sample-based distributional policy gradient (SDPG) algorithm. It models the return distribution using samples via a reparameterization technique widely used in generative modeling and inference. We compare SDPG with the state-of-art policy gradient method in DRL, distributed distributional deterministic policy gradients (D4PG), which has demonstrated state-of-art performance. We apply SDPG and D4PG to multiple OpenAI Gym environments and observe that our algorithm shows better sample efficiency as well as higher reward for most tasks.
Synchronous Byzantine Lattice Agreement in ${\cal O}(\log (f))$ Rounds
Venue: arXiv cs.DC 2020
Year: 2020

In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. \cite{Attiya:1995}, a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element $e$ of a certain join-semi lattice $L$ and it has to decide on a value that contains $e$. Moreover, any pair $p_i,p_j$ of correct processes has to decide two values $dec_i$ and $dec_j$ that are comparable (e.g., $dec_i \leq dec_j$ or $dec_j < dec_i$). LA has been studied for its practical applications, as example it can be used to implement a snapshot objects \cite{Attiya:1995} or a replicated state machine with commutative operations \cite{Faleiro:2012}. Interestingly, the study of the Byzantine Lattice Agreement started only recently, and it has been mainly devoted to asynchronous systems. The synchronous case has been object of a recent pre-print \cite{Zheng:aa} where Zheng et al. propose an algorithm terminating in ${\cal O}(\sqrt f)$ rounds and tolerating $f < \lceil n/3 \rceil$ Byzantine processes. In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of $n$ processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if $f=n/3$ or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the {\em authenticated message} model), tolerates up to $f$ byzantine failures (where $f<n/3$) and that terminates in ${\cal O}(\log f)$ rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency ($f < n/4$). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing
Venue: arXiv cs.DS 2020
Year: 2020

In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans.
Learning Generative Models using Denoising Density Estimators
Venue: arXiv cs.LG 2020
Year: 2020

Learning probabilistic models that can estimate the density of a given set of samples, and generate samples from that density, is one of the fundamental challenges in unsupervised machine learning. We introduce a new generative model based on denoising density estimators (DDEs), which are scalar functions parameterized by neural networks, that are efficiently trained to represent kernel density estimators of the data. Leveraging DDEs, our main contribution is a novel technique to obtain generative models by minimizing the KL-divergence directly. We prove that our algorithm for obtaining generative models is guaranteed to converge to the correct solution. Our approach does not require specific network architecture as in normalizing flows, nor use ordinary differential equation solvers as in continuous normalizing flows. Experimental results demonstrate substantial improvement in density estimation and competitive performance in generative model training.
A novel tree-structured point cloud dataset for skeletonization algorithm evaluation
Venue: arXiv cs.CV 2020
Year: 2020

Curve skeleton extraction from unorganized point cloud is a fundamental task of computer vision and three-dimensional data preprocessing and visualization. A great amount of work has been done to extract skeleton from point cloud. but the lack of standard datasets of point cloud with ground truth skeleton makes it difficult to evaluate these algorithms. In this paper, we construct a brand new tree-structured point cloud dataset, including ground truth skeletons, and point cloud models. In addition, four types of point cloud are built on clean point cloud: point clouds with noise, point clouds with missing data, point clouds with different density, and point clouds with uneven density distribution. We first use tree editor to build the tree skeleton and corresponding mesh model. Since the implicit surface is sufficiently expressive to retain the edges and details of the complex branches model, we use the implicit surface to model the triangular mesh. With the implicit surface, virtual scanner is applied to the sampling of point cloud. Finally, considering the challenges in skeleton extraction, we introduce different methods to build four different types of point cloud models. This dataset can be used as standard dataset for skeleton extraction algorithms. And the evaluation between skeleton extraction algorithms can be performed by comparing the ground truth skeleton with the extracted skeleton.
Hybrid Multiple Attention Network for Semantic Segmentation in Aerial Images
Venue: arXiv cs.CV 2020
Year: 2020

Semantic segmentation in very high resolution (VHR) aerial images is one of the most challenging tasks in remote sensing image understanding. Most of the current approaches are based on deep convolutional neural networks (DCNNs). However, standard convolution with local receptive fields fails in modeling global dependencies. Prior researches have indicated that attention-based methods can capture long-range dependencies and further reconstruct the feature maps for better representation. Nevertheless, limited by the mere perspective of spacial and channel attention and huge computation complexity of self-attention mechanism, it is unlikely to model the effective semantic interdependencies between each pixel-pair of remote sensing data of complex spectra. In this work, we propose a novel attention-based framework named Hybrid Multiple Attention Network (HMANet) to adaptively capture global correlations from the perspective of space, channel and category in a more effective and efficient manner. Concretely, a class augmented attention (CAA) module embedded with a class channel attention (CCA) module can be used to compute category-based correlation and recalibrate the class-level information. Additionally, we introduce a simple yet effective region shuffle attention (RSA) module to reduce feature redundant and improve the efficiency of self-attention mechanism via region-wise representations. Extensive experimental results on the ISPRS Vaihingen and Potsdam benchmark demonstrate the effectiveness and efficiency of our HMANet over other state-of-the-art methods.
Short-Range Audio Channels Security: Survey of Mechanisms, Applications, and Research Challenges
Venue: arXiv cs.CR 2020
Year: 2020

Short-range audio channels have a few distinguishing characteristics: ease of use, low deployment costs, and easy to tune frequencies, to cite a few. Moreover, thanks to their seamless adaptability to the security context, many techniques and tools based on audio signals have been recently proposed. However, while the most promising solutions are turning into valuable commercial products, acoustic channels are increasingly used also to launch attacks against systems and devices, leading to security concerns that could thwart their adoption. To provide a rigorous, scientific, security-oriented review of the field, in this paper we survey and classify methods, applications, and use-cases rooted on short-range audio channels for the provisioning of security services---including Two-Factor Authentication techniques, pairing solutions, device authorization strategies, defense methodologies, and attack schemes. Moreover, we also point out the strengths and weaknesses deriving from the use of short-range audio channels. Finally, we provide open research issues in the context of short-range audio channels security, calling for contributions from both academia and industry.
Binary and Multitask Classification Model for Dutch Anaphora Resolution: Die/Dat Prediction
Venue: arXiv cs.CL 2020
Year: 2020

The correct use of Dutch pronouns 'die' and 'dat' is a stumbling block for both native and non-native speakers of Dutch due to the multiplicity of syntactic functions and the dependency on the antecedent's gender and number. Drawing on previous research conducted on neural context-dependent dt-mistake correction models (Heyman et al. 2018), this study constructs the first neural network model for Dutch demonstrative and relative pronoun resolution that specifically focuses on the correction and part-of-speech prediction of these two pronouns. Two separate datasets are built with sentences obtained from, respectively, the Dutch Europarl corpus (Koehn 2015) - which contains the proceedings of the European Parliament from 1996 to the present - and the SoNaR corpus (Oostdijk et al. 2013) - which contains Dutch texts from a variety of domains such as newspapers, blogs and legal texts. Firstly, a binary classification model solely predicts the correct 'die' or 'dat'. The classifier with a bidirectional long short-term memory architecture achieves 84.56% accuracy. Secondly, a multitask classification model simultaneously predicts the correct 'die' or 'dat' and its part-of-speech tag. The model containing a combination of a sentence and context encoder with both a bidirectional long short-term memory architecture results in 88.63% accuracy for die/dat prediction and 87.73% accuracy for part-of-speech prediction. More evenly-balanced data, larger word embeddings, an extra bidirectional long short-term memory layer and integrated part-of-speech knowledge positively affects die/dat prediction performance, while a context encoder architecture raises part-of-speech prediction performance. This study shows promising results and can serve as a starting point for future research on machine learning models for Dutch anaphora resolution.
Performance-Oriented Neural Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

Hardware-Software Co-Design is a highly successful strategy for improving performance of domain-specific computing systems. We argue for the application of the same methodology to deep learning; specifically, we propose to extend neural architecture search with information about the hardware to ensure that the model designs produced are highly efficient in addition to the typical criteria around accuracy. Using the task of keyword spotting in audio on edge computing devices, we demonstrate that our approach results in neural architecture that is not only highly accurate, but also efficiently mapped to the computing platform which will perform the inference. Using our modified neural architecture search, we demonstrate $0.88\%$ increase in TOP-1 accuracy with $1.85\times$ reduction in latency for keyword spotting in audio on an embedded SoC, and $1.59\times$ on a high-end GPU.
Evidence Based Decision Making in Blockchain Economic Systems: From Theory to Practice
Venue: arXiv cs.CR 2020
Year: 2020

We present a methodology for evidence based design of cryptoeconomic systems, and elucidate a real-world example of how this methodology was used in the design of a blockchain network. This work provides a rare insight into the application of Data Science and Stochastic Simulation and Modelling to Token Engineering. We demonstrate how the described process has the ability to uncover previously unexpected system level behaviors. Furthermore, it is observed that the process itself creates opportunities for the discovery of new knowledge and business understanding while developing the system from a high level specification to one precise enough to be executed as a computational model. Discovery of performance issues during design time can spare costly emergency interventions that would be necessary if issues instead became apparent in a production network. For this reason, network designers are increasingly adopting evidence-based design practices, such as the one described herein.
On The Optimality of The Whittle's Index Policy For Minimizing The Age of Information
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is out of reach. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.
Online Minimum Cost Matching on the Line with Recourse
Venue: arXiv cs.DS 2020
Year: 2020

In online minimum cost matching on the line, $n$ requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an $O(1)$-competitive algorithm. The best known online algorithm by Raghvendra [SoCG18] achieves a competitive factor of $Θ(\log n)$. This result matches a lower bound of $Ω(\log n)$ [Latin18] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an $O(1)$-competitive algorithm for online matching on the line that uses at most $O(n\log n)$ reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a $(1+\varepsilon)$-competitive algorithm that reassigns any request at most $O(\varepsilon^{-1.001})$ times. This special case is interesting as the aforementioned quite general lower bound $Ω(\log n)$ holds for such instances.
The Counterfactual $χ$-GAN
Venue: arXiv cs.LG 2020
Year: 2020

Causal inference often relies on the counterfactual framework, which requires that treatment assignment is independent of the outcome, known as strong ignorability. Approaches to enforcing strong ignorability in causal analyses of observational data include weighting and matching methods. Effect estimates, such as the average treatment effect (ATE), are then estimated as expectations under the reweighted or matched distribution, P . The choice of P is important and can impact the interpretation of the effect estimate and the variance of effect estimates. In this work, instead of specifying P, we learn a distribution that simultaneously maximizes coverage and minimizes variance of ATE estimates. In order to learn this distribution, this research proposes a generative adversarial network (GAN)-based model called the Counterfactual $χ$-GAN (cGAN), which also learns feature-balancing weights and supports unbiased causal estimation in the absence of unobserved confounding. Our model minimizes the Pearson $χ^2$ divergence, which we show simultaneously maximizes coverage and minimizes the variance of importance sampling estimates. To our knowledge, this is the first such application of the Pearson $χ^2$ divergence. We demonstrate the effectiveness of cGAN in achieving feature balance relative to established weighting methods in simulation and with real-world medical data.
Four Years in Review: Statistical Practices of Likert Scales in Human-Robot Interaction Studies
Venue: arXiv cs.HC 2020
Year: 2020

As robots become more prevalent, the importance of the field of human-robot interaction (HRI) grows accordingly. As such, we should endeavor to employ the best statistical practices. Likert scales are commonly used metrics in HRI to measure perceptions and attitudes. Due to misinformation or honest mistakes, most HRI researchers do not adopt best practices when analyzing Likert data. We conduct a review of psychometric literature to determine the current standard for Likert scale design and analysis. Next, we conduct a survey of four years of the International Conference on Human-Robot Interaction (2016 through 2019) and report on incorrect statistical practices and design of Likert scales. During these years, only 3 of the 110 papers applied proper statistical testing to correctly-designed Likert scales. Our analysis suggests there are areas for meaningful improvement in the design and testing of Likert scales. Lastly, we provide recommendations to improve the accuracy of conclusions drawn from Likert data.