OpenRaiser/Intern-Atlas huggingface dataset:
Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
Venue: arXiv cs.DS 2024
Year: 2024

In this paper, we study temporal graphs arising from mobility models, where vertices correspond to agents moving in space and edges appear each time two agents meet. We propose a rather natural one-dimensional model. If each pair of agents meets exactly once, we get a simple temporal clique where the edges are ordered according to meeting times. In order to characterize which temporal cliques can be obtained as such `mobility graphs', we introduce the notion of forbidden patterns in temporal graphs. Furthermore, using a classical result in combinatorics, we count the number of such mobility cliques for a given number of agents, and show that not every temporal clique resulting from the 1D model can be realized with agents moving with different constant speeds. For the analogous circular problem, where agents are moving along a circle, we provide a characterization via circular forbidden patterns. Our characterization in terms of forbidden patterns can be extended to the case where each edge appears at most once. We also study the problem where pairs of agents are allowed to cross each other several times, using an approach from automata theory. We observe that in this case, there is no finite set of forbidden patterns that characterize such temporal graphs and nevertheless give a linear-time algorithm to recognize temporal graphs arising from this model.
Transformer models: an introduction and catalog
Venue: arXiv cs.CL 2024
Year: 2024

In the past few years we have seen the meteoric appearance of dozens of foundation models of the Transformer family, all of which have memorable and sometimes funny, but not self-explanatory, names. The goal of this paper is to offer a somewhat comprehensive but simple catalog and classification of the most popular Transformer models. The paper also includes an introduction to the most important aspects and innovations in Transformer models. Our catalog will include models that are trained using self-supervised learning (e.g., BERT or GPT3) as well as those that are further trained using a human-in-the-loop (e.g. the InstructGPT model used by ChatGPT).
cGAN-Based High Dimensional IMU Sensor Data Generation for Enhanced Human Activity Recognition in Therapeutic Activities
Venue: arXiv cs.LG 2024
Year: 2024

Human activity recognition is a core technology for applications such as rehabilitation, health monitoring, and human-computer interactions. Wearable devices, especially IMU sensors, provide rich features of human movements at a reasonable cost, which can be leveraged in activity recognition. Developing a robust classifier for activity recognition has always been of interest to researchers. One major problem is that there is usually a deficit of training data, which makes developing deep classifiers difficult and sometimes impossible. In this work, a novel GAN network called TheraGAN was developed to generate IMU signals associated with rehabilitation activities. The generated signal comprises data from a 6-channel IMU, i.e., angular velocities and linear accelerations. Also, introducing simple activities simplified the generation process for activities of varying lengths. To evaluate the generated signals, several qualitative and quantitative studies were conducted, including perceptual similarity analysis, comparing manually extracted features to those from real data, visual inspection, and an investigation into how the generated data affects the performance of three deep classifiers trained on the generated and real data. The results showed that the generated signals closely mimicked the real signals, and adding generated data resulted in a significant improvement in the performance of all tested networks. Among the tested networks, the LSTM classifier demonstrated the most significant improvement, achieving a 13.27% boost, effectively addressing the challenge of data scarcity. This shows the validity of the generated data as well as TheraGAN as a tool to build more robust classifiers in case of imbalanced and insufficient data problems.
Local Causal Discovery for Estimating Causal Effects
Venue: arXiv cs.LG 2024
Year: 2024

Even when the causal graph underlying our data is unknown, we can use observational data to narrow down the possible values that an average treatment effect (ATE) can take by (1) identifying the graph up to a Markov equivalence class; and (2) estimating that ATE for each graph in the class. While the PC algorithm can identify this class under strong faithfulness assumptions, it can be computationally prohibitive. Fortunately, only the local graph structure around the treatment is required to identify the set of possible ATE values, a fact exploited by local discovery algorithms to improve computational efficiency. In this paper, we introduce Local Discovery using Eager Collider Checks (LDECC), a new local causal discovery algorithm that leverages unshielded colliders to orient the treatment's parents differently from existing methods. We show that there exist graphs where LDECC exponentially outperforms existing local discovery algorithms and vice versa. Moreover, we show that LDECC and existing algorithms rely on different faithfulness assumptions, leveraging this insight to weaken the assumptions for identifying the set of possible ATE values.
Distances for Markov Chains, and Their Differentiation
Venue: arXiv cs.LG 2024
Year: 2024

(Directed) graphs with node attributes are a common type of data in various applications and there is a vast literature on developing metrics and efficient algorithms for comparing them. Recently, in the graph learning and optimization communities, a range of new approaches have been developed for comparing graphs with node attributes, leveraging ideas such as the Optimal Transport (OT) and the Weisfeiler-Lehman (WL) graph isomorphism test. Two state-of-the-art representatives are the OTC distance proposed in (O'Connor et al., 2022) and the WL distance in (Chen et al., 2022). Interestingly, while these two distances are developed based on different ideas, we observe that they both view graphs as Markov chains, and are deeply connected. Indeed, in this paper, we propose a unified framework to generate distances for Markov chains (thus including (directed) graphs with node attributes), which we call the Optimal Transport Markov (OTM) distances, that encompass both the OTC and the WL distances. We further introduce a special one-parameter family of distances within our OTM framework, called the discounted WL distance. We show that the discounted WL distance has nice theoretical properties and can address several limitations of the existing OTC and WL distances. Furthermore, contrary to the OTC and the WL distances, our new discounted WL distance can be differentiated after a entropy-regularization similar to the Sinkhorn distance, making it suitable to use in learning frameworks, e.g., as the reconstruction loss in a graph generative model.
Deep Learning for Event-based Vision: A Comprehensive Survey and Benchmarks
Venue: arXiv cs.CV 2024
Year: 2024

Event cameras are bio-inspired sensors that capture the per-pixel intensity changes asynchronously and produce event streams encoding the time, pixel position, and polarity (sign) of the intensity changes. Event cameras possess a myriad of advantages over canonical frame-based cameras, such as high temporal resolution, high dynamic range, low latency, etc. Being capable of capturing information in challenging visual conditions, event cameras have the potential to overcome the limitations of frame-based cameras in the computer vision and robotics community. In very recent years, deep learning (DL) has been brought to this emerging field and inspired active research endeavors in mining its potential. However, there is still a lack of taxonomies in DL techniques for event-based vision. We first scrutinize the typical event representations with quality enhancement methods as they play a pivotal role as inputs to the DL models. We then provide a comprehensive survey of existing DL-based methods by structurally grouping them into two major categories: 1) image/video reconstruction and restoration; 2) event-based scene understanding and 3D vision. We conduct benchmark experiments for the existing methods in some representative research directions, i.e., image reconstruction, deblurring, and object recognition, to identify some critical insights and problems. Finally, we have discussions regarding the challenges and provide new perspectives for inspiring more research studies.
Like a Good Nearest Neighbor: Practical Content Moderation and Text Classification
Venue: arXiv cs.CL 2024
Year: 2024

Few-shot text classification systems have impressive capabilities but are infeasible to deploy and use reliably due to their dependence on prompting and billion-parameter language models. SetFit (Tunstall et al., 2022) is a recent, practical approach that fine-tunes a Sentence Transformer under a contrastive learning paradigm and achieves similar results to more unwieldy systems. Inexpensive text classification is important for addressing the problem of domain drift in all classification tasks, and especially in detecting harmful content, which plagues social media platforms. Here, we propose Like a Good Nearest Neighbor (LaGoNN), a modification to SetFit that introduces no learnable parameters but alters input text with information from its nearest neighbor, for example, the label and text, in the training data, making novel data appear similar to an instance on which the model was optimized. LaGoNN is effective at flagging undesirable content and text classification, and improves the performance of SetFit. To demonstrate the value of LaGoNN, we conduct a thorough study of text classification systems in the context of content moderation under four label distributions, and in general and multilingual classification settings.
mBEST: Realtime Deformable Linear Object Detection Through Minimal Bending Energy Skeleton Pixel Traversals
Venue: arXiv cs.RO 2024
Year: 2024

Robotic manipulation of deformable materials is a challenging task that often requires realtime visual feedback. This is especially true for deformable linear objects (DLOs) or "rods", whose slender and flexible structures make proper tracking and detection nontrivial. To address this challenge, we present mBEST, a robust algorithm for the realtime detection of DLOs that is capable of producing an ordered pixel sequence of each DLO's centerline along with segmentation masks. Our algorithm obtains a binary mask of the DLOs and then thins it to produce a skeleton pixel representation. After refining the skeleton to ensure topological correctness, the pixels are traversed to generate paths along each unique DLO. At the core of our algorithm, we postulate that intersections can be robustly handled by choosing the combination of paths that minimizes the cumulative bending energy of the DLO(s). We show that this simple and intuitive formulation outperforms the state-of-the-art methods for detecting DLOs with large numbers of sporadic crossings ranging from curvatures with high variance to nearly-parallel configurations. Furthermore, our method achieves a significant performance improvement of approximately 50% faster runtime and better scaling over the state of the art.
Wrapyfi: A Python Wrapper for Integrating Robots, Sensors, and Applications across Multiple Middleware
Venue: arXiv cs.RO 2024
Year: 2024

Message oriented and robotics middleware play an important role in facilitating robot control, abstracting complex functionality, and unifying communication patterns between sensors and devices. However, using multiple middleware frameworks presents a challenge in integrating different robots within a single system. To address this challenge, we present Wrapyfi, a Python wrapper supporting multiple message oriented and robotics middleware, including ZeroMQ, YARP, ROS, and ROS 2. Wrapyfi also provides plugins for exchanging deep learning framework data, without additional encoding or preprocessing steps. Using Wrapyfi eases the development of scripts that run on multiple machines, thereby enabling cross-platform communication and workload distribution. We finally present the three communication schemes that form the cornerstone of Wrapyfi's communication model, along with examples that demonstrate their applicability.
DINOISER: Diffused Conditional Sequence Learning by Manipulating Noises
Venue: arXiv cs.CL 2024
Year: 2024

While diffusion models have achieved great success in generating continuous signals such as images and audio, it remains elusive for diffusion models in learning discrete sequence data like natural languages. Although recent advances circumvent this challenge of discreteness by embedding discrete tokens as continuous surrogates, they still fall short of satisfactory generation quality. To understand this, we first dive deep into the denoised training protocol of diffusion-based sequence generative models and determine their three severe problems, i.e., 1) failing to learn, 2) lack of scalability, and 3) neglecting source conditions. We argue that these problems can be boiled down to the pitfall of the not completely eliminated discreteness in the embedding space, and the scale of noises is decisive herein. In this paper, we introduce DINOISER to facilitate diffusion models for sequence generation by manipulating noises. We propose to adaptively determine the range of sampled noise scales for counter-discreteness training; and encourage the proposed diffused sequence learner to leverage source conditions with amplified noise scales during inference. Experiments show that DINOISER enables consistent improvement over the baselines of previous diffusion-based sequence generative models on several conditional sequence modeling benchmarks thanks to both effective training and inference strategies. Analyses further verify that DINOISER can make better use of source conditions to govern its generative process.
Contrastive Learning and the Emergence of Attributes Associations
Venue: arXiv cs.CV 2024
Year: 2024

In response to an object presentation, supervised learning schemes generally respond with a parsimonious label. Upon a similar presentation we humans respond again with a label, but are flooded, in addition, by a myriad of associations. A significant portion of these consist of the presented object attributes. Contrastive learning is a semi-supervised learning scheme based on the application of identity preserving transformations on the object input representations. It is conjectured in this work that these same applied transformations preserve, in addition to the identity of the presented object, also the identity of its semantically meaningful attributes. The corollary of this is that the output representations of such a contrastive learning scheme contain valuable information not only for the classification of the presented object, but also for the presence or absence decision of any attribute of interest. Simulation results which demonstrate this idea and the feasibility of this conjecture are presented.
Complexity of Maker-Breaker Games on Edge Sets of Graphs
Venue: arXiv cs.CC 2024
Year: 2024

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the $H$-game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph $H$ in the second. We prove that deciding who wins the perfect matching game and the $H$-game is PSPACE-complete, even for the latter in small-diameter graphs if $H$ is a tree. Toward finding the smallest graph $H$ for which the $H$-game is PSPACE-complete, we also prove that such an $H$ of order 51 and size 57 exists. We then give several positive results for the $H$-game. As the $H$-game is already PSPACE-complete when $H$ is a tree, we mainly consider the case where $H$ belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the $P_4$-game in general graphs and the $K_{1,\ell}$-game in trees. Then, we prove that the $K_{1,\ell}$-game in any graph, and the $H$-game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest. Another natural direction to take is to consider the $H$-game when $H$ is a cycle. While we were unable to resolve this case, we prove that the related arboricity-$k$ game is polynomial-time solvable. In particular, when $k=2$, Maker wins this game if she claims the edges of any cycle.
Constructing Deterministic Parity Automata from Positive and Negative Examples
Venue: arXiv cs.FL 2024
Year: 2024

We present a polynomial time algorithm that constructs a deterministic parity automaton (DPA) from a given set of positive and negative ultimately periodic example words. We show that this algorithm is complete for the class of $ω$-regular languages, that is, it can learn a DPA for each regular $ω$-language. For use in the algorithm, we give a definition of a DPA, that we call the precise DPA of a language, and show that it can be constructed from the syntactic family of right congruences for that language (introduced by Maler and Staiger in 1997). Depending on the structure of the language, the precise DPA can be of exponential size compared to a minimal DPA, but it can also be a minimal DPA. The upper bound that we obtain on the number of examples required for our algorithm to find a DPA for $L$ is therefore exponential in the size of a minimal DPA, in general. However we identify two parameters of regular $ω$-languages such that fixing these parameters makes the bound polynomial.
Modular Deep Learning
Venue: arXiv cs.LG 2024
Year: 2024

Transfer learning has recently become the dominant paradigm of machine learning. Pre-trained models fine-tuned for downstream tasks achieve better performance with fewer labelled examples. Nonetheless, it remains unclear how to develop models that specialise towards multiple tasks without incurring negative interference and that generalise systematically to non-identically distributed tasks. Modular deep learning has emerged as a promising solution to these challenges. In this framework, units of computation are often implemented as autonomous parameter-efficient modules. Information is conditionally routed to a subset of modules and subsequently aggregated. These properties enable positive transfer and systematic generalisation by separating computation from routing and updating modules locally. We offer a survey of modular architectures, providing a unified view over several threads of research that evolved independently in the scientific literature. Moreover, we explore various additional purposes of modularity, including scaling language models, causal inference, programme induction, and planning in reinforcement learning. Finally, we report various concrete applications where modularity has been successfully deployed such as cross-lingual and cross-modal knowledge transfer. Related talks and projects to this survey, are available at https://www.modulardeeplearning.com/.
MONGOOSE: Path-wise Smooth Bayesian Optimisation via Meta-learning
Venue: arXiv cs.LG 2024
Year: 2024

In Bayesian optimisation, we often seek to minimise the black-box objective functions that arise in real-world physical systems. A primary contributor to the cost of evaluating such black-box objective functions is often the effort required to prepare the system for measurement. We consider a common scenario where preparation costs grow as the distance between successive evaluations increases. In this setting, smooth optimisation trajectories are preferred and the jumpy paths produced by the standard myopic (i.e.\ one-step-optimal) Bayesian optimisation methods are sub-optimal. Our algorithm, MONGOOSE, uses a meta-learnt parametric policy to generate smooth optimisation trajectories, achieving performance gains over existing methods when optimising functions with large movement costs.
Out-of-Domain Robustness via Targeted Augmentations
Venue: arXiv cs.LG 2024
Year: 2024

Models trained on one set of domains often suffer performance drops on unseen domains, e.g., when wildlife monitoring models are deployed in new camera locations. In this work, we study principles for designing data augmentations for out-of-domain (OOD) generalization. In particular, we focus on real-world scenarios in which some domain-dependent features are robust, i.e., some features that vary across domains are predictive OOD. For example, in the wildlife monitoring application above, image backgrounds vary across camera locations but indicate habitat type, which helps predict the species of photographed animals. Motivated by theoretical analysis on a linear setting, we propose targeted augmentations, which selectively randomize spurious domain-dependent features while preserving robust ones. We prove that targeted augmentations improve OOD performance, allowing models to generalize better with fewer domains. In contrast, existing approaches such as generic augmentations, which fail to randomize domain-dependent features, and domain-invariant augmentations, which randomize all domain-dependent features, both perform poorly OOD. In experiments on three real-world datasets, we show that targeted augmentations set new states-of-the-art for OOD performance by 3.2-15.2 percentage points.
Novel Epileptic Seizure Detection Techniques and their Empirical Analysis
Venue: arXiv cs.LG 2024
Year: 2024

An Electroencephalogram (EEG) is a non-invasive exam that records the brain's electrical activity. This is used to help diagnose conditions such as different brain problems. EEG signals are taken for epilepsy detection, and with Discrete Wavelet Transform (DWT) and machine learning classifier, they perform epilepsy detection. In Epilepsy seizure detection, machine learning classifiers and statistical features are mainly used. The hidden information in the EEG signal helps detect diseases affecting the brain. Sometimes it is complicated to identify the minimum changes in the EEG in the time and frequency domain's purpose. The DWT can give a suitable decomposition of the signals in different frequency bands and feature extraction. We use the tri-dimensionality reduction algorithm, Principal Component Analysis (PCA), Independent Component Analysis (ICA), and Linear Discriminant Analysis (LDA). Finally, features are selected by using a fusion rule and at the last step, three different classifiers, Support Vector Machine (SVM), Naive Bayes (NB), and K-Nearest-Neighbor (KNN) have been used individually for the classification. The proposed framework is tested on the Bonn dataset. The simulation results provide 100% accuracy for the LDA and NB combination outperforming accuracy with other classifiers combinations, including 89.17% for LDA and SVM, 80.42% for LDA and KNN, 89.92% for PCA and NB, 85.58% PCA and SVM, 80.42% PCA and KNN, 82.33% for ICA and NB, 90.42% for ICA and SVM, 90% for ICA and KNN. Also, the LDA and NB combination shows the sensitivity, specificity, accuracy, Precision, and Recall of 100%, 100%, 100%, 100%, and 100%. The results prove the effectiveness of this model.