OpenRaiser/Intern-Atlas huggingface dataset:
Improved Bounds for Sampling Solutions of Random CNF Formulas
Venue: arXiv cs.DS 2023
Year: 2023

Let $Φ$ be a random $k$-CNF formula on $n$ variables and $m$ clauses, where each clause is a disjunction of $k$ literals chosen independently and uniformly. Our goal is to sample an approximately uniform solution of $Φ$ (or equivalently, approximate the partition function of $Φ$). Let $α=m/n$ be the density. The previous best algorithm runs in time $n^{\mathsf{poly}(k,α)}$ for any $α\lesssim2^{k/300}$ [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. Our result significantly improves both bounds by providing an almost-linear time sampler for any $α\lesssim2^{k/3}$. The density $α$ captures the \emph{average degree} in the random formula. In the worst-case model with bounded \emph{maximum degree}, current best efficient sampler works up to degree bound $2^{k/5}$ [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its average-case counterpart due to our $2^{k/3}$ bound. Our result is the first progress towards establishing the intuition that the solvability of the average-case model (random $k$-CNF formula with bounded average degree) is better than the worst-case model (standard $k$-CNF formula with bounded maximal degree) in terms of sampling solutions.
Neural Generation Meets Real People: Building a Social, Informative Open-Domain Dialogue Agent
Venue: arXiv cs.CL 2023
Year: 2023

We present Chirpy Cardinal, an open-domain social chatbot. Aiming to be both informative and conversational, our bot chats with users in an authentic, emotionally intelligent way. By integrating controlled neural generation with scaffolded, hand-written dialogue, we let both the user and bot take turns driving the conversation, producing an engaging and socially fluent experience. Deployed in the fourth iteration of the Alexa Prize Socialbot Grand Challenge, Chirpy Cardinal handled thousands of conversations per day, placing second out of nine bots with an average user rating of 3.58/5.
A Survey of Explainable Graph Neural Networks: Taxonomy and Evaluation Metrics
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural networks (GNNs) have demonstrated a significant boost in prediction performance on graph data. At the same time, the predictions made by these models are often hard to interpret. In that regard, many efforts have been made to explain the prediction mechanisms of these models from perspectives such as GNNExplainer, XGNN and PGExplainer. Although such works present systematic frameworks to interpret GNNs, a holistic review for explainable GNNs is unavailable. In this survey, we present a comprehensive review of explainability techniques developed for GNNs. We focus on explainable graph neural networks and categorize them based on the use of explainable methods. We further provide the common performance metrics for GNNs explanations and point out several future research directions.
Asymptotic Mutual Information Analysis for Double-scattering MIMO Channels: A New Approach by Gaussian Tools
Venue: arXiv cs.IT 2023
Year: 2023

The asymptotic mutual information (MI) analysis for multiple-input multiple-output (MIMO) systems over double-scattering channels has achieved engaging results, but the convergence rates of the mean, variance, and the distribution of the MI are not yet available in the literature. In this paper, by utilizing the large random matrix theory (RMT), we give a central limit theory (CLT) for the MI and derive the closed-form approximation for the mean and the variance by a new approach -- Gaussian tools. The convergence rates of the mean, variance, and the characteristic function are proved to be O(1/N) for the first time, where N is the number of transmit antennas. Furthermore, the impact of the number of effective scatterers on the mean and variance was investigated in the moderate-to-high SNR regime with some interesting physical insights. The proposed evaluation framework can be utilized for the asymptotic performance analysis of other systems over double-scattering channels.
GPS-GLASS: Learning Nighttime Semantic Segmentation Using Daytime Video and GPS data
Venue: arXiv cs.CV 2023
Year: 2023

Semantic segmentation for autonomous driving should be robust against various in-the-wild environments. Nighttime semantic segmentation is especially challenging due to a lack of annotated nighttime images and a large domain gap from daytime images with sufficient annotation. In this paper, we propose a novel GPS-based training framework for nighttime semantic segmentation. Given GPS-aligned pairs of daytime and nighttime images, we perform cross-domain correspondence matching to obtain pixel-level pseudo supervision. Moreover, we conduct flow estimation between daytime video frames and apply GPS-based scaling to acquire another pixel-level pseudo supervision. Using these pseudo supervisions with a confidence map, we train a nighttime semantic segmentation network without any annotation from nighttime images. Experimental results demonstrate the effectiveness of the proposed method on several nighttime semantic segmentation datasets. Our source code is available at https://github.com/jimmy9704/GPS-GLASS.
On the Effects of Different Types of Label Noise in Multi-Label Remote Sensing Image Classification
Venue: arXiv cs.CV 2023
Year: 2023

The development of accurate methods for multi-label classification (MLC) of remote sensing (RS) images is one of the most important research topics in RS. To address MLC problems, the use of deep neural networks that require a high number of reliable training images annotated by multiple land-cover class labels (multi-labels) has been found popular in RS. However, collecting such annotations is time-consuming and costly. A common procedure to obtain annotations at zero labeling cost is to rely on thematic products or crowdsourced labels. As a drawback, these procedures come with the risk of label noise that can distort the learning process of the MLC algorithms. In the literature, most label noise robust methods are designed for single-label classification (SLC) problems in computer vision (CV), where each image is annotated by a single label. Unlike SLC, label noise in MLC can be associated with: 1) subtractive label-noise (a land cover class label is not assigned to an image while that class is present in the image); 2) additive label-noise (a land cover class label is assigned to an image although that class is not present in the given image); and 3) mixed label-noise (a combination of both). In this paper, we investigate three different noise robust CV SLC methods and adapt them to be robust for multi-label noise scenarios in RS. During experiments, we study the effects of different types of multi-label noise and evaluate the adapted methods rigorously. To this end, we also introduce a synthetic multi-label noise injection strategy that is more adequate to simulate operational scenarios compared to the uniform label noise injection strategy, in which the labels of absent and present classes are flipped at uniform probability. Further, we study the relevance of different evaluation metrics in MLC problems under noisy multi-labels.
Generating Teammates for Training Robust Ad Hoc Teamwork Agents via Best-Response Diversity
Venue: arXiv cs.LG 2023
Year: 2023

