OpenRaiser/Intern-Atlas huggingface dataset:
Decoupling Long- and Short-Term Patterns in Spatiotemporal Inference
Venue: arXiv cs.LG 2024
Year: 2024

Sensors are the key to environmental monitoring, which impart benefits to smart cities in many aspects, such as providing real-time air quality information to assist human decision-making. However, it is impractical to deploy massive sensors due to the expensive costs, resulting in sparse data collection. Therefore, how to get fine-grained data measurement has long been a pressing issue. In this paper, we aim to infer values at non-sensor locations based on observations from available sensors (termed spatiotemporal inference), where capturing spatiotemporal relationships among the data plays a critical role. Our investigations reveal two significant insights that have not been explored by previous works. Firstly, data exhibits distinct patterns at both long- and short-term temporal scales, which should be analyzed separately. Secondly, short-term patterns contain more delicate relations including those across spatial and temporal dimensions simultaneously, while long-term patterns involve high-level temporal trends. Based on these observations, we propose to decouple the modeling of short-term and long-term patterns. Specifically, we introduce a joint spatiotemporal graph attention network to learn the relations across space and time for short-term patterns. Furthermore, we propose a graph recurrent network with a time skip strategy to alleviate the gradient vanishing problem and model the long-term dependencies. Experimental results on four public real-world datasets demonstrate that our method effectively captures both long- and short-term relations, achieving state-of-the-art performance against existing methods.
The Theoretical Limit of Radar Target Detection
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we solve the optimal target detection problem employing the thoughts and methodologies of Shannon's information theory. Introducing a target state variable into a general radar system model, an equivalent detection channel is derived, and the a posteriori probability distribution is given accordingly. Detection information (DI) is proposed for measuring system performance, which holds for any specific detection method. Moreover, we provide an analytic expression for the false alarm probability concerning the a priori probability. In particular, for a sufficiently large observation interval, the false alarm probability equals the a priori probability of the existing state. A stochastic detection method, the sampling a posteriori probability, is also proposed. The target detection theorem is proved mathematically, which indicates that DI is an achievable theoretical limit of target detection. Specifically, when empirical DI is gained from the sampling a posteriori detection method approaches the DI, the probability of failed decisions tends to be zero. Conversely, there is no detector whose empirical DI is more than DI. Numerical simulations are performed to verify the correctness of the theorems. The results demonstrate that the maximum a posteriori and the Neyman-Pearson detection methods are upper bounded by the theoretical limit.
Near-Field Wideband Beamforming for Extremely Large Antenna Arrays
Venue: arXiv cs.IT 2024
Year: 2024

The natural integration of extremely large antenna arrays (ELAAs) and terahertz (THz) communications can potentially achieve Tbps data rates in 6G networks. However, due to the extremely large array aperture and wide bandwidth, a new phenomenon called "near-field beam split" emerges. This phenomenon causes beams at different frequencies to focus on distinct physical locations, leading to a significant gain loss of beamforming. To address this challenging problem, we first harness a piecewise-far-field channel model to approximate the complicated near-field wideband channel. In this model, the entire large array is partitioned into several small sub-arrays. While the wireless channel's phase discrepancy across the entire array is modeled as near-field spherical, the phase discrepancy within each sub-array is approximated as far-field planar. Built on this approximation, a phase-delay focusing (PDF) method employing delay phase precoding (DPP) architecture is proposed. Our PDF method could compensate for the intra-array far-field phase discrepancy and the inter-array near-field phase discrepancy via the joint control of phase shifters and time delayers, respectively. Theoretical and numerical results are provided to demonstrate the efficiency of the proposed PDF method in mitigating the near-field beam split effect.Finally, we define and derive a novel metric termed the "effective Rayleigh distance" by the evaluation of beamforming gain loss. Compared to classical Rayleigh distance, the effective Rayleigh distance is more accurate in determining the near-field range for practical communications.
LIBRA: Enabling Workload-aware Multi-dimensional Network Topology Optimization for Distributed Training of Large AI Models
Venue: arXiv cs.DC 2024
Year: 2024

As model sizes in machine learning continue to scale, distributed training is necessary to accommodate model weights within each device and to reduce training time. However, this comes with the expense of increased communication overhead due to the exchange of gradients and activations, which become the critical bottleneck of the end-to-end training process. In this work, we motivate the design of multi-dimensional networks within machine learning systems as a cost-efficient mechanism to enhance overall network bandwidth. We also identify that optimal bandwidth allocation is pivotal for multi-dimensional networks to ensure efficient resource utilization. We introduce LIBRA, a framework specifically focused on optimizing multi-dimensional fabric architectures. Through case studies, we demonstrate the value of LIBRA, both in architecting optimized fabrics under diverse constraints and in enabling co-optimization opportunities.
Text-based Person Search in Full Images via Semantic-Driven Proposal Generation
Venue: arXiv cs.CV 2024
Year: 2024

