OpenRaiser/Intern-Atlas huggingface dataset:
Think you have Solved Direct-Answer Question Answering? Try ARC-DA, the Direct-Answer AI2 Reasoning Challenge
Venue: arXiv cs.CL 2021
Year: 2021

We present the ARC-DA dataset, a direct-answer ("open response", "freeform") version of the ARC (AI2 Reasoning Challenge) multiple-choice dataset. While ARC has been influential in the community, its multiple-choice format is unrepresentative of real-world questions, and multiple choice formats can be particularly susceptible to artifacts. The ARC-DA dataset addresses these concerns by converting questions to direct-answer format using a combination of crowdsourcing and expert review. The resulting dataset contains 2985 questions with a total of 8436 valid answers (questions typically have more than one valid answer). ARC-DA is one of the first DA datasets of natural questions that often require reasoning, and where appropriate question decompositions are not evident from the questions themselves. We describe the conversion approach taken, appropriate evaluation metrics, and several strong models. Although high, the best scores (81% GENIE, 61.4% F1, 63.2% ROUGE-L) still leave considerable room for improvement. In addition, the dataset provides a natural setting for new research on explanation, as many questions require reasoning to construct answers. We hope the dataset spurs further advances in complex question-answering by the community. ARC-DA is available at https://allenai.org/data/arc-da
On Two Signature Variants Of Buchberger's Algorithm Over Principal Ideal Domains
Venue: arXiv cs.SC 2021
Year: 2021

Signature-based algorithms have brought large improvements in the performances of Gröbner bases algorithms for polynomial systems over fields. Furthermore, they yield additional data which can be used, for example, to compute the module of syzygies of an ideal or to compute coefficients in terms of the input generators. In this paper, we examine two variants of Buchberger's algorithm to compute Gröbner bases over principal ideal domains, with the addition of signatures. The first one is adapted from Kandri-Rody and Kapur's algorithm, whereas the second one uses the ideas developed in the algorithms by L. Pan (1989) and D. Lichtblau (2012). The differences in constructions between the algorithms entail differences in the operations which are compatible with the signatures, and in the criteria which can be used to discard elements. We prove that both algorithms are correct and discuss their relative performances in a prototype implementation in Magma.
Frontrunner Jones and the Raiders of the Dark Forest: An Empirical Study of Frontrunning on the Ethereum Blockchain
Venue: arXiv cs.CR 2021
Year: 2021

Ethereum prospered the inception of a plethora of smart contract applications, ranging from gambling games to decentralized finance. However, Ethereum is also considered a highly adversarial environment, where vulnerable smart contracts will eventually be exploited. Recently, Ethereum's pool of pending transaction has become a far more aggressive environment. In the hope of making some profit, attackers continuously monitor the transaction pool and try to frontrun their victims' transactions by either displacing or suppressing them, or strategically inserting their transactions. This paper aims to shed some light into what is known as a dark forest and uncover these predators' actions. We present a methodology to efficiently measure the three types of frontrunning: displacement, insertion, and suppression. We perform a large-scale analysis on more than 11M blocks and identify almost 200K attacks with an accumulated profit of 18.41M USD for the attackers, providing evidence that frontrunning is both, lucrative and a prevalent issue.
Child-directed Listening: How Caregiver Inference Enables Children's Early Verbal Communication
Venue: arXiv cs.CL 2021
Year: 2021

How do adults understand children's speech? Children's productions over the course of language development often bear little resemblance to typical adult pronunciations, yet caregivers nonetheless reliably recover meaning from them. Here, we employ a suite of Bayesian models of spoken word recognition to understand how adults overcome the noisiness of child language, showing that communicative success between children and adults relies heavily on adult inferential processes. By evaluating competing models on phonetically-annotated corpora, we show that adults' recovered meanings are best predicted by prior expectations fitted specifically to the child language environment, rather than to typical adult-adult language. After quantifying the contribution of this "child-directed listening" over developmental time, we discuss the consequences for theories of language acquisition, as well as the implications for commonly-used methods for assessing children's linguistic proficiency.
Overcoming Bias in Community Detection Evaluation
Venue: arXiv cs.SI 2021
Year: 2021