Ad hoc teamwork (AHT) is the challenge of designing a robust learner agent that effectively collaborates with unknown teammates without prior coordination mechanisms. Early approaches address the AHT challenge by training the learner with a diverse set of handcrafted teammate policies, usually designed based on an expert's domain knowledge about the policies the learner may encounter. However, implementing teammate policies for training based on domain knowledge is not always feasible. In such cases, recent approaches attempted to improve the robustness of the learner by training it with teammate policies generated by optimising information-theoretic diversity metrics. The problem with optimising existing information-theoretic diversity metrics for teammate policy generation is the emergence of superficially different teammates. When used for AHT training, superficially different teammate behaviours may not improve a learner's robustness during collaboration with unknown teammates. In this paper, we present an automated teammate policy generation method optimising the Best-Response Diversity (BRDiv) metric, which measures diversity based on the compatibility of teammate policies in terms of returns. We evaluate our approach in environments with multiple valid coordination strategies, comparing against methods optimising information-theoretic diversity metrics and an ablation not optimising any diversity metric. Our experiments indicate that optimising BRDiv yields a diverse set of training teammate policies that improve the learner's performance relative to previous teammate generation approaches when collaborating with near-optimal previously unseen teammate policies.
Locally-iterative $(Δ+1)$-Coloring in Sublinear (in $Δ$) Rounds
Venue: arXiv cs.DS 2023
Year: 2023

