OpenRaiser/Intern-Atlas huggingface dataset:
Heterogeneous Federated Learning via Grouped Sequential-to-Parallel Training
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) is a rapidly growing privacy-preserving collaborative machine learning paradigm. In practical FL applications, local data from each data silo reflect local usage patterns. Therefore, there exists heterogeneity of data distributions among data owners (a.k.a. FL clients). If not handled properly, this can lead to model performance degradation. This challenge has inspired the research field of heterogeneous federated learning, which currently remains open. In this paper, we propose a data heterogeneity-robust FL approach, FedGSP, to address this challenge by leveraging on a novel concept of dynamic Sequential-to-Parallel (STP) collaborative training. FedGSP assigns FL clients to homogeneous groups to minimize the overall distribution divergence among groups, and increases the degree of parallelism by reassigning more groups in each round. It is also incorporated with a novel Inter-Cluster Grouping (ICG) algorithm to assist in group assignment, which uses the centroid equivalence theorem to simplify the NP-hard grouping problem to make it solvable. Extensive experiments have been conducted on the non-i.i.d. FEMNIST dataset. The results show that FedGSP improves the accuracy by 3.7% on average compared with seven state-of-the-art approaches, and reduces the training time and communication overhead by more than 90%.
On Sub-optimality of Random Binning for Distributed Hypothesis Testing
Venue: arXiv cs.IT 2022
Year: 2022

We investigate the quantize and binning scheme, known as the Shimokawa-Han-Amari (SHA) scheme, for the distributed hypothesis testing. We develop tools to evaluate the critical rate attainable by the SHA scheme. For a product of binary symmetric double sources, we present a sequential scheme that improves upon the SHA scheme.
Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism
Venue: arXiv cs.DC 2022
Year: 2022

Nearest Neighbor Search (NNS) has recently drawn a rapid increase of interest due to its core role in managing high-dimensional vector data in data science and AI applications. The interest is fueled by the success of neural embedding, where deep learning models transform unstructured data into semantically correlated feature vectors for data analysis, e.g., recommend popular items. Among several categories of methods for fast NNS, similarity graph is one of the most successful algorithmic trends. Several of the most popular and top-performing similarity graphs, such as NSG and HNSW, at their core employ best-first traversal along the underlying graph indices to search near neighbors. Maximizing the performance of the search is essential for many tasks, especially at the large-scale and high-recall regime. In this work, we provide an in-depth examination of the challenges of the state-of-the-art similarity search algorithms, revealing its challenges in leveraging multi-core processors to speed up the search efficiency. We also exploit whether similarity graph search is robust to deviation from maintaining strict order by allowing multiple walkers to simultaneously advance the search frontier. Based on our insights, we propose Speed-ANN, a parallel similarity search algorithm that exploits hidden intra-query parallelism and memory hierarchy that allows similarity search to take advantage of multiple CPU cores to significantly accelerate search speed while achieving high accuracy. We evaluate Speed-ANN on a wide range of datasets, ranging from million to billion data points, and show its shorter query latency than NSG and HNSW, respectively. Besides, with multicore support, we show that our approach offers faster search latency than highly-optimized GPU implementation and provides good scalability as the increase of the number of hardware resources (e.g., CPU cores) and graph sizes.
Architectures for Protecting Cloud Data Planes
Venue: arXiv cs.CR 2022
Year: 2022

This paper explores three approaches for protecting cloud application data planes to prevent unauthorized access to the application and its data and to prevent unwanted data exfiltration. Through an exploration of various concrete security architectures, we focus on (1) Cloud Security Perimeters to provide a boundary around data and infrastructure in the cloud that provides a line of defense both to improper access to sensitive information and the exfiltration of that information, (2) Cloud Landing Points to provide a safe integration point between parts of your cloud applications and on-premises applications to communicate through, and (3) Zero Trust security architectures that are built on the principles of defense in depth and least-privilege access. Using these approaches together provides critical protection for services and applications as they transition from traditional on-premises network security to the Cloud security architectures, and then to potentially Zero Trust security architectures.
SZx: an Ultra-fast Error-bounded Lossy Compressor for Scientific Datasets
Venue: arXiv cs.DC 2022
Year: 2022

