OpenRaiser/Intern-Atlas huggingface dataset:
BGADAM: Boosting based Genetic-Evolutionary ADAM for Neural Network Optimization
Venue: arXiv cs.NE 2021
Year: 2021

For various optimization methods, gradient descent-based algorithms can achieve outstanding performance and have been widely used in various tasks. Among those commonly used algorithms, ADAM owns many advantages such as fast convergence with both the momentum term and the adaptive learning rate. However, since the loss functions of most deep neural networks are non-convex, ADAM also shares the drawback of getting stuck in local optima easily. To resolve such a problem, the idea of combining genetic algorithm with base learners is introduced to rediscover the best solutions. Nonetheless, from our analysis, the idea of combining genetic algorithm with a batch of base learners still has its shortcomings. The effectiveness of genetic algorithm can hardly be guaranteed if the unit models converge to close or the same solutions. To resolve this problem and further maximize the advantages of genetic algorithm with base learners, we propose to implement the boosting strategy for input model training, which can subsequently improve the effectiveness of genetic algorithm. In this paper, we introduce a novel optimization algorithm, namely Boosting based Genetic ADAM (BGADAM). With both theoretic analysis and empirical experiments, we will show that adding the boosting strategy into the BGADAM model can help models jump out the local optima and converge to better solutions.
A Novel Method to Generate Key-Dependent S-Boxes with Identical Algebraic Properties
Venue: arXiv cs.CR 2021
Year: 2021

The s-box plays the vital role of creating confusion between the ciphertext and secret key in any cryptosystem, and is the only nonlinear component in many block ciphers. Dynamic s-boxes, as compared to static, improve entropy of the system, hence leading to better resistance against linear and differential attacks. It was shown in [2] that while incorporating dynamic s-boxes in cryptosystems is sufficiently secure, they do not keep non-linearity invariant. This work provides an algorithmic scheme to generate key-dependent dynamic $n\times n$ clone s-boxes having the same algebraic properties namely bijection, nonlinearity, the strict avalanche criterion (SAC), the output bits independence criterion (BIC) as of the initial seed s-box. The method is based on group action of symmetric group $S_n$ and a subgroup $S_{2^n}$ respectively on columns and rows of Boolean functions ($GF(2^n)\to GF(2)$) of s-box. Invariance of the bijection, nonlinearity, SAC, and BIC for the generated clone copies is proved. As illustration, examples are provided for $n=8$ and $n=4$ along with comparison of the algebraic properties of the clone and initial seed s-box. The proposed method is an extension of [3,4,5,6] which involved group action of $S_8$ only on columns of Boolean functions ($GF(2^8)\to GF(2)$ ) of s-box. For $n=4$, we have used an initial $4\times 4$ s-box constructed by Carlisle Adams and Stafford Tavares [7] to generated $(4!)^2$ clone copies. For $n=8$, it can be seen [3,4,5,6] that the number of clone copies that can be constructed by permuting the columns is $8!$. For each column permutation, the proposed method enables to generate $8!$ clone copies by permuting the rows.
API Beauty is in the eye of the Clients: 2.2 Million Maven Dependencies reveal the Spectrum of Client-API Usages
Venue: arXiv cs.SE 2021
Year: 2021

Hyrum's law states a common observation in the software industry: "With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody". Meanwhile, recent research results seem to contradict this observation when they state that "for most APIs, there is a small number of features that are actually used". We investigate this seeming paradox between the observations in industry and the research literature, with a large scale empirical study of client API relationships in one single ecosystem: Maven Central. We study the 94 most popular libraries in Maven Central, as well as the 829,410 client artifacts that declare a dependency to these libraries and that are available in Maven Central, summing up to 2.2M dependencies. Our analysis indicates the existence of a wide spectrum of API usages, with enough clients, most API types end up being used at least once. Our second key observation is that, for all libraries, there is a small set of API types that are used by the vast majority of its clients. The practical consequences of this study are two-fold: (i) it is possible for API maintainers to find an essential part of their API on which they can focus their efforts; (ii) API developers should limit the public API elements to the set of features for which they are ready to have users.
Semantic Hypergraphs
Venue: arXiv cs.IR 2021
Year: 2021