Community detection is a key task to further understand the function and the structure of complex networks. Therefore, a strategy used to assess this task must be able to avoid biased and incorrect results that might invalidate further analyses or applications that rely on such communities. Two widely used strategies to assess this task are generally known as structural and functional. The structural strategy basically consists in detecting and assessing such communities by using multiple methods and structural metrics. On the other hand, the functional strategy might be used when ground truth data are available to assess the detected communities. However, the evaluation of communities based on such strategies is usually done in experimental configurations that are largely susceptible to biases, a situation that is inherent to algorithms, metrics and network data used in this task. Furthermore, such strategies are not systematically combined in a way that allows for the identification and mitigation of bias in the algorithms, metrics or network data to converge into more consistent results. In this context, the main contribution of this article is an approach that supports a robust quality evaluation when detecting communities in real-world networks. In our approach, we measure the quality of a community by applying the structural and functional strategies, and the combination of both, to obtain different pieces of evidence. Then, we consider the divergences and the consensus among the pieces of evidence to identify and overcome possible sources of bias in community detection algorithms, evaluation metrics, and network data. Experiments conducted with several real and synthetic networks provided results that show the effectiveness of our approach to obtain more consistent conclusions about the quality of the detected communities.
Injective Objects and Fibered Codensity Liftings
Venue: arXiv cs.LO 2021
Year: 2021

Functor lifting along a fibration is used for several different purposes in computer science. In the theory of coalgebras, it is used to define coinductive predicates, such as simulation preorder and bisimilarity. Codensity lifting is a scheme to obtain a functor lifting along a fibration. It generalizes a few previous lifting schemes including the Kantorovich lifting. In this paper, we seek a property of functor lifting called fiberedness. Hinted by a known result for Kantorovich lifting, we identify a sufficient condition for a codensity lifting to be fibered. We see that this condition applies to many examples that have been studied. As an application, we derive some results on bisimilarity-like notions.
Directed percolation and numerical stability of simulations of digital memcomputing machines
Venue: arXiv cs.ET 2021
Year: 2021

Digital memcomputing machines (DMMs) are a novel, non-Turing class of machines designed to solve combinatorial optimization problems. They can be physically realized with continuous-time, non-quantum dynamical systems with memory (time non-locality), whose ordinary differential equations (ODEs) can be numerically integrated on modern computers. Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs, showing substantial advantages over state-of-the-art solvers. To investigate the reasons behind the robustness and effectiveness of this method, we employ three explicit integration schemes (forward Euler, trapezoid and Runge-Kutta 4th order) with a constant time step, to solve 3-SAT instances with planted solutions. We show that, (i) even if most of the trajectories in the phase space are destroyed by numerical noise, the solution can still be achieved; (ii) the forward Euler method, although having the largest numerical error, solves the instances in the least amount of function evaluations; and (iii) when increasing the integration time step, the system undergoes a "solvable-unsolvable transition" at a critical threshold, which needs to decay at most as a power law with the problem size, to control the numerical errors. To explain these results, we model the dynamical behavior of DMMs as directed percolation of the state trajectory in the phase space in the presence of noise. This viewpoint clarifies the reasons behind their numerical robustness and provides an analytical understanding of the unsolvable-solvable transition. These results land further support to the usefulness of DMMs in the solution of hard combinatorial optimization problems.
Jointly Improving Language Understanding and Generation with Quality-Weighted Weak Supervision of Automatic Labeling
Venue: arXiv cs.CL 2021
Year: 2021

Neural natural language generation (NLG) and understanding (NLU) models are data-hungry and require massive amounts of annotated data to be competitive. Recent frameworks address this bottleneck with generative models that synthesize weak labels at scale, where a small amount of training labels are expert-curated and the rest of the data is automatically annotated. We follow that approach, by automatically constructing a large-scale weakly-labeled data with a fine-tuned GPT-2, and employ a semi-supervised framework to jointly train the NLG and NLU models. The proposed framework adapts the parameter updates to the models according to the estimated label-quality. On both the E2E and Weather benchmarks, we show that this weakly supervised training paradigm is an effective approach under low resource scenarios and outperforming benchmark systems on both datasets when 100% of training data is used.
Policy options for digital infrastructure strategies: A simulation model for broadband universal service in Africa
Venue: arXiv cs.CY 2021
Year: 2021

