OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Decoding of Gabidulin Codes over Galois Rings
Venue: arXiv cs.IT 2021
Year: 2021

This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.
Disambiguatory Signals are Stronger in Word-initial Positions
Venue: arXiv cs.CL 2021
Year: 2021

Psycholinguistic studies of human word processing and lexical access provide ample evidence of the preferred nature of word-initial versus word-final segments, e.g., in terms of attention paid by listeners (greater) or the likelihood of reduction by speakers (lower). This has led to the conjecture -- as in Wedel et al. (2019b), but common elsewhere -- that languages have evolved to provide more information earlier in words than later. Information-theoretic methods to establish such tendencies in lexicons have suffered from several methodological shortcomings that leave open the question of whether this high word-initial informativeness is actually a property of the lexicon or simply an artefact of the incremental nature of recognition. In this paper, we point out the confounds in existing methods for comparing the informativeness of segments early in the word versus later in the word, and present several new measures that avoid these confounds. When controlling for these confounds, we still find evidence across hundreds of languages that indeed there is a cross-linguistic tendency to front-load information in words.
When Can Models Learn From Explanations? A Formal Framework for Understanding the Roles of Explanation Data
Venue: arXiv cs.CL 2021
Year: 2021

Many methods now exist for conditioning model outputs on task instructions, retrieved documents, and user-provided explanations and feedback. Rather than relying solely on examples of task inputs and outputs, these approaches use valuable additional data for improving model correctness and aligning learned models with human priors. Meanwhile, a growing body of evidence suggests that some language models can (1) store a large amount of knowledge in their parameters, and (2) perform inference over tasks in textual inputs at test time. These results raise the possibility that, for some tasks, humans cannot explain to a model any more about the task than it already knows or could infer on its own. In this paper, we study the circumstances under which explanations of individual data points can (or cannot) improve modeling performance. In order to carefully control important properties of the data and explanations, we introduce a synthetic dataset for experiments, and we also make use of three existing datasets with explanations: e-SNLI, TACRED, and SemEval. We first give a formal framework for the available modeling approaches, in which explanation data can be used as model inputs, as targets, or as a prior. After arguing that the most promising role for explanation data is as model inputs, we propose to use a retrieval-based method and show that it solves our synthetic task with accuracies upwards of 95%, while baselines without explanation data achieve below 65% accuracy. We then identify properties of datasets for which retrieval-based modeling fails. With the three existing datasets, we find no improvements from explanation retrieval. Drawing on findings from our synthetic task, we suggest that at least one of six preconditions for successful modeling fails to hold with these datasets. Our code is publicly available at https://github.com/peterbhase/ExplanationRoles
Harvest -- An Open Source Toolkit for Extracting Posts and Post Metadata from Web Forums
Venue: arXiv cs.IR 2021
Year: 2021

Automatic extraction of forum posts and metadata is a crucial but challenging task since forums do not expose their content in a standardized structure. Content extraction methods, therefore, often need customizations such as adaptations to page templates and improvements of their extraction code before they can be deployed to new forums. Most of the current solutions are also built for the more general case of content extraction from web pages and lack key features important for understanding forum content such as the identification of author metadata and information on the thread structure. This paper, therefore, presents a method that determines the XPath of forum posts, eliminating incorrect mergers and splits of the extracted posts that were common in systems from the previous generation. Based on the individual posts further metadata such as authors, forum URL and structure are extracted. We also introduce Harvest, a new open source toolkit that implements the presented methods and create a gold standard extracted from 52 different Web forums for evaluating our approach. A comprehensive evaluation reveals that Harvest clearly outperforms competing systems.
Nearest Neighbor-based Importance Weighting
Venue: arXiv cs.LG 2021
Year: 2021

Importance weighting is widely applicable in machine learning in general and in techniques dealing with data covariate shift problems in particular. A novel, direct approach to determine such importance weighting is presented. It relies on a nearest neighbor classification scheme and is relatively straightforward to implement. Comparative experiments on various classification tasks demonstrate the effectiveness of our so-called nearest neighbor weighting (NNeW) scheme. Considering its performance, our procedure can act as a simple and effective baseline method for importance weighting.
Operational Semantics with Hierarchical Abstract Syntax Graphs
Venue: arXiv cs.PL 2021
Year: 2021

