OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Recovery of Structured Signals Using Atomic Norm
Venue: arXiv cs.IT 2023
Year: 2023

In many applications we seek to recover signals from linear measurements far fewer than the ambient dimension, given the signals have exploitable structures such as sparse vectors or low rank matrices. In this paper we work in a general setting where signals are approximately sparse in an so called atomic set. We provide general recovery results stating that a convex programming can stably and robustly recover signals if the null space of the sensing map satisfies certain properties. Moreover, we argue that such null space property can be satisfied with high probability if each measurement is subgaussian even when the number of measurements are very few. Some new results for recovering signals sparse in a frame, and recovering low rank matrices are also derived as a result.
AutoMerge: A Framework for Map Assembling and Smoothing in City-scale Environments
Venue: arXiv cs.RO 2023
Year: 2023

We present AutoMerge, a LiDAR data processing framework for assembling a large number of map segments into a complete map. Traditional large-scale map merging methods are fragile to incorrect data associations, and are primarily limited to working only offline. AutoMerge utilizes multi-perspective fusion and adaptive loop closure detection for accurate data associations, and it uses incremental merging to assemble large maps from individual trajectory segments given in random order and with no initial estimations. Furthermore, after assembling the segments, AutoMerge performs fine matching and pose-graph optimization to globally smooth the merged map. We demonstrate AutoMerge on both city-scale merging (120km) and campus-scale repeated merging (4.5km x 8). The experiments show that AutoMerge (i) surpasses the second- and third- best methods by 14% and 24% recall in segment retrieval, (ii) achieves comparable 3D mapping accuracy for 120 km large-scale map assembly, (iii) and it is robust to temporally-spaced revisits. To the best of our knowledge, AutoMerge is the first mapping approach that can merge hundreds of kilometers of individual segments without the aid of GPS.
Multitrack Music Transformer
Venue: arXiv cs.SD 2023
Year: 2023

Existing approaches for generating multitrack music with transformer models have been limited in terms of the number of instruments, the length of the music segments and slow inference. This is partly due to the memory requirements of the lengthy input sequences necessitated by existing representations. In this work, we propose a new multitrack music representation that allows a diverse set of instruments while keeping a short sequence length. Our proposed Multitrack Music Transformer (MMT) achieves comparable performance with state-of-the-art systems, landing in between two recently proposed models in a subjective listening test, while achieving substantial speedups and memory reductions over both, making the method attractive for real time improvisation or near real time creative applications. Further, we propose a new measure for analyzing musical self-attention and show that the trained model attends more to notes that form a consonant interval with the current note and to notes that are 4N beats away from the current step.
Sound Randomized Smoothing in Floating-Point Arithmetics
Venue: arXiv cs.LG 2023
Year: 2023

Randomized smoothing is sound when using infinite precision. However, we show that randomized smoothing is no longer sound for limited floating-point precision. We present a simple example where randomized smoothing certifies a radius of $1.26$ around a point, even though there is an adversarial example in the distance $0.8$ and extend this example further to provide false certificates for CIFAR10. We discuss the implicit assumptions of randomized smoothing and show that they do not apply to generic image classification models whose smoothed versions are commonly certified. In order to overcome this problem, we propose a sound approach to randomized smoothing when using floating-point precision with essentially equal speed and matching the certificates of the standard, unsound practice for standard classifiers tested so far. Our only assumption is that we have access to a fair coin.
Set-based value operators for non-stationary Markovian environments
Venue: arXiv cs.LG 2023
Year: 2023

