OpenRaiser/Intern-Atlas huggingface dataset:
Measurement-Driven Design and Runtime Optimization in Edge Computing: Methodology and Tools
Venue: arXiv cs.NI 2023
Year: 2023

Edge computing is projected to become the dominant form of cloud computing in the future because of the significant advantages it brings to both users (less latency, higher throughput) and telecom operators (less Internet traffic, more local management). However, to fully unlock its potential at scale, system designers and automated optimization systems alike will have to monitor closely the dynamics of both processing and communication facilities. Especially the latter is often neglected in current systems since network performance in cloud computing plays only a minor role. In this paper, we propose the architecture of MECPerf, which is a solution to collect network measurements in a live edge computing domain, to be collected for offline provisioning analysis and simulations, or to be provided in real-time for on-line system optimization. MECPerf has been validated in a realistic testbed funded by the European Commission (Fed4Fire+), and we describe here a summary of the results, which are fully available as open data and through a Python library to expedite their utilization. This is demonstrated via a use case involving the optimization of a system parameter for migrating clients in a federated edge computing system adopting the GSMA platform operator concept.
POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments
Venue: arXiv cs.RO 2023
Year: 2023

This paper focuses on Passable Obstacles Aware (POA) planner - a novel navigation method for two-wheeled robots in a highly cluttered environment. The navigation algorithm detects and classifies objects to distinguish two types of obstacles - passable and unpassable. Our algorithm allows two-wheeled robots to find a path through passable obstacles. Such a solution helps the robot working in areas inaccessible to standard path planners and find optimal trajectories in scenarios with a high number of objects in the robot's vicinity. The POA planner can be embedded into other planning algorithms and enables them to build a path through obstacles. Our method decreases path length and the total travel time to the final destination up to 43% and 39%, respectively, comparing to standard path planners such as GVD, A*, and RRT*
Clustered Cell-Free Multi-User MIMO Systems with Rate-Splitting
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we address two crucial challenges in the design of cell-free (CF) systems: degradation in the performance of CF systems by imperfect channel state information at the transmitter (CSIT) and high computational/signaling loads arising from the increasing number of distributed antennas and parameters to be exchanged. To mitigate the effects of imperfect CSIT, we employ rate-splitting (RS) multiple-access, which separates the messages into common and private streams. Unlike prior works, we present a clustered CF multi-user multiple-antenna framework with RS, which groups the transmit antennas in several clusters to reduce the computational and signaling loads. The proposed RS-CF system employs one common stream per cluster to exploit the network diversity. Furthermore, we propose new cluster-based linear precoders for this framework. We then devise a power allocation strategy for the common and private streams within clusters and derive closed-form expressions for the sum-rate performance of the proposed cluster-based RS-CF system. Numerical results show that the proposed clustered RS-CF system and algorithms outperform existing approaches. % in terms of the sum-rate.
Enabling Efficient, Reliable Real-World Reinforcement Learning with Approximate Physics-Based Models
Venue: arXiv cs.LG 2023
Year: 2023

We focus on developing efficient and reliable policy optimization strategies for robot learning with real-world data. In recent years, policy gradient methods have emerged as a promising paradigm for training control policies in simulation. However, these approaches often remain too data inefficient or unreliable to train on real robotic hardware. In this paper we introduce a novel policy gradient-based policy optimization framework which systematically leverages a (possibly highly simplified) first-principles model and enables learning precise control policies with limited amounts of real-world data. Our approach $1)$ uses the derivatives of the model to produce sample-efficient estimates of the policy gradient and $2)$ uses the model to design a low-level tracking controller, which is embedded in the policy class. Theoretical analysis provides insight into how the presence of this feedback controller overcomes key limitations of stand-alone policy gradient methods, while hardware experiments with a small car and quadruped demonstrate that our approach can learn precise control strategies reliably and with only minutes of real-world data.
Can Euclidean Symmetry be Leveraged in Reinforcement Learning and Planning?
Venue: arXiv cs.LG 2023
Year: 2023

In robotic tasks, changes in reference frames typically do not influence the underlying physical properties of the system, which has been known as invariance of physical laws.These changes, which preserve distance, encompass isometric transformations such as translations, rotations, and reflections, collectively known as the Euclidean group. In this work, we delve into the design of improved learning algorithms for reinforcement learning and planning tasks that possess Euclidean group symmetry. We put forth a theory on that unify prior work on discrete and continuous symmetry in reinforcement learning, planning, and optimal control. Algorithm side, we further extend the 2D path planning with value-based planning to continuous MDPs and propose a pipeline for constructing equivariant sampling-based planning algorithms. Our work is substantiated with empirical evidence and illustrated through examples that explain the benefits of equivariance to Euclidean symmetry in tackling natural control problems.
Video Frame Interpolation with Stereo Event and Intensity Camera
Venue: arXiv cs.CV 2023
Year: 2023