This is a motivating tutorial introduction to a semantic analysis of programming languages using a graphical language as the representation of terms, and graph rewriting as a representation of reduction rules. We show how the graphical language automatically incorporates desirable features, such as alpha-equivalence and how it can describe pure computation, imperative store, and control features in a uniform framework. The graph semantics combines some of the best features of structural operational semantics and abstract machines, while offering powerful new methods for reasoning about contextual equivalence. All technical details are available in an extended technical report by Muroya and the author and in Muroya's doctoral dissertation.
Verifying Security Vulnerabilities in Large Software Systems using Multi-Core k-Induction
Venue: arXiv cs.CR 2021
Year: 2021

Computer-based systems have been used to solve several domain problems, such as industrial, military, education, and wearable. Those systems need high-quality software to guarantee security and safety. We advocate that Bounded Model Checking (BMC) techniques can detect security vulnerabilities in the early stages of development processes. However, this technique struggles to scale up and verify large software commonly found on computer-based systems. Here, we develop and evaluate a pragmatic approach to verify large software systems using a state-of-the-art bounded model checker. In particular, we pre-process the input source-code files and then guide the model checker to explore the code systematically. We also present a multi-core implementation of the k-induction proof algorithm to verify and falsify large software systems iteratively. Our experimental results using the Efficient SMT-based Model Checker (ESBMC) show that our approach can guide ESBMC to efficiently verify large software systems. We evaluate our approach using the PuTTY application to verify 136 files and 2803 functions in less than 86 minutes, and the SlimGuard allocator, where we have found real security vulnerabilities confirmed by the developers. We conclude that our approach can successfully guide a bounded model checker to verify large software systems systematically.
Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC
Venue: arXiv cs.LG 2021
Year: 2021

Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. However, a major limitation of HMC is its inability to be applied to discrete domains due to the lack of gradient signal. In this work, we introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions using a combination of neural transport methods like normalizing flows and variational dequantization, and the Metropolis-Hastings rule. Our method first learns a continuous embedding of the discrete space using a surjective map and subsequently learns a bijective transformation from the continuous space to an approximately Gaussian distributed latent variable. Sampling proceeds by simulating MCMC chains in the latent space and mapping these samples to the target discrete space via the learned transformations. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
SAFELearning: Enable Backdoor Detectability In Federated Learning With Secure Aggregation
Venue: arXiv cs.CR 2021
Year: 2021

For model privacy, local model parameters in federated learning shall be obfuscated before sent to the remote aggregator. This technique is referred to as \emph{secure aggregation}. However, secure aggregation makes model poisoning attacks such backdooring more convenient considering that existing anomaly detection methods mostly require access to plaintext local models. This paper proposes SAFELearning which supports backdoor detection for secure aggregation. We achieve this through two new primitives - \emph{oblivious random grouping (ORG)} and \emph{partial parameter disclosure (PPD)}. ORG partitions participants into one-time random subgroups with group configurations oblivious to participants; PPD allows secure partial disclosure of aggregated subgroup models for anomaly detection without leaking individual model privacy. SAFELearning can significantly reduce backdoor model accuracy without jeopardizing the main task accuracy under common backdoor strategies. Extensive experiments show SAFELearning is robust against malicious and faulty participants, whilst being more efficient than the state-of-art secure aggregation protocol in terms of both communication and computation costs.
A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
Venue: arXiv cs.LG 2021
Year: 2021

While over-parameterization is widely believed to be crucial for the success of optimization for the neural networks, most existing theories on over-parameterization do not fully explain the reason -- they either work in the Neural Tangent Kernel regime where neurons don't move much, or require an enormous number of neurons. In practice, when the data is generated using a teacher neural network, even mildly over-parameterized neural networks can achieve 0 loss and recover the directions of teacher neurons. In this paper we develop a local convergence theory for mildly over-parameterized two-layer neural net. We show that as long as the loss is already lower than a threshold (polynomial in relevant parameters), all student neurons in an over-parameterized two-layer neural network will converge to one of teacher neurons, and the loss will go to 0. Our result holds for any number of student neurons as long as it is at least as large as the number of teacher neurons, and our convergence rate is independent of the number of student neurons. A key component of our analysis is the new characterization of local optimization landscape -- we show the gradient satisfies a special case of Lojasiewicz property which is different from local strong convexity or PL conditions used in previous work.
Online Sketch-based Query Optimization
Venue: arXiv cs.DB 2021
Year: 2021

