OpenRaiser/Intern-Atlas huggingface dataset:
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Venue: arXiv cs.DS 2024
Year: 2024

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string $T$ from left to right into blocks (called phrases) so that each phrase is either the leftmost occurrence of a letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in $T$. Due to numerous applications, LZ77 factorization is one of the most studied problems on strings. In the 47 years since its inception, several algorithms were developed for different models of computation, including parallel, GPU, external-memory, and quantum. Remarkably, however, the complexity of the most basic variant is still not settled: All existing algorithms in the RAM model run in $Ω(n)$ time, which is a $Θ(\log n)$ factor away from the lower bound of $Ω(n/\log n)$ (following from the necessity to read the input, which takes $Θ(n/\log n)$ space for $T\in\{0,1\}^{n}$). We present the first $o(n)$-time algorithm for LZ77 factorization, breaking the linear-time barrier present for nearly 50 years. For $T\in\{0,1\}^{n}$, our algorithm runs in $\mathcal{O}(n/\sqrt{\log n})=o(n)$ time and uses the optimal $\mathcal{O}(n/\log n)$ working space. Our algorithm generalizes to $Σ=[0..σ)$, where $σ=n^{\mathcal{O}(1)}$. The runtime and working space then become $\mathcal{O}((n\logσ)/\sqrt{\log n})$ and $\mathcal{O}(n/\log_σ n)$. To obtain our algorithm, we prove a more general result: For any constant $ε\in(0,1)$ and $T\in[0..σ)^{n}$, in $\mathcal{O}((n\logσ)/\sqrt{\log n})$ time and using $\mathcal{O}(n/\log_σn)$ space, we can construct an $\mathcal{O}(n/\log_σn)$-size index that, given any $P=T[j..j+\ell)$ (represented as $(j,\ell)$), computes the leftmost occurrence of $P$ in $T$ in $\mathcal{O}(\log^εn)$ time. In other words, we solve the indexing/online variant of the LZ77 problem.
Robots that Learn to Safely Influence via Prediction-Informed Reach-Avoid Dynamic Games
Venue: arXiv cs.RO 2024
Year: 2024

Robots can influence people to accomplish their tasks more efficiently: autonomous cars can inch forward at an intersection to pass through, and tabletop manipulators can go for an object on the table first. However, a robot's ability to influence can also compromise the safety of nearby people if naively executed. In this work, we pose and solve a novel robust reach-avoid dynamic game which enables robots to be maximally influential, but only when a safety backup control exists. On the human side, we model the human's behavior as goal-driven but conditioned on the robot's plan, enabling us to capture influence. On the robot side, we solve the dynamic game in the joint physical and belief space, enabling the robot to reason about how its uncertainty in human behavior will evolve over time. We instantiate our method, called SLIDE (Safely Leveraging Influence in Dynamic Environments), in a high-dimensional (39-D) simulated human-robot collaborative manipulation task solved via offline game-theoretic reinforcement learning. We compare our approach to a robust baseline that treats the human as a worst-case adversary, a safety controller that does not explicitly reason about influence, and an energy-function-based safety shield. We find that SLIDE consistently enables the robot to leverage the influence it has on the human when it is safe to do so, ultimately allowing the robot to be less conservative while still ensuring a high safety rate during task execution.
Expanding Expressivity in Transformer Models with MöbiusAttention
Venue: arXiv cs.LG 2024
Year: 2024