Finding target persons in full scene images with a query of text description has important practical applications in intelligent video surveillance.However, different from the real-world scenarios where the bounding boxes are not available, existing text-based person retrieval methods mainly focus on the cross modal matching between the query text descriptions and the gallery of cropped pedestrian images. To close the gap, we study the problem of text-based person search in full images by proposing a new end-to-end learning framework which jointly optimize the pedestrian detection, identification and visual-semantic feature embedding tasks. To take full advantage of the query text, the semantic features are leveraged to instruct the Region Proposal Network to pay more attention to the text-described proposals. Besides, a cross-scale visual-semantic embedding mechanism is utilized to improve the performance. To validate the proposed method, we collect and annotate two large-scale benchmark datasets based on the widely adopted image-based person search datasets CUHK-SYSU and PRW. Comprehensive experiments are conducted on the two datasets and compared with the baseline methods, our method achieves the state-of-the-art performance.
Neural Knitworks: Patched Neural Implicit Representation Networks
Venue: arXiv cs.CV 2024
Year: 2024

Coordinate-based Multilayer Perceptron (MLP) networks, despite being capable of learning neural implicit representations, are not performant for internal image synthesis applications. Convolutional Neural Networks (CNNs) are typically used instead for a variety of internal generative tasks, at the cost of a larger model. We propose Neural Knitwork, an architecture for neural implicit representation learning of natural images that achieves image synthesis by optimizing the distribution of image patches in an adversarial manner and by enforcing consistency between the patch predictions. To the best of our knowledge, this is the first implementation of a coordinate-based MLP tailored for synthesis tasks such as image inpainting, super-resolution, and denoising. We demonstrate the utility of the proposed technique by training on these three tasks. The results show that modeling natural images using patches, rather than pixels, produces results of higher fidelity. The resulting model requires 80% fewer parameters than alternative CNN-based solutions while achieving comparable performance and training time.
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Venue: arXiv cs.CC 2024
Year: 2024

