OpenRaiser/Intern-Atlas huggingface dataset:
A Combinatorial Characterization of Self-Stabilizing Population Protocols
Venue: arXiv cs.DC 2020
Year: 2020

We fully characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of $n$ finite state agents in which a malicious scheduler selects an arbitrary sequence of pairwise interactions under a global fairness condition. We show a necessary and sufficient condition for self-stabilization. Specifically we show that functions without certain set-theoretic conditions are impossible to compute in a self-stabilizing manner. Our main contribution is in the converse, where we construct a self-stabilizing protocol for all other functions that meet this characterization. Our positive construction uses Dickson's Lemma to develop the notion of the root set, a concept that turns out to fundamentally characterize self-stabilization in this model. We believe it may lend to characterizing self-stabilization in more general models as well.
Improved approximation ratios for two Euclidean maximum spanning tree problems
Venue: arXiv cs.CG 2020
Year: 2020

We study the following two maximization problems related to spanning trees in the Euclidean plane. It is not known whether or not these problems are NP-hard. We present approximation algorithms with better approximation ratios for both problems. The improved ratios are obtained mainly by employing the Steiner ratio, which has not been used in this context earlier. (i) Longest noncrossing spanning tree: Given a set of points in the plane, the goal is to find a maximum-length noncrossing spanning tree. Alon, Rajagopalan, and Suri (SoCG 1993) studied this problem for the first time and gave a $0.5$-approximation algorithm. Over the years, the approximation ratio has been successively improved to $0.502$, $0.503$, and to $0.512$ which is the current best ratio, due to Cabello et al.. We revisit this problem and improve the ratio further to $0.519$. The improvement is achieved by a collection of ideas, some from previous works and some new ideas (including the use of the Steiner ratio), along with a more refined analysis. (ii) Longest spanning tree with neighborhoods: Given a collection of regions (neighborhoods) in the plane, the goal is to select a point in each neighborhood so that the longest spanning tree on selected points has maximum length. We present an algorithm with approximation ratio $0.524$ for this problem. The previous best ratio, due to Chen and Dumitrescu, is $0.511$ which is in turn the first improvement beyond the trivial ratio $0.5$. Our algorithm is fairly simple, its analysis is relatively short, and it takes linear time after computing a diametral pair of points. The simplicity comes from the fact that our solution belongs to a set containing three stars and one double-star. The shortness and the improvement come from the use of the Steiner ratio.
Large Product Key Memory for Pretrained Language Models
Venue: arXiv cs.CL 2020
Year: 2020

Product key memory (PKM) proposed by Lample et al. (2019) enables to improve prediction accuracy by increasing model capacity efficiently with insignificant computational overhead. However, their empirical application is only limited to causal language modeling. Motivated by the recent success of pretrained language models (PLMs), we investigate how to incorporate large PKM into PLMs that can be finetuned for a wide variety of downstream NLP tasks. We define a new memory usage metric, and careful observation using this metric reveals that most memory slots remain outdated during the training of PKM-augmented models. To train better PLMs by tackling this issue, we propose simple but effective solutions: (1) initialization from the model weights pretrained without memory and (2) augmenting PKM by addition rather than replacing a feed-forward network. We verify that both of them are crucial for the pretraining of PKM-augmented PLMs, enhancing memory utilization and downstream performance. Code and pretrained weights are available at https://github.com/clovaai/pkm-transformers.
Intrinsic Hierarchical Clustering Behavior Recovers Higher Dimensional Shape Information
Venue: arXiv cs.CG 2020
Year: 2020

We show that specific higher dimensional shape information of point cloud data can be recovered by observing lower dimensional hierarchical clustering dynamics. We generate multiple point samples from point clouds and perform hierarchical clustering within each sample to produce dendrograms. From these dendrograms, we take cluster evolution and merging data that capture clustering behavior to construct simplified diagrams that record the lifetime of clusters akin to what zero dimensional persistence diagrams do in topological data analysis. We compare differences between these diagrams using the bottleneck metric, and examine the resulting distribution. Finally, we show that statistical features drawn from these bottleneck distance distributions detect artefacts of, and can be tapped to recover higher dimensional shape characteristics.
BGM: Building a Dynamic Guidance Map without Visual Images for Trajectory Prediction
Venue: arXiv cs.CV 2020
Year: 2020

