OpenRaiser/Intern-Atlas huggingface dataset:
Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
Venue: arXiv cs.MA 2023
Year: 2023

Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem arising in multi-agent systems with a wide range of applications. The problem's intractability has led to extensive research on improving the scalability of solvers for it. Since optimal solvers can struggle to scale, a major challenge that arises is understanding what makes MAPF hard. We tackle this challenge through a fine-grained complexity analysis of time-optimal MAPF on 2D grids, thereby closing two gaps and identifying a new tractability frontier. First, we show that 2-colored MAPF, i.e., where the agents are divided into two teams, each with its own set of targets, remains NP-hard. Second, for the flowtime objective (also called sum-of-costs), we show that it remains NP-hard to find a solution in which agents have an individually optimal cost, which we call an individually optimal solution. The previously tightest results for these MAPF variants are for (non-grid) planar graphs. We use a single hardness construction that replaces, strengthens, and unifies previous proofs. We believe that it is also simpler than previous proofs for the planar case as it employs minimal gadgets that enable its full visualization in one figure. Finally, for the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in. Namely, we complement our hardness result, which holds for three directions, with an efficient algorithm for finding an individually optimal solution if only two directions are allowed. This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem.
Securing Deep Generative Models with Universal Adversarial Signature
Venue: arXiv cs.CV 2023
Year: 2023

