OpenRaiser/Intern-Atlas huggingface dataset:
Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorability
Venue: arXiv cs.LG 2023
Year: 2023

We consider off-policy evaluation of dynamic treatment rules under sequential ignorability, given an assumption that the underlying system can be modeled as a partially observed Markov decision process (POMDP). We propose an estimator, partial history importance weighting, and show that it can consistently estimate the stationary mean rewards of a target policy given long enough draws from the behavior policy. We provide an upper bound on its error that decays polynomially in the number of observations (i.e., the number of trajectories times their length), with an exponent that depends on the overlap of the target and behavior policies, and on the mixing time of the underlying system. Furthermore, we show that this rate of convergence is minimax given only our assumptions on mixing and overlap. Our results establish that off-policy evaluation in POMDPs is strictly harder than off-policy evaluation in (fully observed) Markov decision processes, but strictly easier than model-free off-policy evaluation.
Maximizing the Smallest Eigenvalue of Grounded Laplacian Matrix
Venue: arXiv cs.IT 2023
Year: 2023

For a connected graph $\mathcal{G}=(V,E)$ with $n$ nodes, $m$ edges, and Laplacian matrix $\boldsymbol{\mathit{L}}$, a grounded Laplacian matrix $\boldsymbol{\mathit{L}}(S)$ of $\mathcal{G}$ is a $(n-k) \times (n-k)$ principal submatrix of $\boldsymbol{\mathit{L}}$, obtained from $\boldsymbol{\mathit{L}}$ by deleting $k$ rows and columns corresponding to $k$ selected nodes forming a set $S\subseteq V$. The smallest eigenvalue $λ(S)$ of $\boldsymbol{\mathit{L}}(S)$ plays a pivotal role in various dynamics defined on $\mathcal{G}$. For example, $λ(S)$ characterizes the convergence rate of leader-follower consensus, as well as the effectiveness of a pinning scheme for the pinning control problem, with larger $λ(S)$ corresponding to smaller convergence time or better effectiveness of a pinning scheme. In this paper, we focus on the problem of optimally selecting a subset $S$ of fixed $k \ll n$ nodes, in order to maximize the smallest eigenvalue $λ(S)$ of the grounded Laplacian matrix $\boldsymbol{\mathit{L}}(S)$. We show that this optimization problem is NP-hard and that the objective function is non-submodular but monotone. Due to the difficulty to obtain the optimal solution, we first propose a na\"ıve heuristic algorithm selecting one optimal node at each time for $k$ iterations. Then we propose a fast heuristic scalable algorithm to approximately solve this problem, using derivative matrix, matrix perturbations, and Laplacian solvers as tools. Our na\"ıve heuristic algorithm takes $\tilde{O}(knm)$ time, while the fast greedy heuristic has a nearly linear time complexity of $\tilde{O}(km)$. We also conduct numerous experiments on different networks sized up to one million nodes, demonstrating the superiority of our algorithm in terms of efficiency and effectiveness.
Reconstructing Pruned Filters using Cheap Spatial Transformations
Venue: arXiv cs.CV 2023
Year: 2023

We present an efficient alternative to the convolutional layer using cheap spatial transformations. This construction exploits an inherent spatial redundancy of the learned convolutional filters to enable a much greater parameter efficiency, while maintaining the top-end accuracy of their dense counter-parts. Training these networks is modelled as a generalised pruning problem, whereby the pruned filters are replaced with cheap transformations from the set of non-pruned filters. We provide an efficient implementation of the proposed layer, followed by two natural extensions to avoid excessive feature compression and to improve the expressivity of the transformed features. We show that these networks can achieve comparable or improved performance to state-of-the-art pruning models across both the CIFAR-10 and ImageNet-1K datasets.
History Aware Multimodal Transformer for Vision-and-Language Navigation
Venue: arXiv cs.CV 2023
Year: 2023

Vision-and-language navigation (VLN) aims to build autonomous visual agents that follow instructions and navigate in real scenes. To remember previously visited locations and actions taken, most approaches to VLN implement memory using recurrent states. Instead, we introduce a History Aware Multimodal Transformer (HAMT) to incorporate a long-horizon history into multimodal decision making. HAMT efficiently encodes all the past panoramic observations via a hierarchical vision transformer (ViT), which first encodes individual images with ViT, then models spatial relation between images in a panoramic observation and finally takes into account temporal relation between panoramas in the history. It, then, jointly combines text, history and current observation to predict the next action. We first train HAMT end-to-end using several proxy tasks including single step action prediction and spatial relation prediction, and then use reinforcement learning to further improve the navigation policy. HAMT achieves new state of the art on a broad range of VLN tasks, including VLN with fine-grained instructions (R2R, RxR), high-level instructions (R2R-Last, REVERIE), dialogs (CVDN) as well as long-horizon VLN (R4R, R2R-Back). We demonstrate HAMT to be particularly effective for navigation tasks with longer trajectories.
Unified Instance and Knowledge Alignment Pretraining for Aspect-based Sentiment Analysis
Venue: arXiv cs.CL 2023
Year: 2023