Approaches to Natural language processing (NLP) may be classified along a double dichotomy open/opaque - strict/adaptive. The former axis relates to the possibility of inspecting the underlying processing rules, the latter to the use of fixed or adaptive rules. We argue that many techniques fall into either the open-strict or opaque-adaptive categories. Our contribution takes steps in the open-adaptive direction, which we suggest is likely to provide key instruments for interdisciplinary research. The central idea of our approach is the Semantic Hypergraph (SH), a novel knowledge representation model that is intrinsically recursive and accommodates the natural hierarchical richness of natural language. The SH model is hybrid in two senses. First, it attempts to combine the strengths of ML and symbolic approaches. Second, it is a formal language representation that reduces but tolerates ambiguity and structural variability. We will see that SH enables simple yet powerful methods of pattern detection, and features a good compromise for intelligibility both for humans and machines. It also provides a semantically deep starting point (in terms of explicit meaning) for further algorithms to operate and collaborate on. We show how modern NLP ML-based building blocks can be used in combination with a random forest classifier and a simple search tree to parse NL to SH, and that this parser can achieve high precision in a diversity of text categories. We define a pattern language representable in SH itself, and a process to discover knowledge inference rules. We then illustrate the efficiency of the SH framework in a variety of tasks, including conjunction decomposition, open information extraction, concept taxonomy inference and co-reference resolution, and an applied example of claim and conflict analysis in a news corpus.
A Deep Neural Information Fusion Architecture for Textual Network Embeddings
Venue: arXiv cs.SI 2021
Year: 2021

Textual network embeddings aim to learn a low-dimensional representation for every node in the network so that both the structural and textual information from the networks can be well preserved in the representations. Traditionally, the structural and textual embeddings were learned by models that rarely take the mutual influences between them into account. In this paper, a deep neural architecture is proposed to effectively fuse the two kinds of informations into one representation. The novelties of the proposed architecture are manifested in the aspects of a newly defined objective function, the complementary information fusion method for structural and textual features, and the mutual gate mechanism for textual feature extraction. Experimental results show that the proposed model outperforms the comparing methods on all three datasets.
Ellipsis Resolution as Question Answering: An Evaluation
Venue: arXiv cs.CL 2021
Year: 2021

Most, if not all forms of ellipsis (e.g., so does Mary) are similar to reading comprehension questions (what does Mary do), in that in order to resolve them, we need to identify an appropriate text span in the preceding discourse. Following this observation, we present an alternative approach for English ellipsis resolution relying on architectures developed for question answering (QA). We present both single-task models, and joint models trained on auxiliary QA and coreference resolution datasets, clearly outperforming the current state of the art for Sluice Ellipsis (from 70.00 to 86.01 F1) and Verb Phrase Ellipsis (from 72.89 to 78.66 F1).
Enabling Simulation-Based Optimization Through Machine Learning: A Case Study on Antenna Design
Venue: arXiv cs.IT 2021
Year: 2021

Complex phenomena are generally modeled with sophisticated simulators that, depending on their accuracy, can be very demanding in terms of computational resources and simulation time. Their time-consuming nature, together with a typically vast parameter space to be explored, make simulation-based optimization often infeasible. In this work, we present a method that enables the optimization of complex systems through Machine Learning (ML) techniques. We show how well-known learning algorithms are able to reliably emulate a complex simulator with a modest dataset obtained from it. The trained emulator is then able to yield values close to the simulated ones in virtually no time. Therefore, it is possible to perform a global numerical optimization over the vast multi-dimensional parameter space, in a fraction of the time that would be required by a simple brute-force search. As a testbed for the proposed methodology, we used a network simulator for next-generation mmWave cellular systems. After simulating several antenna configurations and collecting the resulting network-level statistics, we feed it into our framework. Results show that, even with few data points, extrapolating a continuous model makes it possible to estimate the global optimum configuration almost instantaneously. The very same tool can then be used to achieve any further optimization goal on the same input parameters in negligible time.
NEZHA: Neural Contextualized Representation for Chinese Language Understanding
Venue: arXiv cs.CL 2021
Year: 2021

