OpenRaiser/Intern-Atlas huggingface dataset:
Improved Energy-Based Signal Detection for Ambient Backscatter Communications
Venue: arXiv cs.IT 2024
Year: 2024

In ambient backscatter communication (AmBC) systems, passive tags connect to a reader by reflecting an ambient radio frequency (RF) signal. However, the reader may not know the channel states and RF source parameters. The traditional energy detector (TED) appears to be an ideal solution. However, it performs poorly under these conditions. To address this, we propose two new detectors: (1) A joint correlation-energy detector (JCED) based on the first-order correlation of the received samples and (2) An improved energy detector (IED) based on the p-th norm of the received signal vector. We compare the performance of IED and TED under the generalized noise model using McLeish distribution and derive a general analytical formula for the area under the receiver operating characteristic (ROC) curves. Based on our results, both detectors outperform TED. For example, the probability of detection with a false alarm rate of 1\% for JCED and IED is 22.97\% and 5.41\% higher, respectively, compared to TED for a single-antenna reader. Using the direct interference cancellation (DIC) technique, these gains are 34.92\% and 3.7\%, respectively. With a four-antenna array at the reader and a 5\% false alarm rate, the JCED shows a significant BER improvement of 28.68\% without DIC and 48.21\% with DIC.
Locally Differentially Private Distributed Online Learning with Guaranteed Optimality
Venue: arXiv cs.LG 2024
Year: 2024

Distributed online learning is gaining increased traction due to its unique ability to process large-scale datasets and streaming data. To address the growing public awareness and concern on privacy protection, plenty of algorithms have been proposed to enable differential privacy in distributed online optimization and learning. However, these algorithms often face the dilemma of trading learning accuracy for privacy. By exploiting the unique characteristics of online learning, this paper proposes an approach that tackles the dilemma and ensures both differential privacy and learning accuracy in distributed online learning. More specifically, while ensuring a diminishing expected instantaneous regret, the approach can simultaneously ensure a finite cumulative privacy budget, even in the infinite time horizon. To cater for the fully distributed setting, we adopt the local differential-privacy framework, which avoids the reliance on a trusted data curator that is required in the classic "centralized" (global) differential-privacy framework. To the best of our knowledge, this is the first algorithm that successfully ensures both rigorous local differential privacy and learning accuracy. The effectiveness of the proposed algorithm is evaluated using machine learning tasks, including logistic regression on the the "mushrooms" datasets and CNN-based image classification on the "MNIST" and "CIFAR-10" datasets.
BotanicGarden: A High-Quality Dataset for Robot Navigation in Unstructured Natural Environments
Venue: arXiv cs.RO 2024
Year: 2024

The rapid developments of mobile robotics and autonomous navigation over the years are largely empowered by public datasets for testing and upgrading, such as sensor odometry and SLAM tasks. Impressive demos and benchmark scores have arisen, which may suggest the maturity of existing navigation techniques. However, these results are primarily based on moderate structured scenario testing. When transitioning to challenging unstructured environments, especially in GNSS-denied, texture-monotonous, and dense-vegetated natural fields, their performance can hardly sustain at a high level and requires further validation and improvement. To bridge this gap, we build a novel robot navigation dataset in a luxuriant botanic garden of more than 48000m2. Comprehensive sensors are used, including Gray and RGB stereo cameras, spinning and MEMS 3D LiDARs, and low-cost and industrial-grade IMUs, all of which are well calibrated and hardware-synchronized. An all-terrain wheeled robot is employed for data collection, traversing through thick woods, riversides, narrow trails, bridges, and grasslands, which are scarce in previous resources. This yields 33 short and long sequences, forming 17.1km trajectories in total. Excitedly, both highly-accurate ego-motions and 3D map ground truth are provided, along with fine-annotated vision semantics. We firmly believe that our dataset can advance robot navigation and sensor fusion research to a higher level.
Time and State Dependent Neural Delay Differential Equations
Venue: arXiv cs.AI 2024
Year: 2024