Aspect-based Sentiment Analysis (ABSA) aims to determine the sentiment polarity towards an aspect. Because of the expensive and limited labelled data, the pretraining strategy has become the de-facto standard for ABSA. However, there always exists severe domain shift between the pretraining and downstream ABSA datasets, hindering the effective knowledge transfer when directly finetuning and making the downstream task performs sub-optimal. To mitigate such domain shift, we introduce a unified alignment pretraining framework into the vanilla pretrain-finetune pipeline with both instance- and knowledge-level alignments. Specifically, we first devise a novel coarse-to-fine retrieval sampling approach to select target domain-related instances from the large-scale pretraining dataset, thus aligning the instances between pretraining and target domains (First Stage). Then, we introduce a knowledge guidance-based strategy to further bridge the domain gap at the knowledge level. In practice, we formulate the model pretrained on the sampled instances into a knowledge guidance model and a learner model, respectively. On the target dataset, we design an on-the-fly teacher-student joint fine-tuning approach to progressively transfer the knowledge from the knowledge guidance model to the learner model (Second Stage). Thereby, the learner model can maintain more domain-invariant knowledge when learning new knowledge from the target dataset. In the Third Stage, the learner model is finetuned to better adapt its learned knowledge to the target dataset. Extensive experiments and analyses on several ABSA benchmarks demonstrate the effectiveness and universality of our proposed pretraining framework. Our source code and models are publicly available at https://github.com/WHU-ZQH/UIKA.
Task-Aware Meta Learning-based Siamese Neural Network for Classifying Obfuscated Malware
Venue: arXiv cs.CR 2023
Year: 2023

Malware authors apply different techniques of control flow obfuscation, in order to create new malware variants to avoid detection. Existing Siamese neural network (SNN)-based malware detection methods fail to correctly classify different malware families when such obfuscated malware samples are present in the training dataset, resulting in high false-positive rates. To address this issue, we propose a novel task-aware few-shot-learning-based Siamese Neural Network that is resilient against the presence of malware variants affected by such control flow obfuscation techniques. Using the average entropy features of each malware family as inputs, in addition to the image features, our model generates the parameters for the feature layers, to more accurately adjust the feature embedding for different malware families, each of which has obfuscated malware variants. In addition, our proposed method can classify malware classes, even if there are only one or a few training samples available. Our model utilizes few-shot learning with the extracted features of a pre-trained network (e.g., VGG-16), to avoid the bias typically associated with a model trained with a limited number of training samples. Our proposed approach is highly effective in recognizing unique malware signatures, thus correctly classifying malware samples that belong to the same malware family, even in the presence of obfuscated malware variants. Our experimental results, validated by N-way on N-shot learning, show that our model is highly effective in classification accuracy, exceeding a rate \textgreater 91\%, compared to other similar methods.
LTL-Based Non-Markovian Inverse Reinforcement Learning
Venue: arXiv cs.FL 2023
Year: 2023

The successes of reinforcement learning in recent years are underpinned by the characterization of suitable reward functions. However, in settings where such rewards are non-intuitive, difficult to define, or otherwise error-prone in their definition, it is useful to instead learn the reward signal from expert demonstrations. This is the crux of inverse reinforcement learning (IRL). While eliciting learning requirements in the form of scalar reward signals has been shown to effective, such representations lack explainability and lead to opaque learning. We aim to mitigate this situation by presenting a novel IRL method for eliciting declarative learning requirements in the form of a popular formal logic -- Linear Temporal Logic (LTL) -- from a set of traces given by the expert policy. A key novelty of the proposed approach is quantitative semantics of satisfaction of an LTL formula by a word that, following Occam's razor principle, incentivizes simpler explanations. Given a sample $S=(P,N)$ consisting of positive traces $P$ and negative traces $N$, the proposed algorithms automate the search for a formula $φ$ which provides the simplest explanation (in the $GF$ fragment of LTL) of the samples. We have implemented this approach as an open-source tool QuantLearn to perform logic-based non-Markovian IRL. Our results demonstrate the feasibility of the proposed approach in eliciting intuitive LTL-based reward signals from noisy data.
Token Games and History-Deterministic Quantitative-Automata
Venue: arXiv cs.FL 2023
Year: 2023

