OpenRaiser/Intern-Atlas huggingface dataset:
DRIVE: Dual Gradient-Based Rapid Iterative Pruning
Venue: arXiv cs.LG 2024
Year: 2024

Modern deep neural networks (DNNs) consist of millions of parameters, necessitating high-performance computing during training and inference. Pruning is one solution that significantly reduces the space and time complexities of DNNs. Traditional pruning methods that are applied post-training focus on streamlining inference, but there are recent efforts to leverage sparsity early on by pruning before training. Pruning methods, such as iterative magnitude-based pruning (IMP) achieve up to a 90% parameter reduction while retaining accuracy comparable to the original model. However, this leads to impractical runtime as it relies on multiple train-prune-reset cycles to identify and eliminate redundant parameters. In contrast, training agnostic early pruning methods, such as SNIP and SynFlow offer fast pruning but fall short of the accuracy achieved by IMP at high sparsities. To bridge this gap, we present Dual Gradient-Based Rapid Iterative Pruning (DRIVE), which leverages dense training for initial epochs to counteract the randomness inherent at the initialization. Subsequently, it employs a unique dual gradient-based metric for parameter ranking. It has been experimentally demonstrated for VGG and ResNet architectures on CIFAR-10/100 and Tiny ImageNet, and ResNet on ImageNet that DRIVE consistently has superior performance over other training-agnostic early pruning methods in accuracy. Notably, DRIVE is 43$\times$ to 869$\times$ faster than IMP for pruning.
Improvement of Performance in Freezing of Gait detection in Parkinsons Disease using Transformer networks and a single waist worn triaxial accelerometer
Venue: arXiv cs.LG 2024
Year: 2024

Freezing of gait (FOG) is one of the most incapacitating symptoms in Parkinsons disease, affecting more than 50 percent of patients in advanced stages of the disease. The presence of FOG may lead to falls and a loss of independence with a consequent reduction in the quality of life. Wearable technology and artificial intelligence have been used for automatic FOG detection to optimize monitoring. However, differences between laboratory and daily-life conditions present challenges for the implementation of reliable detection systems. Consequently, improvement of FOG detection methods remains important to provide accurate monitoring mechanisms intended for free-living and real-time use. This paper presents advances in automatic FOG detection using a single body-worn triaxial accelerometer and a novel classification algorithm based on Transformers and convolutional networks. This study was performed with data from 21 patients who manifested FOG episodes while performing activities of daily living in a home setting. Results indicate that the proposed FOG-Transformer can bring a significant improvement in FOG detection using leave-one-subject-out cross-validation (LOSO CV). These results bring opportunities for the implementation of accurate monitoring systems for use in ambulatory or home settings.
Self-organized free-flight arrival for urban air mobility
Venue: arXiv cs.LG 2024
Year: 2024

Urban air mobility is an innovative mode of transportation in which electric vertical takeoff and landing (eVTOL) vehicles operate between nodes called vertiports. We outline a self-organized vertiport arrival system based on deep reinforcement learning. The airspace around the vertiport is assumed to be circular, and the vehicles can freely operate inside. Each aircraft is considered an individual agent and follows a shared policy, resulting in decentralized actions that are based on local information. We investigate the development of the reinforcement learning policy during training and illustrate how the algorithm moves from suboptimal local holding patterns to a safe and efficient final policy. The latter is validated in simulation-based scenarios, including robustness analyses against sensor noise and a changing distribution of inbound traffic. Lastly, we deploy the final policy on small-scale unmanned aerial vehicles to showcase its real-world usability.
Optimization of resources for digital radio transmission over IBOC FM through max-min fairness
Venue: arXiv cs.IT 2024
Year: 2024

The equitable distribution of resources in a network is a complex process, considering that not all nodes have the same requirements, and the In-Band On-Channel (IBOC) hybrid transmission system is no exception. The IBOC system utilizes a hybrid in-band transmission to simultaneously broadcast analog and digital audio over the FM band. This article proposes the use of a Max-Min Fairness (MMF) algorithm, with a strategy to optimize resource allocation for IBOC FM transmission in a multiservice scenario. Additionally, the MMF algorithm offers low computational complexity for implementation in low-cost embedded systems, aiming to achieve fair resource distribution and provide adequate Quality of Service (QoS) levels for each node in the RF network, considering channel conditions and traffic types. The article explores a scenario under saturated traffic conditions to assess the optimization capabilities of the MMF algorithm under well-defined traffic and channel conditions. The evaluation process yielded highly favorable results, indicating that theMMF algorithm can be considered a viable alternative for bandwidth optimization in digital broadcasting over IBOC on FM with 95% confidence, and it holds potential for implementation in other digital broadcasting system.
I Did Not Notice: A Comparison of Immersive Analytics with Augmented and Virtual Reality
Venue: arXiv cs.HC 2024
Year: 2024

