OpenRaiser/Intern-Atlas huggingface dataset:
Isolated Suborders and their Application to Counting Closure Operators
Venue: arXiv cs.DM 2024
Year: 2024

In this paper we investigate the interplay between isolated suborders and closures. Isolated suborders are a special kind of suborders and can be used to diminish the number of elements of an ordered set by means of a quotient construction. The decisive point is that there are simple formulae establishing relationships between the number of closures in the original ordered set and the quotient thereof induced by isolated suborders. We show how these connections can be used to derive a recursive algorithm for counting closures, provided the ordered set under consideration contains suitable isolated suborders.
Ensemble learning for Physics Informed Neural Networks: a Gradient Boosting approach
Venue: arXiv cs.LG 2024
Year: 2024

While the popularity of physics-informed neural networks (PINNs) is steadily rising, to this date, PINNs have not been successful in simulating multi-scale and singular perturbation problems. In this work, we present a new training paradigm referred to as "gradient boosting" (GB), which significantly enhances the performance of physics informed neural networks (PINNs). Rather than learning the solution of a given PDE using a single neural network directly, our algorithm employs a sequence of neural networks to achieve a superior outcome. This approach allows us to solve problems presenting great challenges for traditional PINNs. Our numerical experiments demonstrate the effectiveness of our algorithm through various benchmarks, including comparisons with finite element methods and PINNs. Furthermore, this work also unlocks the door to employing ensemble learning techniques in PINNs, providing opportunities for further improvement in solving PDEs.
A Finite Sample Complexity Bound for Distributionally Robust Q-learning
Venue: arXiv cs.LG 2024
Year: 2024

We consider a reinforcement learning setting in which the deployment environment is different from the training environment. Applying a robust Markov decision processes formulation, we extend the distributionally robust $Q$-learning framework studied in Liu et al. [2022]. Further, we improve the design and analysis of their multi-level Monte Carlo estimator. Assuming access to a simulator, we prove that the worst-case expected sample complexity of our algorithm to learn the optimal robust $Q$-function within an $ε$ error in the sup norm is upper bounded by $\tilde O(|S||A|(1-γ)^{-5}ε^{-2}p_{\wedge}^{-6}δ^{-4})$, where $γ$ is the discount rate, $p_{\wedge}$ is the non-zero minimal support probability of the transition kernels and $δ$ is the uncertainty size. This is the first sample complexity result for the model-free robust RL problem. Simulation studies further validate our theoretical results.
Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
Venue: arXiv cs.GT 2024
Year: 2024

We study fair allocation of resources consisting of both divisible and indivisible goods to agents with additive valuations. When only divisible or indivisible goods exist, it is known that an allocation that achieves the maximum Nash welfare (MNW) satisfies the classic fairness notions based on envy. Moreover, the literature shows the structures and characterizations of MNW allocations when valuations are binary and linear (i.e., divisible goods are homogeneous). In this paper, we show that when all agents' valuations are binary linear, an MNW allocation for mixed goods satisfies the envy-freeness up to any good for mixed goods (EFXM). This notion is stronger than an existing one called envy-freeness for mixed goods (EFM), and our result generalizes the existing results for the case when only divisible or indivisible goods exist. When all agents' valuations are binary over indivisible goods and identical over divisible goods (e.g., the divisible good is money), we extend the known characterization of an MNW allocation for indivisible goods to mixed goods, and also show that an MNW allocation satisfies EFXM. For the general additive valuations, we also provide a formal proof that an MNW allocation satisfies a weaker notion than EFM.
Decentralized Learning Made Practical with Client Sampling
Venue: arXiv cs.DC 2024
Year: 2024

Decentralized learning (DL) leverages edge devices for collaborative model training while avoiding coordination by a central server. Due to privacy concerns, DL has become an attractive alternative to centralized learning schemes since training data never leaves the device. In a round of DL, all nodes participate in model training and exchange their model with some other nodes. Performing DL in large-scale heterogeneous networks results in high communication costs and prolonged round durations due to slow nodes, effectively inflating the total training time. Furthermore, current DL algorithms also assume all nodes are available for training and aggregation at all times, diminishing the practicality of DL. This paper presents Plexus, an efficient, scalable, and practical DL system. Plexus (1) avoids network-wide participation by introducing a decentralized peer sampler that selects small subsets of available nodes that train the model each round and, (2) aggregates the trained models produced by nodes every round. Plexus is designed to handle joining and leaving nodes (churn). We extensively evaluate Plexus by incorporating realistic traces for compute speed, pairwise latency, network capacity, and availability of edge devices in our experiments. Our experiments on four common learning tasks empirically show that Plexus reduces time-to-accuracy by 1.2-8.3x, communication volume by 2.4-15.3x and training resources needed for convergence by 6.4-370x compared to baseline DL algorithms.
SpikeGPT: Generative Pre-trained Language Model with Spiking Neural Networks
Venue: arXiv cs.CL 2024
Year: 2024

