OpenRaiser/Intern-Atlas huggingface dataset:
POAR: Efficient Policy Optimization via Online Abstract State Representation Learning
Venue: arXiv cs.RO 2023
Year: 2023

While the rapid progress of deep learning fuels end-to-end reinforcement learning (RL), direct application, especially in high-dimensional space like robotic scenarios still suffers from low sample efficiency. Therefore State Representation Learning (SRL) is proposed to specifically learn to encode task-relevant features from complex sensory data into low-dimensional states. However, the pervasive implementation of SRL is usually conducted by a decoupling strategy in which the observation-state mapping is learned separately, which is prone to over-fit. To handle such problem, we summarize the state-of-the-art (SOTA) SRL sub-tasks in previous works and present a new algorithm called Policy Optimization via Abstract Representation which integrates SRL into the policy optimization phase. Firstly, We engage RL loss to assist in updating SRL model so that the states can evolve to meet the demand of RL and maintain a good physical interpretation. Secondly, we introduce a dynamic loss weighting mechanism so that both models can efficiently adapt to each other. Thirdly, we introduce a new SRL prior called domain resemblance to leverage expert demonstration to improve SRL interpretations. Finally, we provide a real-time access of state graph to monitor the course of learning. Experiments indicate that POAR significantly outperforms SOTA RL algorithms and decoupling SRL strategies in terms of sample efficiency and final rewards. We empirically verify POAR to efficiently handle tasks in high dimensions and facilitate training real-life robots directly from scratch.
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
Venue: arXiv cs.GT 2023
Year: 2023

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.
Denial-of-Service Attack Detection via Differential Analysis of Generalized Entropy Progressions
Venue: arXiv cs.CR 2023
Year: 2023

Denial-of-Service (DoS) attacks are one of the most common and consequential cyber attacks in computer networks. While existing research offers a plethora of detection methods, the issue of achieving both scalability and high detection accuracy remains open. In this work, we address this problem by developing a differential method based on generalized entropy progression. In this method, we continuously fit the line of best fit to the entropy progression and check if the derivative, that is, the slope of this line is less than the negative of the dynamically computed standard deviation of the derivatives. As a result, we omit the usage of the thresholds and the results with five real-world network traffic datasets confirm that our method outperforms threshold-based DoS attack detection by two orders of magnitude on average. Our method achieves false positive rates that are up to 7% where the arithmetic mean is 3% with Tsallis entropy and only 5% sampling of the total network flow. Moreover, since the main computation cost of our method is the entropy computation, which is linear in the volume of the unit-time network flow and it uses integer only operations and a small fraction of the total flow, it is therefore lightweight and scalable.
Exploring the Training Robustness of Distributional Reinforcement Learning against Noisy State Observations
Venue: arXiv cs.LG 2023
Year: 2023

In real scenarios, state observations that an agent observes may contain measurement errors or adversarial noises, misleading the agent to take suboptimal actions or even collapse while training. In this paper, we study the training robustness of distributional Reinforcement Learning (RL), a class of state-of-the-art methods that estimate the whole distribution, as opposed to only the expectation, of the total return. Firstly, we validate the contraction of distributional Bellman operators in the State-Noisy Markov Decision Process (SN-MDP), a typical tabular case that incorporates both random and adversarial state observation noises. In the noisy setting with function approximation, we then analyze the vulnerability of least squared loss in expectation-based RL with either linear or nonlinear function approximation. By contrast, we theoretically characterize the bounded gradient norm of distributional RL loss based on the categorical parameterization equipped with the KL divergence. The resulting stable gradients while the optimization in distributional RL accounts for its better training robustness against state observation noises. Finally, extensive experiments on the suite of environments verified that distributional RL is less vulnerable against both random and adversarial noisy state observations compared with its expectation-based counterpart.
Wages and Utilities in a Closed Economy
Venue: arXiv cs.GT 2023
Year: 2023

