OpenRaiser/Intern-Atlas huggingface dataset:
Jointly Learning Span Extraction and Sequence Labeling for Information Extraction from Business Documents
Venue: arXiv cs.CL 2022
Year: 2022

This paper introduces a new information extraction model for business documents. Different from prior studies which only base on span extraction or sequence labeling, the model takes into account advantage of both span extraction and sequence labeling. The combination allows the model to deal with long documents with sparse information (the small amount of extracted information). The model is trained end-to-end to jointly optimize the two tasks in a unified manner. Experimental results on four business datasets in English and Japanese show that the model achieves promising results and is significantly faster than the normal span-based extraction method. The code is also available.
Validated Objects: Specification, Implementation, and Applications
Venue: arXiv cs.DC 2022
Year: 2022

Guaranteeing the validity of concurrent operations on distributed objects is a key property for ensuring reliability and consistency in distributed systems. Usually, the methods for validating these operations, if present, are wired in the object implementation. In this work, we formalize the notion of a {\em validated object}, decoupling the object operations and properties from the validation procedure. We consider two types of objects, satisfying different levels of consistency: the validated {\em totally-ordered} object, offering a total ordering of its operations, and its weaker variant, the validated {\em regular} object. We provide conditions under which it is possible to implement these objects. In particular, we show that crash-tolerant implementations of validated regular objects are always possible in an asynchronous system with a majority of correct processes. However, for validated totally-ordered objects, consensus is always required if a property of the object we introduce in this work, {\em persistent validity,} does not hold. Persistent validity combined with another new property, {\em persistent execution}, allows consensus-free crash-tolerant implementations of validated totally-ordered objects. We demonstrate the utility of validated objects by considering several applications conforming to our formalism.
An Analytic Framework for Robust Training of Artificial Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

The reliability of a learning model is key to the successful deployment of machine learning in various industries. Creating a robust model, particularly one unaffected by adversarial attacks, requires a comprehensive understanding of the adversarial examples phenomenon. However, it is difficult to describe the phenomenon due to the complicated nature of the problems in machine learning. Consequently, many studies investigate the phenomenon by proposing a simplified model of how adversarial examples occur and validate it by predicting some aspect of the phenomenon. While these studies cover many different characteristics of the adversarial examples, they have not reached a holistic approach to the geometric and analytic modeling of the phenomenon. This paper propose a formal framework to study the phenomenon in learning theory and make use of complex analysis and holomorphicity to offer a robust learning rule for artificial neural networks. With the help of complex analysis, we can effortlessly move between geometric and analytic perspectives of the phenomenon and offer further insights on the phenomenon by revealing its connection with harmonic functions. Using our model, we can explain some of the most intriguing characteristics of adversarial examples, including transferability of adversarial examples, and pave the way for novel approaches to mitigate the effects of the phenomenon.
Dynamically Relative Position Encoding-Based Transformer for Automatic Code Edit
Venue: arXiv cs.SE 2022
Year: 2022

Adapting Deep Learning (DL) techniques to automate non-trivial coding activities, such as code documentation and defect detection, has been intensively studied recently. Learning to predict code changes is one of the popular and essential investigations. Prior studies have shown that DL techniques such as Neural Machine Translation (NMT) can benefit meaningful code changes, including bug fixing and code refactoring. However, NMT models may encounter bottleneck when modeling long sequences, thus are limited in accurately predicting code changes. In this work, we design a Transformer-based approach, considering that Transformer has proven effective in capturing long-term dependencies. Specifically, we propose a novel model named DTrans. For better incorporating the local structure of code, i.e., statement-level information in this paper, DTrans is designed with dynamically relative position encoding in the multi-head attention of Transformer. Experiments on benchmark datasets demonstrate that DTrans can more accurately generate patches than the state-of-the-art methods, increasing the performance by at least 5.45\%-46.57\% in terms of the exact match metric on different datasets. Moreover, DTrans can locate the lines to change with 1.75\%-24.21\% higher accuracy than the existing methods.
Unequal Covariance Awareness for Fisher Discriminant Analysis and Its Variants in Classification
Venue: arXiv cs.LG 2022
Year: 2022

Fisher Discriminant Analysis (FDA) is one of the essential tools for feature extraction and classification. In addition, it motivates the development of many improved techniques based on the FDA to adapt to different problems or data types. However, none of these approaches make use of the fact that the assumption of equal covariance matrices in FDA is usually not satisfied in practical situations. Therefore, we propose a novel classification rule for the FDA that accounts for this fact, mitigating the effect of unequal covariance matrices in the FDA. Furthermore, since we only modify the classification rule, the same can be applied to many FDA variants, improving these algorithms further. Theoretical analysis reveals that the new classification rule allows the implicit use of the class covariance matrices while increasing the number of parameters to be estimated by a small amount compared to going from FDA to Quadratic Discriminant Analysis. We illustrate our idea via experiments, which show the superior performance of the modified algorithms based on our new classification rule compared to the original ones.
Block Ciphers Substitution Box Generation Based on Natural Randomness in Underwater Acoustics and Knights Tour Chain
Venue: arXiv cs.CR 2022
Year: 2022

