OpenRaiser/Intern-Atlas huggingface dataset:
FNet: Mixing Tokens with Fourier Transforms
Venue: arXiv cs.CL 2022
Year: 2022

We show that Transformer encoder architectures can be sped up, with limited accuracy costs, by replacing the self-attention sublayers with simple linear transformations that "mix" input tokens. These linear mixers, along with standard nonlinearities in feed-forward layers, prove competent at modeling semantic relationships in several text classification tasks. Most surprisingly, we find that replacing the self-attention sublayer in a Transformer encoder with a standard, unparameterized Fourier Transform achieves 92-97% of the accuracy of BERT counterparts on the GLUE benchmark, but trains 80% faster on GPUs and 70% faster on TPUs at standard 512 input lengths. At longer input lengths, our FNet model is significantly faster: when compared to the "efficient" Transformers on the Long Range Arena benchmark, FNet matches the accuracy of the most accurate models, while outpacing the fastest models across all sequence lengths on GPUs (and across relatively shorter lengths on TPUs). Finally, FNet has a light memory footprint and is particularly efficient at smaller model sizes; for a fixed speed and accuracy budget, small FNet models outperform Transformer counterparts.
Leveraging Structural Information to Improve Point Line Visual-Inertial Odometry
Venue: arXiv cs.RO 2022
Year: 2022

Leveraging line features can help to improve the localization accuracy of point-based monocular Visual-Inertial Odometry (VIO) system, as lines provide additional constraints. Moreover, in an artificial environment, some straight lines are parallel to each other. In this paper, we designed a VIO system based on points and straight lines, which divides straight lines into structural straight lines (that is, straight lines parallel to each other) and non-structural straight lines. In addition, unlike the orthogonal representation using four parameters to represent the 3D straight line, we only used two parameters to minimize the representation of the structural straight line and the non-structural straight line. Furthermore, we designed a straight line matching strategy based on sampling points to improve the efficiency and success rate of straight line matching. The effectiveness of our method is verified on both public datasets of EuRoc and TUM VI benchmark and compared with other state-of-the-art algorithms.
A Sharp Algorithmic Analysis of Covariate Adjusted Precision Matrix Estimation with General Structural Priors
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we present a sharp analysis for a class of alternating projected gradient descent algorithms which are used to solve the covariate adjusted precision matrix estimation problem in the high-dimensional setting. We demonstrate that these algorithms not only enjoy a linear rate of convergence in the absence of convexity, but also attain the optimal statistical rate (i.e., minimax rate). By introducing the generic chaining, our analysis removes the impractical resampling assumption used in the previous work. Moreover, our results also reveal a time-data tradeoff in this covariate adjusted precision matrix estimation problem. Numerical experiments are provided to verify our theoretical results.
Poolingformer: Long Document Modeling with Pooling Attention
Venue: arXiv cs.CL 2022
Year: 2022

In this paper, we introduce a two-level attention schema, Poolingformer, for long document modeling. Its first level uses a smaller sliding window pattern to aggregate information from neighbors. Its second level employs a larger window to increase receptive fields with pooling attention to reduce both computational cost and memory consumption. We first evaluate Poolingformer on two long sequence QA tasks: the monolingual NQ and the multilingual TyDi QA. Experimental results show that Poolingformer sits atop three official leaderboards measured by F1, outperforming previous state-of-the-art models by 1.9 points (79.8 vs. 77.9) on NQ long answer, 1.9 points (79.5 vs. 77.6) on TyDi QA passage answer, and 1.6 points (67.6 vs. 66.0) on TyDi QA minimal answer. We further evaluate Poolingformer on a long sequence summarization task. Experimental results on the arXiv benchmark continue to demonstrate its superior performance.
Continual Learning via Bit-Level Information Preserving
Venue: arXiv cs.LG 2022
Year: 2022

Continual learning tackles the setting of learning different tasks sequentially. Despite the lots of previous solutions, most of them still suffer significant forgetting or expensive memory cost. In this work, targeted at these problems, we first study the continual learning process through the lens of information theory and observe that forgetting of a model stems from the loss of \emph{information gain} on its parameters from the previous tasks when learning a new task. From this viewpoint, we then propose a novel continual learning approach called Bit-Level Information Preserving (BLIP) that preserves the information gain on model parameters through updating the parameters at the bit level, which can be conveniently implemented with parameter quantization. More specifically, BLIP first trains a neural network with weight quantization on the new incoming task and then estimates information gain on each parameter provided by the task data to determine the bits to be frozen to prevent forgetting. We conduct extensive experiments ranging from classification tasks to reinforcement learning tasks, and the results show that our method produces better or on par results comparing to previous state-of-the-arts. Indeed, BLIP achieves close to zero forgetting while only requiring constant memory overheads throughout continual learning.
Physical Fault Injection and Side-Channel Attacks on Mobile Devices: A Comprehensive Analysis
Venue: arXiv cs.CR 2022
Year: 2022