This paper analyzes finite state Markov Decision Processes (MDPs) with uncertain parameters in compact sets and re-examines results from robust MDP via set-based fixed point theory. To this end, we generalize the Bellman and policy evaluation operators to contracting operators on the value function space and denote them as \emph{value operators}. We lift these value operators to act on \emph{sets} of value functions and denote them as \emph{set-based value operators}. We prove that the set-based value operators are \emph{contractions} in the space of compact value function sets. Leveraging insights from set theory, we generalize the rectangularity condition in classic robust MDP literature to a containment condition for all value operators, which is weaker and can be applied to a larger set of parameter-uncertain MDPs and contracting operators in dynamic programming. We prove that both the rectangularity condition and the containment condition sufficiently ensure that the set-based value operator's fixed point set contains its own extrema elements. For convex and compact sets of uncertain MDP parameters, we show equivalence between the classic robust value function and the supremum of the fixed point set of the set-based Bellman operator. Under dynamically changing MDP parameters in compact sets, we prove a set convergence result for value iteration, which otherwise may not converge to a single value function. Finally, we derive novel guarantees for probabilistic path-planning problems in planet exploration and stratospheric station-keeping.
PASS: A Parameter Audit-based Secure and Fair Federated Learning Scheme against Free-Rider Attack
Venue: arXiv cs.CR 2023
Year: 2023

Federated Learning (FL) as a secure distributed learning framework gains interests in Internet of Things (IoT) due to its capability of protecting the privacy of participant data. However, traditional FL systems are vulnerable to Free-Rider (FR) attacks, which causes unfairness, privacy leakage and inferior performance to FL systems. The prior defense mechanisms against FR attacks assumed that malicious clients (namely, adversaries) declare less than 50% of the total amount of clients. Moreover, they aimed for Anonymous FR (AFR) attacks and lost effectiveness in resisting Selfish FR (SFR) attacks. In this paper, we propose a Parameter Audit-based Secure and fair federated learning Scheme (PASS) against FR attack. PASS has the following key features: (a) prevent from privacy leakage with less accuracy loss; (b) be effective in countering both AFR and SFR attacks; (c) work well no matter whether AFR and SFR adversaries occupy the majority of clients or not. Extensive experimental results validate that PASS: (a) has the same level as the State-Of-The-Art method in mean square error against privacy leakage; (b) defends against AFR and SFR attacks in terms of a higher defense success rate, lower false positive rate, and higher F1-score; (c) is still effective where adversaries exceed 50%, with F1-score 89% against AFR attack and F1-score 87% against SFR attack. Note that PASS produces no negative effect on FL accuracy when there is no FR adversary.
Augmenting Softmax Information for Selective Classification with Out-of-Distribution Data
Venue: arXiv cs.LG 2023
Year: 2023

Detecting out-of-distribution (OOD) data is a task that is receiving an increasing amount of research attention in the domain of deep learning for computer vision. However, the performance of detection methods is generally evaluated on the task in isolation, rather than also considering potential downstream tasks in tandem. In this work, we examine selective classification in the presence of OOD data (SCOD). That is to say, the motivation for detecting OOD samples is to reject them so their impact on the quality of predictions is reduced. We show under this task specification, that existing post-hoc methods perform quite differently compared to when evaluated only on OOD detection. This is because it is no longer an issue to conflate in-distribution (ID) data with OOD data if the ID data is going to be misclassified. However, the conflation within ID data of correct and incorrect predictions becomes undesirable. We also propose a novel method for SCOD, Softmax Information Retaining Combination (SIRC), that augments softmax-based confidence scores with feature-agnostic information such that their ability to identify OOD samples is improved without sacrificing separation between correct and incorrect ID predictions. Experiments on a wide variety of ImageNet-scale datasets and convolutional neural network architectures show that SIRC is able to consistently match or outperform the baseline for SCOD, whilst existing OOD detection methods fail to do so.
Transcribing Medieval Manuscripts for Machine Learning
Venue: arXiv cs.DL 2023
Year: 2023