A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional properties, history-deterministic automata are useful in solving games and synthesis problems. Deciding whether a given nondeterministic automaton is history-deterministic (the HDness problem) is generally a difficult task, which can involve an exponential procedure, or even be undecidable, as is the case for example with pushdown automata. Token games provide a PTime solution to the HDness problem of Büchi and coBüchi automata, and it is conjectured that 2-token games characterise HDness for all $ω$-regular automata. We extend token games to the quantitative setting and analyse their potential to help deciding HDness of quantitative automata. In particular, we show that 1-token games characterise HDness for all quantitative (and Boolean) automata on finite words, as well as discounted-sum (DSum), Inf and Reachability automata on infinite words, and that 2-token games characterise HDness of LimInf and LimSup automata, as well as Sup automata on infinite words. Using these characterisations, we provide solutions to the HDness problem of Safety, Reachability, Inf and Sup automata on finite and infinite words in PTime, of DSum automata on finite and infinite words in NP$\cap$co-NP, of LimSup automata in quasipolynomial time, and of LimInf automata in exponential time, where the latter two are only polynomial for automata with a logarithmic number of weights.
An efficient bundle-based approach for the share-a-ride problem
Venue: arXiv cs.DS 2023
Year: 2023

Some of today's most significant challenges in urban environments concern individual mobility and rapid parcel delivery. With the surge of e-commerce and the ever-increasing volume of goods to be handled, new logistic solutions are in high demand. The share-a-ride problem (SARP) was proposed as one such solution, combining people and parcel transportation in taxis. This is an NP-hard problem and thus obtaining optimal solutions can be computationally costly. In this paper, we work with a variation of SARP for ride-hailing systems, which can be formulated as a multi-depot open generalised vehicle routing problem with time windows. We present and solve a mixed-integer linear programming (MILP) formulation for this problem that bundles requests together, and we compare its results to a previously proposed two-stage method. The latter solves the so-called freight insertion problem (FIP) in the second stage, for which we consider two versions, and the problem consists of inserting parcels into predefined passenger routes obtained in the first stage. We tested the methods in three sets of instances. The developed bundle-based approach outperformed both FIP versions in solution quality and in the service of parcels. Our method also compares favourably when it comes to reducing the amount of deadheading distance.
10 Security and Privacy Problems in Large Foundation Models
Venue: arXiv cs.CR 2023
Year: 2023

Foundation models--such as GPT, CLIP, and DINO--have achieved revolutionary progress in the past several years and are commonly believed to be a promising approach for general-purpose AI. In particular, self-supervised learning is adopted to pre-train a foundation model using a large amount of unlabeled data. A pre-trained foundation model is like an ``operating system'' of the AI ecosystem. Specifically, a foundation model can be used as a feature extractor for many downstream tasks with little or no labeled training data. Existing studies on foundation models mainly focused on pre-training a better foundation model to improve its performance on downstream tasks in non-adversarial settings, leaving its security and privacy in adversarial settings largely unexplored. A security or privacy issue of a pre-trained foundation model leads to a single point of failure for the AI ecosystem. In this book chapter, we discuss 10 basic security and privacy problems for the pre-trained foundation models, including six confidentiality problems, three integrity problems, and one availability problem. For each problem, we discuss potential opportunities and challenges. We hope our book chapter will inspire future research on the security and privacy of foundation models.
DFL: High-Performance Blockchain-Based Federated Learning
Venue: arXiv cs.DC 2023
Year: 2023

Many researchers have proposed replacing the aggregation server in federated learning with a blockchain system to improve privacy, robustness, and scalability. In this approach, clients would upload their updated models to the blockchain ledger and use a smart contract to perform model averaging. However, the significant delay and limited computational capabilities of blockchain systems make it inefficient to support machine learning applications on the blockchain. In this paper, we propose a new public blockchain architecture called DFL, which is specially optimized for distributed federated machine learning. Our architecture inherits the merits of traditional blockchain systems while achieving low latency and low resource consumption by waiving global consensus. To evaluate the performance and robustness of our architecture, we implemented a prototype and tested it on a physical four-node network, and also developed a simulator to simulate larger networks and more complex situations. Our experiments show that the DFL architecture can reach over 90\% accuracy for non-I.I.D. datasets, even in the presence of model poisoning attacks, while ensuring that the blockchain part consumes less than 5\% of hardware resources.
Successor Feature Representations
Venue: arXiv cs.LG 2023
Year: 2023

Transfer in Reinforcement Learning aims to improve learning performance on target tasks using knowledge from experienced source tasks. Successor Representations (SR) and their extension Successor Features (SF) are prominent transfer mechanisms in domains where reward functions change between tasks. They reevaluate the expected return of previously learned policies in a new target task to transfer their knowledge. The SF framework extended SR by linearly decomposing rewards into successor features and a reward weight vector allowing their application in high-dimensional tasks. But this came with the cost of having a linear relationship between reward functions and successor features, limiting its application to tasks where such a linear relationship exists. We propose a novel formulation of SR based on learning the cumulative discounted probability of successor features, called Successor Feature Representations (SFR). Crucially, SFR allows to reevaluate the expected return of policies for general reward functions. We introduce different SFR variations, prove its convergence, and provide a guarantee on its transfer performance. Experimental evaluations based on SFR with function approximation demonstrate its advantage over SF not only for general reward functions, but also in the case of linearly decomposable reward functions.
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Venue: arXiv cs.DS 2023
Year: 2023

