OpenRaiser/Intern-Atlas huggingface dataset:
Rank Resilience of Pattern Matrices against Structured Perturbations with Applications
Venue: arXiv cs.IT 2024
Year: 2024

In structured system theory, a pattern matrix is a matrix with entries either fixed to zero or free to take arbitrary numbers. The (generic) rank of a pattern matrix is the rank of almost all its realizations. The resilience of various system properties is closely tied to the rank resilience of the corresponding pattern matrices. Yet, existing literature predominantly explores the latter aspect by focusing on perturbations that change the zero-nonzero structure of pattern matrices, corresponding to link additions/deletions. In this paper, we consider the rank resilience of pattern matrices against structured perturbations that can arbitrarily alter the values of a prescribed set of entries, corresponding to link weight variations. We say a pattern matrix is structurally rank $r$ resilient against a perturbation pattern if almost all realizations of this pattern matrix have a rank not less than $r$ under arbitrary complex-valued realizations of the perturbation pattern. We establish a generic property in this concept. We then present combinatorial necessary and sufficient conditions for a rectangular pattern matrix to lose full rank under given perturbation patterns. We also generalize them to obtain a sufficient condition and a necessary one for losing an arbitrarily prescribed rank. We finally show our results can be applied to the resilience analysis of various properties of structured (descriptor) systems, including controllability and input-state observability, as well as characterizing zero structurally fixed modes.
Mixed Policy Gradient: off-policy reinforcement learning driven jointly by data and model
Venue: arXiv cs.LG 2024
Year: 2024

Reinforcement learning (RL) shows great potential in sequential decision-making. At present, mainstream RL algorithms are data-driven, which usually yield better asymptotic performance but much slower convergence compared with model-driven methods. This paper proposes mixed policy gradient (MPG) algorithm, which fuses the empirical data and the transition model in policy gradient (PG) to accelerate convergence without performance degradation. Formally, MPG is constructed as a weighted average of the data-driven and model-driven PGs, where the former is the derivative of the learned Q-value function, and the latter is that of the model-predictive return. To guide the weight design, we analyze and compare the upper bound of each PG error. Relying on that, a rule-based method is employed to heuristically adjust the weights. In particular, to get a better PG, the weight of the data-driven PG is designed to grow along the learning process while the other to decrease. Simulation results show that the MPG method achieves the best asymptotic performance and convergence speed compared with other baseline algorithms.
Emerging Trends in Federated Learning: From Model Fusion to Federated X Learning
Venue: arXiv cs.LG 2024
Year: 2024

Federated learning is a new learning paradigm that decouples data collection and model training via multi-party computation and model aggregation. As a flexible learning setting, federated learning has the potential to integrate with other learning frameworks. We conduct a focused survey of federated learning in conjunction with other learning algorithms. Specifically, we explore various learning algorithms to improve the vanilla federated averaging algorithm and review model fusion methods such as adaptive aggregation, regularization, clustered methods, and Bayesian methods. Following the emerging trends, we also discuss federated learning in the intersection with other learning paradigms, termed federated X learning, where X includes multitask learning, meta-learning, transfer learning, unsupervised learning, and reinforcement learning. In addition to reviewing state-of-the-art studies, this paper also identifies key challenges and applications in this field, while also highlighting promising future directions.
Learning to Extend Molecular Scaffolds with Structural Motifs
Venue: arXiv cs.LG 2024
Year: 2024

Recent advancements in deep learning-based modeling of molecules promise to accelerate in silico drug discovery. A plethora of generative models is available, building molecules either atom-by-atom and bond-by-bond or fragment-by-fragment. However, many drug discovery projects require a fixed scaffold to be present in the generated molecule, and incorporating that constraint has only recently been explored. Here, we propose MoLeR, a graph-based model that naturally supports scaffolds as initial seed of the generative procedure, which is possible because it is not conditioned on the generation history. Our experiments show that MoLeR performs comparably to state-of-the-art methods on unconstrained molecular optimization tasks, and outperforms them on scaffold-based tasks, while being an order of magnitude faster to train and sample from than existing approaches. Furthermore, we show the influence of a number of seemingly minor design choices on the overall performance.
Deep Learning Based 3D Segmentation: A Survey
Venue: arXiv cs.CV 2024
Year: 2024