The stereo event-intensity camera setup is widely applied to leverage the advantages of both event cameras with low latency and intensity cameras that capture accurate brightness and texture information. However, such a setup commonly encounters cross-modality parallax that is difficult to be eliminated solely with stereo rectification especially for real-world scenes with complex motions and varying depths, posing artifacts and distortion for existing Event-based Video Frame Interpolation (E-VFI) approaches. To tackle this problem, we propose a novel Stereo Event-based VFI (SE-VFI) network (SEVFI-Net) to generate high-quality intermediate frames and corresponding disparities from misaligned inputs consisting of two consecutive keyframes and event streams emitted between them. Specifically, we propose a Feature Aggregation Module (FAM) to alleviate the parallax and achieve spatial alignment in the feature domain. We then exploit the fused features accomplishing accurate optical flow and disparity estimation, and achieving better interpolated results through flow-based and synthesis-based ways. We also build a stereo visual acquisition system composed of an event camera and an RGB-D camera to collect a new Stereo Event-Intensity Dataset (SEID) containing diverse scenes with complex motions and varying depths. Experiments on public real-world stereo datasets, i.e., DSEC and MVSEC, and our SEID dataset demonstrate that our proposed SEVFI-Net outperforms state-of-the-art methods by a large margin.
PAT: Parallel Attention Transformer for Visual Question Answering in Vietnamese
Venue: arXiv cs.CL 2023
Year: 2023

We present in this paper a novel scheme for multimodal learning named the Parallel Attention mechanism. In addition, to take into account the advantages of grammar and context in Vietnamese, we propose the Hierarchical Linguistic Features Extractor instead of using an LSTM network to extract linguistic features. Based on these two novel modules, we introduce the Parallel Attention Transformer (PAT), achieving the best accuracy compared to all baselines on the benchmark ViVQA dataset and other SOTA methods including SAAA and MCAN.
Zero-th Order Algorithm for Softmax Attention Optimization
Venue: arXiv cs.LG 2023
Year: 2023

Large language models (LLMs) have brought about significant transformations in human society. Among the crucial computations in LLMs, the softmax unit holds great importance. Its helps the model generating a probability distribution on potential subsequent words or phrases, considering a series of input words. By utilizing this distribution, the model selects the most probable next word or phrase, based on the assigned probabilities. The softmax unit assumes a vital function in LLM training as it facilitates learning from data through the adjustment of neural network weights and biases. With the development of the size of LLMs, computing the gradient becomes expensive. However, Zero-th Order method can approximately compute the gradient with only forward passes. In this paper, we present a Zero-th Order algorithm specifically tailored for Softmax optimization. We demonstrate the convergence of our algorithm, highlighting its effectiveness in efficiently computing gradients for large-scale LLMs. By leveraging the Zeroth-Order method, our work contributes to the advancement of optimization techniques in the context of complex language models.
Gender mobility in the labor market with skills-based matching models
Venue: arXiv cs.AI 2023
Year: 2023

Skills-based matching promises mobility of workers between different sectors and occupations in the labor market. In this case, job seekers can look for jobs they do not yet have experience in, but for which they do have relevant skills. Currently, there are multiple occupations with a skewed gender distribution. For skills-based matching, it is unclear if and how a shift in the gender distribution, which we call gender mobility, between occupations will be effected. It is expected that the skills-based matching approach will likely be data-driven, including computational language models and supervised learning methods. This work, first, shows the presence of gender segregation in language model-based skills representation of occupations. Second, we assess the use of these representations in a potential application based on simulated data, and show that the gender segregation is propagated by various data-driven skills-based matching models.These models are based on different language representations (bag of words, word2vec, and BERT), and distance metrics (static and machine learning-based). Accordingly, we show how skills-based matching approaches can be evaluated and compared on matching performance as well as on the risk of gender segregation. Making the gender segregation bias of models more explicit can help in generating healthy trust in the use of these models in practice.
A Novel Multiagent Flexibility Aggregation Framework
Venue: arXiv cs.AI 2023
Year: 2023

