OpenRaiser/Intern-Atlas huggingface dataset:
New Delay Doppler Communication Paradigm in 6G era: A Survey of Orthogonal Time Frequency Space (OTFS)
Venue: arXiv cs.IT 2023
Year: 2023

In the 6G era, space-air-Ground integrated networks (SAGIN) are anticipated to deliver global coverage, necessitating support for a diverse array of emerging applications in high-mobility, hostile environments. Under such conditions, conventional orthogonal frequency division multiplexing (OFDM) modulation, widely employed in cellular and Wi-Fi communication systems, experiences performance degradation due to significant Doppler shifts. To overcome this obstacle, a novel two-dimensional (2D) modulation approach, namely orthogonal time frequency space (OTFS), has emerged as a key enabler for future high-mobility use cases. Distinctively, OTFS modulates information within the delay-Doppler (DD) domain, as opposed to the time-frequency (TF) domain utilized by OFDM. This offers advantages such as Doppler and delay resilience, reduced signaling latency, a lower peak-to-average ratio (PAPR), and a reduced-complexity implementation. Recent studies further indicate that the direct interplay between information and the physical world in the DD domain positions OTFS as a promising waveform for achieving integrated sensing and communications (ISAC). In this article, we present an in-depth review of OTFS technology in the context of the 6G era, encompassing fundamentals, recent advancements, and future directions. Our objective is to provide a valuable resource for researchers engaged in the field of OTFS.
Unsupervised Unlearning of Concept Drift with Autoencoders
Venue: arXiv cs.LG 2023
Year: 2023

Concept drift refers to a change in the data distribution affecting the data stream of future samples. Consequently, learning models operating on the data stream might become obsolete, and need costly and difficult adjustments such as retraining or adaptation. Existing methods usually implement a local concept drift adaptation scheme, where either incremental learning of the models is used, or the models are completely retrained when a drift detection mechanism triggers an alarm. This paper proposes an alternative approach in which an unsupervised and model-agnostic concept drift adaptation method at the global level is introduced, based on autoencoders. Specifically, the proposed method aims to ``unlearn'' the concept drift without having to retrain or adapt any of the learning models operating on the data. An extensive experimental evaluation is conducted in two application domains. We consider a realistic water distribution network with more than 30 models in-place, from which we create 200 simulated data sets / scenarios. We further consider an image-related task to demonstrate the effectiveness of our method.
Physics-Based Object 6D-Pose Estimation during Non-Prehensile Manipulation
Venue: arXiv cs.RO 2023
Year: 2023

We propose a method to track the 6D pose of an object over time, while the object is under non-prehensile manipulation by a robot. At any given time during the manipulation of the object, we assume access to the robot joint controls and an image from a camera. We use the robot joint controls to perform a physics-based prediction of how the object might be moving. We then combine this prediction with the observation coming from the camera, to estimate the object pose as accurately as possible. We use a particle filtering approach to combine the control information with the visual information. We compare the proposed method with two baselines: (i) using only an image-based pose estimation system at each time-step, and (ii) a particle filter which does not perform the computationally expensive physics predictions, but assumes the object moves with constant velocity. Our results show that making physics-based predictions is worth the computational cost, resulting in more accurate tracking, and estimating object pose even when the object is not clearly visible to the camera.
FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption
Venue: arXiv cs.CR 2023
Year: 2023