Immersive environments enable users to engage in embodied interaction, enhancing the sensemaking processes involved in completing tasks such as immersive analytics. Previous comparative studies on immersive analytics using augmented and virtual realities have revealed that users employ different strategies for data interpretation and text-based analytics depending on the environment. Our study seeks to investigate how augmented and virtual reality influences sensemaking processes in quantitative immersive analytics. Our results, derived from a diverse group of participants, indicate that users demonstrate comparable performance in both environments. However, it was observed that users exhibit a higher tolerance for cognitive load in VR and travel further in AR. Based on our findings, we recommend providing users with the option to switch between AR and VR, thereby enabling them to select an environment that aligns with their preferences and task requirements.
Accounting for Hysteresis in the Forward Kinematics of Nonlinearly-Routed Tendon-Driven Continuum Robots via a Learned Deep Decoder Network
Venue: arXiv cs.RO 2024
Year: 2024

Tendon-driven continuum robots have been gaining popularity in medical applications due to their ability to curve around complex anatomical structures, potentially reducing the invasiveness of surgery. However, accurate modeling is required to plan and control the movements of these flexible robots. Physics-based models have limitations due to unmodeled effects, leading to mismatches between model prediction and actual robot shape. Recently proposed learning-based methods have been shown to overcome some of these limitations but do not account for hysteresis, a significant source of error for these robots. To overcome these challenges, we propose a novel deep decoder neural network that predicts the complete shape of tendon-driven robots using point clouds as the shape representation, conditioned on prior configurations to account for hysteresis. We evaluate our method on a physical tendon-driven robot and show that our network model accurately predicts the robot's shape, significantly outperforming a state-of-the-art physics-based model and a learning-based model that does not account for hysteresis.
CantTalkAboutThis: Aligning Language Models to Stay on Topic in Dialogues
Venue: arXiv cs.CL 2024
Year: 2024

Recent advancements in instruction-tuning datasets have predominantly focused on specific tasks like mathematical or logical reasoning. There has been a notable gap in data designed for aligning language models to maintain topic relevance in conversations - a critical aspect for deploying chatbots to production. We introduce the CantTalkAboutThis dataset to help language models remain focused on the subject at hand during task-oriented interactions. It consists of synthetic dialogues on a wide range of conversation topics from different domains. These dialogues are interspersed with distractor turns that intentionally divert the chatbot from the predefined topic. Fine-tuning language models on this dataset helps make them resilient to deviating from the role assigned and improves their ability to maintain topical coherence compared to general-purpose instruction-tuned LLMs like GPT-4-turbo and Mixtral-Instruct. Additionally, preliminary observations suggest that training models on this dataset also enhance their performance on fine-grained instruction following tasks, including safety alignment.
A Bi-consolidating Model for Joint Relational Triple Extraction
Venue: arXiv cs.CL 2024
Year: 2024

Current methods to extract relational triples directly make a prediction based on a possible entity pair in a raw sentence without depending on entity recognition. The task suffers from a serious semantic overlapping problem, in which several relation triples may share one or two entities in a sentence. In this paper, based on a two-dimensional sentence representation, a bi-consolidating model is proposed to address this problem by simultaneously reinforcing the local and global semantic features relevant to a relation triple. This model consists of a local consolidation component and a global consolidation component. The first component uses a pixel difference convolution to enhance semantic information of a possible triple representation from adjacent regions and mitigate noise in neighbouring neighbours. The second component strengthens the triple representation based a channel attention and a spatial attention, which has the advantage to learn remote semantic dependencies in a sentence. They are helpful to improve the performance of both entity identification and relation type classification in relation triple extraction. After evaluated on several publish datasets, the bi-consolidating model achieves competitive performance. Analytical experiments demonstrate the effectiveness of our model for relational triple extraction and give motivation for other natural language processing tasks.
SLSM : An Efficient Strategy for Lazy Schema Migration on Shared-Nothing Databases
Venue: arXiv cs.DB 2024
Year: 2024