Distributed graph coloring is one of the most extensively studied problems in distributed computing. There is a canonical family of distributed graph coloring algorithms known as the locally-iterative coloring algorithms, first formalized in the seminal work of [Szegedy and Vishwanathan, STOC'93]. In such algorithms, every vertex iteratively updates its own color according to a predetermined function of the current coloring of its local neighborhood. Due to the simplicity and naturalness of its framework, locally-iterative coloring algorithms are of great significance both in theory and practice. In this paper, we give a locally-iterative $(Δ+1)$-coloring algorithm with $O(Δ^{3/4}\logΔ)+\log^*n$ running time. This is the first locally-iterative $(Δ+1)$-coloring algorithm with sublinear-in-$Δ$ running time, and answers the main open question raised in a recent breakthrough [Barenboim, Elkin, and Goldberg, JACM'21]. A key component of our algorithm is a locally-iterative procedure that transforms an $O(Δ^2)$-coloring to a $(Δ+O(Δ^{3/4}\logΔ))$-coloring in $o(Δ)$ time. Inside this procedure we work on special proper colorings that encode (arb)defective colorings, and reduce the number of used colors quadratically in a locally-iterative fashion. As a main application of our result, we also give a self-stabilizing distributed algorithm for $(Δ+1)$-coloring with $O(Δ^{3/4}\logΔ)+\log^*n$ stabilization time. To the best of our knowledge, this is the first self-stabilizing algorithm for $(Δ+1)$-coloring with sublinear-in-$Δ$ stabilization time.
NFFT.jl: Generic and Fast Julia Implementation of the Nonequidistant Fast Fourier Transform
Venue: arXiv cs.MS 2023
Year: 2023

The non-equidistant fast Fourier transform (NFFT) is an extension of the famous fast Fourier transform (FFT), which can be applied to non-equidistantly sampled data in time/space or frequency domain. It is an approximative algorithm that allows to control the approximation error in such a way that machine precision is reached while keeping the algorithmic complexity in the same order as a regular FFT. The NFFT plays a major role in many signal processing applications and has been intensively studied from a theoretical and computational perspective. The fastest CPU implementations of the NFFT are implemented in the low-level programming languages C and C++ and require a compromise between code generalizability, code readability, and code efficiency. The programming language Julia promises new opportunities in optimizing these three conflicting goals. In this work we show that Julia indeed allows to develop an NFFT implementation, which is completely generic, dimension-agnostic and requires about 2-3 times less code than other famous libraries while still being one of the fastest NFFT implementations developed to date.
UAVM: Towards Unifying Audio and Visual Models
Venue: arXiv cs.CV 2023
Year: 2023

Conventional audio-visual models have independent audio and video branches. In this work, we unify the audio and visual branches by designing a Unified Audio-Visual Model (UAVM). The UAVM achieves a new state-of-the-art audio-visual event classification accuracy of 65.8% on VGGSound. More interestingly, we also find a few intriguing properties of UAVM that the modality-independent counterparts do not have.
Quality Evaluation of Arbitrary Style Transfer: Subjective Study and Objective Metric
Venue: arXiv cs.CV 2023
Year: 2023

Arbitrary neural style transfer is a vital topic with great research value and wide industrial application, which strives to render the structure of one image using the style of another. Recent researches have devoted great efforts on the task of arbitrary style transfer (AST) for improving the stylization quality. However, there are very few explorations about the quality evaluation of AST images, even it can potentially guide the design of different algorithms. In this paper, we first construct a new AST images quality assessment database (AST-IQAD), which consists 150 content-style image pairs and the corresponding 1200 stylized images produced by eight typical AST algorithms. Then, a subjective study is conducted on our AST-IQAD database, which obtains the subjective rating scores of all stylized images on the three subjective evaluations, i.e., content preservation (CP), style resemblance (SR), and overall vision (OV). To quantitatively measure the quality of AST image, we propose a new sparse representation-based method, which computes the quality according to the sparse feature similarity. Experimental results on our AST-IQAD have demonstrated the superiority of the proposed method. The dataset and source code will be released at https://github.com/Hangwei-Chen/AST-IQAD-SRQE
Graph Neural Network with Local Frame for Molecular Potential Energy Surface
Venue: arXiv cs.LG 2023
Year: 2023

