OpenRaiser/Intern-Atlas huggingface dataset:
Neural Plasticity Networks
Venue: arXiv cs.NE 2021
Year: 2021

Neural plasticity is an important functionality of human brain, in which number of neurons and synapses can shrink or expand in response to stimuli throughout the span of life. We model this dynamic learning process as an $L_0$-norm regularized binary optimization problem, in which each unit of a neural network (e.g., weight, neuron or channel, etc.) is attached with a stochastic binary gate, whose parameters determine the level of activity of a unit in the network. At the beginning, only a small portion of binary gates (therefore the corresponding neurons) are activated, while the remaining neurons are in a hibernation mode. As the learning proceeds, some neurons might be activated or deactivated if doing so can be justified by the cost-benefit tradeoff measured by the $L_0$-norm regularized objective. As the training gets mature, the probability of transition between activation and deactivation will diminish until a final hardening stage. We demonstrate that all of these learning dynamics can be modulated by a single parameter $k$ seamlessly. Our neural plasticity network (NPN) can prune or expand a network depending on the initial capacity of network provided by the user; it also unifies dropout (when $k=0$), traditional training of DNNs (when $k=\infty$) and interpolates between these two. To the best of our knowledge, this is the first learning framework that unifies network sparsification and network expansion in an end-to-end training pipeline. Extensive experiments on synthetic dataset and multiple image classification benchmarks demonstrate the superior performance of NPN. We show that both network sparsification and network expansion can yield compact models of similar architectures, while retaining competitive accuracies of the original networks.
Covering convex bodies and the Closest Vector Problem
Venue: arXiv cs.DS 2021
Year: 2021

We present algorithms for the $(1+ε)$-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms has running time of $2^{O(n)} (1/ε)^n$. We improve this substantially in the following two cases. For $\ell_p$-norms with $p>2$ (resp. $p \in [1,2]$) fixed, we present an algorithm with a running time of $2^{O(n)} (1/ε)^{n/2}$ (resp. $2^{O(n)} (1/ε)^{n/p}$). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by two around their centroids, each one is contained in the $(1+ε)$-scaled homothet of the norm ball? We provide upper bounds for this problem by exploiting the \emph{modulus of smoothness} of the $\ell_p$-balls. Applying a covering scheme, we can boost any constant approximation algorithm for CVP to a $(1+ε)$-approximation algorithm with the improved run time, either using a straightforward sampling routine or using the deterministic algorithm of Dadush for the construction of an epsilon net. The space requirement only depends on the constant approximation CVP solver used. Furthermore, we generalise the result of Eisenbrand et al. for the $\ell_\infty$-norm. For centrally symmetric polytopes (resp. zonotopes) with $O(n)$ facets (resp. generated by $O(n)$ line segments), we provide a deterministic $O(\log_2(1/ε))^{O(n)}$ time algorithm. Finally, we establish a connection between the \emph{modulus of smoothness} and \emph{lattice sparsification}. Using the enumeration and sparsification tools developped by Dadush, Kun, Peikert and Vempala, this leads to a simple alternative to the boosting procedure for CVP under $\ell_p$-norms. This connection might be of independent interest.
Controllable Dual Skew Divergence Loss for Neural Machine Translation
Venue: arXiv cs.CL 2021
Year: 2021

In sequence prediction tasks like neural machine translation, training with cross-entropy loss often leads to models that overgeneralize and plunge into local optima. In this paper, we propose an extended loss function called \emph{dual skew divergence} (DSD) that integrates two symmetric terms on KL divergences with a balanced weight. We empirically discovered that such a balanced weight plays a crucial role in applying the proposed DSD loss into deep models. Thus we eventually develop a controllable DSD loss for general-purpose scenarios. Our experiments indicate that switching to the DSD loss after the convergence of ML training helps models escape local optima and stimulates stable performance improvements. Our evaluations on the WMT 2014 English-German and English-French translation tasks demonstrate that the proposed loss as a general and convenient mean for NMT training indeed brings performance improvement in comparison to strong baselines.
Quadratic Surface Support Vector Machine with L1 Norm Regularization
Venue: arXiv cs.LG 2021
Year: 2021

We propose $\ell_1$ norm regularized quadratic surface support vector machine models for binary classification in supervised learning. We establish their desired theoretical properties, including the existence and uniqueness of the optimal solution, reduction to the standard SVMs over (almost) linearly separable data sets, and detection of true sparsity pattern over (almost) quadratically separable data sets if the penalty parameter of $\ell_1$ norm is large enough. We also demonstrate their promising practical efficiency by conducting various numerical experiments on both synthetic and publicly available benchmark data sets.
Situational Fusion of Visual Representation for Visual Navigation
Venue: arXiv cs.CV 2021
Year: 2021