This article focuses on the transcription of medieval manuscripts. Whereas problems of transcription have long interested medievalists, few workable options in the era of printed editions were available besides normalisation. The automation of this process, known as handwritten text recognition (HTR), has made new kinds of digital text creation possible, but also has foregrounded the necessity of theorising transcription in our scholarly practices. We reflect here on different notions of transcription against the backdrop of changing text technologies. Moreover, drawing on our own research on medieval Latin Bibles, we present general guidelines for customizing transcription schemes, arguing that they must be designed with specific research questions and scholarly end use in mind. Since we are particularly interested in the scribal contribution to the production of codices, our transcription guidelines aim to capture abbreviations and orthographic variation between different textual witnesses for downstream machine learning tasks. In the final section of the article, we discuss a few examples of how the HTR-created transcriptions allow us to address new questions at scale in medieval manuscripts, such as textual variance across witnesses, the prediction of a change in scribal hands within a single manuscript as well as the profiling of individual and regional scribal characteristics.
Human keypoint detection for close proximity human-robot interaction
Venue: arXiv cs.CV 2023
Year: 2023

We study the performance of state-of-the-art human keypoint detectors in the context of close proximity human-robot interaction. The detection in this scenario is specific in that only a subset of body parts such as hands and torso are in the field of view. In particular, (i) we survey existing datasets with human pose annotation from the perspective of close proximity images and prepare and make publicly available a new Human in Close Proximity (HiCP) dataset; (ii) we quantitatively and qualitatively compare state-of-the-art human whole-body 2D keypoint detection methods (OpenPose, MMPose, AlphaPose, Detectron2) on this dataset; (iii) since accurate detection of hands and fingers is critical in applications with handovers, we evaluate the performance of the MediaPipe hand detector; (iv) we deploy the algorithms on a humanoid robot with an RGB-D camera on its head and evaluate the performance in 3D human keypoint detection. A motion capture system is used as reference. The best performing whole-body keypoint detectors in close proximity were MMPose and AlphaPose, but both had difficulty with finger detection. Thus, we propose a combination of MMPose or AlphaPose for the body and MediaPipe for the hands in a single framework providing the most accurate and robust detection. We also analyse the failure modes of individual detectors -- for example, to what extent the absence of the head of the person in the image degrades performance. Finally, we demonstrate the framework in a scenario where a humanoid robot interacting with a person uses the detected 3D keypoints for whole-body avoidance maneuvers.
BDPC: Controlling Application Delay in 6TiSCH networks for the Industrial Internet of Things
Venue: arXiv cs.NI 2023
Year: 2023

One of the essential requirements of wireless industrial Internet of Things (IoT) systems is to have an extremely high packet delivery rate, generally over 99.9% and comply wih realtime deadline constraints. In industrial IoT networks, packets arriving after the deadline become part of packet loss and lose meaning when they arrive late. However, currently available industial IoT proposals aim to minimize End-to-End delay without taking into account simultaneous realtime and reliability constraints. In this paper, we propose a new mechanism, called BDPC (Bounded Delay Packet Control) to tackle this challenge. BDPC combines the knowledge of a node's traffic delay to the destination (root) with the time budget of a data packet traversing the industrial IoT network, to allocate network resources to comply the system maximum delay requirements using an adaptive and distributed algorithm. Unlike the general aim to minimze end-to-end delay, we propose that data packets must arrive before the deadline, but not faster. Our results show, for example, that by using BDPC, the number of packets arriving before the deadline can be improved more than 2.6 times compared to the case when using the default Minimal Scheduling Function from the standard. As a further advantage, BDPC involves minor modifications to the 6TiSCH protocol stack, which makes it compatible with current implementations.
Understanding Influence Maximization via Higher-Order Decomposition
Venue: arXiv cs.SI 2023
Year: 2023