Attention mechanisms and Transformer architectures have revolutionized Natural Language Processing (NLP) by enabling exceptional modeling of long-range dependencies and capturing intricate linguistic patterns. However, their inherent reliance on linear operations in the form of matrix multiplications limits their ability to fully capture inter-token relationships on their own. We propose MöbiusAttention, a novel approach that integrates Möbius transformations within the attention mechanism of Transformer-based models. Möbius transformations are non-linear operations in spaces over complex numbers with the ability to map between various geometries. By incorporating these properties, MöbiusAttention empowers models to learn more intricate geometric relationships between tokens and capture a wider range of information through complex-valued weight vectors. We build and pre-train a BERT and a RoFormer version enhanced with MöbiusAttention, which we then finetune on the GLUE benchmark. We evaluate empirically our approach against the baseline BERT and RoFormer models on a range of downstream tasks. Our approach compares favorably against the baseline models, even with smaller number of parameters suggesting the enhanced expressivity of MöbiusAttention. This research paves the way for exploring the potential of Möbius transformations in the complex projective space to enhance the expressivity and performance of foundation models.
C-Uniform Trajectory Sampling For Fast Motion Planning
Venue: arXiv cs.RO 2024
Year: 2024

We study the problem of sampling robot trajectories and introduce the notion of C-Uniformity. As opposed to the standard method of uniformly sampling control inputs (which lead to biased samples of the configuration space), C-Uniform trajectories are generated by control actions which lead to uniform sampling of the configuration space. After presenting an intuitive closed-form solution to generate C-Uniform trajectories for the 1D random-walker, we present a network-flow based optimization method to precompute C-Uniform trajectories for general robot systems. We apply the notion of C-Uniformity to the design of Model Predictive Path Integral controllers. Through simulation experiments, we show that using C-Uniform trajectories significantly improves the performance of MPPI-style controllers, achieving up to 40% coverage performance gain compared to the best baseline. We demonstrate the practical applicability of our method with an implementation on a 1/10th scale racer.
Unlocking the Power of Environment Assumptions for Unit Proofs
Venue: arXiv cs.SE 2024
Year: 2024

Clearly articulating the assumptions of the execution environment is crucial for the successful application of code-level formal verification. The process of specifying a model for the environment can be both laborious and error-prone, often requiring domain experts. In contrast, when engineers write unit tests, they frequently employ mocks (tMocks) to define the expected behavior of the environment in which the function under test operates. These tMocks describe how the environment behaves, e.g., the return types of an external API call (stateless behaviour) or the correct sequence of function calls (stateful behaviour). Mocking frameworks have proven to be highly effective tools for crafting unit tests. In our work, we draw inspiration from tMocks and introduce their counterpart in the realm of formal verification, which we term vMocks. vMocks offer an intuitive framework for specifying a plausible environment when conducting code-level formal verification. We implement a vMock library for the verification of C programs called SEAMOCK. We investigate the practicality of vMocks by, first, comparing specifications styles in the communication layer of the Android Trusty Trusted Execution Environment (TEE) open source project, and second, in the verification of mbedTLS, a widely used open source C library that provides secure communication protocols and cryptography primitives for embedded systems. Based on our experience, we conclude that vMocks complement other forms of environment models. We believe that vMocks ease adoption of code-level formal verification among developers already familiar with tMocks.
Improving Soft-Capture Phase Success in Space Debris Removal Missions: Leveraging Deep Reinforcement Learning and Tactile Feedback
Venue: arXiv cs.RO 2024
Year: 2024

Traditional control methods effectively manage robot operations using models like motion equations but face challenges with issues of contact and friction, leading to unstable and imprecise controllers that often require manual tweaking. Reinforcement learning, however, has developed as a capable solution for developing robust robot controllers that excel in handling contact-related challenges. In this work, we introduce a deep reinforcement learning approach to tackle the soft-capture phase for free-floating moving targets, mainly space debris, amidst noisy data. Our findings underscore the crucial role of tactile sensors, even during the soft-capturing phase. By employing deep reinforcement learning, we eliminate the need for manual feature design, simplifying the problem and allowing the robot to learn soft-capture strategies through trial and error. To facilitate effective learning of the approach phase, we have crafted a specialized reward function that offers clear and insightful feedback to the agent. Our method is trained entirely within the simulation environment, eliminating the need for direct demonstrations or prior knowledge of the task. The developed control policy shows promising results, highlighting the necessity of using tactile sensor information. The code and simulation results are available at Soft_Capture_Tactile repo.
Measuring Sound Symbolism in Audio-visual Models
Venue: arXiv cs.CL 2024
Year: 2024