The pre-trained language models have achieved great successes in various natural language understanding (NLU) tasks due to its capacity to capture the deep contextualized information in text by pre-training on large-scale corpora. In this technical report, we present our practice of pre-training language models named NEZHA (NEural contextualiZed representation for CHinese lAnguage understanding) on Chinese corpora and finetuning for the Chinese NLU tasks. The current version of NEZHA is based on BERT with a collection of proven improvements, which include Functional Relative Positional Encoding as an effective positional encoding scheme, Whole Word Masking strategy, Mixed Precision Training and the LAMB Optimizer in training the models. The experimental results show that NEZHA achieves the state-of-the-art performances when finetuned on several representative Chinese tasks, including named entity recognition (People's Daily NER), sentence matching (LCQMC), Chinese sentiment classification (ChnSenti) and natural language inference (XNLI).
The Complexity of Reachability in Affine Vector Addition Systems with States
Venue: arXiv cs.LO 2021
Year: 2021

Vector addition systems with states (VASS) are widely used for the formal verification of concurrent systems. Given their tremendous computational complexity, practical approaches have relied on techniques such as reachability relaxations, e.g., allowing for negative intermediate counter values. It is natural to question their feasibility for VASS enriched with primitives that typically translate into undecidability. Spurred by this concern, we pinpoint the complexity of integer relaxations with respect to arbitrary classes of affine operations. More specifically, we provide a trichotomy on the complexity of integer reachability in VASS extended with affine operations (affine VASS). Namely, we show that it is NP-complete for VASS with resets, PSPACE-complete for VASS with (pseudo-)transfers and VASS with (pseudo-)copies, and undecidable for any other class. We further present a dichotomy for standard reachability in affine VASS: it is decidable for VASS with permutations, and undecidable for any other class. This yields a complete and unified complexity landscape of reachability in affine VASS. We also consider the reachability problem parameterized by a fixed affine VASS, rather than a class, and we show that the complexity landscape is arbitrary in this setting.
On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons
Venue: arXiv cs.LG 2021
Year: 2021

This paper studies the problem of finding the exact ranking from noisy comparisons. A comparison over a set of $m$ items produces a noisy outcome about the most preferred item, and reveals some information about the ranking. By repeatedly and adaptively choosing items to compare, we want to fully rank the items with a certain confidence, and use as few comparisons as possible. Different from most previous works, in this paper, we have three main novelties: (i) compared to prior works, our upper bounds (algorithms) and lower bounds on the sample complexity (aka number of comparisons) require the minimal assumptions on the instances, and are not restricted to specific models; (ii) we give lower bounds and upper bounds on instances with unequal noise levels; and (iii) this paper aims at the exact ranking without knowledge on the instances, while most of the previous works either focus on approximate rankings or study exact ranking but require prior knowledge. We first derive lower bounds for pairwise ranking (i.e., compare two items each time), and then propose (nearly) optimal pairwise ranking algorithms. We further make extensions to listwise ranking (i.e., comparing multiple items each time). Numerical results also show our improvements against the state of the art.
A scalable constructive algorithm for the optimization of neural network architectures
Venue: arXiv cs.LG 2021
Year: 2021

We propose a new scalable method to optimize the architecture of an artificial neural network. The proposed algorithm, called Greedy Search for Neural Network Architecture, aims to determine a neural network with minimal number of layers that is at least as performant as neural networks of the same structure identified by other hyperparameter search algorithms in terms of accuracy and computational cost. Numerical results performed on benchmark datasets show that, for these datasets, our method outperforms state-of-the-art hyperparameter optimization algorithms in terms of attainable predictive performance by the selected neural network architecture, and time-to-solution for the hyperparameter optimization to complete.
Czech Text Processing with Contextual Embeddings: POS Tagging, Lemmatization, Parsing and NER
Venue: arXiv cs.CL 2021
Year: 2021

Contextualized embeddings, which capture appropriate word meaning depending on context, have recently been proposed. We evaluate two meth ods for precomputing such embeddings, BERT and Flair, on four Czech text processing tasks: part-of-speech (POS) tagging, lemmatization, dependency pars ing and named entity recognition (NER). The first three tasks, POS tagging, lemmatization and dependency parsing, are evaluated on two corpora: the Prague Dependency Treebank 3.5 and the Universal Dependencies 2.3. The named entity recognition (NER) is evaluated on the Czech Named Entity Corpus 1.1 and 2.0. We report state-of-the-art results for the above mentioned tasks and corpora.
On the Strong Equivalences for LPMLN Programs
Venue: arXiv cs.LO 2021
Year: 2021

LPMLN is a powerful knowledge representation and reasoning tool that combines the non-monotonic reasoning ability of Answer Set Programming (ASP) and the probabilistic reasoning ability of Markov Logic Networks (MLN). In this paper, we study the strong equivalence for LPMLN programs, which is an important tool for program rewriting and theoretical investigations in the field of logic programming. First of all, we present the notion of p-strong equivalence for LPMLN and present a model-theoretical characterization for the notion. And we investigate the relationships among the p-strong equivalence and other existing notions of strong equivalences for LPMLN. Then, we investigate several properties of the p-strong equivalence from the following four aspects. Firstly, we investigate two relaxed notions of the p-strong equivalence according to practical scenarios of program rewriting, and present corresponding characterizations for the notions. Secondly, we analyze the computational complexities of deciding strong equivalences for LPMLN programs. Thirdly, we investigate the relationships among the strong equivalences of LPMLN and two extensions of ASP: ASP with weak constraints and ordered disjunctions. Finally, we investigate LPMLN program simplification via the p-strong equivalence and present some syntactic conditions that decide the p-strong equivalence between a single LPMLN rule and the empty program. The contributions of the paper are as follows. Firstly, all of the results presented in this paper provide a better understanding of LPMLN programming, which helps us further explore the properties of LPMLN. Secondly, the relationships among the strong equivalences open a way to study the strong equivalences for some logic formalisms by translating into LPMLN. Thirdly, the program simplification can be used to enhance the implementations of the LPMLN solvers ...
A Generalised Construction of Multiple Complete Complementary Codes and Asymptotically Optimal Aperiodic Quasi-Complementary Sequence Sets
Venue: arXiv cs.IT 2021
Year: 2021

In recent years, complementary sequence sets have found many important applications in multi-carrier code-division multiple-access (MC-CDMA) systems for their good correlation properties. In this paper, we propose a construction, which can generate multiple sets of complete complementary codes (CCCs) over $\mathbb{Z}_N$, where $N~(N\geq 3)$ is a positive integer of the form $N=p_0^{e^0}p_1^{e^1}\dots p_{n-1}^{e^{n-1}}$, $p_0<p_1<\cdots<p_{n-1}$ are prime factors of $N$ and $e_0,e_1,\cdots,e_{n-1}$ are non-negative integers. Interestingly, the maximum inter-set aperiodic cross-correlation magnitude of the proposed CCCs is upper bounded by $N$. When $N$ is odd, the combination of the proposed CCCs results to a new set of sequences to obtain asymptotically optimal and near-optimal aperiodic quasi-complementary sequence sets (QCSSs) with more flexible parameters.
Antipodal Robotic Grasping using Generative Residual Convolutional Neural Network
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we present a modular robotic system to tackle the problem of generating and performing antipodal robotic grasps for unknown objects from n-channel image of the scene. We propose a novel Generative Residual Convolutional Neural Network (GR-ConvNet) model that can generate robust antipodal grasps from n-channel input at real-time speeds (~20ms). We evaluate the proposed model architecture on standard datasets and a diverse set of household objects. We achieved state-of-the-art accuracy of 97.7% and 94.6% on Cornell and Jacquard grasping datasets respectively. We also demonstrate a grasp success rate of 95.4% and 93% on household and adversarial objects respectively using a 7 DoF robotic arm.
Cache Where you Want! Reconciling Predictability and Coherent Caching
Venue: arXiv cs.DC 2021
Year: 2021

Real-time and cyber-physical systems need to interact with and respond to their physical environment in a predictable time. While multicore platforms provide incredible computational power and throughput, they also introduce new sources of unpredictability. Large fluctuations in latency to access data shared between multiple cores is an important contributor to the overall execution-time variability. In addition to the temporal unpredictability introduced by caching, parallel applications with data shared across multiple cores also pay additional latency overheads due to data coherence. Analyzing the impact of data coherence on the worst-case execution-time of real-time applications is challenging because only scarce implementation details are revealed by manufacturers. This paper presents application level control for caching data at different levels of the cache hierarchy. The rationale is that by caching data only in shared cache it is possible to bypass private caches. The access latency to data present in caches becomes independent of its coherence state. We discuss the existing architectural support as well as the required hardware and OS modifications to support the proposed cacheability control. We evaluate the system on an architectural simulator. We show that the worst case execution time for a single memory write request is reduced by 52%. Benchmark evaluations show that proposed technique has a minimal impact on average performance.
Horizontal Flows and Manifold Stochastics in Geometric Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

We introduce two constructions in geometric deep learning for 1) transporting orientation-dependent convolutional filters over a manifold in a continuous way and thereby defining a convolution operator that naturally incorporates the rotational effect of holonomy; and 2) allowing efficient evaluation of manifold convolution layers by sampling manifold valued random variables that center around a weighted diffusion mean. Both methods are inspired by stochastics on manifolds and geometric statistics, and provide examples of how stochastic methods -- here horizontal frame bundle flows and non-linear bridge sampling schemes, can be used in geometric deep learning. We outline the theoretical foundation of the two methods, discuss their relation to Euclidean deep networks and existing methodology in geometric deep learning, and establish important properties of the proposed constructions.
LDPC Codes Achieve List Decoding Capacity
Venue: arXiv cs.IT 2021
Year: 2021

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any $\textit{local}$ property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decodability, list-recoverability and average-radius list-decodability. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$.
Propagation complete encodings of smooth DNNF theories
Venue: arXiv cs.AI 2021
Year: 2021

We investigate conjunctive normal form (CNF) encodings of a function represented with a decomposable negation normal form (DNNF). Several encodings of DNNFs and decision diagrams were considered by (Abio et al. 2016). The authors differentiate between encodings which implement consistency or domain consistency by unit propagation from encodings which are unit refutation complete or propagation complete. The difference is that in the former case we do not care about propagation strength of the encoding with respect to the auxiliary variables while in the latter case we treat all variables (the main and the auxiliary ones) in the same way. The currently known encodings of DNNF theories implement domain consistency. Building on these encodings we generalize the result of (Abio et al. 2016) on a propagation complete encoding of decision diagrams and present a propagation complete encoding of a DNNF and its generalization for variables with finite domains.