Given its vast application on online social networks, Influence Maximization (IM) has garnered considerable attention over the last couple of decades. Due to the intricacy of IM, most current research concentrates on estimating the first-order contribution of the nodes to select a seed set, disregarding the higher-order interplay between different seeds. Consequently, the actual influence spread frequently deviates from expectations, and it remains unclear how the seed set quantitatively contributes to this deviation. To address this deficiency, this work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index, a variance-based sensitivity analysis. To adapt to IM contexts, seed selection is phrased as binary variables and split into distributions of varying orders. Based on our analysis with various Sobol indices, an IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes followed by strategic pruning. A case study is carried out to demonstrate that the explanation of the impact effect can dependably identify the key higher-order interactions among seeds. SIM is empirically proved to be superior in effectiveness and competitive in efficiency by experiments on synthetic and real-world graphs.
MWS and FWS Codes for Coordinate-Wise Weight Functions
Venue: arXiv cs.IT 2023
Year: 2023

A combinatorial problem concerning the maximum size of the (hamming) weight set of an $[n,k]_q$ linear code was recently introduced. Codes attaining the established upper bound are the Maximum Weight Spectrum (MWS) codes. Those $[n,k]_q $ codes with the same weight set as $ \mathbb{F}_q^n $ are called Full Weight Spectrum (FWS) codes. FWS codes are necessarily ``short", whereas MWS codes are necessarily ``long". For fixed $ k,q $ the values of $ n $ for which an $ [n,k]_q $-FWS code exists are completely determined, but the determination of the minimum length $ M(H,k,q) $ of an $ [n,k]_q $-MWS code remains an open problem. The current work broadens discussion first to general coordinate-wise weight functions, and then specifically to the Lee weight and a Manhattan like weight. In the general case we provide bounds on $ n $ for which an FWS code exists, and bounds on $ n $ for which an MWS code exists. When specializing to the Lee or to the Manhattan setting we are able to completely determine the parameters of FWS codes. As with the Hamming case, we are able to provide an upper bound on $ M(\mathcal{L},k,q) $ (the minimum length of Lee MWS codes), and pose the determination of $ M(\mathcal{L},k,q) $ as an open problem. On the other hand, with respect to the Manhattan weight we completely determine the parameters of MWS codes.
SatMAE: Pre-training Transformers for Temporal and Multi-Spectral Satellite Imagery
Venue: arXiv cs.CV 2023
Year: 2023

Unsupervised pre-training methods for large vision models have shown to enhance performance on downstream supervised tasks. Developing similar techniques for satellite imagery presents significant opportunities as unlabelled data is plentiful and the inherent temporal and multi-spectral structure provides avenues to further improve existing pre-training strategies. In this paper, we present SatMAE, a pre-training framework for temporal or multi-spectral satellite imagery based on Masked Autoencoder (MAE). To leverage temporal information, we include a temporal embedding along with independently masking image patches across time. In addition, we demonstrate that encoding multi-spectral data as groups of bands with distinct spectral positional encodings is beneficial. Our approach yields strong improvements over previous state-of-the-art techniques, both in terms of supervised learning performance on benchmark datasets (up to $\uparrow$ 7%), and transfer learning performance on downstream remote sensing tasks, including land cover classification (up to $\uparrow$ 14%) and semantic segmentation. Code and data are available on the project website: https://sustainlab-group.github.io/SatMAE/
Protecting Global Properties of Datasets with Distribution Privacy Mechanisms
Venue: arXiv cs.CR 2023
Year: 2023

We consider the problem of ensuring confidentiality of dataset properties aggregated over many records of a dataset. Such properties can encode sensitive information, such as trade secrets or demographic data, while involving a notion of data protection different to the privacy of individual records typically discussed in the literature. In this work, we demonstrate how a distribution privacy framework can be applied to formalize such data confidentiality. We extend the Wasserstein Mechanism from Pufferfish privacy and the Gaussian Mechanism from attribute privacy to this framework, then analyze their underlying data assumptions and how they can be relaxed. We then empirically evaluate the privacy-utility tradeoffs of these mechanisms and apply them against a practical property inference attack which targets global properties of datasets. The results show that our mechanisms can indeed reduce the effectiveness of the attack while providing utility substantially greater than a crude group differential privacy baseline. Our work thus provides groundwork for theoretical mechanisms for protecting global properties of datasets along with their evaluation in practice.
Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points
Venue: arXiv cs.CG 2023
Year: 2023