A complex visual navigation task puts an agent in different situations which call for a diverse range of visual perception abilities. For example, to "go to the nearest chair", the agent might need to identify a chair in a living room using semantics, follow along a hallway using vanishing point cues, and avoid obstacles using depth. Therefore, utilizing the appropriate visual perception abilities based on a situational understanding of the visual environment can empower these navigation models in unseen visual environments. We propose to train an agent to fuse a large set of visual representations that correspond to diverse visual perception abilities. To fully utilize each representation, we develop an action-level representation fusion scheme, which predicts an action candidate from each representation and adaptively consolidate these action candidates into the final action. Furthermore, we employ a data-driven inter-task affinity regularization to reduce redundancies and improve generalization. Our approach leads to a significantly improved performance in novel environments over ImageNet-pretrained baseline and other fusion methods.
Feedback linearly extended discrete functions
Venue: arXiv cs.CR 2021
Year: 2021

We study a new flexible method to extend linearly the graph of a non-linear, and usually not bijective, function so that the resulting extension is a bijection. Our motivation comes from cryptography. Examples from symmetric cryptography are given as how the extension was used implicitly in the construction of some well-known block ciphers. The method heavily relies on ideas brought from linear coding theory and secret sharing. We are interested in the behaviour of the composition of many extensions, and especially the space of parameters that defines a family of equations based on finite differences or linear forms. For any linear extension, we characterize entirely the space of parameters for which such equations are solvable in terms of the space of parameters that render those equations for the corresponding non-linear extended functions solvable. Conditions are derived to assess the solvability of those kind of equations in terms of the number of compositions or iterations. We prove a relation between the number of compositions and the dimensions of vector spaces that appear in our results. The proofs of those properties rely mostly on tools from linear algebra.
Open Named Entity Modeling from Embedding Distribution
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we report our discovery on named entity distribution in a general word embedding space, which helps an open definition on multilingual named entity definition rather than previous closed and constraint definition on named entities through a named entity dictionary, which is usually derived from human labor and replies on schedule update. Our initial visualization of monolingual word embeddings indicates named entities tend to gather together despite of named entity types and language difference, which enable us to model all named entities using a specific geometric structure inside embedding space, namely, the named entity hypersphere. For monolingual cases, the proposed named entity model gives an open description of diverse named entity types and different languages. For cross-lingual cases, mapping the proposed named entity model provides a novel way to build a named entity dataset for resource-poor languages. At last, the proposed named entity model may be shown as a handy clue to enhance state-of-the-art named entity recognition systems generally.
Topics to Avoid: Demoting Latent Confounds in Text Classification
Venue: arXiv cs.LG 2021
Year: 2021