Internet access is essential for economic development and helping to deliver the Sustainable Development Goals, especially as even basic broadband can revolutionize available economic opportunities. Yet, more than one billion people still live without internet access. Governments must make strategic choices to connect these citizens, but currently have few independent, transparent and scientifically reproducible assessments to rely on. This paper develops open-source software to test broadband universal service strategies which meet the 10 Mbps target being considered by the UN Broadband Commission. The private and government costs of different infrastructure decisions are quantified in six East and West African countries (Côte D`Ivoire, Mali, Senegal, Kenya, Tanzania and Uganda). The results provide strong evidence that `leapfrogging` straight to 4G in unconnected areas is the least-cost option for providing broadband universal service, with savings between 13-51% over 3G. The results also demonstrate how the extraction of spectrum and tax revenues in unviable markets provide no net benefit, as for every $1 taken in revenue, a $1 infrastructure subsidy is required from government to achieve broadband universal service. Importantly, the use of a Shared Rural Network in unviable locations provides impressive cost savings (up to 78%), while retaining the benefits of dynamic infrastructure competition in viable urban and suburban areas. This paper provides evidence to design national and international policies aimed at broadband universal service.
Algorithms for Linearly Recurrent Sequences of Truncated Polynomials
Venue: arXiv cs.SC 2021
Year: 2021

Linear recurrent sequences are those whose elements are defined as linear combinations of preceding elements, and finding recurrence relations is a fundamental problem in computer algebra. In this paper, we focus on sequences whose elements are vectors over the ring $\mathbb{A} = \mathbb{K}[x]/(x^d)$ of truncated polynomials. Finding the ideal of their recurrence relations has applications such as the computation of minimal polynomials and determinants of sparse matrices over $\mathbb{A}$. We present three methods for finding this ideal: a Berlekamp-Massey-like approach due to Kurakin, one which computes the kernel of some block-Hankel matrix over $\mathbb{A}$ via a minimal approximant basis, and one based on bivariate Padé approximation. We propose complexity improvements for the first two methods, respectively by avoiding the computation of redundant relations and by exploiting the Hankel structure to compress the approximation problem. Then we confirm these improvements empirically through a C++ implementation, and we discuss the above-mentioned applications.
Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we study the problem of inferring time-varying Markov random fields (MRF), where the underlying graphical model is both sparse and changes sparsely over time. Most of the existing methods for the inference of time-varying MRFs rely on the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high computational time. Instead, we introduce a new class of constrained optimization problems for the inference of sparsely-changing MRFs. The proposed optimization problem is formulated based on the exact $\ell_0$ regularization, and can be solved in near-linear time and memory. Moreover, we show that the proposed estimator enjoys a provably small estimation error. As a special case, we derive sharp statistical guarantees for the inference of sparsely-changing Gaussian MRFs (GMRF) in the high-dimensional regime, showing that such problems can be learned with as few as one sample per time. Our proposed method is extremely efficient in practice: it can accurately estimate sparsely-changing graphical models with more than 500 million variables in less than one hour.
Does He Wink or Does He Nod? A Challenging Benchmark for Evaluating Word Understanding of Language Models
Venue: arXiv cs.CL 2021
Year: 2021

Recent progress in pretraining language models on large corpora has resulted in large performance gains on many NLP tasks. These large models acquire linguistic knowledge during pretraining, which helps to improve performance on downstream tasks via fine-tuning. To assess what kind of knowledge is acquired, language models are commonly probed by querying them with `fill in the blank' style cloze questions. Existing probing datasets mainly focus on knowledge about relations between words and entities. We introduce WDLMPro (Word Definition Language Model Probing) to evaluate word understanding directly using dictionary definitions of words. In our experiments, three popular pretrained language models struggle to match words and their definitions. This indicates that they understand many words poorly and that our new probing task is a difficult challenge that could help guide research on LMs in the future.
Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
Venue: arXiv cs.LG 2021
Year: 2021

Dynamic graphs are rife with higher-order interactions, such as co-authorship relationships and protein-protein interactions in biological networks, that naturally arise between more than two nodes at once. In spite of the ubiquitous presence of such higher-order interactions, limited attention has been paid to the higher-order counterpart of the popular pairwise link prediction problem. Existing higher-order structure prediction methods are mostly based on heuristic feature extraction procedures, which work well in practice but lack theoretical guarantees. Such heuristics are primarily focused on predicting links in a static snapshot of the graph. Moreover, these heuristic-based methods fail to effectively utilize and benefit from the knowledge of latent substructures already present within the higher-order structures. In this paper, we overcome these obstacles by capturing higher-order interactions succinctly as \textit{simplices}, model their neighborhood by face-vectors, and develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process (i.e., a sequence of graph snapshots). Our method substantially outperforms several baseline higher-order prediction methods. As a theoretical achievement, we prove the consistency and asymptotic normality in terms of the Wasserstein distance of our estimator using Stein's method.
Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
Venue: arXiv cs.DS 2021
Year: 2021

We analyze Oja's algorithm for streaming $k$-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $d \times d$ symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top $k$ eigenvectors of their expectation using a number of samples that scales polylogarithmically with $d$. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.
Linking Labs: Interconnecting Experimental Environments
Venue: arXiv cs.HC 2021
Year: 2021

We introduce the concept of LabLinking: a technology-based interconnection of experimental laboratories across institutions, disciplines, cultures, languages, and time zones - in other words experiments without borders. In particular, we introduce LabLinking levels (LLL), which define the degree of tightness of empirical interconnection between labs. We describe the technological infrastructure in terms of hard- and software required for the respective LLLs and present examples of linked laboratories along with insights about the challenges and benefits. In sum, we argue that linked labs provide a unique platform for a continuous exchange between scientists and experimenters, thereby enabling a time synchronous execution of experiments performed with and by decentralized user and researchers, improving outreach and ease of subject recruitment, allowing to establish new experimental designs and to incorporate a panoply of complementary biosensors, devices, hard- and software solutions.
HGAN: Hybrid Generative Adversarial Network
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we present a simple approach to train Generative Adversarial Networks (GANs) in order to avoid a \textit {mode collapse} issue. Implicit models such as GANs tend to generate better samples compared to explicit models that are trained on tractable data likelihood. However, GANs overlook the explicit data density characteristics which leads to undesirable quantitative evaluations and mode collapse. To bridge this gap, we propose a hybrid generative adversarial network (HGAN) for which we can enforce data density estimation via an autoregressive model and support both adversarial and likelihood framework in a joint training manner which diversify the estimated density in order to cover different modes. We propose to use an adversarial network to \textit {transfer knowledge} from an autoregressive model (teacher) to the generator (student) of a GAN model. A novel deep architecture within the GAN formulation is developed to adversarially distill the autoregressive model information in addition to simple GAN training approach. We conduct extensive experiments on real-world datasets (i.e., MNIST, CIFAR-10, STL-10) to demonstrate the effectiveness of the proposed HGAN under qualitative and quantitative evaluations. The experimental results show the superiority and competitiveness of our method compared to the baselines.
Lie complexity of words
Venue: arXiv cs.FL 2021
Year: 2021

Given a finite alphabet $Σ$ and a right-infinite word $\bf w$ over $Σ$, we define the Lie complexity function $L_{\bf w}:\mathbb{N}\to \mathbb{N}$, whose value at $n$ is the number of conjugacy classes (under cyclic shift) of length-$n$ factors $x$ of $\bf w$ with the property that every element of the conjugacy class appears in $\bf w$. We show that the Lie complexity function is uniformly bounded for words with linear factor complexity, and as a result we show that words of linear factor complexity have at most finitely many primitive factors $y$ with the property that $y^n$ is again a factor for every $n$. We then look at automatic sequences and show that the Lie complexity function of a $k$-automatic sequence is again $k$-automatic.
Asynchronous semi-anonymous dynamics over large-scale networks
Venue: arXiv cs.SI 2021
Year: 2021

We analyze a class of stochastic processes, referred to as asynchronous and semi-anonymous dynamics (ASD), over directed labeled random networks. These processes are a natural tool to describe general best-response and noisy best-response dynamics in network games where each agent, at random times governed by independent Poisson clocks, can choose among a finite set of actions. The payoff is determined by the relative popularity of different actions among neighbors, while being independent of the specific identities of neighbors. Using a mean-field approach, we prove that, under certain conditions on the network and initial node configuration, the evolution of ASD can be approximated, in the limit of large network sizes, by the solution of a system of non-linear ordinary differential equations. Our framework is very general and applies to a large class of graph ensembles for which the typical random graph locally behaves like a tree. In particular, we will focus on labeled configuration-model random graphs, a generalization of the traditional configuration model which allows different classes of nodes to be mixed together in the network, permitting us, for example, to incorporate a community structure in the system. Our analysis also applies to configuration-model graphs having a power-law degree distribution, an essential feature of many real systems. To demonstrate the power and flexibility of our framework, we consider several examples of dynamics belonging to our class of stochastic processes. Moreover, we illustrate by simulation the applicability of our analysis to realistic scenarios by running our example dynamics over a real social network graph.
AttributeNet: Attribute Enhanced Vehicle Re-Identification
Venue: arXiv cs.CV 2021
Year: 2021

Vehicle Re-Identification (V-ReID) is a critical task that associates the same vehicle across images from different camera viewpoints. Many works explore attribute clues to enhance V-ReID; however, there is usually a lack of effective interaction between the attribute-related modules and final V-ReID objective. In this work, we propose a new method to efficiently explore discriminative information from vehicle attributes (for instance, color and type). We introduce AttributeNet (ANet) that jointly extracts identity-relevant features and attribute features. We enable the interaction by distilling the ReID-helpful attribute feature and adding it into the general ReID feature to increase the discrimination power. Moreover, we propose a constraint, named Amelioration Constraint (AC), which encourages the feature after adding attribute features onto the general ReID feature to be more discriminative than the original general ReID feature. We validate the effectiveness of our framework on three challenging datasets. Experimental results show that our method achieves the state-of-the-art performance.