OpenRaiser/Intern-Atlas huggingface dataset:
On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
Venue: arXiv cs.DS 2023
Year: 2023

Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several $\mathsf{NP}$-hard graph problems become tractable for graph classes whose mim-width is bounded and quickly computable, no algorithmic applications of boundedness of sim-width are known. In [Kang et al., A width parameter useful for chordal and co-comparability graphs, Theoretical Computer Science, 704:1-17, 2017], it is asked whether \textsc{Independent Set} and \textsc{$3$-Colouring} are $\mathsf{NP}$-complete on graphs of sim-width at most $1$. We observe that, for each $k \in \mathbb{N}$, \textsc{List $k$-Colouring} is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. Moreover, we show that if the same holds for \textsc{Independent Set}, then \textsc{Independent $\mathcal{H}$-Packing} is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. This problem is a common generalisation of \textsc{Independent Set}, \textsc{Induced Matching}, \textsc{Dissociation Set} and \textsc{$k$-Separator}. We also make progress toward classifying the mim-width of $(H_1,H_2)$-free graphs in the case $H_1$ is complete or edgeless. Our results solve some open problems in [Brettell et al., Bounding the mim-width of hereditary graph classes, Journal of Graph Theory, 99(1):117-151, 2022].
Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
Venue: arXiv cs.LO 2023
Year: 2023

This paper introduces the exponential substitution calculus (ESC), a new presentation of cut elimination for IMELL, based on proof terms and building on the idea that exponentials can be seen as explicit substitutions. The idea in itself is not new, but here it is pushed to a new level, inspired by Accattoli and Kesner's linear substitution calculus (LSC). One of the key properties of the LSC is that it naturally models the sub-term property of abstract machines, that is the key ingredient for the study of reasonable time cost models for the $λ$-calculus. The new ESC is then used to design a cut elimination strategy with the sub-term property, providing the first polynomial cost model for cut elimination with unconstrained exponentials. For the ESC, we also prove untyped confluence and typed strong normalization, showing that it is an alternative to proof nets for an advanced study of cut elimination.
Minimax Optimal Online Imitation Learning via Replay Estimation
Venue: arXiv cs.LG 2023
Year: 2023

