OpenRaiser/Intern-Atlas huggingface dataset:
Brick: Asynchronous Payment Channels
Venue: arXiv cs.DC 2020
Year: 2020

Off-chain protocols (channels) are a promising solution to the scalability and privacy challenges of blockchain payments. Current proposals, however, require synchrony assumptions to preserve the safety of a channel, leaking to an adversary the exact amount of time needed to control the network for a successful attack. In this paper, we introduce Brick, the first payment channel that remains secure under network asynchrony and concurrently provides correct incentives. The core idea is to incorporate the conflict resolution process within the channel by introducing a rational committee of external parties, called Wardens. Hence, if a party wants to close a channel unilaterally, it can only get the committee's approval for the last valid state. Brick provides sub-second latency because it does not employ heavy-weight consensus. Instead, Brick uses consistent broadcast to announce updates and close the channel, a light-weight abstraction that is powerful enough to preserve safety and liveness to any rational parties. Furthermore, we consider permissioned blockchains, where the additional property of auditability might be desired for regulatory purposes. We introduce Brick+, an off-chain construction that provides auditability on top of Brick without conflicting with its privacy guarantees. We formally define the properties our payment channel construction should fulfill, and prove that both Brick and Brick+ satisfy them. We also design incentives for Brick such that honest and rational behavior aligns. Finally, we provide a reference implementation of the smart contracts in Solidity.
Using Neural Networks for Relation Extraction from Biomedical Literature
Venue: arXiv cs.CL 2020
Year: 2020

Using different sources of information to support automated extracting of relations between biomedical concepts contributes to the development of our understanding of biological systems. The primary comprehensive source of these relations is biomedical literature. Several relation extraction approaches have been proposed to identify relations between concepts in biomedical literature, namely, using neural networks algorithms. The use of multichannel architectures composed of multiple data representations, as in deep neural networks, is leading to state-of-the-art results. The right combination of data representations can eventually lead us to even higher evaluation scores in relation extraction tasks. Thus, biomedical ontologies play a fundamental role by providing semantic and ancestry information about an entity. The incorporation of biomedical ontologies has already been proved to enhance previous state-of-the-art results.
Evaluating and Calibrating Uncertainty Prediction in Regression Tasks
Venue: arXiv cs.LG 2020
Year: 2020

Predicting not only the target but also an accurate measure of uncertainty is important for many machine learning applications and in particular safety-critical ones. In this work we study the calibration of uncertainty prediction for regression tasks which often arise in real-world systems. We show that the existing definition for calibration of a regression uncertainty [Kuleshov et al. 2018] has severe limitations in distinguishing informative from non-informative uncertainty predictions. We propose a new definition that escapes this caveat and an evaluation method using a simple histogram-based approach. Our method clusters examples with similar uncertainty prediction and compares the prediction with the empirical uncertainty on these examples. We also propose a simple, scaling-based calibration method that preforms as well as much more complex ones. We show results on both a synthetic, controlled problem and on the object detection bounding-box regression task using the COCO and KITTI datasets.
When do Trajectories have Bounded Sensitivity to Cumulative Perturbations?
Venue: arXiv cs.SY 2020
Year: 2020

We investigate sensitivity to cumulative perturbations for a few dynamical system classes of practical interest. A system is said to have bounded sensitivity to cumulative perturbations (bounded sensitivity, for short) if an additive disturbance leads to a change in the state trajectory that is bounded by a constant multiple of the size of the cumulative disturbance. As our main result, we show that there exist dynamical systems in the form of (negative) gradient field of a convex function that have unbounded sensitivity. We show that the result holds even when the convex potential function is piecewise linear. This resolves a question raised in [1], wherein it was shown that the (negative) (sub)gradient field of a piecewise linear and convex function has bounded sensitivity if the number of linear pieces is finite. Our results establish that the finiteness assumption is indeed necessary. Among our other results, we provide a necessary and sufficient condition for a linear dynamical system to have bounded sensitivity to cumulative perturbations. We also establish that the bounded sensitivity property is preserved, when a dynamical system with bounded sensitivity undergoes certain transformations. These transformations include convolution, time discretization, and spreading of a system (a transformation that captures approximate solutions of a system).
On Collapsing Prefix Normal Words
Venue: arXiv cs.FL 2020
Year: 2020