Despite impressive performance on many text classification tasks, deep neural networks tend to learn frequent superficial patterns that are specific to the training data and do not always generalize well. In this work, we observe this limitation with respect to the task of native language identification. We find that standard text classifiers which perform well on the test set end up learning topical features which are confounds of the prediction task (e.g., if the input text mentions Sweden, the classifier predicts that the author's native language is Swedish). We propose a method that represents the latent topical confounds and a model which "unlearns" confounding features by predicting both the label of the input text and the confound; but we train the two predictors adversarially in an alternating fashion to learn a text representation that predicts the correct label but is less prone to using information about the confound. We show that this model generalizes better and learns features that are indicative of the writing style rather than the content.
DRAT and Propagation Redundancy Proofs Without New Variables
Venue: arXiv cs.LO 2021
Year: 2021

We study the complexity of a range of propositional proof systems which allow inference rules of the form: from a set of clauses $Γ$ derive the set of clauses $Γ\cup \{ C \}$ where, due to some syntactic condition, $Γ\cup \{ C \}$ is satisfiable if $Γ$ is, but where $Γ$ does not necessarily imply $C$. These inference rules include BC, RAT, SPR and PR (respectively short for blocked clauses, resolution asymmetric tautologies, subset propagation redundancy and propagation redundancy), which arose from work in satisfiability (SAT) solving. We introduce a new, more general rule SR (substitution redundancy). If the new clause $C$ is allowed to include new variables then the systems based on these rules are all equivalent to extended resolution. We focus on restricted systems that do not allow new variables. The systems with deletion, where we can delete a clause from our set at any time, are denoted DBC${}^-$, DRAT${}^-$, DSPR${}^-$, DPR${}^-$ and DSR${}^-$. The systems without deletion are BC${}^-$, RAT${}^-$, SPR${}^-$, PR${}^-$ and SR${}^-$. With deletion, we show that DRAT${}^-$, DSPR${}^-$ and DPR${}^-$ are equivalent. By earlier work of Kiesl, Rebola-Pardo and Heule, they are also equivalent to DBC${}^-$. Without deletion, we show that SPR${}^-$ can simulate PR${}^-$ provided only short clauses are inferred by SPR inferences. We also show that many of the well-known "hard" principles have small SPR${}^-$ refutations. These include the pigeonhole principle, bit pigeonhole principle, parity principle, Tseitin tautologies and clique-coloring tautologies. SPR${}^-$ can also handle or-fication and xor-ification, and lifting with an index gadget. Our final result is an exponential size lower bound for RAT${}^-$ refutations, giving exponential separations between RAT${}^-$ and both DRAT${}^-$ and SPR${}^-$.
From 'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Venue: arXiv cs.CL 2021
Year: 2021

AI has achieved remarkable mastery over games such as Chess, Go, and Poker, and even Jeopardy, but the rich variety of standardized exams has remained a landmark challenge. Even in 2016, the best AI system achieved merely 59.3% on an 8th Grade science exam challenge. This paper reports unprecedented success on the Grade 8 New York Regents Science Exam, where for the first time a system scores more than 90% on the exam's non-diagram, multiple choice (NDMC) questions. In addition, our Aristo system, building upon the success of recent language models, exceeded 83% on the corresponding Grade 12 Science Exam NDMC questions. The results, on unseen test questions, are robust across different test years and different variations of this kind of test. They demonstrate that modern NLP methods can result in mastery on this task. While not a full solution to general question-answering (the questions are multiple choice, and the domain is restricted to 8th Grade science), it represents a significant milestone for the field.
Learning Action-Transferable Policy with Action Embedding
Venue: arXiv cs.LG 2021
Year: 2021

Transfer learning (TL) is a promising way to improve the sample efficiency of reinforcement learning. However, how to efficiently transfer knowledge across tasks with different state-action spaces is investigated at an early stage. Most previous studies only addressed the inconsistency across different state spaces by learning a common feature space, without considering that similar actions in different action spaces of related tasks share similar semantics. In this paper, we propose a method to learning action embeddings by leveraging this idea, and a framework that learns both state embeddings and action embeddings to transfer policy across tasks with different state and action spaces. Our experimental results on various tasks show that the proposed method can not only learn informative action embeddings but accelerate policy learning.
NEAR: Neighborhood Edge AggregatoR for Graph Classification
Venue: arXiv cs.LG 2021
Year: 2021

Learning graph-structured data with graph neural networks (GNNs) has been recently emerging as an important field because of its wide applicability in bioinformatics, chemoinformatics, social network analysis and data mining. Recent GNN algorithms are based on neural message passing, which enables GNNs to integrate local structures and node features recursively. However, past GNN algorithms based on 1-hop neighborhood neural message passing are exposed to a risk of loss of information on local structures and relationships. In this paper, we propose Neighborhood Edge AggregatoR (NEAR), a framework that aggregates relations between the nodes in the neighborhood via edges. NEAR, which can be orthogonally combined with Graph Isomorphism Network (GIN), gives integrated information that describes which nodes in the neighborhood are connected. Therefore, NEAR can reflect additional information of a local structure of each node beyond the nodes themselves in 1-hop neighborhood. Experimental results on multiple graph classification tasks show that our algorithm makes a good improvement over other existing 1-hop based GNN-based algorithms.
Regression Under Human Assistance
Venue: arXiv cs.LG 2021
Year: 2021

Decisions are increasingly taken by both humans and machine learning models. However, machine learning models are currently trained for full automation -- they are not aware that some of the decisions may still be taken by humans. In this paper, we take a first step towards the development of machine learning models that are optimized to operate under different automation levels. More specifically, we first introduce the problem of ridge regression under human assistance and show that it is NP-hard. Then, we derive an alternative representation of the corresponding objective function as a difference of nondecreasing submodular functions. Building on this representation, we further show that the objective is nondecreasing and satisfies $α$-submodularity, a recently introduced notion of approximate submodularity. These properties allow a simple and efficient greedy algorithm to enjoy approximation guarantees at solving the problem. Experiments on synthetic and real-world data from two important applications -- medical diagnosis and content moderation-demonstrate that our algorithm outsources to humans those samples in which the prediction error of the ridge regression model would have been the highest if it had to make a prediction, it outperforms several competitive baselines, and its performance is robust with respect to several design choices and hyperparameters used in the experiments.
Symmetric Regularization based BERT for Pair-wise Semantic Reasoning
Venue: arXiv cs.CL 2021
Year: 2021

The ability of semantic reasoning over the sentence pair is essential for many natural language understanding tasks, e.g., natural language inference and machine reading comprehension. A recent significant improvement in these tasks comes from BERT. As reported, the next sentence prediction (NSP) in BERT, which learns the contextual relationship between two sentences, is of great significance for downstream problems with sentence-pair input. Despite the effectiveness of NSP, we suggest that NSP still lacks the essential signal to distinguish between entailment and shallow correlation. To remedy this, we propose to augment the NSP task to a 3-class categorization task, which includes a category for previous sentence prediction (PSP). The involvement of PSP encourages the model to focus on the informative semantics to determine the sentence order, thereby improves the ability of semantic understanding. This simple modification yields remarkable improvement against vanilla BERT. To further incorporate the document-level information, the scope of NSP and PSP is expanded into a broader range, i.e., NSP and PSP also include close but nonsuccessive sentences, the noise of which is mitigated by the label-smoothing technique. Both qualitative and quantitative experimental results demonstrate the effectiveness of the proposed method. Our method consistently improves the performance on the NLI and MRC benchmarks, including the challenging HANS dataset \cite{hans}, suggesting that the document-level task is still promising for the pre-training.
Fine Grained Dataflow Tracking with Proximal Gradients
Venue: arXiv cs.CR 2021
Year: 2021

Dataflow tracking with Dynamic Taint Analysis (DTA) is an important method in systems security with many applications, including exploit analysis, guided fuzzing, and side-channel information leak detection. However, DTA is fundamentally limited by the Boolean nature of taint labels, which provide no information about the significance of detected dataflows and lead to false positives/negatives on complex real world programs. We introduce proximal gradient analysis (PGA), a novel, theoretically grounded approach that can track more accurate and fine-grained dataflow information. PGA uses proximal gradients, a generalization of gradients for non-differentiable functions, to precisely compose gradients over non-differentiable operations in programs. Composing gradients over programs eliminates many of the dataflow propagation errors that occur in DTA and provides richer information about how each measured dataflow effects a program. We compare our prototype PGA implementation to three state of the art DTA implementations on 7 real-world programs. Our results show that PGA can improve the F1 accuracy of data flow tracking by up to 33% over taint tracking (20% on average) without introducing any significant overhead (<5% on average). We further demonstrate the effectiveness of PGA by discovering 22 bugs (20 confirmed by developers) and 2 side-channel leaks, and identifying exploitable dataflows in 19 existing CVEs in the tested programs.
On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$
Venue: arXiv cs.DM 2021
Year: 2021

Graph homomorphism has been an important research topic since its introduction [17]. Stated in the language of binary relational structures in that paper [17], Lovász proved a fundamental theorem that, for a graph $H$ given by its $0$-$1$ valued adjacency matrix, the graph homomorphism function $G \mapsto \hom(G, H)$ determines the isomorphism type of $H$. In the past 50 years various extensions have been proved by many researchers [18, 12, 1, 23, 21]. These extend the basic $0$-$1$ case to admit vertex and edge weights; but these extensions all have some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. A noteworthy aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective in the following sense: it provides an algorithm that for any $H$ either outputs a P-time algorithm solving $\hom(\cdot, H)$ or a P-time reduction from a canonical #P-hard problem to $\hom(\cdot, H)$.
Imitation Learning from Pixel-Level Demonstrations by HashReward
Venue: arXiv cs.LG 2021
Year: 2021

One of the key issues for imitation learning lies in making policy learned from limited samples to generalize well in the whole state-action space. This problem is much more severe in high-dimensional state environments, such as game playing with raw pixel inputs. Under this situation, even state-of-the-art adversary-based imitation learning algorithms fail. Through empirical studies, we find that the main cause lies in the failure of training a powerful discriminator to generate meaningful rewards in high-dimensional environments. Although it seems that dimensionality reduction can help, a straightforward application of off-the-shelf methods cannot achieve good performance. In this work, we show in theory that the balance between dimensionality reduction and discriminative training is essential for effective learning. To achieve this target, we propose HashReward, which utilizes the idea of supervised hashing to realize such an ideal balance. Experimental results show that HashReward could outperform state-of-the-art methods for a large gap under the challenging high-dimensional environments.
Testing Deep Learning Models for Image Analysis Using Object-Relevant Metamorphic Relations
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning models are widely used for image analysis. While they offer high performance in terms of accuracy, people are concerned about if these models inappropriately make inferences using irrelevant features that are not encoded from the target object in a given image. To address the concern, we propose a metamorphic testing approach that assesses if a given inference is made based on irrelevant features. Specifically, we propose two novel metamorphic relations to detect such inappropriate inferences. We applied our approach to 10 image classification models and 10 object detection models, with three large datasets, i.e., ImageNet, COCO, and Pascal VOC. Over 5.3% of the top-5 correct predictions made by the image classification models are subject to inappropriate inferences using irrelevant features. The corresponding rate for the object detection models is over 8.5%. Based on the findings, we further designed a new image generation strategy that can effectively attack existing models. Comparing with a baseline approach, our strategy can double the success rate of attacks.