Modeling molecular potential energy surface is of pivotal importance in science. Graph Neural Networks have shown great success in this field. However, their message passing schemes need special designs to capture geometric information and fulfill symmetry requirement like rotation equivariance, leading to complicated architectures. To avoid these designs, we introduce a novel local frame method to molecule representation learning and analyze its expressivity. Projected onto a frame, equivariant features like 3D coordinates are converted to invariant features, so that we can capture geometric information with these projections and decouple the symmetry requirement from GNN design. Theoretically, we prove that given non-degenerate frames, even ordinary GNNs can encode molecules injectively and reach maximum expressivity with coordinate projection and frame-frame projection. In experiments, our model uses a simple ordinary GNN architecture yet achieves state-of-the-art accuracy. The simpler architecture also leads to higher scalability. Our model only takes about 30% inference time and 10% GPU memory compared to the most efficient baselines.
Benchmarking Visual-Inertial Deep Multimodal Fusion for Relative Pose Regression and Odometry-aided Absolute Pose Regression
Venue: arXiv cs.CV 2023
Year: 2023

Visual-inertial localization is a key problem in computer vision and robotics applications such as virtual reality, self-driving cars, and aerial vehicles. The goal is to estimate an accurate pose of an object when either the environment or the dynamics are known. Absolute pose regression (APR) techniques directly regress the absolute pose from an image input in a known scene using convolutional and spatio-temporal networks. Odometry methods perform relative pose regression (RPR) that predicts the relative pose from a known object dynamic (visual or inertial inputs). The localization task can be improved by retrieving information from both data sources for a cross-modal setup, which is a challenging problem due to contradictory tasks. In this work, we conduct a benchmark to evaluate deep multimodal fusion based on pose graph optimization and attention networks. Auxiliary and Bayesian learning are utilized for the APR task. We show accuracy improvements for the APR-RPR task and for the RPR-RPR task for aerial vehicles and hand-held devices. We conduct experiments on the EuRoC MAV and PennCOSYVIO datasets and record and evaluate a novel industry dataset.
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
Venue: arXiv cs.CL 2023
Year: 2023

In-context learning refers to the ability of a model to condition on a prompt sequence consisting of in-context examples (input-output pairs corresponding to some task) along with a new query input, and generate the corresponding output. Crucially, in-context learning happens only at inference time without any parameter updates to the model. While large language models such as GPT-3 exhibit some ability to perform in-context learning, it is unclear what the relationship is between tasks on which this succeeds and what is present in the training data. To make progress towards understanding in-context learning, we consider the well-defined problem of training a model to in-context learn a function class (e.g., linear functions): that is, given data derived from some functions in the class, can we train a model to in-context learn "most" functions from this class? We show empirically that standard Transformers can be trained from scratch to perform in-context learning of linear functions -- that is, the trained model is able to learn unseen linear functions from in-context examples with performance comparable to the optimal least squares estimator. In fact, in-context learning is possible even under two forms of distribution shift: (i) between the training data of the model and inference-time prompts, and (ii) between the in-context examples and the query input during inference. We also show that we can train Transformers to in-context learn more complex function classes -- namely sparse linear functions, two-layer neural networks, and decision trees -- with performance that matches or exceeds task-specific learning algorithms. Our code and models are available at https://github.com/dtsip/in-context-learning .
Boosted Off-Policy Learning
Venue: arXiv cs.LG 2023
Year: 2023