Prefix normal words are binary words in which each prefix has at least the same number of $\so$s as any factor of the same length. Firstly introduced by Fici and Lipták in 2011, the problem of determining the index of the prefix equivalence relation is still open. In this paper, we investigate two aspects of the problem, namely prefix normal palindromes and so-called collapsing words (extending the notion of critical words). We prove characterizations for both the palindromes and the collapsing words and show their connection. Based on this, we show that still open problems regarding prefix normal words can be split into certain subproblems.
Clustering and Recognition of Spatiotemporal Features through Interpretable Embedding of Sequence to Sequence Recurrent Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Encoder-decoder recurrent neural network models (RNN Seq2Seq) have achieved great success in ubiquitous areas of computation and applications. It was shown to be successful in modeling data with both temporal and spatial dependencies for translation or prediction tasks. In this study, we propose an embedding approach to visualize and interpret the representation of data by these models. Furthermore, we show that the embedding is an effective method for unsupervised learning and can be utilized to estimate the optimality of model training. In particular, we demonstrate that embedding space projections of the decoder states of RNN Seq2Seq model trained on sequences prediction are organized in clusters capturing similarities and differences in the dynamics of these sequences. Such performance corresponds to an unsupervised clustering of any spatio-temporal features and can be employed for time-dependent problems such as temporal segmentation, clustering of dynamic activity, self-supervised classification, action recognition, failure prediction, etc. We test and demonstrate the application of the embedding methodology to time-sequences of 3D human body poses. We show that the methodology provides a high-quality unsupervised categorization of movements.
Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?
Venue: arXiv cs.LG 2020
Year: 2020

Based on differential privacy (DP) framework, we introduce and unify privacy definitions for the multi-armed bandit algorithms. We represent the framework with a unified graphical model and use it to connect privacy definitions. We derive and contrast lower bounds on the regret of bandit algorithms satisfying these definitions. We leverage a unified proving technique to achieve all the lower bounds. We show that for all of them, the learner's regret is increased by a multiplicative factor dependent on the privacy level $ε$. We observe that the dependency is weaker when we do not require local differential privacy for the rewards.
SECRET: Semantically Enhanced Classification of Real-world Tasks
Venue: arXiv cs.LG 2020
Year: 2020

Supervised machine learning (ML) algorithms are aimed at maximizing classification performance under available energy and storage constraints. They try to map the training data to the corresponding labels while ensuring generalizability to unseen data. However, they do not integrate meaning-based relationships among labels in the decision process. On the other hand, natural language processing (NLP) algorithms emphasize the importance of semantic information. In this paper, we synthesize the complementary advantages of supervised ML and NLP algorithms into one method that we refer to as SECRET (Semantically Enhanced Classification of REal-world Tasks). SECRET performs classifications by fusing the semantic information of the labels with the available data: it combines the feature space of the supervised algorithms with the semantic space of the NLP algorithms and predicts labels based on this joint space. Experimental results indicate that, compared to traditional supervised learning, SECRET achieves up to 14.0% accuracy and 13.1% F1 score improvements. Moreover, compared to ensemble methods, SECRET achieves up to 12.7% accuracy and 13.3% F1 score improvements. This points to a new research direction for supervised classification based on incorporation of semantic information.
Are Disentangled Representations Helpful for Abstract Visual Reasoning?
Venue: arXiv cs.LG 2020
Year: 2020

A disentangled representation encodes information about the salient factors of variation in the data independently. Although it is often argued that this representational format is useful in learning to solve many real-world down-stream tasks, there is little empirical evidence that supports this claim. In this paper, we conduct a large-scale study that investigates whether disentangled representations are more suitable for abstract reasoning tasks. Using two new tasks similar to Raven's Progressive Matrices, we evaluate the usefulness of the representations learned by 360 state-of-the-art unsupervised disentanglement models. Based on these representations, we train 3600 abstract reasoning models and observe that disentangled representations do in fact lead to better down-stream performance. In particular, they enable quicker learning using fewer samples.
Calibrated Surrogate Maximization of Linear-fractional Utility in Binary Classification
Venue: arXiv cs.LG 2020
Year: 2020

Complex classification performance metrics such as the F${}_β$-measure and Jaccard index are often used, in order to handle class-imbalanced cases such as information retrieval and image segmentation. These performance metrics are not decomposable, that is, they cannot be expressed in a per-example manner, which hinders a straightforward application of M-estimation widely used in supervised learning. In this paper, we consider linear-fractional metrics, which are a family of classification performance metrics that encompasses many standard ones such as the F${}_β$-measure and Jaccard index, and propose methods to directly maximize performances under those metrics. A clue to tackle their direct optimization is a calibrated surrogate utility, which is a tractable lower bound of the true utility function representing a given metric. We characterize sufficient conditions which make the surrogate maximization coincide with the maximization of the true utility. Simulation results on benchmark datasets validate the effectiveness of our calibrated surrogate maximization especially if the sample sizes are extremely small.
Adapting Text Embeddings for Causal Inference
Venue: arXiv cs.LG 2020
Year: 2020