Audio-visual pre-trained models have gained substantial attention recently and demonstrated superior performance on various audio-visual tasks. This study investigates whether pre-trained audio-visual models demonstrate non-arbitrary associations between sounds and visual representations$\unicode{x2013}$known as sound symbolism$\unicode{x2013}$which is also observed in humans. We developed a specialized dataset with synthesized images and audio samples and assessed these models using a non-parametric approach in a zero-shot setting. Our findings reveal a significant correlation between the models' outputs and established patterns of sound symbolism, particularly in models trained on speech data. These results suggest that such models can capture sound-meaning connections akin to human language processing, providing insights into both cognitive architectures and machine learning strategies.
Towards Closing the Loop in Robotic Pollination for Indoor Farming via Autonomous Microscopic Inspection
Venue: arXiv cs.RO 2024
Year: 2024

Effective pollination is a key challenge for indoor farming, since bees struggle to navigate without the sun. While a variety of robotic system solutions have been proposed, it remains difficult to autonomously check that a flower has been sufficiently pollinated to produce high-quality fruit, which is especially critical for self-pollinating crops such as strawberries. To this end, this work proposes a novel robotic system for indoor farming. The proposed hardware combines a 7-degree-of-freedom (DOF) manipulator arm with a custom end-effector, comprised of an endoscope camera, a 2-DOF microscope subsystem, and a custom vibrating pollination tool; this is paired with algorithms to detect and estimate the pose of strawberry flowers, navigate to each flower, pollinate using the tool, and inspect with the microscope. The key novelty is vibrating the flower from below while simultaneously inspecting with a microscope from above. Each subsystem is validated via extensive experiments.
Advancing Cucumber Disease Detection in Agriculture through Machine Vision and Drone Technology
Venue: arXiv cs.CV 2024
Year: 2024

This study uses machine vision and drone technologies to propose a unique method for the diagnosis of cucumber disease in agriculture. The backbone of this research is a painstakingly curated dataset of hyperspectral photographs acquired under genuine field conditions. Unlike earlier datasets, this study included a wide variety of illness types, allowing for precise early-stage detection. The model achieves an excellent 87.5\% accuracy in distinguishing eight unique cucumber illnesses after considerable data augmentation. The incorporation of drone technology for high-resolution images improves disease evaluation. This development has enormous potential for improving crop management, lowering labor costs, and increasing agricultural productivity. This research, which automates disease detection, represents a significant step toward a more efficient and sustainable agricultural future.
Dynamics of Post-disaster Recovery in Behavior-dependent Business Networks
Venue: arXiv cs.SI 2024
Year: 2024

The recovery of businesses after a disaster is vital to community economic resilience, yet the network dynamics influencing the speed and spillover effects of recovery remain poorly understood. Understanding these dynamics is essential for characterizing economic resilience and informing more effective recovery policies. This study explores the extent to which post-disaster business recovery is shaped by network diffusion processes within pre-disaster business dependency networks, driven by visitation behaviors among business points of interest (POIs). We developed a network diffusion model to simulate recovery across businesses in the Louisiana Gulf Coast following Hurricane Ida (2021) and assessed its performance using empirical data. Our analysis focuses on four key areas: (1) the presence of a diffusion process influencing recovery across the business network; (2) variations in how different business types depend on others for recovery; (3) identification of recovery multiplier businesses that accelerate regional recovery; and (4) differences in recovery multipliers across high- and low-income areas. The findings reveal that business recovery is governed by diffusion dynamics in these behavior-based networks, with recovery speed closely linked to pre-disaster visitation patterns. Retail and service businesses are identified as key recovery multipliers whose rapid recovery accelerates the broader business network's recovery, enhancing economic resilience. Additionally, recovery multipliers vary between high- and low-income areas. This study enhances our understanding of network mechanisms in post-disaster recovery and offers valuable insights for improving recovery policies.
Extracting Memorized Training Data via Decomposition
Venue: arXiv cs.LG 2024
Year: 2024