Discontinuities and delayed terms are encountered in the governing equations of a large class of problems ranging from physics and engineering to medicine and economics. These systems cannot be properly modelled and simulated with standard Ordinary Differential Equations (ODE), or data-driven approximations such as Neural Ordinary Differential Equations (NODE). To circumvent this issue, latent variables are typically introduced to solve the dynamics of the system in a higher dimensional space and obtain the solution as a projection to the original space. However, this solution lacks physical interpretability. In contrast, Delay Differential Equations (DDEs), and their data-driven approximated counterparts, naturally appear as good candidates to characterize such systems. In this work we revisit the recently proposed Neural DDE by introducing Neural State-Dependent DDE (SDDDE), a general and flexible framework that can model multiple and state- and time-dependent delays. We show that our method is competitive and outperforms other continuous-class models on a wide variety of delayed dynamical systems. Code is available at the repository \href{https://github.com/thibmonsel/Time-and-State-Dependent-Neural-Delay-Differential-Equations}{here}.
Dialectical Reconciliation via Structured Argumentative Dialogues
Venue: arXiv cs.AI 2024
Year: 2024

We present a novel framework designed to extend model reconciliation approaches, commonly used in human-aware planning, for enhanced human-AI interaction. By adopting a structured argumentation-based dialogue paradigm, our framework enables dialectical reconciliation to address knowledge discrepancies between an explainer (AI agent) and an explainee (human user), where the goal is for the explainee to understand the explainer's decision. We formally describe the operational semantics of our proposed framework, providing theoretical guarantees. We then evaluate the framework's efficacy ``in the wild'' via computational and human-subject experiments. Our findings suggest that our framework offers a promising direction for fostering effective human-AI interactions in domains where explainability is important.
Optimized Vectorizing of Building Structures with Switch: High-Efficiency Convolutional Channel-Switch Hybridization Strategy
Venue: arXiv cs.AI 2024
Year: 2024

The building planar graph reconstruction, a.k.a. footprint reconstruction, which lies in the domain of computer vision and geoinformatics, has been long afflicted with the challenge of redundant parameters in conventional convolutional models. Therefore, in this letter, we proposed an advanced and adaptive shift architecture, namely the Switch operator, which incorporates non-exponential growth parameters while retaining analogous functionalities to integrate local feature spatial information, resembling a high-dimensional convolution operation. The Switch operator, cross-channel operation, architecture implements the XOR operation to alternately exchange adjacent or diagonal features, and then blends alternating channels through a 1x1 convolution operation to consolidate information from different channels. The SwitchNN architecture, on the other hand, incorporates a group-based parameter-sharing mechanism inspired by the convolutional neural network process and thereby significantly reducing the number of parameters. We validated our proposed approach through experiments on the SpaceNet corpus, a publicly available dataset annotated with 2,001 buildings across the cities of Los Angeles, Las Vegas, and Paris. Our results demonstrate the effectiveness of this innovative architecture in building planar graph reconstruction from 2D building images.
Privacy-Preserving Community Detection for Locally Distributed Multiple Networks
Venue: arXiv cs.SI 2024
Year: 2024

Modern multi-layer networks are commonly stored and analyzed in a local and distributed fashion because of the privacy, ownership, and communication costs. The literature on the model-based statistical methods for community detection based on these data is still limited. This paper proposes a new method for consensus community detection and estimation in a multi-layer stochastic block model using locally stored and computed network data with privacy protection. A novel algorithm named privacy-preserving Distributed Spectral Clustering (ppDSC) is developed. To preserve the edges' privacy, we adopt the randomized response (RR) mechanism to perturb the network edges, which satisfies the strong notion of differential privacy. The ppDSC algorithm is performed on the squared RR-perturbed adjacency matrices to prevent possible cancellation of communities among different layers. To remove the bias incurred by RR and the squared network matrices, we develop a two-step bias-adjustment procedure. Then we perform eigen-decomposition on the debiased matrices, aggregation of the local eigenvectors using an orthogonal Procrustes transformation, and k-means clustering. We provide theoretical analysis on the statistical errors of ppDSC in terms of eigen-vector estimation. In addition, the blessings and curses of network heterogeneity are well-explained by our bounds.
What Makes ImageNet Look Unlike LAION
Venue: arXiv cs.LG 2024
Year: 2024

ImageNet was famously created from Flickr image search results. What if we recreated ImageNet instead by searching the massive LAION dataset based on image captions alone? In this work, we carry out this counterfactual investigation. We find that the resulting ImageNet recreation, which we call LAIONet, looks distinctly unlike the original. Specifically, the intra-class similarity of images in the original ImageNet is dramatically higher than it is for LAIONet. Consequently, models trained on ImageNet perform significantly worse on LAIONet. We propose a rigorous explanation for the discrepancy in terms of a subtle, yet important, difference in two plausible causal data-generating processes for the respective datasets, that we support with systematic experimentation. In a nutshell, searching based on an image caption alone creates an information bottleneck that mitigates the selection bias otherwise present in image-based filtering. Our explanation formalizes a long-held intuition in the community that ImageNet images are stereotypical, unnatural, and overly simple representations of the class category. At the same time, it provides a simple and actionable takeaway for future dataset creation efforts.
Fair and Almost Truthful Mechanisms for Additive Valuations and Beyond
Venue: arXiv cs.GT 2024
Year: 2024

We study the problem of fairly allocating indivisible goods among $n$ strategic agents. It is well-known that truthfulness is incompatible with any meaningful fairness notions. We bypass the strong negative result by considering the concept of incentive ratio, a relaxation of truthfulness quantifying agents' incentive to misreport. Previous studies show that Round-Robin, which satisfies envy-freeness up to one good (EF1), achieves an incentive ratio of $2$ for additive valuations. In this paper, we explore the incentive ratio achievable by fair mechanisms for various classes of valuations besides additive ones. We first show that, for arbitrary $ε> 0$, every $(\frac{1}{2} + ε)$-EF1 mechanism for additive valuations admits an incentive ratio of at least $1.5$. Then, using the above lower bound for additive valuations in a black-box manner, we show that for arbitrary $ε> 0$, every $ε$-EF1 mechanism for cancelable valuations admits an infinite incentive ratio. Moreover, for subadditive cancelable valuations, we show that Round-Robin, which satisfies EF1, achieves an incentive ratio of $2$, and every $(φ- 1)$-EF1 mechanism admits an incentive ratio of at least $φ$ with $φ= (1 + \sqrt{5}) / 2 \approx 1.618$. Finally, for submodular valuations, we show that Round-Robin, which satisfies $\frac{1}{2}$-EF1, admits an incentive ratio of $n$.
Divide-and-rule policy in the Naming Game
Venue: arXiv cs.SI 2024
Year: 2024

The Naming Game is a classic model for studying the emergence and evolution of language within a population. In this paper, we extend the traditional Naming Game model to encompass multiple committed opinions and investigate the system dynamics on the complete graph with an arbitrarily large population and random networks of finite size. For the fully connected complete graph, the homogeneous mixing condition enables us to use mean-field theory to analyze the opinion evolution of the system. However, when the number of opinions increases, the number of variables describing the system grows exponentially. To mitigate this, we focus on a special scenario where the largest group of committed agents competes with a motley of committed groups, each of which is smaller than the largest one, while initially, most of uncommitted agents hold one unique opinion. This scenario is chosen for its recurrence in diverse societies and its potential for complexity reduction by unifying agents from smaller committed groups into one category. Our investigation reveals that when the size of the largest committed group reaches the critical threshold, most of uncommitted agents change their beliefs to this opinion, triggering a phase transition. Further, we derive the general formula for the multi-opinion evolution using a recursive approach, enabling investigation into any scenario. Finally, we employ agent-based simulations to reveal the opinion evolution and dominance transition in random graphs. Our results provide insights into the conditions under which the dominant opinion emerges in a population and the factors that influence these conditions.
Refining the Adaptivity Notion in the Huge Object Model
Venue: arXiv cs.DS 2024
Year: 2024

The Huge Object model for distribution testing, first defined by Goldreich and Ron in 2022, combines the features of classical string testing and distribution testing. In this model we are given access to independent samples from an unknown distribution $P$ over the set of strings $\{0,1\}^n$, but are only allowed to query a few bits from the samples. The distinction between adaptive and non-adaptive algorithms, which occurs naturally in the realm of string testing (while being irrelevant for classical distribution testing), plays a substantial role also in the Huge Object model. In this work we show that the full picture in the Huge Object model is much richer than just that of the ``adaptive vs. non-adaptive'' dichotomy. We define and investigate several models of adaptivity that lie between the fully-adaptive and the completely non-adaptive extremes. These models are naturally grounded by observing the querying process from each sample independently, and considering the ``algorithmic flow'' between them. For example, if we allow no information at all to cross over between samples (up to the final decision), then we obtain the locally bounded adaptive model, arguably the ``least adaptive'' one apart from being completely non-adaptive. A slightly stronger model allows only a ``one-way'' information flow. Even stronger (but still far from being fully adaptive) models follow by taking inspiration from the setting of streaming algorithms. To show that we indeed have a hierarchy, we prove a chain of exponential separations encompassing most of the models that we define.
Generative User-Experience Research for Developing Domain-specific Natural Language Processing Applications
Venue: arXiv cs.CL 2024
Year: 2024

User experience (UX) is a part of human-computer interaction (HCI) research and focuses on increasing intuitiveness, transparency, simplicity, and trust for the system users. Most UX research for machine learning (ML) or natural language processing (NLP) focuses on a data-driven methodology. It engages domain users mainly for usability evaluation. Moreover, more typical UX methods tailor the systems towards user usability, unlike learning about the user needs first. This paper proposes a new methodology for integrating generative UX research into developing domain NLP applications. Generative UX research employs domain users at the initial stages of prototype development, i.e., ideation and concept evaluation, and the last stage for evaluating system usefulness and user utility. The methodology emerged from and is evaluated on a case study about the full-cycle prototype development of a domain-specific semantic search for daily operations in the process industry. A key finding of our case study is that involving domain experts increases their interest and trust in the final NLP application. The combined UX+NLP research of the proposed method efficiently considers data- and user-driven opportunities and constraints, which can be crucial for developing NLP applications.
Latent SDEs on Homogeneous Spaces
Venue: arXiv cs.LG 2024
Year: 2024

We consider the problem of variational Bayesian inference in a latent variable model where a (possibly complex) observed stochastic process is governed by the solution of a latent stochastic differential equation (SDE). Motivated by the challenges that arise when trying to learn an (almost arbitrary) latent neural SDE from data, such as efficient gradient computation, we take a step back and study a specific subclass instead. In our case, the SDE evolves on a homogeneous latent space and is induced by stochastic dynamics of the corresponding (matrix) Lie group. In learning problems, SDEs on the unit n-sphere are arguably the most relevant incarnation of this setup. Notably, for variational inference, the sphere not only facilitates using a truly uninformative prior, but we also obtain a particularly simple and intuitive expression for the Kullback-Leibler divergence between the approximate posterior and prior process in the evidence lower bound. Experiments demonstrate that a latent SDE of the proposed type can be learned efficiently by means of an existing one-step geometric Euler-Maruyama scheme. Despite restricting ourselves to a less rich class of SDEs, we achieve competitive or even state-of-the-art results on various time series interpolation/classification problems.
Proving Confluence in the Confluence Framework with CONFident
Venue: arXiv cs.LO 2024
Year: 2024

This article describes the *Confluence Framework*, a novel framework for proving and disproving confluence using a divide-and-conquer modular strategy, and its implementation in CONFident. Using this approach, we are able to automatically prove and disprove confluence of *Generalized Term Rewriting Systems*, where (i) only selected arguments of function symbols can be rewritten and (ii) a rather general class of conditional rules can be used. This includes, as particular cases, several variants of rewrite systems such as (context-sensitive) *term rewriting systems*, *string rewriting systems*, and (context-sensitive) *conditional term rewriting systems*. The divide-and-conquer modular strategy allows us to combine in a proof tree different techniques for proving confluence, including modular decompositions, checking joinability of (conditional) critical and variable pairs, transformations, etc., and auxiliary tasks required by them, e.g., joinability of terms, joinability of conditional pairs, etc.
Rapid-INR: Storage Efficient CPU-free DNN Training Using Implicit Neural Representation
Venue: arXiv cs.CV 2024
Year: 2024

Implicit Neural Representation (INR) is an innovative approach for representing complex shapes or objects without explicitly defining their geometry or surface structure. Instead, INR represents objects as continuous functions. Previous research has demonstrated the effectiveness of using neural networks as INR for image compression, showcasing comparable performance to traditional methods such as JPEG. However, INR holds potential for various applications beyond image compression. This paper introduces Rapid-INR, a novel approach that utilizes INR for encoding and compressing images, thereby accelerating neural network training in computer vision tasks. Our methodology involves storing the whole dataset directly in INR format on a GPU, mitigating the significant data communication overhead between the CPU and GPU during training. Additionally, the decoding process from INR to RGB format is highly parallelized and executed on-the-fly. To further enhance compression, we propose iterative and dynamic pruning, as well as layer-wise quantization, building upon previous work. We evaluate our framework on the image classification task, utilizing the ResNet-18 backbone network and three commonly used datasets with varying image sizes. Rapid-INR reduces memory consumption to only about 5% of the original dataset size in RGB format and achieves a maximum 6$\times$ speedup over the PyTorch training pipeline, as well as a maximum 1.2x speedup over the DALI training pipeline, with only a marginal decrease in accuracy. Importantly, Rapid-INR can be readily applied to other computer vision tasks and backbone networks with reasonable engineering efforts. Our implementation code is publicly available at https://github.com/sharc-lab/Rapid-INR.
SWAT: A System-Wide Approach to Tunable Leakage Mitigation in Encrypted Data Stores
Venue: arXiv cs.CR 2024
Year: 2024

Numerous studies have underscored the significant privacy risks associated with various leakage patterns in encrypted data stores. While many solutions have been proposed to mitigate these leakages, they either (1) incur substantial overheads, (2) focus on specific subsets of leakage patterns, or (3) apply the same security notion across various workloads, thereby impeding the attainment of fine-tuned privacy-efficiency trade-offs. In light of various detrimental leakage patterns, this paper starts with an investigation into which specific leakage patterns require our focus in the contexts of key-value, range-query, and dynamic workloads, respectively. Subsequently, we introduce new security notions tailored to the specific privacy requirements of these workloads. Accordingly, we propose and instantiate SWAT, an efficient construction that progressively enables these workloads, while provably mitigating system-wide leakage via a suite of algorithms with tunable privacy-efficiency trade-offs. We conducted extensive experiments and compiled a detailed result analysis, showing the efficiency of our solution. SWATis about an order of magnitude slower than an encryption-only data store that reveals various leakage patterns and is two orders of magnitude faster than a trivial zero-leakage solution. Meanwhile, the performance of SWATremains highly competitive compared to other designs that mitigate specific types of leakage.