Cost-based query optimization remains a critical task in relational databases even after decades of research and industrial development. Query optimizers rely on a large range of statistical synopses -- including attribute-level histograms and table-level samples -- for accurate cardinality estimation. As the complexity of selection predicates and the number of join predicates increase, two problems arise. First, statistics cannot be incrementally composed to effectively estimate the cost of the sub-plans generated in plan enumeration. Second, small errors are propagated exponentially through join operators, which can lead to severely sub-optimal plans. In this paper, we introduce COMPASS, a novel query optimization paradigm for in-memory databases based on a single type of statistics -- Fast-AGMS sketches. In COMPASS, query optimization and execution are intertwined. Selection predicates and sketch updates are pushed-down and evaluated online during query optimization. This allows Fast-AGMS sketches to be computed only over the relevant tuples -- which enhances cardinality estimation accuracy. Plan enumeration is performed over the query join graph by incrementally composing attribute-level sketches -- not by building a separate sketch for every sub-plan. We prototype COMPASS in MapD -- an open-source parallel database -- and perform extensive experiments over the complete JOB benchmark. The results prove that COMPASS generates better execution plans -- both in terms of cardinality and runtime -- compared to four other database systems. Overall, COMPASS achieves a speedup ranging from 1.35X to 11.28X in cumulative query execution time over the considered competitors.
Persistent Rule-based Interactive Reinforcement Learning
Venue: arXiv cs.AI 2021
Year: 2021

Interactive reinforcement learning has allowed speeding up the learning process in autonomous agents by including a human trainer providing extra information to the agent in real-time. Current interactive reinforcement learning research has been limited to real-time interactions that offer relevant user advice to the current state only. Additionally, the information provided by each interaction is not retained and instead discarded by the agent after a single-use. In this work, we propose a persistent rule-based interactive reinforcement learning approach, i.e., a method for retaining and reusing provided knowledge, allowing trainers to give general advice relevant to more than just the current state. Our experimental results show persistent advice substantially improves the performance of the agent while reducing the number of interactions required for the trainer. Moreover, rule-based advice shows similar performance impact as state-based advice, but with a substantially reduced interaction count.
Introducing lop-kernels: a framework for kernelization lower bounds
Venue: arXiv cs.DS 2021
Year: 2021

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph $G$ and a positive integer $k$, and the objective is to decide whether $G$ contains a minimal vertex cover of size at least $k$. Motivated by the kernelization of MMVC with parameter $k$, our main contribution is to introduce a simple general framework to obtain kernelization lower bounds for a certain type of kernels for optimization problems, which we call lop-kernels. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. We present further applications for Tree Deletion Set and for Maximum Independent Set on $K_t$-free graphs. Back to the MMVC problem, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on $H$-free graphs for several graphs $H$, such as the bull, the paw, or the complete graphs, by making use of the Erdös-Hajnal property. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$.
Image Restoration by Deep Projected GSURE
Venue: arXiv cs.CV 2021
Year: 2021

Ill-posed inverse problems appear in many image processing applications, such as deblurring and super-resolution. In recent years, solutions that are based on deep Convolutional Neural Networks (CNNs) have shown great promise. Yet, most of these techniques, which train CNNs using external data, are restricted to the observation models that have been used in the training phase. A recent alternative that does not have this drawback relies on learning the target image using internal learning. One such prominent example is the Deep Image Prior (DIP) technique that trains a network directly on the input image with a least-squares loss. In this paper, we propose a new image restoration framework that is based on minimizing a loss function that includes a "projected-version" of the Generalized SteinUnbiased Risk Estimator (GSURE) and parameterization of the latent image by a CNN. We demonstrate two ways to use our framework. In the first one, where no explicit prior is used, we show that the proposed approach outperforms other internal learning methods, such as DIP. In the second one, we show that our GSURE-based loss leads to improved performance when used within a plug-and-play priors scheme.
Understanding the Capabilities, Limitations, and Societal Impact of Large Language Models
Venue: arXiv cs.CL 2021
Year: 2021