The broad objective of this paper is to propose a mathematical model for the study of causes of wage inequality and relate it to choices of consumption, the technologies of production, and the composition of labor in an economy. The paper constructs a Simple Closed Model, or an SCM, for short, for closed economies, in which the consumption and the production parts are clearly separated and yet coupled. The model is established as a specialization of the Arrow-Debreu model and its equilibria correspond directly with those of the general Arrow-Debreu model. The formulation allows us to identify the combinatorial data which link parameters of the economic system with its equilibria, in particular, the impact of consumer preferences on wages. The SCM model also allows the formulation and explicit construction of the consumer choice game, where expressed utilities of various labor classes serve as strategies with total or relative wages as the pay-offs. We illustrate, through examples, the mathematical details of the consumer choice game. We show that consumer preferences, expressed through modified utility functions, do indeed percolate through the economy, and influence not only prices but also production and wages. Thus, consumer choice may serve as an effective tool for wage redistribution.
Skin Deep Unlearning: Artefact and Instrument Debiasing in the Context of Melanoma Classification
Venue: arXiv cs.CV 2023
Year: 2023

Convolutional Neural Networks have demonstrated dermatologist-level performance in the classification of melanoma from skin lesion images, but prediction irregularities due to biases seen within the training data are an issue that should be addressed before widespread deployment is possible. In this work, we robustly remove bias and spurious variation from an automated melanoma classification pipeline using two leading bias unlearning techniques. We show that the biases introduced by surgical markings and rulers presented in previous studies can be reasonably mitigated using these bias removal methods. We also demonstrate the generalisation benefits of unlearning spurious variation relating to the imaging instrument used to capture lesion images. Our experimental results provide evidence that the effects of each of the aforementioned biases are notably reduced, with different debiasing techniques excelling at different tasks.
FooBaR: Fault Fooling Backdoor Attack on Neural Network Training
Venue: arXiv cs.CR 2023
Year: 2023

Neural network implementations are known to be vulnerable to physical attack vectors such as fault injection attacks. As of now, these attacks were only utilized during the inference phase with the intention to cause a misclassification. In this work, we explore a novel attack paradigm by injecting faults during the training phase of a neural network in a way that the resulting network can be attacked during deployment without the necessity of further faulting. In particular, we discuss attacks against ReLU activation functions that make it possible to generate a family of malicious inputs, which are called fooling inputs, to be used at inference time to induce controlled misclassifications. Such malicious inputs are obtained by mathematically solving a system of linear equations that would cause a particular behaviour on the attacked activation functions, similar to the one induced in training through faulting. We call such attacks fooling backdoors as the fault attacks at the training phase inject backdoors into the network that allow an attacker to produce fooling inputs. We evaluate our approach against multi-layer perceptron networks and convolutional networks on a popular image classification task obtaining high attack success rates (from 60% to 100%) and high classification confidence when as little as 25 neurons are attacked while preserving high accuracy on the originally intended classification task.
FormatFuzzer: Effective Fuzzing of Binary File Formats
Venue: arXiv cs.SE 2023
Year: 2023

Effective fuzzing of programs that process structured binary inputs, such as multimedia files, is a challenging task, since those programs expect a very specific input format. Existing fuzzers, however, are mostly format-agnostic, which makes them versatile, but also ineffective when a specific format is required. We present FormatFuzzer, a generator for format-specific fuzzers. FormatFuzzer takes as input a binary template (a format specification used by the 010 Editor) and compiles it into C++ code that acts as parser, mutator, and highly efficient generator of inputs conforming to the rules of the language. The resulting format-specific fuzzer can be used as a standalone producer or mutator in black-box settings, where no guidance from the program is available. In addition, by providing mutable decision seeds, it can be easily integrated with arbitrary format-agnostic fuzzers such as AFL to make them format-aware. In our evaluation on complex formats such as MP4 or ZIP, FormatFuzzer showed to be a highly effective producer of valid inputs that also detected previously unknown memory errors in ffmpeg and timidity.
Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning
Venue: arXiv cs.AR 2023
Year: 2023