Today's scientific high performance computing (HPC) applications or advanced instruments are producing vast volumes of data across a wide range of domains, which introduces a serious burden on data transfer and storage. Error-bounded lossy compression has been developed and widely used in scientific community, because not only can it significantly reduce the data volumes but it can also strictly control the data distortion based on the use-specified error bound. Existing lossy compressors, however, cannot offer ultra-fast compression speed, which is highly demanded by quite a few applications or use-cases (such as in-memory compression and online instrument data compression). In this paper, we propose a novel ultra-fast error-bounded lossy compressor, which can obtain fairly high compression performance on both CPU and GPU, also with reasonably high compression ratios. The key contributions are three-fold: (1) We propose a novel, generic ultra-fast error-bounded lossy compression framework -- called UFZ, by confining our design to be composed of only super-lightweight operations such as bitwise and addition/subtraction operation, still keeping a certain high compression ratio. (2) We implement UFZ on both CPU and GPU and optimize the performance according to their architectures carefully. (3) We perform a comprehensive evaluation with 6 real-world production-level scientific datasets on both CPU and GPU. Experiments show that UFZ is 2~16X as fast as the second-fastest existing error-bounded lossy compressor (either SZ or ZFP) on CPU and GPU, with respect to both compression and decompression.
Glowing Experience or Bad Trip? A Quantitative Analysis of User Reported Drug Experiences on Erowid.org
Venue: arXiv cs.SI 2022
Year: 2022

Erowid.org is a website dedicated to documenting information about psychoactive substances, with over 36,000 user-submitted drug Experience Reports. We study the potential of these reports to provide information about characteristic experiences with drugs. First, we assess different kinds of drug experiences, such as 'addiction' or 'bad trips'. We quantitatively analyze how such experiences are related to substances and user variables. Furthermore, we classify positive and negative experiences as well as reported addiction using information about the consumer, substance, context and location of the drug experience. While variables based only on objective characteristics yield poor predictive performance for subjective experiences, we find subjective user reports can help to identify new patterns and impact factors on drug experiences. In particular, we found a positive association between addiction experiences and dextromethorphan, a substance with largely unknown withdrawal effects. Our research can help to gain a deeper sociological understanding of drug consumption and to identify relationships which may have clinical relevance. Moreover, it can show how non-mainstream social media platforms can be utilized to study characteristics of human behavior and how this can be done in an ethical way in collaboration with the platform providers.
Single Object Tracking: A Survey of Methods, Datasets, and Evaluation Metrics
Venue: arXiv cs.CV 2022
Year: 2022

Object tracking is one of the foremost assignments in computer vision that has numerous commonsense applications such as traffic monitoring, robotics, autonomous vehicle tracking, and so on. Different researches have been tried later a long time, but since of diverse challenges such as occlusion, illumination variations, fast motion, etc. researches in this area continues. In this paper, different strategies of the following objects are inspected and a comprehensive classification is displayed that classified the following strategies into four fundamental categories of feature-based, segmentation-based, estimation-based, and learning-based methods that each of which has its claim sub-categories. The most center of this paper is on learning-based strategies, which are classified into three categories of generative strategies, discriminative strategies, and reinforcement learning. One of the sub-categories of the discriminative show is deep learning. Since of high-performance, deep learning has as of late been exceptionally much consider. Finally, the different datasets and the evaluation methods that are most commonly used will be introduced.
Learning Representations of Entities and Relations
Venue: arXiv cs.LG 2022
Year: 2022

Encoding facts as representations of entities and binary relationships between them, as learned by knowledge graph representation models, is useful for various tasks, including predicting new facts, question answering, fact checking and information retrieval. The focus of this thesis is on (i) improving knowledge graph representation with the aim of tackling the link prediction task; and (ii) devising a theory on how semantics can be captured in the geometry of relation representations. Most knowledge graphs are very incomplete and manually adding new information is costly, which drives the development of methods which can automatically infer missing facts. The first contribution of this thesis is HypER, a convolutional model which simplifies and improves upon the link prediction performance of the existing convolutional state-of-the-art model ConvE and can be mathematically explained in terms of constrained tensor factorisation. The second contribution is TuckER, a relatively straightforward linear model, which, at the time of its introduction, obtained state-of-the-art link prediction performance across standard datasets. The third contribution is MuRP, first multi-relational graph representation model embedded in hyperbolic space. MuRP outperforms all existing models and its Euclidean counterpart MuRE in link prediction on hierarchical knowledge graph relations whilst requiring far fewer dimensions. Despite the development of a large number of knowledge graph representation models with gradually increasing predictive performance, relatively little is known of the latent structure they learn. We generalise recent theoretical understanding of how semantic relations of similarity, paraphrase and analogy are encoded in the geometric interactions of word embeddings to how more general relations, as found in knowledge graphs, can be encoded in their representations.
GADoT: GAN-based Adversarial Training for Robust DDoS Attack Detection
Venue: arXiv cs.CR 2022
Year: 2022