On October 14th, 2020, researchers from OpenAI, the Stanford Institute for Human-Centered Artificial Intelligence, and other universities convened to discuss open research questions surrounding GPT-3, the largest publicly-disclosed dense language model at the time. The meeting took place under Chatham House Rules. Discussants came from a variety of research backgrounds including computer science, linguistics, philosophy, political science, communications, cyber policy, and more. Broadly, the discussion centered around two main questions: 1) What are the technical capabilities and limitations of large language models? 2) What are the societal effects of widespread use of large language models? Here, we provide a detailed summary of the discussion organized by the two themes above.
Improved Communication Efficiency for Distributed Mean Estimation with Side Information
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we consider the distributed mean estimation problem where the server has access to some side information, e.g., its local computed mean estimation or the received information sent by the distributed clients at the previous iterations. We propose a practical and efficient estimator based on an r-bit Wynzer-Ziv estimator proposed by Mayekar et al., which requires no probabilistic assumption on the data. Unlike Mayekar's work which only utilizes side information at the server, our scheme jointly exploits the correlation between clients' data and server' s side information, and also between data of different clients. We derive an upper bound of the estimation error of the proposed estimator. Based on this upper bound, we provide two algorithms on how to choose input parameters for the estimator. Finally, parameter regions in which our estimator is better than the previous one are characterized.
Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach
Venue: arXiv cs.IT 2021
Year: 2021

Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gröbner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.
Optimizing Blockchain Based Smart Grid Auctions: A Green Revolution
Venue: arXiv cs.CR 2021
Year: 2021

Traditional smart grid energy auctions cannot directly be integrated in blockchain due to its decentralized nature. Therefore, research works are being carried out to propose efficient decentralized auctions for energy trading. Since, blockchain is a novel paradigm which ensures trust, but it also comes up with a curse of high computation and communication complexity which eventually causes resource scarcity. Therefore, there is a need to develop and encourage development of greener and computational-friendly auctions to carry out decentralized energy trading. In this paper, we first provide a thorough motivation of decentralized auctions over traditional auctions. Afterwards, we provide in-depth design requirements that can be taken into consideration while developing such auctions. After that, we analyze technical works that have developed blockchain based energy auctions from green perspective. Finally, we summarize the article by providing challenges and possible future research directions of blockchain based energy auction from green viewpoint.
Lookup subnet based Spatial Graph Convolutional neural Network
Venue: arXiv cs.LG 2021
Year: 2021

Convolutional Neural Networks(CNNs) has achieved remarkable performance breakthrough in Euclidean structure data. Recently, aggregation-transformation based Graph Neural networks(GNNs) gradually produce a powerful performance on non-Euclidean data. In this paper, we propose a cross-correlation based graph convolution method allowing to naturally generalize CNNs to non-Euclidean domains and inherit the excellent natures of CNNs, such as local filters, parameter sharing, flexible receptive field, etc. Meanwhile, it leverages dynamically generated convolution kernel and cross-correlation operators to address the shortcomings of prior methods based on aggregation-transformation or their approximations. Our method has achieved or matched popular state-of-the-art results across three established graph benchmarks: the Cora, Citeseer, and Pubmed citation network datasets.
Improving Reinforcement Learning with Human Assistance: An Argument for Human Subject Studies with HIPPO Gym
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning (RL) is a popular machine learning paradigm for game playing, robotics control, and other sequential decision tasks. However, RL agents often have long learning times with high data requirements because they begin by acting randomly. In order to better learn in complex tasks, this article argues that an external teacher can often significantly help the RL agent learn. OpenAI Gym is a common framework for RL research, including a large number of standard environments and agents, making RL research significantly more accessible. This article introduces our new open-source RL framework, the Human Input Parsing Platform for Openai Gym (HIPPO Gym), and the design decisions that went into its creation. The goal of this platform is to facilitate human-RL research, again lowering the bar so that more researchers can quickly investigate different ways that human teachers could assist RL agents, including learning from demonstrations, learning from feedback, or curriculum learning.