Cai and Hemachandra used iterative constant-setting to prove that Few $\subseteq$ $\oplus$P (and thus that FewP $\subseteq$ $\oplus$P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant's unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all (O(1) + loglogn)-ambiguity NP sets are in the restricted counting class $\rm RC_{PRIMES}$.
Combining Transformers with Natural Language Explanations
Venue: arXiv cs.CL 2024
Year: 2024

Many NLP applications require models to be interpretable. However, many successful neural architectures, including transformers, still lack effective interpretation methods. A possible solution could rely on building explanations from domain knowledge, which is often available as plain, natural language text. We thus propose an extension to transformer models that makes use of external memories to store natural language explanations and use them to explain classification outputs. We conduct an experimental evaluation on two domains, legal text analysis and argument mining, to show that our approach can produce relevant explanations while retaining or even improving classification performance.
Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
Venue: arXiv cs.DS 2024
Year: 2024

Motivated by a phylogeny reconstruction problem in evolutionary biology, we study the minimum Steiner arborescence problem on directed hypercubes (MSA-DH). Given $m$, representing the directed hypercube $\vec{Q}_m$, and a set of terminals $R$, the problem asks to find a Steiner arborescence that spans $R$ with minimum cost. As $m$ implicitly represents $\vec{Q}_m$ comprising $2^{m}$ vertices, the running time analyses of traditional Steiner tree algorithms on general graphs does not give a clear understanding of the actual complexity of this problem. We present algorithms that exploit the structure of the hypercube and run in time polynomial in $|R|$ and $m$. We explore the MSA-DH problem on three natural parameters - $R$, and two above-guarantee parameters, number of Steiner nodes $p$ and penalty $q$. For above-guarantee parameters, the parameterized MSA-DH problem takes $p \geq 0$ or $q\geq 0$ as input, and outputs a Steiner arborescence with at most $|R| + p - 1$ or $m + q$ edges respectively. We present the following results ($\tilde{\mathcal{O}}$ hides the polynomial factors): 1. An exact algorithm that runs in $\tilde{\mathcal{O}}(3^{|R|})$ time. 2. A randomized algorithm that runs in $\tilde{\mathcal{O}}(9^q)$ time with success probability $\geq 4^{-q}$. 3. An exact algorithm that runs in $\tilde{\mathcal{O}}(36^q)$ time. 4. A $(1+q)$-approximation algorithm that runs in $\tilde{\mathcal{O}}(1.25284^q)$ time. 5. An $\mathcal{O}\left(p\ell_{\mathrm{max}} \right)$-additive approximation algorithm that runs in $\tilde{\mathcal{O}}(\ell_{\mathrm{max}}^{p+2})$ time, where $\ell_{\mathrm{max}}$ is the maximum distance of any terminal from the root.
Complex-valued Federated Learning with Differential Privacy and MRI Applications
Venue: arXiv cs.CR 2024
Year: 2024

Federated learning enhanced with Differential Privacy (DP) is a powerful privacy-preserving strategy to protect individuals sharing their sensitive data for processing in fields such as medicine and healthcare. Many medical applications, for example magnetic resonance imaging (MRI), rely on complex-valued signal processing techniques for data acquisition and analysis. However, the appropriate application of DP to complex-valued data is still underexplored. To address this issue, from the theoretical side, we introduce the complex-valued Gaussian mechanism, whose behaviour we characterise in terms of $f$-DP, $(\varepsilon, δ)$-DP and Rényi-DP. Moreover, we generalise the fundamental algorithm DP stochastic gradient descent to complex-valued neural networks and present novel complex-valued neural network primitives compatible with DP. Experimentally, we showcase a proof-of-concept by training federated complex-valued neural networks with DP on a real-world task (MRI pulse sequence classification in $k$-space), yielding excellent utility and privacy. Our results highlight the relevance of combining federated learning with robust privacy-preserving techniques in the MRI context.
ProgFed: Effective, Communication, and Computation Efficient Federated Learning by Progressive Training
Venue: arXiv cs.LG 2024
Year: 2024

Federated learning is a powerful distributed learning scheme that allows numerous edge devices to collaboratively train a model without sharing their data. However, training is resource-intensive for edge devices, and limited network bandwidth is often the main bottleneck. Prior work often overcomes the constraints by condensing the models or messages into compact formats, e.g., by gradient compression or distillation. In contrast, we propose ProgFed, the first progressive training framework for efficient and effective federated learning. It inherently reduces computation and two-way communication costs while maintaining the strong performance of the final models. We theoretically prove that ProgFed converges at the same asymptotic rate as standard training on full models. Extensive results on a broad range of architectures, including CNNs (VGG, ResNet, ConvNets) and U-nets, and diverse tasks from simple classification to medical image segmentation show that our highly effective training approach saves up to $20\%$ computation and up to $63\%$ communication costs for converged models. As our approach is also complimentary to prior work on compression, we can achieve a wide range of trade-offs by combining these techniques, showing reduced communication of up to $50\times$ at only $0.1\%$ loss in utility. Code is available at https://github.com/hui-po-wang/ProgFed.
Communication-Efficient Triangle Counting under Local Differential Privacy
Venue: arXiv cs.CR 2024
Year: 2024

Triangle counting in networks under LDP (Local Differential Privacy) is a fundamental task for analyzing connection patterns or calculating a clustering coefficient while strongly protecting sensitive friendships from a central server. In particular, a recent study proposes an algorithm for this task that uses two rounds of interaction between users and the server to significantly reduce estimation error. However, this algorithm suffers from a prohibitively high communication cost due to a large noisy graph each user needs to download. In this work, we propose triangle counting algorithms under LDP with a small estimation error and communication cost. We first propose two-rounds algorithms consisting of edge sampling and carefully selecting edges each user downloads so that the estimation error is small. Then we propose a double clipping technique, which clips the number of edges and then the number of noisy triangles, to significantly reduce the sensitivity of each user's query. Through comprehensive evaluation, we show that our algorithms dramatically reduce the communication cost of the existing algorithm, e.g., from 6 hours to 8 seconds or less at a 20 Mbps download rate, while keeping a small estimation error.
WebAssembly enables low latency interoperable augmented and virtual reality software
Venue: arXiv cs.HC 2024
Year: 2024

There is a clear difference in runtime performance between native applications that use augmented/virtual reality (AR/VR) device-specific hardware and comparable web-based implementations. Here we show that WebAssembly (Wasm) offers a promising developer solution that can bring near-native low latency performance to web-based applications, enabling hardware-agnostic interoperability at scale through portable bytecode that runs on any WiFi or cellular data network-enabled AR/VR device. Many software application areas have begun to realize Wasm's potential as a key enabling technology, but it has yet to establish a robust presence in the AR/VR domain. When considering the limitations of current web-based AR/VR development technologies such as WebXR, which provides an existing application programming interface (API) that enables AR/VR capabilities for web-based programs, Wasm can resolve critical issues faced with just-in-time (JIT) compilation, slow run-times, large file sizes, and big data, among other challenges. Existing applications using Wasm-based WebXR are sparse but growing, and the potential for porting native applications to use this emerging framework will benefit the web-based AR/VR application space and bring it closer to its native counterparts in terms of performance. Taken together, this kind of standardized ``write-once-deploy-everywhere'' software framework for AR/VR applications has the potential to consolidate user experiences across different head-mounted displays and other embedded devices to ultimately create an interoperable AR/VR ecosystem.
Role Similarity Metric Based on Spanning Rooted Forest
Venue: arXiv cs.SI 2024
Year: 2024

As a fundamental issue in network analysis, structural node similarity has received much attention in academia and is adopted in a wide range of applications. Among these proposed structural node similarity measures, role similarity stands out because of satisfying several axiomatic properties including automorphism conformation. Existing role similarity metrics cannot handle top-k queries on large real-world networks due to the high time and space cost. In this paper, we propose a new role similarity metric, namely \textsf{ForestSim}. We prove that \textsf{ForestSim} is an admissible role similarity metric and devise the corresponding top-k similarity search algorithm, namely \textsf{ForestSimSearch}, which is able to process a top-k query in $O(k)$ time once the precomputation is finished. Moreover, we speed up the precomputation by using a fast approximate algorithm to compute the diagonal entries of the forest matrix, which reduces the time and space complexity of the precomputation to $O(ε^{-2}m\log^5{n}\log{\frac{1}ε})$ and $O(m\log^3{n})$, respectively. Finally, we conduct extensive experiments on 26 real-world networks. The results show that \textsf{ForestSim} works efficiently on million-scale networks and achieves comparable performance to the state-of-art methods.
On the Completeness and Complexity of the Lifted Dynamic Junction Tree Algorithm
Venue: arXiv cs.AI 2024
Year: 2024

For static lifted inference algorithms, completeness, i.e., domain liftability, is extensively studied. However, so far no domain liftability results for temporal lifted inference algorithms exist. In this paper, we close this gap. More precisely, we contribute the first completeness and complexity analysis for a temporal lifted algorithm, the socalled lifted dynamic junction tree algorithm (LDJT), which is the only exact lifted temporal inference algorithm out there. To handle temporal aspects efficiently, LDJT uses conditional independences to proceed in time, leading to restrictions w.r.t. elimination orders. We show that these restrictions influence the domain liftability results and show that one particular case while proceeding in time, has to be excluded from FO12 . Additionally, for the complexity of LDJT, we prove that the lifted width is in even more cases smaller than the corresponding treewidth in comparison to static inference.
Learning Realtime One-Counter Automata
Venue: arXiv cs.FL 2024
Year: 2024

We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin's L* algorithm, as well as counter value queries and partial equivalence queries. In a partial equivalence query, we ask the teacher whether the language of a given finite-state automaton coincides with a counter-bounded subset of the target language. We evaluate an implementation of our algorithm on a number of random benchmarks and on a use case regarding efficient JSON-stream validation.
Similarity-Aware Skill Reproduction based on Multi-Representational Learning from Demonstration
Venue: arXiv cs.RO 2024
Year: 2024

Learning from Demonstration (LfD) algorithms enable humans to teach new skills to robots through demonstrations. The learned skills can be robustly reproduced from the identical or near boundary conditions (e.g., initial point). However, when generalizing a learned skill over boundary conditions with higher variance, the similarity of the reproductions changes from one boundary condition to another, and a single LfD representation cannot preserve a consistent similarity across a generalization region. We propose a novel similarity-aware framework including multiple LfD representations and a similarity metric that can improve skill generalization by finding reproductions with the highest similarity values for a given boundary condition. Given a demonstration of the skill, our framework constructs a similarity region around a point of interest (e.g., initial point) by evaluating individual LfD representations using the similarity metric. Any point within this volume corresponds to a representation that reproduces the skill with the greatest similarity. We validate our multi-representational framework in three simulated and four sets of real-world experiments using a physical 6-DOF robot. We also evaluate 11 different similarity metrics and categorize them according to their biases in 286 simulated experiments.