The increasing number of Distributed Energy Resources (DERs) in the emerging Smart Grid, has created an imminent need for intelligent multiagent frameworks able to utilize these assets efficiently. In this paper, we propose a novel DER aggregation framework, encompassing a multiagent architecture and various types of mechanisms for the effective management and efficient integration of DERs in the Grid. One critical component of our architecture is the Local Flexibility Estimators (LFEs) agents, which are key for offloading the Aggregator from serious or resource-intensive responsibilities -- such as addressing privacy concerns and predicting the accuracy of DER statements regarding their offered demand response services. The proposed framework allows the formation of efficient LFE cooperatives. To this end, we developed and deployed a variety of cooperative member selection mechanisms, including (a) scoring rules, and (b) (deep) reinforcement learning. We use data from the well-known PowerTAC simulator to systematically evaluate our framework. Our experiments verify its effectiveness for incorporating heterogeneous DERs into the Grid in an efficient manner. In particular, when using the well-known probabilistic prediction accuracy-incentivizing CRPS scoring rule as a selection mechanism, our framework results in increased average payments for participants, when compared with traditional commercial aggregators.
Improving End-to-End Speech Translation by Imitation-Based Knowledge Distillation with Synthetic Transcripts
Venue: arXiv cs.CL 2023
Year: 2023

End-to-end automatic speech translation (AST) relies on data that combines audio inputs with text translation outputs. Previous work used existing large parallel corpora of transcriptions and translations in a knowledge distillation (KD) setup to distill a neural machine translation (NMT) into an AST student model. While KD allows using larger pretrained models, the reliance of previous KD approaches on manual audio transcripts in the data pipeline restricts the applicability of this framework to AST. We present an imitation learning approach where a teacher NMT system corrects the errors of an AST student without relying on manual transcripts. We show that the NMT teacher can recover from errors in automatic transcriptions and is able to correct erroneous translations of the AST student, leading to improvements of about 4 BLEU points over the standard AST end-to-end baseline on the English-German CoVoST-2 and MuST-C datasets, respectively. Code and data are publicly available.\footnote{\url{https://github.com/HubReb/imitkd_ast/releases/tag/v1.1}}
Dense Affinity Matching for Few-Shot Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Few-Shot Segmentation (FSS) aims to segment the novel class images with a few annotated samples. In this paper, we propose a dense affinity matching (DAM) framework to exploit the support-query interaction by densely capturing both the pixel-to-pixel and pixel-to-patch relations in each support-query pair with the bidirectional 3D convolutions. Different from the existing methods that remove the support background, we design a hysteretic spatial filtering module (HSFM) to filter the background-related query features and retain the foreground-related query features with the assistance of the support background, which is beneficial for eliminating interference objects in the query background. We comprehensively evaluate our DAM on ten benchmarks under cross-category, cross-dataset, and cross-domain FSS tasks. Experimental results demonstrate that DAM performs very competitively under different settings with only 0.68M parameters, especially under cross-domain FSS tasks, showing its effectiveness and efficiency.
Fast Algorithms for Energy Games in Special Cases
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we study algorithms for special cases of energy games, a class of turn-based games on graphs that show up in the quantitative analysis of reactive systems. In an energy game, the vertices of a weighted directed graph belong either to Alice or to Bob. A token is moved to a next vertex by the player controlling its current location, and its energy is changed by the weight of the edge. Given a fixed starting vertex and initial energy, Alice wins the game if the energy of the token remains nonnegative at every moment. If the energy goes below zero at some point, then Bob wins. The problem of determining the winner in an energy game lies in $\mathsf{NP} \cap \mathsf{coNP}$. It is a long standing open problem whether a polynomial time algorithm for this problem exists. We devise new algorithms for three special cases of the problem. The first two results focus on the single-player version, where either Alice or Bob controls the whole game graph. We develop an $\tilde{O}(n^ωW^ω)$ time algorithm for a game graph controlled by Alice, by providing a reduction to the All-Pairs Nonnegative Prefix Paths problem (APNP). Thus we study the APNP problem separately, for which we develop an $\tilde{O}(n^ωW^ω)$ time algorithm. For both problems, we improve over the state of the art of $\tilde O(mn)$ for small $W$. For the APNP problem, we also provide a conditional lower bound which states that there is no $O(n^{3-ε})$ time algorithm for any $ε> 0$, unless the APSP Hypothesis fails. For a game graph controlled by Bob, we obtain a near-linear time algorithm. Regarding our third result, we present a variant of the value iteration algorithm, and we prove that it gives an $O(mn)$ time algorithm for game graphs without negative cycles, which improves a previous upper bound.
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
Venue: arXiv cs.DS 2023
Year: 2023

In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation, also known as the Santa Claus problem. For both of these problems the best approximation factor is a notorious open question; more precisely, whether there is a better-than-2 approximation for the former problem and whether there is a constant approximation for the latter. While the two problems are intuitively related and history has shown that techniques can often be transferred between them, no formal reductions are known. We first show that an affirmative answer to the open question for makespan minimization implies the same for the Santa Claus problem by reducing the latter problem to the former. We also prove that for problem instances with only two input values both questions are equivalent. We then move to a special case called ``restricted assignment'', which is well studied in both problems. Although our reductions do not maintain the characteristics of this special case, we give a reduction in a slight generalization, where the jobs or resources are assigned to multiple machines or players subject to a matroid constraint and in addition we have only two values. This draws a similar picture as before: equivalence for two values and the general case of Santa Claus can only be easier than makespan minimization. To complete the picture, we give an algorithm for our new matroid variant of the Santa Claus problem using a non-trivial extension of the local search method from restricted assignment. Thereby we unify, generalize, and improve several previous results. We believe that this matroid generalization may be of independent interest and provide several sample applications.
Towards eXplainable AI for Mobility Data Science
Venue: arXiv cs.AI 2023
Year: 2023

This paper presents our ongoing work towards XAI for Mobility Data Science applications, focusing on explainable models that can learn from dense trajectory data, such as GPS tracks of vehicles and vessels using temporal graph neural networks (GNNs) and counterfactuals. We review the existing GeoXAI studies, argue the need for comprehensible explanations with human-centered approaches, and outline a research path toward XAI for Mobility Data Science.
Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
Venue: arXiv cs.LO 2023
Year: 2023

This paper establishes alternative characterizations of very expressive classes of existential rule sets with decidable query entailment. We consider the notable class of greedy bounded-treewidth sets (gbts) and a new, generalized variant, called weakly gbts (wgbts). Revisiting and building on the notion of derivation graphs, we define (weakly) cycle-free derivation graph sets ((w)cdgs) and employ elaborate proof-theoretic arguments to obtain that gbts and cdgs coincide, as do wgbts and wcdgs. These novel characterizations advance our analytic proof-theoretic understanding of existential rules and will likely be instrumental in practice.
Approximation Algorithms for the Graph Burning on Cactus and Directed Trees
Venue: arXiv cs.DS 2023
Year: 2023

Given a graph $G=(V, E)$, the problem of Graph Burning is to find a sequence of nodes from $V$, called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a $ 3$-approximation algorithm for general graphs and a $ 2$-approximation algorithm for trees. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose 1) A $2.75$-approximation algorithm for a cactus graph (undirected), 2) A $3$-approximation algorithm for multi-rooted directed trees (polytree) and 3) A $1.905$-approximation algorithm for single-rooted directed tree (arborescence). We implement all the three approximation algorithms and the results are shown for randomly generated cactus graphs and directed trees.
Simulation of Stance Perturbations
Venue: arXiv cs.SI 2023
Year: 2023

