OpenRaiser/Intern-Atlas huggingface dataset:
RepMLP: Re-parameterizing Convolutions into Fully-connected Layers for Image Recognition
Venue: arXiv cs.CV 2022
Year: 2022

We propose RepMLP, a multi-layer-perceptron-style neural network building block for image recognition, which is composed of a series of fully-connected (FC) layers. Compared to convolutional layers, FC layers are more efficient, better at modeling the long-range dependencies and positional patterns, but worse at capturing the local structures, hence usually less favored for image recognition. We propose a structural re-parameterization technique that adds local prior into an FC to make it powerful for image recognition. Specifically, we construct convolutional layers inside a RepMLP during training and merge them into the FC for inference. On CIFAR, a simple pure-MLP model shows performance very close to CNN. By inserting RepMLP in traditional CNN, we improve ResNets by 1.8% accuracy on ImageNet, 2.9% for face recognition, and 2.3% mIoU on Cityscapes with lower FLOPs. Our intriguing findings highlight that combining the global representational capacity and positional perception of FC with the local prior of convolution can improve the performance of neural network with faster speed on both the tasks with translation invariance (e.g., semantic segmentation) and those with aligned images and positional patterns (e.g., face recognition). The code and models are available at https://github.com/DingXiaoH/RepMLP.
GRAPHOPT: constrained-optimization-based parallelization of irregular graphs
Venue: arXiv cs.DC 2022
Year: 2022

Sparse, irregular graphs show up in various applications like linear algebra, machine learning, engineering simulations, robotic control, etc. These graphs have a high degree of parallelism, but their execution on parallel threads of modern platforms remains challenging due to the irregular data dependencies. The execution performance can be improved by efficiently partitioning the graphs such that the communication and thread synchronization overheads are minimized without hurting the utilization of the threads. To achieve this, this paper proposes GRAPHOPT, a tool that models the graph parallelization as a constrained optimization problem and uses the open Google OR-Tools solver to find good partitions. Several scalability techniques are developed to handle large real-world graphs with millions of nodes and edges. Extensive experiments are performed on the graphs of sparse matrix triangular solves (linear algebra) and sum-product networks (machine learning), respectively, showing a mean speedup of 2.0X and 1.8X over previous state-of-the-art libraries, demonstrating the effectiveness of the constrained-optimization-based graph parallelization.
Evaluation Of Word Embeddings From Large-Scale French Web Content
Venue: arXiv cs.CL 2022
Year: 2022

Distributed word representations are popularly used in many tasks in natural language processing. Adding that pretrained word vectors on huge text corpus achieved high performance in many different NLP tasks. This paper introduces multiple high-quality word vectors for the French language where two of them are trained on massive crawled French data during this study and the others are trained on an already existing French corpus. We also evaluate the quality of our proposed word vectors and the existing French word vectors on the French word analogy task. In addition, we do the evaluation on multiple real NLP tasks that shows the important performance enhancement of the pre-trained word vectors compared to the existing and random ones. Finally, we created a demo web application to test and visualize the obtained word embeddings. The produced French word embeddings are available to the public, along with the finetuning code on the NLU tasks and the demo code.
When Fair Ranking Meets Uncertain Inference
Venue: arXiv cs.IR 2022
Year: 2022

Existing fair ranking systems, especially those designed to be demographically fair, assume that accurate demographic information about individuals is available to the ranking algorithm. In practice, however, this assumption may not hold -- in real-world contexts like ranking job applicants or credit seekers, social and legal barriers may prevent algorithm operators from collecting peoples' demographic information. In these cases, algorithm operators may attempt to infer peoples' demographics and then supply these inferences as inputs to the ranking algorithm. In this study, we investigate how uncertainty and errors in demographic inference impact the fairness offered by fair ranking algorithms. Using simulations and three case studies with real datasets, we show how demographic inferences drawn from real systems can lead to unfair rankings. Our results suggest that developers should not use inferred demographic data as input to fair ranking algorithms, unless the inferences are extremely accurate.
Coherence Attacks and Countermeasures in Interposer-Based Systems
Venue: arXiv cs.AR 2022
Year: 2022

