OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Planar Two-Center Algorithms
Venue: arXiv cs.CG 2020
Year: 2020

We consider the planar Euclidean two-center problem in which given $n$ points in the plane we are to find two congruent disks of the smallest radius covering the points. We present a deterministic $O(n \log n)$-time algorithm for the case that the centers of the two optimal disks are close to each other, that is, the overlap of the two optimal disks is a constant fraction of the disk area. We also present a deterministic $O(n\log n)$-time algorithm for the case that the input points are in convex position. Both results improve the previous best $O(n\log n\log\log n)$ bound on the problems.
On the Robustness of Active Learning
Venue: arXiv cs.CV 2020
Year: 2020

Active Learning is concerned with the question of how to identify the most useful samples for a Machine Learning algorithm to be trained with. When applied correctly, it can be a very powerful tool to counteract the immense data requirements of Artificial Neural Networks. However, we find that it is often applied with not enough care and domain knowledge. As a consequence, unrealistic hopes are raised and transfer of the experimental results from one dataset to another becomes unnecessarily hard. In this work we analyse the robustness of different Active Learning methods with respect to classifier capacity, exchangeability and type, as well as hyperparameters and falsely labelled data. Experiments reveal possible biases towards the architecture used for sample selection, resulting in suboptimal performance for other classifiers. We further propose the new "Sum of Squared Logits" method based on the Simpson diversity index and investigate the effect of using the confusion matrix for balancing in sample selection.
DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
Venue: arXiv cs.LG 2020
Year: 2020

We introduce DREAM, a deep reinforcement learning algorithm that finds optimal strategies in imperfect-information games with multiple agents. Formally, DREAM converges to a Nash Equilibrium in two-player zero-sum games and to an extensive-form coarse correlated equilibrium in all other games. Our primary innovation is an effective algorithm that, in contrast to other regret-based deep learning algorithms, does not require access to a perfect simulator of the game to achieve good performance. We show that DREAM empirically achieves state-of-the-art performance among model-free algorithms in popular benchmark games, and is even competitive with algorithms that do use a perfect simulator.
Train Unit Shunting and Servicing: a Real-Life Application of Multi-Agent Path Finding
Venue: arXiv cs.MA 2020
Year: 2020

In between transportation services, trains are parked and maintained at shunting yards. The conflict-free routing of trains to and on these yards and the scheduling of service and maintenance tasks is known as the train unit shunting and service problem. Efficient use of the capacity of these yards is becoming increasingly important, because of increasing numbers of trains without proportional extensions of the yards. Efficiently scheduling maintenance activities is extremely challenging: currently only heuristics succeed in finding solutions to the integrated problem at all. Bounds are needed to determine the quality of these heuristics, and also to support investment decisions on increasing the yard capacity. For this, a complete algorithm for a possibly relaxed problem model is required. We analyze the potential of extending the model for multi-agent path finding to be used for such a relaxation.
Bi-Abduction for Shapes with Ordered Data
Venue: arXiv cs.LO 2020
Year: 2020

Shape analysis is of great importance for the verification of the correctness and memory-safety of heap-manipulating programs, yet such analyses have been shown to be highly difficult problems. The integration of separation logic into shape analyses has improved the effectiveness of the techniques, but the most significant advancement in this area is bi-abductive inference. Enabled by separation logic, bi-abduction - a combination of abductive inference and frame inference - is the key enabler for compositional reasoning, helping to scale up verification significantly. Indeed, the success of bi-abduction has led to the development of Infer, the tool used daily to verify Facebook's codebase of millions of lines of code. However, this success currently stays largely within the shape domain. To extend this impact towards the combination of shape and arithmetic domains, in this work, we present a novel one-stage bi-abductive procedure for a combination of data structures and ordering values. The procedure is designed in the spirit of the Unfold-and-Match paradigm where the inference is utilized to derive any mismatched portion. We have also implemented a prototype solver, based on the Cyclist library, and demonstrate its capabilities over a range of benchmarks from the SL-COMP competition. The experimental results show that our proposal shows promise for the specification inference in an automated verification of heap-manipulating programs.
Palette Sparsification Beyond $(Δ+1)$ Vertex Coloring
Venue: arXiv cs.DS 2020
Year: 2020