Recent advances in deep generative models have led to the development of methods capable of synthesizing high-quality, realistic images. These models pose threats to society due to their potential misuse. Prior research attempted to mitigate these threats by detecting generated images, but the varying traces left by different generative models make it challenging to create a universal detector capable of generalizing to new, unseen generative models. In this paper, we propose to inject a universal adversarial signature into an arbitrary pre-trained generative model, in order to make its generated contents more detectable and traceable. First, the imperceptible optimal signature for each image can be found by a signature injector through adversarial training. Subsequently, the signature can be incorporated into an arbitrary generator by fine-tuning it with the images processed by the signature injector. In this way, the detector corresponding to the signature can be reused for any fine-tuned generator for tracking the generator identity. The proposed method is validated on the FFHQ and ImageNet datasets with various state-of-the-art generative models, consistently showing a promising detection rate. Code will be made publicly available at \url{https://github.com/zengxianyu/genwm}.
Image as First-Order Norm+Linear Autoregression: Unveiling Mathematical Invariance
Venue: arXiv cs.CV 2023
Year: 2023

This paper introduces a novel mathematical property applicable to diverse images, referred to as FINOLA (First-Order Norm+Linear Autoregressive). FINOLA represents each image in the latent space as a first-order autoregressive process, in which each regression step simply applies a shared linear model on the normalized value of its immediate neighbor. This intriguing property reveals a mathematical invariance that transcends individual images. Expanding from image grids to continuous coordinates, we unveil the presence of two underlying partial differential equations. We validate the FINOLA property from two distinct angles: image reconstruction and self-supervised learning. Firstly, we demonstrate the ability of FINOLA to auto-regress up to a 256x256 feature map (the same resolution to the image) from a single vector placed at the center, successfully reconstructing the original image by only using three 3x3 convolution layers as decoder. Secondly, we leverage FINOLA for self-supervised learning by employing a simple masked prediction approach. Encoding a single unmasked quadrant block, we autoregressively predict the surrounding masked region. Remarkably, this pre-trained representation proves highly effective in image classification and object detection tasks, even when integrated into lightweight networks, all without the need for extensive fine-tuning. The code will be made publicly available.
Detecting Concept Drift for the reliability prediction of Software Defects using Instance Interpretation
Venue: arXiv cs.SE 2023
Year: 2023

In the context of Just-In-Time Software Defect Prediction (JIT-SDP), Concept drift (CD) can occur due to changes in the software development process, the complexity of the software, or changes in user behavior that may affect the stability of the JIT-SDP model over time. Additionally, the challenge of class imbalance in JIT-SDP data poses a potential risk to the accuracy of CD detection methods if rebalancing is implemented. This issue has not been explored to the best of our knowledge. Furthermore, methods to check the stability of JIT-SDP models over time by considering labeled evaluation data have been proposed. However, it should be noted that future data labels may not always be available promptly. We aim to develop a reliable JIT-SDP model using CD point detection directly by identifying changes in the interpretation of unlabeled simplified and resampled data. To evaluate our approach, we first obtained baseline methods based on model performance monitoring to identify CD points on labeled data. We then compared the output of the proposed methods with baseline methods based on performance monitoring of threshold-dependent and threshold-independent criteria using well-known performance measures in CD detection methods, such as accuracy, MDR, MTD, MTFA, and MTR. We also utilize the Friedman statistical test to assess the effectiveness of our approach. As a result, our proposed methods show higher compatibility with baseline methods based on threshold-independent criteria when applied to rebalanced data, and with baseline methods based on threshold-dependent criteria when applied to simple data.
Segmented Recurrent Transformer: An Efficient Sequence-to-Sequence Model
Venue: arXiv cs.CL 2023
Year: 2023

Transformers have shown dominant performance across a range of domains including language and vision. However, their computational cost grows quadratically with the sequence length, making their usage prohibitive for resource-constrained applications. To counter this, our approach is to divide the whole sequence into segments and apply attention to the individual segments. We propose a segmented recurrent transformer (SRformer) that combines segmented (local) attention with recurrent attention. The loss caused by reducing the attention window length is compensated by aggregating information across segments with recurrent attention. SRformer leverages Recurrent Accumulate-and-Fire (RAF) neurons' inherent memory to update the cumulative product of keys and values. The segmented attention and lightweight RAF neurons ensure the efficiency of the proposed transformer. Such an approach leads to models with sequential processing capability at a lower computation/memory cost. We apply the proposed method to T5 and BART transformers. The modified models are tested on summarization datasets including CNN-dailymail, XSUM, ArXiv, and MediaSUM. Notably, using segmented inputs of varied sizes, the proposed model achieves $6-22\%$ higher ROUGE1 scores than a segmented transformer and outperforms other recurrent transformer approaches. Furthermore, compared to full attention, the proposed model reduces the computational complexity of cross attention by around $40\%$.
An Experimental Investigation into the Evaluation of Explainability Methods
Venue: arXiv cs.LG 2023
Year: 2023

EXplainable Artificial Intelligence (XAI) aims to help users to grasp the reasoning behind the predictions of an Artificial Intelligence (AI) system. Many XAI approaches have emerged in recent years. Consequently, a subfield related to the evaluation of XAI methods has gained considerable attention, with the aim to determine which methods provide the best explanation using various approaches and criteria. However, the literature lacks a comparison of the evaluation metrics themselves, that one can use to evaluate XAI methods. This work aims to fill this gap by comparing 14 different metrics when applied to nine state-of-the-art XAI methods and three dummy methods (e.g., random saliency maps) used as references. Experimental results show which of these metrics produces highly correlated results, indicating potential redundancy. We also demonstrate the significant impact of varying the baseline hyperparameter on the evaluation metric values. Finally, we use dummy methods to assess the reliability of metrics in terms of ranking, pointing out their limitations.
FIDS: Fuzzy Intrusion Detection System for simultaneous detection of DoS/DDoS attacks in Cloud computing
Venue: arXiv cs.CR 2023
Year: 2023

In recent times, I've encountered a principle known as cloud computing, a model that simplifies user access to data and computing power on a demand basis. The main objective of cloud computing is to accommodate users' growing needs by decreasing dependence on human resources, minimizing expenses, and enhancing the speed of data access. Nevertheless, preserving security and privacy in cloud computing systems pose notable challenges. This issue arises because these systems have a distributed structure, which is susceptible to unsanctioned access - a fundamental problem. In the context of cloud computing, the provision of services on demand makes them targets for common assaults like Denial of Service (DoS) attacks, which include Economic Denial of Sustainability (EDoS) and Distributed Denial of Service (DDoS). These onslaughts can be classified into three categories: bandwidth consumption attacks, specific application attacks, and connection layer attacks. Most of the studies conducted in this arena have concentrated on a singular type of attack, with the concurrent detection of multiple DoS attacks often overlooked. This article proposes a suitable method to identify four types of assaults: HTTP, Database, TCP SYN, and DNS Flood. The aim is to present a universal algorithm that performs effectively in detecting all four attacks instead of using separate algorithms for each one. In this technique, seventeen server parameters like memory usage, CPU usage, and input/output counts are extracted and monitored for changes, identifying the failure point using the CUSUM algorithm to calculate the likelihood of each attack. Subsequently, a fuzzy neural network is employed to determine the occurrence of an attack. When compared to the Snort software, the proposed method's results show a significant improvement in the average detection rate, jumping from 57% to 95%.
Automatic Extraction of Time-windowed ROS Computation Graphs from ROS Bag Files
Venue: arXiv cs.RO 2023
Year: 2023

Robotic systems react to different environmental stimuli, potentially resulting in the dynamic reconfiguration of the software controlling such systems. One effect of such dynamism is the reconfiguration of the software architecture reconfiguration of the system at runtime. Such reconfigurations might severely impact the runtime properties of robotic systems, e.g., in terms of performance and energy efficiency. The ROS \emph{rosbag} package enables developers to record and store timestamped data related to the execution of robotic missions, implicitly containing relevant information about the architecture of the monitored system during its execution. In this study, we discuss about our approach for statically extracting (time-windowed) architectural information from ROS bag files. The proposed approach can support the robotics community in better discussing and reasoning the software architecture (and its runtime reconfigurations) of ROS-based systems. We evaluate our approach against hundreds of ROS bag files systematically mined from 4,434 public GitHub repositories.
Optimizations for a Current-Controlled Memristor-based Neuromorphic Synapse Design
Venue: arXiv cs.ET 2023
Year: 2023

The synapse is a key element of neuromorphic computing in terms of efficiency and accuracy. In this paper, an optimized current-controlled memristive synapse circuit is proposed. Our proposed synapse demonstrates reliability in the face of process variation and the inherent stochastic behavior of memristors. Up to an 82% energy optimization can be seen during the SET operation over prior work. In addition, the READ process shows up to 54% energy savings. Our current-controlled approach also provides more reliable programming over traditional programming methods. This design is demonstrated with a 4-bit memory precision configuration. Using a spiking neural network (SNN), a neuromorphic application analysis was performed with this precision configuration. Our optimized design showed up to 82% improvement in control applications and a 2.7x improvement in classification applications compared with other design cases.
Not wacky vs. definitely wacky: A study of scalar adverbs in pretrained language models
Venue: arXiv cs.CL 2023
Year: 2023

Vector space models of word meaning all share the assumption that words occurring in similar contexts have similar meanings. In such models, words that are similar in their topical associations but differ in their logical force tend to emerge as semantically close, creating well-known challenges for NLP applications that involve logical reasoning. Modern pretrained language models, such as BERT, RoBERTa and GPT-3 hold the promise of performing better on logical tasks than classic static word embeddings. However, reports are mixed about their success. In the current paper, we advance this discussion through a systematic study of scalar adverbs, an under-explored class of words with strong logical force. Using three different tasks, involving both naturalistic social media data and constructed examples, we investigate the extent to which BERT, RoBERTa, GPT-2 and GPT-3 exhibit general, human-like, knowledge of these common words. We ask: 1) Do the models distinguish amongst the three semantic categories of MODALITY, FREQUENCY and DEGREE? 2) Do they have implicit representations of full scales from maximally negative to maximally positive? 3) How do word frequency and contextual factors impact model performance? We find that despite capturing some aspects of logical meaning, the models fall far short of human performance.
Representation Transfer Learning via Multiple Pre-trained models for Linear Regression
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we consider the problem of learning a linear regression model on a data domain of interest (target) given few samples. To aid learning, we are provided with a set of pre-trained regression models that are trained on potentially different data domains (sources). Assuming a representation structure for the data generating linear models at the sources and the target domains, we propose a representation transfer based learning method for constructing the target model. The proposed scheme is comprised of two phases: (i) utilizing the different source representations to construct a representation that is adapted to the target data, and (ii) using the obtained model as an initialization to a fine-tuning procedure that re-trains the entire (over-parameterized) regression model on the target data. For each phase of the training method, we provide excess risk bounds for the learned model compared to the true data generating target model. The derived bounds show a gain in sample complexity for our proposed method compared to the baseline method of not leveraging source representations when achieving the same excess risk, therefore, theoretically demonstrating the effectiveness of transfer learning for linear regression.
Investigation of UAV Detection in Images with Complex Backgrounds and Rainy Artifacts
Venue: arXiv cs.CV 2023
Year: 2023