The protection of confidential information is a global issue and block encryption algorithms are the most reliable option. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on Communication Theory of Secrecy Systems. block ciphers strictly follow the substitution and permutation principle to generate a ciphertext. The actual strength of the block ciphers against several attacks is entirely based on its substitution characteristic, which is gained by using the S-Box. In the current literature, algebraic structure-based and chaos-based techniques are highly used for the construction of S-boxes because both these techniques have favourable features for S-box construction, but also various attacks of these techniques have been identified. True randomness has been universally recognized as the ideal method for cipher primitives design because true random numbers are unpredictable, irreversible, and unreproducible. The basic concept of the proposed technique is the extraction of true random bits from underwater acoustic waves and to design a novel technique for the dynamic generation of S-boxes using the chain of knights tour. The proposed method satisfies all standard evaluation tests of S-boxes construction and true random numbers generation. Two million bits have been analyzed using the NIST randomness test suite, and the results show that underwater sound waves are an impeccable entropy source for true randomness. Additionally, our dynamically generated S-boxes have better or equal strength, over the latest published S-boxes (2020 to 2021). According to our knowledge first time, this type of research has been done, in which natural randomness of underwater acoustic waves has been used for the construction of block cipher's S-Box
Differentially Private Decoding in Large Language Models
Venue: arXiv cs.CL 2022
Year: 2022

Recent large-scale natural language processing (NLP) systems use a pre-trained Large Language Model (LLM) on massive and diverse corpora as a headstart. In practice, the pre-trained model is adapted to a wide array of tasks via fine-tuning on task-specific datasets. LLMs, while effective, have been shown to memorize instances of training data thereby potentially revealing private information processed during pre-training. The potential leakage might further propagate to the downstream tasks for which LLMs are fine-tuned. On the other hand, privacy-preserving algorithms usually involve retraining from scratch, which is prohibitively expensive for LLMs. In this work, we propose a simple, easy to interpret, and computationally lightweight perturbation mechanism to be applied to an already trained model at the decoding stage. Our perturbation mechanism is model-agnostic and can be used in conjunction with any LLM. We provide theoretical analysis showing that the proposed mechanism is differentially private, and experimental results showing a privacy-utility trade-off.
A Model Predictive Control Functional Continuous Time Bayesian Network for Self-Management of Multiple Chronic Conditions
Venue: arXiv cs.LG 2022
Year: 2022

Multiple chronic conditions (MCC) are one of the biggest challenges of modern times. The evolution of MCC follows a complex stochastic process that is influenced by a variety of risk factors, ranging from pre-existing conditions to modifiable lifestyle behavioral factors (e.g. diet, exercise habits, tobacco use, alcohol use, etc.) to non-modifiable socio-demographic factors (e.g., age, gender, education, marital status, etc.). People with MCC are at an increased risk of new chronic conditions and mortality. This paper proposes a model predictive control functional continuous time Bayesian network, an online recursive method to examine the impact of various lifestyle behavioral changes on the emergence trajectories of MCC and generate strategies to minimize the risk of progression of chronic conditions in individual patients. The proposed method is validated based on the Cameron county Hispanic cohort (CCHC) dataset, which has a total of 385 patients. The dataset examines the emergence of 5 chronic conditions (diabetes, obesity, cognitive impairment, hyperlipidemia, and hypertension) based on four modifiable risk factors representing lifestyle behaviors (diet, exercise habits, tobacco use, alcohol use) and four non-modifiable risk factors, including socio-demographic information (age, gender, education, marital status). The proposed method is tested under different scenarios (e.g., age group, the prior existence of MCC), demonstrating the effective intervention strategies for improving the lifestyle behavioral risk factors to offset MCC evolution.
Looking at Creative ML Blindspots with a Sociological Lens
Venue: arXiv cs.CY 2022
Year: 2022

How can researchers from the creative ML/AI community and sociology of culture engage in fruitful collaboration? How do researchers from both fields think (differently) about creativity and the production of creative work? While the ML community considers creativity as a matter of technical expertise and acumen, social scientists have emphasized the role of embeddedness in cultural production. This perspective aims to bridge both disciplines and proposes a conceptual and methodological toolkit for collaboration. We provide a systematic review of recent research in both fields and offer three perspectives around which to structure interdisciplinary research on cultural production: people, processes, and products. We thereby provide necessary grounding work to support multidisciplinary researchers to navigate conceptual and methodological hurdles in their collaboration. Our research will be of interest to ML researchers and sociologists interested in creativity that aim to conduct innovative research by bridging both fields.
Understanding Long Programming Languages with Structure-Aware Sparse Attention
Venue: arXiv cs.CL 2022
Year: 2022