Visual images usually contain the informative context of the environment, thereby helping to predict agents' behaviors. However, they hardly impose the dynamic effects on agents' actual behaviors due to the respectively fixed semantics. To solve this problem, we propose a deterministic model named BGM to construct a guidance map to represent the dynamic semantics, which circumvents to use visual images for each agent to reflect the difference of activities in different periods. We first record all agents' activities in the scene within a period close to the current to construct a guidance map and then feed it to a Context CNN to obtain their context features. We adopt a Historical Trajectory Encoder to extract the trajectory features and then combine them with the context feature as the input of the social energy based trajectory decoder, thus obtaining the prediction that meets the social rules. Experiments demonstrate that BGM achieves state-of-the-art prediction accuracy on the two widely used ETH and UCY datasets and handles more complex scenarios.
Active Tuning
Venue: arXiv cs.LG 2020
Year: 2020

We introduce Active Tuning, a novel paradigm for optimizing the internal dynamics of recurrent neural networks (RNNs) on the fly. In contrast to the conventional sequence-to-sequence mapping scheme, Active Tuning decouples the RNN's recurrent neural activities from the input stream, using the unfolding temporal gradient signal to tune the internal dynamics into the data stream. As a consequence, the model output depends only on its internal hidden dynamics and the closed-loop feedback of its own predictions; its hidden state is continuously adapted by means of the temporal gradient resulting from backpropagating the discrepancy between the signal observations and the model outputs through time. In this way, Active Tuning infers the signal actively but indirectly based on the originally learned temporal patterns, fitting the most plausible hidden state sequence into the observations. We demonstrate the effectiveness of Active Tuning on several time series prediction benchmarks, including multiple super-imposed sine waves, a chaotic double pendulum, and spatiotemporal wave dynamics. Active Tuning consistently improves the robustness, accuracy, and generalization abilities of all evaluated models. Moreover, networks trained for signal prediction and denoising can be successfully applied to a much larger range of noise conditions with the help of Active Tuning. Thus, given a capable time series predictor, Active Tuning enhances its online signal filtering, denoising, and reconstruction abilities without the need for additional training.
Unconstrained Text Detection in Manga
Venue: arXiv cs.CV 2020
Year: 2020

The detection and recognition of unconstrained text is an open problem in research. Text in comic books has unusual styles that raise many challenges for text detection. This work aims to identify text characters at a pixel level in a comic genre with highly sophisticated text styles: Japanese manga. To overcome the lack of a manga dataset with individual character level annotations, we create our own. Most of the literature in text detection use bounding box metrics, which are unsuitable for pixel-level evaluation. Thus, we implemented special metrics to evaluate performance. Using these resources, we designed and evaluated a deep network model, outperforming current methods for text detection in manga in most metrics.
Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we study the problem of learning partially observed linear dynamical systems from a single sample trajectory. A major practical challenge in the existing system identification methods is the undesirable dependency of their required sample size on the system dimension: roughly speaking, they presume and rely on sample sizes that scale linearly with respect to the system dimension. Evidently, in high-dimensional regime where the system dimension is large, it may be costly, if not impossible, to collect as many samples from the unknown system. In this paper, we will remedy this undesirable dependency on the system dimension by introducing an $\ell_1$-regularized estimation method that can accurately estimate the Markov parameters of the system, provided that the number of samples scale logarithmically with the system dimension. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems: it shows that the Markov parameters of the system can be learned in the high-dimensional setting, where the number of samples is significantly smaller than the system dimension. Traditionally, the $\ell_1$-regularized estimators have been used to promote sparsity in the estimated parameters. By resorting to the notion of "weak sparsity", we show that, irrespective of the true sparsity of the system, a similar regularized estimator can be used to reduce the sample complexity of learning partially observed linear systems, provided that the true system is inherently stable.
EDNA-Covid: A Large-Scale Covid-19 Tweets Dataset Collected with the EDNA Streaming Toolkit
Venue: arXiv cs.SI 2020
Year: 2020

The Covid-19 pandemic has fundamentally altered many facets of our lives. With nationwide lockdowns and stay-at-home advisories, conversations about the pandemic have naturally moved to social networks, e.g. Twitter. This affords an unprecedented insight into the evolution of social discourse in the presence of a long-running destabilizing factor such as a pandemic with the high-volume, high-velocity, high-noise Covid-19 Twitter feed. However, real-time information extraction from such a data stream requires a fault-tolerant streaming infrastructure to perform the non-trivial integration of heterogenous data sources from news organizations, social feeds, and authoritative medical organizations like the CDC. To address this, we present (i) the EDNA streaming toolkit for consuming and processing streaming data, and (ii) EDNA-Covid, a multilingual, large-scale dataset of coronavirus-related tweets collected with EDNA since January 25, 2020. EDNA-Covid includes, at time of this publication, over 600M tweets from around the world in over 10 languages. We release both the EDNA toolkit and the EDNA-Covid dataset to the public so that they can be used to extract valuable insights on this extraordinary social event.
Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits
Venue: arXiv cs.LG 2020
Year: 2020