3D segmentation is a fundamental and challenging problem in computer vision with applications in autonomous driving and robotics. It has received significant attention from the computer vision, graphics and machine learning communities. Conventional methods for 3D segmentation, based on hand-crafted features and machine learning classifiers, lack generalization ability. Driven by their success in 2D computer vision, deep learning techniques have recently become the tool of choice for 3D segmentation tasks. This has led to an influx of many methods in the literature that have been evaluated on different benchmark datasets. Whereas survey papers on RGB-D and point cloud segmentation exist, there is a lack of a recent in-depth survey that covers all 3D data modalities and application domains. This paper fills the gap and comprehensively surveys the recent progress in deep learning-based 3D segmentation techniques. We cover over 220 works from the last six years, analyze their strengths and limitations, and discuss their competitive results on benchmark datasets. The survey provides a summary of the most commonly used pipelines and finally highlights promising research directions for the future.
Reaching Agreement in Competitive Microbial Systems
Venue: arXiv cs.DC 2024
Year: 2024

We study distributed agreement in microbial distributed systems under stochastic population dynamics and competitive interactions. Motivated by recent applications in synthetic biology, we examine how the presence and absence of direct competition among microbial species influences their ability to reach majority consensus. In this problem, two species are designated as input species, and the goal is to guarantee that eventually only the input species which had the highest initial count prevails. We show that direct competition dynamics reach majority consensus with high probability even when the initial gap between the species is small, i.e., $Ω(\sqrt{n\log n})$, where $n$ is the initial population size. In contrast, we show that absence of direct competition is not robust: solving majority consensus with constant probability requires a large initial gap of $Ω(n)$. To corroborate our analytical results, we use simulations to show that these consensus dynamics occur within practical biological time scales.
Partial Differential Equations is All You Need for Generating Neural Architectures -- A Theory for Physical Artificial Intelligence Systems
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we generalize the reaction-diffusion equation in statistical physics, Schrödinger equation in quantum mechanics, Helmholtz equation in paraxial optics into the neural partial differential equations (NPDE), which can be considered as the fundamental equations in the field of artificial intelligence research. We take finite difference method to discretize NPDE for finding numerical solution, and the basic building blocks of deep neural network architecture, including multi-layer perceptron, convolutional neural network and recurrent neural networks, are generated. The learning strategies, such as Adaptive moment estimation, L-BFGS, pseudoinverse learning algorithms and partial differential equation constrained optimization, are also presented. We believe it is of significance that presented clear physical image of interpretable deep neural networks, which makes it be possible for applying to analog computing device design, and pave the road to physical artificial intelligence.
Algorithmic Challenges in Ensuring Fairness at the Time of Decision
Venue: arXiv cs.LG 2024
Year: 2024

Algorithmic decision-making in societal contexts, such as retail pricing, loan administration, recommendations on online platforms, etc., can be framed as stochastic optimization under bandit feedback, which typically requires experimentation with different decisions for the sake of learning. Such experimentation often results in perceptions of unfairness among people impacted by these decisions; for instance, there have been several recent lawsuits accusing companies that deploy algorithmic pricing practices of price gouging. Motivated by the changing legal landscape surrounding algorithmic decision-making, we introduce the well-studied fairness notion of envy-freeness within the context of stochastic convex optimization. Our notion requires that upon receiving decisions in the present time, groups do not envy the decisions received by any of the other groups, both in the present as well as the past. This results in a novel trajectory-constrained stochastic optimization problem that renders existing techniques inapplicable. The main technical contribution of this work is to show problem settings where there is no gap in achievable regret (up to logarithmic factors) when envy-freeness is imposed. In particular, in our main result, we develop a near-optimal envy-free algorithm that achieves $\tilde{O}(\sqrt{T})$ regret for smooth convex functions that satisfy the PL inequality. This algorithm has a coordinate-descent structure, in which we carefully leverage gradient information to ensure monotonic sampling along each dimension, while avoiding overshooting the constrained optimum with high probability. This latter aspect critically uses smoothness and the structure of the envy-freeness constraints, while the PL inequality allows for sufficient progress towards the optimal solution. We discuss several open questions that arise from this analysis, which may be of independent interest.
Marine Snow Removal Benchmarking Dataset
Venue: arXiv cs.CV 2024
Year: 2024

This paper introduces a new benchmarking dataset for marine snow removal of underwater images. Marine snow is one of the main degradation sources of underwater images that are caused by small particles, e.g., organic matter and sand, between the underwater scene and photosensors. We mathematically model two typical types of marine snow from the observations of real underwater images. The modeled artifacts are synthesized with underwater images to construct large-scale pairs of ground truth and degraded images to calculate objective qualities for marine snow removal and to train a deep neural network. We propose two marine snow removal tasks using the dataset and show the first benchmarking results of marine snow removal. The Marine Snow Removal Benchmarking Dataset is publicly available online.
Random line graphs and edge-attributed network inference
Venue: arXiv cs.SI 2024
Year: 2024