Past research has proposed numerous hardware prefetching techniques, most of which rely on exploiting one specific type of program context information (e.g., program counter, cacheline address) to predict future memory accesses. These techniques either completely neglect a prefetcher's undesirable effects (e.g., memory bandwidth usage) on the overall system, or incorporate system-level feedback as an afterthought to a system-unaware prefetch algorithm. We show that prior prefetchers often lose their performance benefit over a wide range of workloads and system configurations due to their inherent inability to take multiple different types of program context and system-level feedback information into account while prefetching. In this paper, we make a case for designing a holistic prefetch algorithm that learns to prefetch using multiple different types of program context and system-level feedback information inherent to its design. To this end, we propose Pythia, which formulates the prefetcher as a reinforcement learning agent. For every demand request, Pythia observes multiple different types of program context information to make a prefetch decision. For every prefetch decision, Pythia receives a numerical reward that evaluates prefetch quality under the current memory bandwidth usage. Pythia uses this reward to reinforce the correlation between program context information and prefetch decision to generate highly accurate, timely, and system-aware prefetch requests in the future. Our extensive evaluations using simulation and hardware synthesis show that Pythia outperforms multiple state-of-the-art prefetchers over a wide range of workloads and system configurations, while incurring only 1.03% area overhead over a desktop-class processor and no software changes in workloads. The source code of Pythia can be freely downloaded from https://github.com/CMU-SAFARI/Pythia.
Connected Coordinated Motion Planning with Bounded Stretch
Venue: arXiv cs.CG 2023
Year: 2023

We consider the problem of connected coordinated motion planning for a large collective of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-complete, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, then the total duration of our overall schedule is $\mathcal{O}(d)$, which is optimal up to constant factors.
Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis
Venue: arXiv cs.LG 2023
Year: 2023

Classic and deep generalized canonical correlation analysis (GCCA) algorithms seek low-dimensional common representations of data entities from multiple ``views'' (e.g., audio and image) using linear transformations and neural networks, respectively. When the views are acquired and stored at different computing agents (e.g., organizations and edge devices) and data sharing is undesired due to privacy or communication cost considerations, federated learning-based GCCA is well-motivated. In federated learning, the views are kept locally at the agents and only derived, limited information exchange with a central server is allowed. However, applying existing GCCA algorithms onto such federated learning settings may incur prohibitively high communication overhead. This work puts forth a communication-efficient federated learning framework for both linear and deep GCCA under the maximum variance (MAX-VAR) formulation. The overhead issue is addressed by aggressively compressing (via quantization) the exchanging information between the computing agents and a central controller. Compared to the unquantized version, our empirical study shows that the proposed algorithm enjoys a substantial reduction of communication overheads with virtually no loss in accuracy and convergence speed. Rigorous convergence analyses are also presented, which is a nontrivial effort. Generic federated optimization results do not cover the special problem structure of GCCA. Our result shows that the proposed algorithms for both linear and deep GCCA converge to critical points at a sublinear rate, even under heavy quantization and stochastic approximations. In addition, in the linear MAX-VAR case, the quantized algorithm approaches a global optimum in a geometric rate under reasonable conditions. Synthetic and real-data experiments are used to showcase the effectiveness of the proposed approach.
On the Power of Finite Ambiguity in Büchi Complementation
Venue: arXiv cs.FL 2023
Year: 2023

In this work, we exploit the power of \emph{finite ambiguity} for the complementation problem of Büchi automata by using reduced run directed acyclic graphs (DAGs) over infinite words, in which each vertex has at most one predecessor; these reduced run DAGs have only a finite number of infinite runs, thus obtaining the finite ambiguity in Büchi complementation. We show how to use this type of reduced run DAGs as a unified tool to optimize both rank-based and slice-based complementation constructions for Büchi automata with a finite degree of ambiguity. As a result, given a Büchi automaton with $n$ states and a finite degree of ambiguity, the number of states in the complementary Büchi automaton constructed by the classical rank-based and slice-based complementation constructions can be improved from $2^{\mathsf{O}(n \log n)}$ and $\mathsf{O}((3n)^{n})$ to $\mathsf{O}(6^{n}) \subseteq 2^{\mathsf{O}(n)}$ and $\mathsf{O}(4^{n})$, respectively. We further show how to construct such reduced run DAGs for limit deterministic Büchi automata and obtain a specialized complementation algorithm, thus demonstrating the generality of the power of finite ambiguity.
A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions
Venue: arXiv cs.IR 2023
Year: 2023