Modifying the reward-biased maximum likelihood method originally proposed in the adaptive control literature, we propose novel learning algorithms to handle the explore-exploit trade-off in linear bandits problems as well as generalized linear bandits problems. We develop novel index policies that we prove achieve order-optimality, and show that they achieve empirical performance competitive with the state-of-the-art benchmark methods in extensive experiments. The new policies achieve this with low computation time per pull for linear bandits, and thereby resulting in both favorable regret as well as computational efficiency.
Did You Get The Gist Of It? Understanding How Visualization Impacts Decision-Making
Venue: arXiv cs.HC 2020
Year: 2020

As visualization researchers evaluate the impact of visualization design on decision-making, they often hold a one-dimensional perspective on the cognitive processes behind making a decision. Several psychological and economical researchers have shown that to make decisions, people rely on quantitative reasoning as well as gist-based intuition -- two systems that operate in parallel. In this position paper, we discuss decision theories and provide suggestions to bridge the gap between the evaluation of decision-making in visualization and psychology research. The goal is to question the limits of our knowledge and to advocate for a more nuanced understanding of decision-making with visualization.
Leakage-Adjusted Simulatability: Can Models Generate Non-Trivial Explanations of Their Behavior in Natural Language?
Venue: arXiv cs.CL 2020
Year: 2020

Data collection for natural language (NL) understanding tasks has increasingly included human explanations alongside data points, allowing past works to introduce models that both perform a task and generate NL explanations for their outputs. Yet to date, model-generated explanations have been evaluated on the basis of surface-level similarities to human explanations, both through automatic metrics like BLEU and human evaluations. We argue that these evaluations are insufficient, since they fail to indicate whether explanations support actual model behavior (faithfulness), rather than simply match what a human would say (plausibility). In this work, we address the problem of evaluating explanations from the model simulatability perspective. Our contributions are as follows: (1) We introduce a leakage-adjusted simulatability (LAS) metric for evaluating NL explanations, which measures how well explanations help an observer predict a model's output, while controlling for how explanations can directly leak the output. We use a model as a proxy for a human observer, and validate this choice with two human subject experiments. (2) Using the CoS-E and e-SNLI datasets, we evaluate two existing generative graphical models and two new approaches; one rationalizing method we introduce achieves roughly human-level LAS scores. (3) Lastly, we frame explanation generation as a multi-agent game and optimize explanations for simulatability while penalizing label leakage, which can improve LAS scores. We provide code for the experiments in this paper at https://github.com/peterbhase/LAS-NL-Explanations
DART: A Lightweight Quality-Suggestive Data-to-Text Annotation Tool
Venue: arXiv cs.CL 2020
Year: 2020

We present a lightweight annotation tool, the Data AnnotatoR Tool (DART), for the general task of labeling structured data with textual descriptions. The tool is implemented as an interactive application that reduces human efforts in annotating large quantities of structured data, e.g. in the format of a table or tree structure. By using a backend sequence-to-sequence model, our system iteratively analyzes the annotated labels in order to better sample unlabeled data. In a simulation experiment performed on annotating large quantities of structured data, DART has been shown to reduce the total number of annotations needed with active learning and automatically suggesting relevant labels.
Machine Learning for Gas and Oil Exploration
Venue: arXiv cs.LG 2020
Year: 2020

Drilling boreholes for gas and oil extraction is an expensive process and profitability strongly depends on characteristics of the subsurface. As profitability is a key success factor, companies in the industry utilise well logs to explore the subsurface beforehand. These well logs contain various characteristics of the rock around the borehole, which allow petrophysicists to determine the expected amount of contained hydrocarbon. However, these logs are often incomplete and, as a consequence, the subsequent analyses cannot exploit the full potential of the well logs. In this paper we demonstrate that Machine Learning can be applied to \emph{fill in the gaps} and estimate missing values. We investigate how the amount of training data influences the accuracy of prediction and how to best design regression models (Gradient Boosting and neural network) to obtain optimal results. We then explore the models' predictions both quantitatively, tracking the prediction error, and qualitatively, capturing the evolution of the measured and predicted values for a given property with depth. Combining the findings has enabled us to develop a predictive model that completes the well logs, increasing their quality and potential commercial value.
Towards the Detection of Building Occupancy with Synthetic Environmental Data
Venue: arXiv cs.LG 2020
Year: 2020