By introducing intermediate states for metadata changes and ensuring that at most two versions of metadata exist in the cluster at the same time, shared-nothing databases are capable of making online, asynchronous schema changes. However, this method leads to delays in the deployment of new schemas since it requires waiting for massive data backfill. To shorten the service vacuum period before the new schema is available, this paper proposes a strategy named SLSM for zero-downtime schema migration on shared-nothing databases. Based on the lazy migration of stand-alone databases, SLSM keeps the old and new schemas with the same data distribution, reducing the node communication overhead of executing migration transactions for shared-nothing databases. Further, SLSM combines migration transactions with user transactions by extending the distributed execution plan to allow the data involved in migration transactions to directly serve user transactions, greatly reducing the waiting time of user transactions. Experiments demonstrate that our strategy can greatly reduce the latency of user transactions and improve the efficiency of data migration compared to existing schemes.
Minor Containment and Disjoint Paths in almost-linear time
Venue: arXiv cs.DS 2024
Year: 2024

We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are computable. By the Graph Minor Theorem, this implies the existence of an $n^{1+o(1)}$-time membership test for every minor-closed class of graphs. More generally, we give an ${\cal O}_{H,|X|}(m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which $G$ comes with a set of roots $X\subseteq V(G)$ and some of the branch sets of the sought minor model of $H$ are required to contain prescribed subsets of $X$; here, $m$ is the total number of vertices and edges of $G$. This captures the Disjoint Paths problem, for which we obtain an ${\cal O}_{k}(m^{1+o(1)})$-time algorithm, where $k$ is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of $G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.
Game-theoretic Distributed Learning Approach for Heterogeneous-cost Task Allocation with Budget Constraints
Venue: arXiv cs.GT 2024
Year: 2024

This paper investigates heterogeneous-cost task allocation with budget constraints (HCTAB), wherein heterogeneity is manifested through the varying capabilities and costs associated with different agents for task execution. Different from the centralized optimization-based method, the HCTAB problem is solved using a fully distributed framework, and a coalition formation game is introduced to provide a theoretical guarantee for this distributed framework. To solve the coalition formation game, a convergence-guaranteed log-linear learning algorithm based on heterogeneous cost is proposed. This algorithm incorporates two improvement strategies, namely, a cooperative exchange strategy and a heterogeneous-cost log-linear learning strategy. These strategies are specifically designed to be compatible with the heterogeneous cost and budget constraints characteristic of the HCTAB problem. Through ablation experiments, we demonstrate the effectiveness of these two improvements. Finally, numerical results show that the proposed algorithm outperforms existing task allocation algorithms and learning algorithms in terms of solving the HCTAB problem.
Random Walk in Random Permutation Set Theory
Venue: arXiv cs.AI 2024
Year: 2024

Random walk is an explainable approach for modeling natural processes at the molecular level. The Random Permutation Set Theory (RPST) serves as a framework for uncertainty reasoning, extending the applicability of Dempster-Shafer Theory. Recent explorations indicate a promising link between RPST and random walk. In this study, we conduct an analysis and construct a random walk model based on the properties of RPST, with Monte Carlo simulations of such random walk. Our findings reveal that the random walk generated through RPST exhibits characteristics similar to those of a Gaussian random walk and can be transformed into a Wiener process through a specific limiting scaling procedure. This investigation establishes a novel connection between RPST and random walk theory, thereby not only expanding the applicability of RPST, but also demonstrating the potential for combining the strengths of both approaches to improve problem-solving abilities.
Approximate UMAP allows for high-rate online visualization of high-dimensional data streams
Venue: arXiv cs.LG 2024
Year: 2024

In the BCI field, introspection and interpretation of brain signals are desired for providing feedback or to guide rapid paradigm prototyping but are challenging due to the high noise level and dimensionality of the signals. Deep neural networks are often introspected by transforming their learned feature representations into 2- or 3-dimensional subspace visualizations using projection algorithms like Uniform Manifold Approximation and Projection (UMAP). Unfortunately, these methods are computationally expensive, making the projection of data streams in real-time a non-trivial task. In this study, we introduce a novel variant of UMAP, called approximate UMAP (aUMAP). It aims at generating rapid projections for real-time introspection. To study its suitability for real-time projecting, we benchmark the methods against standard UMAP and its neural network counterpart parametric UMAP. Our results show that approximate UMAP delivers projections that replicate the projection space of standard UMAP while decreasing projection speed by an order of magnitude and maintaining the same training time.
From Theory to Comprehension: A Comparative Study of Differential Privacy and $k$-Anonymity
Venue: arXiv cs.CR 2024
Year: 2024

The notion of $\varepsilon$-differential privacy is a widely used concept of providing quantifiable privacy to individuals. However, it is unclear how to explain the level of privacy protection provided by a differential privacy mechanism with a set $\varepsilon$. In this study, we focus on users' comprehension of the privacy protection provided by a differential privacy mechanism. To do so, we study three variants of explaining the privacy protection provided by differential privacy: (1) the original mathematical definition; (2) $\varepsilon$ translated into a specific privacy risk; and (3) an explanation using the randomized response technique. We compare users' comprehension of privacy protection employing these explanatory models with their comprehension of privacy protection of $k$-anonymity as baseline comprehensibility. Our findings suggest that participants' comprehension of differential privacy protection is enhanced by the privacy risk model and the randomized response-based model. Moreover, our results confirm our intuition that privacy protection provided by $k$-anonymity is more comprehensible.
A Dataset for Physical and Abstract Plausibility and Sources of Human Disagreement
Venue: arXiv cs.CL 2024
Year: 2024

We present a novel dataset for physical and abstract plausibility of events in English. Based on naturally occurring sentences extracted from Wikipedia, we infiltrate degrees of abstractness, and automatically generate perturbed pseudo-implausible events. We annotate a filtered and balanced subset for plausibility using crowd-sourcing, and perform extensive cleansing to ensure annotation quality. In-depth quantitative analyses indicate that annotators favor plausibility over implausibility and disagree more on implausible events. Furthermore, our plausibility dataset is the first to capture abstractness in events to the same extent as concreteness, and we find that event abstractness has an impact on plausibility ratings: more concrete event participants trigger a perception of implausibility.
Discrete Fréchet Distance Oracles
Venue: arXiv cs.CG 2024
Year: 2024

It is unlikely that the discrete Fréchet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, $P$, is known in advance. In particular, we wish to construct data structures (distance oracles) of near-linear size that support efficient distance queries with respect to $P$ in sublinear time. Since there is evidence that this is impossible for query curves of length $Θ(n^α)$, for any $α> 0$, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, $t$-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph $G$ in the family, so that, given a query segment and a pair $u,v$ of vertices in $G$, one can quickly compute the smallest discrete Fréchet distance between the segment and any $(u,v)$-path in $G$. The answer is exact, if $t=1$, and approximate if $t>1$.
VoicePilot: Harnessing LLMs as Speech Interfaces for Physically Assistive Robots
Venue: arXiv cs.RO 2024
Year: 2024

Physically assistive robots present an opportunity to significantly increase the well-being and independence of individuals with motor impairments or other forms of disability who are unable to complete activities of daily living. Speech interfaces, especially ones that utilize Large Language Models (LLMs), can enable individuals to effectively and naturally communicate high-level commands and nuanced preferences to robots. Frameworks for integrating LLMs as interfaces to robots for high level task planning and code generation have been proposed, but fail to incorporate human-centric considerations which are essential while developing assistive interfaces. In this work, we present a framework for incorporating LLMs as speech interfaces for physically assistive robots, constructed iteratively with 3 stages of testing involving a feeding robot, culminating in an evaluation with 11 older adults at an independent living facility. We use both quantitative and qualitative data from the final study to validate our framework and additionally provide design guidelines for using LLMs as speech interfaces for assistive robots. Videos and supporting files are located on our project website: https://sites.google.com/andrew.cmu.edu/voicepilot/
ChoreoVis: Planning and Assessing Formations in Dance Choreographies
Venue: arXiv cs.HC 2024
Year: 2024

Sports visualization has developed into an active research field over the last decades. Many approaches focus on analyzing movement data recorded from unstructured situations, such as soccer. For the analysis of choreographed activities like formation dancing, however, the goal differs, as dancers follow specific formations in coordinated movement trajectories. To date, little work exists on how visual analytics methods can support such choreographed performances. To fill this gap, we introduce a new visual approach for planning and assessing dance choreographies. In terms of planning choreographies, we contribute a web application with interactive authoring tools and views for the dancers' positions and orientations, movement trajectories, poses, dance floor utilization, and movement distances. For assessing dancers' real-world movement trajectories, extracted by manual bounding box annotations, we developed a timeline showing aggregated trajectory deviations and a dance floor view for detailed trajectory comparison. Our approach was developed and evaluated in collaboration with dance instructors, showing that introducing visual analytics into this domain promises improvements in training efficiency for the future.