Machine Learning (ML) has proven to be effective in many application domains. However, ML methods can be vulnerable to adversarial attacks, in which an attacker tries to fool the classification/prediction mechanism by crafting the input data. In the case of ML-based Network Intrusion Detection Systems (NIDSs), the attacker might use their knowledge of the intrusion detection logic to generate malicious traffic that remains undetected. One way to solve this issue is to adopt adversarial training, in which the training set is augmented with adversarial traffic samples. This paper presents an adversarial training approach called GADoT, which leverages a Generative Adversarial Network (GAN) to generate adversarial DDoS samples for training. We show that a state-of-the-art NIDS with high accuracy on popular datasets can experience more than 60% undetected malicious flows under adversarial attacks. We then demonstrate how this score drops to 1.8% or less after adversarial training using GADoT.
partitura: A Python Package for Handling Symbolic Musical Data
Venue: arXiv cs.SD 2022
Year: 2022

This demo paper introduces partitura, a Python package for handling symbolic musical information. The principal aim of this package is to handle richly structured musical information as conveyed by modern staff music notation. It provides a much wider range of possibilities to deal with music than the more reductive (but very common) piano roll-oriented approach inspired by the MIDI standard. The package is an open source project and is available on GitHub.
FEN-Hedonic Games with Distance-Based Preferences
Venue: arXiv cs.GT 2022
Year: 2022

Hedonic games formalize coalition formation scenarios where players evaluate an outcome based on the coalition they are contained in. Due to a large number of possible coalitions, compact representations of these games are crucial. We complement known compact representation models by a distance-based approach: Players' preferences are encoded in a bipolar manner by ordinal preferences over a small set of known neighbouring players, coalitions are represented by adequate preference orders from a player's perspective, and preferences over coalitions are extended based on a directed form of Hausdorff-Kendall-tau distance between individual preferences and coalitions. We show that this model satisfies desirable axiomatic properties and has reasonable computational complexity in terms of selected individual-based stability notions.
AnyCall: Fast and Flexible System-Call Aggregation
Venue: arXiv cs.CR 2022
Year: 2022

Operating systems rely on system calls to allow the controlled communication of isolated processes with the kernel and other processes. Every system call includes a processor mode switch from the unprivileged user mode to the privileged kernel mode. Although processor mode switches are the essential isolation mechanism to guarantee the system's integrity, they induce direct and indirect performance costs as they invalidate parts of the processor state. In recent years, high-performance networks and storage hardware has made the user/kernel transition overhead the bottleneck for IO-heavy applications. To make matters worse, security vulnerabilities in modern processors (e.g., Meltdown) have prompted kernel mitigations that further increase the transition overhead. To decouple system calls from user/kernel transitions we propose AnyCall, which uses an in-kernel compiler to execute safety-checked user bytecode in kernel mode. This allows for very fast system calls interleaved with error checking and processing logic using only a single user/kernel transition. We have implemented AnyCall based on the Linux kernel's eBPF subsystem. Our evaluation demonstrates that system call bursts are up to 55 times faster using AnyCall and that real-world applications can be sped up by 24% even if only a minimal part of their code is run by AnyCall.
Memory-Efficient Backpropagation through Large Linear Layers
Venue: arXiv cs.LG 2022
Year: 2022

In modern neural networks like Transformers, linear layers require significant memory to store activations during backward pass. This study proposes a memory reduction approach to perform backpropagation through linear layers. Since the gradients of linear layers are computed by matrix multiplications, we consider methods for randomized matrix multiplications and demonstrate that they require less memory with a moderate decrease of the test accuracy. Also, we investigate the variance of the gradient estimate induced by the randomized matrix multiplication. We compare this variance with the variance coming from gradient estimation based on the batch of samples. We demonstrate the benefits of the proposed method on the fine-tuning of the pre-trained RoBERTa model on GLUE tasks.
Online Assessment Misconduct Detection using Internet Protocol and Behavioural Classification
Venue: arXiv cs.CY 2022
Year: 2022

With the recent prevalence of remote education, academic assessments are often conducted online, leading to further concerns surrounding assessment misconducts. This paper investigates the potentials of online assessment misconduct (e-cheating) and proposes practical countermeasures against them. The mechanism for detecting the practices of online cheating is presented in the form of an e-cheating intelligent agent, comprising of an internet protocol (IP) detector and a behavioural monitor. The IP detector is an auxiliary detector which assigns randomised and unique assessment sets as an early procedure to reduce potential misconducts. The behavioural monitor scans for irregularities in assessment responses from the candidates, further reducing any misconduct attempts. This is highlighted through the proposal of the DenseLSTM using a deep learning approach. Additionally, a new PT Behavioural Database is presented and made publicly available. Experiments conducted on this dataset confirm the effectiveness of the DenseLSTM, resulting in classification accuracies of up to 90.7%.
A Proof Procedure For Separation Logic With Inductive Definitions and Theory Reasoning
Venue: arXiv cs.LO 2022
Year: 2022