We extend the latent position random graph model to the line graph of a random graph, which is formed by creating a vertex for each edge in the original random graph, and connecting each pair of edges incident to a common vertex in the original graph. We prove concentration inequalities for the spectrum of a line graph, as well as limiting distribution results for the largest eigenvalue and the empirical spectral distribution in certain settings. For the stochastic blockmodel, we establish that although naive spectral decompositions can fail to extract necessary signal for edge clustering, there exist signal-preserving singular subspaces of the line graph that can be recovered through a carefully-chosen projection. Moreover, we can consistently estimate edge latent positions in a random line graph, even though such graphs are of a random size, typically have high rank, and possess no spectral gap. Our results demonstrate that the line graph of a stochastic block model exhibits underlying block structure, and in simulations, we synthesize and test our methods against several commonly-used techniques, including tensor decompositions, for cluster recovery and edge covariate inference. By naturally incorporating information encoded in both vertices and edges, the random line graph improves network inference.
Disentangling Parallelism and Interference in Game Semantics
Venue: arXiv cs.LO 2024
Year: 2024

Game semantics is a denotational semantics presenting compositionally the computational behaviour of various kinds of effectful programs. One of its celebrated achievement is to have obtained full abstraction results for programming languages with a variety of computational effects, in a single framework. This is known as the semantic cube or Abramsky's cube, which for sequential deterministic programs establishes a correspondence between certain conditions on strategies (''innocence'', ''well-bracketing'', ''visibility'') and the absence of matching computational effects. Outside of the sequential deterministic realm, there are still a wealth of game semantics-based full abstraction results; but they no longer fit in a unified canvas. In particular, Ghica and Murawski's fully abstract model for shared state concurrency (IA) does not have a matching notion of pure parallel program-we say that parallelism and interference (i.e. state plus semaphores) are entangled. In this paper we construct a causal version of Ghica and Murawski's model, also fully abstract for IA. We provide compositional conditions parallel innocence and sequentiality, respectively banning interference and parallelism, and leading to four full abstraction results. To our knowledge, this is the first extension of Abramsky's semantic cube programme beyond the sequential deterministic world.
DCVNet: Dilated Cost Volume Networks for Fast Optical Flow
Venue: arXiv cs.CV 2024
Year: 2024

The cost volume, capturing the similarity of possible correspondences across two input images, is a key ingredient in state-of-the-art optical flow approaches. When sampling correspondences to build the cost volume, a large neighborhood radius is required to deal with large displacements, introducing a significant computational burden. To address this, coarse-to-fine or recurrent processing of the cost volume is usually adopted, where correspondence sampling in a local neighborhood with a small radius suffices. In this paper, we propose an alternative by constructing cost volumes with different dilation factors to capture small and large displacements simultaneously. A U-Net with skip connections is employed to convert the dilated cost volumes into interpolation weights between all possible captured displacements to get the optical flow. Our proposed model DCVNet only needs to process the cost volume once in a simple feedforward manner and does not rely on the sequential processing strategy. DCVNet obtains comparable accuracy to existing approaches and achieves real-time inference (30 fps on a mid-end 1080ti GPU). The code and model weights are available at https://github.com/neu-vi/ezflow.
A Detector-oblivious Multi-arm Network for Keypoint Matching
Venue: arXiv cs.CV 2024
Year: 2024

This paper presents a matching network to establish point correspondence between images. We propose a Multi-Arm Network (MAN) to learn region overlap and depth, which can greatly improve the keypoint matching robustness while bringing little computational cost during the inference stage. Another design that makes this framework different from many existing learning based pipelines that require re-training when a different keypoint detector is adopted, our network can directly work with different keypoint detectors without such a time-consuming re-training process. Comprehensive experiments conducted on outdoor and indoor datasets demonstrated that our proposed MAN outperforms state-of-the-art methods.
Inapproximability of Unique Games in Fixed-Point Logic with Counting
Venue: arXiv cs.LO 2024
Year: 2024

We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). Formally, we prove lower bounds against the accuracy of FPC-interpretations that map Unique Games instances (encoded as relational structures) to rational numbers giving the approximate fraction of constraints that can be satisfied. We prove two new FPC-inexpressibility results for Unique Games: the existence of a $(1/2, 1/3 + δ)$-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPC-inexpressibility results are based on variants of the CFI-construction, ours is significantly different. We start with a graph of very large girth and label the edges with random affine vector spaces over $\mathbb{F}_2$ that determine the constraints in the two structures. Duplicator's strategy involves maintaining a partial isomorphism over a minimal tree that spans the pebbled vertices of the graph.
OneLog: Towards End-to-End Training in Software Log Anomaly Detection
Venue: arXiv cs.SE 2024
Year: 2024