Does adding a theorem to a paper affect its chance of acceptance? Does labeling a post with the author's gender affect the post popularity? This paper develops a method to estimate such causal effects from observational text data, adjusting for confounding features of the text such as the subject or writing quality. We assume that the text suffices for causal adjustment but that, in practice, it is prohibitively high-dimensional. To address this challenge, we develop causally sufficient embeddings, low-dimensional document representations that preserve sufficient information for causal identification and allow for efficient estimation of causal effects. Causally sufficient embeddings combine two ideas. The first is supervised dimensionality reduction: causal adjustment requires only the aspects of text that are predictive of both the treatment and outcome. The second is efficient language modeling: representations of text are designed to dispose of linguistically irrelevant information, and this information is also causally irrelevant. Our method adapts language models (specifically, word embeddings and topic models) to learn document embeddings that are able to predict both treatment and outcome. We study causally sufficient embeddings with semi-synthetic datasets and find that they improve causal estimation over related embedding methods. We illustrate the methods by answering the two motivating questions---the effect of a theorem on paper acceptance and the effect of a gender label on post popularity. Code and data available at https://github.com/vveitch/causal-text-embeddings-tf2}{github.com/vveitch/causal-text-embeddings-tf2
Dynamic Adaptation of Software-defined Networks for IoT Systems: A Search-based Approach
Venue: arXiv cs.SE 2020
Year: 2020

The concept of Internet of Things (IoT) has led to the development of many complex and critical systems such as smart emergency management systems. IoT-enabled applications typically depend on a communication network for transmitting large volumes of data in unpredictable and changing environments. These networks are prone to congestion when there is a burst in demand, e.g., as an emergency situation is unfolding, and therefore rely on configurable software-defined networks (SDN). In this paper, we propose a dynamic adaptive SDN configuration approach for IoT systems. The approach enables resolving congestion in real time while minimizing network utilization, data transmission delays and adaptation costs. Our approach builds on existing work in dynamic adaptive search-based software engineering (SBSE) to reconfigure an SDN while simultaneously ensuring multiple quality of service criteria. We evaluate our approach on an industrial national emergency management system, which is aimed at detecting disasters and emergencies, and facilitating recovery and rescue operations by providing first responders with a reliable communication infrastructure. Our results indicate that (1) our approach is able to efficiently and effectively adapt an SDN to dynamically resolve congestion, and (2) compared to two baseline data forwarding algorithms that are static and non-adaptive, our approach increases data transmission rate by a factor of at least 3 and decreases data loss by at least 70%.
Learning Nonsymmetric Determinantal Point Processes
Venue: arXiv cs.LG 2020
Year: 2020

Determinantal point processes (DPPs) have attracted substantial attention as an elegant probabilistic model that captures the balance between quality and diversity within sets. DPPs are conventionally parameterized by a positive semi-definite kernel matrix, and this symmetric kernel encodes only repulsive interactions between items. These so-called symmetric DPPs have significant expressive power, and have been successfully applied to a variety of machine learning tasks, including recommendation systems, information retrieval, and automatic summarization, among many others. Efficient algorithms for learning symmetric DPPs and sampling from these models have been reasonably well studied. However, relatively little attention has been given to nonsymmetric DPPs, which relax the symmetric constraint on the kernel. Nonsymmetric DPPs allow for both repulsive and attractive item interactions, which can significantly improve modeling power, resulting in a model that may better fit for some applications. We present a method that enables a tractable algorithm, based on maximum likelihood estimation, for learning nonsymmetric DPPs from data composed of observed subsets. Our method imposes a particular decomposition of the nonsymmetric kernel that enables such tractable learning algorithms, which we analyze both theoretically and experimentally. We evaluate our model on synthetic and real-world datasets, demonstrating improved predictive performance compared to symmetric DPPs, which have previously shown strong performance on modeling tasks associated with these datasets.
Corpus Distillation for Effective Fuzzing: A Comparative Evaluation
Venue: arXiv cs.CR 2020
Year: 2020

Mutation-based fuzzing typically uses an initial set of non-crashing seed inputs (a corpus) from which to generate new inputs by mutation. A corpus of potential seeds will often contain thousands of similar inputs. This lack of diversity can lead to wasted fuzzing effort by exhaustive mutation from all available seeds. To address this, fuzzers come with distillation tools (e.g., afl-cmin) that select the smallest subset of seeds that triggers the same range of instrumentation data points as the full corpus. Common practice suggests that minimizing the number and cumulative size of the seeds leads to more efficient fuzzing, which we explore systematically. We present results of 34+ CPU-years of fuzzing with five distillation approaches to understand their impact in finding bugs in real-world software. We evaluate a number of techniques, includibng the existing afl-cmin and Minset, and also MoonLight---a freely available, configurable, state-of-the-art, open-source, tool. Our experiments compare the effectiveness of distillation approaches, targeting the Google Fuzzer Test Suite and a diverse set of six real-world libraries and programs, covering 13 different input file formats across 16 programs. Our results show that distillation is a necessary precursor to any fuzzing campaign when starting with a large initial corpus. We compare the effectiveness of alternative distillation approaches. Notably, our experiments reveal that state-of-the-art distillation tools (such as MoonLight and Minset) do not exclusively find all of the 33 bugs (in the real-world targets) exposed by our combined campaign: each technique appears to have its own strengths. We find (and report) new bugs with MoonLight that are not found by Minset, and vice versa. Moreover, afl-cmin fails to reveal many of these bugs. Of the 33 bugs revealed in our campaign, seven new bugs have received CVEs.
Differential Equation Invariance Axiomatization
Venue: arXiv cs.LO 2020
Year: 2020