Programming-based Pre-trained Language Models (PPLMs) such as CodeBERT have achieved great success in many downstream code-related tasks. Since the memory and computational complexity of self-attention in the Transformer grow quadratically with the sequence length, PPLMs typically limit the code length to 512. However, codes in real-world applications are generally long, such as code searches, which cannot be processed efficiently by existing PPLMs. To solve this problem, in this paper, we present SASA, a Structure-Aware Sparse Attention mechanism, which reduces the complexity and improves performance for long code understanding tasks. The key components in SASA are top-$k$ sparse attention and Abstract Syntax Tree (AST)-based structure-aware attention. With top-$k$ sparse attention, the most crucial attention relation can be obtained with a lower computational cost. As the code structure represents the logic of the code statements, which is a complement to the code sequence characteristics, we further introduce AST structures into attention. Extensive experiments on CodeXGLUE tasks show that SASA achieves better performance than the competing baselines.
Machine Learning-based Ransomware Detection Using Low-level Memory Access Patterns Obtained From Live-forensic Hypervisor
Venue: arXiv cs.CR 2022
Year: 2022

Since modern anti-virus software mainly depends on a signature-based static analysis, they are not suitable for coping with the rapid increase in malware variants. Moreover, even worse, many vulnerabilities of operating systems enable attackers to evade such protection mechanisms. We, therefore, developed a thin and lightweight live-forensic hypervisor to create an additional protection layer under a conventional protection layer of operating systems with supporting ransomware detection using dynamic behavioral features. The developed live-forensic hypervisor collects low-level memory access patterns instead of high-level information such as process IDs and API calls that modern Virtual Machine Introspection techniques have employed. We then created the low-level memory access patterns dataset of three ransomware samples, one wiper malware sample, and four benign applications. We confirmed that our best machine learning classifier using only low-level memory access patterns achieved an $F_1$ score of 0.95 in detecting ransomware and wiper malware.
kNN-Prompt: Nearest Neighbor Zero-Shot Inference
Venue: arXiv cs.CL 2022
Year: 2022

Retrieval-augmented language models (LMs) use non-parametric memory to substantially outperform their non-retrieval counterparts on perplexity-based evaluations, but it is an open question whether they achieve similar gains in few- and zero-shot end-task accuracy. We extensively study one such model, the k-nearest neighbor LM (kNN-LM), showing that the gains marginally transfer. The main challenge is to achieve coverage of the verbalizer tokens that define the different end-task class labels. To address this challenge, we also introduce kNN-Prompt, a simple and effective kNN-LM with automatically expanded fuzzy verbalizers (e.g. to expand terrible to also include silly and other task-specific synonyms for sentiment classification). Across nine diverse end-tasks, using kNN-Prompt with GPT-2 large yields significant performance boosts over strong zero-shot baselines (13.4% absolute improvement over the base LM on average). We also show that other advantages of non-parametric augmentation hold for end tasks; kNN-Prompt is effective for domain adaptation with no further training, and gains increase with the size of the retrieval model.
X-ViT: High Performance Linear Vision Transformer without Softmax
Venue: arXiv cs.CV 2022
Year: 2022

Vision transformers have become one of the most important models for computer vision tasks. Although they outperform prior works, they require heavy computational resources on a scale that is quadratic to the number of tokens, $N$. This is a major drawback of the traditional self-attention (SA) algorithm. Here, we propose the X-ViT, ViT with a novel SA mechanism that has linear complexity. The main approach of this work is to eliminate nonlinearity from the original SA. We factorize the matrix multiplication of the SA mechanism without complicated linear approximation. By modifying only a few lines of code from the original SA, the proposed models outperform most transformer-based models on image classification and dense prediction tasks on most capacity regimes.
Hide and Seek -- Preserving Location Privacy and Utility in the Remote Identification of Unmanned Aerial Vehicles
Venue: arXiv cs.CR 2022
Year: 2022