Today's mobile devices contain densely packaged system-on-chips (SoCs) with multi-core, high-frequency CPUs and complex pipelines. In parallel, sophisticated SoC-assisted security mechanisms have become commonplace for protecting device data, such as trusted execution environments, full-disk and file-based encryption. Both advancements have dramatically complicated the use of conventional physical attacks, requiring the development of specialised attacks. In this survey, we consolidate recent developments in physical fault injections and side-channel attacks on modern mobile devices. In total, we comprehensively survey over 50 fault injection and side-channel attack papers published between 2009-2021. We evaluate the prevailing methods, compare existing attacks using a common set of criteria, identify several challenges and shortcomings, and suggest future directions of research.
Representative community divisions of networks
Venue: arXiv cs.SI 2022
Year: 2022

Methods for detecting community structure in networks typically aim to identify a single best partition of network nodes into communities, often by optimizing some objective function, but in real-world applications there may be many competitive partitions with objective scores close to the global optimum and one can obtain a more informative picture of the community structure by examining a representative set of such high-scoring partitions than by looking at just the single optimum. However, such a set can be difficult to interpret since its size can easily run to hundreds or thousands of partitions. In this paper we present a method for analyzing large partition sets by dividing them into groups of similar partitions and then identifying an archetypal partition as a representative of each group. The resulting set of archetypal partitions provides a succinct, interpretable summary of the form and variety of community structure in any network. We demonstrate the method on a range of example networks.
Differentially Private Transferrable Deep Learning with Membership-Mappings
Venue: arXiv cs.LG 2022
Year: 2022

This paper considers the problem of differentially private semi-supervised transfer and multi-task learning. The notion of \emph{membership-mapping} has been developed using measure theory basis to learn data representation via a fuzzy membership function. An alternative conception of deep autoencoder, referred to as \emph{Conditionally Deep Membership-Mapping Autoencoder (CDMMA)}, is considered for transferrable deep learning. Under practice-oriented settings, an analytical solution for the learning of CDMMA can be derived by means of variational optimization. The paper proposes a transfer and multi-task learning approach that combines CDMMA with a tailored noise adding mechanism to achieve a given level of privacy-loss bound with the minimum perturbation of the data. Numerous experiments were carried out using MNIST, USPS, Office, and Caltech256 datasets to verify the competitive robust performance of the proposed methodology.
Causal Inference in medicine and in health policy, a summary
Venue: arXiv cs.LG 2022
Year: 2022

A data science task can be deemed as making sense of the data or testing a hypothesis about it. The conclusions inferred from data can greatly guide us to make informative decisions. Big data has enabled us to carry out countless prediction tasks in conjunction with machine learning, such as identifying high risk patients suffering from a certain disease and taking preventable measures. However, healthcare practitioners are not content with mere predictions - they are also interested in the cause-effect relation between input features and clinical outcomes. Understanding such relations will help doctors treat patients and reduce the risk effectively. Causality is typically identified by randomized controlled trials. Often such trials are not feasible when scientists and researchers turn to observational studies and attempt to draw inferences. However, observational studies may also be affected by selection and/or confounding biases that can result in wrong causal conclusions. In this chapter, we will try to highlight some of the drawbacks that may arise in traditional machine learning and statistical approaches to analyze the observational data, particularly in the healthcare data analytics domain. We will discuss causal inference and ways to discover the cause-effect from observational studies in healthcare domain. Moreover, we will demonstrate the applications of causal inference in tackling some common machine learning issues such as missing data and model transportability. Finally, we will discuss the possibility of integrating reinforcement learning with causality as a way to counter confounding bias.
Exact Recovery in the General Hypergraph Stochastic Block Model
Venue: arXiv cs.IT 2022
Year: 2022

This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph stochastic block model (d-HSBM), wherein n nodes are partitioned into k disjoint communities with relative sizes (p1,..., pk). Each subset of nodes with cardinality d is generated independently as an order-d hyperedge with a certain probability that depends on the ground-truth communities that the d nodes belong to. The goal is to exactly recover the k hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and d-HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.
Smart Name Lookup for NDN Forwarding Plane via Neural Networks
Venue: arXiv cs.NI 2022
Year: 2022