The most fundamental model of a molecule is a cloud of unordered atoms, even without chemical bonds that can depend on thresholds for distances and angles. The strongest equivalence between clouds of atoms is rigid motion, which is a composition of translations and rotations. The existing datasets of experimental and simulated molecules require a continuous quantification of similarity in terms of a distance metric. While clouds of m ordered points were continuously classified by Lagrange's quadratic forms (distance matrices or Gram matrices), their extensions to m unordered points are impractical due to the exponential number of m! permutations. We propose new metrics that are continuous in general position and are computable in a polynomial time in the number m of unordered points in any Euclidean space of a fixed dimension n.
Active Exploration for Inverse Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

Inverse Reinforcement Learning (IRL) is a powerful paradigm for inferring a reward function from expert demonstrations. Many IRL algorithms require a known transition model and sometimes even a known expert policy, or they at least require access to a generative model. However, these assumptions are too strong for many real-world applications, where the environment can be accessed only through sequential interaction. We propose a novel IRL algorithm: Active exploration for Inverse Reinforcement Learning (AceIRL), which actively explores an unknown environment and expert policy to quickly learn the expert's reward function and identify a good policy. AceIRL uses previous observations to construct confidence intervals that capture plausible reward functions and find exploration policies that focus on the most informative regions of the environment. AceIRL is the first approach to active IRL with sample-complexity bounds that does not require a generative model of the environment. AceIRL matches the sample complexity of active IRL with a generative model in the worst case. Additionally, we establish a problem-dependent bound that relates the sample complexity of AceIRL to the suboptimality gap of a given IRL problem. We empirically evaluate AceIRL in simulations and find that it significantly outperforms more naive exploration strategies.
Structure from Action: Learning Interactions for Articulated Object 3D Structure Discovery
Venue: arXiv cs.CV 2023
Year: 2023

We introduce Structure from Action (SfA), a framework to discover 3D part geometry and joint parameters of unseen articulated objects via a sequence of inferred interactions. Our key insight is that 3D interaction and perception should be considered in conjunction to construct 3D articulated CAD models, especially for categories not seen during training. By selecting informative interactions, SfA discovers parts and reveals occluded surfaces, like the inside of a closed drawer. By aggregating visual observations in 3D, SfA accurately segments multiple parts, reconstructs part geometry, and infers all joint parameters in a canonical coordinate frame. Our experiments demonstrate that a SfA model trained in simulation can generalize to many unseen object categories with diverse structures and to real-world objects. Empirically, SfA outperforms a pipeline of state-of-the-art components by 25.4 3D IoU percentage points on unseen categories, while matching already performant joint estimation baselines.
Generalizing Goal-Conditioned Reinforcement Learning with Variational Causal Reasoning
Venue: arXiv cs.LG 2023
Year: 2023

As a pivotal component to attaining generalizable solutions in human intelligence, reasoning provides great potential for reinforcement learning (RL) agents' generalization towards varied goals by summarizing part-to-whole arguments and discovering cause-and-effect relations. However, how to discover and represent causalities remains a huge gap that hinders the development of causal RL. In this paper, we augment Goal-Conditioned RL (GCRL) with Causal Graph (CG), a structure built upon the relation between objects and events. We novelly formulate the GCRL problem into variational likelihood maximization with CG as latent variables. To optimize the derived objective, we propose a framework with theoretical performance guarantees that alternates between two steps: using interventional data to estimate the posterior of CG; using CG to learn generalizable models and interpretable policies. Due to the lack of public benchmarks that verify generalization capability under reasoning, we design nine tasks and then empirically show the effectiveness of the proposed method against five baselines on these tasks. Further theoretical analysis shows that our performance improvement is attributed to the virtuous cycle of causal discovery, transition modeling, and policy training, which aligns with the experimental evidence in extensive ablation studies.