With the growth of online services, IoT devices, and DevOps-oriented software development, software log anomaly detection is becoming increasingly important. Prior works mainly follow a traditional four-staged architecture (Preprocessor, Parser, Vectorizer, and Classifier). This paper proposes OneLog, which utilizes a single Deep Neural Network (DNN) instead of multiple separate components. OneLog harnesses Convolutional Neural Networks (CNN) at the character level to take digits, numbers, and punctuations, which were removed in prior works, into account alongside the main natural language text. We evaluate our approach in six message- and sequence-based data sets: HDFS, Hadoop, BGL, Thunderbird, Spirit, and Liberty. We experiment with Onelog with single-, multi-, and cross-project setups. Onelog offers state-of-the-art performance in our datasets. Onelog can utilize multi-project datasets simultaneously during training, which suggests our model can generalize between datasets. Multi-project training also improves Onelog performance making it ideal when limited training data is available for an individual project. We also found that cross-project anomaly detection is possible with a single project pair (Liberty and Spirit). Analysis of model internals shows that one log has multiple modes of detecting anomalies and that the model learns manually validated parsing rules for the log messages. We conclude that character-based CNNs are a promising approach toward end-to-end learning in log anomaly detection. They offer good performance and generalization over multiple datasets. We will make our scripts publicly available upon the acceptance of this paper.
AeroTraj: Trajectory Planning for Fast, and Accurate 3D Reconstruction Using a Drone-based LiDAR
Venue: arXiv cs.RO 2024
Year: 2024

This paper presents AeroTraj, a system that enables fast, accurate, and automated reconstruction of 3D models of large buildings using a drone-mounted LiDAR. LiDAR point clouds can be used directly to assemble 3D models if their positions are accurately determined. AeroTraj uses SLAM for this, but must ensure complete and accurate reconstruction while minimizing drone battery usage. Doing this requires balancing competing constraints: drone speed, height, and orientation. AeroTraj exploits building geometry in designing an optimal trajectory that incorporates these constraints. Even with an optimal trajectory, SLAM's position error can drift over time, so AeroTraj tracks drift in-flight by offloading computations to the cloud and invokes a re-calibration procedure to minimize error. AeroTraj can reconstruct large structures with centimeter-level accuracy and with an average end-to-end latency below 250 ms, significantly outperforming the state of the art.
Sequential composition of answer set programs
Venue: arXiv cs.AI 2024
Year: 2024

This paper contributes to the mathematical foundations of logic programming by introducing and studying the sequential composition of answer set programs. On the semantic side, we show that the immediate consequence operator of a program can be represented via composition, which allows us to compute the least model semantics of Horn programs without any explicit reference to operators. As a result, we can characterize answer sets algebraically, which further provides an algebraic characterization of strong and uniform equivalence which is appealing. This bridges the conceptual gap between the syntax and semantics of an answer set program in a mathematically satisfactory way. The so-obtained algebraization of answer set programming allows us to transfer algebraic concepts into the ASP-setting which we demonstrate by introducing the index and period of an answer set program as an algebraic measure of its cyclicality. The technical part of the paper ends with a brief section introducing the algebraically inspired novel class of aperiodic answer set programs strictly containing the acyclic ones. In a broader sense, this paper is a first step towards an algebra of answer set programs and in the future we plan to lift the methods of this paper to wider classes of programs, most importantly to higher-order and disjunctive programs and extensions thereof.
Explore BiLSTM-CRF-Based Models for Open Relation Extraction
Venue: arXiv cs.CL 2024
Year: 2024

Extracting multiple relations from text sentences is still a challenge for current Open Relation Extraction (Open RE) tasks. In this paper, we develop several Open RE models based on the bidirectional LSTM-CRF (BiLSTM-CRF) neural network and different contextualized word embedding methods. We also propose a new tagging scheme to solve overlapping problems and enhance models' performance. From the evaluation results and comparisons between models, we select the best combination of tagging scheme, word embedder, and BiLSTM-CRF network to achieve an Open RE model with a remarkable extracting ability on multiple-relation sentences.
secml-malware: Pentesting Windows Malware Classifiers with Adversarial EXEmples in Python
Venue: arXiv cs.CR 2024
Year: 2024

Machine learning has been increasingly used as a first line of defense for Windows malware detection. Recent work has however shown that learning-based malware detectors can be evaded by carefully-perturbed input malware samples, referred to as adversarial EXEmples, thus demanding for tools that can ease and automate the adversarial robustness evaluation of such detectors. To this end, we present secml-malware, the first Python library for computing adversarial attacks on Windows malware detectors. secml-malware implements state-of-the-art white-box and black-box attacks on Windows malware classifiers, by leveraging a set of feasible manipulations that can be applied to Windows programs while preserving their functionality. The library can be used to perform the penetration testing and assessment of the adversarial robustness of Windows malware detectors, and it can be easily extended to include novel attack strategies. Our library is available at https://github.com/pralab/secml_malware.