The widespread use of Large Language Models (LLMs) in society creates new information security challenges for developers, organizations, and end-users alike. LLMs are trained on large volumes of data, and their susceptibility to reveal the exact contents of the source training datasets poses security and safety risks. Although current alignment procedures restrict common risky behaviors, they do not completely prevent LLMs from leaking data. Prior work demonstrated that LLMs may be tricked into divulging training data by using out-of-distribution queries or adversarial techniques. In this paper, we demonstrate a simple, query-based decompositional method to extract news articles from two frontier LLMs. We use instruction decomposition techniques to incrementally extract fragments of training data. Out of 3723 New York Times articles, we extract at least one verbatim sentence from 73 articles, and over 20% of verbatim sentences from 6 articles. Our analysis demonstrates that this method successfully induces the LLM to generate texts that are reliable reproductions of news articles, meaning that they likely originate from the source training dataset. This method is simple, generalizable, and does not fine-tune or change the production model. If replicable at scale, this training data extraction methodology could expose new LLM security and safety vulnerabilities, including privacy risks and unauthorized data leaks. These implications require careful consideration from model development to its end-use.
Selecting a classification performance measure: matching the measure to the problem
Venue: arXiv cs.LG 2024
Year: 2024

The problem of identifying to which of a given set of classes objects belong is ubiquitous, occurring in many research domains and application areas, including medical diagnosis, financial decision making, online commerce, and national security. But such assignments are rarely completely perfect, and classification errors occur. This means it is necessary to compare classification methods and algorithms to decide which is ``best'' for any particular problem. However, just as there are many different classification methods, so there are many different ways of measuring their performance. It is thus vital to choose a measure of performance which matches the aims of the research or application. This paper is a contribution to the growing literature on the relative merits of different performance measures. Its particular focus is the critical importance of matching the properties of the measure to the aims for which the classification is being made.
Is it Still Fair? A Comparative Evaluation of Fairness Algorithms through the Lens of Covariate Drift
Venue: arXiv cs.LG 2024
Year: 2024

Over the last few decades, machine learning (ML) applications have grown exponentially, yielding several benefits to society. However, these benefits are tempered with concerns of discriminatory behaviours exhibited by ML models. In this regard, fairness in machine learning has emerged as a priority research area. Consequently, several fairness metrics and algorithms have been developed to mitigate against discriminatory behaviours that ML models may possess. Yet still, very little attention has been paid to the problem of naturally occurring changes in data patterns (\textit{aka} data distributional drift), and its impact on fairness algorithms and metrics. In this work, we study this problem comprehensively by analyzing 4 fairness-unaware baseline algorithms and 7 fairness-aware algorithms, carefully curated to cover the breadth of its typology, across 5 datasets including public and proprietary data, and evaluated them using 3 predictive performance and 10 fairness metrics. In doing so, we show that (1) data distributional drift is not a trivial occurrence, and in several cases can lead to serious deterioration of fairness in so-called fair models; (2) contrary to some existing literature, the size and direction of data distributional drift is not correlated to the resulting size and direction of unfairness; and (3) choice of, and training of fairness algorithms is impacted by the effect of data distributional drift which is largely ignored in the literature. Emanating from our findings, we synthesize several policy implications of data distributional drift on fairness algorithms that can be very relevant to stakeholders and practitioners.
Incremental and Data-Efficient Concept Formation to Support Masked Word Prediction
Venue: arXiv cs.CL 2024
Year: 2024