Online imitation learning is the problem of how best to mimic expert demonstrations, given access to the environment or an accurate simulator. Prior work has shown that in the infinite sample regime, exact moment matching achieves value equivalence to the expert policy. However, in the finite sample regime, even if one has no optimization error, empirical variance can lead to a performance gap that scales with $H^2 / N$ for behavioral cloning and $H / \sqrt{N}$ for online moment matching, where $H$ is the horizon and $N$ is the size of the expert dataset. We introduce the technique of replay estimation to reduce this empirical variance: by repeatedly executing cached expert actions in a stochastic simulator, we compute a smoother expert visitation distribution estimate to match. In the presence of general function approximation, we prove a meta theorem reducing the performance gap of our approach to the parameter estimation error for offline classification (i.e. learning the expert policy). In the tabular setting or with linear function approximation, our meta theorem shows that the performance gap incurred by our approach achieves the optimal $\widetilde{O} \left( \min({H^{3/2}} / {N}, {H} / {\sqrt{N}} \right)$ dependency, under significantly weaker assumptions compared to prior work. We implement multiple instantiations of our approach on several continuous control tasks and find that we are able to significantly improve policy performance across a variety of dataset sizes.
A Simulation Environment and Reinforcement Learning Method for Waste Reduction
Venue: arXiv cs.LG 2023
Year: 2023

In retail (e.g., grocery stores, apparel shops, online retailers), inventory managers have to balance short-term risk (no items to sell) with long-term-risk (over ordering leading to product waste). This balancing task is made especially hard due to the lack of information about future customer purchases. In this paper, we study the problem of restocking a grocery store's inventory with perishable items over time, from a distributional point of view. The objective is to maximize sales while minimizing waste, with uncertainty about the actual consumption by costumers. This problem is of a high relevance today, given the growing demand for food and the impact of food waste on the environment, the economy, and purchasing power. We frame inventory restocking as a new reinforcement learning task that exhibits stochastic behavior conditioned on the agent's actions, making the environment partially observable. We make two main contributions. First, we introduce a new reinforcement learning environment, RetaiL, based on real grocery store data and expert knowledge. This environment is highly stochastic, and presents a unique challenge for reinforcement learning practitioners. We show that uncertainty about the future behavior of the environment is not handled well by classical supply chain algorithms, and that distributional approaches are a good way to account for the uncertainty. Second, we introduce GTDQN, a distributional reinforcement learning algorithm that learns a generalized Tukey Lambda distribution over the reward space. GTDQN provides a strong baseline for our environment. It outperforms other distributional reinforcement learning approaches in this partially observable setting, in both overall reward and reduction of generated waste.
Causal Explanations for Sequential Decision Making Under Uncertainty
Venue: arXiv cs.AI 2023
Year: 2023

We introduce a novel framework for causal explanations of stochastic, sequential decision-making systems built on the well-studied structural causal model paradigm for causal reasoning. This single framework can identify multiple, semantically distinct explanations for agent actions -- something not previously possible. In this paper, we establish exact methods and several approximation techniques for causal inference on Markov decision processes using this framework, followed by results on the applicability of the exact methods and some run time bounds. We discuss several scenarios that illustrate the framework's flexibility and the results of experiments with human subjects that confirm the benefits of this approach.
HierarchyNet: Learning to Summarize Source Code with Heterogeneous Representations
Venue: arXiv cs.SE 2023
Year: 2023

We propose a novel method for code summarization utilizing Heterogeneous Code Representations (HCRs) and our specially designed HierarchyNet. HCRs effectively capture essential code features at lexical, syntactic, and semantic levels by abstracting coarse-grained code elements and incorporating fine-grained program elements in a hierarchical structure. Our HierarchyNet method processes each layer of the HCR separately through a unique combination of the Heterogeneous Graph Transformer, a Tree-based CNN, and a Transformer Encoder. This approach preserves dependencies between code elements and captures relations through a novel Hierarchical-Aware Cross Attention layer. Our method surpasses current state-of-the-art techniques, such as PA-Former, CAST, and NeuralCodeSum.
Pseudo-Data based Self-Supervised Federated Learning for Classification of Histopathological Images
Venue: arXiv cs.CV 2023
Year: 2023

Computer-aided diagnosis (CAD) can help pathologists improve diagnostic accuracy together with consistency and repeatability for cancers. However, the CAD models trained with the histopathological images only from a single center (hospital) generally suffer from the generalization problem due to the straining inconsistencies among different centers. In this work, we propose a pseudo-data based self-supervised federated learning (FL) framework, named SSL-FT-BT, to improve both the diagnostic accuracy and generalization of CAD models. Specifically, the pseudo histopathological images are generated from each center, which contains inherent and specific properties corresponding to the real images in this center, but does not include the privacy information. These pseudo images are then shared in the central server for self-supervised learning (SSL). A multi-task SSL is then designed to fully learn both the center-specific information and common inherent representation according to the data characteristics. Moreover, a novel Barlow Twins based FL (FL-BT) algorithm is proposed to improve the local training for the CAD model in each center by conducting contrastive learning, which benefits the optimization of the global model in the FL procedure. The experimental results on three public histopathological image datasets indicate the effectiveness of the proposed SSL-FL-BT on both diagnostic accuracy and generalization.
Neural Improvement Heuristics for Graph Combinatorial Optimization Problems
Venue: arXiv cs.AI 2023
Year: 2023

Recent advances in graph neural network architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, Neural Improvement (NI) models have been particularly successful. However, existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and node-wise positional encodings. To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the Preference Ranking Problem with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the Traveling Salesman Problem and the Graph Partitioning Problem, recommending operations in the 98th and 97th percentile, respectively.
FETA: Fairness Enforced Verifying, Training, and Predicting Algorithms for Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Algorithmic decision making driven by neural networks has become very prominent in applications that directly affect people's quality of life. In this paper, we study the problem of verifying, training, and guaranteeing individual fairness of neural network models. A popular approach for enforcing fairness is to translate a fairness notion into constraints over the parameters of the model. However, such a translation does not always guarantee fair predictions of the trained neural network model. To address this challenge, we develop a counterexample-guided post-processing technique to provably enforce fairness constraints at prediction time. Contrary to prior work that enforces fairness only on points around test or train data, we are able to enforce and guarantee fairness on all points in the input domain. Additionally, we propose an in-processing technique to use fairness as an inductive bias by iteratively incorporating fairness counterexamples in the learning process. We have implemented these techniques in a tool called FETA. Empirical evaluation on real-world datasets indicates that FETA is not only able to guarantee fairness on-the-fly at prediction time but also is able to train accurate models exhibiting a much higher degree of individual fairness.
Federated Learning in Non-IID Settings Aided by Differentially Private Synthetic Data
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning (FL) is a privacy-promoting framework that enables potentially large number of clients to collaboratively train machine learning models. In a FL system, a server coordinates the collaboration by collecting and aggregating clients' model updates while the clients' data remains local and private. A major challenge in federated learning arises when the local data is heterogeneous -- the setting in which performance of the learned global model may deteriorate significantly compared to the scenario where the data is identically distributed across the clients. In this paper we propose FedDPMS (Federated Differentially Private Means Sharing), an FL algorithm in which clients deploy variational auto-encoders to augment local datasets with data synthesized using differentially private means of latent data representations communicated by a trusted server. Such augmentation ameliorates effects of data heterogeneity across the clients without compromising privacy. Our experiments on deep image classification tasks demonstrate that FedDPMS outperforms competing state-of-the-art FL methods specifically designed for heterogeneous data settings.
Adversarial Laser Spot: Robust and Covert Physical-World Attack to DNNs
Venue: arXiv cs.CV 2023
Year: 2023

Most existing deep neural networks (DNNs) are easily disturbed by slight noise. However, there are few researches on physical attacks by deploying lighting equipment. The light-based physical attacks has excellent covertness, which brings great security risks to many vision-based applications (such as self-driving). Therefore, we propose a light-based physical attack, called adversarial laser spot (AdvLS), which optimizes the physical parameters of laser spots through genetic algorithm to perform physical attacks. It realizes robust and covert physical attack by using low-cost laser equipment. As far as we know, AdvLS is the first light-based physical attack that perform physical attacks in the daytime. A large number of experiments in the digital and physical environments show that AdvLS has excellent robustness and covertness. In addition, through in-depth analysis of the experimental data, we find that the adversarial perturbations generated by AdvLS have superior adversarial attack migration. The experimental results show that AdvLS impose serious interference to advanced DNNs, we call for the attention of the proposed AdvLS. The code of AdvLS is available at: https://github.com/ChengYinHu/AdvLS
Using Connectome Features to Constrain Echo State Networks
Venue: arXiv cs.LG 2023
Year: 2023

We report an improvement to the conventional Echo State Network (ESN) across three benchmark chaotic time-series prediction tasks using fruit fly connectome data alone. We also investigate the impact of key connectome-derived structural features on prediction performance -- uniquely bridging neurobiological structure and machine learning function; and find that both increasing the global average clustering coefficient and modifying the position of weights -- by permuting their synapse-synapse partners -- can lead to increased model variance and (in some cases) degraded performance. In all we consider four topological point modifications to a connectome-derived ESN reservoir (null model): namely, we alter the network sparsity, re-draw nonzero weights from a uniform distribution, permute nonzero weight positions, and increase the network global average clustering coefficient. We compare the four resulting ESN model classes -- and the null model -- with a conventional ESN by conducting time-series prediction experiments on size-variants of the Mackey-Glass 17 (MG-17), Lorenz, and Rossler chaotic time series; denoting each model's performance and variance across train-validate trials.
Which models are innately best at uncertainty estimation?
Venue: arXiv cs.LG 2023
Year: 2023

Due to the comprehensive nature of this paper, it has been updated and split into two separate papers: "A Framework For Benchmarking Class-out-of-distribution Detection And Its Application To ImageNet" and "What Can We Learn From The Selective Prediction And Uncertainty Estimation Performance Of 523 Imagenet Classifiers". We recommend reading them instead. Deep neural networks must be equipped with an uncertainty estimation mechanism when deployed for risk-sensitive tasks. This paper studies the relationship between deep architectures and their training regimes with their corresponding selective prediction and uncertainty estimation performance. We consider both in-distribution uncertainties and class-out-of-distribution ones. Moreover, we consider some of the most popular estimation performance metrics previously proposed including AUROC, ECE, AURC, and coverage for selective accuracy constraint. We present a novel and comprehensive study of selective prediction and the uncertainty estimation performance of 484 existing pretrained deep ImageNet classifiers that are available at popular repositories. We identify numerous and previously unknown factors that affect uncertainty estimation and examine the relationships between the different metrics. We find that distillation-based training regimes consistently yield better uncertainty estimations than other training schemes such as vanilla training, pretraining on a larger dataset and adversarial training. We also provide strong empirical evidence showing that ViT is by far the most superior architecture in terms of uncertainty estimation performance, judging by any aspect, in both in-distribution and class-out-of-distribution scenarios.
A Memory System of a Robot Cognitive Architecture and its Implementation in ArmarX
Venue: arXiv cs.AI 2023
Year: 2023

Cognitive agents such as humans and robots perceive their environment through an abundance of sensors producing streams of data that need to be processed to generate intelligent behavior. A key question of cognition-enabled and AI-driven robotics is how to organize and manage knowledge efficiently in a cognitive robot control architecture. We argue, that memory is a central active component of such architectures that mediates between semantic and sensorimotor representations, orchestrates the flow of data streams and events between different processes and provides the components of a cognitive architecture with data-driven services for the abstraction of semantics from sensorimotor data, the parametrization of symbolic plans for execution and prediction of action effects. Based on related work, and the experience gained in developing our ARMAR humanoid robot systems, we identified conceptual and technical requirements of a memory system as central component of cognitive robot control architecture that facilitate the realization of high-level cognitive abilities such as explaining, reasoning, prospection, simulation and augmentation. Conceptually, a memory should be active, support multi-modal data representations, associate knowledge, be introspective, and have an inherently episodic structure. Technically, the memory should support a distributed design, be access-efficient and capable of long-term data storage. We introduce the memory system for our cognitive robot control architecture and its implementation in the robot software framework ArmarX. We evaluate the efficiency of the memory system with respect to transfer speeds, compression, reproduction and prediction capabilities.
LNGate$^2$: Secure Bidirectional IoT Micro-payments using Bitcoin's Lightning Network and Threshold Cryptography
Venue: arXiv cs.CR 2023
Year: 2023

Bitcoin has emerged as a revolutionary payment system with its decentralized ledger concept; however it has significant problems such as high transaction fees and low throughput. Lightning Network (LN), which was introduced much later, solves most of these problems with an innovative concept called off-chain payments. With this advancement, Bitcoin has become an attractive venue to perform micro-payments which can also be adopted in many IoT applications (e.g., toll payments). Nevertheless, it is not feasible to host LN and Bitcoin on IoT devices due to the storage, memory, and processing restrictions. Therefore, in this paper, we propose a secure and efficient protocol that enables an IoT device to use LN's functions through an untrusted gateway node. Through this gateway which hosts the LN and Bitcoin nodes, the IoT device can open & close LN channels and send & receive LN payments. This delegation approach is powered by a threshold cryptography based scheme that requires the IoT device and the LN gateway to jointly perform all LN operations. Specifically, we propose thresholdizing LN's Bitcoin public and private keys as well as its public and private keys for the new channel states (i.e., commitment points). We prove with a game theoretical security analysis that the IoT device is secure against collusion attacks. We implemented the proposed protocol by changing LN's source code and thoroughly evaluated its performance using several Raspberry Pis. Our evaluation results show that the protocol; is fast, does not bring extra cost overhead, can be run on low data rate wireless networks, is scalable and has negligible energy consumption overhead. To the best of our knowledge, this is the first work that implemented threshold cryptography in LN.
Complex Locomotion Skill Learning via Differentiable Physics
Venue: arXiv cs.AI 2023
Year: 2023

Differentiable physics enables efficient gradient-based optimizations of neural network (NN) controllers. However, existing work typically only delivers NN controllers with limited capability and generalizability. We present a practical learning framework that outputs unified NN controllers capable of tasks with significantly improved complexity and diversity. To systematically improve training robustness and efficiency, we investigated a suite of improvements over the baseline approach, including periodic activation functions, and tailored loss functions. In addition, we find our adoption of batching and an Adam optimizer effective in training complex locomotion tasks. We evaluate our framework on differentiable mass-spring and material point method (MPM) simulations, with challenging locomotion tasks and multiple robot designs. Experiments show that our learning framework, based on differentiable physics, delivers better results than reinforcement learning and converges much faster. We demonstrate that users can interactively control soft robot locomotion and switch among multiple goals with specified velocity, height, and direction instructions using a unified NN controller trained in our system. Code is available at https://github.com/erizmr/Complex-locomotion-skill-learning-via-differentiable-physics.
Achieving Goals using Reward Shaping and Curriculum Learning
Venue: arXiv cs.RO 2023
Year: 2023

Real-time control for robotics is a popular research area in the reinforcement learning community. Through the use of techniques such as reward shaping, researchers have managed to train online agents across a multitude of domains. Despite these advances, solving goal-oriented tasks still requires complex architectural changes or hard constraints to be placed on the problem. In this article, we solve the problem of stacking multiple cubes by combining curriculum learning, reward shaping, and a high number of efficiently parallelized environments. We introduce two curriculum learning settings that allow us to separate the complex task into sequential sub-goals, hence enabling the learning of a problem that may otherwise be too difficult. We focus on discussing the challenges encountered while implementing them in a goal-conditioned environment. Finally, we extend the best configuration identified on a higher complexity environment with differently shaped objects.