To detect unmanned aerial vehicles (UAVs) in real-time, computer vision and deep learning approaches are evolving research areas. Interest in this problem has grown due to concerns regarding the possible hazards and misuse of employing UAVs in many applications. These include potential privacy violations. To address the concerns, vision-based object detection methods have been developed for UAV detection. However, UAV detection in images with complex backgrounds and weather artifacts like rain has yet to be reasonably studied. Hence, for this purpose, we prepared two training datasets. The first dataset has the sky as its background and is called the Sky Background Dataset (SBD). The second training dataset has more complex scenes (with diverse backgrounds) and is named the Complex Background Dataset (CBD). Additionally, two test sets were prepared: one containing clear images and the other with images with three rain artifacts, named the Rainy Test Set (RTS). This work also focuses on benchmarking state-of-the-art object detection models, and to the best of our knowledge, it is the first to investigate the performance of recent and popular vision-based object detection methods for UAV detection under challenging conditions such as complex backgrounds, varying UAV sizes, and low-to-heavy rainy conditions. The findings presented in the paper shall help provide insights concerning the performance of the selected models for UAV detection under challenging conditions and pave the way to develop more robust UAV detection methods. The codes and datasets are available at: https://github.com/AdnanMunir294/UAVD-CBRA.
Metaheuristic planner for cooperative multi-agent wall construction with UAVs
Venue: arXiv cs.RO 2023
Year: 2023