Industry is moving towards large-scale systems where processor cores, memories, accelerators, etc.\ are bundled via 2.5D integration. These various components are fabricated separately as chiplets and then integrated using an interconnect carrier, a so-called interposer. This new design style provides benefits in terms of yield as well as economies of scale, as chiplets may come from various third-party vendors, and be integrated into one sophisticated system. The benefits of this approach, however, come at the cost of new challenges for the system's security and integrity when many third-party component chiplets, some from not fully trusted vendors, are integrated. Here, we explore these challenges, but also promises, for modern interposer-based systems of cache-coherent, multi-core chiplets. First, we introduce a new, coherence-based attack, GETXspy, wherein a single compromised chiplet can expose a high-bandwidth side/covert-channel in an ostensibly secure system. We further show that prior art is insufficient to stop this new attack. Second, we propose using an active interposer as generic, secure-by-construction platform that forms a physical root of trust for modern 2.5D systems. Our scheme has limited overhead, restricted to the active interposer, allowing the chiplets and the coherence system to remain untouched. We show that our scheme prevents a wide range of attacks, including but not limited to our GETXspy attack, with little overhead on system performance, $\sim$4\%. This overhead reduces as workloads increase, ensuring scalability of the scheme.
Static Inference Meets Deep Learning: A Hybrid Type Inference Approach for Python
Venue: arXiv cs.SE 2022
Year: 2022

Type inference for dynamic programming languages such as Python is an important yet challenging task. Static type inference techniques can precisely infer variables with enough static constraints but are unable to handle variables with dynamic features. Deep learning (DL) based approaches are feature-agnostic, but they cannot guarantee the correctness of the predicted types. Their performance significantly depends on the quality of the training data (i.e., DL models perform poorly on some common types that rarely appear in the training dataset). It is interesting to note that the static and DL-based approaches offer complementary benefits. Unfortunately, to our knowledge, precise type inference based on both static inference and neural predictions has not been exploited and remains an open challenge. In particular, it is hard to integrate DL models into the framework of rule-based static approaches. This paper fills the gap and proposes a hybrid type inference approach named HiTyper based on both static inference and deep learning. Specifically, our key insight is to record type dependencies among variables in each function and encode the dependency information in type dependency graphs (TDGs). Based on TDGs, we can easily integrate type inference rules in the nodes to conduct static inference and type rejection rules to inspect the correctness of neural predictions. HiTyper iteratively conducts static inference and DL-based prediction until the TDG is fully inferred. Experiments on two benchmark datasets show that HiTyper outperforms state-of-the-art DL models by exactly matching 10% more human annotations. HiTyper also achieves an increase of more than 30% on inferring rare types. Considering only the static part of HiTyper, it infers 2x ~ 3x more types than existing static type inference tools.
FastCorrect: Fast Error Correction with Edit Alignment for Automatic Speech Recognition
Venue: arXiv cs.CL 2022
Year: 2022

Error correction techniques have been used to refine the output sentences from automatic speech recognition (ASR) models and achieve a lower word error rate (WER) than original ASR outputs. Previous works usually use a sequence-to-sequence model to correct an ASR output sentence autoregressively, which causes large latency and cannot be deployed in online ASR services. A straightforward solution to reduce latency, inspired by non-autoregressive (NAR) neural machine translation, is to use an NAR sequence generation model for ASR error correction, which, however, comes at the cost of significantly increased ASR error rate. In this paper, observing distinctive error patterns and correction operations (i.e., insertion, deletion, and substitution) in ASR, we propose FastCorrect, a novel NAR error correction model based on edit alignment. In training, FastCorrect aligns each source token from an ASR output sentence to the target tokens from the corresponding ground-truth sentence based on the edit distance between the source and target sentences, and extracts the number of target tokens corresponding to each source token during edition/correction, which is then used to train a length predictor and to adjust the source tokens to match the length of the target sentence for parallel generation. In inference, the token number predicted by the length predictor is used to adjust the source tokens for target sequence generation. Experiments on the public AISHELL-1 dataset and an internal industrial-scale ASR dataset show the effectiveness of FastCorrect for ASR error correction: 1) it speeds up the inference by 6-9 times and maintains the accuracy (8-14% WER reduction) compared with the autoregressive correction model; and 2) it outperforms the popular NAR models adopted in neural machine translation and text edition by a large margin.
Opening the Blackbox: Accelerating Neural Differential Equations by Regularizing Internal Solver Heuristics
Venue: arXiv cs.LG 2022
Year: 2022