A proof procedure, in the spirit of the sequent calculus, is proposed to check the validity of entailments between Separation Logic formulas combining inductively defined predicates denoted structures of bounded tree width and theory reasoning. The calculus is sound and complete, in the sense that a sequent is valid iff it admits a (possibly infinite) proof tree. We show that the procedure terminates in the two following cases: (i) When the inductive rules that define the predicates occurring on the left-hand side of the entailment terminate, in which case the proof tree is always finite. (ii) When the theory is empty, in which case every valid sequent admits a rational proof tree, where the total number of pairwise distinct sequents occurring in the proof tree is doubly exponential w.r.t.\ the size of the end-sequent.
POTATO: exPlainable infOrmation exTrAcTion framewOrk
Venue: arXiv cs.CL 2022
Year: 2022

We present POTATO, a task- and languageindependent framework for human-in-the-loop (HITL) learning of rule-based text classifiers using graph-based features. POTATO handles any type of directed graph and supports parsing text into Abstract Meaning Representations (AMR), Universal Dependencies (UD), and 4lang semantic graphs. A streamlit-based user interface allows users to build rule systems from graph patterns, provides real-time evaluation based on ground truth data, and suggests rules by ranking graph features using interpretable machine learning models. Users can also provide patterns over graphs using regular expressions, and POTATO can recommend refinements of such rules. POTATO is applied in projects across domains and languages, including classification tasks on German legal text and English social media data. All components of our system are written in Python, can be installed via pip, and are released under an MIT License on GitHub.
Metrics for saliency map evaluation of deep learning explanation methods
Venue: arXiv cs.CV 2022
Year: 2022

Due to the black-box nature of deep learning models, there is a recent development of solutions for visual explanations of CNNs. Given the high cost of user studies, metrics are necessary to compare and evaluate these different methods. In this paper, we critically analyze the Deletion Area Under Curve (DAUC) and Insertion Area Under Curve (IAUC) metrics proposed by Petsiuk et al. (2018). These metrics were designed to evaluate the faithfulness of saliency maps generated by generic methods such as Grad-CAM or RISE. First, we show that the actual saliency score values given by the saliency map are ignored as only the ranking of the scores is taken into account. This shows that these metrics are insufficient by themselves, as the visual appearance of a saliency map can change significantly without the ranking of the scores being modified. Secondly, we argue that during the computation of DAUC and IAUC, the model is presented with images that are out of the training distribution which might lead to an unreliable behavior of the model being explained. To complement DAUC/IAUC, we propose new metrics that quantify the sparsity and the calibration of explanation methods, two previously unstudied properties. Finally, we give general remarks about the metrics studied in this paper and discuss how to evaluate them in a user study.
On scale-invariant properties in natural images and their simulations
Venue: arXiv cs.CV 2022
Year: 2022

We study samples of natural images for which a set of statistical characteristics is computed and scale-invariant properties of samples are demonstrated computationally. Computations of the power spectrum are carried out and a power-law decaying power spectrum is observed on samples taken from van Hateren images of natural scenes. We propose a dynamic model to reproduce the observed slope in the power spectrum qualitatively. For two types of sources for this model the behaviour of power spectrum is investigated and scale-invariance confirmed numerically. We then discuss potential applications of scale-invariant properties of natural images.
Efficiently Maintaining Next Basket Recommendations under Additions and Deletions of Baskets and Items
Venue: arXiv cs.IR 2022
Year: 2022

Recommender systems play an important role in helping people find information and make decisions in today's increasingly digitalized societies. However, the wide adoption of such machine learning applications also causes concerns in terms of data privacy. These concerns are addressed by the recent "General Data Protection Regulation" (GDPR) in Europe, which requires companies to delete personal user data upon request when users enforce their "right to be forgotten". Many researchers argue that this deletion obligation does not only apply to the data stored in primary data stores such as relational databases but also requires an update of machine learning models whose training set included the personal data to delete. We explore this direction in the context of a sequential recommendation task called Next Basket Recommendation (NBR), where the goal is to recommend a set of items based on a user's purchase history. We design efficient algorithms for incrementally and decrementally updating a state-of-the-art next basket recommendation model in response to additions and deletions of user baskets and items. Furthermore, we discuss an efficient, data-parallel implementation of our method in the Spark Structured Streaming system. We evaluate our implementation on a variety of real-world datasets, where we investigate the impact of our update techniques on several ranking metrics and measure the time to perform model updates. Our results show that our method provides constant update time efficiency with respect to an additional user basket in the incremental case, and linear efficiency in the decremental case where we delete existing baskets. With modest computational resources, we are able to update models with a latency of around 0.2~milliseconds regardless of the history size in the incremental case, and less than one millisecond in the decremental case.