Information about room-level occupancy is crucial to many building-related tasks, such as building automation or energy performance simulation. Current occupancy detection literature focuses on data-driven methods, but is mostly based on small case studies with few rooms. The necessity to collect room-specific data for each room of interest impedes applicability of machine learning, especially data-intensive deep learning approaches, in practice. To derive accurate predictions from less data, we suggest knowledge transfer from synthetic data. In this paper, we conduct an experiment with data from a CO$_2$ sensor in an office room, and additional synthetic data obtained from a simulation. Our contribution includes (a) a simulation method for CO$_2$ dynamics under randomized occupant behavior, (b) a proof of concept for knowledge transfer from simulated CO$_2$ data, and (c) an outline of future research implications. From our results, we can conclude that the transfer approach can effectively reduce the required amount of data for model training.
Fast Fourier Transformation for Optimizing Convolutional Neural Networks in Object Recognition
Venue: arXiv cs.CV 2020
Year: 2020

This paper proposes to use Fast Fourier Transformation-based U-Net (a refined fully convolutional networks) and perform image convolution in neural networks. Leveraging the Fast Fourier Transformation, it reduces the image convolution costs involved in the Convolutional Neural Networks (CNNs) and thus reduces the overall computational costs. The proposed model identifies the object information from the images. We apply the Fast Fourier transform algorithm on an image data set to obtain more accessible information about the image data, before segmenting them through the U-Net architecture. More specifically, we implement the FFT-based convolutional neural network to improve the training time of the network. The proposed approach was applied to publicly available Broad Bioimage Benchmark Collection (BBBC) dataset. Our model demonstrated improvement in training time during convolution from $600-700$ ms/step to $400-500$ ms/step. We evaluated the accuracy of our model using Intersection over Union (IoU) metric showing significant improvements.
Test4Enforcers: Test Case Generation for Software Enforcers
Venue: arXiv cs.SE 2020
Year: 2020

Software enforcers can be used to modify the runtime behavior of software applications to guarantee that relevant correctness policies are satisfied. Indeed, the implementation of software enforcers can be tricky, due to the heterogeneity of the situations that they must be able to handle. Assessing their ability to steer the behavior of the target system without introducing any side effect is an important challenge to fully trust the resulting system. To address this challenge, this paper presents Test4Enforcers, the first approach to derive thorough test suites that can validate the impact of enforcers on a target system. The paper also shows how to implement the Test4Enforcers approach in the DroidBot test generator to validate enforcers for Android apps.
Fake Reviews Detection through Analysis of Linguistic Features
Venue: arXiv cs.CL 2020
Year: 2020

Online reviews play an integral part for success or failure of businesses. Prior to purchasing services or goods, customers first review the online comments submitted by previous customers. However, it is possible to superficially boost or hinder some businesses through posting counterfeit and fake reviews. This paper explores a natural language processing approach to identify fake reviews. We present a detailed analysis of linguistic features for distinguishing fake and trustworthy online reviews. We study 15 linguistic features and measure their significance and importance towards the classification schemes employed in this study. Our results indicate that fake reviews tend to include more redundant terms and pauses, and generally contain longer sentences. The application of several machine learning classification algorithms revealed that we were able to discriminate fake from real reviews with high accuracy using these linguistic features.
Comments on the "Generalized" KLJN Key Exchanger with Arbitrary Resistors: Power, Impedance, Security
Venue: arXiv cs.CR 2020
Year: 2020

In (Nature) Science Report 5 (2015) 13653, Vadai, Mingesz and Gingl (VMG) introduce a new Kirchhoff-law-Johnson-noise (KLJN) secure key exchanger that operates with 4 arbitrary resistors (instead of 2 arbitrary resistance values forming 2 identical resistor pairs in the original system). They state that in this new, VMG-KLJN, non-equilibrium system with nonzero power flow, the security during the exchange of the two (HL and LH) bit values is as strong as in the original KLJN scheme. Moreover, they claim that, at practical conditions, their VMG-KLJN protocol "supports more robust protection against attacks". First, we investigate the power flow and thermal equilibrium issues of the VMG-KLJN system with 4 arbitrary resistors. Then we introduce a new KLJN protocol that allows the arbitrary choice of 3 resistors from the 4, while it still operates with zero power flow during the exchange of single bits by utilizing a specific value of the 4th resistor and a binary temperature set for the exchanged (HL and LH) bit values. Then we show that, in general, the KLJN schemes with more than 2 arbitrary resistors (including our new protocol mentioned above) are prone to 4 new passive attacks utilizing the parasitic capacitance and inductance in the cable, while the original KLJN scheme is naturally immune against these new attacks. The core of the security vulnerability exploited by these attacks is the different line resistances in the HL and LH cases. Therefore, on the contrary of the statement and claim cited above, the practical VMG-KLJN system is less secure than the original KLJN scheme. We introduce another 2, modified, non-equilibrium KLJN systems to eliminate the vulnerability against some - but not all - of these attacks. However the price for that is the loss of arbitrariness of the selection of the 4th resistor and the information leak still remains greater than zero.