Democratization of machine learning requires architectures that automatically adapt to new problems. Neural Differential Equations (NDEs) have emerged as a popular modeling framework by removing the need for ML practitioners to choose the number of layers in a recurrent model. While we can control the computational cost by choosing the number of layers in standard architectures, in NDEs the number of neural network evaluations for a forward pass can depend on the number of steps of the adaptive ODE solver. But, can we force the NDE to learn the version with the least steps while not increasing the training cost? Current strategies to overcome slow prediction require high order automatic differentiation, leading to significantly higher training time. We describe a novel regularization method that uses the internal cost heuristics of adaptive differential equation solvers combined with discrete adjoint sensitivities to guide the training process towards learning NDEs that are easier to solve. This approach opens up the blackbox numerical analysis behind the differential equation solver's algorithm and directly uses its local error estimates and stiffness heuristics as cheap and accurate cost estimates. We incorporate our method without any change in the underlying NDE framework and show that our method extends beyond Ordinary Differential Equations to accommodate Neural Stochastic Differential Equations. We demonstrate how our approach can halve the prediction time and, unlike other methods which can increase the training time by an order of magnitude, we demonstrate similar reduction in training times. Together this showcases how the knowledge embedded within state-of-the-art equation solvers can be used to enhance machine learning.
High-performance symbolic-numerics via multiple dispatch
Venue: arXiv cs.CL 2022
Year: 2022

As mathematical computing becomes more democratized in high-level languages, high-performance symbolic-numeric systems are necessary for domain scientists and engineers to get the best performance out of their machine without deep knowledge of code optimization. Naturally, users need different term types either to have different algebraic properties for them, or to use efficient data structures. To this end, we developed Symbolics.jl, an extendable symbolic system which uses dynamic multiple dispatch to change behavior depending on the domain needs. In this work we detail an underlying abstract term interface which allows for speed without sacrificing generality. We show that by formalizing a generic API on actions independent of implementation, we can retroactively add optimized data structures to our system without changing the pre-existing term rewriters. We showcase how this can be used to optimize term construction and give a 113x acceleration on general symbolic transformations. Further, we show that such a generic API allows for complementary term-rewriting implementations. We demonstrate the ability to swap between classical term-rewriting simplifiers and e-graph-based term-rewriting simplifiers. We showcase an e-graph ruleset which minimizes the number of CPU cycles during expression evaluation, and demonstrate how it simplifies a real-world reaction-network simulation to halve the runtime. Additionally, we show a reaction-diffusion partial differential equation solver which is able to be automatically converted into symbolic expressions via multiple dispatch tracing, which is subsequently accelerated and parallelized to give a 157x simulation speedup. Together, this presents Symbolics.jl as a next-generation symbolic-numeric computing environment geared towards modeling and simulation.
A United Framework for both Formal, Natural and Social Science
Venue: arXiv cs.DL 2022
Year: 2022

With the expansion of scientific research, the number of scientific research is increasing. A new urgent problem is raised that how to keep these researches in a proper way. Therefore, knowledge mapping methods come into being, providing a lot of management and application functions. Therefore, knowledge mapping methods come into being, providing a lot of management and application functions. To answer this question, a three-dimensional knowledge map is proposed in this paper, with time, space and number based on category and numericity. It is able to conclude most of scientific problems related to numericity interdisciplinary. Compared with the traditional way, this map is normative, and puts forward the general production criteria of labeling and digitization. It is also intuitive and readable, on which nature, society and formal science are expressed in the same view. The scientific methodologies are summarized, so that the methods with similar logic between different disciplines can be used for reference in development. Compared with the traditional way, this map is normative, and puts forward the general production criteria of labeling and digitization. It is also intuitive and readable, on which nature, society and formal science are expressed in the same view. The scientific methodologies are summarized, so that the methods with similar logic between different disciplines can be used for reference in development. Mathematics also show its importance on the map as formal Science, indicating that it is the key to the development of science. This is not only a preliminary model of a comprehensive scientific worldview, but also a preliminary framework for the connection and cooperation of various disciplines in the future.
Polynomial-Delay Enumeration of Large Maximal Matchings
Venue: arXiv cs.DS 2022
Year: 2022

Enumerating matchings is a classical problem in the field of enumeration algorithms. There are polynomial-delay enumeration algorithms for several settings, such as enumerating perfect matchings, maximal matchings, and (weighted) matchings in specific orders. In this paper, we present polynomial-delay enumeration algorithms for maximal matchings with cardinality at least given threshold $t$. Our algorithm enumerates all such matchings in $O(nm)$ delay with exponential space, where $n$ and $m$ are the number of vertices and edges of an input graph, respectively. We also present a polynomial-delay and polynomial-space enumeration algorithm for this problem. As a variant of this algorithm, we give an algorithm that enumerates all maximal matchings in non-decreasing order of its cardinality and runs in $O(nm)$ delay.
TRAP: The Bait of Rational Players to Solve Byzantine Consensus
Venue: arXiv cs.DC 2022
Year: 2022