Due to the frequent unauthorized access by commercial drones to Critical Infrastructures (CIs) such as airports and oil refineries, the US-based Federal Avionics Administration (FAA) recently published a new specification, namely RemoteID. The aforementioned rule mandates that all Unmanned Aerial Vehicles (UAVs) have to broadcast information about their identity and location wirelessly to allow for immediate invasion attribution. However, the enforcement of such a rule poses severe concerns on UAV operators, especially in terms of location privacy and tracking threats, to name a few. Indeed, by simply eavesdropping on the wireless channel, an adversary could know the precise location of the UAV and track it, as well as obtaining sensitive information on path source and destination of the UAV. In this paper, we investigate the trade-off between location privacy and data utility that can be provided to UAVs when obfuscating the broadcasted location through differential privacy techniques. Leveraging the concept of Geo-Indistinguishability (Geo-Ind), already adopted in the context of Location-Based Services (LBS), we show that it is possible to enhance the privacy of the UAVs without preventing CI operators to timely detect unauthorized invasions. In particular, our experiments showed that when the location of an UAV is obfuscated with an average distance of 1.959 km, a carefully designed UAV detection system can detect 97.9% of invasions, with an average detection delay of 303.97 msec. The UAVs have to trade-off such enhanced location privacy with a non-negligible probability of false positives, i.e., being detected as invading while not really invading the no-fly zone. UAVs and CI operators can solve such ambiguous situations later on through the help of the FAA, being this latter the only one that can unveil the actual location of the UAV.
Adaptive Random Forests for Energy-Efficient Inference on Microcontrollers
Venue: arXiv cs.LG 2022
Year: 2022

Random Forests (RFs) are widely used Machine Learning models in low-power embedded devices, due to their hardware friendly operation and high accuracy on practically relevant tasks. The accuracy of a RF often increases with the number of internal weak learners (decision trees), but at the cost of a proportional increase in inference latency and energy consumption. Such costs can be mitigated considering that, in most applications, inputs are not all equally difficult to classify. Therefore, a large RF is often necessary only for (few) hard inputs, and wasteful for easier ones. In this work, we propose an early-stopping mechanism for RFs, which terminates the inference as soon as a high-enough classification confidence is reached, reducing the number of weak learners executed for easy inputs. The early-stopping confidence threshold can be controlled at runtime, in order to favor either energy saving or accuracy. We apply our method to three different embedded classification tasks, on a single-core RISC-V microcontroller, achieving an energy reduction from 38% to more than 90% with a drop of less than 0.5% in accuracy. We also show that our approach outperforms previous adaptive ML methods for RFs.
On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps
Venue: arXiv cs.LG 2022
Year: 2022

This paper presents consideration of the Semi-Relaxed Sinkhorn (SR-Sinkhorn) algorithm for the semi-relaxed optimal transport (SROT) problem, which relaxes one marginal constraint of the standard OT problem. For evaluation of how the constraint relaxation affects the algorithm behavior and solution, it is vitally necessary to present the theoretical convergence analysis in terms not only of the functional value gap, but also of the marginal constraint gap as well as the OT distance gap. However, no existing work has addressed all analyses simultaneously. To this end, this paper presents a comprehensive convergence analysis for SR-Sinkhorn. After presenting the $ε$-approximation of the functional value gap based on a new proof strategy and exploiting this proof strategy, we give the upper bound of the marginal constraint gap. We also provide its convergence to the $ε$-approximation when two distributions are in the probability simplex. Furthermore, the convergence analysis of the OT distance gap to the $ε$-approximation is given as assisted by the obtained marginal constraint gap. The latter two theoretical results are the first results presented in the literature related to the SROT problem.
Semeval-2022 Task 1: CODWOE -- Comparing Dictionaries and Word Embeddings
Venue: arXiv cs.CL 2022
Year: 2022

Word embeddings have advanced the state of the art in NLP across numerous tasks. Understanding the contents of dense neural representations is of utmost interest to the computational semantics community. We propose to focus on relating these opaque word vectors with human-readable definitions, as found in dictionaries. This problem naturally divides into two subtasks: converting definitions into embeddings, and converting embeddings into definitions. This task was conducted in a multilingual setting, using comparable sets of embeddings trained homogeneously.
How to Peel a Million: Validating and Expanding Bitcoin Clusters
Venue: arXiv cs.CR 2022
Year: 2022

One of the defining features of Bitcoin and the thousands of cryptocurrencies that have been derived from it is a globally visible transaction ledger. While Bitcoin uses pseudonyms as a way to hide the identity of its participants, a long line of research has demonstrated that Bitcoin is not anonymous. This has been perhaps best exemplified by the development of clustering heuristics, which have in turn given rise to the ability to track the flow of bitcoins as they are sent from one entity to another. In this paper, we design a new heuristic that is designed to track a certain type of flow, called a peel chain, that represents many transactions performed by the same entity; in doing this, we implicitly cluster these transactions and their associated pseudonyms together. We then use this heuristic to both validate and expand the results of existing clustering heuristics. We also develop a machine learning-based validation method and, using a ground-truth dataset, evaluate all our approaches and compare them with the state of the art. Ultimately, our goal is to not only enable more powerful tracking techniques but also call attention to the limits of anonymity in these systems.