We propose the first boosting algorithm for off-policy learning from logged bandit feedback. Unlike existing boosting methods for supervised learning, our algorithm directly optimizes an estimate of the policy's expected reward. We analyze this algorithm and prove that the excess empirical risk decreases (possibly exponentially fast) with each round of boosting, provided a ''weak'' learning condition is satisfied by the base learner. We further show how to reduce the base learner to supervised learning, which opens up a broad range of readily available base learners with practical benefits, such as decision trees. Experiments indicate that our algorithm inherits many desirable properties of tree-based boosting algorithms (e.g., robustness to feature scaling and hyperparameter tuning), and that it can outperform off-policy learning with deep neural networks as well as methods that simply regress on the observed rewards.
Implicit Two-Tower Policies
Venue: arXiv cs.LG 2023
Year: 2023

We present a new class of structured reinforcement learning policy-architectures, Implicit Two-Tower (ITT) policies, where the actions are chosen based on the attention scores of their learnable latent representations with those of the input states. By explicitly disentangling action from state processing in the policy stack, we achieve two main goals: substantial computational gains and better performance. Our architectures are compatible with both: discrete and continuous action spaces. By conducting tests on 15 environments from OpenAI Gym and DeepMind Control Suite, we show that ITT-architectures are particularly suited for blackbox/evolutionary optimization and the corresponding policy training algorithms outperform their vanilla unstructured implicit counterparts as well as commonly used explicit policies. We complement our analysis by showing how techniques such as hashing and lazy tower updates, critically relying on the two-tower structure of ITTs, can be applied to obtain additional computational improvements.
CathSim: An Open-source Simulator for Endovascular Intervention
Venue: arXiv cs.RO 2023
Year: 2023

Autonomous robots in endovascular operations have the potential to navigate circulatory systems safely and reliably while decreasing the susceptibility to human errors. However, there are numerous challenges involved with the process of training such robots, such as long training duration and safety issues arising from the interaction between the catheter and the aorta. Recently, endovascular simulators have been employed for medical training but generally do not conform to autonomous catheterization. Furthermore, most current simulators are closed-source, which hinders the collaborative development of safe and reliable autonomous systems. In this work, we introduce CathSim, an open-source simulation environment that accelerates the development of machine learning algorithms for autonomous endovascular navigation. We first simulate the high-fidelity catheter and aorta with a state-of-the-art endovascular robot. We then provide the capability of real-time force sensing between the catheter and the aorta in simulation. Furthermore, we validate our simulator by conducting two different catheterization tasks using two popular reinforcement learning algorithms. The experimental results show that our open-source simulator can mimic the behaviour of real-world endovascular robots and facilitate the development of different autonomous catheterization tasks. Our simulator is publicly available at https://github.com/robotvisionlabs/cathsim.
Super-Wideband Massive MIMO
Venue: arXiv cs.IT 2023
Year: 2023

We present a unified model for connected antenna arrays with a large number of tightly integrated (i.e., coupled) antennas in a compact space within the context of massive multiple-input multiple-output (MIMO) communication. We refer to this system as tightly-coupled massive MIMO. From an information-theoretic perspective, scaling the design of tightly-coupled massive MIMO systems in terms of the number of antennas, the operational bandwidth, and form factor was not addressed in prior art. We investigate this open research problem using a physically consistent modeling approach for far-field (FF) MIMO communication based on multi-port circuit theory. In doing so, we turn mutual coupling (MC) from a foe to a friend of MIMO systems design, thereby challenging a basic percept in antenna systems engineering that promotes MC mitigation/compensation. We show that tight MC widens the operational bandwidth of antenna arrays thereby unleashing a missing MIMO gain that we coin "bandwidth gain". Furthermore, we derive analytically the asymptotically optimum spacing-to-antenna-size ratio by establishing a condition for tight coupling in the limit of large-size antenna arrays with quasi-continuous apertures. We also optimize the antenna array size while maximizing the achievable rate under fixed transmit power and inter-element spacing. Then, we study the impact of MC on the achievable rate of MIMO systems under line-of-sight (LoS) and Rayleigh fading channels. These results reveal new insights into the design of tightly-coupled massive antenna arrays as opposed to the widely-adopted "disconnected" designs that disregard MC by putting faith in the half-wavelength spacing rule.