A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every $n$-vertex graph $G$ with maximum degree $Δ$, sampling $O(\log{n})$ colors per each vertex independently from $Δ+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Δ+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+\varepsilon) Δ$ coloring, sampling only $O_{\varepsilon}(\sqrt{\log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Δ+1)$ are triangle-free graphs which are $O(\fracΔ{\lnΔ})$ colorable. We prove that sampling $O(Δ^γ + \sqrt{\log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_γ(\fracΔ{\lnΔ})$ coloring of triangle-free graphs. * We show that sampling $O_{\varepsilon}(\log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+\varepsilon) \cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets $\{1,\ldots,deg(v)+1\}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
Privacy-Preserving Technology to Help Millions of People: Federated Prediction Model for Stroke Prevention
Venue: arXiv cs.LG 2020
Year: 2020

Prevention of stroke with its associated risk factors has been one of the public health priorities worldwide. Emerging artificial intelligence technology is being increasingly adopted to predict stroke. Because of privacy concerns, patient data are stored in distributed electronic health record (EHR) databases, voluminous clinical datasets, which prevent patient data from being aggregated and restrains AI technology to boost the accuracy of stroke prediction with centralized training data. In this work, our scientists and engineers propose a privacy-preserving scheme to predict the risk of stroke and deploy our federated prediction model on cloud servers. Our system of federated prediction model asynchronously supports any number of client connections and arbitrary local gradient iterations in each communication round. It adopts federated averaging during the model training process, without patient data being taken out of the hospitals during the whole process of model training and forecasting. With the privacy-preserving mechanism, our federated prediction model trains over all the healthcare data from hospitals in a certain city without actual data sharing among them. Therefore, it is not only secure but also more accurate than any single prediction model that trains over the data only from one single hospital. Especially for small hospitals with few confirmed stroke cases, our federated model boosts model performance by 10%~20% in several machine learning metrics. To help stroke experts comprehend the advantage of our prediction system more intuitively, we developed a mobile app that collects the key information of patients' statistics and demonstrates performance comparisons between the federated prediction model and the single prediction model during the federated training process.
Improving Post Training Neural Quantization: Layer-wise Calibration and Integer Programming
Venue: arXiv cs.LG 2020
Year: 2020

Lately, post-training quantization methods have gained considerable attention, as they are simple to use, and require only a small unlabeled calibration set. This small dataset cannot be used to fine-tune the model without significant over-fitting. Instead, these methods only use the calibration set to set the activations' dynamic ranges. However, such methods always resulted in significant accuracy degradation, when used below 8-bits (except on small datasets). Here we aim to break the 8-bit barrier. To this end, we minimize the quantization errors of each layer separately by optimizing its parameters over the calibration set. We empirically demonstrate that this approach is: (1) much less susceptible to over-fitting than the standard fine-tuning approaches, and can be used even on a very small calibration set; and (2) more powerful than previous methods, which only set the activations' dynamic ranges. Furthermore, we demonstrate how to optimally allocate the bit-widths for each layer, while constraining accuracy degradation or model compression by proposing a novel integer programming formulation. Finally, we suggest model global statistics tuning, to correct biases introduced during quantization. Together, these methods yield state-of-the-art results for both vision and text models. For instance, on ResNet50, we obtain less than 1\% accuracy degradation --- with 4-bit weights and activations in all layers, but the smallest two. We open-sourced our code.
LSTM-TrajGAN: A Deep Learning Approach to Trajectory Privacy Protection
Venue: arXiv cs.LG 2020
Year: 2020

The prevalence of location-based services contributes to the explosive growth of individual-level trajectory data and raises public concerns about privacy issues. In this research, we propose a novel LSTM-TrajGAN approach, which is an end-to-end deep learning model to generate privacy-preserving synthetic trajectory data for data sharing and publication. We design a loss metric function TrajLoss to measure the trajectory similarity losses for model training and optimization. The model is evaluated on the trajectory-user-linking task on a real-world semantic trajectory dataset. Compared with other common geomasking methods, our model can better prevent users from being re-identified, and it also preserves essential spatial, temporal, and thematic characteristics of the real trajectory data. The model better balances the effectiveness of trajectory privacy protection and the utility for spatial and temporal analyses, which offers new insights into the GeoAI-powered privacy protection.
PIDA: Smooth and Stable Flight Using Stochastic Dual Simplex Algorithm and Genetic Filter
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents a new Proportional-Integral-Derivative-Accelerated (PIDA) control with a derivative filter to improve quadcopter flight stability in a noisy environment. The mathematical model is derived from having an accurate model with a high level of fidelity by addressing the problems of non-linearity, uncertainties, and coupling. These uncertainties and measurement noises cause instability in flight and automatic hovering. The proposed controller associated with a heuristic Genetic Filter (GF) addresses these challenges. The tuning of the proposed PIDA controller associated with the objective of controlling is performed by Stochastic Dual Simplex Algorithm (SDSA). GF is applied to the PIDA control to estimate the observed states and parameters of quadcopters in both attitude and altitude. The simulation results show that the proposed control associated with GF has a strong ability to track the desired point in the presence of disturbances.
Reinforcement Learning as Iterative and Amortised Inference
Venue: arXiv cs.LG 2020
Year: 2020

There are several ways to categorise reinforcement learning (RL) algorithms, such as either model-based or model-free, policy-based or planning-based, on-policy or off-policy, and online or offline. Broad classification schemes such as these help provide a unified perspective on disparate techniques and can contextualise and guide the development of new algorithms. In this paper, we utilise the control as inference framework to outline a novel classification scheme based on amortised and iterative inference. We demonstrate that a wide range of algorithms can be classified in this manner providing a fresh perspective and highlighting a range of existing similarities. Moreover, we show that taking this perspective allows us to identify parts of the algorithmic design space which have been relatively unexplored, suggesting new routes to innovative RL algorithms.
The United Nations Sustainable Development Goals in Systems Engineering: Eliciting sustainability requirements
Venue: arXiv cs.CY 2020
Year: 2020

This paper discusses a PhD research project testing the hypothesis that using the United Nations Sustainable Development Goals(SDG) as explicit inputs to drive the Software Requirements Engineering process will result in requirements with improved sustainability benefits. The research has adopted the Design Science Research Method (DSRM) [21] to test a process named SDG Assessment for Requirements Elicitation (SDGARE). Three DSRM cycles are being used to test the hypothesis in safety-critical, highprecision, software-intensive systems in aerospace and healthcare. Initial results from the first two DSRM cycles support the hypothesis. However, these cycles are in a plan-driven (waterfall) development context and future research agenda would be a similar application in an Agile development context.
Differentially-private Federated Neural Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

Neural architecture search, which aims to automatically search for architectures (e.g., convolution, max pooling) of neural networks that maximize validation performance, has achieved remarkable progress recently. In many application scenarios, several parties would like to collaboratively search for a shared neural architecture by leveraging data from all parties. However, due to privacy concerns, no party wants its data to be seen by other parties. To address this problem, we propose federated neural architecture search (FNAS), where different parties collectively search for a differentiable architecture by exchanging gradients of architecture variables without exposing their data to other parties. To further preserve privacy, we study differentially-private FNAS (DP-FNAS), which adds random noise to the gradients of architecture variables. We provide theoretical guarantees of DP-FNAS in achieving differential privacy. Experiments show that DP-FNAS can search highly-performant neural architectures while protecting the privacy of individual parties. The code is available at https://github.com/UCSD-AI4H/DP-FNAS
Tight Bounds for Connectivity of Random K-out Graphs
Venue: arXiv cs.IT 2020
Year: 2020

Random K-out graphs are used in several applications including modeling by sensor networks secured by the random pairwise key predistribution scheme, and payment channel networks. The random K-out graph with $n$ nodes is constructed as follows. Each node draws an edge towards $K$ distinct nodes selected uniformly at random. The orientation of the edges is then ignored, yielding an undirected graph. An interesting property of random K-out graphs is that they are connected almost surely in the limit of large $n$ for any $K \geq2$. This means that they attain the property of being connected very easily, i.e., with far fewer edges ($O(n)$) as compared to classical random graph models including Erdős-Rényi graphs ($O(n \log n)$). This work aims to reveal to what extent the asymptotic behavior of random K-out graphs being connected easily extends to cases where the number $n$ of nodes is small. We establish upper and lower bounds on the probability of connectivity when $n$ is finite. Our lower bounds improve significantly upon the existing results, and indicate that random K-out graphs can attain a given probability of connectivity at much smaller network sizes than previously known. We also show that the established upper and lower bounds match order-wise; i.e., further improvement on the order of $n$ in the lower bound is not possible. In particular, we prove that the probability of connectivity is $1-Θ({1}/{n^{K^2-1}})$ for all $K \geq 2$. Through numerical simulations, we show that our bounds closely mirror the empirically observed probability of connectivity.
Multi-Density Sketch-to-Image Translation Network
Venue: arXiv cs.CV 2020
Year: 2020

Sketch-to-image (S2I) translation plays an important role in image synthesis and manipulation tasks, such as photo editing and colorization. Some specific S2I translation including sketch-to-photo and sketch-to-painting can be used as powerful tools in the art design industry. However, previous methods only support S2I translation with a single level of density, which gives less flexibility to users for controlling the input sketches. In this work, we propose the first multi-level density sketch-to-image translation framework, which allows the input sketch to cover a wide range from rough object outlines to micro structures. Moreover, to tackle the problem of noncontinuous representation of multi-level density input sketches, we project the density level into a continuous latent space, which can then be linearly controlled by a parameter. This allows users to conveniently control the densities of input sketches and generation of images. Moreover, our method has been successfully verified on various datasets for different applications including face editing, multi-modal sketch-to-photo translation, and anime colorization, providing coarse-to-fine levels of controls to these applications.
Mapping the "long tail" of research funding: A topic analysis of NSF grant proposals in the Division of Astronomical Sciences
Venue: arXiv cs.DL 2020
Year: 2020

"Long tail" data are considered to be smaller, heterogeneous, researcher-held data, which present unique data management and scholarly communication challenges. These data are presumably concentrated within relatively lower-funded projects due to insufficient resources for curation. To better understand the nature and distribution of long tail data, we examine National Science Foundation (NSF) funding patterns using Latent Dirichlet Analysis (LDA) and bibliographic data. We also introduce the concept of "Topic Investment" to capture differences in topics across funding levels and to illuminate the distribution of funding across topics. This study uses the discipline of astronomy as a case study, overall exploring possible associations between topic, funding level and research output, with implications for research policy and practice. We find that while different topics demonstrate different funding levels and publication patterns, dynamics predicted by the "long tail" theoretical framework presented here can be observed within NSF-funded topics in astronomy.
Latent Video Transformer
Venue: arXiv cs.CV 2020
Year: 2020

The video generation task can be formulated as a prediction of future video frames given some past frames. Recent generative models for videos face the problem of high computational requirements. Some models require up to 512 Tensor Processing Units for parallel training. In this work, we address this problem via modeling the dynamics in a latent space. After the transformation of frames into the latent space, our model predicts latent representation for the next frames in an autoregressive manner. We demonstrate the performance of our approach on BAIR Robot Pushing and Kinetics-600 datasets. The approach tends to reduce requirements to 8 Graphical Processing Units for training the models while maintaining comparable generation quality.
Set Distribution Networks: a Generative Model for Sets of Images
Venue: arXiv cs.LG 2020
Year: 2020

Images with shared characteristics naturally form sets. For example, in a face verification benchmark, images of the same identity form sets. For generative models, the standard way of dealing with sets is to represent each as a one hot vector, and learn a conditional generative model $p(\mathbf{x}|\mathbf{y})$. This representation assumes that the number of sets is limited and known, such that the distribution over sets reduces to a simple multinomial distribution. In contrast, we study a more generic problem where the number of sets is large and unknown. We introduce Set Distribution Networks (SDNs), a novel framework that learns to autoencode and freely generate sets. We achieve this by jointly learning a set encoder, set discriminator, set generator, and set prior. We show that SDNs are able to reconstruct image sets that preserve salient attributes of the inputs in our benchmark datasets, and are also able to generate novel objects/identities. We examine the sets generated by SDN with a pre-trained 3D reconstruction network and a face verification network, respectively, as a novel way to evaluate the quality of generated sets of images.
Reflection in Game-Based Learning: A Survey of Programming Games
Venue: arXiv cs.HC 2020
Year: 2020

Reflection is a critical aspect of the learning process. However, educational games tend to focus on supporting learning concepts rather than supporting reflection. While reflection occurs in educational games, the educational game design and research community can benefit from more knowledge of how to facilitate player reflection through game design. In this paper, we examine educational programming games and analyze how reflection is currently supported. We find that current approaches prioritize accuracy over the individual learning process and often only support reflection post-gameplay. Our analysis identifies common reflective features, and we develop a set of open areas for future work. We discuss these promising directions towards engaging the community in developing more mechanics for reflection in educational games.