In this work, we analyze the circumstances under which social influence operations are likely to succeed. These circumstances include the selection of Confederate agents to execute intentional perturbations and the selection of Perturbation strategies. We use Agent-Based Modelling (ABM) as a simulation technique to observe the effect of intentional stance perturbations on scale-free networks. We develop a co-evolutionary social influence model to interrogate the tradeoff between perturbing stance and maintaining influence when these variables are linked through homophily. In our experiments, we observe that stances in a network will converge in sufficient simulation timesteps, influential agents are the best Confederates and the optimal Perturbation strategy involves the cascade of local ego networks. Finally, our experimental results support the theory of tipping points and are in line with empirical findings suggesting that 20-25% of agents need to be Confederates before a change in consensus can be achieved.
Satellite Computing: A Case Study of Cloud-Native Satellites
Venue: arXiv cs.DC 2023
Year: 2023

The on-orbit processing of massive satellite-native data relies on powerful computing power. Satellite computing has started to gain attention, with researchers proposing various algorithms, applications, and simulation testbeds. Unfortunately, a practical platform for deploying satellite computing is currently lacking. As a result, the industry needs to make relentless efforts to achieve this goal. We suggest using cloud-native technology to enhance the computing power of LEO satellites. The first main satellite of the Tiansuan constellation, BUPT-1, is a significant example of a cloud-native satellite. Prior to delving into the details of BUPT-1, we define the essential concepts of cloud-native satellites, i.e., the cloud-native load and cloud-native platform. Afterwards, we present the design scheme of cloud-native satellites, including the architecture of BUPT-1 and the experimental subjects it can support. Two validation tests are shown to reflect the operation and capability of BUPT-1. Besides, we predict possible research fields that could shape the future of satellites in the next decade.