Fully Homomorphic Encryption is a technique that allows computation on encrypted data. It has the potential to change privacy considerations in the cloud, but computational and memory overheads are preventing its adoption. TFHE is a promising Torus-based FHE scheme that relies on bootstrapping, the noise-removal tool invoked after each encrypted logical/arithmetical operation. We present FPT, a Fixed-Point FPGA accelerator for TFHE bootstrapping. FPT is the first hardware accelerator to exploit the inherent noise present in FHE calculations. Instead of double or single-precision floating-point arithmetic, it implements TFHE bootstrapping entirely with approximate fixed-point arithmetic. Using an in-depth analysis of noise propagation in bootstrapping FFT computations, FPT is able to use noise-trimmed fixed-point representations that are up to 50% smaller than prior implementations. FPT is built as a streaming processor inspired by traditional streaming DSPs: it instantiates directly cascaded high-throughput computational stages, with minimal control logic and routing networks. We explore throughput-balanced compositions of streaming kernels with a user-configurable streaming width in order to construct a full bootstrapping pipeline. Our approach allows 100% utilization of arithmetic units and requires only a small bootstrapping key cache, enabling an entirely compute-bound bootstrapping throughput of 1 BS / 35us. This is in stark contrast to the classical CPU approach to FHE bootstrapping acceleration, which is typically constrained by memory and bandwidth. FPT is implemented and evaluated as a bootstrapping FPGA kernel for an Alveo U280 datacenter accelerator card. FPT achieves two to three orders of magnitude higher bootstrapping throughput than existing CPU-based implementations, and 2.5x higher throughput compared to recent ASIC emulation experiments.
Global and Local Hierarchy-aware Contrastive Framework for Implicit Discourse Relation Recognition
Venue: arXiv cs.CL 2023
Year: 2023

Due to the absence of explicit connectives, implicit discourse relation recognition (IDRR) remains a challenging task in discourse analysis. The critical step for IDRR is to learn high-quality discourse relation representations between two arguments. Recent methods tend to integrate the whole hierarchical information of senses into discourse relation representations for multi-level sense recognition. Nevertheless, they insufficiently incorporate the static hierarchical structure containing all senses (defined as global hierarchy), and ignore the hierarchical sense label sequence corresponding to each instance (defined as local hierarchy). For the purpose of sufficiently exploiting global and local hierarchies of senses to learn better discourse relation representations, we propose a novel GlObal and Local Hierarchy-aware Contrastive Framework (GOLF), to model two kinds of hierarchies with the aid of multi-task learning and contrastive learning. Experimental results on PDTB 2.0 and PDTB 3.0 datasets demonstrate that our method remarkably outperforms current state-of-the-art models at all hierarchical levels. Our code is publicly available at https://github.com/YJiangcm/GOLF_for_IDRR
Towards Better Bounds for Finding Quasi-Identifiers
Venue: arXiv cs.DS 2023
Year: 2023

We revisit the problem of finding small $ε$-separation keys introduced by Motwani and Xu (2008). In this problem, the input is $m$-dimensional tuples $x_1,x_2,\ldots,x_n $. The goal is to find a small subset of coordinates that separates at least $(1-ε){n \choose 2}$ pairs of tuples. They provided a fast algorithm that runs on $Θ(m/ε)$ tuples sampled uniformly at random. We show that the sample size can be improved to $Θ(m/\sqrtε)$. Our algorithm also enjoys a faster running time. To obtain this result, we provide upper and lower bounds on the sample size to solve the following decision problem. Given a subset of coordinates $A$, reject if $A$ separates fewer than $(1-ε){n \choose 2}$ pairs, and accept if $A$ separates all pairs. The algorithm must be correct with probability at least $1-δ$ for all $A$. We show that for algorithms based on sampling: - $Θ(m/\sqrtε)$ samples are sufficient and necessary so that $δ\leq e^{-m}$ and - $Ω(\sqrt{\frac{\log m}ε})$ samples are necessary so that $δ$ is a constant. Our analysis is based on a constrained version of the balls-into-bins problem. We believe our analysis may be of independent interest. We also study a related problem that asks for the following sketching algorithm: with given parameters $α,k$ and $ε$, the algorithm takes a subset of coordinates $A$ of size at most $k$ and returns an estimate of the number of unseparated pairs in $A$ up to a $(1\pmε)$ factor if it is at least $α{n \choose 2}$. We show that even for constant $α$ and success probability, such a sketching algorithm must use $Ω(mk \log ε^{-1})$ bits of space; on the other hand, uniform sampling yields a sketch of size $Θ(\frac{mk \log m}{αε^2})$ for this purpose.
Complementary Explanations for Effective In-Context Learning
Venue: arXiv cs.CL 2023
Year: 2023