This paper introduces Cobweb4L, a novel approach for efficient language model learning that supports masked word prediction. The approach builds on Cobweb, an incremental system that learns a hierarchy of probabilistic concepts. Each concept stores the frequencies of words that appear in instances tagged with that concept label. The system utilizes an attribute value representation to encode words and their surrounding context into instances. Cobweb4L uses the information theoretic variant of category utility and a new performance mechanism that leverages multiple concepts to generate predictions. We demonstrate that with these extensions it significantly outperforms prior Cobweb performance mechanisms that use only a single node to generate predictions. Further, we demonstrate that Cobweb4L learns rapidly and achieves performance comparable to and even superior to Word2Vec. Next, we show that Cobweb4L and Word2Vec outperform BERT in the same task with less training data. Finally, we discuss future work to make our conclusions more robust and inclusive.
FoME: A Foundation Model for EEG using Adaptive Temporal-Lateral Attention Scaling
Venue: arXiv cs.LG 2024
Year: 2024

Electroencephalography (EEG) is a vital tool to measure and record brain activity in neuroscience and clinical applications, yet its potential is constrained by signal heterogeneity, low signal-to-noise ratios, and limited labeled datasets. In this paper, we propose FoME (Foundation Model for EEG), a novel approach using adaptive temporal-lateral attention scaling to address above-mentioned challenges. FoME is pre-trained on a diverse 1.7TB dataset of scalp and intracranial EEG recordings, comprising 745M parameters trained for 1,096k steps. Our model introduces two key innovations: a time-frequency fusion embedding technique and an adaptive time-lateral attention scaling (ATLAS) mechanism. These components synergistically capture complex temporal and spectral EEG dynamics, enabling FoME to adapt to varying patterns across diverse data streams and facilitate robust multi-channel modeling. Evaluations across four downstream tasks demonstrate FoME's superior performance in classification and forecasting applications, consistently achieving state-of-the-art results. To conclude, FoME establishes a new paradigm for EEG analysis, offering a versatile foundation that advances brain-computer interfaces, clinical diagnostics, and cognitive research across neuroscience and related fields. Our code will be available at https://github.com/1061413241/FoME.
Arena 4.0: A Comprehensive ROS2 Development and Benchmarking Platform for Human-centric Navigation Using Generative-Model-based Environment Generation
Venue: arXiv cs.RO 2024
Year: 2024

Building on the foundations of our previous work, this paper introduces Arena 4.0, a significant advancement over Arena 3.0, Arena-Bench, Arena 1.0, and Arena 2.0. Arena 4.0 offers three key novel contributions: (1) a generative-model-based world and scenario generation approach that utilizes large language models (LLMs) and diffusion models to dynamically generate complex, human-centric environments from text prompts or 2D floorplans, useful for the development and benchmarking of social navigation strategies; (2) a comprehensive 3D model database, extendable with additional 3D assets that are semantically linked and annotated for dynamic spawning and arrangement within 3D worlds; and (3) a complete migration to ROS 2, enabling compatibility with modern hardware and enhanced functionalities for improved navigation, usability, and easier deployment on real robots. We evaluated the platform's performance through a comprehensive user study, demonstrating significant improvements in usability and efficiency compared to previous versions. Arena 4.0 is openly available at https://github.com/Arena-Rosnav.
Reference Dataset and Benchmark for Reconstructing Laser Parameters from On-axis Video in Powder Bed Fusion of Bulk Stainless Steel
Venue: arXiv cs.CV 2024
Year: 2024

We present RAISE-LPBF, a large dataset on the effect of laser power and laser dot speed in powder bed fusion (LPBF) of 316L stainless steel bulk material, monitored by on-axis 20k FPS video. Both process parameters are independently sampled for each scan line from a continuous distribution, so interactions of different parameter choices can be investigated. The data can be used to derive statistical properties of LPBF, as well as to build anomaly detectors. We provide example source code for loading the data, baseline machine learning models and results, and a public benchmark to evaluate predictive models.