We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve the distances of a given graph. A shortcut set is a set of edges that when added to a directed graph, decreases its diameter. The previous best known lower bounds for these three structures are given by Huang and Pettie [SWAT 2018]. For $O(n)$-sized spanners, we improve the lower bound on the additive stretch from $Ω(n^{1/11})$ to $Ω(n^{2/21})$. For $O(n)$-sized emulators, we improve the lower bound on the additive stretch from $Ω(n^{1/18})$ to $Ω(n^{1/16})$. For $O(m)$-sized shortcut sets, we improve the lower bound on the graph diameter from $Ω(n^{1/11})$ to $Ω(n^{1/8})$. Our key technical contribution, which is the basis of all of our bounds, is an improvement of a graph product known as an alternation product.
Learning Safety Filters for Unknown Discrete-Time Linear Systems
Venue: arXiv cs.LG 2023
Year: 2023

A learning-based safety filter is developed for discrete-time linear time-invariant systems with unknown models subject to Gaussian noises with unknown covariance. Safety is characterized using polytopic constraints on the states and control inputs. The empirically learned model and process noise covariance with their confidence bounds are used to construct a robust optimization problem for minimally modifying nominal control actions to ensure safety with high probability. The optimization problem relies on tightening the original safety constraints. The magnitude of the tightening is larger at the beginning since there is little information to construct reliable models, but shrinks with time as more data becomes available.
Piezoelectric Soft Robot Inchworm Motion by Tuning Ground Friction through Robot Shape: Quasi-Static Modeling and Experimental Validation
Venue: arXiv cs.RO 2023
Year: 2023

Electrically-driven soft robots based on piezoelectric actuators may enable compact form factors and maneuverability in complex environments. In most prior work, piezoelectric actuators are used to control a single degree of freedom. In this work, the coordinated activation of five independent piezoelectric actuators, attached to a common metal foil, is used to implement inchworm-inspired crawling motion in a robot that is less than 0.5 mm thick. The motion is based on the control of its friction to the ground through the robot's shape, in which one end of the robot (depending on its shape) is anchored to the ground by static friction, while the rest of its body expands or contracts. A complete analytical model of the robot shape, which includes gravity, is developed to quantify the robot shape, friction, and displacement. After validation of the model by experiments, the robot's five actuators are collectively sequenced for inchworm-like forward and backward motion.
Geometry-aware Bayesian Optimization in Robotics using Riemannian Matérn Kernels
Venue: arXiv cs.RO 2023
Year: 2023

Bayesian optimization is a data-efficient technique which can be used for control parameter tuning, parametric policy adaptation, and structure design in robotics. Many of these problems require optimization of functions defined on non-Euclidean domains like spheres, rotation groups, or spaces of positive-definite matrices. To do so, one must place a Gaussian process prior, or equivalently define a kernel, on the space of interest. Effective kernels typically reflect the geometry of the spaces they are defined on, but designing them is generally non-trivial. Recent work on the Riemannian Matérn kernels, based on stochastic partial differential equations and spectral theory of the Laplace-Beltrami operator, offers promising avenues towards constructing such geometry-aware kernels. In this paper, we study techniques for implementing these kernels on manifolds of interest in robotics, demonstrate their performance on a set of artificial benchmark functions, and illustrate geometry-aware Bayesian optimization for a variety of robotic applications, covering orientation control, manipulability optimization, and motion planning, while showing its improved performance.
Elucidating Robust Learning with Uncertainty-Aware Corruption Pattern Estimation
Venue: arXiv cs.LG 2023
Year: 2023

Robust learning methods aim to learn a clean target distribution from noisy and corrupted training data where a specific corruption pattern is often assumed a priori. Our proposed method can not only successfully learn the clean target distribution from a dirty dataset but also can estimate the underlying noise pattern. To this end, we leverage a mixture-of-experts model that can distinguish two different types of predictive uncertainty, aleatoric and epistemic uncertainty. We show that the ability to estimate the uncertainty plays a significant role in elucidating the corruption patterns as these two objectives are tightly intertwined. We also present a novel validation scheme for evaluating the performance of the corruption pattern estimation. Our proposed method is extensively assessed in terms of both robustness and corruption pattern estimation through a number of domains, including computer vision and natural language processing.