Name lookup is a key technology for the forwarding plane of content router in Named Data Networking (NDN). To realize the efficient name lookup, what counts is deploying a highperformance index in content routers. So far, the proposed indexes have shown good performance, most of which are optimized for or evaluated with URLs collected from the current Internet, as the large-scale NDN names are not available yet. Unfortunately, the performance of these indexes is always impacted in terms of lookup speed, memory consumption and false positive probability, as the distributions of URLs retrieved in memory may differ from those of real NDN names independently generated by content-centric applications online. Focusing on this gap, a smart mapping model named Pyramid-NN via neural networks is proposed to build an index called LNI for NDN forwarding plane. Through learning the distributions of the names retrieved in the static memory, LNI can not only reduce the memory consumption and the probability of false positive, but also ensure the performance of real NDN name lookup. Experimental results show that LNI-based FIB can reduce the memory consumption to 58.258 MB for 2 million names. Moreover, as it can be deployed on SRAMs, the throughput is about 177 MSPS, which well meets the current network requirement for fast packet processing.
The explicit formulae for the distributions of nonoverlapping words and its applications to statistical tests for pseudo random numbers
Venue: arXiv cs.IT 2022
Year: 2022

The distributions of the number of occurrences of words (the distributions of words for short) play key roles in information theory, statistics, probability theory, ergodic theory, computer science, and DNA analysis. Bassino et al. 2010 and Regnier et al. 1998 showed generating functions of the distributions of words for all sample sizes. Robin et al. 1999 presented generating functions of the distributions for the return time of words and demonstrated a recurrence formula for these distributions. These generating functions are rational functions; except for simple cases, it is difficult to expand them into power series. In this paper, we study finite-dimensional generating functions of the distributions of nonoverlapping words for each fixed sample size and demonstrate the explicit formulae for the distributions of words for the Bernoulli models. Our results are generalized to nonoverlapping partial words. We study statistical tests that depend on the number of occurrences of words and the number of block-wise occurrences of words, respectively. We demonstrate that the power of the test that depends on the number of occurrences of words is significantly large compared to the other one. Finally, we apply our results to statistical tests for pseudo random numbers.
Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve
Venue: arXiv cs.GT 2022
Year: 2022

We consider the problem of dividing limited resources to individuals arriving over $T$ rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type (i.e. preferences over the different resources). A standard notion of 'fairness' in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency. The former is an individual guarantee, requiring that each agent prefers their own allocation over the allocation of any other; in contrast, efficiency is a global property, requiring that the allocations clear the available resources. For divisible resources, when the number of individuals of each type are known upfront, the above desiderata are simultaneously achievable for a large class of utility functions. However, in an online setting when the number of individuals of each type are only revealed round by round, no policy can guarantee these desiderata simultaneously, and hence the best one can do is to try and allocate so as to approximately satisfy the two properties. We show that in the online setting, the two desired properties (envy-freeness and efficiency) are in direct contention, in that any algorithm achieving additive counterfactual envy-freeness up to a factor of $L_T$ necessarily suffers a efficiency loss of at least $1 / L_T$. We complement this uncertainty principle with a simple algorithm, HopeGuardrail, which allocates resources based on an adaptive threshold policy and is able to achieve any fairness-efficiency point on this frontier. In simulation results, our algorithm provides allocations close to the optimal fair solution in hindsight, motivating its use in practical applications as the algorithm is able to adapt to any desired fairness efficiency trade-off.
Supporting Land Reuse of Former Open Pit Mining Sites using Text Classification and Active Learning
Venue: arXiv cs.CL 2022
Year: 2022

Open pit mines left many regions worldwide inhospitable or uninhabitable. To put these regions back into use, entire stretches of land must be renaturalized. For the sustainable subsequent use or transfer to a new primary use, many contaminated sites and soil information have to be permanently managed. In most cases, this information is available in the form of expert reports in unstructured data collections or file folders, which in the best case are digitized. Due to size and complexity of the data, it is difficult for a single person to have an overview of this data in order to be able to make reliable statements. This is one of the most important obstacles to the rapid transfer of these areas to after-use. An information-based approach to this issue supports fulfilling several Sustainable Development Goals regarding environment issues, health and climate action. We use a stack of Optical Character Recognition, Text Classification, Active Learning and Geographic Information System Visualization to effectively mine and visualize this information. Subsequently, we link the extracted information to geographic coordinates and visualize them using a Geographic Information System. Active Learning plays a vital role because our dataset provides no training data. In total, we process nine categories and actively learn their representation in our dataset. We evaluate the OCR, Active Learning and Text Classification separately to report the performance of the system. Active Learning and text classification results are twofold: Whereas our categories about restrictions work sufficient ($>$.85 F1), the seven topic-oriented categories were complicated for human coders and hence the results achieved mediocre evaluation scores ($<$.70 F1).
Model Pruning Based on Quantified Similarity of Feature Maps
Venue: arXiv cs.CV 2022
Year: 2022