Large language models (LLMs) have exhibited remarkable capabilities in learning from explanations in prompts, but there has been limited understanding of exactly how these explanations function or why they are effective. This work aims to better understand the mechanisms by which explanations are used for in-context learning. We first study the impact of two different factors on the performance of prompts with explanations: the computation trace (the way the solution is decomposed) and the natural language used to express the prompt. By perturbing explanations on three controlled tasks, we show that both factors contribute to the effectiveness of explanations. We further study how to form maximally effective sets of explanations for solving a given test query. We find that LLMs can benefit from the complementarity of the explanation set: diverse reasoning skills shown by different exemplars can lead to better performance. Therefore, we propose a maximal marginal relevance-based exemplar selection approach for constructing exemplar sets that are both relevant as well as complementary, which successfully improves the in-context learning performance across three real-world tasks on multiple LLMs.
Learning General Audio Representations with Large-Scale Training of Patchout Audio Transformers
Venue: arXiv cs.SD 2023
Year: 2023

The success of supervised deep learning methods is largely due to their ability to learn relevant features from raw data. Deep Neural Networks (DNNs) trained on large-scale datasets are capable of capturing a diverse set of features, and learning a representation that can generalize onto unseen tasks and datasets that are from the same domain. Hence, these models can be used as powerful feature extractors, in combination with shallower models as classifiers, for smaller tasks and datasets where the amount of training data is insufficient for learning an end-to-end model from scratch. During the past years, Convolutional Neural Networks (CNNs) have largely been the method of choice for audio processing. However, recently attention-based transformer models have demonstrated great potential in supervised settings, outperforming CNNs. In this work, we investigate the use of audio transformers trained on large-scale datasets to learn general-purpose representations. We study how the different setups in these audio transformers affect the quality of their embeddings. We experiment with the models' time resolution, extracted embedding level, and receptive fields in order to see how they affect performance on a variety of tasks and datasets, following the HEAR 2021 NeurIPS challenge evaluation setup. Our results show that representations extracted by audio transformers outperform CNN representations. Furthermore, we will show that transformers trained on Audioset can be extremely effective representation extractors for a wide range of downstream tasks.
The European AI Liability Directives -- Critique of a Half-Hearted Approach and Lessons for the Future
Venue: arXiv cs.CY 2023
Year: 2023

As ChatGPT et al. conquer the world, the optimal liability framework for AI systems remains an unsolved problem across the globe. In a much-anticipated move, the European Commission advanced two proposals outlining the European approach to AI liability in September 2022: a novel AI Liability Directive and a revision of the Product Liability Directive. They constitute the final cornerstone of EU AI regulation. Crucially, the liability proposals and the EU AI Act are inherently intertwined: the latter does not contain any individual rights of affected persons, and the former lack specific, substantive rules on AI development and deployment. Taken together, these acts may well trigger a Brussels Effect in AI regulation, with significant consequences for the US and beyond. This paper makes three novel contributions. First, it examines in detail the Commission proposals and shows that, while making steps in the right direction, they ultimately represent a half-hearted approach: if enacted as foreseen, AI liability in the EU will primarily rest on disclosure of evidence mechanisms and a set of narrowly defined presumptions concerning fault, defectiveness and causality. Hence, second, the article suggests amendments, which are collected in an Annex at the end of the paper. Third, based on an analysis of the key risks AI poses, the final part of the paper maps out a road for the future of AI liability and regulation, in the EU and beyond. This includes: a comprehensive framework for AI liability; provisions to support innovation; an extension to non-discrimination/algorithmic fairness, as well as explainable AI; and sustainability. I propose to jump-start sustainable AI regulation via sustainability impact assessments in the AI Act and sustainable design defects in the liability regime. In this way, the law may help spur not only fair AI and XAI, but potentially also sustainable AI (SAI).
A Configurable Protocol for Quantum Entanglement Distribution to End Nodes
Venue: arXiv cs.NI 2023
Year: 2023