This article proves the completeness of an axiomatization for differential equation invariants described by Noetherian functions. First, the differential equation axioms of differential dynamic logic are shown to be complete for reasoning about analytic invariants. Completeness crucially exploits differential ghosts, which introduce additional variables that can be chosen to evolve freely along new differential equations. Cleverly chosen differential ghosts are the proof-theoretical counterpart of dark matter. They create new hypothetical state, whose relationship to the original state variables satisfies invariants that did not exist before. The reflection of these new invariants in the original system then enables its analysis. An extended axiomatization with existence and uniqueness axioms is complete for all local progress properties, and, with a real induction axiom, is complete for all semianalytic invariants. This parsimonious axiomatization serves as the logical foundation for reasoning about invariants of differential equations. Indeed, it is precisely this logical treatment that enables the generalization of completeness to the Noetherian case.
Metric Learning for Individual Fairness
Venue: arXiv cs.LG 2020
Year: 2020

There has been much discussion recently about how fairness should be measured or enforced in classification. Individual Fairness [Dwork, Hardt, Pitassi, Reingold, Zemel, 2012], which requires that similar individuals be treated similarly, is a highly appealing definition as it gives strong guarantees on treatment of individuals. Unfortunately, the need for a task-specific similarity metric has prevented its use in practice. In this work, we propose a solution to the problem of approximating a metric for Individual Fairness based on human judgments. Our model assumes that we have access to a human fairness arbiter, who can answer a limited set of queries concerning similarity of individuals for a particular task, is free of explicit biases and possesses sufficient domain knowledge to evaluate similarity. Our contributions include definitions for metric approximation relevant for Individual Fairness, constructions for approximations from a limited number of realistic queries to the arbiter on a sample of individuals, and learning procedures to construct hypotheses for metric approximations which generalize to unseen samples under certain assumptions of learnability of distance threshold functions.
Does It Make Sense? And Why? A Pilot Study for Sense Making and Explanation
Venue: arXiv cs.AI 2020
Year: 2020

Introducing common sense to natural language understanding systems has received increasing research attention. It remains a fundamental question on how to evaluate whether a system has a sense making capability. Existing benchmarks measures commonsense knowledge indirectly and without explanation. In this paper, we release a benchmark to directly test whether a system can differentiate natural language statements that make sense from those that do not make sense. In addition, a system is asked to identify the most crucial reason why a statement does not make sense. We evaluate models trained over large-scale language modeling tasks as well as human performance, showing that there are different challenges for system sense making.
Impact of Traffic Lights on Trajectory Forecasting of Human-driven Vehicles Near Signalized Intersections
Venue: arXiv cs.RO 2020
Year: 2020

Forecasting trajectories of human-driven vehicles is a crucial problem in autonomous driving. Trajectory forecasting in the urban area is particularly hard due to complex interactions with cars and pedestrians, and traffic lights (TLs). Unlike the former that has been widely studied, the impact of TLs on the trajectory prediction has been rarely discussed. In this work, we first identify the less studied, perhaps overlooked impact of TLs. Second, we present a novel resolution that is mindful of the impact, inspired by the fact that human drives differently depending on signal phase (green, yellow, red) and timing (elapsed time). Central to the proposed approach is Human Policy Models which model how drivers react to various states of TLs by mapping a sequence of states of vehicles and TLs to a subsequent action (acceleration) of the vehicle. We then combine the Human Policy Models with a known transition function (system dynamics) to conduct a sequential prediction; thus our approach is viewed as Behavior Cloning. One novelty of our approach is the use of vehicle-to-infrastructure communications to obtain the future states of TLs. We demonstrate the impact of TL and the proposed approach using an ablation study for longitudinal trajectory forecasting tasks on real-world driving data recorded near a signalized intersection. Finally, we propose probabilistic (generative) Human Policy Models which provide probabilistic contexts and capture competing policies, e.g., pass or stop in the yellow-light dilemma zone.