It is impossible to solve the Byzantine consensus problem in an open network of $n$ participants if only $2n/3$ or less of them are correct. As blockchains need to solve consensus, one might think that blockchains need more than $2n/3$ correct participants. But it is yet unknown whether consensus can be solved when less than $2n/3$ participants are correct and $k$ participants are rational players, which misbehave if they can gain the loot. Trading correct participants for rational players may not seem helpful to solve consensus since rational players can misbehave whereas correct participants, by definition, cannot. In this paper, we show that consensus is actually solvable in this model, even with less than $2n/3$ correct participants. The key idea is a baiting strategy that lets rational players pretend to misbehave in joining a coalition but rewards them to betray this coalition before the loot gets stolen. We propose TRAP, a protocol that builds upon recent advances in the theory of accountability to solve consensus as soon as $n>\max\bigl(\frac{3}{2}k+3t,2(k+t)\bigr)$: by assuming that private keys cannot be forged, this protocol is an equilibrium where no coalition of $k$ rational players can coordinate to increase their expected utility regardless of the arbitrary behavior of up to $t$ Byzantine players. Finally, we show that a baiting strategy is necessary and sufficient to solve this, so-called rational agreement problem. First, we show that it is impossible to solve this rational agreement problem without implementing a baiting strategy. Second, the existence of TRAP demonstrates the sufficiency of the baiting strategy. Our TRAP protocol finds applications in blockchains to prevent players from disagreeing, that could otherwise lead to "double spending".
Multi-Objective Controller Synthesis with Uncertain Human Preferences
Venue: arXiv cs.AI 2022
Year: 2022

Complex real-world applications of cyber-physical systems give rise to the need for multi-objective controller synthesis, which concerns the problem of computing an optimal controller subject to multiple (possibly conflicting) criteria. The relative importance of objectives is often specified by human decision-makers. However, there is inherent uncertainty in human preferences (e.g., due to artifacts resulting from different preference elicitation methods). In this paper, we formalize the notion of uncertain human preferences and present a novel approach that accounts for this uncertainty in the context of multi-objective controller synthesis for Markov decision processes (MDPs). Our approach is based on mixed-integer linear programming and synthesizes an optimally permissive multi-strategy that satisfies uncertain human preferences with respect to a multi-objective property. Experimental results on a range of large case studies show that the proposed approach is feasible and scalable across varying MDP model sizes and uncertainty levels of human preferences. Evaluation via an online user study also demonstrates the quality and benefits of the synthesized controllers.
Proving Regulatory Compliance: Full Compliance Against an Expressive Unconditional Obligation is coNP-Complete
Venue: arXiv cs.CC 2022
Year: 2022

Organisations are required to show that their procedures and processes satisfy the relevant regulatory requirements. The computational complexity of proving regulatory compliance is known to be generally hard. However, for some of its simpler variants the computational complexity is still unknown. We focus on the eight variants of the problem that can be identified by the following binary properties: whether the requirements consists of one or multiple obligations, whether the obligations are conditional or always in force, and whether only propositional literals or formulae can be used to describe the obligations. This paper in particular shows that proving full compliance of a model against a single unconditional obligation whose elements can be described using formulae is coNP-complete. Finally we show how this result allows to fully map the computational complexity of these variants for proving full and non compliance, while for partial compliance the complexity result of one of the variants is still missing.
A Systematic Literature Review on Blockchain Governance
Venue: arXiv cs.SE 2022
Year: 2022

Blockchain has been increasingly used as a software component to enable decentralisation in software architecture for a variety of applications. Blockchain governance has received considerable attention to ensure the safe and appropriate use and evolution of blockchain, especially after the Ethereum DAO attack in 2016. However, there are no systematic efforts to analyse existing governance solutions. To understand the state-of-the-art of blockchain governance, we conducted a systematic literature review with 37 primary studies. The extracted data from primary studies are synthesised to answer identified research questions. The study results reveal several major findings: 1) governance can improve the adaptability and upgradability of blockchain, whilst the current studies neglect broader ethical responsibilities as the objectives of blockchain governance; 2) governance is along with the development process of a blockchain platform, while ecosystem-level governance process is missing, and; 3) the responsibilities and capabilities of blockchain stakeholders are briefly discussed, whilst the decision rights, accountability, and incentives of blockchain stakeholders are still under studied. We provide actionable guidelines for academia and practitioners to use throughout the lifecycle of blockchain, and identify future trends to support researchers in this area.