The primary task of a quantum repeater network is to deliver entanglement among end nodes. Most of existing entanglement distribution protocols do not consider purification, which is thus delegated to an upper layer. This is a major drawback since, once an end-to-end entangled connection (or a portion thereof) is established it cannot be purified if its fidelity (F) does not fall within an interval bounded by Fmin (greater than 0.5) and Fmax (less than 1). In this paper, we propose the Ranked Entanglement Distribution Protocol (REDiP), a connection-oriented protocol that overcomes the above drawback. This result was achieved by including in our protocol two mechanisms for carrying out jointly purification and entanglement swapping. We use simulations to investigate the impact of these mechanisms on the performance of a repeater network, in terms of throughput and fidelity. Moreover, we show how REDiP can easily be configured to implement custom entanglement swapping and purification strategies, including (but not restricted to) those adopted in two recent works.
Re^2TAL: Rewiring Pretrained Video Backbones for Reversible Temporal Action Localization
Venue: arXiv cs.CV 2023
Year: 2023

Temporal action localization (TAL) requires long-form reasoning to predict actions of various durations and complex content. Given limited GPU memory, training TAL end to end (i.e., from videos to predictions) on long videos is a significant challenge. Most methods can only train on pre-extracted features without optimizing them for the localization problem, consequently limiting localization performance. In this work, to extend the potential in TAL networks, we propose a novel end-to-end method Re2TAL, which rewires pretrained video backbones for reversible TAL. Re2TAL builds a backbone with reversible modules, where the input can be recovered from the output such that the bulky intermediate activations can be cleared from memory during training. Instead of designing one single type of reversible module, we propose a network rewiring mechanism, to transform any module with a residual connection to a reversible module without changing any parameters. This provides two benefits: (1) a large variety of reversible networks are easily obtained from existing and even future model designs, and (2) the reversible models require much less training effort as they reuse the pre-trained parameters of their original non-reversible versions. Re2TAL, only using the RGB modality, reaches 37.01% average mAP on ActivityNet-v1.3, a new state-of-the-art record, and mAP 64.9% at tIoU=0.5 on THUMOS-14, outperforming all other RGB-only methods.
Secure Distributed Gram Matrix Multiplication
Venue: arXiv cs.IT 2023
Year: 2023

The Gram matrix of a matrix $A$ is defined as $AA^T$ (or $A^T\!A$). Computing the Gram matrix is an important operation in many applications, such as linear regression with the least squares method, where the explicit solution formula includes the Gram matrix of the data matrix. Secure distributed matrix multiplication (SDMM) can be used to compute the product of two matrices using the help of worker servers. If a Gram matrix were computed using SDMM, the data matrix would need to be encoded twice, which causes an unnecessary overhead in the communication cost. We propose a new scheme for this purpose called secure distributed Gram matrix multiplication (SDGMM). It can leverage the advantages of computing a Gram matrix instead of a regular matrix product.
On the Effect of Anticipation on Reading Times
Venue: arXiv cs.CL 2023
Year: 2023

Over the past two decades, numerous studies have demonstrated how less predictable (i.e., higher surprisal) words take more time to read. In general, these studies have implicitly assumed the reading process is purely responsive: Readers observe a new word and allocate time to process it as required. We argue that prior results are also compatible with a reading process that is at least partially anticipatory: Readers could make predictions about a future word and allocate time to process it based on their expectation. In this work, we operationalize this anticipation as a word's contextual entropy. We assess the effect of anticipation on reading by comparing how well surprisal and contextual entropy predict reading times on four naturalistic reading datasets: two self-paced and two eye-tracking. Experimentally, across datasets and analyses, we find substantial evidence for effects of contextual entropy over surprisal on a word's reading time (RT): in fact, entropy is sometimes better than surprisal in predicting a word's RT. Spillover effects, however, are generally not captured by entropy, but only by surprisal. Further, we hypothesize four cognitive mechanisms through which contextual entropy could impact RTs -- three of which we are able to design experiments to analyze. Overall, our results support a view of reading that is not just responsive, but also anticipatory.
Multidimensional rank-one convexification of incremental damage models at finite strains
Venue: arXiv cs.CE 2023
Year: 2023