This paper introduces a wall construction planner for Unmanned Aerial Vehicles (UAVs), which uses a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic to generate near-time-optimal building plans for even large walls within seconds. This approach addresses one of the most time-consuming and labor-intensive tasks, while also minimizing workers' safety risks. To achieve this, the wall-building problem is modeled as a variant of the Team Orienteering Problem and is formulated as Mixed-Integer Linear Programming (MILP), with added precedence and concurrence constraints that ensure bricks are built in the correct order and without collision between cooperating agents. The GRASP planner is validated in a realistic simulation and demonstrated to find solutions with similar quality as the optimal MILP, but much faster. Moreover, it outperforms all other state-of-the-art planning approaches in the majority of test cases. This paper presents a significant advancement in the field of automated wall construction, demonstrating the potential of UAVs and optimization algorithms in improving the efficiency and safety of construction projects.
Efficient Computation of Quantiles over Joins
Venue: arXiv cs.DB 2023
Year: 2023

We present efficient algorithms for Quantile Join Queries, abbreviated as %JQ. A %JQ asks for the answer at a specified relative position (e.g., 50% for the median) under some ordering over the answers to a Join Query (JQ). Our goal is to avoid materializing the set of all join answers, and to achieve quasilinear time in the size of the database, regardless of the total number of answers. A recent dichotomy result rules out the existence of such an algorithm for a general family of queries and orders. Specifically, for acyclic JQs without self-joins, the problem becomes intractable for ordering by sum whenever we join more than two relations (and these joins are not trivial intersections). Moreover, even for basic ranking functions beyond sum, such as min or max over different attributes, so far it is not known whether there is any nontrivial tractable %JQ. In this work, we develop a new approach to solving %JQ. Our solution uses two subroutines: The first one needs to select what we call a "pivot answer". The second subroutine partitions the space of query answers according to this pivot, and continues searching in one partition that is represented as new %JQ over a new database. For pivot selection, we develop an algorithm that works for a large class of ranking functions that are appropriately monotone. The second subroutine requires a customized construction for the specific ranking function at hand. We show the benefit and generality of our approach by using it to establish several new complexity results. First, we prove the tractability of min and max for all acyclic JQs, thereby resolving the above question. Second, we extend the previous %JQ dichotomy for sum to all partial sums. Third, we handle the intractable cases of sum by devising a deterministic approximation scheme that applies to every acyclic JQ.
Unsupervised Embedding Quality Evaluation
Venue: arXiv cs.LG 2023
Year: 2023

Unsupervised learning has recently significantly gained in popularity, especially with deep learning-based approaches. Despite numerous successes and approaching supervised-level performance on a variety of academic benchmarks, it is still hard to train and evaluate SSL models in practice due to the unsupervised nature of the problem. Even with networks trained in a supervised fashion, it is often unclear whether they will perform well when transferred to another domain. Past works are generally limited to assessing the amount of information contained in embeddings, which is most relevant for self-supervised learning of deep neural networks. This works chooses to follow a different approach: can we quantify how easy it is to linearly separate the data in a stable way? We survey the literature and uncover three methods that could be potentially used for evaluating quality of representations. We also introduce one novel method based on recent advances in understanding the high-dimensional geometric structure of self-supervised learning. We conduct extensive experiments and study the properties of these metrics and ones introduced in the previous work. Our results suggest that while there is no free lunch, there are metrics that can robustly estimate embedding quality in an unsupervised way.
An Investigation of Noise in Morphological Inflection
Venue: arXiv cs.CL 2023
Year: 2023

With a growing focus on morphological inflection systems for languages where high-quality data is scarce, training data noise is a serious but so far largely ignored concern. We aim at closing this gap by investigating the types of noise encountered within a pipeline for truly unsupervised morphological paradigm completion and its impact on morphological inflection systems: First, we propose an error taxonomy and annotation pipeline for inflection training data. Then, we compare the effect of different types of noise on multiple state-of-the-art inflection models. Finally, we propose a novel character-level masked language modeling (CMLM) pretraining objective and explore its impact on the models' resistance to noise. Our experiments show that various architectures are impacted differently by separate types of noise, but encoder-decoders tend to be more robust to noise than models trained with a copy bias. CMLM pretraining helps transformers, but has lower impact on LSTMs.