Convolutional Neural Networks (CNNs) has been applied in numerous Internet of Things (IoT) devices for multifarious downstream tasks. However, with the increasing amount of data on edge devices, CNNs can hardly complete some tasks in time with limited computing and storage resources. Recently, filter pruning has been regarded as an effective technique to compress and accelerate CNNs, but existing methods rarely prune CNNs from the perspective of compressing high-dimensional tensors. In this paper, we propose a novel theory to find redundant information in three-dimensional tensors, namely Quantified Similarity between Feature Maps (QSFM), and utilize this theory to guide the filter pruning procedure. We perform QSFM on datasets (CIFAR-10, CIFAR-100 and ILSVRC-12) and edge devices, demonstrate that the proposed method can find the redundant information in the neural networks effectively with comparable compression and tolerable drop of accuracy. Without any fine-tuning operation, QSFM can compress ResNet-56 on CIFAR-10 significantly (48.7% FLOPs and 57.9% parameters are reduced) with only a loss of 0.54% in the top-1 accuracy. For the practical application of edge devices, QSFM can accelerate MobileNet-V2 inference speed by 1.53 times with only a loss of 1.23% in the ILSVRC-12 top-1 accuracy.
Variable Coded Batch Matrix Multiplication
Venue: arXiv cs.IT 2022
Year: 2022

A majority of coded matrix-matrix computation literature has broadly focused in two directions: matrix partitioning for computing a single computation task and batch processing of multiple distinct computation tasks. While these works provide codes with good straggler resilience and fast decoding for their problem spaces, these codes would not be able to take advantage of the natural redundancy of re-using matrices across batch jobs. In this paper, we introduce the Variable Coded Distributed Batch Matrix Multiplication (VCDBMM) problem which tasks a distributed system to perform batch matrix multiplication where matrices are not necessarily distinct among batch jobs. Inspired in part by Cross-Subspace Alignment codes, we develop Flexible Cross-Subspace Alignments (FCSA) codes that are flexible enough to utilize this redundancy. We provide a full characterization of FCSA codes which allow for a wide variety of system complexities including good straggler resilience and fast decoding. We theoretically demonstrate that, under certain practical conditions, FCSA codes are within a factor of 2 of the optimal solution when it comes to straggler resilience. Furthermore, our simulations demonstrate that our codes can achieve even better optimality gaps in practice, even going as low as 1.7.
LGPMA: Complicated Table Structure Recognition with Local and Global Pyramid Mask Alignment
Venue: arXiv cs.CV 2022
Year: 2022

Table structure recognition is a challenging task due to the various structures and complicated cell spanning relations. Previous methods handled the problem starting from elements in different granularities (rows/columns, text regions), which somehow fell into the issues like lossy heuristic rules or neglect of empty cell division. Based on table structure characteristics, we find that obtaining the aligned bounding boxes of text region can effectively maintain the entire relevant range of different cells. However, the aligned bounding boxes are hard to be accurately predicted due to the visual ambiguities. In this paper, we aim to obtain more reliable aligned bounding boxes by fully utilizing the visual information from both text regions in proposed local features and cell relations in global features. Specifically, we propose the framework of Local and Global Pyramid Mask Alignment, which adopts the soft pyramid mask learning mechanism in both the local and global feature maps. It allows the predicted boundaries of bounding boxes to break through the limitation of original proposals. A pyramid mask re-scoring module is then integrated to compromise the local and global information and refine the predicted boundaries. Finally, we propose a robust table structure recovery pipeline to obtain the final structure, in which we also effectively solve the problems of empty cells locating and division. Experimental results show that the proposed method achieves competitive and even new state-of-the-art performance on several public benchmarks.
Retrieval-Free Knowledge-Grounded Dialogue Response Generation with Adapters
Venue: arXiv cs.CL 2022
Year: 2022

To diversify and enrich generated dialogue responses, knowledge-grounded dialogue has been investigated in recent years. The existing methods tackle the knowledge grounding challenge by retrieving the relevant sentences over a large corpus and augmenting the dialogues with explicit extra information. Despite their success, however, the existing works have drawbacks in inference efficiency. This paper proposes KnowExpert, a framework to bypass the explicit retrieval process and inject knowledge into the pre-trained language models with lightweight adapters and adapt to the knowledge-grounded dialogue task. To the best of our knowledge, this is the first attempt to tackle this challenge without retrieval in this task under an open-domain chit-chat scenario. The experimental results show that Knowexpert performs comparably with some retrieval-based baselines while being time-efficient in inference, demonstrating the effectiveness of our proposed method.