Recommender system is one of the most important information services on today's Internet. Recently, graph neural networks have become the new state-of-the-art approach to recommender systems. In this survey, we conduct a comprehensive review of the literature on graph neural network-based recommender systems. We first introduce the background and the history of the development of both recommender systems and graph neural networks. For recommender systems, in general, there are four aspects for categorizing existing works: stage, scenario, objective, and application. For graph neural networks, the existing methods consist of two categories, spectral models and spatial ones. We then discuss the motivation of applying graph neural networks into recommender systems, mainly consisting of the high-order connectivity, the structural property of data, and the enhanced supervision signal. We then systematically analyze the challenges in graph construction, embedding propagation/aggregation, model optimization, and computation efficiency. Afterward and primarily, we provide a comprehensive overview of a multitude of existing works of graph neural network-based recommender systems, following the taxonomy above. Finally, we raise discussions on the open problems and promising future directions in this area. We summarize the representative papers along with their code repositories in \url{https://github.com/tsinghua-fib-lab/GNN-Recommender-Systems}.
Channel Customization for Joint Tx-RISs-Rx Design in Hybrid mmWave Systems
Venue: arXiv cs.IT 2023
Year: 2023

In strong line-of-sight millimeter-wave (mmWave) wireless systems, the rank-deficient channel severely hampers spatial multiplexing. To address this inherent deficiency, multiple reconfigurable-intelligent-surfaces (RISs) are introduced in this study to customize the wireless channel. Utilizing the RIS to reshape electromagnetic waves, we theoretically show that a favorable channel with an arbitrary tunable rank and a minimized truncated condition number can be established by elaborately designing the placement and reflection matrix of RISs. Different from existing works on multi-RISs, the number of elements needed for each RIS to combat the path loss and the limited phase control is also considered. On the basis of the proposed channel customization, a joint transmitter-RISs-receiver (Tx-RISs-Rx) design under a hybrid mmWave system is investigated to maximize the spectral efficiency. Using the proposed scheme, the optimal singular value decomposition-based hybrid beamforming at the Tx and Rx can be obtained without matrix decomposition for the digital and analog beamforming. The bottoms of the sub-channel mode in the water-filling algorithm, which are conventionally uncontrollable, are proven to be independently adjustable by RISs. Moreover, the transmit power required for realizing multi-stream transmission is derived. Numerical results are presented to verify our theoretical analysis and exhibit substantial gains over systems without RISs.
Solving Challenging Control Problems Using Two-Staged Deep Reinforcement Learning
Venue: arXiv cs.RO 2023
Year: 2023

We present a deep reinforcement learning (deep RL) algorithm that consists of learning-based motion planning and imitation to tackle challenging control problems. Deep RL has been an effective tool for solving many high-dimensional continuous control problems, but it cannot effectively solve challenging problems with certain properties, such as sparse reward functions or sensitive dynamics. In this work, we propose an approach that decomposes the given problem into two deep RL stages: motion planning and motion imitation. The motion planning stage seeks to compute a feasible motion plan by leveraging the powerful planning capability of deep RL. Subsequently, the motion imitation stage learns a control policy that can imitate the given motion plan with realistic sensors and actuation models. This new formulation requires only a nominal added cost to the user because both stages require minimal changes to the original problem. We demonstrate that our approach can solve challenging control problems, rocket navigation, and quadrupedal locomotion, which cannot be solved by the monolithic deep RL formulation or the version with Probabilistic Roadmap.
An Explainable-AI approach for Diagnosis of COVID-19 using MALDI-ToF Mass Spectrometry
Venue: arXiv cs.LG 2023
Year: 2023

The severe acute respiratory syndrome coronavirus type-2 (SARS-CoV-2) caused a global pandemic and immensely affected the global economy. Accurate, cost-effective, and quick tests have proven substantial in identifying infected people and mitigating the spread. Recently, multiple alternative platforms for testing coronavirus disease 2019 (COVID-19) have been published that show high agreement with current gold standard real-time polymerase chain reaction (RT-PCR) results. These new methods do away with nasopharyngeal (NP) swabs, eliminate the need for complicated reagents, and reduce the burden on RT-PCR test reagent supply. In the present work, we have designed an artificial intelligence-based (AI) testing method to provide confidence in the results. Current AI applications for COVID-19 studies often lack a biological foundation in the decision-making process, and our AI approach is one of the earliest to leverage explainable AI (X-AI) algorithms for COVID-19 diagnosis using mass spectrometry. Here, we have employed X-AI to explain the decision-making process on a local (per-sample) and global (all samples) basis underscored by biologically relevant features. We evaluated our technique with data extracted from human gargle samples and achieved a testing accuracy of 94.12%. Such techniques would strengthen the relationship between AI and clinical diagnostics by providing biomedical researchers and healthcare workers with trustworthy and, most importantly, explainable test results