As the size of large language models continue to scale, so does the computational resources required to run it. Spiking Neural Networks (SNNs) have emerged as an energy-efficient approach to deep learning that leverage sparse and event-driven activations to reduce the computational overhead associated with model inference. While they have become competitive with non-spiking models on many computer vision tasks, SNNs have also proven to be more challenging to train. As a result, their performance lags behind modern deep learning, and we are yet to see the effectiveness of SNNs in language generation. In this paper, inspired by the Receptance Weighted Key Value (RWKV) language model, we successfully implement `SpikeGPT', a generative language model with binary, event-driven spiking activation units. We train the proposed model on two model variants: 45M and 216M parameters. To the best of our knowledge, SpikeGPT is the largest backpropagation-trained SNN model to date, rendering it suitable for both the generation and comprehension of natural language. We achieve this by modifying the transformer block to replace multi-head self attention to reduce quadratic computational complexity O(N^2) to linear complexity O(N) with increasing sequence length. Input tokens are instead streamed in sequentially to our attention mechanism (as with typical SNNs). Our preliminary experiments show that SpikeGPT remains competitive with non-spiking models on tested benchmarks, while maintaining 20x fewer operations when processed on neuromorphic hardware that can leverage sparse, event-driven activations. Our code implementation is available at https://github.com/ridgerchu/SpikeGPT.
Multi-Layer Attention-Based Explainability via Transformers for Tabular Data
Venue: arXiv cs.LG 2024
Year: 2024

We propose a graph-oriented attention-based explainability method for tabular data. Tasks involving tabular data have been solved mostly using traditional tree-based machine learning models which have the challenges of feature selection and engineering. With that in mind, we consider a transformer architecture for tabular data, which is amenable to explainability, and present a novel way to leverage self-attention mechanism to provide explanations by taking into account the attention matrices of all heads and layers as a whole. The matrices are mapped to a graph structure where groups of features correspond to nodes and attention values to arcs. By finding the maximum probability paths in the graph, we identify groups of features providing larger contributions to explain the model's predictions. To assess the quality of multi-layer attention-based explanations, we compare them with popular attention-, gradient-, and perturbation-based explanability methods.
Beamforming and Device Selection Design in Federated Learning with Over-the-air Aggregation
Venue: arXiv cs.IT 2024
Year: 2024

Federated learning (FL) with over-the-air computation can efficiently utilize the communication bandwidth but is susceptible to analog aggregation error. Excluding those devices with weak channel conditions can reduce the aggregation error, but it also limits the amount of local training data for FL, which can reduce the training convergence rate. In this work, we jointly design uplink receiver beamforming and device selection for over-the-air FL over time-varying wireless channels to maximize the training convergence rate. We reformulate this stochastic optimization problem into a mixed-integer program using an upper bound on the global training loss over communication rounds. We then propose a Greedy Spatial Device Selection (GSDS) approach, which uses a sequential procedure to select devices based on a measure capturing both the channel strength and the channel correlation to the selected devices. We show that given the selected devices, the receiver beamforming optimization problem is equivalent to downlink single-group multicast beamforming. To reduce the computational complexity, we also propose an Alternating-optimization-based Device Selection and Beamforming (ADSBF) approach, which solves the receiver beamforming and device selection subproblems alternatingly. In particular, despite the device selection being an integer problem, we are able to develop an efficient algorithm to find its optimal solution. Simulation results with real-world image classification demonstrate that our proposed methods achieve faster convergence with significantly lower computational complexity than existing alternatives. Furthermore, although ADSBF shows marginally inferior performance to GSDS, it offers the advantage of lower computational complexity when the number of devices is large.
Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
Venue: arXiv cs.NE 2024
Year: 2024

The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take $r$ different values, the time for genetic drift to become significant is $r$ times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen $r$ times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the $r$-valued \leadingones problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in $O(r\ln(r)^2 n^2 \ln(n))$ function evaluations. This bound is nearly tight as our lower bound $Ω(r\ln(r) n^2 \ln(n))$ shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.
Design, Kinematics, and Deployment of a Continuum Underwater Vehicle-Manipulator System
Venue: arXiv cs.RO 2024
Year: 2024

Underwater vehicle-manipulator systems (UVMSs) are underwater robots equipped with one or more manipulators to perform intervention missions. This paper provides the mechanical, electrical, and software design of a novel UVMS equipped with a continuum manipulator, referred to as a continuum-UVMS. A kinematic model for the continuum-UVMS is derived in order to build an algorithm to resolve the robot's redundancy and generate joint space commands. Different methods to optimize the trajectory for specific tasks are proposed using both the weighted least norm solution and the gradient projection method. Kinematic simulation results are analyzed to assess the performance of the proposed algorithm. Finally, the continuum-UVMS is deployed in an experimental demonstration in which both teleoperation and autonomous control are tested for a given reference trajectory.
Representation Disentaglement via Regularization by Causal Identification
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we propose the use of a causal collider structured model to describe the underlying data generative process assumptions in disentangled representation learning. This extends the conventional i.i.d. factorization assumption model $p(\mathbf{y}) = \prod_{i} p(\mathbf{y}_i )$, inadequate to handle learning from biased datasets (e.g., with sampling selection bias). The collider structure, explains that conditional dependencies between the underlying generating variables may be exist, even when these are in reality unrelated, complicating disentanglement. Under the rubric of causal inference, we show this issue can be reconciled under the condition of causal identification; attainable from data and a combination of constraints, aimed at controlling the dependencies characteristic of the \textit{collider} model. For this, we propose regularization by identification (ReI), a modular regularization engine designed to align the behavior of large scale generative models with the disentanglement constraints imposed by causal identification. Empirical evidence on standard benchmarks demonstrates the superiority of ReI in learning disentangled representations in a variational framework. In a real-world dataset we additionally show that our framework, results in interpretable representations robust to out-of-distribution examples and that align with the true expected effect from domain knowledge.
Meal-time Detection by Means of Long Periods Blood Glucose Level Monitoring via IoT Technology
Venue: arXiv cs.HC 2024
Year: 2024

Blood glucose level monitoring is of great importance, especially for subjects experiencing type 1 diabetes. Accurate monitoring of their blood glucose level prevents dangerous and life-threatening situations that might be experienced by those subjects. In addition, precise monitoring of blood glucose levels over long periods of time helps establishing knowledge about the daily mealtime routine which aids the medical staff to monitor subjects and properly intervene in hazardous cases such as hypo- or hyperglycemia. Establishing such knowledge will play a potential role when designing proper treatment intervention plan. In this research, we present a complete IoT framework, starting from hardware acquisition system to data analysis approaches that gives a hand for medical staff when long periods of blood glucose monitoring are essential for subjects. Also, this framework is validated with real-time data collection from 7 subjects over 10 successive days with temporal resolution of 5 minutes allowing for near real-time monitoring and analysis. Our results show the precisely estimated daily mealtime routines for 4 subjects out of the 7 with discard of 3 subjects due to huge data loss mainly. The daily mealtime routines for the 4 subjects are found to be matching to have a pattern of 4 periods of blood glucose level changes corresponding to the breakfast around 8 AM, the lunch around 5 PM, the dinner around 8 PM, and finally a within-day snack around 12 PM. The research shows the potential of IoT ecosystem in support for medically related studies.
DeFNet: Deconstructed Strategy for Multi-step Fabric Folding Tasks
Venue: arXiv cs.RO 2024
Year: 2024

Fabric folding through robots is complex and challenging due to the deformability of fabric. Based on deconstruction strategy, we split the complex fabric folding task into three relatively simple sub-tasks, and propose a Deconstructed Fabric Folding Network (DeFNet), including corresponding three modules to solve them. (1) We use the Folding Planning Module (FPM), which is based on Latent Space Roadmap, to infer the most straight folding intermediate states from the start to the goal in latent space. (2) We utilize the flow-based approach, Folding Action Module (FAM), to calculate the action coordinates and execute them to reach the inferred intermediate state. (3) We introduce an Iterative Interactive Module (IIM) for fabric folding tasks, which can iteratively execute the FPM and FAM after every grasp-and-place action until the fabric reaches the goal. Experimentally, We demonstrated our method on multi-step fabric folding tasks against three baselines in simulation. We also apply the method to an existing robotic system and present its performance.
Exploring Epipolar Consistency Conditions for Rigid Motion Compensation in In-vivo X-ray Microscopy
Venue: arXiv cs.CV 2024
Year: 2024

Intravital X-ray microscopy (XRM) in preclinical mouse models is of vital importance for the identification of microscopic structural pathological changes in the bone which are characteristic of osteoporosis. The complexity of this method stems from the requirement for high-quality 3D reconstructions of the murine bones. However, respiratory motion and muscle relaxation lead to inconsistencies in the projection data which result in artifacts in uncompensated reconstructions. Motion compensation using epipolar consistency conditions (ECC) has previously shown good performance in clinical CT settings. Here, we explore whether such algorithms are suitable for correcting motion-corrupted XRM data. Different rigid motion patterns are simulated and the quality of the motion-compensated reconstructions is assessed. The method is able to restore microscopic features for out-of-plane motion, but artifacts remain for more realistic motion patterns including all six degrees of freedom of rigid motion. Therefore, ECC is valuable for the initial alignment of the projection data followed by further fine-tuning of motion parameters using a reconstruction-based method.
Has the Virtualization of the Face Changed Facial Perception? A Study of the Impact of Photo Editing and Augmented Reality on Facial Perception
Venue: arXiv cs.HC 2024
Year: 2024

Augmented reality and other photo editing filters are popular methods used to modify faces online. Considering the important role of facial perception in communication, how do we perceive this increasing number of modified faces? In this paper we present the results of six surveys that measure familiarity with different styles of facial filters, perceived strangeness of faces edited with different filters, and ability to discern whether images are filtered. Our results demonstrate that faces modified with more traditional face filters are perceived similarly to unmodified faces, and faces filtered with augmented reality filters are perceived differently from unmodified faces. We discuss possible explanations for these results, including a societal adjustment to traditional photo editing techniques or the inherent differences in the different types of filters. We conclude with a discussion of how to build online spaces more responsibly based on our results.
A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
Venue: arXiv cs.NE 2024
Year: 2024

There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve using a drone in conjunction with a truck for package delivery. This study presents a hybrid genetic algorithm for solving TSPD and FSTSP by incorporating local search and dynamic programming. Similar algorithms exist in the literature. Our algorithm, however, considers more sophisticated chromosomes and less computationally complex dynamic programming to enable broader exploration by the genetic algorithm and efficient exploitation through dynamic programming and local search. The key contribution of this paper is the discovery of how decision-making processes for solving TSPD and FSTSP should be divided among the layers of genetic algorithm, dynamic programming, and local search. In particular, our genetic algorithm generates the truck and the drone sequences separately and encodes them in a type-aware chromosome, wherein each customer is assigned to either the truck or the drone. We apply local search to each chromosome, which is decoded by dynamic programming for fitness evaluation. Our new algorithm is shown to outperform existing algorithms on most benchmark instances in both quality and time. Our algorithms found the new best solutions for 538 TSPD instances out of 920 and 74 FSTSP instances out of 132.
ESceme: Vision-and-Language Navigation with Episodic Scene Memory
Venue: arXiv cs.CV 2024
Year: 2024

Vision-and-language navigation (VLN) simulates a visual agent that follows natural-language navigation instructions in real-world scenes. Existing approaches have made enormous progress in navigation in new environments, such as beam search, pre-exploration, and dynamic or hierarchical history encoding. To balance generalization and efficiency, we resort to memorizing visited scenarios apart from the ongoing route while navigating. In this work, we introduce a mechanism of Episodic Scene memory (ESceme) for VLN that wakes an agent's memories of past visits when it enters the current scene. The episodic scene memory allows the agent to envision a bigger picture of the next prediction. This way, the agent learns to utilize dynamically updated information instead of merely adapting to the current observations. We provide a simple yet effective implementation of ESceme by enhancing the accessible views at each location and progressively completing the memory while navigating. We verify the superiority of ESceme on short-horizon (R2R), long-horizon (R4R), and vision-and-dialog (CVDN) VLN tasks. Our ESceme also wins first place on the CVDN leaderboard. Code is available: \url{https://github.com/qizhust/esceme}.