This paper presents computationally feasible rank-one relaxation algorithms for the efficient simulation of a time-incremental damage model with nonconvex incremental stress potentials in multiple spatial dimensions. While the standard model suffers from numerical issues due to the lack of convexity, the relaxation by rank-one convexification prevents non-existence of minimizers and mesh dependence of the solutions of finite element discretizations. By the combination, modification and parallelization of the underlying convexification algorithms, the novel approach becomes computationally feasible. A descent method and a Newton scheme enhanced by step-size control prevent stability issues related to local minima in the energy landscape and the computation of derivatives. Numerical techniques for the construction of continuous derivatives of the approximated rank-one convex envelope are discussed. A series of numerical experiments demonstrates the ability of the computationally relaxed model to capture softening effects and the mesh independence of the computed approximations. An interpretation in terms of microstructural damage evolution is given, based on the rank-one lamination process.
Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
Venue: arXiv cs.AI 2023
Year: 2023

For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the 'holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm based on dynamic programming (DP). While DP is not new, it has typically been implemented as a problem-specific method. We propose Dynamic Programming Description Language (DyPDL), a formalism to define DP models, and develop Cost-Algebraic A* Solver for DyPDL (CAASDy), a generic solver for DyPDL using state space search. We formalize existing problem-specific DP and state space search methods for combinatorial optimization problems as DP models in DyPDL. Using CAASDy and commercial MIP and CP solvers, we experimentally compare the DP models with existing MIP and CP models, showing that, despite its nascent nature, CAASDy outperforms MIP and CP on a number of common problem classes.
PatchGT: Transformer over Non-trainable Clusters for Learning Graph Representations
Venue: arXiv cs.LG 2023
Year: 2023

Recently the Transformer structure has shown good performances in graph learning tasks. However, these Transformer models directly work on graph nodes and may have difficulties learning high-level information. Inspired by the vision transformer, which applies to image patches, we propose a new Transformer-based graph neural network: Patch Graph Transformer (PatchGT). Unlike previous transformer-based models for learning graph representations, PatchGT learns from non-trainable graph patches, not from nodes directly. It can help save computation and improve the model performance. The key idea is to segment a graph into patches based on spectral clustering without any trainable parameters, with which the model can first use GNN layers to learn patch-level representations and then use Transformer to obtain graph-level representations. The architecture leverages the spectral information of graphs and combines the strengths of GNNs and Transformers. Further, we show the limitations of previous hierarchical trainable clusters theoretically and empirically. We also prove the proposed non-trainable spectral clustering method is permutation invariant and can help address the information bottlenecks in the graph. PatchGT achieves higher expressiveness than 1-WL-type GNNs, and the empirical study shows that PatchGT achieves competitive performances on benchmark datasets and provides interpretability to its predictions. The implementation of our algorithm is released at our Github repo: https://github.com/tufts-ml/PatchGT.
Analysis of Molecule Harvesting by Heterogeneous Receptors on MC Transmitters
Venue: arXiv cs.ET 2023
Year: 2023

This paper designs a molecule harvesting transmitter (TX) model, where the surface of a spherical TX is covered by heterogeneous receptors with different sizes and arbitrary locations. If molecules hit any receptor, they are absorbed by the TX immediately. Within the TX, molecules are stored in vesicles that are continuously generated and released by the TX via the membrane fusion process. Considering a transparent receiver (RX) and molecular degradation during the propagation from the TX to the RX, we derive the molecule release rate and the fraction of molecules absorbed by the TX as well as the received signal at the RX. Notably, this analytical result is applicable for different numbers, sizes, and locations of receptors, and its accuracy is verified via particle-based simulations. Numerical results show that different vesicle generation rates result in the same number of molecules absorbed by the TX, but different peak received signals at the RX.